数据结构

数据结构二、填空题(共30题)1、若用一个大小为8的数组来实现循环队列,且当rear和front的值分别为0,5。当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为（______）。考生答案：6,42、在一个长度为m的顺序表中,如果要在第i个元素后插入一个元素,要后移（______）个元素。考生答案：m-i3、对于一个具有n个结点的二叉树,当它为一棵（______）二叉树时具有最小高度,即为（______）；它具有的最大高度是（______）考生答案：完全log2n+1n4、下列程序段的时间复杂度是（______）for(i=1;i=n;i+=2)for(j=1;j=m;j++)x=x+1;考生答案：O(m*n)5、设有向无环图G中的有向边集合E={a,b,a,c,d,b,d,e},请写出该有向图G的一种拓扑排序序列（______）考生答案：ACDEB([答案]不唯一)6、具有n个叶子结点的哈夫曼数的总结点个数是（______）考生答案：2n-17、设有一组初始记录关键字序列为(34,76,45,18,26,54,92),则由这组记录关键字生成的二叉排序树的深度为（______）考生答案：48、若一组记录的排序码值序列为{50,80,30,40,70,60}利用快速排序方法,以第一个记录为基准,得到一趟快速排序的结果为（______）考生答案：40,30,50,80,70,609、已知有向图的邻接表如下图所示图则该图中从结点1出发的广度优先遍历序列是（______）,深度优先遍历序列是（______）。考生答案：1,3,2,4,5##1,3,4,5,210、在顺序表（3,10,13,18,24,29,31,38,45,49,56）中,用二分（折半）法查找关键码20,需做的关键码比较次数为（______）考生答案：411、设有一个顺序栈S,元素A,B,C,D,E,F,依次进栈,如果六个元素出栈的顺序是B,D,C,F,E,A,则栈的容量至少应是（______）考生答案：312、在一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动（______）个元素考生答案：n-i13、对于一棵具有n个结点的二叉树,当进行链接存储时,其二叉链表中的指针域的总数为（______）个,其中（______）个用于链接孩子结点（______）个空闲着。考生答案：2nn-1n+114、程序段i=1；while(i=n)i=i*2；的时间复杂度是（______）考生答案：O(log2n15、假定一个有向图的顶点集为{a,b,c,d,e,f},边集为{a,c,a,e,c,f,d,c,e,b,e,d},则出度为0的顶点个数为（______）,入度为1的顶点个数为（______）。考生答案：2416、已知二叉树如下图所示图该二叉树的前序遍历序列是（______）,中序遍历序列事（______）,后序遍历序列是（______）考生答案：ABDCEFGDBAFGECDBGFECA17、在对一组记录(53,41,96,22,16,75,61,46,88)进行堆排序时,根据初始记录构成初始堆（大根堆）后,这组记录的顺序变为（______）考生答案：96,88,75,46,16,53,61,41,2218、已知一个有向图的边集为{a,b,a,c,a,d,b,d,b,e,d,e},则由该图产生的一种可能的拓扑序列为(______)考生答案：abcde19、设一个顺序有序表A[1:14]中有14个元素,则采用二分法查找元素A[10]的过程中比较元素的顺序为(______)考生答案：A[7],A[11],A[9],A[10]20、假定一棵二叉树的结点数为35,则它的最小深度为(______),最大深度为(______)。考生答案：63521、假设S和X分别表示进栈和出栈操作,由输入序列“XYZ”得到输出序列“YZX”的操作序列为SSXSXX,则由“ABCDEF”得到“CDBFEA”的操作序列为（______）考生答案：SSSXSXXSSXXX22、一个采用了顺序存储结构的线性表,其长度为20,若在第5个元素前插入一个元素,需要移动（______）个元素,若接着又将第10个元素删除,那么需要移动（______）个元素考生答案：161123、对有27个结点的完全二叉树的结点以从上至下从左至右的顺序进行从1开始编号后,序号最小的叶结点的序号为（______）考生答案：1424、程序段for(i=1;i=n;)i=i*5；的时间复杂度是（______）考生答案：O(log5n)25、已知二叉树的前序遍历序列为ABDCEF,中序遍历序列为DBAEFC,则它的后序遍历序列为（______）考生答案：DBFECA26、已知有向图G的边集为{1,2,2,4,3,2,2,4,5,4},写出图G的一个拓扑排序序列（______）考生答案：13254（[答案]不唯一）27、在具有m个单元的循环队列中,队头指针为front,队尾指针为rear,则队满的条件是（______）考生答案：(rear+1)%m==front28、对关键字序列(51,11,47,77,12,27,64,20)进行快速排序,使关键字降序排列,那么以第一个元素为划分基准,进行第一趟扫描后得到的关键字序列为（______）。考生答案：647751471227112029、已知有序表为（13,19,23,36,45,56,68,82,91,114,133）,当用折半查找82时,需进行（______）次查找可确定成功考生答案：430、在对一组记录(13,25,3,9,38,17,46,29,6,31)进行希尔(shell)排序时,取d=3,则一趟希尔排序后记录变为（______）。考生答案：（9,25,3,13,29,6,31,38,17,46）三、简答题(共17题)31、已知二叉树的先序遍历序列为ABDGCEFH,中序遍历序列为DGBAECFH,请完成下面两题:（1）用括号法表示出这棵二叉树（可用#表示空树）（2）写出这棵二叉树的后序遍历序列。考生答案：（1）A(B(D(#,G),#),C(E,F(#,H)))/pp（2）GDBEHFCA32、一个无向图如下图所示,要求使用Kruskal算法生成一棵最小生成树。图请按顺序写出生成最小生成树中各条边的过程。用（1,2）20这种形式表示图中顶点1和顶点2之间的边,权值为20。考生答案：（2,3）5（2,4）6（1,6）9（6,5）10（2,6）11/pp（也可用（3,4）6代替（2,4）6,用（1,5）10代替（6,5）10）33、假定用于通信的电文仅由8个字母a,b,c,d,e,f,g,h组成,各个字母在电文中出现的频率分别为37,10,4,8,24,13,5,3。试为这8个字母设计不等长Huffman编码。考生答案：a:01b:101c:00011d:100e:11f:001g:0000h:0001034、已知数据序列{13,3,17,31,29,11,18,21,7,19},写出希尔排序每一趟排序的结果。（设d=5、2、1）考生答案：113177191318213129/pp133177181319213129/pp37111317181921293135、阅读以下程序:typedefstructnode{intdata;structnode*next;}Lnode,*LinkList;voidfun(LinkListhead){Lnode*p,*q;p=q=head-next;if(p==NULL)return;p=p-next;q-next=NULL;while(p!=NULL){q=p-next;p-next=head-next;head-next=p;p=q;}}请写出函数fun的功能。考生答案：使带头节点的链表倒序存放36、已知有n个顶点的有向图邻接表,编写一个函数求出该图中指定顶点的出度。已知边类型edgenode,包含next（指向下一条边）和adjvex（序号）成员。类型adjlist表示顶点数组类型,每个数组元素包含link（指向第一条边）和vex成员。考生答案：37、若以{3,5,6,9,10}作为叶子结点的权值构造哈夫曼树,（1）用括号表示法表示出这棵哈夫曼树（2）求出其带权路径长度考生答案：（1）33（14（6,8（3,5））,19（9,10））/pp（2）带权路径长度为:（3+5）*3+（6+9+10）*2=7438、已知图的邻接表如下所示图请写出该图从顶点1出发的深度优先遍历序列和广度优先遍历序列。考生答案：深度:12534768910/pp广度:1234567891039、设有一组关键字(20,2,24,15,56,19,85,28,69,12,11,32),采用哈希函数:H(key)=key%13,采用开放地址法的线性探测再散列方法解决冲突,试在0~18的散列地址空间中对该关键字序列构造哈希表。（1）写出每一个关键字在哈希表中的地址。（2）计算哈希查找在等概率查找成功的情况的平均查找长度ASL。考生答案：(1)20的地址:72的地址:224的地址:1115的地址:356的地址:419的地址:685的地址:828的地址:069的地址:512的地址:1211的地址:1332的地址:9(2)ASL=（7*1+3*2+1*3+1*4）/12=20/12=1.66740、已知图G如下所示图从顶点v1出发,按照普里姆算法生成最小生成树中各边的次序写出各条边。用（1,2）6这种形式表示图中顶点1和顶点2之间的边,权值为6。考生答案：(1,2)6,(2,7)4,(7,3)9,/pp(3,4)5,(4,5)10(1,6)1241、阅读以下程序:typedefstructnode{intdata;structnode*lchild;structnode*rchild;}BTNode;intfun(BTNode*root){intm,n;if(root==NULL)return0;m=fun(root-lchild);n=fun(root-rchild);returnmn?m+1:n+1;}请写出函数fun的功能。考生答案：fun的功能是求出二叉树的深度。42、若一个无向连通图以邻接表作为存储结构,请设计一个函数,功能是删除图中的一条边(i,j)。已知边类型EdgNd,包含next和adjvex（序号）成员。类型AdjList表示顶点数组类型,每个数组元素包含first（指针成员）。考生答案：43、由字符集{A,B,C,D,E,F,G,H}及其在电文中出现的频度构建的哈夫曼树如下图所示。（1）请写出每个字符的哈夫曼编码。（2）已知某段电文的哈夫曼编码为1110010100011001000010001001001101,请根据该哈夫曼树进行译码,写出原来的电文。考生答案：44、已知图G的邻接表如下图所示:图请写出从顶点0出发,该图的深度优先遍历序列和广度优先遍历序列。考生答案：深度优先遍历序列为:054321/pp广度优先遍历序列为:05421345、已知一表为（43,21,67,9,40,78,2,41,70,90）,按表中顺序依次插入初始为空的二叉排序树,要求:（1）用括号法表示建立的二叉排序树（用#表示空树）。（2）求出在等概率情况下查找成功的平均查找长度。考生答案：（1）43（21（9（2,#）,40（#,41））,67(#,78(70,90))）/pp（2）ASL=(1+2*2+3*3+4*4)/10=346、阅读以下程序:typedefstructnode{intdata;structnode*lchild;structnode*rchild;}BTNode;intfun(BTNode*b){intnum1,num2;if(b==