发布时间 : 星期日 文章专升本数据结构考前必看更新完毕开始阅读878c518bd4d8d15abe234e9c
vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi，．．．vk，．．．，vj）和已经得到的从vi到vj且中间顶点序号不大于k-１的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。经过n次比较后必求得vi到vj的最短路径，依次，可求得各对顶点间的最短路径。 求解的关键是求解如下的一个n阶方阵序列：
＿＿
D(1)，D(0)，D(1)，．．．，D(k)，D(n1) 其中
D(＿1)[i][j]=G．arcs[i][j]
D(k)=Min{D(k-1)[i][j]，D(k-1)[i][k]+D(k-1)[k][j]} 0≤k≤n-1 【答案】 D(-1) D(0) D(1) D(2) D 0 1 2 0 1 2 0 1 2 0 1 2 0 0 1 7 0 1 7 0 1 4 0 1 4 1 2 P 0 1 2 ∞ 9 0 ∞ P(-1) 0 BA 1 2 0 3 0 ∞ 9 0 10 P(0) 1 AC 2 AB CB 0 3 0 ∞ 9 0 10 P(1) 1 AC 2 ACB CB 0 CBA BA 3 0 12 9 0 10 P (2) 1 AC BAC 2 ACB CB 3 0 AC AB CB BA BAC BA BAC 每对顶点之间的最短路径及长度总结如下： 顶点A到顶点C最短路径为：A->C，长度为：１ 顶点A到顶点B最短路径为：A->C->B，长度为：4 顶点C到顶点A最短路径为：C->B->A，长度为：12 顶点C到顶点B最短路径为：C->B，长度为：3 顶点B到顶点A最短路径为：B->A，长度为：9 顶点B到顶点C最短路径为：B->A->C，长度为：10
8.4 应用题
1．顺序查找时间为O(n)，二分法查找时间为O(log2n)，散列法为O(1)，为什么有高效率的查找方法而低效率的方法不被放弃?
【答案】不同的查找方法适用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率要高，而且也不是在所有情况下都可以采用。
2．对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 【答案】n-1次 【解析】设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。
3．若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：
（1）查找不成功，即表中无关键字等于给定值K的记录； （2）查找成功，即表中有关键字等于给定值K的记录。 【答案】
（1）不成功时需要n+1 次比较 （2）成功时平均为(n+1)/2次
【解析】有序表和无序表顺序查找时，都需要进行n+1次比较才能确定查找失败。因此平均查找长度都为n+1。查找成功时，平均查找长度都为(n+1)/2，有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。
4．设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。
【答案】
（1）查找a的过程如下(圆括号表示当前比较的关键字)，经过三次比较，查找成功。
下标 第一次比较 第二次比较 第三次比较 1 a a (a） 2 b b b 3 c (c） c 4 d d d 5 e e e 6 f f f 7 (g) g g 8 h h h 9 i i i 10 j j j 11 k k k 12 p p p 13 q q q 区间 [a..q] [a..f] [a..b] （2）g的查找过程如下，一次比较成功。
[a b c d e f (g) h i j k p q ] （3）n的查找过程如下， 经过四次比较，查找失败。 5．为什么有序的单
1 2 3 4 5 6 7 8 9 10 11 12 13 下标 区间 链表不能进行折半a b c d e f (g) h i j k p q [a..q] 第一次比较 查找?
h i (j) k p q [h..q] 为链表无第二次比较 a b c d e f g 【答案】因
h i j k (p) q [k..q] 机访问， 第三次比较 a b c d e f g 法进行随如
a b c d e f g h i j (k) p q [k] 第四次比较 果要访问链表的中
间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 6．构造有12个元素的二分查找的判定树，并求解下列问题： （1）各元素的查找长度最大是多少？
（2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？ （3）查找第5个元素依次要比较哪些元素？ 【答案】12个元素的判断树如下图所示： 6
3 9
1 4 7 11
2 5 8 10 12
（1）最大查找长度是树的深度4。
（2）查找长度为1的元素有1个，为第6个，查找长度为2的元素有2个，为第3个和第9个，查找长度为3的元素有4个，为第1、4、7、11个，查找长度为4的元素有5个，为第2、5、8、10、12个。
（3）查找第五个元素依次比较6，3，4，5。
7．以数据集合{1,2,3,4,5,6}的不同序列为输入，构造4棵高度为4的二叉排序树。 【答案】
4 6
6 1 3 2 5 1 4 3 2 5 图1 图2
2 2
1 4 1 59
3 5 3 6
6 4
图3 图4
8．直接在二叉排序树中查找关键码K与从中序遍历输出的有序序列中用二分查找法查找关键码K，其数据比较次数是否相同？
【答案】不相同。
【解析】因为二分查找得到的判定树和二叉排序树的形状不一定相同。 9．已知一棵二叉排序树如下： 38
28 49
17 34 47 55
22 35 48 50 56
（1）假如删除关键字28，画出新二叉树。 （2）若查找56，需和哪些关键字比较。 【答案】
（1）删除元素28后，需修改二叉排序树的形态，可用结点28左子树上最大的结点代替它如图（1），也可用其右子树上最小的结点代替它，如图（2）。
38 38 22 49 34 49 17 34 47 55 17 35 47 55 图（1） 图（2） 35 48 50 56 22 48 50 56 （2）若要查找56，需和38、49、55、56进行4次比较。
10．设散列函数为h(key)=key1，解决冲突的方法为线性探测，表中用\表示空单元。
0 1 2 3
202 304 507
（1）若删去散列表HT中的304（即令HT[1]=-1）之后，在表HT中查找707将会发生什么？
（2）若将删去的表项标记为\，查找时探测到\继续向前搜索，探测到\时终止搜索。请问用这种方法删去304后能否正确地查找到707？
【答案】 （1）查找707时，首先根据散列函数计算得出该元素应在散列表中的0单元，但是在0单元没有找到，因此将向下一单元探测，结果发现该单元是-1(为空单元)，所以结束查找，这将导致707无法找到。
（2）如果改用\作为删除标记，则可以正确找到707所在的结点。
11．已知散列表的地址区间为0～11，散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。
【答案】构造散列表如下（每个元素的查找长度标注在该元素的下方）。
等概率情况下成功时的平均查找长度为（1×5＋2＋3＋4＋5）/9＝19/9
12．设散列函数为H(k)=k % 11，采用拉链法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。
【答案】
在等概率情况下成功的平均查找长度为： (1*5+2*2+3*1+4*1)/9=16/9
13．假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查找长度。
【答案】
序号 1 2 3 4 5 6 7 8 9 10 元素值 32 75 29 63 48 94 25 46 18 70 初始地址 6 10 3 11 9 3 12 7 5 5 最终地址 6 10 3 11 9 4 12 7 5 8
构造的散列表如下：
0 1 2 3 4 5 6 7
29 94 18 32 46
在等概率情况下成功的平均查找长度为(1*7+2*5+3*1+4*1)/14=24/14
14．散列表的地址区间为0～15，散列函数为H(key)=key。设有一组关键字{19,01,23,14,55,20,84}, 采用线性探测法解决冲突，依次存放在散列表中。问：