数据结构习题答案

数据结构数据结构 作业题参考答案作业题参考答案 第一章第一章 1 简述下列概念 数据 数据元素 数据类型 数据结构 逻辑结构 存储结构 线性结 构 非线性结构 答 数据数据 指能够被计算机识别 存储和加工处理的信息载体 数据元素数据元素 就是数据的基本单位 在某些情况下 数据元素也称为元素 结点 顶点 记录 数据元素有时可以由若干数据项组成 数据类型数据类型 是一个值的集合以及在这些值上定义的一组操作的总称 数据结构数据结构 指的是数据之间的相互关系 即数据的组织形式 一般包括三个方面的内容 数据的逻辑结构 存储结构和数据的运算 逻辑结构逻辑结构 指各数据元素之间的逻辑关系 存储结构存储结构 就是数据的逻辑结构用计算机语言的实现 线性结构线性结构 数据逻辑结构中的一类 它的特征是若结构为非空集 则该结构有且只有一 个开始结点和一个终端结点 并且所有结点都最多只有一个直接前趋和一个直接后继 线 性表就是一个典型的线性结构 非线性结构非线性结构 数据逻辑结构中的另一大类 它的逻辑特征是一个结点可能有多个直接前趋 和直接后继 2 常用的存储表示方法有哪几种 答 常用的存储表示方法有四种 顺序存储方法 它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里 结点间的 逻辑关系由存储单元的邻接关系来体现 由此得到的存储表示称为顺序存储结构 链接存储方法 它不要求逻辑上相邻的结点在物理位置上亦相邻 结点间的逻辑关系是 由附加的指针字段表示的 由此得到的存储表示称为链式存储结构 索引存储方法 除建立存储结点信息外 还建立附加的索引表来标识结点的地址 散列存储方法 就是根据结点的关键字直接计算出该结点的存储地址 3 设有两个算法在同一机器上运行 其执行时间分别为 100n2 和 2n 要使前者快于后者 n 至少要多大 答 15 最简单最笨的办法就是拿自然数去代 假定 n 取为 10 则前者的值是 10000 后者的值 是 1024 小于前者 那我们就加个 5 用 15 代入得前者为 22500 后者为 32768 已经比前 者大但相差不多 那我们再减个 1 用 14 代入得 前者为 19600 后者为 16384 又比前者 小了 所以结果得出来就是 n 至少要是 15 第二章第二章 线性表线性表 1 利用顺序表的操作 实现以下的函数 1 从顺序表 L 中删除具有最小值的元素并由函数返回被删元素的值 空出的位置由最 后一个元素填补 若顺序表为空则显示出错信息并退出运行 Status del min sqlist min p L elem p 为第 1 个元素的位置 min 为最小元素的位置 q L elem L length 1 表尾元素的位置 for p p min p 找最小元素的位置存在 min 中 e min min q 被删除元素位置填补最后一个元素值 L length return OK 2 删除顺序表 L 中从第 i 个元素起的 k 个元素 Status Del Sq Sqlist j k i for i j i p L elem i 1 q L elem L length 1 for p p q p p 1 p L length return OK 3 从顺序表中删除具有给定值 x 的所有元素 Status DelValue sqlist while i L length 循环 寻找具有值 x 的元素并删除它 if L elem i x 删除具有值 x 的元素 后续元素前移 for j i j L length j L elem j L elem j 1 L length 表长减 1 else i return OK 4 从顺序表中删除所有其值重复的元素 使表中所有元素的值均不相同 Status DelDouble sqlist int i 0 j k ElemType temp while i L length 循环检测 j i 1 temp L elem i while j L length 对于每一个 i 重复检测一遍后续元素 if temp L elem j 如果相等 后续元素前移 for k j 1 k L length k L elem k 1 L elem k L length 表最后元素位置减 1 else j i 检测完 data i 检测下一个 2 描述头指针 头结点 开始结点的区别 并说明头指针和头结点的作用 答 开始结点开始结点是指链表中的第一个结点 也就是没有直接前趋的那个结点 链表的头指针头指针是一指向链表开始结点的指针 没有头结点时 单链表由头指针唯一确 定 因此单链表可以用头指针的名字来命名 头结点头结点是我们人为地在链表的开始结点之前附加的一个结点 有了头结点之后 头指针指向头结点 不论链表否为空 头指针总是非空 而且头指 针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致 都是在某一结点 之后 3 何时选用顺序表 何时选用链表作为线性表的存储结构为宜 答 在实际应用中 应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储 结构 通常有以下几方面的考虑 1 基于空间的考虑基于空间的考虑 当要求存储的线性表长度变化不大 易于事先确定其大小时 为 了节约存储空间 宜采用顺序表 反之 当线性表长度变化大 难以估计其存储规模时 采用动态链表作为存储结构为好 2 基于时间的考虑基于时间的考虑 若线性表的操作主要是进行查找 很少做插入和删除操作时 采 用顺序表做存储结构为宜 反之 若需要对线性表进行频繁地插入或删除等的操作时 宜 采用链表做存储结构 并且 若链表的插入和删除主要发生在表的首尾两端 则采用尾指 针表示的单循环链表为宜 4 试分别用顺序表和单链表作为存储结构 实现将线性表 a0 a1 an 1 就地逆置的操作 所谓 就地 指辅助空间应为 O 1 解 1 顺序表实现 要将该表逆置 可以将表中的开始结点与终端结点互换 第二个结点与倒数第二个 结点互换 如此反复 就可将整个表逆置了 算法如下 define ListSize 100 假定表空间大小为 100 typedef int Elemtype typedef struct Elemtype elem ListSize 向量 elem 用于存放表结点 int length 当前表的长度 Sqlist 以上为定义表结构 以下为要求算法 void ReverseList Sqlist 设置临时空间用于存放 elem int i j for i 0 j L length 1 inext q p next p next NULL 将开始结点变成终端结点 while q 每次循环后将后一个结点变成开始结点 p q q q next p next head next head next p return head return head 如是空表或单结点表 直接返回 head 5 写一算法在单链表上实现线性表的求长度 ListLength L 运算 解 用遍历单链表的方法从头数到尾 算法如下 int ListLength LinkList L int len 0 Lnode p p L 设该表没有头结点 while p len p p next return len 第三章第三章 栈和队列栈和队列 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 不能得到 因为出栈 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 共 14 种 其余 10 种序列不能实现 1423 2413 3142 3124 3412 4312 4132 4123 4213 4231 2 链栈中为何不设头指针 答 答 链栈不需要在头部附加头结点 因为栈都是在头部进行操作的 如果加了头结点 等于要对头结点之后的结点进行操作 反而使算法更复杂 所以只要有链表的头指针就可 以了 3 循环队列的优点是什么 如何判断它的空和满 答 答 循环队列的优点是 它可以克服顺序队列的 假上溢 现象 能够使存储队列的向量空间 得到充分的利用 判别循环队列的 空 或 满 不能以头尾指针是否相等来确定 一般是通过以 下几种方法 一是另设一布尔变量来区别队列的空和满 二是少用一个元素的空间 每次入队 前测试入队后头尾指针是否会重合 如果会重合就认为队列已满 三是设置一计数器记录队列 中元素总数 不仅可判别空或满 还可以得到队列中元素的个数 4 设长度为 n 的链队列用单循环链表表示 若只设头指针 则怎样进行入队和出队操作 若只设尾指针呢 答 答 当只设头指针时 出队的时间为 1 而入队的时间需要 n 因为每次入队均需从头指针 开始查找 找到最后一个元素时方可进行入队操作 若只设尾指针 则出入队时间均为 1 因 为是循环链表 尾指针所指的下一个元素就是头指针所指元素 所以出队时不需要遍历整个队 列 5 利用栈的基本操作 写一个返回栈 s 中结点个数的算法 int stacksize seqstack s 并说明 s 为何不用作为指针参数 解 算法如下 int StackSize SeqStack S 计算栈中结点个数 int n 0 if EmptyStack n return n 我们要计算栈中元素个数就要弹出元素才能 数 得出来 那如果用指针做参数的话 就会把原来的栈中元素 弹 光 要恢复还得用别的办法给它装回去 而不用指针做参数 则可以避免对原来的栈中元素进行任何操作 系统会把原来的栈按值传递给形参 函数只 对形参进行操作 最后返回元素个数就可以了 6 利用栈的基本操作 写一个将栈中所有结点均删除算法 并说明 S 为何要作为指针参 数 解 算法如下 void ClearStack SeqStack S 删除栈中所有结点 S Top 0 其实只是将栈置空 因为我们要置空的是栈 S 如果不用指针来做参数传递 那么函数进行的操作不能对 原来的栈产生影响 系统将会在内存中开辟另外的单元来对形参进行函数操作 结果等于 什么也没有做 所以想要把函数操作的结果返回给实参的话 就只能用指针来做参数传递 了 7 用第二种方法 即少用一个元素空间的方法来区别循环队列的队空和队满 试设计置空 队 判队空 判队满 出队 入队及取队头元素等六个基本操作 解 算法设计如下 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 DataType DeQueue CirQueue Q 出队 DataType temp if EmptyQueue Q Error 队已空 无元素可以出队 temp Q data Q front 保存队首元素值 Q front Q front 1 QueueSize 循环意义上的加 1 return temp void EnQueue CirQueue Q DataType x 入队 if FullQueue Q Error 队已满 不可以入队 Q data Q rear x Q rear Q rear 1 QueueSize rear 指向下一个空元素位置 DataType FrontQueue CirQueue Q 取队头元素 if EmptyQueue Q Error 队空 无元素可取 return Q data Q front 将以上算法存为 Queue2 h 文件 循环队列的定义 存入 StructQ h 文件中 define QueueSize 10 元素的最大空间为 10 typedef char DataType 设元素类型为 char 型 int front int rear DataType data QueueSize CirQueue 以下是验证算法的主程序 include include include StructQ h include Queue2 h 出错控制程序 void Error char message fprintf stderr Error s n message exit 1 主函数 void main int i CirQueue Q 定义一个循环队列 InitQueue 初始