计算机软件技术基础(第三版)沈被娜 课后习题答案较全

V1作广度优先搜索:

(3)为了避免同一顶点被多次访问。

2.35.有一又向图如题图2.5所示： １ １

6

２

5 4

3

（1）写出每一结点的入度和出度各为多少； （2）写出上图的邻接矩阵和邻接表。 解：

V1:入度=3 出度=0 V2:入度=2 出度=2 V3:入度=1 出度=2 V4:入度=2 出度=2 V5:入度=2 出度=1 V6:入度=0 出度=4

1 ^ 2 3 4 5 6 1 4 ^ ^ ^ 2 3 1 1 ^ 6 5 ^ 2 4 5 ^

3.36 求题图2.6中结点a到各结点之间最短路径。

2 b e g

2 2 2 1 2 3 a d

3 1 4 1 c f h 解：

2.37 求题图2.7中所示AOV网所有可能的拓扑顺序结果。 解:

1 2 3 8 7 5

4 6 V1 0 V2 V3 V4 V5 V6 0 0 0 0 0 8 1 8 6 4 ^ ^ ^ ^ 3 4 ^ 8 ^ V7 0 V8 0 ^ 8 ^

拓扑排序：V7->V5->V2->V4->V6->V3->V1->V8 2.38 题图2.8所示AOE网，求:

(1).每一事件最早开始时间和最晚开始时间; (2).该计划最早完成时间为多少。 解:

活动最早最迟开始时间 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 E 0 0 5 6 6 12 12 12 19 19 16 L 4 0 9 6 16 12 19 16 19 19 23 L-E 4 0 4 0 10 0 7 4 0 0 7

a12 a13 a14 20 23 25 20 23 25 0 0 0

事件最早最迟开始时间 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 VE 0 5 6 12 19 16 20 23 25 27 VL 0 9 6 12 19 23 20 23 25 27

2.39某校97级同学举办运动会，报名同学学号为

97438，97102，97528，97136，97338，97250，97407，97239，97227，97517，97321，97421，97451，97241，97118，97543，97309 画出进行分块查找的数据组织形式。

2.40 画一棵对20个记录进行对分查找的判定树,并求等概率情况下的平均查找长度。

ASL=(1+2*2+3*4+4*8+5*5)/20=3.7

2.41设有10个记录的关键字为

ICKES，BARBER，ELYOT，KERN，FRENCE，LOWES，BENSDN，FONK，ERVIN，KNOX。构造α=10/13的哈希表，取关键字首字母表中的序号为哈希函数值，用随机探测解决冲突，di=(d1+Rj) mod 13，Rj取自伪随机数列：3，7，1，12，10，…。统计该表的平均查找长度ASL。

2.42对于给定的一组关键字：41,62,13,84,35,96,57,39,79,61,15,83。分别写出：插入排序、简单选择排序、堆排序、冒泡排序、快速排序、二叉树排序的排序过程，并对各排序方法进行分析。

排序，简单选择排序、堆排序、冒泡排序、快速排序、二叉树排序的排序过程，并对排序方法进行分析。

插入

13 41 62 84 35, 96,57,39, 79,61,15,83 13 35 41 62 84 96 57 39 79 61 15 83 13 35 41 57 62 84 96 39 79 61 15 83 13 35 39 41 57 62 84 96 79 61 15 83 13 35 39 41 57 62 79 84 96 61 15 83 13 35 39 41 57 61 62 79 84 96 15 83 13 15 35 39 41 57 61 62 79 84 96 83 13 15 35 39 41 57 61 62 79 83 84 96

对于具有n个记录的文件，要进行n-1趟排序 就地排序

稳定的排序方法

简单选择排序41，62，13，84，35，96，57，39，79，61，15，83 41 62 13 84 35 96 57 39 79 61 15 83 13 41 62 84 35 96 57 39 79 61 15 83 13 15 41 62 84 35 96 57 39 79 61 83 13 15 35 41 62 84 96 57 39 79 61 83 13 15 35 39 41 62 84 96 57 79 61 83 13 15 35 39 41 57 62 84 96 79 61 83 13 15 35 39 41 57 61 62 84 96 79 83 13 15 35 39 41 57 61 62 79 84 96 83 13 15 35 39 41 57 61 62 79 83 84 96

堆排序