16．一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少? 答：最大深度：n，最小深度：│logk(n(k-1))│+1
17．画出和已知序列对应的树T：树的前序序列为：ABCEFDGH；树的后序序列为：BEFCHGDA。 答：略.
五、算法设计题
1．以二叉链表作为存储结构，试编写求二叉树深度的算法。 答：int bdepth(btree t)
{ if (t==NULL) return 0; else
{l=bdepht(t->lchild); r=bdepht(t->rchild); return (l>r？l:r+1；} }
2．以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。 答：略.
第六节 图
一、选择题
1．在一个图中，所有顶点的度数之和等于所有边数的( )倍。 A．1／2 B．1 *C．2 D．4
2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。 A．1／2 *B．1 C．2 D．4
3．一个有N个顶点的无向图最多有( )条边。
A．N B．N*(N-1) *C．N*(N-1)／2 D．2N 4．具有4个顶点的无向完全图有( )条边， *A．6 B．12 C．16 D．20
5．具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 *A．5 B．6 C．7 D．8
6．一个具有N个顶点的无向图中，要连通全部顶点至少需要( )条边。 A．N B．N+1 *C．N-1 D．N／2
7．对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是( )。 A．N B．(N-1)*(N-1) C．N-1 *D．N*N
8．对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为((1))；所有邻接表中的结点总数是((2))。
(1) *A．N B．N+1 C．N-1 D．N+E (2)A．E/2 B．E *C．2E D．N+E
9．已知图7-1所示的图，若从顶点A出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为((1))；若按广度优先搜索法进行遍历，则可能得到的一种顶点序列为((2))。 (1)A．ABECDF B．ACFEBD C．AEBCFD *D．AEDFCB (2)A．ABCEDF *B．ABCEFD C．AEBCFD D．ACFDEB
10．采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。 *A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 11．采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。 A．前序遍历 B．中序遍历 C．后序遍历 *D．层次遍历
12．含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。 A．1 B．n／2 *C．n-1 D．n
21
13．一有向图的邻接表存储结构如图7-2所示。现在按深度优先遍历算法，从顶点v1出发，所得到的顶点序列是( )。
A．v1v3v2v4v5 B．v1v3v4v2v5 C．v1v2v3v4v5 *D．v1v3v4v5v2
14．设有两个无向图G=(V,E)，G’=(V’，E’)，如果G’是G的生成树，则下列说法不正确的是( )。 A．G’是G的子图 *B．G’是G的连通分量 C．G’是G的无环子图 D．G’是G的极小子图，且V’=V
15．任何一个带权的无向连通图的最小生成树( )。
A．只有一棵 *B．有一棵或多棵 C一定有多棵 D．可能不存在 16．设图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )。 A．O(n) *B．O(n+e) C．O(n*n) D．O(n*e)
17．在图7-3中，从顶点vl出发，按广度优先遍历图的顶点序列是( )。
A．V1V5V3V4V2V6V7 *B．V1V2V4V5V7V6V3 C．VlV5V3V4V2V7V6 D．VlV2V7V4V6V5V3
18．以下说法正确的是( )。
A．连通图的生成树是该连通图的一个极大连通子图 B．无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的 C．任何一个有向图，其全部顶点可以排成一个拓扑序列 *D．有回路的图不能进行拓扑排序
19．以下说法错误的是( )。
A．用邻接矩阵法存储图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关 *B．邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用 C．存储无向图的邻接矩阵是对称的，因此也可以只存储邻接矩阵的下(或上)三角部分 D．用邻接矩阵A表
m
示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第i行第j列的元素是否为0即可
20．以下说法正确的是( )。
A．连通分量是无向图中的极小连通子图 *B．强连通分量是有向图中的极大强连通子图 C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧 D．对有向图G，如果从任意顶点出发进行一次深度优先搜索或广度优先搜索能访问到每个顶点，则该图一定是完全图 二、判断题
√1．用邻接矩阵法存储图时，所占用的存储空间大小仅与图中结点个数有关。
╳2．对任意图，从它的某个顶点出发，进行一次深度优先搜索或广度优先搜索，即可访问图的每个顶点。 ╳3．任何有向网拓扑排序的结果是惟一的。 √4．有回路的图不能进行拓扑排序。
╳5．存储有向图的邻接矩阵一定是对称的。
√6．一个有向图G中若有弧
√7．含有10个顶点的无向连通图其生成树含有9条边。 ╳8．十字链表是图的一种顺序表示法。 三、填空题
1．对具有n个顶点的图，其生成树有且仅有__n-1_条边，即生成树是图的边数__最少_的连通图。 2．对无向图，其邻接矩阵是一个关于__主对角线_对称的矩阵。
3．在有向图的邻接矩阵上，由第i行可得到第__i__个结点的出度，而由第j列可得到第__j__个结点的入度。 4．对无向图，设有n个结点e条边，则其邻接表表示中需要_2e_个表结点。对有向图，设有n个顶点e条弧，则其邻接表表示需要__e_个表结点。
22
5．在无权图G的邻接矩阵A中，若(Vi，Vj)或
6．已知图G的邻接表如图7-4所示，从其顶点V1出发的深度优先搜索序列为___V1V2V3V6V5V4__，从其顶点v1出发的广度优先搜索序列为__V1V2V5V4V3V6___。
7．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是__第i列的元素之和__。删除所有从第i个结点出发的边的方法是__将第i行的元素清0____。
8．设无向图G中顶点数为n，则图G最少有__0___条边，最多有__n（n-1）/2__条边。若G为有向图，有n个顶点，则图至少有___0__条边，最多有___ n（n-1）__条边。
2
9．设图G有n个顶点和e条边，若采用邻接矩阵的存储结构，进行深度优先搜索的时间复杂度为__O(n)__；若采用邻接表存储结构，进行广度优先搜索的时间复杂度至少为___ O(e+n)___。 10．连通分量是无向图中的__ 极大__连通子图。
11．对无向图，若它有n个顶点e条边，则其邻接表中需要___n+2e__个结点。其中，___n__个结点构成头结点，___2e__个结点构成顶点表。
12．对有向图，若它有n个顶点e条边，则其邻接表中需要___n+e__个结点。其中，_n___个结点构成头结点，____e__个结点构成顶点表。
13．在邻接表上，无向图中顶点vi的度恰为__第i个链表中的结点数__。对有向图，顶点Vi的出度是__第i个链表中的结点数__。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为__i__的结点的个数是顶点vi的入度。
14．遍历图的基本方法有__深度__优先搜索和___广度__优先搜索两种。 四、应用题
1．给出如图7-6所示的无向图G1的邻接矩阵和邻接表。 答：略
2．分别给出图7-6所示的G2的邻接矩阵、邻接表和逆邻接表。 答：略
3．分别给出图7-6所示的G3从V5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。
答：深度优先：V5V4V3V2V1，广度优先：V5V4V2V3V1
4．设有一无向图G=(V，E)，其中V={1，2，3，4，5，6}，E={(1，2)，(1，6)，(2，6)，(1，4)，(6，4)，(1，3)，(3，4)，(6，5)，(4，5)，(1，5)，(3，5)}。
(1)按上述顺序输入后，画出其相应的邻接表。(2)在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
答：(1) 略 (2) DFS序列453162，BFS序列453612。
5．已知连通网的邻接矩阵如图7-8所示，顶点集合为{V1，V2，V3，V4，V5}，试画出它所表示的从顶点V1开始利用Prim算法得到的最小生成树。
23
答：略。
6．拓扑排序的结果不是惟一的，对图7-9进行拓扑排序，写出全部不同的拓扑排序序列。
答：拓扑排序序列：164275938，614275938，641275938。
7．已知图G的邻接表如图7-10所示，顶点V1为出发点，完成以下要求： (1)深度优先搜索的顶点序列。 (2)广度优先搜索的顶点序列。
答：(1)深度优先：V1V5V6V3V2V4 (2)广度优先：V1V2V4V5V3V6
第七节 查找
一、选择题
1．顺序查找法适合于( )存储结构的查找表。
A．压缩 B．散列 C．索引 *D．顺序或链式
2．对采用折半查找法进行查找操作的查找表，要求按( )方式进行存储。
A．顺序存储 B．链式存储 *C．顺序存储且结点按关键字有序 D．链式存储且结点按关键字有序 3．设顺序表的长为n，用顺序查找法,则其每个元素的平均查找长度是( )。 *A．(n+1)／2 B．(n-1)／2 C．n／2 D．n
4．设有序表的关键字序列为(1，4，6，10，18，35，42，53，67，71，78，84，92，99)，当用折半查找法查找键值为35的结点时，经( )次比较后查找成功。 A．2 B．3 *C．4 D．6
5．长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是( )。
A．24／10 B．24／11 C．39／10 *D．39／11
6．在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为( )。 *A．n+l B．1 C．n D．n-1
7．在采用链地址法处理冲突所构成的开散列表上查找某一关键字，在查找成功的情况下，所探测的这些位置上的键值( )。
*A．一定都是同义词 B．不一定都是同义词 C．都相同 D．一定都不是同义词 8．用顺序查找法对具有n个结点的线性表查找的时间复杂度量级为( )。
2
A．O(n) B．O (nlog2n) *C．O(n) D．O (log2n)
9．用折半查找法对具有n个结点的线性表查找的时间复杂度量级为( )。
2
A．O(n) B．O(nlog2n) C．O(n) *D．O(log 2n)
10．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值( )。
24
A．一定都是同义词 *B．不一定都是同义词 C．都相同 D．一定都不是同义词
11．设哈希函数为H(key)=key％7，一组关键字为(37，21，9，20，30，19，46)，哈希表T的地址空间为0..6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为( )。 A． 0 1 2 3 4 5 6 21 20 37 9 46 30 19 *B． 0 1 2 3 4 5 6 21 46 37 9 30 19 20 C． 0 1 2 3 4 5 6 21 19 9 37 30 46 20 D．0 1 2 3 4 5 6 20 37 30 21 46 19 9
12．设有一个用线性探测法解决冲突得到的哈希表：
0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14
哈希函数为H(key)=key％11，若要查找元素14，探测的次数是( )。 A．3 *B．6 C．7 D．9
13．在哈希函数H(key)=key％m中，一般来讲，m应取( )。 A．奇数 B．偶数 *C．素数 D．充分大的数 14．分块查找的时间性能( )。
A．低于折半查找 *B．高于顺序查找而低于折半查找 C．高于顺序查找 D．低于顺序查找而高于折半查找
15．以下说法错误的是( )。
A．哈希法存储的基本思想是由关键字的值决定数据的存储地址 *B．哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C．装填因子是哈希法的一个重要参数，它反映哈希表的装填程度 D．哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法 16．以下说法正确的是( )。
A．前序遍历二叉排序树的结点就可以得到排好序的结点序列 B．任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 C．对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的 *D．采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要
17．已知采用线性探测法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是( )。
A．将该元素所在的存储单元清空 *B．将该元素用一个特殊的符号代替 C．将与该元素有相同散列地址的后继元素顺次前移一个位置 D．用与该元素有相同散列地址的最后插入表中的元素替代
18．设哈希表长为M=14，哈希函数H(key)=key％11。表中已有4个结点：ADDR(15)=4，ADDR(38)=5，
ADDR(61)=6，ADDR(84)=7，其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是( )。
A．3 B．8 C．9 *D．10
19．有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为( )。
A．32／12 B．35／12 *C．37／12 D．39／12
20．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应( )个结点最佳。 *A．25 B．10 C．6 D．625
21．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用( )查找方法。 *A．分块 B．顺序 C．折半 D．散列
22．有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行( )次探测。 A．k-1 B．k C．k+l *D．k(k+1)／2
23．在关键字随机分布的情况下，用二叉排序树的方法进行查找，其平均查找长度与( )查找方法量级相当。 A．分块 B．顺序 *C．折半 D．散列
24．在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为( )。
2
*A．O(n) B．O(1) C．O(log2n) D．O(n) 25．哈希表的平均查找长度( )。
A．与处理冲突的方法有关而与表的长度无关 B．与处理冲突的方法无关而与表的长度有关 *C．与处理冲突的方法有关且与表的长度有关 D．与处理冲突的方法无关且与表的长度无关
26．若对长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3次计算的哈希地址为( )。
25
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库软件基础习题2009-10答案(5)在线全文阅读。
相关推荐：