第1、2章讨论题答案

第一章第一章 绪论绪论 1 研究和讨论数据结构的目的 研究和讨论数据结构的目的 参考答案 研究和讨论数据结构的目的是为了让计算机能够对数据进行更好 的处理 从软件设计和程序设计角度看 应包括两个方面 1 概念上一致 2 更高的处理效率 2 数据结构与程序设计的关系数据结构与程序设计的关系 参考答案 数据结构就是为程序设计而产生 没有程序设计 数据结构就无 用武之地 设计出的各种结构将会变成纯粹的脑力游戏而已 无实际价值 而 没有数据结构 程序设计的效用将大打折扣 而且面对复杂问题时根本不现实 可以这样说 没有程序设计 就没有数据结构 反之亦然 3 数据类型和抽象数据类型是如何定义的 二者有何相同和不同之处 抽象数数据类型和抽象数据类型是如何定义的 二者有何相同和不同之处 抽象数 据类型的主要特点是什么 使用抽象数据类型的主要好处是什么 据类型的主要特点是什么 使用抽象数据类型的主要好处是什么 参考答案 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 如 C 语言中的整型 实型 字符型等 抽象数据类型是指一个数学模型以及定 义在该模型上的一组操作 抽象数据类型和数据类型实质上是一个概念 此外 抽象数据类型的范围更广 它已不再局限于机器已定义和实现的数据类型 还包括用户在设计软件系统时 自行定义的数据类型 抽象数据类型可理解为数据类型的进一步抽象 即把数 据类型和数据类型上的运算捆在一起 进行封装 抽象数据类型的主要特点是数据抽象和数据封装 它的出现使程序设计不再是 艺术 而是向 科学 迈进了一步 4 数据的逻辑结构 数据的存储结构及数据的运算之间存在着怎样的关系 数据的逻辑结构 数据的存储结构及数据的运算之间存在着怎样的关系 参考答案 数据的逻辑结构反映数据元素之间的逻辑关系 即数据元素之间 的关联方式或 邻接关系 数据的存储结构是数据结构在计算机中的表示 包括数据元素的表示及其关系的表示 数据的运算是对数据定义的一组操作 运算是定义在逻辑结构上的 和存储结构无关 而运算的实现则是依赖于存储 结构 5 当你为解决某一问题而选择数据结构时 应从哪些方面考虑 在编制管理通当你为解决某一问题而选择数据结构时 应从哪些方面考虑 在编制管理通 讯录的程序时讯录的程序时 什么样的数据结构合适什么样的数据结构合适 为什么为什么 参考答案 通常从两方面考虑 第一是算法所需的存储空间量 第二是算法 所需的时间 对算法所需的时间又涉及以下三点 1 程序运行时所需输入的 数据总量 2 计算机执行每条指令所需的时间 3 程序中指令重复执行的 次数 仅供参考 可以从两方面进行讨论 针对通讯录较少变动 如城市私人电话号 码 主要用于查询 以顺序存储较方便 既能顺序查找也可随机查找 而如果 通讯录经常有增删操作 用链式存储结构较为合适 将每个人的情况作为一个 元素 即一个结点存放一个人 设姓名作关键字 链表安排成有序表 这样可 提高查询速度 第二章第二章 线性表线性表 1 线性表有两种存储结构 一是顺序表 二是链表 试问 线性表有两种存储结构 一是顺序表 二是链表 试问 1 如果有 如果有 n 个线性表同时并存 并且在处理过程中各表的长度会动态变化 个线性表同时并存 并且在处理过程中各表的长度会动态变化 线性表的总数也会自动地改变 在此情况下 应选用哪种存储结构 线性表的总数也会自动地改变 在此情况下 应选用哪种存储结构 为什么 为什么 2 若线性表的总数基本稳定 且很少进行插入和删除 但要求以最快的速度 若线性表的总数基本稳定 且很少进行插入和删除 但要求以最快的速度 存取线性表中的元素 那么应采用哪种存储结构 为什么 存取线性表中的元素 那么应采用哪种存储结构 为什么 参考答案 1 选用链表 由于多个线性表在处理过程中长度都在动态变化 主要操作是插入 删除操作 顺序表插入或删除元素时不方便 而用链表的存 储结构更加灵活 2 选用顺序表 由于线性表很少进行插入和删除 主要用于存取 用顺序表 能更好的实现这样的要求 2 试比较顺序存储结构和链式存储结构的优缺点 在什么情况下用顺序表比链试比较顺序存储结构和链式存储结构的优缺点 在什么情况下用顺序表比链 表好 表好 参考答案 顺序存储时 相邻数据元素的存放地址也相邻 逻辑与物理统 一 要求内存中可用存储单元的地址必须是连续的 优点 存储密度大 1 存储空间利用率高 缺点 插入或删除元素时不 方便 链式存储时 相邻数据元素可随意存放 但所占存储空间分两部分 一部 分存放结点值 另一部分存放表示结点间关系的指针 优点 插入或删除元素时很方便 使用灵活 缺点 存储密度小 next p 为工作指针 指向待处理的结点 假定链表非空 pre L pre 指向最小值结点的前驱 q p q 指向最小值结点 初始假定第一元素结点是最小值结点 while p next null if p next datadata pre p q p next 查最小值结点 p p next 指针后移 pre next q next 从链表上删除最小值结点 free q 释放最小值结点空间 5 约瑟夫问题 约瑟夫问题 问题描述如下 问题描述如下 m 个人围成一圈 每个人手里有一个令牌 令牌值为一个正整个人围成一圈 每个人手里有一个令牌 令牌值为一个正整 数 从第一个人开始报数 数到数 从第一个人开始报数 数到 n 的人出圈 同时将其令牌的值作为新的的人出圈 同时将其令牌的值作为新的 n 值 值 再由下一个人开始报数 数到再由下一个人开始报数 数到 n 的人出圈 的人出圈 依次输出出圈的人的编号 依次输出出圈的人的编号 参考答案 思路一 设一个包括 m 个元素的数组 初始时将数组的每个元素存放所持令牌 值 从第一个元素开始 依次遍历数组 并通过计数器计数 如果元素所存令 牌值已被清 0 则不计数 当计数器的值为 n 时 输出该元素的下标 它即是 应该出圈人的编号 并将该元素所存令牌值取出 设为新的 n 同时将计数器 值归 0 然后将该元素所存令牌值清 0 使以后计数时不再起作用 相当于该人 已出圈 再从下一个元素开始 依据上面的方法 如此继续 直到输出 m 个值 以后结束 参考程序 void Joseph int player int m int n int i 0 Counter 0 del 0 i 记录序号下标 Counter 表示计数器 del 表示当 前已出圈人数 while del m delnext p 为工作指针 指向第一个游戏者结点 pre L pre 指向第一个游戏者结点的前驱 while pre p if Counternext Counter else 如果计数器达到 n 指针 p 所指即为出圈人结点 pre 则指向出圈人结点 的前驱 pre next p next pre next 指向 p 的后继 以便删除出圈人结点 printf 出圈人序列号为 d n p index 输出出圈人序号 n p token 提取出圈人所持令牌值作为新的 n free p p pre next Counter 1 printf 出圈人序列号为 d n p index 输出最后一个出圈人序号 free p 删除最后一个结点 L NULL 算法 void Joseph Node head int n int m m 总人数 n 出列者报的数 int i j Node p q p head