12. 对图7.14所示的有向网，试利用Dijkstra算法求从源点1到其他各顶点的最短路径。
10 4 6
5 15 4 30 10 4 15 10 图7.14
2 20 2 1 3
13. 试写出图7.15所示有向图的所有拓扑排序，并指出应用教材中的算法求得的是哪个序列，设邻接表的
边表结点中的邻接点序号是递增的。 V0 V 1
V2 V3
V5 V4 V6 图7.15
14. 已知如图7.16所示的AOE网。求：
（1）每项活动的最早开始时间和最晚开始时间； （2）完成此工程最少需要多少单位时间； （3）关键活动与关键路径。
e3=3 5 2 e8=1
e1=3 e4=2
4 6 1 e7=2 e5=4
e2=2 e6=3 3
图7.16
15. 已知带权连通图，G（V,E）的邻接表如图7.17所示。试画出该图，并分别从顶点1开始的深度优先和
广度优先遍历之，给出遍历中结点的序列，最后画出该图的一棵最小生成树。其中表结点的三个域为
顶点号 边上的权值 指针
2 8 2 1 8 3 1 10 4 1 11 5 2 13 图 7.17 1 3 3 2 3 10 3 3 4 4 ∧ 11 5 ∧ 13 4 ∧ 4 5 ∧ 7 4 ∧ 7 ?0?116. 已知某图G的邻接矩阵为 ??0??1101001011?0??，顶点集合为{v1,v2,v3,v4} 1??0?（1）由邻接矩阵画出相应的图G；
（2）如果要使用此图成为完全图还要增加哪几条边。
17. 试利用弗洛伊德算法，写出如图7.18所示相应的带权邻接矩阵的变化。
6
3 8 2 3 9 5 1 1 图 7.18
4 10 2
18. 对于图7.19所示的AOE网络，计算各事件（顶点）的ve(vi)和vl(vj)和活动（边）的e(ai)和l(ai)函数值；
列出各条关键路径和关键活动。 a7=6 A
a1=1 a2=6 B D a8=2 a 9=7 E a11 =8 a20=10 a 17 =4 a13=11 W C a 16 =8 a 3=3 a4=4 F V a5=3 G a6=1 I a10=6 a=12 a 18 =4 22H J a14 =10 a19=9 a15=6 a=9 21K a12=5 图7.19
第8章
一、应用题
动态存储管理
1、 假设利用边界标识法首次适配策略分配，已知在某个时刻的可利用空间表的状态如图8.1所示：
pav 802 213 462 604 0 56 0 117 0 122 0 53 0 0 0 0
图8.1
（1）画出当文件系统回收一个起始地址为559、大小为45的空闲块之后的链表状态；
（2）画出系统继而在接受存储块大小为100的请求之后，又回收一块起始地址为515、大小为44的空闲块
之后的链表状态。
注意：存储块头部中大小域的值和申请分配的存储量均包括头和尾的存储空间。
2、组织成循环链表的可利用空间表可附加何条件时，首次适配策略转变为最佳适配策略？
3、设两个大小分别为100和200的空闲块依次顺序链接成可利用空间表。设分配一块时，该块的剩余部分在可利用空间表中保持原链接状态，试分别给出满足下列条件的申请序列： （1）最佳适配策略能够满足全部申请而首次适配策略不能； （2）首次适配策略能够满足全部申请而最佳适配策略不能。 4、考虑边界标志法的两种策略（最佳适配和首次适配）： （1）数据结构的主要区别是什么？ （2）分配算法的主要区别是什么？ （3）回收算法的主要区别是什么？
5、二进制地址011011110000，大小为（4）2的伙伴的二进制地址是什么？若块的大小为 （16）10时又如何？
6、已知一个大小为512字的内存，假设先后由6个用户提出大小分别为：23，45，52，100，11和9的分配请求，此后大小为45，52和11的占用块顺序被释放。假设以伙伴系统实现动态存储管理， （1）画出可利用空间表的初始状态；
（2）画出6个用户进入之后的链表状态以及每个用户所得的存储块的起始地址； （3）画出在回收三个用户释放的存储块之后的链表状态。
7、试求一个满足以下条件的空间申请序列a1,a2,…,an：从可用空间为25的伙伴管理系统的初始状态开始，a1,a2,…,an-1均能满足，而an不能满足，并使
?ai?1ni最小。
第九章：查找复习题
一、
选择题
1、顺序查找一个共有n个元素的线性表，其时间复杂度为（ ），折半查找一个具有n个元素的有序表，其时间复杂度为（ ）。
A、O(n) B、O(log2n) C、O(n2) D、O(nlog2n)
2、在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（ ）。 A、n B、[log2n] C、[log2(n+1)] D、「log2(n+1)
3、采用顺序查找方式查找长度为n的线性表时，平均查找长度为（ ） A、n B、n/2 C、(n+1)/2 D、(n-1)/2
4、采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（ ）对应判定树的高度（设高度大于等于2）。
A、小于 B、大于 C、等于 D、大于等于
5、已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（ ）。
A、1 B、2 C、3 D、4
6、对线性表进行折半查找时，要求线性表必须（ ）。
A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链接方式存储，且结点按关键字有序排序
7、顺序查找法适合于存储结构为（ ）的查找表。
A、散列存储 B、顺序或链接存储 C、压缩存储 D、索引存储
8、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（ ）个结点最佳。 A、10 B、25 C、6 D、625
9、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l，建立二叉排序树，则其先序遍历序列为（ ），中序遍历序列为（ ）。
A、abcloprstu B、alcpobsrut C、trbaoclpsu D、trubsaocpl 10、折半查找和二叉排序树的时间性能（ ）。 A、相同 B、不相同
11、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。 A、2k-1-1 B、2k-1 C、2k-1+1 D、2k-1
12、利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（ ）元素间的比较。
A、4次 B、5次 C、7次 D、10次
13、设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（ ）。 A、小于m的最大奇数 B、小于m的最大素数 C、小于m的最大偶数D、小于m的最大合数。 14、长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（ ）
A、24/10 B、 24/11 C、39/10 D、39/11
15、在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（ ）
A、n+1 B、1 C、n D、n-1
16、设哈希函数为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 21 46 21 19
37 37 9 9 9 37 46 30 30 30 19 46 19 20 20 B、 0 1 2 3 4 5 6 C、 0 1 2 3 4 5 6
D、 0 1 2 3 4 5 6 20 37 30 21 46 19 9 17、设有一个用线性探测法解决冲突得到的哈希表：
T: 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 哈希函数为H(key)=key,若要查找元素14，探测的次数是（ ） A、 3 B、 6 C、7 D、9 18、在哈希函数H(key)=key%m 中，一般来讲，m应取（ ）
A、奇数 B、偶数 C、 素数 D、充分大的数 19、分块查找的时间性能（ ）
A、低于二分查找 B、高于顺序查找而低于二分查找 C、高于顺序查找 D、低于顺序查找而高于二分查找 20、以下说法错误的是（ ）
A、哈希法存储的基本思想是由关键字的值决定数据的存储地址 B、哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C、装填因子是哈希法的一个重要参数，它反映哈希表的装填程度
D、哈希表的查找效率主要取决于哈希表造表时选取的散列函数和处理冲突的方法 21、以下说法正确的是（ ）
A、前序遍历二叉排序树的结点就可以得到排好序的结点序列
B、任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 C、对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的
D、采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要
22、已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是（ ） A、将该元素所在的存储单元清空 B、将该元素用一个特殊的符号代替
C、将与该元素有相同Hash地址的后继元素顺次前移一个位置 D、用与该元素有相同Hash地址的最后插入表中的元素替代
23、设哈希表长为M=14，哈希函数H（key）=key。表中已有4个结点：
ADDR(15)=4 ADDR(38)=5 ADDR(61)=6 ADDR(84)=7
其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是（ ） A、3 B、8 C、9 D、10
24、有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为（ ）
A、32/12 B、35/12 C、37/12 D、39/12
25、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应（ ）个结点最佳。
A、25 B、10 C、6 D、625
26、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（ ）查找方法。
A、分块 B、顺序 C、折半 D、散列 27、深度为6的AVL树至少有（ ）个结点。
A、10 B、12 C、20 D、21 28、哈希表的平均查找长度（ ）
A、与处理冲突的方法有关而与表的长度无关 B、与处理冲突的方法无关而与表的长度有关 C、与处理冲突的方法有关且与表的长度有关 D、与处理冲突的方法无关且与表的长度无关