A.二叉排序树 B.满二叉树 C.完全二叉树 D.判定树
20、若要在单链表中的结点 *p 之后插入一个结点 *s ，则应执行的语句是 ( )
A．s->next=p->next； p->next=s； B．p->next=s； s->next=p->next； C．p->next=s->next； s->next=p； D．s->next=p； p->next=s->next； 21、链表不具有的特点是（ ）。
A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比
22、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
23、递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表 24、设给定权值总数有n 个，其哈夫曼树的结点总数为( ) 。
A．不确定 B．2n C．2n+1 D．2n-1
25、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序
方法是（ ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 26、某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是（ ）。
A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子
27、下列说法正确的是（ ）。
(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索 (2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前 (3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值
A．(1)(2)(3) B．(1)(2) C．(1)(3) D．前面的可选答案都不对 28、下面的说法中正确的是（ ）。
(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义，具有三个节点的二叉树共有6种。
A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错
29、树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是（ ）。 A．树的后根遍历与其对应的二叉树的后根遍历相同
B．树的后根遍历与其对应的二叉树的中根遍历相同
C．树的先根遍历与其对应的二叉树的中根遍历相同 D．以上都不对 30、.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是
（ ）。
A. V1V2V3V4V5 B. V1V2V3V5V4 C. V1V4V3V5V2 D.V1V3V4V5V2
31、以下说法不正确的是（ ）。
A．无向图中的极大连通子图称为连通分量
B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索
32、设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，
84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（ ）。
A．8 B．3 C．5 D．9
33、对散列文件，以下说法错误的是（ ）。
A．散列文件插入、删除方便，不需要索引区且节省存储空间 B．散列文件只能按关键字随机存取且存取速度快 C．经过多次插入、删除后，可能出现溢出桶满的情况 D．散列文件顺序存取方便 34、二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，?，8，列下标为j=1，
2．?．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是（ ）。
A．A[8，5] B．A[3，10] C．A[5，8] D．A[0，9]
35、.在n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（ ）。
2
A. O(n) B. O(log2n) C. O(nlog2n) D. O(n)
三、判断题
1．如果两个串含有相同的字符，则这两个串相等。（ ）
2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。（ ） 3．二叉树是度为2的树。（ ）
4．在顺序表中取出第i个元素所花费的时间与i成正比。（ ） 5．在栈满情况下不能作进栈运算，否则产生“上溢”。 ( ） 6．图G的生成树是该图的一个极小连通子图。（ ） 7．所谓数据的逻辑结构指的是数据之间的逻辑关系。（ ） 8．二叉排序树的查找和折半查找的时间性能相同。（ ）
9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。（ ） 11、双向链表中至多只有一个结点的后继指针为空。（ ）
12、在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ）
13、对链表进行插入和删除操作时，不必移动结点。（ ） 14、栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ）
15、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧
18、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（ ）
19、二分查找要求序列顺序存储且关键字序列有序。（ ）
20、二路归并时，被归并的两个子序列中的关键字个数一定要相等。（ ） 21、调用一次深度优先遍历可以访问到图中的所有顶点。（ ）
22、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ） 23、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ） 24、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）
25、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ） 26、层次遍历初始堆可以得到一个有序的序列。（ ）
27、设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ） 28、线性表的顺序存储结构比链式存储结构更好。（ ） 29、中序遍历二叉排序树可以得到一个有序的序列。（ ） 30、快速排序是排序算法中平均性能最好的一种排序。（ ）
31、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ） 32、当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）
33、设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ） 34、完全二叉树中的叶子结点只可能在最后两层中出现。（ ） 35、哈夫曼树中没有度数为1的结点。（ ）
36、对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ） 37、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ） 38、由树转化成二叉树，该二叉树的右子树不一定为空。（ ） 39、线性表中的所有元素都有一个前驱元素和后继元素。（ ） 40、带权无向图的最小生成树是唯一的。（ ） 四、应用题
1、已知一棵二叉树的先根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树，并给出其后序序列。
2、将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） G D A J H I E B C L M K N O F P
类似例题：画出与下列二叉树对应的森林。
3、已知无向图如下所示： （1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。
4、假定用于通讯的电文仅有8个字母C1，C2，?，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，请先构建一棵哈夫曼树，计算其WPL值，并为这8个字母设计相应的哈夫曼编码。
5、已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中顺序依次插入初始为空的二叉排序树，要求：
(1)画出建立的二叉排序树（值的大小以字母顺序为准）。 (2)对该二叉排序树作中序遍历，试写出遍历序列。 (3)求出在等概率情况下查找成功的平均查找长度。 6、已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7};
E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20};
按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
________, ________, ________, ________, ________, ________, ________。
7、已知散列函数为H(K)=K mod 11,健值序列为{57，14，29，11，16，82，42，16，3}哈希表长为11，采用线性探测法处理冲突，试构造闭散列表，并计算查找成功的平均查找长度。
8、已知待排序的序列为（503，87，542，41，900，170，827，275，603，422），试完成下列各题。
(1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。 (2) 输出最小值后，如何得到次小值。（并画出相应结果图）。
9、下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示
修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出一个方案。
16 v1 v2
19 21 11 6 6
5 v6 33 18 14 v3
v5 v4