高等教育自学考试《数据结构》复习资料

一、单项选择（每空2分，共20分）

1、若某线性表中最常用的操作是在最后一个元素之前插入和删除元素，则采用___________最节省运算时间。

A、单链表

B、仅有头指针的单循环链表

C、仅有尾指针的单循环链表

D、双链表

2、哈夫曼树的带权路径长度WPL等于___________.

A、除根以外的所有结点的权植之和

B、所有结点权值之和

C、各叶子结点的带权路径长度之和

D、根结点的值

3、设输入序列为1，2，3，4，5，借助一个栈不可能得到的输出序列是___________.

A、1，2，3，4，5

B、1，4，3，2，5

C、4，1，3，2，5

D、1，3，2，5，4

4、对于下面二叉树，按后序遍历所得的结点序列为___________.

A、1234567

B、1245367

C、4251637

D、4526731

5、栈和队列都是___________.

A、顺序存储的线性结构

B、链式存储的线性结构

C、限制存储点的线性结构

D、限制存储点的非线性结构

6、已知完全二叉树有30个结点，则整个二叉树有___________个度为1的结点。

A、0

B、1

C、2

D、不确定

7、对下图，不能得到的拓扑序列是___________.

A、1，2，3，4，5，6，7，8

B、1，5，2，6，3，7，4，8

C、1，2，5，6，3，4，7，8

D、1，2，3，4，8，7，6，5

8、下列排序算法中，第一趟排序完毕后，其最大或最小元一定在其最终位置上的算法是___________.

A、归并排序

B、直接选择排序

C、快速排序

D、基数排序

9、下列排序方法中，排序所花费时间不受数据初始排列特性影响的算法是___________.

A、直接插入排序

B、冒泡排序

C、直接选择排序

D、快速排序

10、下列排序方法中，最好情况下，时间复杂度为O（N）的算法是___________.

A、选择排序

B、归并排序

C、快速排序

D、直接插入排序

二、判断题（每小题1分，共10分）

（ ）1、线性表的长度是线性表占用的存储空间的大小。

（ ）2、双循环链表中，任一结点的后继指针均指向其逻辑后继。

（ ）3、队列只能采用链式存储方式。

（ ）4、树（或森林）转化为对应的二叉树后，两者的分支数相等。

（ ）5、由二叉树的先序序列和中序序列能唯一确定一棵二叉树。

（ ）6、图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。

（ ）7、在用线性探查法解决冲突所构造的闭散列表中，每组同义词中至少有一个元素的地址正好等于其散列地址。

（ ）8、所谓冲突即是两个关键字的值相同的元素，其散列地址相同。

（ ）9、对n个元素的有序表用快速排序方法进行排序，时间复杂是O（n2）。

（ ）10、存在有偶数个结点的满二叉树。

三、填空题（每空2分，共20分）

1、在单链表中，若要删除指针P所指结点的后继结点，则需执行下列三条语句： U：=P↑。next；P↑。next：=U↑。next；___________.

2、设有一个链队列，结点结构为：队尾指针为Ls（≠nil），则执行入队操作时， S↑。next：=Ls↑。next；___________；___________.

3、单链表中指针P所指结点不为尾结点的条件是___________. 4、设数组B[1……4，1……5]中的任一元素均占3个单元，从首地址SA开始把数组B按行优先存储， 则元素B[3，4]的地址为___________. 5、在有n（n 0）个结点的二叉链表中，非空链域的个数为___________. 6、深度为6（根的层次号为i）的完全二叉树至多有___________个结点。

7、一个具有n个顶点的连通有向图至多有___________条边。

8、一棵二叉排序树中若存在30个结点其成功的查找长度≤6，则有___________个结点其成功的查找长度=4. 9、在对有10个数据的有序表作二分查找时，有___________个结点的查找长度是4. 10、在完全二叉树中，编号为i的结点的左孩子结点的编号为___________.

四、解答下列各题（共30分）

1、 以数据集{3，4，5，8，12，18，20，30}为叶子结点的权值，（1）构造一棵哈夫曼树 （4分）

（2）计算其带权路径长度（2分）。

2、已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，构造出该二叉树（6分）

先序序列 _BC_EF__中序序列 BDE_AG_H后序序列 _DC_GH_A

3、如图所示

（1）写出邻接矩阵（2分）

（2）求出其最小生成树（4分）

4、设散列函数H（X）=K MOD 7，若输入序列为 {100，90，120，60，78，35，42，31，15，20，22，12，16，27}，求：（1）构造出开散列表。

（2）求出在等概率查找情况下查找成功的平均查找长度。

5、有一个数据序列：25，50，70，100，43，7，12.现采用堆排序算法进行排序，写出每趟的结果。

五、算法设计题：（共20分）

1、设计一个用带头结点的单链表表示的直接插入排序算法，各结点结构如图：

要求：用类PASCAL语言写出算法（10分）

2、设二叉树采用二叉链表表示，各结点结构为：其中data为整数型字段。设计算法判别一棵二叉树是否是二叉排序树。（10分）