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

2006年12月25日来源：字体：大小打印

　　一、单项选择（每空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、如图所示