数据结构三次作业答案

1、第三阶段离线作业第七章图7.1已知图 7.1 所示的有向图，请给出该图的 每个顶点的入 / 出度； 邻接矩阵； 邻接表； 逆邻接表；（ 1）顶点ABCDEF入度141031出度202222ABCFED图 7.1（ 2） A=0 1 0 0 0 10 0 0 0 0 00 1 0 0 1 00 0 1 0 1 01 1 0 0 0 00 1 0 0 1 0（ 3）ABFBCBEDCEEABFBE（ 4）AEBCEFCDDECD FFA7.2用深度优先搜索和广度优先搜索对图7.2 进行遍历（从顶点1 出发），给出遍历序列。1234567图 7.2深度优先1 2 4 8 5 36 7广度优先1 2

2、3 4 5 67 8第九章查找9.1画出长度为10 的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。等概率时查找成功的平均查找长度：ASLsucc =(1*1+2*2+3*4+4*3)/10=2.99.2 假设按下述递归方法进行顺序表的查找：若表长 10，则进行顺序查找，否则进行折半查找。试画出对表长 n=50 的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。ASLsucc =(1*1+2*2+3*4+(4+5+6+7+8)*8+9*3)/50=5.689.3设有一组关键字19 ， 01， 23， 14， 55， 20， 84， 27

3、，68， 11，10， 77 ，采用哈希函数：H(key)=key%13构造哈希表。 采用开放地址法的线性探测再散列方法解决冲突。 采用开放地址法的二次探测再散列方法解决冲突。 采用开放地址法的随机探测再散列方法解决冲突。 采用链地址法解决冲突。(1)哈希列表012345678910111213关键字011455276819208423111077(2)哈希列表0123456789101112关键字270114556884192010231177(3)哈希列表0123456789101112关键字840155142768192010231177(4)哈希列表0123456789101112指针

4、015519202311771468841027第十章内部排序10.1已知序列 503 ，87，512， 61， 908， 170，897，275，653，462 ，请给出采用快速排序法对该序列作升序排序时的每一趟结果。初始序列： 5038751261908170879275653462第一趟后： 4628727561170503879908653462第二趟后： 1708727561462503897908653512第三趟后： 6187170275462503897908653512第四趟后： 6187170275462503879908653512第五趟后： 61871702754625

5、03512653879908第五趟后： 618717027546250351265387990810.2已知序列 10 ，18，4，3，6，12，1， 9， 15， 8 ，请给出采用归并排序法对该序列作升序排序时的每一趟结果。初始序列： 10 1843 6 12 1915 8第一趟后： 10 1834 6 12 19815第二趟后： 3410 18 1 6912 815第三趟后： 13469 10 12 18 815第四趟后： 13468 910 12 15 1810.3已知序列 503 ，087， 512， 061，908，170， 897，275，653，426 ，请给出采用归并排序法对该

6、序列作升序排序时的每一趟结果。初始序列： 503 087 512 061 908 170 897 275 653 426第一趟后： 087 503 061 512 170 908 275 897 426 653第二趟后： 061 087 503 512 170 275 897 908 426 653第三趟后： 061 087 170 275 503 512 897 908 426 653第四趟后： 061 087 170 275 426 503 512 653 897 90810.4 已知序列 503 ， 087， 512， 061，908， 170， 897， 275， 653，426 ，执

7、行以下排序算法，写出每一趟排序结束时的关键字状态。起泡排序 直接插入排序希尔排序 树形选择排序堆排序 归并排序答：起泡排序：初始序列： 503， 087， 512，061， 908， 170， 897， 275， 653， 426第一趟后： 087， 503， 061，512， 170， 897， 275， 653， 426， 908第二趟后： 087， 061， 503，170， 512， 275， 653， 426， 897， 908第三趟后： 061， 087， 170，503， 275， 512， 426， 653， 897， 908第四趟后： 061， 087， 170，275， 5

8、03， 426， 512， 653， 897， 908第五趟后： 061， 087， 170，275， 426， 503， 512， 653， 897， 908直接插入排序：初始序列：（ 503） 087 512 061 908 170 897 275 653 426第一趟后：（ 087 503 ） 512 061 908 170 897 275 653 426第二趟后：（ 087 503 512） 061 908 170 897 275 653 426第三趟后：（ 061 087 503512） 908 170 897 275 653 426第四趟后：（ 061 087 503512908）

9、 170 897 275 653 426第五趟后：（ 061 087 170503512908） 897 275 653 426第六趟后：（ 061087170503512897908） 275 653 426第七趟后：（ 061087170275503512897908） 653 426第八趟后：（ 061087170275503512653897908） 426第九趟后：（ 061087170275426503512653897 908） 希尔排序：初始序列 : 503 087 512 061 908 170 897 275 653 426170087512 061908503897275

10、653426170087512061908503897275653426170087275061908503897512653426170087275061908 503897 512653426第一趟后 : 170087 275061426503897 512653908061087275 170426503897512653908第二趟后 : 061087275170 426503 897 512653908第三趟后 :061087170275426503 897512653908 树形选择排序：( 参考教材P279 内容，过程图略 )堆排序：初始序列： 503， 087， 512，061

11、， 908， 170， 897， 275， 653， 426第一趟后： 908， 653， 897，503， 426， 170， 512， 275， 061， 087第二趟后： 897， 653， 512，503， 426， 170， 087， 275， 061， 908第三趟后： 653， 503， 512，275， 426， 170， 087， 061， 897， 908第四趟后： 512， 503， 170，275， 426， 061， 087， 653， 897， 908第五趟后： 503， 426， 170，275， 087， 061， 512， 653， 897， 908第六趟后：

12、 426， 275， 170，061， 087， 503， 512， 653， 897， 908第七趟后： 275， 087， 170，061， 426， 503， 512， 653， 897， 908第八趟后： 170， 087， 061，275， 426， 503， 512， 653， 897， 908第九趟后： 087， 061， 170，275， 426， 503， 512， 653， 897， 908第十趟后： 061， 087， 170，275， 426， 503， 512， 653， 897， 908 （ 6）归并排序：初始序列： 503 087 512 061 908 170 897 27