武汉理工大学852数据结构2018试卷复盘
需积分: 18 100 浏览量
2018-03-11
13:04:34
上传
评论 8
收藏 13KB DOCX 举报
2018 武汉理工大学 852 数据结构
一．十个选择题很基础的题
二．6 个填空题也很基础，一些基础知识
三．简答题
1. 矩阵为什么要采用线性存储结构
2. 拓扑排序可以用图的深度优先搜索来完成吗？如果可以说明方法，若不能说明原因
3. 给了段简单的不带头结点的链表代码，①问你某一句语句是干嘛（遍历链表找到最
后一个节点），②问你该代码执行完之后返回的结果是啥（把链表的第一个节点接到了链
表的最后）③问你代码的时间复杂度（0（n））
4. 我们在定义一个数据结构的时候通常会给出它的抽象数据类型，那么是不是可以说：抽
象数据类型就等于数据结构？说明为什么，并举出例子说明。
四．应用题
1. 给出一颗树的层次遍历和中序遍历要求画出这颗树
2. 依次向小根堆中插入元素，给出每一步的操作之后的结果
3. Hash 查找，用线性探测法解决冲突，分别计算查找成功的概率和失败的概率
4. 给了一个带权图，用 prim 算法生成最小生成树，给出构造过程
五．算法题（58 分）
①．用类 c 语言编写
②．写出数据类型定义
③．合理的注释
1. 编写一个高效的算法，删除线性表中所有值为 X 的元素，并使其他元素保持相对位置不
变，并能得出它的个数。(12 分）
2. 在线性结构中，选定一个元素，编写一个算法使他左边的元素都比他小，右边的元素都
比他大（考察快速排序）（12 分）
3. 图采用邻接表存储，编写算法判断一个有向图是否是强连通图（12 分）
4. 采 用 Human 算 法 对 图 片 进 行 压 缩 ， 并 保 存 。 例 如 ： 原 图 p.bmp 压 缩 后 保 存 为
p.human（22 分）
资源评论
