习题和实验指导解答2

《习题和实验指导解答2》由会员分享，可在线阅读，更多相关《习题和实验指导解答2（19页珍藏版）》请在金锄头文库上搜索。

1、 1 第第 2 2 章章 习题 思考题和上机题解答习题 思考题和上机题解答 2 12 1 习题习题2 2 解答解答 1 算法或程序阅读题 1 阅读下列程序 将其中函数 算法 Del k 其功能是从线性表的第 i 个元素起 删除连续的 k 个元素 改为一个正确而高效的函数 算法 include const int MaxSize 100 void Del k int a int return else int count j for count 0 counti 1 j a j 1 a j length length 1 void main int a 9 1 2 3 4 5 6 7 8 9 i

2、nt length 9 int i 2 int k 3 Del k a length i k for int j 0 j length j cout a j 解答 只要将其中 int count j for count 0 counti 1 j a j 1 a j length length 1 改为 for int j i k j length j a j k a j length length k 2 在用带头结点的单链表作存储结构表示集合 A 和 B 的情况下 下列函数为 LinkList 类的友函数 实现求 A B 即保留 A 中不在 B 内的元素 结果保留在单链表 A 中 templ

3、ate void Difference LinkList while q NULL pre A first p pre next 2 while p NULL p p next if p NULL delete p p pre next q q next 试用集合 A 为 1 3 5 6 B 为 3 6 执行该算法 给出结果 并将该算法改写成自然语 言描写的伪代码形式 解答 用集合 A 为 1 3 5 6 B 为 3 6 执行该算法的结果是 1 5 该算法的自然语言 描写的伪代码形式为 2 2 论述题论述题 1 试论顺序表 顺序存储 顺序存取以及随机存取之间的区别 解答 顺序表是指将线性表逻辑

4、相邻元素映射在物理位置上也相邻的内存中的一 种存储结构的统称 通常用数组来具体实现 顺序存储指的顺序表实现中的存储方式 顺序存储指的是访问表中某个元素必须先顺次由前往后扫描完其前面的所有元素 或 顺次由后往前扫描完其后面的所有元素之后 才能访问该元素的一种访问方法 随机 存取指的是访问某个数据元素时直接定位访问而不需扫描其它元素的一种访问方法 2 试给出单链表的头指针 头结点 第一个结点的区别 并说明头指针和头结点的作用 解答 头指针指的是链表访问的入口地址 头结点往往是指在单链表中实际存放数据元 素的第一个结点之前虚设的一个结点 第一个结点又称开始结点或始结点 是存放第一个数据 元素的结点

5、其最大区别是 头指针是指针 而头结点和第一个结点都指的是结点 头指针的 作用是帮助标识单链表的入口 对单链表结点的访问都从头指针开始 头结点的作用是使得头 指针始终不为空 减少某些操作进行之前判断头指针是否为空的判断 使得在带头结点的单链 表 不管是空表还是非空表 不同位置上 插入 删除等操作达到统一 从而代码得以简化 3 有哪些链表可由一个尾指针唯一确定 即从尾指针出发能访问表上任何一个结点 解答 循环单链表 双链表和循环双链表都可通过设置尾指针唯一确定对应的链 表 且能从尾指针出发访问表上任何一个结点 3 3 填空题填空题 1 等概率情况下 在顺序表中插入和删除一个元素平均都分别需约移动

6、个元素 在 处插入元素不需要移动元素 而在处插入元素需要移动全部元素 解答 表中一半 最后一个位置后 第一个位置 两集合单链表表示下差算法 Difference 伪代码 1 将 q 指针初始化指向 B 的第一个结点 2 只要 q 不为空 执行 2 1 指针 pre 和 p 分别初始化指向 A 的头结点和第一个结点 2 2 只要 p NULL 且 p data q data pre 和 p 分别向前移动扫描一步 2 3 若 p NULL 且 p data q data 则将 p 结点从 A 中删除 2 4 q 指针向前移动扫描一步 3 2 顺序表的第一个元素的存储地址是 50 每个元素的长度为

7、5 个单位 则第 20 个元素 的存储地址是 解答 50 20 1 5 145 3 设单链表中指针 p 指向结点 A 若要删除 A 的后继结点的后继节点 则需执行的操作 序列为 解答 q p next p next q next next delete q next delete q 4 单链表中设置头结点的带来的好处和不足之处分别是 解答 好处是减少是否为空的判断 统一不同位置上进行插入或删除的代码 不足是额 外占用一个结点空间 5 非空的带头结点的循环单链表 由头指针 H 指示 扫描工作指针变量 p 赋初值 为 p H next 则判断整个循环单链表中结点全部扫描完并控制结束的判定条件是

8、解答 p H 6 带头结点的单链表 由头指针 H 指示 扫描工作指针变量 p 赋初值为 p H next 若 现在已扫描到由指针 q 所指的结点为第 i 个结点 p 与 q 已相同 而要在第 i 位置上插入数据 元素为 x 的结点 能否用建立一个在第 i 1 位置上的结点 而将第 i 位置上 所对应结点中 的元素取出 放入第 i 1 结点 而将 x 放入第 i 个结点的方法 完成此插入任务 操作序列为 解答 生成一个结点 将其插在第 i 个结点和第 i 1 个结点之间 将第 i 个结点的 数 据 赋 给 该 结 点 在 将 x 赋 给 第 i 个 结 点 的 数 据 域 代 码 为 p new

