「数据结构三次作业答案」.doc

第三阶段离线作业第七章图7.1 已知图7.1所示的有向图，请给出该图的DABCFE 每个顶点的入/出度； 邻接矩阵； 邻接表； 逆邻接表； 图7.1 （1）顶点ABCDEF入度141031出度202222（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）AEBCEFCDDECDFFA7.2 用深度优先搜索和广度优先搜索对图7.2进行遍历（从顶点1出发），给出遍历序列。61234578图7.2深度优先12485367广度优先12345678第九章 查找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，68，11，10，77，采用哈希函数： H(key)=key%13构造哈希表。 采用开放地址法的线性探测再散列方法解决冲突。 采用开放地址法的二次探测再散列方法解决冲突。 采用开放地址法的随机探测再散列方法解决冲突。 采用链地址法解决冲突。(1)哈希列表012345678910111213关键字011455276819208423111077(2)哈希列表0123456789101112关键字270114556884192010231177(3)哈希列表0123456789101112关键字840155142768192010231177(4)哈希列表0123456789101112指针015519202311771468841027第十章内部排序10.1 已知序列503，87，512，61，908，170，897，275，653，462，请给出采用快速排序法对该序列作升序排序时的每一趟结果。初始序列：503 87 512 61 908 170 879 275 653 462第一趟后：462 87 275 61 170 503 879 908 653 462第二趟后：170 87 275 61 462 503 897 908 653 512第三趟后：61 87 170 275 462 503 897 908 653 512第四趟后：61 87 170 275 462 503 879 908 653 512第五趟后：61 87 170 275 462 503 512 653 879 908第五趟后：61 87 170 275 462 503 512 653 879 90810.2 已知序列10，18，4，3，6，12，1，9，15，8，请给出采用归并排序法对该序列作升序排序时的每一趟结果。初始序列：10 18 4 3 6 12 1 9 15 8第一趟后：10 18 3 4 6 12 1 9 8 15第二趟后：3 4 10 18 1 6 9 12 8 15第三趟后：1 3 4 6 9 10 12 18 8 15第四趟后：1 3 4 6 8 9 10 12 15 1810.3 已知序列503，087，512，061，908，170，897，275，653，426，请给出采用归并排序法对该序列作升序排序时的每一趟结果。初始序列：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，执行以下排序算法，写出每一趟排序结束时的关键字状态。 起泡排序 直接插入排序 希尔排序 树形选择排序 堆排序 归并排序答：1 起泡排序：初始序列：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，503，426，512，653，897，908 第五趟后：061，087，170，275，426，503，512，653，897，908 2 直接插入排序：初始序列：（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 503 512） 908 170 897 275 653 426第四趟后：（061 087 503 512 908） 170 897 275 653 426第五趟后：（061 087 170 503 512 908） 897 275 653 426第六趟后：（061 087 170 503 512 897 908） 275 653 426第七趟后：（061 087 170 275 503 512 897 908） 653 426第八趟后：（061 087 170 275 503 512 653 897 908） 426第九趟后：（061 087 170 275 426 503 512 653 897 908）3 希尔排序：初始序列: 503 087 512 061 908 170 897 275 653 426 170 087 512 061 908 503 897 275 653 426 170 087 512 061 908 503 897 275 653 426 170 087 275 061 908 503 897 512 653 426 170 087 275 061 908 503 897 512 653 426第一趟后:170 087 275 061 426 503 897 512 653 908061 087 275 170 426 503 897 512 653 908第二趟后:061 087 275 170 426 503 897 512 653 908第三趟后:061 087 170 275 426 503 897 512 653 9084 树形选择排序：(参考教材P279内容，过程图略)5 堆排序： 初始序列：503，087，512，061，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 第六趟后：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 275