发布时间 : 星期六 文章1数据结构习题及参考答案更新完毕开始阅读
C. 用邻接矩阵法储存图，占用的存储空间大小与图中边数喝顶点个数都有关
D. 用邻接矩阵法储存图，占用的存储空间大小只与图中边数有关，而与顶点个数无关 （10）设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,4>},则下列属于该有向图G的一种拓扑排序序列的是（）
A.1，2，3，4 B.2，3，4，1 C.1，4，2，3 D.1，2，4，3
(11)设有无向图G中的边集合E={(a,b)(a,e)(a,c)(b,e)(e,d)(d,f)(f,c)},则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。
A.aedfcb B.acfebd C.aebcfd D.aedfbc (12)连通图G中有n个顶点，G的生成树是（）连通子图。 A.包含G的所有顶点 B.包含G的所有边
C.不必包含G的所有顶点 D .包含G的所有顶点喝所有边
（13）设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。 A.n-1 B.n C. n+1 D. 2n-1
（14）设无向图G中有n个顶点，e 条边，则起对应的邻接中的表头结点喝边表结点的个数分别为（）。
A. n,e B.e.n C.2n,e D.n,2e
(15)用邻接矩阵A 表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C. 第i行0元素的个数之和 D. 第i列0元素的个数之和
（16）用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的出度为（）。 A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C. 第i行0元素的个数之和 D. 第i列0元素的个数之和 （17）可以判断一个有向图中是否含有回路的方法为（）。
A. 广度优先搜索 B. 深度优先搜索 C.拓扑排序 D. 求最短路径 6.2 填空题
（1）.一个连通无向图有5个顶点，8条边，则起生成树将要去掉（）条边。 （2）.在树结构和图结构中，前趋和后继结点之间分别存在（）和（）的联系。
（3）.有n 个顶点的连通图至少有（）条边；有n 个顶点的强连通图则至少有（）条边。 （4）.一个具有n个顶点的有向图至少有（）条弧。
（5）.如果不知道一个图是有向图还是无向图，但知道它的邻接矩阵是非对称的，那么这个图必定是（）。
（6）.在无向图G的邻接矩阵A中，若A[I][J]=1，则A[J][I]为（）。 （7）.无向图用邻接矩阵存储，其所有元素之和表示无向图的边数的（） （8）.无向图用邻接表存储，其所有边表结点之和表示无向图的边数的（） （9）.无向图用邻接表存储，顶点Vi的度为（）。 （10）.有向图用邻接表存储，顶点Vi的出度为（）。 （11）.图的遍历方式一般有（）和（）两种。 （12）.Prim算法的时间复杂度为（），与边数无关，因此适用于求边稠密的网的最小生成树。 （13）.如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图（）。 习题6参考答案 6.1 选择题
（1）C （2）A （3）B（4）C（5）B______条边。（6）B（7）A（8）A（9）B（10）A （11）A（12）A（13）B（14）A（15）B（16）A（17）C
6.2 填空
（1） 4
（2） 1对多 ; 多对多 （3） n-1 ; n （4） 0_
（5） 有向图 （6） 1 （7） 一半 （8） 一半
（9）___第i个链表中边表结点数___ （10）___第i个链表中边表结点数___ （11）深度优先遍历；广度优先遍历
2
（12）O（n） （13）___无回路
7.1选择题
（1）对于长度为n的无序线性表进行顺序查找，则查找成功、不成功时的平均数据比较次数分别为
A n/2 , n B n+1/2 ,n-1 C n+1/2 , n D n-1/2 ,n-1
（2）请指出在顺序表中{2,5,7,10,14,15,18,23,35,41,52}中，用二分法查找关键字码12须做 次关键字比较。
A 2 B 3 C 4 D 5
（3）对线性表进行折半查找时，必须要求线性表 。 A 以线性表方式存储 B 以链接式方式存储
C s以顺序方式存储，且结点按关键字有顺排列 D 以链接式方式存储，且结点按关键字有顺排列
（4）设二叉排序树中有n个结点，则二叉排序树的平均查找长度为 。 A O(1) B O(long
) C O（n） D （
）
（5）依次插入顺序（50,72,43,85,75,20,35,45,65,30）后建立的二叉搜索树中，查找元素35要进行 元素间的比较。
A 4次 B 5次 C 7次 D 10次
（6）一颗高度为5的理想平衡树中，最少含有16个结点，最多含有 个结点。 A 31 B 32 C 30 D 33
（7）对包含N个元素的散列表进行查找，平均查找度 。 A 为 O（long
） B 为O(N)
C 不直接依赖于N D 上述三者都不对
（8）设散列表中有m个存储单元，散列函数H(key)=key%p,则p最好选择 。 A 小于等于m的最大奇数 B 小于等于m的最大素数
C 小于等于m的最大偶数 D 小于等于m的最大合数 （9） 是Hash查找的冲突处理方法。
A 求余法 B 平方取中法 C 二分法 D 开放地址法
（10）当a的值较小时，散列存储通常比其他存储方式具有 的查找速度。
A 较慢 B 较快 C 相同 D 不确定
（11）对线性表进行折半查找，最方便的存储结构是 。 A 顺序表 B 有序的顺序表 C 链表 D 有序的链表 （12）对一个排好序的线性表，用二分法检索表中的元素，被检索的表应当采用 表示。
A 顺序存储 B 连接存储
C 散列法存储 D 存储表示不受限制
（13）若在线性表中采用折半查找法查找元素，该线性表应该 。（北京航天大学1999年试题）
A 元素按值有序 B 采用顺序存储结构
C 元素按值有序，且采用顺序存储结构 D元素按值有序 ，且采用链式存储结构
（14）用二分法查找一个长度为10的排好序的线性表，查找不成功时，最多需要比较 次。
A 5 B 2 C 4 D 1
（15）采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。 A 10 B 25 C 6 D 625
（16）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用 查找方法。
A 分块 B 顺序 C 二分 D 散列 7.2填空题
（1）对于长度为n的线性表，若进行顺序查找，则时间复杂度为 ；若采用折半法查找，则时间复杂度为 。
（2）假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为 ，比较两次查找成功的结点数为
，比较三次查找成功的结点数为 ， 比较四次查找成功的结点数为 ，比较五次查找成功的结点数为 ，平均查找长度为 。 （3）在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 该结点的值，右子树上所有结点的值一定 该结点的值。
（4）对于一棵二叉搜索树进行遍历时，得到的结点序列是一个 （5）在一棵m阶B-树上，每个非树根结点的关键字数目最少为 个，最多为 。
（6）对于线性表（70 ，34,55,23,65,41,20）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有 ，散列地址为6的有 。
（8）散列表中解决冲突的两种方法是 和 。 （11）最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度
最小的树，
其中对最优二叉树，n表示 ，对最优查找树，n表示 ，构成这两种树 。
（12）在分块检索中，对256个元素的线性表分成 块最好，每块的最佳长度是 ；若每块的长度为 ，其平均检索长度为 。 （14）哈希表处理冲突的方法有 。
（16）在分块查找中首先查找 ，然后查找相应的
（18）当所有的结点的权值都相等时，用这些结点构造的二叉排序树 遍历它们得到的序列的顺序是一样的。
(19)对两棵具有相同关键字集合而形状不同的二叉树， 遍历它们得到的序列的顺序是一样的。 习题7参考答案 7.1 选择题
（1）C (2)C (3) C (4)B (5) A (6)A (7) D (8)B (9)D (10) B (11)B (12)A (13)C (14)C (15)A (16)D (17)C (18)B,C (19)B (20)A 7.2 填空题
（1） O(n),O(log2n)
（2） 1,2,4,8,5, log2(n+1)-1 （3） 小于，大于 （4） 增序序列 （5） ?n/2? ,m-1
（6） 70; 34,20,55 （7） n/m
（8） 开放地址法，链地址法
（9） 产生冲突的可能性就越大，产生冲突的可能性就越小 （10） 关键码直接 （11） ②, ①, ⑦ （12） 16,16,8,21
（13） 直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法 （14） 开放地址法，再哈希法，链地址法，建立一个公共溢出区 （15） 装满程度 （16） 索引，快
（17） 哈希函数，装填因子 （18） 一个结点 （19） 中序 （20） 等于
习题8 8.1选择题
（1）下述排序算法中，稳定的是 。
A.直接选择排序 B.直接插入排序 C.快速排序 D.堆排序
（2）下列排序算法中， 需要的辅助储存空间最大。 A.快速排序 B.插入排序 C.希尔排序 D.基数排序
（3）下列各种排序算法中平均时间复杂度为O（n2）是 。