^数据结构模拟试卷(一)及参考答案一．单项选择题（本大题共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，1>C．1，2，5，3，4，6 D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（ A ）A．15 B．16C．17 D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（ B ）。

A. 108B. 112C. 116D. 1207．从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（ C ）个结点。

A. nB. n/2C. (n+1)/2D. (n-1)/2。

8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ D ）A．不一定相同 B．互为逆序C．都不相同 D．都相同9．高度为5的二叉树至多有结点数为（ A ）A. 63B. 32C. 2410．若用邻接矩阵表示一个有向图，则其中每一列包含的″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,bC．g,c,b D．g,d,b15．如下图所示的4棵二叉树中，（ C ）不是完全二叉树。

<二．填空题（本大题共15小题，每小题2分，共30分）1.-2.在数据结构中，数据的逻辑结构分线性结构和非线性结构。

3.称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和___ f(n)____的数量级相同。

4.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_____O(n)____。

5.假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为__10____。

6.对于栈只能在___栈顶_____插入和删除元素。

7.通常从正确性、____可使用性___、可读性、效率和健壮性等5个方面评价算法（包括程序）的质量。

8.在具有n个单元的循环队列中，队满时共有n-1 个元素。

9.若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为(15,02,21,24,26,57,43,66,80,48,73) 。

10.—11.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为稠密索引，若对应数据对象表中的若干个表项，则称此索引为稀疏索引。

12.二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为 89 。

13.广义表A((a，b，c)，(d，e，f))的表尾为（(d，e，f)）。

14.设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为 3 。

15.根据一组记录(56，42，50，64，48)依次插入结点生成一棵AVL树(高度平衡的二叉搜索树)时，当插人到值为 50 的结点时需要进行旋转调整。

16.n（n＞0）个顶点的无向图最多有 n(n-1)／2 条边。

17.设无向图的邻接表如下图所示，则该图的边的数目是 5 。

A B C D三．~ 四． 判断题(本大题共10小题，每小题1分，共10分) 1. （×）链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

2. （√）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

3. （×）通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

4. （√）一个广义表的表尾总是一个广义表。

5. （×）对于一棵具有n 个结点，其高度为h 的二叉树，进行任一种次序遍历的时间复杂度为O （h ）。

6. （√）当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

7. （×）存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

8. ! 9. （√）进行折半搜索的表必须是顺序存储的有序表。

10. （×）直接选择排序是一种稳定的排序方法。

11. （×）在用单链表表示的链式队列中，队头在链表的链尾位置。

五．问答题 (本大题共5小题，每小题6分，共30分) 1．由如图所示的二叉树，回答以下问题。

a.其中序遍历序列为 d g b a e c h i f 。

b.其先序遍历序列为 a b d g c e f h i 。

…c.其后序遍历序列为 g d b e i h f c a 。

|2．已知图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 ，并写出其邻接矩阵和邻接表表示。

&&）邻接矩阵：\邻接表：@/3一趟结果。

参考答案：18,24,80,39,43,40,2018,20,80,39,43,40,24…18,20,24,39,43,40, 8018,20,24,39,43,40, 80 18,20,24,39,40,43, 80 18,20,24,39,40,43, 804．设A 、B 、C 是不同的关键字且A>B>C ，可组成6种不同的输入顺序。

问其中哪几种输入顺序所构造的二叉排序树的高度为2参考答案： 【4种。

A BCA CBC A B C B A评分标准：次序不限，写对一种得1分，4种全写对得6分。

若在4种正确答案之外，又多写一种则只能得4分，若6种排列顺序全写上则0分。

5．在如图所示的AOE 网中，试回答如下问题：（1）计算出每个顶点所表示的事件的最早发生时间和最迟发生时间；（2）计算出每条边所表示的活动的最早开始时间和最迟开始时间；（3）找出此网络中的关键活动和关键路径。

】0 1 2 3 4…5/事件的最早发生时间和最迟发生时间：活动的最早开始时间和最迟开始时间：~网络中的关键活动：ab,be,eh,hk关键路径: a b e h k。

~~^数据结构模拟试卷(二)一、单项选择题（每小题2分，共30分）1. 线性结构的逻辑特征是除第一个节点和最后一个节点，其它节点都有。

A．一个直接前趋和一个直接后继B．多个直接前趋和一个直接后继C．一个直接前趋和多个直接后继<D．多个直接前趋和多个直接后继2.算法必须具备输入、输出和。

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]6.设目标串T=“aababbadbbaa”，模式P=“bba”，则该模式匹配的有效位移为。

A. 4B. 5C. 7D. 10'7. 把长度为m的单链表接在长度为n的单链表之后的算法的时间复杂度为。

A．O(m)B．O(n)C．O(m+n)D．O(1)8.在一个单链表中，若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．4（D．512. 某二叉树的前序遍历序列为ABDEFC，中序遍历序列为DBEFAC，则后序遍历序列为。

A．DFEBCAB．DBECFAC．BDAECFD．DBEFCA13.下列哪项不是利用查找表中数据元素的关系进行查找的方法。

A．有序表的查找}B．二叉排序树的查找C．平衡二叉树D．散列查找14.下述几种排序方法中，要求内存量最大的是。