9、Node p next q next q next p p data q data q data x 7 一个非空的带头结点的循环单链表 由头指针 H 指示 p 指向其中的某个结点 在 p 前插入一个数据元素为 x 的结点的操作序列为 解答 q H while q next p q q next s newNode s data x s next p q next s 8 带头结点的循环单链表 H 为空的判定条件是 解答 H next H 4 选择题选择题 1 在线性表存储结构中 能随机存取的是 而只能顺序存取的是 A 单链表B 双链表C 循环单链表D 顺序表 解答 D A B C 2 线性表

10、采用链式存储时 后一个结点的首地址在 中 A 头指针B 前一个结点C 前一个结点的指针域中D 本结点 解答 C 3 用尾指针表示的带头结点的循环单链表的主要优点是 A 不再需要头指针了 B 从尾结点出发也能扫描整个链表的所有节点 C 在进行两个循环单链表的合并时算法效率高 4 D 在进行插入 删除操作时 能更好地扫描链表 解答 C 4 带头结点的循环双链表的特点是 A 插入 删除操作简单B 可随机访问任一元素 C 不受存储空间大小的限制D 定位到某结点后 访问其前驱或后继时间复杂度相同 解答 D 5 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的后继 则采用 存 储方法最节省时

11、间 A 顺序表B 单链表c 双链表D 单循环链表 解答 A 6 若线性表最常用操作是在第一个元素之后插入一个元素和删除最后一个元素 则采用 存储方法最节省时间 A 单链表B 带尾指针的单循环链表 C 循环双链表D 带头指针的单循环链表 解答 B 7 若线性表最常用操作是在最后一个结点之后插入一个元素和删除最后一个元素 则采 用 存储方法最节省操作时间 A 顺序表B 循环双链表 C 单循环链表D 带尾指针的双链表 解答 D 8 在具有 n 个结点有序顺序表中插入一个新结点并使之仍然有序的时间复杂度是 A O 1 B O n C 2 nOD O nn 2 log 解答 B 9 对于 n 个元素组成

12、的线性表 建立一个有序单链表的时间复杂度是 A O 1 B O n C 2 nOD O nn 2 log 解答 C 10 设顺序表中有 10 个元素 删除第 4 个元素需移动个元素 A 5 B 6 C 7 D 8 解答 B 11 在在循环双链表的 p 所指结点后插入 s 所指结点的操作是 A p next s s prior p p next prior s s next p next B p next s p next prior s s prior p s next p next C s prior p s next p next p next s p next prior s D s p

13、rior p s next p next p next prior s p next s 解答 D 5 判断题判断题 1 线性表的逻辑顺序和存储顺序不一定相同 解答 正确 2 线性表的链式存储结构优于顺序存储结构 5 解答 错误 各有优缺点 3 有序表在建立时 新的元素总是添加在表的中间某个位置上 决不放在尾部 解答 错误 4 设 d1 d2 都是 LinkList 类的对象 则 d1 first 与 d2 first 永不相等 解答 错误 5 线性结构的基本特征是 除首尾两个数据元素外 其他每个元素有且仅有一个直接前 驱和一个直接后继 且首结点仅有一个直接后继 尾结点仅有一个直接前驱 解答

14、正确 6 在循环双链表中 要取得某个元素 只要从第一个结点开始扫描到该结点 或者从尾 结点开始扫描到该结点 或者从中间某个结点向前或向后扫描到该结点即可 因此循环双链表 是一种随机存取的存储结构 解答 错误 6 6 算法设计题算法设计题 1 在线性表顺序存储下 设计将其元素循环右移 k 位的操作 并分析算法时间复杂度 解答 利用线性表的一段 下标为 from to 的倒置算法 作为 SeqList 的友函数 三次分段倒置实现循环右移 k 位的算法 也作为 SeqList 的友函数 如下 2 设线性表以顺序存储结构存储 其数据元素为整数 试写出求表中最大元素及其所 一段倒置的算法 templat

15、e void RevListSeg SeqList int i for i 0 i to from 2 i temp a data from i 交换两个变量的值 a data from i a data to i a data to i temp 三次分段倒置实现循环右移 k 位的算法 template void LeftRotate SeqList ReverseSeg a 0 n k 1 前 n k 个元素倒置 ReverseSeg a n k n 1 后 k 个元素倒置 ReverseSeg a 0 n 1 全部倒置 6 在表中位置的算法 解答 假定数据可比较情况下 作为 SeqLis

16、t 类的友函数 可得到算法如下 3 设线性表以顺序存储结构存储 其数据元素为整数 试写出删除表中重复元素的算 法 有相同元素时 仅保留第一个 解答 算法在考虑到线性表中整数不一定是有序的情况下也能工作 4 设有一个整数顺序表 设计算法将其调整为前部为奇数 后部为偶数 且时间复杂度 为 O n 空间复杂度为 O 1 解答 求顺序表最大元素及其所在位置的算法 template void MaxData SeqList a T T max Min Min 为最小 T 类型常数 Maxpos 1 赋初值 1 for int i 0 imax max a data i maxpos i 删除整数顺序表中重复值的算法 template void Delduplicate SeqList a 作为 SeqList 类的友函数 int n a GetLength for int i 0 i n i for j i 1 j n j if a data i a data j for int k j 1 j n j a data k 1 a data k n a SetLength n 调整整数顺序表为前奇