数据结构画图题复习资料

（1）试找出满足下列条件的二叉树

① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同 先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下： （１） 若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树

（２） 若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （３） 若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．

（４） 若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树

（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C

①画出这棵二叉树。

②画出这棵二叉树的后序线索树。

③将这棵二叉树转换成对应的树（或森林）。

A BA B DECCA

DnullEC

DF

EG(

H

BF (1) (2)

GHFGH（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

初态:

1 2 3 4 5 6 7 8 9 10 11 12 13 weight 3 12 7 4 2 8 11 parent 0 0 0 0 0 0 0 0 0 0 0 0 0 lchild 0 0 0 0 0 0 0 0 0 0 0 0 0 rchild 0 0 0 0 0 0 0 0 0 0 0 0 0

终态 1 2 3 4 5 6 7 8 9 10 11 12 13 weight 3 12 7 4 2 8 11 5 9 15 20 27 47 parent 8 12 10 9 8 10 11 9 11 12 13 13 0 lchild 0 0 0 0 0 0 0 5 4 3 9 2 11 rchild 0 0 0 0 0 0 0 1 8 6 7 10 12

2．应用题 （1）已知如图6.27所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；

④ 逆邻接表。

图6.27 有

（2）已知如图6.28所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树

43  4  5 55   3 5 5597655495  46

图6.28 无

  

73632526 a b c d e f g h

→ b 4 → c 3 → a 4 → c 5 → a 3 → b 5 → b 5 → c 5 → b 9 → d 7 → d 6 → e 3 → d 5 → f 2 → c 5 → d 4 → d → d → e → f → g → h → g 5 5 7 3 2 6 6 → e → h → f ^ ^ ^ ^

9 ^ 5 ^ 6 → g 5 → h 4^

（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。

图6.29 邻接矩阵

图6.30 有向网

D 终点 b 15 (a,b) c d e f 2 (a,c) 12 (a,d) ∞ ∞ g S 终点集 {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} {a,c,f,e,d,g} {a,c,f,e,d,g,b} ∞ 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ 15 (a,b) 11 (a,c,f,d) 10 (a,c,e) 16 (a,c,f,g) 15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g) 15 (a,b) 15 (a,b) i=1 i=2 i=3 i=4 i=5 i=6 14 (a,c,f,d,g)

（5）试对图6.31所示的AOE-网：

① 求这个工程最早可能在什么时间结束； ② 求每个活动的最早开始时间和最迟开始时间； ③ 确定哪些活动是关键活动

图6.31 AOE-网

【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。

 Ve Vl 0 19 e l l17 0 0 <1, 2> 0 15 <1, 3> 15 27 0 19 15 <3, 2> 19 19 1  15 37 <2, 4> 19 27 2  29 38 <2, 5> 15 37 0 3  38 43 <3, 5> 29 38 <4, 6> 38 <5, 6> 4  43 5  6 -e 17 0 0 8 0 12 8 此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>

（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

① 画出描述折半查找过程的判定树；

② 若查找元素54，需依次与哪些元素比较？

③ 若查找元素90，需依次与哪些元素比较？

④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

①先画出判定树如下（注：mid=(1+12)/2=6）：

30

5 63

3 7 42 87

4 24 54 72 95 ②查找元素54，需依次与30, 63, 42, 54 元素比较；

③查找元素90，需依次与30, 63,87, 95元素比较；

④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08

（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。 12

7 17

2 11 16 21 4 9 13

验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21

（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）

① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③ 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 解：

（4）对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。

① 插入90 ② 插入25 ③ 插入45 ④ 删除60 50308 2080100 35 4060

（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：

① 画出哈希表的示意图；

② 若查找关键字63，需要依次与哪些关键字进行比较？

③ 若查找关键字60，需要依次与哪些关键字比较？

④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 ①画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 32 17 63 49 24 40 10 ②查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;

然后顺移，与46,47,32,17,63相比，一共比较了6次！

③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

④对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3+6）＝23/11 （6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

散列地址 0 关键字 14 1 01 2 9 3 23 4 84 5 27 6 55 7 20 8 9 比较次数 1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）%10=7（冲突） H2=（6+22）%10=0（冲突） H3=（6+33）%10=5 所以比较了4次。

（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。

① 线性探测法； ② 链地址法。 ① 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 4 1 12 1 49 1 38 2 13 1 24 2 32 1 21 2 比较次数 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11 ②

ASLsucc =（1*5+2*3）/8=11/8

ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11

（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：

① 画出哈希表的示意图；

② 若查找关键字63，需要依次与哪些关键字进行比较？ ③ 若查找关键字60，需要依次与哪些关键字比较？

④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解： （1）画表如下： 0 1 2 3 4 5 32 17 63 49 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 24 40 10 （2） 查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3+6）＝23/11

