华东交大数据结构自测卷及答案

（大数据）华东交大数据结构自测卷及答案第一章绪论一、填空题1.算法的计算量的大小称为计算的（BA．效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（C）A．问题的规模B.待处理数据的初态C.A和B3.计算机算法指的是（CB）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4．从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构5．以下与数据的存储结构无关的术语是（DA．循环队列B.链表C.哈希表D.栈6．以下数据结构中，哪一个不是线性结构（B）？A．广义表B.二叉树C.稀疏矩阵D.串7．以下那一个术语与数据的存储结构无关？（A）A．栈B.哈希表C.线索树D.双向链表8．在下面的程序段中，对x的赋值语句的频度为（C）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)9．程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFA[j]>A[j+1]THENA[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（D）A.O（n）B.O(nlogn)C.O(n3)D.O(n2)10．以下哪个数据结构不是多型数据类型（D）A．栈B．广义表C．有向图D．字符串11A）是非线性数据结构A．树B．字符串C．队D．栈12.C）是非线性数据结构。A．栈B.队列C.完全二叉树D.堆13．连续存储设计时，存储单元的地址（AA．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续14．以下属于逻辑结构的是（CA．顺序表B.哈希表C.有序表D.单链表二、判断题1.数据元素是数据的最小单位。(F)2.记录是数据处理的最小单位。(T)3.数据的逻辑结构是指数据的各数据项之间的逻辑关系；(F)4．算法的优劣与算法描述语言无关，但与所用计算机有关。(F)5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(T)6C语言或PASCAL际上就是程序了。(T)7．程序一定是算法。(T)8．数据的物理结构是指数据在计算机内的实际存储形式。(T)9.数据结构的抽象操作的定义与具体实现有关。(F)10.在顺序存储结构中，有时也存储数据结构中元素之间的关系。(F)11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(F)12.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(T)13.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(F)三、填空1．数据的物理结构包括数据元素的表示和数据关系的表示。2.对于给定的n个元素,可以构造出的逻辑结构有集合，线性，树___四种。3．数据的逻辑结构是指数据元素之间的逻辑关系。4．一个数据结构在计算机中表示称为存储结构。5．抽象数据类型的定义仅取决于它的一组__逻辑特性_，而与_其在计算机内部如何表示和实现__数学特性_6．数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度7.数据结构是研讨数据的_逻辑结构_和_物理结构_结构定义相应的_操作_，设计出相应的算法_。8．一个算法具有5个特性:有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出。9．已知如下程序段for(i=n;i>=1;i--){语句1}{x=x+1；{语句2}for(j=n;j>i;j--){语句3}y=y+1;{语句4}}；语句1执行的频度为n+1；语句2执行的频度为n；语句3执行的频度为n（n+1）/2；语句4执行的频度为(n-1)n/2。10．在下面的程序段中，对ｘ的赋值语句的频度为(n3+3n2+2n)/6_____（表示为n的函数）for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)ｘ：＝ｘ＋delta；11.下面程序段中带下划线的语句的执行次数的数量级是：log2ni=1;while(i<n)i=i*2;12.下面程序段中带下划线的语句的执行次数的数量级是(nlog2n)。i=1;while(i<n){for(j=1;j<=n;j++)x=x+1;i=i*2}13.下面程序段中带有下划线的语句的执行次数的数量级是(log2n)i=n*nwhile(i!=1)i=i/2;14.计算机执行下面的语句时，语句s的执行次数为__(n+3)(n-2)/2_____。for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;15.下面程序段的时间复杂度为__n1/2______。(n>1)sum=1；for(i=0;sum<n;i++)sum+=i;四、应用题1并指出它们分别属于何种结构。（注意：<>表示有方向，（）表示无方向）（1）、A=（K，R），其中：K={a,b,c,d,e,,f,g,h}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g.h>}（2）、B=（K，R），其中：K={a,b,c,d,e,f,g,h}R={r}r={<d,b>，<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e.f>}（3）、C=(K,R),其中:K={1,2,3,4,5,6},R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}线性表、栈和队列测试题姓名班级学号一、选择题（共25分）（B）1、下面关于线性表的叙述中，错误的是哪一个？A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。（A2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表（C3n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)（B）4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;（B）5、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head->next==NULLC．head->next==headD．head->NULL（B）6.栈中元素的进出原则是A．先进先出B.后进先出C栈空则进D栈满则出（C）7.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．iＢ．n=iＣ．n-i+1Ｄ．不确定（B）8.判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（A）9.判定一个队列QU（最多元素为m0）为满队列的条件是Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1（D10为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f;n＋f－r）%n;（Ｃ）n＋r－f;n＋r－f）%n11.设有4个数据元素a1a2a3和a4栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是②，第二次出栈得到的元素是④再进队两次，出队一次；这时，第一次出队得到的元素是①，第二次出队得到的元素是②。经操作后，最后在栈中或队中的元素还有②个。供选择的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答：A、B、C、D、E分别为、、、、12.AA[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值B；从栈中弹出（POP）一个元素时，变量T的值C。设栈空时，有输入序列a，b，c，经过PUSH，POPPUSHPUSHPOPDT的值是E。供选择的答案：A：①先进先出②后进先出③进优于出④出优于进⑤随机进出B，C：①加1②减1③不变④清0⑤加2⑥减2D：①a,b②b,c③c,a④b,a⑤c,b⑥a,cE：①n+1②n+2③n④n-1⑤n-2答：A、B、C、D、E分别为②、②、①、⑥、④13.在做进栈运算时，应先判别栈是否A；在做退栈运算时，应先判别栈是否Bn个，做进栈运算时发生上溢，则说明该栈的最大容量为C。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的D分别设在这片内存空间的两端，这样，只有当E时，才产生上溢。供选择的答案：A，B：①空②满③上溢④下溢C：①n-1②n③n+1④n/2D：①长度②深度③栈顶④栈底E：①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点③两个栈的栈顶在栈空间的某一位置相遇④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底答：A、B、C、D、E分别为②、①、②、④、③二、判断题（共10分）（F）1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（F）2.在表结构中最常用的是线性表，栈和队列不太常用。（T）3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（T）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（F）5.栈和链表是两种不同的数据结构。（F）6.栈和队列是一种非线性数据结构。（T）7.栈和队列的存储方式既可是顺序方式，也可是链接方式。（T）8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（F）9.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（F）10.一个栈的输入序列是12345，则栈的输出序列不可能是12345。三、填空题（共20分）1.线性表、栈和队列都是线性结构，可以在线性表的任意位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队头删除元素。2.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶允许插入和删除运算的一端称为栈底。3.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4.在一个循环队列中，队首指针指向队首元素的当前位置。5.在具有n个单元的循环队列中，队满时共有n-1个元素。6.向栈中压入元素的操作是先插入数据，后移动指针。7.从循环队列中删除一个元素时，其操作是先读取元素，后移动指针。8.带表头结点的空循环双向链表的长度等于0。9．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是__23123*2-4/345*7/++1089/+_____10LP结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a.在P结点后插入S结点的语句序列是：(4)(1)。b.在P结点前插入S结点的语句序列是：711841。c.在表首插入S结点的语句序列是：512。d.在表尾插入S结点的语句序列是：916。供选择的语句有：（1）P->next=S;（2）P->next=P->next->next;（3）P->next=S->next;（4）S->next=P->next;（5）S->next=L;（6）S->next=NULL;（7）Q=P;（8）while(P->next!=Q)P=P->next;（9）while(P->next!=NULL)P=P->next;（10）P=Q;（11）P=L;（12）L=S;（13）L=P;四、简答题(共15分)1、说明线性表、栈与队的异同点。2、顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？3、设循环队列的容量为40（序号从0到39算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？五、算法设计（共30分）1、写一算法，从顺序表中删除自第i个元素开始的k个元素。StatusDelete_k(SqlistL,inti,intk){if(i<0||i>L.length||i+k>L.length)returnerror;for(intj=i+k;j<L.length;j++){L.elem[j-k]=L.elem[j];}L.length-=k;returnOK;}2、试写一个算法，判别读入的一个以‘@’为结束符的字符序列是否是“回文。“回文是回文，‘abcde’和‘ababab’StatusHuiWen(chars[]){inti=0;SqStackS;InitStack(S);while(s[i]!='@'){Push(S,s[i]);cout<<"push"<<s[i];i++;}i=0;while(s[i]!='@'){chare;Pop(S,e);cout<<e<<"*"<<s[i];if(e!=s[i])break;i++;}if(s[i]=='@')return1;//返回结果1表示是回文，0表示不是回文elsereturn0;}3、假设有一个循环链表的长度大于1s为s所指结点的前趋结点。StatusDelete(LinkLists){p=s;while(p->next->next!=s)//查找s的前一个结点的前一个结点；p=p->next;q=p->next;p->next=s;deleteq;returnOK;}第6章树和图自测卷姓名班级学号题号一二三四五总分题分1017174016100得分一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（）2.二叉树中每个结点的两棵子树的高度差等于1。（）3.二叉树中每个结点的两棵子树是有序的。（）4.二叉树中每个结点有两棵非空子树或有两棵空子树。（）5.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（）6.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i－1个结点。（）7.具有12个结点的完全二叉树有5个度为2的结点。（）8.不同的求最小生成树的方法最后得到的生成树是相同的.9.有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。（）10.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。二、填空（每空1分，共17分）1．由３个结点所构成的二叉树有种形态。2.一棵深度为6的满二叉树有个分支结点和个叶子。3．一棵具有257个结点的完全二叉树，它的深度为。4．设一棵完全二叉树有700个结点，则共有个叶子结点。5.用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是。6.判断一个无向图是一棵树的条件是______。7.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。8.G是一个非连通无向图，共有28条边，则该图至少有______个顶点9.N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。10．在有n个顶点的有向图中，每个顶点的度最大可达______。11．设有一稀疏图G，则G采用存储较省空间。12．设有一稠密图G，则G采用存储较省空间。13．n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若采用邻接表存储时，该算法的时间复杂度为。14．已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。则从顶点0出发按广度优先遍历的结点序列是。三、选择题（每小题1分，共17分）（）1．不含任何结点的空树。（Ａ）是一棵树;（Ｂ）是一棵二叉树;（Ｃ）是一棵树也是一棵二叉树;（Ｄ）既不是树也不是二叉树（）2．二叉树是非线性数据结构，所以。（Ａ）它不能用顺序存储结构存储;（Ｂ）它不能用链式存储结构存储;（Ｃ）顺序存储结构和链式存储结构都能存储;（Ｄ）顺序存储结构和链式存储结构都不能使用（）3.具有n(n>0)个结点的完全二叉树的深度为。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1（）4．把一棵树转换为二叉树后，这棵二叉树的形态是。（Ａ）唯一的（Ｂ）有多种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子（）5.在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2B.1C.2D.4（）7.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A．1/2B.1C.2D.4（）8.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A．栈B.队列C.树D.图（）9.深度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（）10.广度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历11.树是结点的有限集合，它A根结点，记为T。其余的结点分成为m（m≥0）个B的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤mC。供选择的答案A：①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上B:①互不相交②允许相交③允许叶结点相交④允许树枝结点相交C：①权②维数③次数④序答案：A=B=C=12.二叉树ABN的左子女是N在原树里对应结点的C，而N的右子女是它在原树里对应结点的D。供选择的答案A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构B:①左子结点②右子结点③左子结点或者没有右子结点④兄弟C～D：①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟答案：A=B=C=D＝四、阅读分析题（每题5分，共40分）1.给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画该出二叉树2．试写出如图1所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。3.把如图2所示的树转化成二叉树。4.画出图3二叉树相应的森林。5．.已知如图所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。6．请对下图的无向带权图：（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。7．已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。8．给定下列网G:（10分）1试着找出网G的最小生成树，画出其逻辑结构图；2用两种不同的表示法画出网G的存储结构图；3用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。五、算法设计题（前1~5题中任选2题，第6~7题中任选1题，共16分）1.编写递归算法，计算二叉树中叶子结点的数目。2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。3．编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。4.编写按层次顺序（同一层自左至右）遍历二叉树的算法。5.编写算法判别给定二叉树是否为完全二叉树。6．编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。解：StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息，以建立邻接表{returnOK;}//Build_AdjList7.试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？提示：将邻接矩阵的第i行全部置0）解：//设本题中的图G为有向无权图StatusDeleteArc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){}returnOK;}//Delete_Arc答案：一、12345678910√×××××√×√×二、156n个顶点n-1条边的连通图11邻接表231,327n12邻接矩阵398913O(n2)O(n+e)435092(n-1)14533102*(n-1)15三、四、1、答：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。2、答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA3、答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。4、答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。五、1、5、(1)（2）（3）12→1→43→2→64→3→5→65→16→1→2→5（4）1→2→5→62→3→63→44→25→4→66→3→46、解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!邻接矩阵为：043405593505555076549703630252065460PRIM算法（横向变化）：VbcdefghUV-UVexaaaaaaa{a}{b,c,d,e,f,lowcos43∞∞∞∞∞g,h}tVexa0caaac{a,c}{b,d,e,f,g,lowcos45∞∞∞5h}tVex00cbaac{a,c,b}{d,e,f,g,h}lowcos59∞∞5tVex000dddd{a,c,b,d}{e,f,g,h}lowcos7654tVex000ddd0{a,c,b,d,{e,f,g}lowcos765h}tVex000dg00{a,c,b,d,{f,e}lowcos72h,g}tVex000f000{a,c,b,d,{e}lowcos3h,g,f}tVex0000000{a,c,b,d,{}lowcosh,g,f,e}t邻接表为：0a→14→231b→04→25→35→49^2c→03→15→35→75^3d→15→25→47→56→65→74^4e→19→37→53^5f→36→43→62^6g→35→52→76^7h→25→34→66^先罗列：f---2---ga—3--cf—3—ea—4---bd—4—h(a,b,c)(e,f,g)(d,h)取b—5—d,g—5--d就把三个连通分量连接起来了。7、8、1试着找出网G的最小生成树，画出其逻辑结构图；2用两种不同的表示法画出网G的存储结构图；3用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。解：1.最小生成树可直接画出，如右图所示。AB———————C2.可用邻接矩阵和邻接表来描述：邻接表为：0a→112→44^1b→012→220→48→59^2c→120→315→612^3d→215→610^4e→04→18→56^5f→19→46^6g→212→310五、1、intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;//叶子结点elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree2、intGet_Depth(BitreeT)//求子树深度的递归算法{if(!T)return0;else{m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}//Get_Depth3、intGet_Sub_Depth(BitreeT,intx)//求二叉树中以值为x的结点为根的子树深度{if(T->data==x){printf("%d\n",Get_Depth(T));//找到了值为x的结点,求其深度exit1;}}else{if(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_Sub_Depth(T->rchild,x);//在左右子树中继续寻找}}//Get_Sub_Depth4、voidLayerOrder(BitreeT)//层序遍历二叉树{InitQueue(Q);//建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q))

{DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}//LayerOrder5、答：intIsFull_Bitree(BitreeT)//判断二叉树是否完全二叉树,是则返回1,否则返回0{InitQueue(Q);flag=0;EnQueue(Q,T);//建立工作队列while(!QueueEmpty(Q)){{DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;else{EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);//不管孩子是否为空,都入队列}}//whilereturn1;}//IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.6、StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);

scanf("%d",&v);if(v<0)returnERROR;//顶点数不能为负G.vexnum=v;scanf("%d",&a);if(a<0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data=getchar();//输入各顶点的符号for(m=1;m<=a;m++)

{t=getchar();h=getchar();//t为弧尾,h为弧头if((i=LocateVex(G,t))<0)returnERROR;if((j=LocateVex(G,h))<0)returnERROR;//顶点未找到p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;}p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//Build_AdjList7、解：//本题中的图G均为有向无权图。StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;

}returnOK;}//Delete_Arc第9章查找自测卷答案姓名班级A题号一二三四五总分题分1027162423100得分一、填空题（每空1分，共10分）1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。2.a1a2a3a256)k表中与k相等的元素，在查找不成功的情况下，最多需要检索8次。设有100个结点，用二分法查找时，最大比较次数是7。3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为3.7。解：显然，平均查找长度＝O（log2n）<5次（25来计算（即（21×log221/20＝4.6n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，10020，它将依次与表中元素28，6，12，20比较大小。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。6.散列法存储的基本思想是由关键字的值决定数据的存储地址。7.有一个表长为mn（n<m解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是n(n-1)/2=（1＋2＋…＋n-1）。(而任一元素查找次数≤n-1)二、单项选择题（每小题1分，共27分）（B）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（A）2．折半查找有序表（4，6，10，12，20，30，50，70，88，10058，则它将依次与表中比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（C）3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。A．3B．4C．5D．6（A）4.链表适用于查找A．顺序B．二分法C．顺序，也能二分法D．随机（C）5.折半搜索与二叉搜索树的时间性能A.相同B.完全不同C.有时不相同D.数量级都是O（log2n）6．从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。要进行线性查找，则线性表A；要进行二分查找，则线性表B；要进行散列查找，则线性表C。90000时，平均比较次数约为D，最大比较次数为E。供选择的答案：A~C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储④既可以以顺序方式，也可以以链表方式存储⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好D，E：①25000②30000③45000④90000答案：A=④B=⑤C=③D＝③E＝④7.？卷的对应栏内。数据结构反映了数据元素之间的结构关系。链表是一种A，它对于数据元素的插入和删除B。通常查找线性表数据元素的方法有C和D两种方法，其中C是一种只适合于顺序存储结构但E的方法；而D是一种对顺序和链式存储结构均适用的方法。供选择的答案：A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表④非顺序存储线性表

B：①不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针③只需移动结点，不需改变结点指针④既需移动结点，又需改变结点指针C：①顺序查找②循环查找③条件查找④二分法查找D：①顺序查找②随机查找③二分法查找④分块查找E：①效率较低的线性查找②效率较低的非线性查找③效率较高的非线性查找④效率较高的线性查找答案：A＝④B＝②C＝④D＝①E＝③8.？卷的对应栏内。在二叉排序树中，每个结点的关键码值A，B一棵二叉排序，即可得到排序序列。同佳二叉排序，最佳二叉排序树在结构上的特点是C。供选择的答案A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大③比左右子树的所有结点的关键码值都大④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系B:①前序遍历②中序（对称）遍历③后序遍历④层次遍历C：①除最下二层可以不满外，其余都是充满的②除最下一层可以不满外，其余都是充满的③每个结点的左右子树的高度之差的绝对值不大于1④最下层的叶子必须在最左边答案：A＝①B＝②C＝②9.？卷的对应栏内。散列法存储的基本思想是根据A来决定B，碰撞（冲突）指的是C，处理碰撞的两类主要方法是D。供选择的答案A，B：①存储地址②元素的符号③元素个数④关键码值⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间C:①两个元素具有相同序号②两个元素的关键码值不同，而非码属性相同

③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多

D：①线性探查法和双散列函数法②建溢出区法和不建溢出区法

③除余法和折叠法④拉链法和开地址法答案：A＝④B＝①C＝③D＝④10.考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结

点的值。并小于等于其右子树上的一切结点的值。现把9个数123，…，89填入右图所示的二叉树的9此时，n1的值是A，n2的值是B，n9的值是C。现欲把放入此树并使该树保持前述性质，增加的一个结点可以放在D或E。供选择的答案A～C：①1②2③3④4⑤5⑥6⑦7⑧8⑨9D～E：①n7下面②n8下面③n9下面④n6下面⑤n1与n2之间⑥n2与n4之间⑦n6与n9之间⑧n3与n6之间答案：A＝⑦B＝④C＝⑥D＝②E＝⑥三、简答题（每小题4分，共16分）1.找速度必然比线性查找的速度快，这种说法对吗？结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。2.3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1）画出描述折半查找过程的判定树；（2）若查找元素54，需依次与哪些元素比较？（3）若查找元素90，需依次与哪些元素比较？（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。解：（1）先画出判定树如下（注：mid=(1+12)/2=6）：3056337428795(2)查找元素54，需依次与30,63,42,54等元素比较；(3)查找元素90，需依次与30,63,87,95,72等元素比较；（4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.083.用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?

如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（14.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：（1）画出哈希表的示意图；（2）若查找关键字63，需要依次与哪些关键字进行比较？（3）若查找关键字60，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：（1）画表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（360,首先要与H(60)=60%16=1212（4）对于黑色数据元素，各比较1次；共6次；“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.454≈1.55四、分析题（每小题6分，共24分）1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。解：判定树应当描述每次查找的位置：528136947102.在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。答：127174913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，213.已知如下所示长度为12的表：（Jan,Feb,Mar,A