一、单项选择（每空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（n0）个结点的二叉链表中，非空链域的个数为___________. 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分）