版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
西南交通大学2019-2020学年第1学期期末考试A
课程代码3271035课程名称数据结构B考试时间120分钟
参考答案
一、单项选择题（每小题2分，共30分）
1~5CBDBA6~10CBDAC11-15ABCAC
二、判断题（正确的划“，错误的划“X”，每小题1分，共11分）
1~5VXVVX6~10XXVVX11V
三、填空题（每空1分，共18分）
1112B[16]3归并
4开放定址法5链地址法6AECBDF
76y/3x2+*+8实现栈的复制
9二叉树后序遍历递归算法10q->prior=p;
11d12013是否有环路
14n-115ala516索引表
175,3,8,12,77,65,16,97,27,7018确定性
四、算法填空（每空2分，共10分）
(1)pa=pa->data(2)pa
(3)0(4)hl>hr
(5)hl+1
五、综合题（共31分）
1、关键码序列（503,087,512,061,908,170,897,275,653,426）,执行希尔排序,
增量数组dlta[]={5,3,2,1）,请写出每一趟排序结束时的关键码状态。（4分）
解：
170087275061426503897512653908（1分）
061087275170426503897512653908（1分）
061087275170426503653512897908（1分）
061087170275426503653512897908（1分）
2、使用克鲁斯卡尔算法构造如图1所示的一棵最小生成树，并写出构造过程。（6分）
图1
解：每个图1分
44
©
（a）
（d）
⑴
3、对关键字序列（72,87,61,23,94,16,05,58）进行堆排序，使之按关键字递减
次序排列（小顶堆），请写出排序过程中得到的初始堆和前三趟的序列状态。（5分）
解：初始堆图2分，后面每一趟的图各1分
初始堆第I的
4、请将如图所示的森林转换成二叉树。（要求写出转换过程）（5分）
5、对如图3所示的有向图，试图利用Dijkstra算法求源点1到其他各顶点的最短路径,
要求给出相应的求解步骤。（6分）
图3
6
(1分)
6
6
25(1分)
6
（1分）
6
（1分）
（1分）
或按以下方式做：（表结构正确1分，i=l至IJi=5每列1分）
终点从1到各终点的D值和最短路径的求解过程
i=li=2i=3i=4i=5
220(1,2)19(1,3,2)
315(1,3)
400000029(1,3,6,4)
5000029(1,3,2,5)29(1,3,2,5)29(1,3,2,5)
60025(1,3,6)25(1,3,6)
Vj32645
S{1,3}{1,3,2)(1,3,2,6)(1,3,2,6,4)(1,3,2,6,4,5)
6、设电文由6个字符A,B,C,D,E,F组成，它们在电文中出现的次数分别为：10,
4,8,3,2,7,画出对应的哈夫曼树，并写出每个字符的编码。（5
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《2025智能设备采购委托项目管理合同》
- 2025合同范本食品供应合同
- 2025年委托借款合同模板
- 2025便利店店面转让合同范本
- 2025标准化的苗木购销合同
- 2025版商品房购买合同范本
- 2025年上海市农产品买卖合同示范文本
- 《年级魅力》课件
- 2025授权合同范本(标准)
- 《金融市场概述》课件
- 粮食熏蒸操作要点培训课件
- 同等学力申硕-同等学力(政治学)笔试（2018-2023年）真题摘选含答案
- 园林植物的识别与应用-灌木园林植物的识别与应用
- 亲子鉴定报告样本
- 饲料市场分析报告
- 六年级下册数学应用题练习100题及答案
- pvc的生产工艺流程图
- 我不能乱起外号课件
- 肝功能衰竭的护理指南
- 老年人营养健康的评估与改善
- Guilin桂林漓江-梦幻般的山水画卷
评论
0/150
提交评论