数据结构作业任务.doc
,第9章 检索的作业9.6 假定值A到H存储在一个自组织线性表中，开始按照升序存放。对于9.2小节建议的三种自组织启发式规则，按照下面顺序访问线性表，给出结果线性表和需要的比较总数。 D H H G H E G H G H E C E H G(1) 频率计数自组织线性表启发式规则： A B C D E F G H 比较次数D: D A B C E F G H 4H: D H A B C E F G 8H: H D A B C E F G 2G: H D G A B C E F 8H: H D G A B C E F 1E：H D G E A B C F 7G: H G D E A B C F 3H: H G D E A B C F 1G: H G D E A B C F 2H: H G D E A B C F 1E: H G E D A B C F 4C: H G E D C A B F 7E: H G E D C A B F 3H: H G E D C A B F 1G: H G E D C A B F 2比较总数=54(2)移至前端自组织线性表启发式规则： A B C D E F G H 比较次数D: D A B C E F G H 4H: H D A B C E F G 8H: H D A B C E F G 1G: G H D A B C E F 8H: H G D A B C E F 2E：E H G D A B C F 7G: G E H D A B C F 3H: H G E D A B C F 3G: G H E D A B C F 2H: H G E D A B C F 2E: E H G D A B C F 3C: C E H G D A B F 7E: E C H G D A B F 2H: H E C G D A B F 3G: G H E C D A B F 4比较总数=59(3)转置自组织线性表启发式规则： A B C D E F G H 比较次数D: A B D C E F G H 4H: A B D C E F H G 8H: A B D C E H F G 7G: A B D C E H G F 8H: A B D C H E G F 6E：A B D C E H G F 6G: A B D C E G H F 7H: A B D C E H G F 7G: A B D C E G H F 7H: A B D C E H G F 7E: A B D E C H G F 5C: A B D C E H G F 5E: A B D E C H G F 5H: A B D E H C G F 6G: A B D E H G C F 7比较总数=959.8 编写一个算法，实现频率计数自组织线性表启发式规则，假定线性表使用数组实现。特别是编写一个函数FreqCount，它把要检索的值作为输入，并且相应地调整线性表。如果值不在线性表中，就把它添加到线性表的最后，其频率计数是1。算法思想： 按顺序访问记录，每访问一条记录，该记录的访问数加1，如果该记录的访问数已经大于它前面记录的访问数，这条记录就在线性表中与前面的记录交换。 伪代码： template <class Elem>void FreqCount(Elem A, int count) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i<n; i+) if (Ai = val) break; else if (i = n) An = val; countn+ = 1; else counti+; while (i > 0) && (counti > counti-1) swap(Ai, Ai-1); swap(counti, counti-1); 9.9 编写一个算法，实现移至前端自组织线性表启发式规则，假定线性表使用数组实现。特别是编写一个函数MoveToFront，它把要检索的值作为输入，并且相应地调整线性表。如果值不在线性表中，就把它添加到线性表的开始位置。算法思想： 按顺序访问记录，每找到一个记录就把它放到线性表的最前面，而把其他记录后退一个位置。伪代码：template <class Elem>void MoveToFront(Elem A) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i<n; i+) if (Ai = val) break; if (i = n) An = val; while (i > 0) swap(Ai, A0); 9.10 编写一个算法，实现转置自组织线性表启发式规则，假定线性表使用数组实现。特别是编写一个函数transpose，它把要检索的值作为输入，并且相应地调整线性表。如果值不在线性表中，就把它添加到线性表的最后。算法思想：按顺序访问记录，把找到的记录与它在线性表中的前一条记录交换位置。伪代码：template <class Elem>void tanspose(Elem A) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i<n; i+) if (Ai = val) break; if (i = n) An = val; While (i != 0) swap(Ai, Ai-1); * 设散列函数为h(K) = K mod 7, 闭散列表的地址空间为0, , 6, 开始时散列表为空, 用线性探查法解决冲突, 请画出依次插入键值23, 14, 9, 6, 30, 12, 18后的散列表。 h(23)=2 h(14)=0 h(9)=2 h(6)=6 h(30)=2 h(12)=5 h(18)=401411822339430512669.16 使用闭散列，利用双散列方法解决冲突，把下面的关键码插入到一个有13个槽的散列表中（槽从0到12编号）。使用的散列函数H1和H2在下面定义。给出插入8个关键码值后的散列表。一定要说明如何使用H1和H2进行散列。函数Rev(k)颠倒10进制数k各个位的数字，例如，Rev(37)=73，Rev(7)=7。H1(k)=k mod 13。H2(k)=(Rev(k+1) mod 11)。关键码：2,8,31,20,19,18,53,27H1(2)=2 H2(2)=3 放在位置2H1(8)=8 H2(8)=9 放在位置8H1(31)=5 H2(31)=1 放在位置5H1(20)=7 H2(20)=1 放在位置7H1(19)=6 H2(19)=2 放在位置6H1(18)=5 H2(18)=3 放在位置5，但位置5已经有数据，5+3=8，位 置8也有数据8+3=11，放在位置11H1(53)=1 H2(53)=1 放在位置53H1(27)=1 H2(27)=5 放在位置1，但位置1已经有数据，1+5=6，位 置6也有数据，6+5=11，位置11也有数据， 11+5=3，放在位置3 015322327453161972088910111812 第11章 图的作业11.3 (a)画出图11.26所示图的相邻矩阵表示。1 2 3 4 5 6 10 20 210 3 5 3 15 20 5 11 10 15 11 32 10 3123456 (b)画出这个图的邻接表表示。1 -> 2(10) -> 4(20) -> 6(2) -> 2 -> 1(10) -> 3(3) -> 4(5) -> 3 -> 2(3) -> 5(15) -> 4 -> 1(20) -> 2(5) -> 5(11) -> 6(10) -> 5 -> 3(15) -> 4(11) -> 6(3) -> 6 -> 1(2) -> 4(10) -> 5(3) -> 11.4 对于图11.26所示的图，给出从顶点1开始DFS树。42163511.5 对于图11.26所示的图，给出从顶点1开始BFS树42163511.8 对于图11.26中的图，给出从顶点4出发，使用Dijkstra最短路径算法产生的最短路径表。请像图11.18所示那样，每处理一个顶点时给出相应D值。123456初始0处理420501110处理2155801110处理3155801110处理5155801110处理6155801110处理1155801110顶点4到顶点1的最短路径为15；顶点4到顶点2的最短路径为5；顶点4到顶点3的最短路径为8；顶点4到顶点4的最短路径为0；顶点4到顶点5的最短路径为11；顶点4到顶点6的最短路径为10。11.12 编写一个算法确定一个有|V|个顶点的有向图是否包含回路。算法的时间代价应该是（|V|+|E|）。算法思想：用广度优先拓扑排序的方法，首先访问所有的边，计算指向每个顶点的边数，将所有没有先决条件的顶点放入队列，然后开始处理队列，当从队列中删除一个顶点时，把它打印出来，同时将其所有相邻顶点的先决条件计数减1，当某个相邻顶点的计数为0时，就将其放入队列，如果还有顶点未被打印，而队列已经为空，则图中包含回路。伪代码：void topsort (Graph*G,Queue) int Count G->n(); int v,w; for (v=0;v<G->n();v+) Countv=0; for (v=0;v<G->n();v+)for (w=G->first(v); w<G->n; w=G->next(v,w) Countw+; for (v=0;v<G->n();v+)if (Countv=0;) Q->enqueue(v); while (Q->length()!=0) Q->dequeue(v);printout(v);for (w=G->first(v); w<G->n(); w=G->next(v,w) Countw-; if (Countw=0) Q->enqueue(w); 11.13 编写一个算法确定一个有|V|个顶点的无向图是否包含回路。算法的时间代价应该是（|V|）。算法思想：用深度优先搜索的方法，如果遇到已经访问过的结点，则说明该无向图包含回路。伪代码：void DFS(int map, int a, int dep) if(dep>1 && a = v) Printout("有环路"); return; for(i=0;i<N;i+) if(mapai = 1) DFS(map, i, dep+); void main() DFS(map, v, 1);11.15 对于图11.26所示的图，给出使用Floyd的每对顶点间最短路径算法的结果。0-path1 2 3 4 5 6 0 10 20 210 0 3 5 3 0 15 20 5 0 11 10 15 11 0 3 2 10 3 01234561-path1 2 3 4 5 6 0 10 20 210 0 3 5 12 3 0 15 20 5 0 11 10 15 11 0 3 2 12 10 3 01234562-path1 2 3 4 5 6 0 10 13 15 210 0 3 5 1213 3 0 8 15 1515 5 8 0 11 10 15 11 0 3 2 12 15 10 3 01234563-path1 2 3 4 5 6 0 10 13 15 28 210 0 3 5 18 1213 3 0 8 15 1515 5 8 0 11 1028 18 15 11 0 3 2 12 15 10 3 01234564-path1 2 3 4 5 6 0 10 13 15 26 210 0 3 5 16 1213 3 0 8 15 1515 5 8 0 11 1026 16 15 11 0 3 2 12 15 10 3 012345651 2 3 4 5 6-path 0 10 13 15 26 210 0 3 5 16 1213 3 0 8 15 1515 5 8 0 11 1026 16 15 11 0 3 2 12 15 10 3 01234561 2 3 4 5 66-path 0 10 13 12 5 210 0 3 5 16 1213 3 0 8 15 1512 5 8 0 11 10 5 16 15 11 0 3 2 12 15 10 3 012345611.18 对于图11.26中的图，给出从顶点3开始使用Prim的MST算法时各个边的访问顺序，并给出最终的MST。各个边的访问顺序：（3,2）（2,4）（2,1）（1,6）（6,5）最终MST：42163511.19 对于图11.26中的图，给出使用Kauskal的MST算法时各个边的访问顺序，每当把一条边添加到MST时，等价类数组的结果是什么（如图6.7那样显示数组内容）？165432 初始状态234561处理边（1,6）45261处理边（2,3）34261处理边（5,6）534261处理边（2,4）5342 处理边（1,2）1635等价类数组结果： 1 2 3 4 5 6初始状态 -1 -1 -1 -1 -1 -1处理边(1，6) -1 -1 -1 -1 -1 1处理边(2，3) -1 -1 2 -1 -1 1处理边(5，6) -1 -1 2 -1 1 1处理边(2，4) -1 1 2 -1 1 1处理边(1，2) -1 1 2 1 1 1
