数据结构模拟试卷及参考答案

数据结构模拟试卷(一)及参考答案单项选择题（本大题共15小题，每小题2分，共30分）1．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用(A)方法最快。A、起泡排序B、快速排序C、堆排序D、直接选择排序2．算法分析的目的是（B）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（C）A．插入 B．删除C．定位 D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（D）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（A）A．15 B．16 C．17 D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（B）。A.108B.112C.116D.1207．从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（C）个结点。A.nB.n/2C.(n+1)/2D.(n-1)/28．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（D）A．不一定相同 B．互为逆序C．都不相同 D．都相同9．高度为5的二叉树至多有结点数为（A）A.63B.32C.24D.6410．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（B）A．图中每个顶点的出度 B．图中每个顶点的入度C．图中弧的条数 D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（C）A．无向图 B．有向图 C．稠密图 D．稀疏图12．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（D）。A.s->next=p;p->next=sB.p-next=s;s->next=pC.p=s;s->next=p->nextD.s->next=p->next;p->next=s13．下列排序算法中，其时间复杂度和记录的初始排列无关的是（A）A．直接选择排序 B．插入排序C．快速排序 D．冒泡排序14．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（B）A．f,d,b B．f,c,b C．g,c,b D．g,d,b15．如下图所示的4棵二叉树中，（C）不是完全二叉树。ABCDABCD填空题（本大题共15小题，每小题2分，共30分）在数据结构中，数据的逻辑结构分线性结构和非线性结构。称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和___f(n)____的数量级相同。在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_____O(n)____。假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为__10____。对于栈只能在___栈顶_____插入和删除元素。通常从正确性、____可使用性___、可读性、效率和健壮性等5个方面评价算法（包括程序）的质量。在具有n个单元的循环队列中，队满时共有n-1个元素。若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为(15,02,21,24,26,57,43,66,80,48,73)。在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为稠密索引，若对应数据对象表中的若干个表项，则称此索引为稀疏索引。二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为89。广义表A((a，b，c)，(d，e，f))的表尾为（(d，e，f)）。设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为3。根据一组记录(56，42，50，64，48)依次插入结点生成一棵AVL树(高度平衡的二叉搜索树)时，当插人到值为50的结点时需要进行旋转调整。n（n＞0）个顶点的无向图最多有n(n-1)／2条边。设无向图的邻接表如下图所示，则该图的边的数目是5。判断题(本大题共10小题，每小题1分，共10分)（×）链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。（√）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（×）通常递归的算法简单、易懂、容易编写，而且执行的效率也高。（√）一个广义表的表尾总是一个广义表。（×）对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。（√）当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。（×）存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（√）进行折半搜索的表必须是顺序存储的有序表。（×）直接选择排序是一种稳定的排序方法。（×）在用单链表表示的链式队列中，队头在链表的链尾位置。问答题(本大题共5小题，每小题6分，共30分)1．由如图所示的二叉树，回答以下问题。a.其中序遍历序列为dgbaechif。b.其先序遍历序列为abdgcefhi。c.其后序遍历序列为gdbeihfca。aadcbefghi2．已知图G=(V,E)，其中V＝{a,b,c,d,e,f,g}，E＝｛<a,b>,<a,g>,<b,g>,<c,b>,<d,c>,<d,f>,<e,d>,<f,a>,<f,e>,<g,c>,<g,d>,<g,f>｝，请画出图G，并写出其邻接矩阵和邻接表表示。aabcgfedabcdefg邻接矩阵：abcdefg100001000001100000010010100001000001100000010010001000000100011010abcdefg010123456abcdefg16Λ6Λ1Λ25Λ3Λ04Λ235Λ3．写出利用直接选择排序对关键字序列(40,24,80,39,43,18,20)进行从小到大排序的每一趟结果。参考答案：18,24,80,39,43,40,2018,20,80,39,43,40,2418,20,24,39,43,40,8018,20,24,39,43,40,8018,20,24,39,40,43,8018,20,24,39,40,43,804．设A、B、C是不同的关键字且A>B>C，可组成6种不同的输入顺序。问其中哪几种输入顺序所构造的二叉排序树的高度为2?参考答案：4种。ABCACBCABCBA评分标准：次序不限，写对一种得1分，4种全写对得6分。若在4种正确答案之外，又多写一种则只能得4分，若6种排列顺序全写上则0分。5．在如图所示的AOE网中，试回答如下问题：（1）计算出每个顶点所表示的事件的最早发生时间和最迟发生时间；（2）计算出每条边所表示的活动的最早开始时间和最迟开始时间；（3）找出此网络中的关键活动和关键路径。664521187244abcehgkdf 事件的最早发生时间和最迟发生时间： 活动的最早开始时间和最迟开始时间：网络中的关键活动：ab,be,eh,hk关键路径:aàbàeàhàk数据结构模拟试卷(二)单项选择题（每小题2分，共30分）1.线性结构的逻辑特征是除第一个节点和最后一个节点，其它节点都有。A．一个直接前趋和一个直接后继B．多个直接前趋和一个直接后继C．一个直接前趋和多个直接后继D．多个直接前趋和多个直接后继算法必须具备输入、输出和。A．计算方法B．排序方法C．解决问题的有限运算步骤D．程式序设计方法3.将递归过程转化为非递归过程需用到。A．栈B．队C．线性表D．链表4.在顺序表上做增、删节点运算的平均时间复杂度是。A．O(1)B．O(n)C．O(log2n)D．O(n2)5.设二维数组A[0…m-1][0…n-1]按行优先顺序存储，则元素A[i][j]的地址为。A．LOC(A[0][0])+(i*m+j)B．LOC(A[0][0])+(i*n+j)C．LOC(A[0][0])+[(i-1)*n+j-1]D．LOC(A[0][0])+[(i-1)*m+j-1]设目标串T=“aababbadbbaa”，模式P=“bba”，则该模式匹配的有效位移为。A.4B.5C.7 D.107.把长度为m的单链表接在长度为n的单链表之后的算法的时间复杂度为。A．O(m)B．O(n)C．O(m+n)D．O(1)在一个单链表中，若P所指节点不是最后节点，在P之后插入S所指节点，则执行。A．S->next=P->next;P->next=S;B．P->next=S->next;S->next=P;C．S->next=P;P->next=S;D．P->next=S;S->next=P;9.设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是。A．23415B．54132C．23145D．1543210.循环队列是空队列的条件是。A．Q->rear==Q->frontB．(Q->rear+1)%maxsize==Q->frontC．Q->rear==0D．Q->front==011.设有一广义表E=（a,b,(c,d)），其长度为。A．2B．3C．4D．512.某二叉树的前序遍历序列为ABDEFC，中序遍历序列为DBEFAC，则后序遍历序列为。A．DFEBCAB．DBECFAC．BDAECFD．DBEFCA下列哪项不是利用查找表中数据元素的关系进行查找的方法。A．有序表的查找B．二叉排序树的查找C．平衡二叉树D．散列查找下述几种排序方法中，要求内存量最大的是。A．插入排序B．快速排序C．归并排序D．选择排序在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A．1/2B．1C．2D．4填空题(每空2分，共20分)16．数据结构一般包括三个方面内容：数据的，数据的存储结构及数据的运算。17．在包含n个结点的顺序表上做等概率插入运算，平均要移动_____个结点。18．队列的特性是______。19．已知二叉树中叶子数为30，仅有一个孩子的结点数为20，则总结点数为____。20．_______遍历二叉排序树中的结点可以得到一个递增的关键字序列（选填“先序”、“中序”或“后序”）。21．n个节点的连通图至少有_________条边。22．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑，应最好选择排序。23．带有一个头结点的单链表head为空的条件是（假设指针域的名称为next）_____。24．设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为___________________。25．在拓扑排序中，拓扑序列的第一个顶点必定是的顶点。简答题（每题6分，共36分）26．已知一棵树边的集合为｛<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h>,<a,c>｝，画出这棵树，并回答下列问题：哪个是根结点？哪些是叶子结点？哪些是结点g的祖先？树的深度是多少？树的度数是多少？27．以下面数据作为叶子结点的权值构造一Huffman树，画出该树并计算出其带权路径长度。2，4，5，828．给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。画出从该二叉搜索树中删除关键码28和52后的结果。29．试画出下面带权无向图的一棵最小生成树。95576843297abdcef30．写出利用希尔排序对关键字序列(40,24,80,39,43,18,20,10,90,70)进行从小到大排序的每一趟结果。（假设gap取值分别为5、3、1）31．设一散列表长为13，采用线性探查法解决冲突。散列函数h(key)=key%13。（1）画出在空表中依次插入关键字25,20,36,15,41,52,29,72,67后的散列表。（2）该散列表在等概率查找成功和不成功的平均查找长度。综合题（共14分）32．试对下图所示的AOE网络回答下列问题：这个工程最早可能在什么时间结束。（2分）求每个活动的最早开始时间e()和最迟开始时间l().（8分）确定哪些活动是关键活动。（4分）652101941512345611652101941512345611数据结构模拟试卷(二)参考答案单项选择题（每小题2分，共30分）1~5ACABB6~10ABABA11~15BADCB填空题(每空2分，共20分)16．数据结构一般包括三个方面内容：数据的逻辑结构，数据的存储结构及数据的运算。17．在包含n个结点的顺序表上做等概率插入运算，平均要移动__n/2____个结点。18．队列的特性是____先进先出__。19．已知二叉树中叶子数为30，仅有一个孩子的结点数为20，则总结点数为__79__。20．______中序_遍历二叉排序树中的结点可以得到一个递增的关键字序列（选填“先序”、“中序”或“后序”）。21．n个节点的连通图至少有_____n-1____条边。22．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑，应最好选择快速排序排序。23．带有一个头结点的单链表head为空的条件是（假设指针域的名称为next）__head->next==NULL___。24．设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为_______10,13,27,76,65,97,38____________。25．在拓扑排序中，拓扑序列的第一个顶点必定是入度为零的顶点。简答题（每题6分，共36分）26．已知一棵树边的集合为｛<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h>,<a,c>｝，画出这棵树，并回答下列问题：哪个是根结点？哪些是叶子结点？哪些是结点g的祖先？树的深度是多少？树的度数是多少？参考答案：根结点是：a叶子结点是：difjklg的祖先：ac树的深度：4树的度数：327．以下面数据作为叶子结点的权值构造一Huffman树，画出该树并计算出其带权路径长度。2，4，5，8参考答案：198116425198116425带权路径长度：WPL=(2+4)*3+5*2+8=3628．给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。画出从该二叉搜索树中删除关键码28和52后的结果。参考答案：(1)(2)（评分标准：每个图3分）29．试画出下面带权无向图的一棵最小生成树。55768432997abdcef参考答案：554326abdcef(对1根线得1分，全对得6分)30．写出利用希尔排序对关键字序列(40,24,80,39,43,18,20,10,90,70)进行从小到大排序的每一趟结果。（假设gap取值分别为5、3、1）参考答案：Gap=5时18,20,10,39,43,40,24,80,90,70Gap=3时18,20,10,24,43,40,39,80,90,70Gap=1时10,18,20,24,39,40,43,70,80,90(每对1行得2分)31．设一散列表长为13，采用线性探查法解决冲突。散列函数h(key)=key%13。（1）画出在空表中依次插入关键字25,20,36,15,41,52,29,72,67后的散列表。（2）该散列表在等概率查找成功和不成功的平均查找长度。参考答案：(1)散列表：（2分）00123456789101112521541296720723625 (2)ASLSUCC=(5*1+3*2+1*4)/9=5/3（2分） ASLNSUCC=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13（2分）综合题（共14分）32．试对下图所示的AOE网络回答下列问题：这个工程最早可能在什么时间结束。（2分）求每个活动的最早开始时间e()和最迟开始时间l().（8分）确定哪些活动是关键活动。（4分）652101941512345611652101941512345611数据结构模拟试卷(三)单项选择题（每小题2分，共30分）1．一个非空广义表的表头A．一定是子表B.一定是原子C．不能是子表D.可以是原子，也可以是子表2．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是A．堆排序B.冒泡排序C．直接选择排序D.快速排序3．设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是A．23415B.15432C．23145D.541324.算法必须具备输入、输出和A.计算方法B.排序方法C．解决问题的有限运算步骤D.程序设计方法5．拓扑排序运算只能用于A．带权有向图B.连通无向图C．有向无环图D.无向图6.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是A.O(1)B.O(n)C.O(n2)D.O(nlogn)7．在一个无向图中，所有顶点的度数之和等于图的边数的倍A．1/2B.1C.2D.48.设二维数组A[0..m-1][0..n-1]按行优先顺序存储，则元素A[i][j]的地址为A．LOC(A[0][0])+(i*m+j)B．LOC(A[0][0])+(i*n+j)LOC(A[0][0])+[(i-1)*n+j-1]D.LOC(A[0][0])+[(i-1)*m+j-1]9．单链表的存储密度A．大于1B.等于1C．小于1D.不能确定10.有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是访问第i个节点（1≤i≤n）在第i个节点后插入一个新节点（1≤i≤n）删除第i个节点（1≤i≤n）将n个节点从小到大排序11.循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执行出队后其头指针front值是A．front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m12．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是A．堆排序B.冒泡排序C．直接选择排序D.快速排序13.若要惟一地确定一棵二叉树，只需知道该二叉树的A．前序序列B.中序序列C．前序和后序序列D.中序和后序序列14．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是A．希尔排序B.冒泡排序C．插入排序D.选择排序15．具有n个节点的完全二叉树的深度为A．élog2(n+1)ù-1B.log2n+1C.log2nD.ëlog2nû填空题（每小题2分，共20分）1．数据的逻辑结构分为两大类，它们是线性结构和。2．在单链表中（假设结点指针域名称为next），删除指针P所指结点的后继结点的语句是。3．已知循环队列用数组data[n]存储元素值，用front,rear分别作为头尾指针，则当前元素个数为。4．若n为主串长，m为子串长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数为____。5．广义表((a),((b),j,(((d)))))的表尾是。6．已知二叉树有61个叶子节点，且仅有一个孩子的节点数为45，则总节点数为。7．解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个结构。8．n个顶点e条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为____________。9．对于n个关键字的集合进行冒泡排序，在最坏情况下所需要的时间为________。10．在一个长度为n的顺序表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移个元素。算法阅读题（每空2分，共10分）1．设线性表的n个结点定义为（a0,a1,…,an-1），在顺序表上实现的插入和删除算法如下，请在空白处填入适当内容。(顺序表的最大可容纳项数为MaxSize)Template<classType>intSeqList<Type>::Insert(Type&x,inti){If(i<0||i>last+1||last==(1))return0;Else{Last++;For(intj=last;j<i;j--)data[j]=(2);(3);Return1;}}Template<classType>intseqList<Type>::Remove(Type&x){inti=Find(x);if(i>=0){last--;for(intj=(4);j<=last;j++)data[j]=(5);return1;}return0;}答题:(1)(2)(3)(4)(5)四、问答题（共40分）1.已知一棵二叉树的中序序列和序序列分别如下，请写出它的后序序列。（10分）前序序列： ABDECRGMHK 中序序列：DBEARGCHKM答题:后序序列：2．