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

^

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

一．单项选择题（本大题共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，5

5．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（ A ）

A．15 B．16

C．17 D．18

6．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（ B ）。

A. 108

B. 112

C. 116

D. 120

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

A. n

B. n/2

C. (n+1)/2

D. (n-1)/2

。

8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ D ）A．不一定相同 B．互为逆序

C．都不相同 D．都相同

9．高度为5的二叉树至多有结点数为（ A ）

A. 63

B. 32

C. 24

10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ B ）A．图中每个顶点的出度 B．图中每个顶点的入度

C．图中弧的条数 D．图中连通分量的数目

】

11．图的邻接矩阵表示法适用于表示（ C ）

A．无向图 B．有向图

C．稠密图D．稀疏图

12．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（ D ）。

A. s->next=p; p->next=s

B. p-next=s; s->next=p

C. p=s; s->next=p->next

D. s->next=p->next; p->next=s

13．下列排序算法中，其时间复杂度和记录的初始排列无关的是（ 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,b

15．如下图所示的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 ＝

｛,,,,,,,, ,,,｝，请画出图G ，并写出其邻接矩阵和邻接表表示。 &

&

）

邻接矩阵：

\

邻接表：

@

/

3

一趟结果。

参考答案：

18,24,80,39,43,40,20

18,20,80,39,43,40,24

…

18,20,24,39,43,40, 80

18,20,24,39,43,40, 80 18,20,24,39,40,43, 80 18,20,24,39,40,43, 80

4．设A 、B 、C 是不同的关键字且A>B>C ，可组成6种不同的输入顺序。问其中哪几种输入顺序所构造的二叉排序树的高度为2

参考答案： 【

4种。A BC

A C

B

C 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. 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.[

16.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

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）!

（4）哪些是结点g的祖先

（5）树的深度是多少

（6）树的度数是多少

27．以下面数据作为叶子结点的权值构造一Huffman树，画出该树并计算出其带权路径长度。

2，4，5，8

28．给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，

（1）$

（2）从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。

（3）画出从该二叉搜索树中删除关键码28和52后的结果。

29．试画出下面带权无向图的一棵最小生成树。 …

30

进行从小到大排

序的每一趟结果。（假设 31．设一散列表长为13，采用线性探查法解决冲突。散列函数h(key)=key%13。 <

（1）画出在空表中依次插入关键字25,20,36,15,41,52,29,72,67后的散列表。 （2）该散列表在等概率查找成功和不成功的平均查找长度。

四、 综合题（共14分）

32．试对下图所示的AOE 网络回答下列问题：

（1） 这个工程最早可能在什么时间结束。（2分）

（2） 求每个活动的最早开始时间e ()和最迟开始时间l ().（8分） （3） 确定哪些活动是关键活动。（4分）

》

…

五、单项选择题（每小题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．已知一棵树边的集合为｛,,,,,,,, , ,｝，画出这棵树，并回答下列问题：

（7） 哪个是根结点 （8） 哪些是叶子结点 （9） 哪些是结点g 的祖先 （10） 【 （11） 树的深度是多少

（12） 树的度数是多少

参考答案：

根结点是：a

叶子结点是：d i f j k l g 的祖先：a c 树的深度：4 树的度数：3

?

27．以下面数据作为叶子结点的权值构造一Huffman 树，画出该树并计算出其带权路径长度。 参考答案：

， 带权路径长度：WPL=(2+4)*3+5*2+8=36

28．给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，

（4） 从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。 （5） 画出从该二叉搜索树中删除关键码28和52后的结果。

参考答案： 、 (1)

19 8 & 6 4

2 ~

(2)

（评分标准：每个图3分）

29．试画出下面带权无向图的一棵最小生成树。 -

$

参考答案：

'

(对根线得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, 70 Gap=3时 18, 20, 10, 24, 43, 40, 39, 80, 90, 70 Gap=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分）

】

(2)ASL SUCC =(5*1+3*2+1*4)/9=5/3 （2分）

5

7

6

8 4

3

2

9 9

7

a

b d

c

e

f

0 1 2 3 4 5 6 7 8 9 10 11 12 52 15 41 29 67 20 72 36 25 5 4

]

2

6

a

】

d

c

e

\

ASL NSUCC =(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13 （2分）

八、 综合题（共14分）

32．试对下图所示的AOE 网络回答下列问题：

（4） - （5） 这个工程最早可能在什么时间结束。（2分）

（6） 求每个活动的最早开始时间e ()和最迟开始时间l ().（8分） （7）

&

&

数据结构模拟试卷(三)

二、 单项选择题（每小题2分，共30分）

1．一个非空广义表的表头

A ．一定是子表 B. 一定是原子

C ．不能是子表 D. 可以是原子，也可以是子表

2．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n 2

)的是

A ．堆排序 B. 冒泡排序

、

6

5

}

