自考《数据结构》课后习题答案.pdf

数据结构课后习题答案 1 自考 数据结构 课后习题答案自考 数据结构 课后习题答案 第一章 概论 1 第二章 线性表 4 第三章 栈与队列 25 第四章 习题及答案 38 第五章 多维数组和广义表 习题参考答案 50 第六章 树习题及答案 上 57 第 六 章 树习题及答案 下 67 第七章 图 习题及答案 基础部分 87 第八章 排 序习题及答案 94 第八章 排序 习题参考答案 下 101 第九章 查找 习题及答案 107 第十章 文 件 习题及答案 117 第一章第一章 概论概论 1 1 简述下列概念 简述下列概念 数据 数据元素 数据类型 数据结构 逻辑结构 存储结构 线性结构 非线性结数据 数据元素 数据类型 数据结构 逻辑结构 存储结构 线性结构 非线性结 构 构 数据 指能够被计算机识别 存储和加工处理的信息载体 数据元素 就是数据的基本单位 在某些情况下 数据元素也称为元素 结点 顶点 记录 数据元素有 时可以由若干数据项组成 数据类型 是一个值的集合以及在这些值上定义的一组操作的总称 数据结构 指的是数据之间的相互关系 即数据的组织形式 一般包括三个方面的内容 数据的逻辑结构 存储结构和数据的运算 逻辑结构 指各数据元素之间的逻辑关系 存储结构 就是数据的逻辑结构用计算机语言的实现 线性结构 数据逻辑结构中的一类 它的特征是若结构为非空集 则该结构有且只有一个开始结点和一个 终端结点 并且所有结点都最多只有一个直接前趋和一个直接后继 线性表就是一个典型的线性结构 非线性结构 数据逻辑结构中的另一大类 它的逻辑特征是一个结点可能有多个直接前趋和直接后继 1 2 试举一个数据结构的例子 叙述其逻辑结构 存储结构 运算三个方面的内容 试举一个数据结构的例子 叙述其逻辑结构 存储结构 运算三个方面的内容 例如有一张学生成绩表 记录了一个班的学生各门课的成绩 按学生的姓名为一行记成的表 这个表就是 一个数据结构 每个记录 有姓名 学号 成绩等字段 就是一个结点 对于整个表来说 只有一个开始结点 数据结构课后习题答案 2 它的前面无记录 和一个终端结点 它的后面无记录 其他的结点则各有一个也只有一个直接前趋和直接后 继 它的前面和后面均有且只有一个记录 这几个关系就确定了这个表的逻辑结构 那么我们怎样把这个表中的数据存储到计算机里呢 用高级语言如何表示各结点之间的关系呢 是用一片连续的内存单元来存放这些记录 如用数组表示 还是随机存放各结点数据再用指针进行链接呢 这就是存储结构的问题 我们都是从高级语言的层次来讨论这个问题的 所以各位赶快学 C 语言吧 最后 我们有了这个表 数据结构 肯定要用它 那么就是要对这张表中的记录进行查询 修改 删除等操 作 对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了 1 3 常用的存储表示方法有哪几种常用的存储表示方法有哪几种 常用的存储表示方法有四种 顺序存储方法 它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里 结点间的逻辑关系由存储单 元的邻接关系来体现 由此得到的存储表示称为顺序存储结构 链接存储方法 它不要求逻辑上相邻的结点在物理位置上亦相邻 结点间的逻辑关系是由附加的指针字段 表示的 由此得到的存储表示称为链式存储结构 索引存储方法 除建立存储结点信息外 还建立附加的索引表来标识结点的地址 散列存储方法 就是根据结点的关键字直接计算出该结点的存储地址 1 4 设三个函数设三个函数 f g h 分别为分别为 f n 100n 3 n 2 1000 g n 25n 3 5000n 2 h n n 1 5 5000nlgn 请判断下列关系是否成立 请判断下列关系是否成立 1 f n O g n 2 g n O f n 3 h n O n 1 5 4 h n O nlgn 1 成立 这里我们复习一下渐近时间复杂度的表示法 T n O f n 这里的 O 是数学符号 它的严格 定义是 若 T n 和 f n 是定义在正整数集合上的两个函数 则 T n O f n 表示存在正的常数 C 和 n0 使得当 n n0 时都满足 0 T n C f n 用容易理解的话说就是这两个函数当整型自变量 n 趋向于无穷大 时 两者的比值是一个不等于 0 的常数 这么一来 就好计算了吧 第 1 题中两个函数的最高次项都是 n 3 因此当 n 时 两个函数的比值是一个常数 所以这个关系式是成立的 2 成立 3 成立 4 不成立 1 5 设有两个算法在同一机器上运行 其执行时间分别为设有两个算法在同一机器上运行 其执行时间分别为 100n 2 和和 2 n 要使前者快于后者 要使前者快于后者 n 至少要至少要 多大多大 15 最简单最笨的办法就是拿自然数去代呗 假定 n 取为 10 则前者的值是 10000 后者的值是 1024 小于前者 那我们就加个 5 用 15 代入得前者为 22500 后者为 32768 已经比前者大但相差不多 那我 数据结构课后习题答案 3 们再减个 1 用 14 代入得 前者为 19600 后者为 16384 又比前者小了 所以结果得出来就是 n 至少要是 15 1 6 设设 n 为正整数 利用大为正整数 利用大 O 记号 将下列程序段的执记号 将下列程序段的执行时间表示为行时间表示为 n 的函数 的函数 1 T n n 1 T n O n 这个函数是按线性阶递增的 2 T n n T n O n 这也是线性阶递增的 3 T n n 2 T n O n 虽然时间函数是 n 2 但其数量级仍是按线性阶递增的 4 T n n1 2 T n O n1 2 最坏的情况是 y 0 那么循环的次数是 n1 2 次 这是一个按平方根阶递增 的函数 5 T n O 1 这个程序看起来有点吓人 总共循环运行了 1000 次 但是我们看到 n 没有 没 这段程序的运行是和 n 无关的 就算它再循环一万年 我们也不管他 只是一个常数阶的函数 1 7 算法的时间复杂度仅与问题的规模相关吗算法的时间复杂度仅与问题的规模相关吗 No 事实上 算法的时间复杂度不仅与问题的规模相关 还与输入实例中的元素取值等相关 但在最坏的情 况下 其时间复杂度就是只与求解问题的规模相关的 我们在讨论时间复杂度时 一般就是以最坏情况下的 时间复杂度为准的 1 8 按增长率由小至大的顺序排列下列各函数 按增长率由小至大的顺序排列下列各函数 2 100 2 3 n 3 2 n n n n 2 n lgn n lgn n 3 2 n 分析如下 2 100 是常数阶 2 3 n 和 3 2 n 是指数阶 其中前者是随 n 的增大而减小的 n n 是指数方阶 n 是方根阶 n 就是 n n 1 n 2 就相当于 n 次方阶 2 n 是指数阶 lgn 是对数阶 n lgn 是对数方阶 n 3 2 是 3 2 次方阶 根据以上分析按增长率由小至大的顺序可排列如下 2 3 n 2 100 lgn n n 3 2 n lgn 3 2 n 2 n n 10 if x 100 x x 10 y else x A O 1 B O x C O y D O n 第二章第二章 线性表线性表 一 基础知识题 2 1 试描述头指针 头结点 开始结点的区别 并说明头指针和头结点的作用 2 1 答 开始结点是指链表中的第一个结点 也就是没有直接前趋的那个结点 链表的头指针是一指向链表开始结点的指针 没有头结点时 单链表由头指针唯一确定 因此单链表可以用 头指针的名字来命名 数据结构课后习题答案 5 头结点是我们人为地在链表的开始结点之前附加的一个结点 有了头结点之后 头指针指向头结点 不论链 表否为空 头指针总是非空 而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作 一致 都是在某一结点之后 2 2 何时选用顺序表 何时选用链表作为线性表的存储结构为宜 2 2 答 在实际应用中 应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构 通常有以下几方 面的考虑 1 基于空间的考虑 当要求存储的线性表长度变化不大 易于事先确定其大小时 为了节约存储空间 宜采 用顺序表 反之 当线性表长度变化大 难以估计其存储规模时 采用动态链表作为存储结构为好 2 基于时间的考虑 若线性表的操作主要是进行查找 很少做插入和删除操作时 采用顺序表做存储结构为 宜 反之 若需要对线性表进行频繁地插入或删除等的操作时 宜采用链表做存储结构 并且 若链表的插入和删除主 要发生在表的首尾两端 则采用尾指针表示的单循环链表为宜 2 3 在顺序表中插入和删除一个结点需平均移动多少个结点 具体的移动次数取决于哪两个因素 2 3 答 在等概率情况下 顺序表中插入一个结点需平均移动 n 2 个结点 删除一个结点需平均移动 n 1 2 个结点 具体的移动次数取决于顺序表的长度 n 以及需插入或删除的位置 i i 越接近 n 则所需移动的结点数 越少 2 4 为什么在单循环链表中设置尾指针比设置头指针更好 2 4 答 尾指针是指向终端结点的指针 用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方 便 设一带头结点的单循环链表 其尾指针为 rear 则开始结点和终端结点的位置分别是 rear next nex t 和 rear 查找时间都是 O 1 若用头指针来表示该链表 则查找终端结点的时间为 O n 2 5 在单链表 双链表和单循环链表中 若仅知道指针 p 指向某结点 不知道头指针 能否将结点 p 从相应的 链表中删去 若可以 其时间复杂度各为多少 2 5 答 我们分别讨论三种链表的情况 1 数据结构课后习题答案 6 单链表 当我们知道指针 p 指向某结点时 能够根据该指针找到其直接后继 但是由于不知道其头指针 所 以无法访问到 p 指针指向的结点的直接前趋 因此无法删去该结点 2 双链表 由于这样的链表提供双向链接 因此根据已知结点可以查找到其直接前趋和直接后继 从而可以删 除该结点 其时间复杂度为 O 1 3 单循环链表 根据已知结点位置 我们可以直接得到其后相邻的结点位置 直接后继 又因为是循环链表 所以我们可以通过查找 得到 p 结点的直接前趋 因此可以删去 p 所指结点 其时间复杂度应为 O n 2 6 下述算法的功能是什么 LinkList Demo LinkList L L 是无头结点单链表 ListNode Q P if LL L next L while P next P P next P next Q Q next NULL return L Demo 2 6 答 该算法的功能是 将开始结点摘下链接到终端结点之后成为新的终端结点 而原来的第二个结点成为新 的开始结点 返回新链表的头指针 二 算法设计题 2 7 设线性表的 n 个结点定义为 a0 a1 an 1 重写顺序表上实现的插入和删除算法 InsertList 和 DeleteList 答 开始结点是指链表中的第一个结点 也就是没有直接前趋的那个结点 链表的头指针是一指向链表开始结点的指针 没有头结点时 单链表由头指针唯一确定 因此单链表可以用 头指针的名字来命名 数据结构课后习题答案 7 头结点是我们人为地在链表的开始结点之前附加的一个结点 有了头结点之后 头指针指向头结点 不论链 表否为空 头指针总是非空 而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作 一致 都是在某一结点之后 2 8 试分别用顺序表和单链表作为存储结构 实现将线性表 a0 a1 an 1 就地逆置的操作 所谓 就地 指辅助 空间应为 O 1 解 按题意 为将线性表逆置 但辅助空间不能随表的规模增大 我们分别讨论顺序表和单链表的情况 1 顺序表 要将该表逆置 可以将表中的开始结点与终端结点互换 第二个结点与倒数第二个结点互换 如此反复 就 可将整个表逆置了 算法如下 表结构定义同上 void ReverseList Seqlist L Datatype t file for i 0 i length 2 i t L data file L data L length 1 i t 2 链表 也是可以用交换数据的方式来达到逆置的目的 但是由于是单链表 数据的存取不是随机的 因此算法效率 太低 我们可以利用指针的指向转换来达到表逆置的目的 算法是这样的 结构定义略 LinkList ReverseList LinkList head 数据结构课后习题答案 8 将 head 所指的单链表逆置 ListNode p q 设置两个临时指针变量 if head next q p next p next NULL file q q next p next head next head next p return head return head file for i 0 i length s ListNode malloc sizeof ListNode s data x s next p next p next s return L 2 11 写一算法在单链表上实现线性表的 ListLength L 运算 解 求单链表长只能用遍历的方法了 从头数到尾 总能数出来吧 算法如下 int ListLength LinkList L int len 0 ListNode p p L file len 数据结构课后习题答案 10 return len 2 12 已知 L1 和 L2 分别指向两个单链表的头结点 且已知其长度分别为 m 和 n 试写一算法将这两个链表连接 在一起 请分析你的算法的时间复杂度 解 算法如下 LinkList Link LinkList L1 LinkList L2 file p L1 q L2 while p next p p next file file 本算法的主要操作时间花费在查找 L1 的终端结点上 与 L2 的长度无关 所以本算的法时间复杂度为 m 1 O m 2 13 设 A 和 B 是两个单链表 其表中元素递增有序 试写一算法将 A 和 B 归并成一个按元素值递减有序的单链表 C 并要求辅助空间为 O 1 请分析算法的时间复杂度 解 根据已知条件 A 和 B 是两个递增有序表 所以我们可以以 A 表为基础 按照插入单个元素的办法把 B 表的 元素插入 A 表中 完成后 将表逆置就得到了一个按元素值递减有序的单链表 C 了 算法如下 LinkList MergeSort LinkList A LinkList B 数据结构课后习题答案 11 归并两个递增有序表为一个递减有序表 ListNode pa pb qa qb pa A pb B qa A next qb B next while qa qb qb next 指向 B 中下一元素 pa next pb pb next qa pa pb else if qb data pa data qa qa next 保存 A 的后一元素位置 pb qb qb qb next 保存 B 的后一元素位置 pa next pb file 数据结构课后习题答案 12 else 如果 B 中元素总是更大 指针移向下一个 A 元素 pa qa qa qa next if qb 如果 A 表已到终端而 B 表还有结点未插入 将 B 表接到 A 表后面 pa next qb LinkList C ReverseList A 调用前面 2 8 题所设计的逆置函数 return C file file struct node next 结点的指针域 数据结构课后习题答案 13 ListNode typedef ListNode LinkList 以下是源文件 在 VC 中运行通过 include include include ListStruct h include LinkList CreatList void file LinkList head LinkList malloc sizeof ListNode file r head 尾指针亦指向头结点 while ch getchar n s ListNode malloc sizeof ListNode s data ch r next s r s r next NULL return head void OutList LinkList L ListNode p p L while p next 数据结构课后习题答案 14 cout next data next cout next q p next p next NULL file q q next p next head next head next p return head return head file pa A pb B qa A next qb B next while qa qb qb next 指向 B 中下一元素 pa next pb pb next qa pa pb else if qb data pa data qa qa next 保存 A 的后一元素位置 pb qb qb qb next 保存 B 的后一元素位置 pa next pb file else 如果 B 中元素总是更大 指针移向下一个 A 元素 pa qa qa qa next if qb 如果 A 表已到终端而 B 表还有结点未插入 将 B 表接到 A 表后面 pa next qb LinkList C ReverseList A 调用前面 2 8 题所设计的逆置函数 return C file A CreatList 数据结构课后习题答案 16 OutList A B CreatList OutList B C MergeSort A B OutList C 以下是一位学友鲁周航提供的算法 我的算法思路为 当 A B 都不空时 各取 A B 表中的第一个结点比较 哪个值小 就把它用头插法插入 C 表 利用原来的头结点 始终是取第一个结点比较 继续取值比较 当 A 表为空 或 B 表为空 则把剩余 结点用头插法插入 C 表 void LinkList Nodetype A Nodetype B Nodetype C 假设 A 和 B 已建立 C 表的头结点已初始化 Nodetype p q p A Next q B Next while p A 指向 A 表的下一个结点 p Next C Next 把 P 的结点用头插法 插入 C 表 C Next p p A Next P 指向 A 表的第一个结点 继续比较 else B Next q Next 算理同上面 q Next C Next C Next q q B Next if p 如 A 表还有结点 则把剩余结点 用头插法插入 C 表 while p A Next p Next p Next C Next C Next p p A Next 数据结构课后习题答案 17 else if q 如 B 表还有结点 则把剩余结点 用头插法插入 B 表 while q B Next q Next q Next C Next C Next q q B Next free A 释放原头结点空间 free B 你的算法要排表两次 第一次为插入 第二次为逆序 2 14 已知单链表 L 是一个递增有序表 试写一高效算法 删除表中值大于 min 且小于 max 的结点 若表中有这样的结点 同时释放被删结点的空间 这里 min 和 max 是两个给定的参数 请分析你的算法的时间复杂度 解 要解这样的问题 我们首先想到的是拿链表中的元素一个个地与 max 和 min 比较 然后删除这个结点 其 实因为已知其是有序链表 所以我们只要找到大于 min 的结点的直接前趋结点 再找到小于 max 的结点 然后一并把中间的全部摘掉就可以了 算法如下 void DeleteList LinkList L DataType min DataType max ListNode p q r p L next while p while p free r 释放这个结点空间 数据结构课后习题答案 18 q next p file if L Next NULL printf 空表 n exit 0 p L while p Next NULL file q 指向被删结点 p Next q Next 从表中摘下被删结点 free q 释放空间 else 否则不在范围中 if p Next Data max 如值已经超出范围 则跳出循环 结束删除 break else p p Next 当下一个值小于 min 时 继续查找 学友 X F 的看法及算法 两个 while 循环并未带来效率的提升 实际上完全可以使用一个 while 循环来代替 而鲁周航的算法里 跳 出循环的条件 if p Next Data max 可不必放在循环体的内部 这样就完全可以不使用 break 语句 Linklist Delete LinkList L DataType min DataType max ListNode p q p L q L next while q free q q p next else 数据结构课后习题答案 19 p p next q q next return L 2 15 写一算法将单链表中值重复的结点删除 使所得的结果表中各结点值均不相同 解 本题 可以这样考虑 先取开始结点中的值 将它与其后的所有结点值一一比较 发现相同的就删除掉 然后再取 第二结点的值 重复上述过程直到最后一个结点 第二种算法是将单链表按值的大小排序 排好后的结点按相同的删除 以下为周鲁航提供的算法 void DeleteList Nodetype L Nodetype p q s if L Next NULL L Next NULL printf 删除错误 n exit 0 p L Next q p Next while p Next NULL while q s q if q Data p Data s Next q Next free q q s Next else q q Next p p Next 2 16 假设在长度大于 1 的单循环链表中 既无头结点也无头指针 s 为指向链表中某个结点的指针 试编写算法 删除结点 s 的直接前趋结点 数据结构课后习题答案 20 解 已知指向这个结点的指针是 s 那么要删除这个结点的直接前趋结点 就只要找到一个结点 它的指针域是 指向 s 的 把这个结点删除就可以了 算法如下 void DeleteNode ListNode s file p s while p next s q p p p next q next s file file ListNode a A ListNode b B ListNode c C while p if p data a 指向下一结点 a next q 将字母结点链到 A 表中 q next A 形成循环链表 数据结构课后习题答案 21 a a next 指向下一结点 else if p data 0 b next q q next B b b next else file p p next c next q q next C c c next 结束 以下学友 X P 的算法 Void Creative LinkList L LinkList A LinkList B LinkList C ListNode p pa pb pc p L next pa A pb B pc C while p if p data a pa p p p next pa next A next else if p data 0 pb p p p next pb next B next 数据结构课后习题答案 22 else pc next p pc p p p next pc next C next 2 18 设有一个双链表 每个结点中除有 prior data 和 next 三个域外 还有一个访问频度域 freq 在链表被 起用之前 其值均初始化为零 每当在链表进行一次 LocateNode L x 运算时 令元素值为 x 的结点中 freq 域的值加 1 并调整表中结点的次序 使其按访问频度的递减序排列 以便使频繁访问的结点总是靠近表头 试写一符合上述要求的 LocateNode 运算的算法 解 给 freq 域的值加 1 比较容易 就是每次加 1 后需进行排序比较麻烦 我们可以这样考虑 每次访问一 个值为 x 的结点后 从表头开始找 根据结点中的 freq 值 如果找到比它小的结点 就把当前结点摘下 插入到 freq 值比它小的结点前面 就完成排序了 算法如下 void LocateNode LinkList L DataType x ListNode p q p L next file while p if p data x p p next else p freq break while q 数据结构课后习题答案 23 if q freq p freq q q next else p prior next p next file file 2 18 周鲁航 算法思路为 当找到要找的值时 freq 计数 比较当前结点前的所有结点的 freq 因为总是把访问次数多的放在 前面 因此该结点后的所有结点的 freq 值一定小于等于它 就不必比较了 所以只要比较前面的就行了 如果 X 结点的 freq 值大于等于它 就把当前结点摘下后 插入到它前面位置 void LocateNode Nodetype L char x Nodetype p q p L Next while p L if p Data x 如找到了结点的位置 p freq 计数访问的次数 q L Next while q p if p freq q freq 摘下 X 结点 p prior Next p Next 把结点插入 q 所指结点的前面 p Next q p prior q prior q prior p p prior Next p else printf 查无此值 n 学友 X P 的算法 编程思想是设置一个变量 i 作为位置计数器 同时作为函数的返回值 若在链表中查找到对应的元素 则计数器 i 就是其对应的位置 指针 p 为指向已查找到的结点 p1 为 p 前趋指针指向的结点 若未找到 则 直接返回 0 无需进入循环 提高了代码执行的效率 int LocateNode LinkList L DataType x ListNode p p1 int i p L next i 1 while p data x p p next if p 如果 p 不为 null 则说明在链表中找到了对应的结点 数据结构课后习题答案 25 p freq p1 p prior while p1 L p next prior p1 p1 prior next p p prior p1 prior p next p1 p1 prior p 逐渐前移 return i else return 0 若 p 为 null 则说明在链表中未找到对应的结点 此时直接返回 0 第三章第三章 栈与队列栈与队列 一 基础知识题 3 1 设将整数 1 2 3 4 依次进栈 但只要出栈时栈非空 则可将出栈操作按任何次序夹入其中 请回答 下述问题 1 若入 出栈次序为 Push 1 Pop Push 2 Push 3 Pop Pop Push 4 Pop 则出栈的数字序列为何 这里 Push i 表示 i 进栈 Pop 表示出栈 2 能否得到出栈序列 1423 和 1432 并说明为什么不能得到或者如何得到 3 请分析 1 2 3 4 的 24 种排列中 哪些序列是可以通过相应的入出栈操作得到的 答 1 出栈序列为 1324 2 不能得到 1423 序列 因为要得到 14 的出栈序列 则应做 Push 1 Pop Push 2 Push 3 Push 4 Pop 这样 3 在栈顶 2 在栈底 所以不能得到 23 的出栈序列 能得到 1432 的出栈序列 具体操作为 Push 1 Pop Push 2 Push 3 Push 4 Pop Pop Pop 3 在 1 2 3 4 的 24 种排列中 可通过相应入出栈操作得到的序列是 1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 数据结构课后习题答案 26 不能得到的序列是 1423 2413 3124 3142 3412 4123 4132 4213 4231 4312 3 2 链栈中为何不设置头结点 答 链栈不需要在头部附加头结点 因为栈都是在头部进行操作的 如果加了头结点 等于要对头结点之后 的结点进行操作 反而使算法更复杂 所以只要有链表的头指针就可以了 3 3 循环队列的优点是什么 如何判别它的空和满 答 循环队列的优点是 它可以克服顺序队列的 假上溢 现象 能够使存储队列的向量空间得到充分的利用 判别循环队列的 空 或 满 不能以头尾指针是否相等来确定 一般是通过以下几种方法 一是另设一布尔变 量来区别队列的空和满 二是少用一个元素的空间 每次入队前测试入队后头尾指针是否会重合 如果会重 合就认为队列已满 三是设置一计数器记录队列中元素总数 不仅可判别空或满 还可以得到队列中元素的 个数 3 4 设长度为 n 的链队用单循环链表表示 若设头指针 则入队出队操作的时间为何 若只设尾指针呢 答 当只设头指针时 出队的时间为 1 而入队的时间需要 n 因为每次入队均需从头指针开始查找 找到 最后一个元素时方可进行入队操作 若只设尾指针 则出入队时间均为 1 因为是循环链表 尾指针所指的 下一个元素就是头指针所指元素 所以出队时不需要遍历整个队列 3 5 指出下述程序段的功能是什么 1 void Demo1 SeqStack S int i arr 64 n 0 while StackEmpty S arr n Pop S for i 0 i n i Push S arr Demo1 2 SeqStack S1 S2 tmp DataType x 假设栈 tmp 和 S2 已做过初始化 while StackEmpty Push while StackEmpty Push Push 3 void Demo2 SeqStack S int m 设 DataType 为 int 型 SeqStack T int i InitStack while StackEmpty S if i Pop S m Push while StackEmpty Push S i 4 void Demo3 CirQueue Q 设 DataType 为 int 型 int x SeqStack S InitStack while QueueEmpty Q x DeQueue Q Push while StackEmpty EnQueue Q x Demo3 5 CirQueue Q1 Q2 设 DataType 为 int 型 int x i m 0 设 Q1 已有内容 Q2 已初始化过 while QueueEmpty EnQueue m for i 0 iTop 1 int EmptyStack SeqStack S 判栈空 return S Top 1 数据结构课后习题答案 29 int FullStack SeqStack S 判栈满 return S Top StackSize 1 void Push SeqStack S Datatype x 进栈 if FullStack S Error Stack overflow S data S Top x Datatype Pop SeqStack S 出栈 退栈 if EmptyStack S Error Stack underflow return S data S Top 取栈顶元素 略 以下是主程序 include include include stack h include ishuiwen h void main char Str 100 数据结构课后习题答案 30 printf 输入一个字符串 n scanf s Str if IsHuiwen Str printf n 这个字符串是回文 else printf n 这个字符串不是回文 附 肖平来信指出问题 个人认为如题目所言 abba 和 abdba 均是回文 但对于这两种回文需要区别对待 原算法在判断类似 abdba 的回文时 会认为其不是回文而与题意相违背 我的编程思想是 设置一个 float 型的变量 用于存放字符串的长度 再利用取整函数对长度为奇数的 回文进行判别 若将字符串长度附给一整型变量 那么无论该整形变量除任何整数 其结果仍然是一整数 因此必须设一实型变量 判断结束后 若是回文返回 1 不是则返回 0 我的算法如下 已验证通过 int HuiWen char p int i float t SeqStack S InitStack t strlen p for i 0 i t 2 1 i Push if floor t 2 t 2 针对 abdba 类的回文 i while p 0 if Pop else return 0 数据结构课后习题答案 31 return 1 也可以直接用字符指针而不用字符数组来处理 只需对算法稍作修改 算法如下 已验证通过 int HuiWen char p int i float t SeqStack S InitStack t strlen p for i 0 iTop 1 其实只是将栈置空 数据结构课后习题答案 32 因为我们要置空的是栈 S 如果不用指针来做参数传递 那么函数进行的操作不能对原来的栈产生影响 系统将会在内存中开辟另外的单元来对形参进行函数操作 结果等于什么也没有做 所以想要把函数操作的 结果返回给实参的话 就只能用指针来做参数传递了 3 8 利用栈的基本操作 写一个返回 S 中结点个数的算法 int StackSize SeqStack S 并说明 S 为何不作为指针参数 解 算法如下 int StackSize SeqStack S 计算栈中结点个数 int n 0 if EmptyStack n return n 类似于上面的原因 我们要计算栈中元素个数就要弹出元素才能 数 得出来 那如果用指针做参数的话 就会把原来的栈中元素 弹 光 要恢复还得用别的办法给它装回去 而不用指针做参数 则可以避免对原来 的栈中元素进行任何操作 系统会把原来的栈按值传递给形参 函数只对形参进行操作 最后返回元素个数 就可以了 3 9 设计算法判断一个算术表达式的圆括号是否正确配对 提示 对表达式进行扫描 凡遇到 就进栈 遇 就退掉栈顶的 表达式被扫描完毕 栈应为空 解 根据提示 可以设计算法如下 include include stack h int PairBracket char S 检查表达式中括号是否配对 int i 数据结构课后习题答案 33 SeqStack T 定义一个栈 InitStack for i 0 i if S Push 遇 时进栈 if S Pop 遇 时出栈 return StackEmpty 由栈空否返回正确配对与否 3 10 一个双向栈 S 是在同一向量空间内实现的两个栈 它们的栈底分别设在向量空间的两端 试为此双向栈设计初始化 InitStack S 入栈 Push S i x 和出栈 Pop S i 等算法 其中 i 为 0 或 1 用以表示栈号 解 双向栈其实和单向栈原理相同 只是在一个向量空间内 好比是两个头对头的栈放在一起 中间的空间 可以充分利用 双向栈的算法设计如下 双向栈的栈结构类型与以前定义略有不同 define StackSize 100 假定分配了 100 个元素的向量空间 define char Datatype typedef struct Datatype Data StackSize int top0 需设两个指针 int top1 DblStack void InitStack DblStack S 初始化双向栈 S top0 1 S top1 StackSize 这里的 top2 也指出了向量空间 但由于是作为栈底 因此不会出错 3 11 Ackerman 函数定义如下 请写出递归算法 n 1 当 m 0 时 AKM m n AKM m 1 1 当 m 0 n 0 时 AKM m 1 AKM m n 1 当 m 0 n 0 时 解 算法如下 int AKM int m int n if m 0 return n 1 if m0 if m0 3 12 用第二种方法 即少用一上元素空间的方法来区别循环队列的队空和队满 试为其设计置空队 判队空 判队满 出队 入队及取队头元素等六个基本操作的算法 数据结构课后习题答案 34 解 算法设计如下 存为 Queue2 h 文件 void InitQueue CirQueue Q 置空队 Q front Q rear 0 int EmptyQueue CirQueue Q 判队空 return Q front Q rear int FullQueue CirQueue Q 判队满 如果尾指针加 1 后等于头指针 则认为满 return Q rear 1 QueueSize Q front 3 13 假设以带头结点的循环链表表示队列 并且只设一个指针指向队尾元素站点 注意不设头指针 试编写相应的置空队 判队空 入队和出队等算法 解 算法如下 先定义链队结构 typedef struct queuenode Datatype data struct queuenode next QueueNode 以上是结点类型的定义 typedef struct queuenode rear LinkQueue 只设一个指向队尾元素的指针 linkQ h 相应算法 void InitQueue LinkQueue Q 置空队 就是使头结点成为队尾元素 Q rear Q rear next 头结点成为尾结点 Q rear next Q rear 形成循环链表 int EmptyQueue LinkQueue Q 判队空 当头结点的 next 指针指向自己时为空队 return Q rear next next Q rear next void EnQueue LinkQueue Q Datatype x 入队 也就是在尾结点处插入元素 QueueNode p QueueNode malloc sizeof QueueNode 申请新结点 数据结构课后习题答案 35 p data x p next NULL 初始化结点 Q rear next next p 将新结点链入 p next Q rear 形成循环链表 Q rear p 将尾指针移至新结点 Datatype DeQueue LinkQueue Q 出队 把头结点之后的元素摘下 Datatype t QueueNode p if EmptyQueue Q Error Queue underflow p Q rear next next 将要摘下的结点 x p data 保存结点中数据 Q rear next next p next 摘下结点 p free p 释放被删结点 return x 肖平朋友提出看法 仔细研究了原算法 发现存在以下几个问题 1 虽然使用了 Q rear next 来代替头结点的表示方法 但不如直接定义头结点 Q head 来的方便 而且题目也明确要求了使用头结点 在结构定义中只反映出去掉了头指针 没有反映出该链队列是否包含头 结点 2 对于入队算法 是采用头插法将新结点依次链入头结点的后面 这似乎与队列的定义相违背 队列 应该在尾部入队 而不是在头部入队 3 同上 出队操作仍然在头部进行 若顺序运行入队和出队算法 由于均在头部进行 其结果会将该 队列演变成一个栈 我的算法如下 typedef struct QueueNode head 去掉头指针 增加头结点 QueueNode rear LinkQueue 置空队 void InitQueue LinkQueue Q 数据结构课后习题答案 36 Q rear Q head Q head next Q rear 形成循环空队列 尾指针指向空队列内唯一的头结点 判队空 int QueueEmpty LinkQueue Q return Q head next Q rear 入队 void EnQueue LinkQueue Q QueueNode p Queue malloc sizeof QueueNode p data x Q rear next p p next Q head Q rear p 对于空队列 由于 Q rear Q head 因此第一个结点和后续结点的入队操作均一致 出队 DataType DeQueue LinkQueue Q if QueueEmpty Q Error Queue underflow DataType x QueueNode p p Q head next x p data Q head next p next 数据结构课后习题答案 37 if Q rear p Q rear Q head 当最后一个结点也出队后 队列为空 尾指针重新指向头结点 free p return x 3 14 对于循环向量中的循环队列 写出求队列长度的公式 解 公式如下 Queuelen 0 当 EmptyQueue Queuelen rear front 当 rear front Queuelen rear QueueSize front 当 rear Queuelen QueueSize 当 FullQueue 3 15 假设循环队列中只设 rear 和 quelen 来分别指示队尾元素的位置和队中元素的个数 试给出判别此循环队列的队满条件 并写出相应的入队 和出队算法 要求出队时需返回队头元素 解 知道了尾指针和元素个数 当然就能知道队头元素了 算法如下 int FullQueue CirQueue Q 判队满 队中元素个数等于空间大小 return Q quelen QueueSize void EnQueue CirQueue Q Datatype x 入队 if FullQueue Q Error 队已满 无法入队 Q Data Q rear x Q rear Q rear 1 QueueSize 在循环意义上的加 1 Q quelen 数据结构课后习题答案 38 Datatype DeQueue CirQueue Q 出队 if Q quelen 0 Error 队已空 无元素可出队 int tmpfront 设一个临时队头指