发布时间 : 星期二 文章数据结构习题集更新完毕开始阅读b1f4ef3b16fc700aba68fc0d
4．在有向图的邻接表和逆邻接表中，每个顶点链表中链接着该顶点的所有 （6） 和 （7）结点。
5．若n个顶点的连通图是一个环，则它有 (8) 棵生成树。 6．图的逆邻接表存储结构只适用于 (9) 。
7．n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度是 （10） ，广度优先算法的时间复杂度是 （11） 。
8．n个顶点e条边的图，采用邻接表存储，广度优先遍历算法的时间复杂度是 （12） ，深度优先遍历算法的时间复杂度是 （13） 。
9．若要求一个稀疏图的最小生成树，最好用 (14) 算法求解。 10．若要求一个稠密图的最小生成树，最好用 （15） 算法求解。 四、应用题
1．已知图C=(V，E)，其中V={a，b，c，d，e}，E={(a，b)，{a，c}，{a，d}，(b，c)，(d，c)，(b，e)，(c，e)，（d，e）}要求： (1)画出图G；
(2)给出图G的邻接矩阵； (3)给出图G的邻接表；
(4)给出图G的所有拓扑有序序列。 2．已知带权无向图的邻接表见下图，要求： 0 1
2 3 4 5 6
(1)画出图G。
(2)各画一棵从顶点a出发的深度优先生成树和广度优先生成树。 (3)给出用prim算法从顶点a出发构造最少生成树的过程。 (4)给出用Kruscal算法构造最小生成树的过程。 3．已知带权有向图如右图所示，要求：
(1)给出图G的邻接矩阵； (2)给出图G的一个拓扑有序序列；
(3)求从顶点a出发到其余各顶点的最短路径。 4．已知带权有向图G见下图，图中边上的权值
13
a b c d e f g 1 0 1 0 0 0 2 9 9 2 3 2 8 8 3 2 3 2 3 1 3 3 2 7 7 4 3 9 4 5 6 4 5 4 4 2 3 8 4 4 4 1 ^ ^ 5 8 ^ 6 6 6 5 9 1 5 5 ^ ^ ^ ^ 为完成活动ai需要的天数，要求：
(1)求每项活动的最早和最晚开工时间；
(2)完成此项工程最少需要多少天； (3)给出图G的关键路径。
四、算法题
1.编写根据无向图G的邻接表，判断图G是否连通的算法。 2．编写根据有向图的邻接表，分别设计实现以下要求的算法： (1)求出图G中每个顶点的出度；
(2)求出图G中出度最大的一个顶点，输出该顶点编号； (3)计算图G中出度为0的顶点数； (4)判断图G中是否存在边〈i，j〉。
第七章 查找
一、单项选择题
1．在长度为n的线性表中进行顺序查找，在等概率的情况下，查找成功的平均查找长度是 (1) 。
(1)：A．n B．n(n+1)／2 C．(n-1)／2 D．(n+1)／2
2．在长度为n的顺序表中进行顺序查找，查找失败时需与键值比较次数是 (2) 。 (2)：A．n B．1 C．n-1 D．n+l
3．对线性表进行顺序查找时，要求线性表的存储结构是 （3） 。 (3)：A．倒排表 B．索引表 C．顺序表或链表 D．散列表 4．对线性表用二分法查找时要求线性表必须是 （4） 。
(4)：A．顺序表 B．单链表 C．顺序存储的有序表 D．散列表
5．在有序表A[80]上进行二分法查找，查找失败时，需对键值进行最多比较次数是 （5） 。
(5)：A．20 B．40 C．10 D．7
6．在长度为n的有序顺序表中，采用二分法查找，在等概率的情况下，查找成功的平均查找长度是 （6）。
(6)：A. O(n) B．O(nlog2n) C．O(n) D．O(log2n)
7．设顺序表为{4，6，12，32，40，42，50，60，72，78，80，90，98}，用二分法查找
14
2
72，需要进行的比较次数是 (7) 。 (7)：A．2 B．3 C．4 D．5
8．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则应采用的查找方法是 (8) 。
(8)：A．顺序查找 B．二分法查找 C．分块查找 D．都不行
9．在采用线性探查法处理冲突的散列表中进行查找，查找成功时所探测位置上的键值 (9) 。
(9)：A．一定都是同义词 B．一定都不是同义词 C．不一定是同义词 D．无任何关系
10．在查找过程中，若同时还要做插入、删除操作，这种查找称为 (10) 。 (10)：A．静态查找 B．动态查找 C．内部查找D． 外部查找 二、填空题
1．在有序表A[30]上进行二分查找，则需要对键值进行4次、5次比较查找成功的记录个数分别为 (1) 、 (2) ，在等概率的情况下，查找成功的平均查找长度是 (3) 。 2．散列法存储的基本思想是由 (4) ，确定记录的存储地址。
3．对一棵二叉排序树进行 (5) 遍历，可以得到一个键值从小到大次序排列的有序序列。 4．对有序表A[80]进行二分查找，则对应的判定树高度为 (6) ．，判定树前6层的结点个数为 (7) ，最高一层的结点个数是 (8) ，查找给定值K，最多与键值比较 (9) 次。 5．对于表长为n的线性表要进行顺序查找，则平均时间复杂度为 (10) ，若采用二分查找，则平均时间复杂度为 (11) 。
6．在散列表中，装填因子。值越大，则插入记录时发生冲突的可能性 (12) 。 7．在散列表的查找过程中与给定值K进行比较的次数取决于 (13) 、 (14) 和 (15)。 8．在使用分块查找时，除表本身外，尚需建立一个 (16) ，用来存放每一块中最高键值及 (17) 。
9．若表中有10000个记录，采用分块查找时，用顺序查找确定记录所在的块，则分成 (18)块最好，每块的最佳长度 (19) ，在这种情况下，查找成功的平均检索长度为 (20) 。 10．用n个键值构造一棵二叉排序树，最低高度是 (21) 。
11．设有散列函数H和键值k1、k2，若k1≠k2，且H(k1)= H(k2)，则称k1、k2是 (22)。 12．设有n个键值互为同义词，若用线性探查法处理冲突，把这n个键值存于表长为m(m>n)的散列表中，至少要进行 (23) 次探查。
13.高度为6的平衡二叉排序树，其每个分支结点的平衡因子均为0，则该二叉树共有 (24)个结点。
14．m阶B-树，除根结点外的分支结点最多有 (25) 棵子树，最少有 (26) 棵子树，最多有 (27) 个键值，最少有 (28) 个键值。
15．m阶B+树，除根结点外的每个结点最多有 (29) 棵子树值，最少有 (30) 棵子树。 三、应用题
1．画出对长度为13的有序表进行二分查找的一棵判定树，并求其等概率时查找成功的
15
平均查找长度。查找失败时需对键值的最多比较次数。
2．将整数序列{8，6，3，1，2，5，9，7，4}中的数依次插入到一棵空的二叉排序树中，求在等概率情况下，查找成功的平均查找长度，查找失败时对键值的最多比较次数。再画出从二叉排序树中删除结点6和8的结果。
3．将整数序列{8，6，3，1，2，5，9，7，41中的数依次插入到一棵空的平衡二叉排序树中，求在等概率情况下，查找成功的平均检索长度，查找失败时对键值的最多比较次数o
4．按不同的输入顺序输入4，5，6，建立相应的不同形态的二叉排序树。
5．设有键值序列{25，40，33，47，12，66，72，87，94，22，5，58}散列表长为12，散列函数为H(key)=key％11，用拉链法处理冲突，请画出散列表，在等概率情况下，求查找成功的平均查找长度和查找失败的平均查找长度。
6．已知一个散列函数为H(key)=key％13，采用双散列法处理冲突，H1(key)=key％11+1，探查序列为di=(H(key)+i* H1(key))％m，i=1，2，?m-1，散列表见表1，要求回答下列问题：
(1)对表中键值21，57，45和50进行查找时，所需进行的比较次数各为多少? (2)在等概率情况下查找时，查找成功的平均查找长度是多少? 0 1 2 3 4 5 6 7 8 9 10 11 12
表1 散列表
四、算法设计题
1．设二叉树用二叉链表表示，且每个结点的键值互不相同，请编写判别该二叉树是否为二叉排序树的非递归算法。
50 21 5 7 45 37 第八章 排序
一、单项选择题
1．对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方法，初始序列在 （1） 情况下，与排序码值总比较次数最少，在 （2） 情况下，与排序码值总比较次数最多；用直接插入排序方法，初始序列在 （3） 情况下，与排序码值总比较次数最少，在 （4） 情况下，与排序码值总比较次数最多；用快速排序方法在 （5） 情况下，与排序码值总比较次数最少，在 （5） 情况下与排序码值总比较次数最多。
(1)-(6)：
A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列
2．用冒泡排序方法对n个记录按排序码值从小到大排序时，当初始序列是按排序码值从大到小排列时，与码值总比较次数是 （7） 。 (7)：A．n-1 B．n C．n+1 D．n(n-1)／2
3．下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状态无关的是 (8) 。
16