行比较的关键字依次为（ ） A．f,d,b B．f,c,b C．g,c,b D．g,d,b 15．如下图所示的4棵二叉树中，（ ）不是完全二叉树。
A B C D
二．填空题（本大题共15小题，每小题2分，共30分）
1. 在数据结构中，数据的逻辑结构分线性结构和 。
2. 称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和___ ____的数量
级相同。
3. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_____
____。
4. 假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13
和17，则当前尾指针的值为________。 5. 对于栈只能在_________插入和删除元素。 6. 通常从正确性、________、可读性、效率和健壮性等5个方面评价算法（包括程序）
的质量。
7. 在具有n个单元的循环队列中，队满时共有 个元素。
8. 若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量
为3的希尔排序，则得到的结果为 。
9. 在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引
为 索引，若对应数据对象表中的若干个表项，则称此索引为 索引。 10. 二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为 。 11. 广义表A((a，b，c)，(d，e，f))的表尾为 。
12. 设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出
栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为 。 13. 根据一组记录(56，42，50，64，48)依次插入结点生成一棵AVL树(高度平衡的二
叉搜索树)时，当插人到值为 的结点时需要进行旋转调整。 14. n（n＞0）个顶点的无向图最多有 条边。
15. 设无向图的邻接表如下图所示，则该图的边的数目是 。
三．判断题(本大题共10小题，每小题1分，共10分) 1. （ ）链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元
素之间的逻辑顺序。 2. （ ）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 3. （ ）通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 4. （ ）一个广义表的表尾总是一个广义表。
5. （ ）对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂
度为O（h）。
6. （ ）当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按
条件把它逐层向下调整，直到调整到合适位置为止。
7. （ ）存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边
数也有关。
8. （ ）进行折半搜索的表必须是顺序存储的有序表。 9. （ ）直接选择排序是一种稳定的排序方法。
10. （ ）在用单链表表示的链式队列中，队头在链表的链尾位置。
四．问答题 (本大题共5小题，每小题6分，共30分) 1．由如图所示的二叉树，回答以下问题。
a.其中序遍历序列为 。 b.其先序遍历序列为 。
c.其后序遍历序列为 。
h g
i 2．已知图G=(V,E)，其中V＝{a,b,c,d,e,f,g}，E＝
｛,,
d b e a c f
3．写出利用直接选择排序对关键字序列 (40,24,80,39,43,18,20) 进行从小到大排序的每一趟结果。
4．设A、B、C是不同的关键字且A>B>C，可组成6种不同的输入顺序。问其中哪几种输入顺序所构造的二叉排序树的高度为3?
5．在如图所示的AOE网中，试回答如下问题：（1）计算出每个顶点所表示的事件的最早发生时间和最迟发生时间；（2）计算出每条边所表示的活动的最早开始时间和最迟开始时间；（3）找出此网络中的关键活动和关键路径。 g 2 b 6 1 8 a e k 4 7 1 4 c 5 h 2 4 f d
数据结构模拟试卷(二)
姓名： 学号： 20103856 班名： 21003
一、单项选择题（每小题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. 4 B. 5
C. 7 D. 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．23415 B．54132 C．23145
D．15432 10. 循环队列是空队列的条件是 。
A．Q->rear==Q->front
B．(Q->rear+1)%maxsize==Q->front C．Q->rear==0
D．Q->front==0 11. 设有一广义表E=（a,b,(c,d)），其长度为 。
A．2 B．3 C．4
D．5
12. 某二叉树的前序遍历序列为ABDEFC，中序遍历序列为DBEFAC，则后序遍历序列
为 。 A．DFEBCA B．DBECFA C．BDAECF
D．DBEFCA 13. 下列哪项不是利用查找表中数据元素的关系进行查找的方法。
A．有序表的查找 B．二叉排序树的查找 C．平衡二叉树
D．散列查找 14. 下述几种排序方法中，要求内存量最大的是 。
A．插入排序 B．快速排序 C．归并排序
D．选择排序
15. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A．1/2 B．1 C．2 D．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．已知一棵树边的集合为｛
（1） 哪个是根结点？ （2） 哪些是叶子结点？ （3） 哪些是结点g的祖先？ （4） 树的深度是多少？ （5） 树的度数是多少？
27．以数据集{2，4，5，8}作为叶子结点的权值构造Huffman树，画出该树并计算出其带权路径长度。
28．给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，
（1） 从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。 （2） 画出从该二叉搜索树中删除关键码28和52后的结果。