活动的最早开始时间和最迟开始时间：
网络中的关键活动：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. 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．以下面数据作为叶子结点的权值构造一Huffman树，画出该树并计算出其带权路径长度。
2，4，5，8
28．给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，
（1） 从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。 （2） 画出从该二叉搜索树中删除关键码28和52后的结果。
29．试画出下面带权无向图的一棵最小生成树。
9 2 a
7 d b 6 3 9 c 7 8 4 e f 5 30．写出利用希尔排序对关键字序列 (40,24,80,39,43,18,20,10,90,70) 进行从小到大排序的每一趟结果。（假设gap取值分别为5、3、1）
31．设一散列表长为13，采用线性探查法解决冲突。散列函数h(key)=key。 （1）画出在空表中依次插入关键字25,20,36,15,41,52,29,72,67后的散列表。
（2）该散列表在等概率查找成功和不成功的平均查找长度。
四、 综合题（共14分）
32．试对下图所示的AOE网络回答下列问题：
（1） 这个工程最早可能在什么时间结束。（2分）
（2） 求每个活动的最早开始时间e()和最迟开始时间l().（8分） （3） 确定哪些活动是关键活动。（4分） 10
2 1 2 4 19 4 3 6 6 15 5 5 数据结构模拟试卷(二)参考答案
11 五、单项选择题（每小题2分，共30分）
1~5 ACABB 6~10 ABABA 11~15 BADCB 六、填空题(每空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．已知一棵树边的集合为｛
（6） 哪个是根结点？ （7） 哪些是叶子结点？ （8） 哪些是结点g的祖先？