2025年数据结构 测试题3 .pdf

子曰:“知者不惑，仁者不忧，勇者不惧。”——《论语》

测试三

一．单项选择题（2分/题）

1．一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其

空链域数为（）。

A.0B.1C.2D.不确定

2．设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（）。

2

A.O(n)B.O(n+e)C.O(n)D.O(n*e)

3．下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是

2

（）。

A.堆排序B.冒泡排序C.快速排序D.SHELL排序

4．已知数据表A中每个元素距其最终位置不远，则采用（）排序算法

最节省时间。

A.堆排序B.插入排序C.快速排序D.直接选择排序

5．串是（）。

A.不少于一个字母的序列B.任意个字母的序列

C.不少于一个字符的序列D.有限个字符的序列

二．判断题（1分/题）

1.（）若一个栈的输入序列为123„n，其输出序列的第一个元素为

n，则其输出序列的每个元素a一定满足a=n-i+1。(i=1,2,...,n)

ii

2.（）二叉树中的叶子结点就是二叉树中没有左右子树的结点。

3.（）一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结

点数。

4.（）删除二叉排序树中的一个结点，再重新插入上去，一定能得到

原来的二叉排序树。

5.（）线性表就是顺序表。

6.（）若一棵树中某结点的度为1，则该结点仅有一棵子树。

7.（）所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二

叉树。

8.（）AOE网所表示的工程至少所需的时间等于从源点到汇点的最短

路径的长度。

9.（）若某二叉树的叶子结点数为1，则其先序序列和后序序列一定

相反。

太上有立德，其次有立功，其次有立言，虽久不废，此谓不朽。——《左传》

10.（）在采用线性探测法处理冲突的散列表中，所有的同义词在表中

相邻。

11.（）对B-树中任一非叶子结点中的某关键字K，比K小的最大关

键字和比K大的最小关键字一定都在非叶结点的最下层。

12.（）若一个连通无向图的以顶点1为起点的深度遍历序列唯一，则

可唯一确定该图。

13.（）若一个有向图的以顶点1为起点的深度遍历序列唯一，则可唯

一确定该图。

14.（）在数据表基本有序时，冒泡排序算法的时间复杂度一定接近

O(n)。

15.（）设指针p指向单链表中的一个结点，则语句序列u:=p^.next;

u:=u^.next将删除一个结点。

三．填空题（2分/题）

1．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结

点数是（129）。

2．已知栈的输入序列为1,2,3,...,n，输出序列为a,a,a,...,a，符合