（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

散列地址 0 1 2 3 4 5 6 7 8 9 关键字 14 01 1 9 1 23 2 84 27 55 1 20 2 比较次数 1 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）%10=7（冲突）

23

H2=（6+2）%10=0（冲突） H3=（6+3）%10=5 所以比较了4次。 （7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。

① 线性探测法；

② 链地址法。

散列地址 0 关键字 比较次数 1 4 1 2 3 12 1 4 49 1 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8

ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11 2．应用题

（1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。

① 直接插入排序

② 折半插入排序

③ 希尔排序（增量选取5，3，1） ④ 冒泡排序 ⑤ 快速排序

⑥ 简单选择排序 ⑦ 堆排序

⑧ 二路归并排序

①直接插入排序

[2 12] 16 30 28 10 16* 20 6 18 [2 12 16] 30 28 10 16* 20 6 18 [2 12 16 30] 28 10 16* 20 6 18 [2 [2 [2 [2

12 10 10 10

16 12 12 12

28 16 16 16

30] 10 16* 20 28 30] 16* 20 16* 28 30] 20 16* 20 28 30]

6 6 6 6

18 18 18 18

[2 6 10 12 16 16* 20 28 30] 18 [2 6 10 12 16 16* 18 20 28 30]

② 折半插入排序 排序过程同①

③ 希尔排序（增量选取5，3，1）

10 2 16 6 18 12 16* 20 30 28 （增量选取5） 6 2 12 10 18 16 16* 20 30 28 （增量选取3） 2 6 10 12 16 16* 18 20 28 30 （增量选取1）

④ 冒泡排序

2 12 16 28 10 16* 20 6 18 [30] 2 12 16 10 16* 20 6 18 [28 30] 2 12 10 16 16* 6 18 [20 28 30] 2 10 12 16 6 16* [18 20 28 30] 2 10 12 6 16 [16* 18 20 28 30] 2 10 6 12 [16 16* 18 20 28 30]

2 6 10 [12 16 16* 18 20 28 30] 2 6 10 12 16 16* 18 20 28 30] ⑤ 快速排序

12 [6 2 10] 12 [28 30 16* 20 16 18] 6 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 28 2 6 10 12 [18 16 16* 20 ] 28 [30 ] 18 2 6 10 12 [16* 16] 18 [20] 28 30 16* 2 6 10 12 16* [16] 18 20 28 30 左子序列递归深度为1，右子序列递归深度为3

⑥ 简单选择排序

2 [12 16 30 28 10 16* 20 6 18] 2 6 [16 30 28 10 16* 20 12 18] 2 6 10 [30 28 16 16* 20 12 18] 2 6 10 12 [28 16 16* 20 30 18] 2 6 10 12 16 [28 16* 20 30 18] 2 6 10 12 16 16* [28 20 30 18] 2 6 10 12 16 16* 18 [20 30 28] 2 6 10 12 16 16* 18 20 [28 30] 2 6 10 12 16 16* 18 20 28 [30] ⑧ 二路归并排序

2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 18 20 28 30

⑦ 堆排序

第一步,形成初始大根堆（详细过程略），第二步做堆排序。

12 2 30 20 6 18 28 10 16 16* 2 20 6 12 28 18 30 16 10 16*

初始排序 不是大根堆 形成初始大根堆

12 28 16 20 18 10 16* 2 6 30 交换1与10对象 6 20 16 12 18 10 16* 2 28 30 交换1与9对象 2 18 16 12 6 10 16* 20 28 30 交换1与8对象 16* 12 16 2 6 10 18 20 28 30 交换1与7对象 28 20 16 12 18 10 16* 2 6 30 从1到9重新形成堆

20 18 16 12 6 10 16* 2 28 30 从1到8重新形成堆

18 12 16 2 12 10 16* 20 28 30 从1到7重新形成堆

16* 12 16 2 6 10 18 20 28 30 从1到6重新形成堆

10 12 16 2 6 16* 18 20 28 30 交换1与6对象 6 12 10 2 16 16* 18 20 28 30 交换1与5对象 12 6 10 12 16 16* 18 20 28 30 交换1与4对象 2 6 10 12 16 16* 18 20 28 30 交换1与3对象 16 12 10 2 6 16* 18 20 28 30 从1到5重新形成堆

12 6 10 2 16 16* 18 20 28 30 从1到4重新形成堆

10 6 2 12 16 16* 18 20 28 30 从1到3重新形成堆

6 2 10 12 16 16* 18 20 28 30 从1到2重新形成堆

2 6 10 12 16 16* 18 20 28 30 交换1与2对象 2 6 10 12 16 16* 18 20 28 30 得到结果