数据结构复习题答案最终版.pdf

数据结构 so easy15730102 夏玉宝 第一章 1 数据数据 对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计 算机程序处理的符号的总称 2 数据元素数据元素 数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 3 数据结构数据结构 是相互之间存在一种或多种特定关系的数据元素的集合 数据结构 数据的逻辑结构 物理结构 4 数据类型数据类型 是一个值的集合和定义在这个值集上的一组操作的总称 5 数据的逻辑结构数据的逻辑结构 存在一种或多种特定关系的数据元素集合 常见的有集合 线性 树状 图 6 数据的物理结构数据的物理结构 数据元素的表示和关系的表示 任何需要计算机进行管理和处理的数据元素都必须首先按某种方式存储在 计算机中 数据存储结构能正确地表示出数据元素间的逻辑关系 7 数据逻辑结构和物理结构的区别和联系是什么 数据逻辑结构和物理结构的区别和联系是什么 区别 区别 逻辑结构 数据元素之间的逻辑关系 即人对数据的理解 而进行抽象的模型 物理结构 数据元素在计算机中的存储方法 即计算机对数据的理解 逻辑结构 在计算机语言中的映射 联系 联系 逻辑结构设计的任务是将基本概念模型图转换为与选用的数据模型相符合的 逻辑结构 逻辑结构设计的步骤 概念模型 一般数据模型 特定的数据模型 优化的数据模型 物理结构设计的任务是根据具体计算机系统的特点 为给定的数据模型确定 合理的存储结构和存取方法 所谓的 合理 主要有两个含义 一个是要使设计 出的物理数据库占用较少的存储空间 另一个对数据库的操作具有尽可能高的速 度 8 算法分析的目的是什么 算法分析的目的是什么 计算算法的时间复杂度和空间复杂度 从而找出解决问题的最优算法 提高效率 9 算法分析的主要方面是什么 算法分析的主要方面是什么 时间复杂度和空间复杂度 10 分析以下程序段的时间复杂度 请说明分析的理由或原因 分析以下程序段的时间复杂度 请说明分析的理由或原因 1 Sum 1 int n int p 1 sum 0 m for m 1 mnext NULL return q p head next 单链表删除节点 必须持有前一个节点 否则无法删除 while p next 查找和节点 p 重复的节点 重复则删除 q p s q next while s if s data p data 重复判断 重复 要删除 q next s next 从链表里删除 free s 实际删除节点 释放内存 s q next 保持 s q next else 不重复 准备判断下一个节点 节点向链表后面移动 q s s s next if p next 删除后 有可能链表 后面所有节点都删除了 所以要判断一下 p p next 节点后移 准备判断下一个数据节点 有没有重复节点 第三章 1 设有一个栈 元素进栈的次序为设有一个栈 元素进栈的次序为 a b c 问经过栈操作化可以得到哪些输出序问经过栈操作化可以得到哪些输出序 列 列 1 a 进栈 a 出栈 b 进栈 b 出栈 c 进栈 c 出栈 得到输出序列 abc 2 a 进栈 a 出栈 b 进栈 c 进栈 c 出栈 b 出栈 得到输出序列 acb 3 a 进栈 b 进栈 b 出栈 a 出栈 c 进栈 c 出栈 得到输出序列 bac 4 a 进栈 b 进栈 b 出栈 c 进栈 c 出栈 a 出栈 得到输出序列 bca 5 a 进栈 b 进栈 c 进栈 c 出栈 b 出栈 a 出栈 得到输出序列 cba 2 循环队列的优点是什么 如何判断它的空和满 循环队列的优点是什么 如何判断它的空和满 1 可以克服顺序队列的 假上溢 现象 当变成循环队列之后 删除元素 后的空间仍然可以利用 最大限度的利用空间 2 判断循环队列空和满有三种方法 第一 采用计数器来判断 空时 计数器为 0 满时 计数器为 maxsize 第二 另设一个布尔变量以匹别队列的空和满 第三 少用一个元素的空间 约定入队前 测试尾指针在循环意义下加 1 后是 否等于头指针 若相等则认为队满 注意 rear 所指的单元始终为空 3 设有一个静态顺序顺序队列 向量的大小为 判断队列为空的条件是什么 队列满的条件是什么 队满的条件 rear front 或rear MAX 1 此时 循环队列中能装入的元素 的个数为 MaxSize 队空的条件 rear front 首指针 front 一个队尾指针 rear 4设有一个静态循环循环队列 向量大小为 MAX 判断队列为空的条件是什么 队 列满的条件是什么 队满的条件 rear 1 MAX front 此时 循环队列中能装入的元素的个数 为 MaxSize 队空的条件 rear front 首指针 front 一个队尾指针 rear 5设 Q 0 6 是一个静态顺序队列 初始状态为 front rear 0 请画出做完下列 操作后队列的头尾指针的状态变化情况 若不能入对 请指出其元素 并说明理 由 a b c d 入队 a b c 出队 i j k l m 入队 d i 出队 n o p q r 入队 第四章 空串 零个字符的串 长度为零 空白串 由一个和多个空格组成 它的长度为串中空格字符的长度 子串 串中任意个连续的字符组成的子序列 主串 包含子串的串 令 分别求出它们的失 效函数值和改进后失效函数的值 第五章 1 什么是广义表 请简述广义表与线性表的区别 广义表是零至多个元素的有限序列 广义表中的元素可以是原子 也可以是广义表是零至多个元素的有限序列 广义表中的元素可以是原子 也可以是 子表 子表 从 元素的有限序列 角度看 广义表满足线性结构的特性 在非空线性结构中 只有一个称为 第一个 的元素 只有一个称为 最后一个 的元素 第一元素 有后继而没有前驱 最后一个元素有前驱而没有后继 其余每个元素有唯一前驱 和唯一后继 从这个意义上说 广义表属于扩充的线性结构 只不过元素并不具 有同一类型 可以是原子 也可以是广义表 当广义表中的元素都是原子时 广义表就蜕变为线性表 广义表是线性表的推广 线性表是广义表的特例 当广义表中的元素都是原 子时 即为线性表 2 一个广义表是 a a b d e a i j k 请画出 该广义表的链式存储结构 3 设有二维数组 a 6 8 每个元素占相邻的 4 个字节 存储器按字节编址 已 知 a 的起始地址是 1000 试计算 数组 a 的最后一个元素 a 5 7 起始地址 按行序优先时 元素 a 4 6 起始地址 按行序优先时 元素 a 4 6 起始地址 答 LOC a 5 7 LOC a 0 0 47 4 1188 LOC a 4 6 LOC a 0 0 4 8 6 4 1152 LOC a 4 6 LOC a 0 0 6 6 4 4 1116 4 假设用于通信的电文是由字符集 a b c d e f g h 中的字符构成 这 8 个字符在电文中出现的概率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 请画出对应的huffman树 按左子树根结点的权小于等于右子树根结点的权的 次序构造 求出每个字符的 huffman 编码 编码如下 a 1010 b 00 c 10000 d 1001 e 11 f 10001 g 01 h 1011 第六章 1 假设在树中 结点 x 是结点 y 的双亲时 用 x y 来表示树边 已知一棵树 边的集合为 i m i n e i b e b d a b g j g k c g c f h l c h a c 用树形表示法画出此树 并回答下列问题 1 哪个是根结点 2 哪些是叶结点 3 哪个是 g 的双亲 4 哪些是 g 的祖先 5 哪些是 g 的孩子 6 哪些是 e 的子孙 7 哪些是 e 的兄弟 哪些是 f 的兄弟 8 结点 b 和 n 的层次各是多少 9 树的深度是多少 10 以结点 c 为根的子树的深度是多少 11 树的度数是多少 答 1 a 是根结点 2 dmnfjkl 是叶结点 3 c 是 g 的双亲 4 c a 是 g 的祖先 5 j k 是 g 的孩子 6 imn 是 e 的子孙 7 d 是 e 的兄弟 g h 是 f 的兄弟 8 b 的层次是 2 n 的层次是 5 9 树的深度是 5 10 以 c 为根的子树深度是 3 11 树的度数是 3 2 已知一棵二叉树的先序遍历序列和中序遍历序列分别为 ABDGHCEFI 和 GDHBAECIF 请画出这棵二叉树 然后给出该树的后序遍历序列 并画出对应的 森林 第七章 1 设一有向图 G V E 其中 V a b c d e E 请画出该有向图 并求各顶点的入度和出度 分别画出有向图的正邻接链表和逆邻接链表 A 入度 2 出度 2 B 入度 3 出度 1 C 入度 1 出度 2 D 入度 2 出度 1 E 入度 1 出度 3 总计 入度 9 出度 9 第九章 对于一个有 n 个元素的线性表 若采用顺序查找方法时的平均查找长度是什 么 若结点是有序的 则采用折半查找法是的平均查找长度是什么 最好的情况 目标在第一个 一次找到 最坏的情况 目标在最后一个 n 次找到 那么 平均长度 1 2 n n n n 1 2 n n 1 2 公式 log 以 2 为底的 n 1 然后再减 1 2 试比较哈希表构造时几种冲突处理方法的优点和缺点 1 开放定址法开放定址法 这种方法也称再散列法 其基本思想是 当关键字 key 的哈希地址 p H key 出现冲突时 以 p 为基础 产生另一个哈希地址 p1 如果 p1 仍然冲突 再以 p 为基础 产生另一个哈希 地址 p2 直到找出一个不冲突的哈希地址 pi 将相应元素存入其中 这种方法有一个 通用的再散列函数形式 Hi H key di mi 1 2 n 其中 H key 为哈希函数 m 为表长 di 称为增量序列 增量序列的取值方式不同 相 应的再散列方式也不同 主要有以下三种 线性探测再散列线性探测再散列 dii 1 2 3 m 1 这种方法的特点是 冲突发生时 顺序查看表中下一单元 直到找出一个空单元或查遍全表 二次探测再散列二次探测再散列 di 12 12 22 22 k2 k2 k m 2 这种方法的特点是 冲突发生时 在表的左右进行跳跃式探测 比较灵活 伪随机探测再散列伪随机探测再散列 2 再哈希法再哈希法 这种方法是同时构造多个不同的哈希函数 Hi RH1 key i 1 2 k 当哈希地址 Hi RH1 key 发生冲突时 再计算 Hi RH2 key 直到冲突 不再产生 这种方法不易产生聚集 但增加了计算时间 3 链地址法链地址法 这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单 链表 并将单链表的头指针存在哈希表的第 i 个单元中 因而查找 插入和删除 主要在同义词链中进行 链地址法适用于经常进行插入和删除的情况 3 设关键字序列是 19 14 23 01 68 84 27 55 11 34 79 散列表长度是 11 散 列函数是 H key keyMOD11 采用开放地址法的线性探测方法解决冲突 请构造该关键字序列的哈希表 采用开放地址法的二次探测方法解决冲突 请构造该关键字序列的哈希表 1 012345678910 55 23 01 14 68 27 11 84 19 34 79 2 012345678910 55 23 01 14 34 27 6884 19 79 11 4 试比较线性索引和树形索引的优点和缺点 优点 1 通过创建唯一性索引 可以保证数据库表中每一行数据的唯一性 2 可以大大加快 数据的检索速度 这也是创建索引的最主要的原因 3 可以加速表和表之间的连接 特别是在实现数据的参考完整性方面特别有 意义 4 在使用分组和排序 子句进行数据检索时 同样可以显著减少查询中分组和 排序的时间 5 通过使用索引 可以在查询的过程中 使用优化隐藏器 提高系统的性能 缺点 1 创建索引和维护索引要耗费时间 这种时间随着数据 量的增加而增加 2 索引需要占物理空间 除了数据表占数据空间之外 每一个索引还要占一 定的物理空间 如果要建立聚簇索引 那么需要的空间就会更大 3 当对表中的数据进行增加 删除和修改的时候 索引也要动态的维护 这 样就降低了数据的维护速度 第十章 1 从未排序序列中挑选元素 并将其依次放入到已排序序列中 初始时为空 的 一端的方法是什么 答 选择排序的基本方法是 扫描整个线性表 从中选出最小的元素 将它交换 到表的最前面 然后对剩下的子表采用同样的方法 直到子表空为止 2 在待排序的元素基本有序的前提下 效率最高的排序方法是什么 答 插入排序通过数据元素的交换来逐步消除线性表中的逆序 所以关键字比较 的次数与记录的初始排列次序有关 在待排序的元素