16．深度为5的二叉树至多有( )个结点。 A.16 B．32 C．31 D．10
17．在一非空二叉树的中序遍历序列中，根结点的右边( )。 A.只有右子树上的所有结点 B．只有右子树上的部分结点 C．只有左子树上的部分结点 D．只有左子树上的所有结点
18．设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是( )。 A. n在m右方 B．n是m祖先 C．n在m左方 D．n是m子孙 二、填空题:
1． 对于二叉树来说，第i层上至多有( 2
K
i-1
)个结点。
2． 深度为k的二叉树至多有( 2-1 )个结点。 3． 树中结点的最大层次称为树的( 深度 )。
4．由一棵二叉树的前序序列和(中序序列)可唯一确定这棵二叉树。 5．高度为5的完全二叉树至少有（ 16 ）个结点。
6．将一棵树转换成一棵二叉树后，二叉树根结点没有（ 右 ）子树。 7．一棵含有n个结点的完全二叉树，它的高度是（ floor(log2n)+1 ）。 8．含有n个结点的二叉树用二叉链表表示时，有（n+1）个空链域。 9．哈夫曼树是带权路径长度（最小）的二叉树。 10．具有m个叶结点的哈夫曼树共有（2m-1）个结点。
11．已知完全二叉树的第8层有8个结点，则其叶子结点数是（ 68 ）。
12．已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是（ 73 ）。 13.一棵二叉树的第i（i>=l）层最多有(2
i-1
)个结点；一棵有n（n＞0）个结点的满
二叉树共有( (n+1)/2 )个叶子和((n-1)/2 )个非终端结点。
14．现有按中序遍历二叉树的结果为abc，问有( 5 )种不同形态的二叉树可以得到这
一遍历结果，这些二叉树分别是( )。
15.以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树为（ ），其带权路径长度为（ ）。 三、简答题：
1．已知权值：4，2，5，7，5，请画出相应的哈夫曼树并计算其带权路径长度WPL。 2．如果二叉树的后序和中序分别为：A，C，D，B，G，I，H，F，E．和A，B，C，D，E，
F，G，H，I． 请给出二叉树的前序。
3．如何实现森林转化为一棵二叉树。
4．一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出，试求出空格处
的内容，并画出二叉树。
先序：＿B F＿ICEH G 中序：D＿KFIA EJC＿ 后序： K FBHJ G A 四，画图题
假设一颗二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树
第7章 图
一、单项选择题：
1．用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法的。 A．栈 B．队列 C．树 D．图
2．用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法的。 A．栈 B．队列 C．树 D．图
3．已知图的邻接矩阵，则从顶点0出发按深度优先遍历的结点序列是（ ）。
0 1 1 1 1 0 1 A. 0 2 4 3 1 5 6 1 0 0 1 0 0 1 B. 0 1 3 6 5 4 2 1 0 0 0 1 0 0 C. 0 4 2 3 1 6 5 1 1 0 0 1 1 0 D. 0 3 6 1 5 4 2 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 4．已知图的邻接矩阵同上题8，则从顶点0出发按广度优先遍历结点序列是（）。 A．0243651 B．0136425 C．0423156 D．0134256 5、深度优先遍历类似于二叉树的（ ）。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 6、广度优先遍历类似于二叉树的（ ）。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 7、任何一个无向连通图的最小生成树（ ）。
A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在
8、对于一个具有n个顶点的有向图，采用邻接矩阵表示该矩阵的大小是（ ）。 A. n B. (n-1) C. n-1 D. n
10、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量的大小为（）；所有弧结点的总数是（ ）。 ①A. n B. n+1 C.n-1 D.n+e ②A. e/2 B. e C. 2e D. n+e 二、填空题：
1、图有（邻接矩阵）、（ 邻接表）（十字链表）（邻接多重表）等存储结构，遍历图有（深度优先搜索）、（广度优先搜索）等方法。
2、有向图用邻接矩阵存储，第i行元素之和等于顶点i的（ 度 ）。 3、设有一稀疏图，则G采用（邻接表）存储较省空间。 4、设有一稠密图，则G采用（邻接矩阵）存储较省空间。
5、已知一个图用邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（邻接矩阵的第i行置0；如果是无向图，第i列也同时置0）。
6、若求一个稀疏图G的最小生成树，最好用（Kruskal）算法来求解。 7、若求一个稠密图G的最小生成树，最好用（ Prim ）算法来求解。 8、拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在（环）。 三．简答题
1. 已知图G如下所示，画出G的邻接矩阵和邻接表、逆邻接表。
A B C
D E 2. 假定无向图G有6个结点和9条边，并依次输入这9条边为（0，1），（0，2），（0，4），
（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。试从顶点0出发，分别写出按深度优先搜索和广度优先搜索进行遍历的结点序列。
2
2
3. 图G=（V，E），V=｛0，1，2，3，4，5｝，E=｛〈0，1〉｝，〈0，2〉，〈1，4〉，〈2，5〉，〈5，
4〉，〈4，3〉，〈5，3〉。写出图G中顶点的所有拓扑排序。 4. 从某源点到其余顶点的最短路径的计算方法。
5. 设无向图G的邻接矩阵如下所示，画出用Prim算法和Kruskal 算法所得的最小生成树。
∞ 1 2 2 2 1 ∞ 3 ∞ ∞ 2 3 ∞ 1 ∞ 2 ∞ 1 ∞ 3 2 ∞ ∞ 3 ∞
第9章 查 找
一、单项选择题：
1．顺序查找法适合于存储结构为（ ）的线性表。
A.散列存储 B．顺序存储或链接存储 C．压缩存储 D．索引存储 2．对线性表进行折半查找时，要求线性表必须( )。
A．以顺序方式存储 B．以链接方式存储
C．以顺序方式存储，且结点按关键字有序排序 D．以链接方式存储，且结点接关键字有序排序
3．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。 A . n B． n／2 C．（n＋ l）／2 D．（n－ 1）／2
4．采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。 A.O(n) B．O(nlog2n) C．O(n ) D．O(log2n)
6．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半
查找值为82的结点时，（ ）次比较后查找成功。 A. 1 B．2 C．4 D．8
7.设哈希表长m=14，哈希函数H（key）二key％11。表中已有4个结点：
addr(15)＝ 4 addr（38）＝5 addr（61）=6 addr（84）=7 其余地址为空, 如用二次探测再散列处理冲突，关键字为49的结点的地址是( )。 A. 8 B. 3 C．5 D．9
8.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内个元素等概率情
况下查找成功所需的平均查找长度为（ ）。
2
A. 35/12 B. 37/12 C．39/12 D．43/12
9．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采
用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。 A. 10 B．25 C．6 D．625
10.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用( )查找方法。
A. 分块 B．顺序 C．二分 D．散列
11.设有100个元素，用折半查找法进行查找时，最大比较次数是（ ）。
A. 25 B．50 C．10 D．7 （判定树的深度＝foor(log2n)+1） 12．设有100个元素，用折半查找法进行查找时，最小比较次数是（ ）。
A. 7 B．4 C．2 D．1
13．哈希函数有一个共同性质，即函数值应当以（ ）取其值域的每个值。
A. 同等概率 B．最大概率 C．最小概率 D．平均概率
14．设哈希地址空间为0..m-1，k为关键字，取哈希函数为H(k)=k % p，为了减少发生冲突的频率，一般取p为（ ）。
A. 小于m的最大奇数 B．小于m的最大偶数 C．小于m的最大质数 D．小于m的最大合数
15．某顺序存储的表格中有90000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值皆不同，用顺序查找法查找时，平均比较次数约为（ C ），最大比较次数约为（ D）。
A. 25000 B．30000 C．45000 D．90000
二、填空题：
1．在各种查找方法中，平均查找长度与结点个数n无关的查法方法是（ 哈希表查找）。 2．折半查找的存储结构仅限于（ 有序表 ），且是（ 顺序存储）。
3．在分块查找方法中，首先查找（ 索引表 ），然后再查找相应的（ 块 ）。 4．长度为255的表，采用分块查找法，每块的最佳长度是（ 15 ）。
5．假设在有序线性表A[l．．20]上进行折半查找，则比较一次查找成功的结点数为（1），则比较二次查找成功的结点数为（ 2 ），则比较三次查找成功的结点数为（ 4 ），则比较四次查找成功的结点数为（ 8 ），则比较五次查找成功的结点数为（ 5 ），平均查找长度为