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

活动的最早开始时间和最迟开始时间:

网络中的关键活动: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的祖先?

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4