C版数据结构所有作业及答案合集.pdf

1 第一章第一章 绪论绪论 1 数据结构课程研究的内容是什么 其中哪个方面和计算机无关 数据结构课程研究的内容是什么 其中哪个方面和计算机无关 答 非数值计算 包括数据的答 非数值计算 包括数据的 逻辑结构 存储结构 操作的实现逻辑结构 存储结构 操作的实现 2 数据结构按逻辑结构可分为哪几类 不要简单答线性和非线性 数据结构按逻辑结构可分为哪几类 不要简单答线性和非线性 3 为什么要进行算法分析 分析算法的效率以求改进 算法分析主要研究哪几个方面 为什么要进行算法分析 分析算法的效率以求改进 算法分析主要研究哪几个方面 时间效率和空间效率 即 空间复杂性和时间复杂性 时间效率和空间效率 即 空间复杂性和时间复杂性 4 分析下面各程序段的时间复杂度 分析下面各程序段的时间复杂度 5 数据结构被形式地定义为 数据结构被形式地定义为 D R 其中 其中 D 是是 数据元素数据元素 的有限集合 的有限集合 R 是是 D 上 的 上 的 关系关系 有限集合 有限集合 设有数据逻辑结构设有数据逻辑结构 S D R 试按各小题所给条件画出 这些逻辑结构的图示 并确定相对于关系 试按各小题所给条件画出 这些逻辑结构的图示 并确定相对于关系 R 哪些结点是开始结点 哪些结点是 终端结点 哪些结点是开始结点 哪些结点是 终端结点 1 严蔚敏习题集严蔚敏习题集 P7 1 3 D d1 d2 d3 d4 R d1 d2 d2 d3 d3 d4 d1 d2 d3 d4 R d1 d2 d2 d3 d3 d4 答 d1 d2 d3 d4 d1 无直接前驱 是首结点 d4 无直接后继是尾结点答 d1 d2 d3 d4 d1 无直接前驱 是首结点 d4 无直接后继是尾结点 2 s 0 for i 0 i n i for j 0 j n j s B i j sum s 1 for i 0 i n i for j 0 j m j A i j 0 3 x 0 for i 1 i n i for j 1 j n i j x 解 因为 x 共执行了 n 1 n 2 1 n n 1 2 所以执行时间为 O n2 4 i 1 while i n i i 3 答 O log3n 2 1 1 D d1 d2 d9 R d1 d2 d1 d3 d3 d4 d3 d6 d6 d8 d4 d5 d6 d7 d8 d9 d1 d2 d9 R d1 d2 d1 d3 d3 d4 d3 d6 d6 d8 d4 d5 d6 d7 d8 d9 答 此图为树形结构 d1 无直接前驱 是根结点 d2 d5 d7 d9 无直接后继 是叶子结点 答 此图为树形结构 d1 无直接前驱 是根结点 d2 d5 d7 d9 无直接后继 是叶子结点 2 2 D d1 d2 d9 R d1 d3 d1 d8 d2 d3 d2 d4 d2 d5 d3 d9 d5 d6 d8 d9 d9 d7 d4 d7 d4 d6 d1 d2 d9 R d1 d3 d1 d8 d2 d3 d2 d4 d2 d5 d3 d9 d5 d6 d8 d9 d9 d7 d4 d7 d4 d6 答 此图为图形结构 d1 d2 无直接前驱 是开始结点 d6 d7 无直接后继 是终端结点 答 此图为图形结构 d1 d2 无直接前驱 是开始结点 d6 d7 无直接后继 是终端结点 2 3 学习方法提示 同学们一定要把教材阅读 理解以后再做题 暂时不要做那些针对考试的 茴香豆的茴 有几种写法的题 以后要参加那些考试的时候再说 平时一定要以理解为核心 没有必要 把一些细枝末节 甲乙丙丁的条款记住 甚至有些说法 这样说也有理 那样说也有理 没 有必要钻牛角尖 比如上面习题中 数据结构分几类 有的教材上写 线性和非线性二类 有的写 线性 树 图三类 还有的写 线性 树 图 集合四类 作者是从不同的角度 去看待的 作为学习 这个问题所谓的 标准答案 是次要的 不要强记公式 公式应该是自己理解 自己能推导出来 比如评价顺序表的删除操作的 复杂度 你应该记得思路 而不是公式 完全忘记了也没关系 我本人就不记得很多公式 但是要用的时候知道怎么自己推导出来 知道去哪里找到这个公式 那就行了 有些公式 在自己的工作中老用老用的 自然就记住了 人的大脑是有限的 要把这有限的 存储容量 用来记住你要用的东西 至于将来要参加程序员的考试的时候 需要 标准答案 和考试速度的时候才需要多看 那些试题及所谓的 标准答案 那些考试 总是把一个简单的说法用很复杂的方式转弯抹 角地说出来 但在学习的过程中应该抓住实质与核心 而不是把精力放在牛角尖上 在你不 熟悉教材内容的时候 你发现那些说法都是晦涩难懂的 而当你渐渐地熟悉问题的实质以后 大多数问题对你来说都是自然而然的 是你自己能解决的 欢迎大家共同讨论学习的方法 以后同学们和我的心得将整理以后继续发出 杨华 谨识 3 第二章第二章 线性表线性表 一 填空 1 向一个长度为 n 的向量的第 i 个元素 1 i n 1 之前插入一个元素时 需向后移动 n i 1 个元素 向一个长度为 n 的向量中删除第 i 个元素 1 i n 时 需向前移动 n i 个元素 2 顺序表中插入或删除一个元素 需要平均移动 表中一半元素 具体移动的元素个数与 表长和该元素 在表中的位置 有关 在顺序表中访问任意一结点的时间复杂度均为 O 1 因此 顺序 表也称为 随机存取 的数据结构 一个向量第一个元素的存储地址是 100 每个元素的长 度为 2 则第 5 个元素的地址是 108 向一个有 127 个元素的顺序表中插入一个新元 素并保持原来顺序不变 平均要移动 63 5 个元素 3 在 n 个结点的单链表中要删除已知结点 p 需找到它的前驱结点的地址 其时间复杂度 为 O n 现有一个具有五个元素的线性表 L 23 17 47 05 31 若它以链接方式存储在下列 100 119 号地址空间中 每个结点由数据 占 2 个字节 和指针 占 2 个字节 组成 如下所示 05 U 17 X23V31Y47Z 100 120 其中指针 X Y Z 的值分别为多少 该线性表的首结点起始地址为多少 末结点的起始地 址为多少 10 分 答 X 116 Y 0 Z 100 首址 108 末址 112 小心 二 简答题 1 试比较顺序存储结构和链式存储结构的优缺点 在什么情况下用顺序表比链表好 答 顺序存储时 相邻数据元素的存放地址也相邻 逻辑与物理统一 要求内存中可用存储单元的地 址必须是连续的 优点 存储密度大 用动态分配的方法 一般都情况下都接近 1 存储空间利用率高 缺点 插入或删除 元素时不方便 顺序表才适合随机存取 链式存储时 相邻数据元素可随意存放 但所占存储空间分两部分 一部分存放结点值 另一部分 存放表示结点间关系的指针 优点 插入或删除元素时很方便 使用灵活 缺点 存储密度小 lchild 叶子结点 else return Leaf Count T lchild Leaf Count T rchild 左子树的叶子数加 上右子树的叶子数 LeafCount BiTree 3 编写按层次顺序 同一层自左至右 遍历二叉树的算法 或 按层次输出二叉树中所有结点 解 思路 既然要求从上到下 从左到右 则利用队列存放各子树结点的指针是个好办法 这是一个循环算法 用 while 语句不断循环 直到队空之后自然退出该函数 技巧之处 当根结点入队后 会自然使得左 右孩子结点入队 而左孩子出队时又会立即使 得它的左右孩子结点入队 以此产生了按层次输出的效果 void LayerOrder Bitree T 层序遍历二叉树 InitQueue Q 建立工作队列 EnQueue Q T while QueueEmpty Q 字母编号对应编码 出现频率 1 1100 0 07 2 00 0 19 3 11110 0 02 4 1110 0 06 5 10 0 32 6 11111 0 03 7 01 0 21 8 1101 0 10 字母编号 对应编码 出现频率 1 000 0 07 2 001 0 19 3 010 0 02 4 011 0 06 5 100 0 32 6 101 0 03 7 110 0 21 8 111 0 10 11 DeQueue Q p visit p if p lchild EnQueue Q p lchild if p rchild EnQueue Q p rchild LayerOrder 12 第七章第七章 图图 1 在一个图中 所有顶点的度数之和等于图的边数的 2 倍 2 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和的 1 倍 3 有 8 个结点的无向图最多有 28 条边 4 有 8 个结点的有向完全图有 56 条边 5 有 8 个结点的无向连通图最少有 7 条边 6 有向图 G 用邻接表矩阵存储 其第 i 行的所有元素之和等于顶点 i 的 出度 7 设有一稀疏图 G 则 G 采用 邻接表 存储较省空间 设有一稠密图 G 则 G 采用 邻 接矩阵 存储较省空间 选填邻接表 邻接矩阵 8 如果 n 个顶点的图是一个环 则它有 n 棵生成树 以任意一顶点为起点 得 到 n 1 条边 9 已知图的邻接矩阵如下 根据算法思想 则从顶点 0 出发按深度优先遍历 的结点序列是 0 1 3 4 2 5 6 按广度优先遍历的结点序列是 0 1 2 3 4 6 5 10 已知图的邻接表如下所示 根据算法 则从顶点 0 出发按深度优先遍历的结点序列是 0 1 2 3 11 已知图的邻接表如下所示 根据算法 则从顶点 0 出发按广度优先遍历的结点序列是 0 3 2 1 12 用邻接表表示图进行广度优先遍历时 通常是采用 队列 来辅助实现算法的 13 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的 14 请对下图的无向带权图 1 按普里姆算法求其最小生成树 计算生成树权值 和 2 按克鲁斯卡尔算法求其最小生成树 计算生成树 0100011 1011000 0101101 0110011 0010001 1001001 1011110 13 权值和 3 根据上面两问 你可能猜测什么出什么结论 解 设起点为 a 可以直接由原始图画出最小生成树 而且最小生成树只有一种 类 15 复习电子讲义中利用 Dijkstra 算法求图中从顶点 a 到其他各顶点间的最短路径的算法 此题不交 最小生成树 最小生成树 14 第八章第八章 查找查找 1 在数据的存放无规律而言的线性表中进行检索的最佳方法是在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找 线性查找 顺序查找 线性查找 2 假设在有序线性表假设在有序线性表 a 20 上进行折半查找 则比较一次查找成功的结点数为上进行折半查找 则比较一次查找成功的结点数为 1 比较两次 查找成功的结点数为 比较两次 查找成功的结点数为 2 比较四次查找成功的结点数为 比较四次查找成功的结点数为 8 平均查找长度为 平均查找长度为 3 7 设有 设有 100 个结点 用二分法查找时 最大比较次数是个结点 用二分法查找时 最大比较次数是 7 对 对 22 个记录的有序 表作折半查找 当查找失败时 至少需要比较 个记录的有序 表作折半查找 当查找失败时 至少需要比较 5 次关键字 次关键字 解 显然 平均查找长度 O log解 显然 平均查找长度 O log2 2n n 5 次 2high return 0 查找不到时返回 0 mid low high 2 if ST elem mid key key return mid else if ST elem mid key key return Search Bin Recursive ST key low mid 1 else return Search Bin Recursive ST key mid 1 high Search Bin Recursive 16 排序排序 注意 不要抄书 一定要自己画出结果 有余力的同学请阅读复杂度分析 否则只需要了解 第 8 题结论 电子讲义上的程序还是要尽量读懂 1 直接插入排序 重复 p266 图 10 1 的排序过程 阅读复杂度分析 2 Shell 排序 见 p271 图 10 5 的关键字 先画第一趟排序过程 就使用直接选择排序 然后 以趟为单位画出每一趟排序的排序结果 阅读复杂度分析 3 冒泡排序 见 p273 图 10 6 对初始关键字 先画第一趟排序过程 然后 以趟为单位画 出每一趟排序的排序结果 阅读复杂度分析 4 快速排序 见 p275 图 10 7 先画第一趟排序过程 然后 以趟为单位画出每一趟排序 的排序结果 阅读复杂度分析 5 直接选择排序 利用上题的关键字 先画第一趟排序过程 然后 以趟为单位画出每一 趟排序的排序结果 阅读复杂度分析 直接插入法的核心操作是寻找插入位置 而直 接选择法的核心操作是寻找无序中最小的一个 6 堆排序 对 p280 末的关键字序列 重复 p281 图 10 12 的建堆过程 重复图 10 11 的过 程 输出堆顶元素 即最小元素以后 将剩余部分整理成堆的过程 阅读时间复杂度分 析 注意结论 堆排序的效率是比较高的 但是首先有一个建堆的过程 所以在数据量 很大的时候使用效果才好 7 归并排序 重复 p283 图 10 13 的排序过程 每一次都使用二路 阅读时间复杂度分析 8 基数排序 桶排序 对关键字序列 710 342 014 686 006 841 429 134 068 264 使用低关键字优先的方法进行排序 画出排序的逻辑过程 暂时不考虑存储 提 示 建立 0 到 9 十个桶 10 个桶 数的进制数 经过 3 次分配与收集 3 次 关键字 序列中的最大位数 则完成整个 排序过程 9 记忆 p289 10 7 节的表格 注意以下结论 1 理论上已经证明 O n log n 是排序算法的 最底线 不要花时间去发明时间复杂度更低的算法 只能在已知道数据的某些特性的情 况下 做一些的改进 但产生数量级上差别不太可能 2 快速排序在数据已经基本有 序的情况下 退化为冒泡排序 O n2 而冒泡排序加上一定检测机制后可做到 O n 所 以排序算法的选择要根据数据的特征来做 若无法提前得知数据特点 则按平均情况选 择 10 了解外部排序的概念 当数据量很大 不能完全在内存中完成的时候 需要和外存 交换数据 比如每个段内部排序 再归并 而归并会使用到败者树 置换 选择过程 最 佳归并树等等技术 将来如果工作遇到很大量的数据要排序的时候 碰到这几个名词的 时候 记得回来阅读这里就可以了 如果暂时不用 是没有必要阅读的 除非你感兴趣 不要偏执 老师我本人就没有仔细阅读过 可见同学们现在是在打基础 但是 如果能学来致用是最好的了 关于软件技术的学习 一 数据结构是软件技术中基础的基础 希望大家考试以后继续多学习 更不要把教材扔了 你做过笔记的书扔掉是非常可惜的 因为你自己的笔记会帮助你将来迅速想起过去学过的内 容 如果你的教材上密密麻麻地写满了阅读中的标志 疑问 心得 那真是一本不可多得的 17 好参考书 二 严老师的教材是中国 数据结构 教材里写的最严谨的 也是最难的教材 实现的效率 相对其他教材比较高 缺点是语言非常简练形式化 即 公式化 数学化 的语言比较多 初学的时候难以阅读 但是经过一个学期的学习 大家应该习惯了 当然 如果还有困难的 地方 可以参考比较浅显的教材 而教材中的参考书目 2 更是一本 分三本很厚的卷 算 法大全 作者是 Donald E Knuth 号称算法的宗师 该书是一本更难更全的书 完整阅读 是不太可能了 但可以当很好的工具书 三 徐士良的 常用算法程序集 是一本比较全的算法集 已经完全用 C 语言实现 也是 可以常常查阅的工具书 四 其实谁也不可能平时把教材上的所有算法都记得 所以学的好的标准应该是 认真琢磨 了教材中的算法了吗 想通了吗 读懂了吗 重要的结论而记得了吗 另外就是要选一些 自己喜欢的 你觉得比较实用的算法来上机调试通过 希望假期同学们能做这件事情 曾经 有一个同学花了一个假期留在学校通过上机的方式深入学习数据结构 我想他现在一定已经 很熟练了 五 数据结构中的一大重要概念是抽象数据类型 所以在后来的算法中 大家看到函数参数 不在是学习 C 语言的时候都是基本类型 比如整型 字符型等等 中常常有一抽象到一个 层次的结构作为参数 比如 队列来作为一个函数的参数辅助实现其他算法 在实际工作中 如果不是特别的要求 需要自己设计结构 很多经典结构可以使用别人实现好的 所以 C 中的继承机制可以帮助你很好地使用别人的算法 所以 特别介绍一本书 潘爱民等翻 译的 C primer 这本书里讲了很多泛型程序设计 教你如何使用别人的结构 虽然它 是一本 C 教材 而且翻译过来叫 初步入门 的教材 但是它是一本很难的教材 学完数 据结构以后再看才会觉得轻松 象队列 链表 二叉树等结构在标准的 C 库中已经有很好 的实现 一般不用自己写了 那么为什么要学习数据结构呢 因为只有经历这个过程 你才 懂得去选择使用别人的结构 比如什么时候选用链表 什么时候使用顺序表 捅排序为什么 不使用数组等等 只有深入学习过 你曾经沧海 才能不轻易忘记 而在标准 C 库和其他 公司的库中 我觉得大家要尽量使用标准 这样才有比较好的移植性 在非标准的库中 经过若干年的竞争 微软的 MFC 占了绝对的优势 而 Borland 的 OWL几乎消失了 但它 确实是很优秀的 只是因为 boland 商业运作不如微软成功 Borland C 4 0 错过了进入 32 位程序的最佳时机 当然 MFC 组织得也很好 六 如果你想解决更深入的问题 而不是熟练的程序员而已 算法值得一读 Sartaj Sahni 写的 数据结构算法与应用 C 语言描述 在各大网上书店都被评价为五星级 书的 前一半写了数据结构 后一半写了经典算法 包括模拟退火 贪心算法 货郎担问题等等 建议你在在图书管借来 做一个略读 算法部分的目录如下 第 13 章 贪婪算法 13 1 最优化问题 13 2 算法思想 13 3 应用 13 3 1 货箱装船 13 3 2 0 昔背包问题13 3 3 拓扑排序13 3 4 二分覆盖13 3 5 单源最短路径13 3 6 最小耗费生成树 13 4 参考及推荐读物 第 14 章分而治之算法 14 1 算法思想 14 2 应用 14 2 1 残缺棋盘 14 2 2 归并排序 14 2 3 快速排序 14 2 4 选择 14 2 5 距离最近的点对 14 3 解递归方程 14 4 复杂性的下限 14 4 1 最小最大问题的下限 14 4 2 排序算法的下限 第 15 章动态规划 15 1 算法思想 15 2 应用 15 2 1 0 l 背包问题 15 2 2 图像压缩 15 2 3 矩阵乘法链 15 2 4 最短路径 15 2 5 网络的无交叉子集 15 2 6 元件折叠 15 3 参考及推荐读物 第 16 章回溯 16 1 算法思想 16 2 应用 16 2 1 货箱装船 16 2 2 0 1 背包问题 16 2