版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、WORD格式第9章 检索的作业9.6 假定值 A 到 H 存储在一个自组织线性表中,开场按照升序存放。对于 9.2 小节建议的三种自组织启发式规那么,按照下面顺序访问线性表,给出结果线性表和需要的比较总数。DHHGHEGHGHECEHG(1) 频率计数自组织线性表启发式规那么:ABCDEFGH比较次数D:DABCEFGH4H:DHABCEFG8H:HDABCEFG2G:HDGABCEF8H:HDGABCEF1E:HDGEABCF 7G:HGDEABCF3H:HGDEABCF1G:HGDEABCF2H:HGDEABCF1E:HGEDABCF4C:HGEDCABF7E:HGEDCABF3H:HGE
2、DCABF1G:HGEDCABF2比较总数 =54(2) 移至前端自组织线性表启发式规那么:ABCDEFGH比较次数D:DABCEFGH4H:HDABCEFG8H:HDABCEFG1G:GHDABCEF8H:HGDABCEF2E:EHGDABCF 7G:GEHDABCF3H:HGEDABCF3G:GHEDABCF2H:HGEDABCF2E:EHGDABCF3C:CEHGDABF7E:ECHGDABF2H:HECGDABF3G:GHECDABF4专业资料整理WORD格式比较总数 =59(3) 转置自组织线性表启发式规那么:ABCDEFGH比较次数D:ABDCEFGH4H:ABDCEFHG8H:A
3、BDCEHFG7G:ABDCEHGF8H:ABDCHEGF6E:ABDCEHGF 6G:ABDCEGHF7H:ABDCEHGF7G:ABDCEGHF7H:ABDCEHGF7E:ABDECHGF5C:ABDCEHGF5E:ABDECHGF5H:ABDEHCGF6G:ABDEHGCF7比较总数 =959.8编写一个算法,实现频率计数自组织线性表启发式规那么,假定线性表使用数组实现。特别是编写一个函数 FreqCount ,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的最后,其频率计数是 1。算法思想:按顺序访问记录,每访问一条记录,该记录的访问数加 1,如果
4、该记录的访问数已经大于它前面记录的访问数,这条记录就在线性表中与前面的记录交换。伪代码: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;专业资料整理WORD格式elsecounti+;while (i > 0) && (counti > counti-1)
5、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
6、 (i=0; i<n; i+)if (Ai = val) break;if (i = n) An = val;while (i > 0)swap(Ai, A0);9.10 编写一个算法,实现转置自组织线性表启发式规那么,假定线性表使用数组实现。特别是编写一个函数 transpose ,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的最后。算法思想:按顺序访问记录,把找到的记录与它在线性表中的前一条记录交换位置。专业资料整理WORD格式伪代码:专业资料整理WORD格式template <class Elem>void tanspose
7、(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)=2h(14)=0h(9)=2h(6)=6h(30)=2h(12)=5h(18)=401411
8、822339430512669.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)=2H2(2)=3放在位置 2H1(8)=8H2(8)=9放在位置 8H
9、1(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,放在位置 11专业资料整理WORD格式H1(53)=1 H2(53)=1放在位置 53H1(27)=1 H2(27)=5放在位置 1,但位置 1 已经有数据, 1+5=6,位置 6 也有数据, 6+5=11,位置 11 也有数据,11+5=3,放在位置 3015322327453161972088910111812第11章 图的作业专业资料整
10、理WORD格式11.3 (a)画出图 11.26 所示图的相邻矩阵表示。1234561102022103533154205111051511362103(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)
11、-> 6 -> 1(2) -> 4(10) -> 5(3) -> 11.4对于图 11.26 所示的图,给出从顶点1 开场 DFS树。24163511.5对于图 11.26 所示的图,给出从顶点1 开场 BFS树24163专业资料整理WORD格式5专业资料整理WORD格式11.8 对于图 11.26 中的图,给出从顶点 4 出发,使用 Dijkstra 最短路径算法产生的最短路径表。请像图 11.18 所示那样,每处理一个顶点时给出相应 D 值。123456初始0处理 420501110处理 2155801110处理 3155801110处理 5155801110
12、处理 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| 。算法思想:用广度优先拓扑排序的方法, 首先访问所有的边,计算指向每个顶点的边数,将所有没有先决条件的顶点放入队列, 然后开场处理队列, 当从队列中删除一个顶点时,把它打印出来,同时将其所有相
13、邻顶点的先决条件计数减 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+;专业资料整理WORD格式for (v=0;v<G->n();v+)if (Cou
14、ntv=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
15、 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);专业资料整理WORD格式11.15 对于图 11.26 所示的图,给出使用 Floyd 的每对顶点间最短路径算法的结果。0-path1234561010202210035330 15420501110515110362 10301-path123456101020221003512330 154205011105
16、151103621210302-path123456101013152210035 12313308151541558011105 15110362121510303-path12345610101315282210035181231330815154155801110528181511036212151030专业资料整理WORD格式4-path123456101013152622100351612313308151541558011105261615110362121510305-path1234561010131526221003516123133081515415580111052616
17、15110362121510306-path12345610101312522100351612313308151541258011105516151103621215103011.18 对于图 11.26 中的图,给出从顶点 3 开场使用 Prim 的 MST算法时各个边的访问顺序,并给出最终的 MST。各个边的访问顺序:3,2 2,4 2,1 1,6 6,5 最终 MST:24163专业资料整理WORD格式5专业资料整理WORD格式11.19 对于图 11.26 中的图,给出使用 Kauskal 的 MST算法时各个边的访问顺序,每当把一条边添加到 MST时,等价类数组的结果是什么如图 6.7 那样显示数
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 湖南文理学院《儿童发展心理学》2022-2023学年第一学期期末试卷
- 湖南农业大学《插花艺术》2023-2024学年第一学期期末试卷
- 湖南工业大学科技学院《数字插画设计》2021-2022学年第一学期期末试卷
- 便秘的饮食误区健康宣教
- 化工机械专业复习题
- 2024年出纳工作计划报告
- 面包咖啡发酵生活节(酵醒生活主题)主题活动策划方案
- 北京市人民大学某中学2024届高考语文三模试卷含解析
- 安全生产月演讲稿2024(30篇)
- 2024至2030年中国网络设备管理软件行业投资前景及策略咨询研究报告
- 嵌入式系统结课设计论文
- 目标责任书-营销总监
- 英国签证户口本翻译模板(共4页)
- 飞行训练模拟器视景仿真系统方案
- 企业公司行政人事管理组织架构图带照片
- 高位钻孔设计参数计算
- 外研版八年级英语上册Module6Unit1说课稿
- 经纬度距离计算小工具-Distance_Formula
- ISO9001-2015培训教材(共166页).ppt
- 嘉陵江上-[原调-D]-钢琴伴奏正谱钢琴伴奏正谱高考声乐伴奏谱钢琴谱五线谱谱
- 并网前单位工程调试报告
评论
0/150
提交评论