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、深