10 19

4

#

1

2

3

、

5

6

11

C．直接选择排序 D. 快速排序

3．设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是

A．23415 B. 15432

C．23145 D. 54132

4. 算法必须具备输入、输出和

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/2 B. 1

C. 2

D. 4

【

8. 设二维数组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]

9．单链表的存储密度

A．大于1 B. 等于1

C．小于1 D. 不能确定

10. 有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是

A.访问第i个节点（1≤i≤n）

B.—

C.在第i个节点后插入一个新节点（1≤i≤n）

D.删除第i个节点（1≤i≤n）

E.将n个节点从小到大排序

11. 循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执行出

队后其头指针front值是

A．front=front+1 B. front=(front+1)%(m-1)

C. front=(front-1)%m

D. front=(front+1)%m

12．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是

A．堆排序 B. 冒泡排序

{

C．直接选择排序 D. 快速排序

13. 若要惟一地确定一棵二叉树，只需知道该二叉树的

A．前序序列 B. 中序序列

C．前序和后序序列 D. 中序和后序序列

14．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是A．希尔排序 B. 冒泡排序

C．插入排序 D. 选择排序

15．具有n个节点的完全二叉树的深度为

|

A．log2(n+1) -1 B. log2n+1

C. log2n

D. 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,…,a n-1），在顺序表上实现的插入和删除算法如下，请在空白处填入适当内容。(顺序表的最大可容纳项数为MaxSize)

Template int SeqList::Insert(Type &x, int i) {

;

If (i<0 || i>last+1 || last== (1) ) return 0;

Else {

Last++;

For(int j=last;j

(3) ;

Return 1;

}

}

：

Template int seqList::Remove(Type &x){

int i=Find(x);

if(i>=0) {

last--;

for (int j= (4) ;j<=last;j++) data[j]= (5) ;

return 1;

}

；

return 0;

}

答题:

(1)

(2)

(3)

(4)

(5)

?

四、问答题（共40分）

1.已知一棵二叉树的中序序列和序序列分别如下，请写出它的后序序列。（10分）

前序序列： A B D E C R G M H K

中序序列： D B E A R G C H K M

答题:

后序序列：

；

2．已知AOE 网的邻接表如下：（10分）

1

2

3

！

;

(1)并标明每个事件发生的Ve 及 Vl

【

(2). 写出AOE网的关键路径:

关键路径(Critical Path):

3.已知关键字序列为：

{03, 87, 12, 61, 98, 70, 61*，97, 27, 53, 42，56，77， }请采用希尔(Shell)排序法对该序列作非递减排序.按5，3，1 分组，写出下列标明的趟的结果（10 分）

初始 03 ， 87， 12 ， 61， 98 ，70， 97， 27， 53， 42， 56，77

第一趟

第二趟

每三趟

4．有一电文共使用5个字符：O, G, D, □,F, 它们的频率依次为4，7，5，2，9，（注意：按左子树根结点的权不大于右子树根结点的权的次序构造;

依次扫描，从左到右）（10分）

①试画出对应的哈夫曼树，求出每个字符哈夫曼树的编码。

②有一电文 00

答案：

①O:=

G:=

D:=

□:=

F:=

②电文是：

数据结构模拟试卷(三)参考答案

三、算法阅读题（每小题5分，共10分）

答案:

(1) MaxSize-1

(2) data[j-1]

(3) Data[i]=x

(4)i

(5) data[j+1]

四、问答题（共40分）

1．已知一棵二叉树的中序序列和序序列分别如下，请写出它的后序序列。（10分）

答案:后序序列：D E B G R K H M C A

2．已知AOE 网的邻接表如下：（10分）

(1)并标明每个事件发生的Ve 及 Vl

(2).写出AOE网的关键路径:

关键路径(Critical Path): , ,,

3.（10 分）

初始 03 ， 87， 12 ， 61， 98 ，70， 97， 27， 53， 42， 56， 77

第一趟 03， 77， 12， 53， 42， 56， 87， 27， 61， 98， 70， 97

第二趟 03， 27， 12， 53， 42， 56， 87， 70， 61， 98， 77， 97

每三趟 03, 12, 27, 42, 53, 56, 61, 70, 77, 87, 97, 98 4．有一电文 00 （10分）

答案：

①O:=011

G:=10

D:=00

□:=010

F:=11

②

GOOD□FOOD□GOOD