2019年《数据结构》期末考试试题及答案

2019数据结构期末考试试题及答案数据结构期末考试试题及答案数据结构期末考试试题及答案12试题1答案7数据结构期末考试试题及答案29试题2答案14数据结构期末考试试题及答案31.6试题辂案21第23页共23页数据结构期末考试试题及答案1、单选题（每题2分，共20分）1.栈和队列的共同特点是（）。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2 .用链接方式存储的队列，在进行插入运算时（）.A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3 .以下数据结构中哪一个是非线性结构？（）A.队列B.栈C.线性表D.二叉树4 .设有一个二维数组Amn,假设A0存放位置在644（10）,A22存放位置在676（10）,每个元素占一个空间，问A33（10）存放在什么位置？脚注（10）表示用10进制表示。A. 688B. 678C. 692D. 6965 .树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6 .二叉树的第k层的结点数最多为（）.A.2k-1B.2K+1C.2K-1D.2k-17 .若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为（）A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,38 .对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A.O(1)B.O(n)C.O(1og2n)D.O(n2)9 .对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有()个，A.1B.2C.3D.410.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8二、填空题(每空1分，共26分)1 .通常从四个方面评价算法的质量：、和2 .一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为3 .假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J),则树中所含的结点数为个，树的深度为,树的度为4 .后缀算式923+-102/-的值为。中缀算式(3+4X)-2Y/3对应的后缀算式为5 .若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有个指针域，其中有个指针域是存放了地址，有个指针是空指针。6 .对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有n和个。7 .AOV网是一种的图。8 .在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边。9 .假定一个线性表为(12,23,74,55,63,40),若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为、口10 .向一棵B树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度。11 .在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为,整个堆排序过程的时间复杂度为。605078903440357204112.在快速排序、堆排序、归并排序中，排序是稳定的。三、运算题（每题6分，共24分）1.在如下数组A中链接存储了一个线性表，表头指针为A0.next,试写出该线性表。datanext012345672 .请画出图10的邻接矩阵和邻接表3 .已知一个图的顶点集V和边集E分别为：(12)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20V=1,2,3,4,5,6,7);,J9E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,图10(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4 .画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。四、阅读算法(每题7分，共14分)1. LinkListmynote(LinkListL)/L是不带头结点的单链表的头指针if(L&L-next)q=L;L=Lnext;p=L;51: while(pnext)p=pnext；52: pnext=q；qnext=NULL;returnL；请回答下列问题：1. (1)查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结点(3)返回的线性表为(a2,a3,an,a1)(1)说明语句S1的功能；(2)说明语句组S2的功能；(3)设链表表示的线性表为(a1,空,an),写出算法执行后的返回值所表示的线性表。2. voidABC(BTNode*BT)ifBTABC(BT-left);ABC(BT-right);coutdatadata)让em=BST-data;/S找成功return;elseif(itemdata)returnFind(,item);elsereturnFind(,item);/if6、 编写算法(共8分)统计出单链表HL中结点的值等于给定值X的结点数intCountX(LNode*HL,ElemTypex)试题1答案1、 单选题(每题2分，共20分)1 .A2.D3.D4.C5.C6.D7.D8.C9.D10.A2、 填空题(每空1分，共26分)1. 正确性易读性强壮性高效率2. O(n)3. 9334. -134X*+2Y*3/-5. 2nn-1n+16. e2e7. 有向无回路8. n(n-1)/2n(n-1)9. (12,40)()(74)(23,55,63)10. 增加111.O(log2n)O(nlog2n)12. 归并3、 运算题(每题6分，共24分)1 .线性表为：(78,50,40,60,34,90)011101010111011101012.邻接矩阵：01110邻接表如图11所示:图113 .用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204 .见图125. 4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。图124、 阅读算法(每题7分，共14分)3 .(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结点(3)返回的线性表为(a2,a3,，an,a1)4 .递归地后序遍历链式存储的二叉树。5、 算法填空(每空2分，共8分)trueBST-leftBST-right6、 编写算法(8分)intCountX(LNode*HL,ElemTypex)inti=0;LNode*p=HL;/i为计数器while(p!=NULL)if(P-data=x)i+;p=p-next;/while,出循环时i中的值即为x结点个数returni;/CountX数据结构期末考试试题及答案21、 单选题（每小题2分，共8分）1、 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为（）。AnBn/2C（n+1）/2D（n-1）/22、 在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指的结点，则执行（）。AsTink=pTink;pTink=s;Bp-link=s;sTink=q;CpTink=sTink;sTink=p;DqTink=s;sTink=p;3、栈的插入和删除操作在（）进行。A栈顶B栈底C任意位置D指定位置4、由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D532、 填空题（每空1分，共32分）1、数据的逻辑结构被分为?、和四种。2、一种抽象数据类型包括f口的个部分。3、在下面的数组a中链接存储着一个线性表，表头指针为ao.next,则该线性表为a0123456786056423874254376201datanext4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为和5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的,该循环队列的最大长度为6、当堆栈采用顺序存储结构时，栈顶元素的值可用表示；当堆栈采用链接存储结构时，栈顶元素的值可用表小07、一棵高度为5的二叉树中最少含有个结点，最多含有个结点；一棵高度为5的理想平衡树中，最少含有个结点，最多含有个结点。8、在图的邻接表中，每个结点被称为,通常它包含三个域：一是;二是;三是9、在一个索引文件的索引表中，每个索引项包含对应记录的?口两项数据。10、 假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J),则树中所含的结点数为个，树的深度为，树的度为，结点H的双亲结点为孩子结点为。11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为，整个堆排序过程的时间复杂度为12、 在对m阶的B树插入元素的过程中，每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针)后，若该结点的索引项数等于个，则必须把它分裂为个结点。运算题(每小题6分，共24分)1、已知一组记录的排序码为(46,79,56,38,40,80,95,24),写出对其进行快速排序的每一次划分结果。2、一个线性表为B=(12,23,45,57,20,03,78,31,15,36)设散列表为HT0.12,散列函数为H(key)=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ,中序遍历的2果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。4、已知一个图的顶点集V各边集G如下：V=。，1,2,3,4,5,6,7,8,9;E=(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6),(5,8),(5,9),(6,7),(7,8),(8,9)当它用邻接矩阵表示和邻接表表示时，分别写出从顶点Vo出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时4、 阅读算法，回答问题（每小题8分，共16分）1、假定从键盘上输入一批整数，依次为：786345309134-1,请写出输出结果。# include# includeconsstintstackmaxsize=30;typedefintelemtype;structstackelemtypestackstackmaxsize;inttop;；# include“stack.hVoidmain()stacka;initstack(a);intx;cinx;while(x!=-1)push(a,x);cinx;while(!stackempty(a)coutpop(a)”coutend1;该算法的输出结果为：2、阅读以下二叉树操作算法，指出该算法的功能。TemplatevoidBinTree:unknown(BinTreeNode*t)BinTreeNode*p=t,*temp;if(p!=NULL)temp=pfleftchild;pTeftchild=pfrightchild;pfrightchild=temp;unknown(pfleftchild);undnown(pfrightchild);该算法的功能是：5、 算法填空，在画有横线的地方填写合适的内容(10分)对顺序存储的有序表进行二分查找的递归算法。intBinsch(ElemTypeA,intlow,inthigh,KeyTypeK)if(low=high)intmid=1if(K=Amid.key)returnmid;elseif(K=0;i-)for(j=0;jnext;p-next=Q.front-next;(B)、p=Q.front-next;Q.front-next=p-next;(C)、p=Q.rear-next;p-next=Q.rear-next;(D)、p=Q-next;Q-next=p-next;9.Huffman树的带权路径长度WPLlf()(B)、所有结点权值之和(D)、根结点的值(A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和10.线索二叉链表是利用()域存储后继结点的地址。(A)、lchild(B)、data(C)、rchild(D)、root二、填空题1 .逻辑结构决定了算法的,而存储结构决定了算法的。2 .栈和队列都是一种的线性表，栈的插入和删除只能在进行。3 .线性表(ai,a2,an)的顺序存储结构中，设每个单元的长度为L,元素a的存储地址LOC(a)为4 .已知一双向链表如下(指针域名为next和prior):现将p所指的结点插入到x和y结点之间，其操作步骤5 .n个结点无向完全图的的边数为n个结点的生成树的边数为6 .已知一有向无环图如下：任意写出二种拓扑排序序列：、。7 .已知二叉树的中序遍历序列为BCA后序遍历序列为CBA则该二叉树的先序遍历序列为,层序遍历序列为。三、应用题1 .设散列函数H(k尸k%13,设关键字系列为22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。(6分)(1)构造HASHH。(2)分别求查找成功和不成功时的平均查找长度。2 .给定表(19,14,22,15,20,21,56,10).(8分)(1) 按元素在表中的次序，建立一棵二叉排序树(2) X(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。(3) 画出对(2)中的遍历序列进行折半查找过程的判定树。3.已知二个稀疏矩阵A和B的压缩存储三元组表如下：ijV13-524625242-1529ABijV25233741352-9558写出A-B压缩存储的三元组表。（5分）4.已知一维数组中的数据为(18,12,25,53,18),试写出插入排序(升序)过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)5.已知一网络的邻接矩阵如下，求从顶点 过程)ABCDA651B65C57D 15 7E 36F2 4(1)求从顶点A开始的最小生成树。A开始的最小生成树。(8分，要有E F326 466(2)分别画出以A为起点的DFS生成树和BFS生成树。6.已知数据六个字母及在通信中出现频率如下表:ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。(1) 画出对应的Huffman树。(2) 计算带权路径长度WPL(3) 求A、B、C、DEF的Huffman编码。7.已知有如下的有向网:62D求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）三、设计题（30分，每题10分，用C语言写出算法，做在答题纸上）1.已知线性表（ai,a2,an）以顺序存储结构为存储结构，其类型定义如下：#defineLIST_INIT_SIZE100顺序表初始分配容量typedefstructElemtype*elem;顺序存储空间基址intlength;当前长度（存储元素个数）SqList;设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：StatusListDelete（Sqlist&L,Elemtypex）2 .设顺序栈如左图所示。其中结点定义如下：typedefstructElemtype*base;栈底指针Elemtype*top;栈顶指针Stack;设计算法，将栈顶元素出栈并存入e中.3 .设二叉链树的类型定义如下：typedefintElemtype;typedefstructnodeElemtypedata;structnode*lchild,*rchild;BinNode,*BinTree;试写出求该二叉树叶子结点数的算法：StatusCountLeaves(BinTree&root,int&n)/nisthenumberofleaves试题3答案选择题(每题i分)1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C一、填空题1. 设计、实现2. 特殊、栈顶3. LOC(a1)+(i-1)*L4. p-next=q-next;q-next-prior=p;q-next=p;p-prior=q;5. n(n-1)/2、n-16. ADCBFEG、ABCDEFFG7. ABC、ABC二、应用题1(1)Hash表(4分)地址0123456789101112关键安132164572282412探测次数11r712311r3:11(2)查找成功的平均查找长度：(1分)(5*1+1*2+2*3+1*7)/9=20/9查找不成功的平均查找长度：(1分)(2+1+9+8+7+6+5+4+3+2+1)/13=2(1)、构造(3分)(2)、1014151920212256(2分)、(3分)3、(5分，每行0.5)ijv13-52463:3741342-152185584、初始关键字：1812255318第一趟:12金18255318第二趟：1218255318第三趟:1218255318第四趟：121818*2553O（n2）（1分）。（4分）5、7分1 1）4分6、（1）3分（1分）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=(3) A: 010B: 011 C: 110 D: 111 E: 00F; 10 (3 分)12、A-B : (A、A-C: (A、A-D : (A、A-E : (A、B)1分D、C) 2分D)1分D、 E)2分三，设计题（20分）1、(10分)StatusListDelete(Sqlist&L,ElemTypex)inti,j;for(i=0;ilength;i+)if(L-elemi=x)break;if(i=L-length)returnERROR;for(j=i;jlengthi-1;j+)L-elemj=L-elemj+1;L-length-;(8分)平均时间复杂度：(2分)设元素个数记为n,则平均时间复杂度为:(ni)2 (10分)voidpop(Stack&S,Elemtype&e)if(S.top=S.base)returnERROR;S.top-;e=*s.top;2、(10分)voidCountLeaves(BinTreeT,int&n)if(T)if(!(T-lchild)&!(T-rchild)n+;CountLeaves(T-lchild,n);CountLeaves(T-rchild,n);