数据结构作业任务.doc

上传人:一*** 文档编号:4542113 上传时间:2021-09-28 格式:DOC 页数:14 大小:2.33MB
返回 下载 相关 举报
数据结构作业任务.doc_第1页
第1页 / 共14页
数据结构作业任务.doc_第2页
第2页 / 共14页
点击查看更多>>
资源描述

《数据结构作业任务.doc》由会员分享,可在线阅读,更多相关《数据结构作业任务.doc(14页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、,第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

2、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

3、 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

4、 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 编写一个算法,实现频率计数自组织线性表启发式规则,假定线性表使用数组实现。特

5、别是编写一个函数FreqCount,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的最后,其频率计数是1。算法思想: 按顺序访问记录,每访问一条记录,该记录的访问数加1,如果该记录的访问数已经大于它前面记录的访问数,这条记录就在线性表中与前面的记录交换。 伪代码: template void FreqCount(Elem A, int count) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i 0) & (counti counti-1) swap(Ai, Ai-1); swap(co

6、unti, counti-1); 9.9 编写一个算法,实现移至前端自组织线性表启发式规则,假定线性表使用数组实现。特别是编写一个函数MoveToFront,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的开始位置。算法思想: 按顺序访问记录,每找到一个记录就把它放到线性表的最前面,而把其他记录后退一个位置。伪代码:template void MoveToFront(Elem A) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i 0) swap(Ai, A0); 9.10 编写一个算法,

7、实现转置自组织线性表启发式规则,假定线性表使用数组实现。特别是编写一个函数transpose,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的最后。算法思想:按顺序访问记录,把找到的记录与它在线性表中的前一条记录交换位置。伪代码:template void tanspose(Elem A) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i 2(10) - 4(20) - 6(2) - 2 - 1(10) - 3(3) - 4(5) - 3 - 2(3) - 5(15) - 4 - 1(20

8、) - 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

9、处理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时,就将其放入队列,如果还有顶点未被打印,而队列

10、已经为空,则图中包含回路。伪代码:void topsort (Graph*G,Queue) int Count G-n(); int v,w; for (v=0;vn();v+) Countv=0; for (v=0;vn();v+)for (w=G-first(v); wn; w=G-next(v,w) Countw+; for (v=0;vn();v+)if (Countv=0;) Q-enqueue(v); while (Q-length()!=0) Q-dequeue(v);printout(v);for (w=G-first(v); wn(); w=G-next(v,w) Count

11、w-; if (Countw=0) Q-enqueue(w); 11.13 编写一个算法确定一个有|V|个顶点的无向图是否包含回路。算法的时间代价应该是(|V|)。算法思想:用深度优先搜索的方法,如果遇到已经访问过的结点,则说明该无向图包含回路。伪代码:void DFS(int map, int a, int dep) if(dep1 & a = v) Printout(有环路); return; for(i=0;iN;i+) if(mapai = 1) DFS(map, i, dep+); void main() DFS(map, v, 1);11.15 对于图11.26所示的图,给出使用F

12、loyd的每对顶点间最短路径算法的结果。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

13、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

14、 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

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 教案示例

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