《数据结构、算法与应用(C++语言描述)》习题参考答案doc

第 1 章 概 论 1 数据 数据元素 数据结构 数据类型的含义分别是什么 数据 对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并由计算 机程序处理的符号的总称 数据元素 数据的基本单位 在计算机程序中通常作为一个整体考虑 数据结构 数据元素之间的关系 运算 是以数据为成员的结构 是带结构的数据元 素的集合 数据元素之间存在着一种或多种特定的关系 数据类型 数据类型是用来区分不同的数据 由于数据在存储时所需要的容量各不相 同 不同的数据就必须要分配不同大小的内存空间来存储 所有就要将数据划分成不同的 数据类型 数据类型包含取值范围和基本运算等概念 2 什么是数据的逻辑结构 什么是数据的物理结构 数据的逻辑结构与物理结构的区别和 联系是什么 逻辑结构 数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系 数据的 逻辑结构包含下面两个方面的信息 数据元素的信息 各数据元素之间的关系 物理结构 也叫储存结构 是 指 逻 辑 结 构 的 存 储 表 示 即 数据的逻辑结构在计算机 存储空间中的存放形式 包括结点的数据和结点间关系的存储表示 数据的逻辑结构和存储结构是密不可分的 一个操作算法的设计取决于所选定的逻辑 结构 而算法的实现依赖于所采与的存储结构 采用不同的存储结构 其数据处理的效率 是不同的 因此 在进行数据处理时 针对不同问题 选择合理的逻辑结构和存储结构非 常重要 3 数据结构的主要操作包括哪些 对于各种数据结构而言 他们在基本操作上是相似的 最常用的操作有 创建 建立一个数据结构 清除 清除一个数据结构 插入 在数据结构中增加新的结点 删除 把指定的结点从数据结构中删除 访问 对数据结构中的结点进行访问 更新 改变指定结点的值或改变指定的某些结点之间的关系 查找 在数据结构中查找满足一定条件的结点 排序 对数据结构中各个结点按指定数据项的值 以升序或降序重新排列 4 什么是抽象数据类型 如何定义抽象数据类型 抽象数据类型 Abstract Data Type 简称 ADT 是指一个数学模型以及定义在此数学 模型上的一组操作 ADT 是与具体的物理存储无关的数据类型 因此 不论 ADT 的内部 结构如何变化 只要其数据结构的特性不变 都不影响其外部使用 对抽象数据类型的描述一般用 D R P 三元组表示 抽象数据类型的定义格式为 ADT 数据对象 D 数据关系 R 基本操作 P ADT 其中 D 是数据对象 R 是 D 上的关系集 P 是对 D 的基本操作集 数据对象和数据关系的定义用伪代码来描述 基本操作的定义格式为 基本操作名 参数表 初始条件 操作结果 初始条件说明操作执行之前数据结构和参数应满足的条件 操作结果说明操作完成后 数据结构的变化状况和应返回的结果 5 什么是算法 算法的基本特征是什么 算法 是在有限的步骤内解决数学问题的过程 是以一步接一步的方式来详细描述计 算机如何将输入转化为所要求的输出的过程 即算法是对计算机上执行的计算过程的具体 描述 一个有效的算法必须满足的五个重要特性 有穷性 算法必须能在有限的时间内做完 即在任何情况下 算法必须能在执行 有限个步骤之后终止 都不能陷入无穷循环中 确定性 算法中的每一个步骤 必须经过明确的定义 并且能够被计算机所理解 和执行 而不能是抽象和模糊的概念 更不允许有二义性 输入 算法有 0 个或多个输入值 来描述算法开始前运算对象的初始情况 这是 算法执行的起点或是依据 0 个输入是指算法本身给出了运算对象的初始条件 输出 算法至少有 1 个或多个输出值 反映对运算对象的处理结果 没有输出的 算法没有任何意义 可行性 算法中要做的运算都是基本运算 能够被精确地进行 即算法中执行的 任何计算都可以被分解为基本的运算步 每个基本的运算步都可以在有限的时间内完成 6 什么是算法分析 算法分析主要考虑哪几方面的内容 算法的研究与实际问题直接相关 用来解一个问题可以有很多不同的算法 他们之间 的效果可能会有很大差异 算法设计者最关心的就是什么是有效的算法 如何评价一个算 法的优劣 如何从多种算法中选择好的算法 除了要首先考虑算法的正确性外 还要分析 和评价算法的性能 分析和评价算法的性能主要要考虑以下两个方面 时间代价 执行算法所耗费的时间 一个好的算法首先应该比其他算法的运行时间 代价要小 算法的时间代价的大小用算法的时间复杂度来度量 空间代价 执行算法所耗费的存储空间 主要是辅助空间 算法运行所需的空间消 耗是衡量算法优劣的另一个重要因素 算法的空间代价的大小用算法的空间复杂度来度量 7 分析下面算法的时间复杂度 1 答 时间复杂度为 n2 2 时间复杂度 n 3 时间复杂度 4 时间复杂度 n 2 5 时间复杂度 O log 2n 8 算法设计中的递归 穷举 递推和迭代等算法的基本思想是什么 递推法 是利用问题本身所具有的一种递推关系求解问题的一种方法 它把问题求解 分成若干步 找出相邻几步的关系 从而达到求解问题的目的 具有如下性质的问题可以 采用递推法 当得到问题规模为 i 1 的解后 由问题的递推性质 能构造出问题规模为 i 的 解 因此 程序可以从 i 0 或 i 1 出发 由已知 i 1 规模的解 通过递推 获得问题规模为 i 的解 直至得到问题规模为 n 的解 递归法 递归策略是利用函数直接或间接地调用自身来完成某个计算过程 能采用递 归描述的算法通常有这样的特征 为求解规模为 n 的问题 设法将它分解成规模较小的问 题 然后从这些小问题的解方便地构造出更大问题的解 并且这些规模较小的问题也能采 用同样的分解和综合方法 分解成规模更小的问题 并从这些更小问题的解构造出较大规 模问题的解 穷举法 穷举搜索法也称穷举法或搜索法是对可能是解的众多候选解按某种顺序进行 逐一枚举和检验 并从中找出那些符合要求的候选解作为问题的解 迭代法 数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题 一般是 解方程或者方程组 的过程 为实现这一过程所使用的方法统称为迭代法 9 算法设计中的分治策略 贪心策略 动态规划策略 回溯策略以及分支定界策略的基本 思想是什么 分治策略的基本思想是把一个规模为 n 的问题划分为若干个规模较小 且与原问题相 似的子问题 然后分别求解这些子问题 最后把各子结果合并得到整个问题的解 分解的 子问题通常与原问题相似 所以可以递归地使用分治策略来求解 贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题 决策一旦 做出 就不能再更改 它是通过若干次的贪心选择而得出最优解 或较优解 的一种解题 策略 动态规划策略与贪心策略类似 将一个问题划分为重复的子问题 通过对相同子问题 的求解来解决较大问题 即将一个问题的解决方案视为一系列决策的结果 不同的是 在 贪心策略中 每采用一次贪心准则便做出一个不可撤回的决策 可能得不到问题的最优解 而在动态规划中 处理要按照某种规则进行选择 还要考察每个最优决策序列中是否包含 一个最优子序列 目的是得到问题的最优解 回溯策略也叫试探法 它的基本思想是 在一些问题求解进程中 先选择某一种可能 情况向前探索 当发现所选用的试探性操作不是最佳选择 需退回一步 重新选择继续进 行试探 直到找到问题的解或者证明问题无解 分支定界策略也经常被称为分支限界策略 它的基本思想是 首先确定目标值的上下 界 然后一边搜索一边剪掉空间树的某些不可能产生最优解的分支 提高搜索效率 第二章 线性表 1 具有什么特征的数据结构被称为线性表 线性表是一种最常用 最简单的典型线性数据结构 应用非常广泛 线性表是由 n n 0 个数据元素组成的一个有限序列 线性表中数据元素的个数 n 称为线性表的长度 当 n 0 时 称为空表 对于非空线性表 数据元素之间存在一对一的关系 具体特性如下 第一个数据元素没有前驱 最后一个数据元素没有后继外 其他数据元素都是首尾相接 有且只有一个前驱和后继 2 如何实现线性表的顺序存储结构 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的 顺序存储 采用顺序存储结构的线性表简称顺序表 线性表的顺序存储结构有如下特点 线性表中所有元素所占的存储空间是连续的 线性表的逻辑顺序与物理顺序一致 数组中的每一个元素的位置可以用公式来确定 假设线性表中的第一个数据元素 的存储地址 指第一个字节的地址 即首地址 为 LOC e1 每一个数据元素占 k 个字节 则线性表中第 i 个元素 ei 在计算机存储空间中的存储地址为 LOC ei LOC e1 i 1 k 3 如何实现线性表的 4 种链式存储结构 数据结构中的每一个数据元素对应于一个存储单元 这种存储单元称为存储结点 简 称结点 每个结点分为两部分 一部分用于存放数据元素的值 称为数据域 另一部分是 指针 用于指向与该结点在逻辑上相连的其他结点 称为指针域 对于线性表 指针域用 于指向该结点的前一个或后一个结点 即前驱结点或后继结点 通过结点的指针域将 n 个结点按其逻辑结构连接在一起的数据存储结构 称为链式存储结构 单向链表 在线性链表中 用一个专门的指针指向线性表中第一个结点 每一个结点 的指针都指向它的下一个逻辑结点 线性链表的最后一个结点的指针为空 用 NULL 或 0 表示 表示链表终止 这样的线性链表称为单向链表 下图是单向链表示意图 线性表的单向链式存储 循环链表 将单向链表最后一个结点的指针指向头结点 这样整个链表就构成一个循 环 这种链式存储结构称为单向循环链表 简称循环链表 头结点的指针域指向线性表的 第一个元素的结点 循环链表中最后一个结点的指针域不再是 NULL 而是指向头结点 只有头结点的循环链表称为空循环链表 下图是带头结点的非空循环链表和空循环链表示 意图 first e 1 e2 ei en NULLNULL NULL 带头结点的循环链表 双向链表 双向链表的每个结点含有两个指针域 一个指针指向其前驱结点 另一个 指针指向其后继结点 双向链表结点的结构下图 a 所示 双向循环链表 如果将双向链表第一个结点的 prev 指针指向最后一个结点 将最后一 个结点的 next 指针与指向第一个结点 就构成了双向循环链表 下图 b 和 c 是双向 链表和双向循环表的逻辑结构示意图 图 双向链表结点结构及双向链表 4 顺序表和线性链表分别有哪些优点和缺点 线性表的顺序存储与链式存储比较 比较内容 顺序存储 链式存储 结点存储空间 少 不需要为表示结点的逻辑关系增 加开销 多 需要增加指针域来表示结点之间 的逻辑关系 空间利用率 低 采用数组 按表的最大长度静态 分配存储空间 高 根据表的实际长度动态分配存储 空间 插入 删除操作 慢 需要大量移动元素 快 仅更改指针指向 不需要移动元 素 访问元素 快 直接访问 慢 通过指针移动才能访问 实现难易程度 相对容易 基于数组操作 一般高级 语言都提供数组类型 相对困难 基于指针操作 5 请列举出一些线性表问题的实例 按员工号排序的员工基本情况表 奥运会各项比赛日程 按学号记录的学生的成绩单 等等 6 对于顺序表和单向链表 如何实现统计重复元素个数的操作 e1 head en 头结点 head 头结点 a 带头结点的非空循环链表 b 带头结点的空循环链 表 e2 en b 双向链表 e1 e2 en c 双向循环链表 prev data next a 双向链表结点结构 first first e1 end 在顺序表中实现统计重复元素个数的操作 在教材的 描述 2 1 中 增加一个统计重复元素个数的成员函数 int Count const T 返回 x 出现的次数 在教材的 描述 2 2 中 增加查找重复元素个数的成员函数的实现 实现统计重复元素个数 template int LinearList Count const T for int i 0 i length i if element i x count return count 在顺序表中实现统计重复元素个数的操作 在教材的 描述 2 3 中 增加一个统计重复元素个数的成员函数 int Count const T 返回 x 出现的次数 在教材的 描述 2 4 中 增加查找重复元素个数的成员函数的实现 实现统计重复元素个数 template int LinkList Count const T int count 0 while p NULL p p next return count 第 3 章 栈和队列 1 具有什么特征的数据结构被称为栈和队列 先进后出 栈顶 栈底 先进先出 队头 队尾的概念是什么 栈 一种插入和删除都只能在表的同一端进行的线性表 队列 一种只允许在表的一端进行插入操作 而在表的另一端进行删除操作的线性表 先进后出 元素是以 e1 e 2 e n 顺序进入数据结构 以相反的顺序即 en e n 1 e 1 离开数据结构 栈顶 允许进行插入和删除操作的一端 栈底 栈中与栈顶相对的另一端 先进先出 元素是以 e1 e 2 e n 顺序进入数据结构 以相同的顺序即 e1 e 2 e n 离开数据结构 队头 允许删除操作的一端 队尾 允许插入操作的一端 2 简述在顺序栈的栈顶插入一个元素的操作过程 在插入元素之前 首先要判断栈是否为满 如果栈满 返回 沾满无法插入 等错误 提示信息 否则让 top 指针 指向当前顺序栈的栈顶 向后移动一个元素空间 元素大小 将要插入的元素放入 top 指针指向的内存单元中 3 一个栈的输入序列为 1 2 3 试给出全部可能的出栈序列 可分为三种情况 当只有一个存储空间时 只有一种出栈序列 1 2 3 当有两个存储空间时 有 1 2 3 2 1 3 2 3 1 等 3 种出栈序列 当存储空间大于等于三个时 有 1 2 3 2 1 3 2 3 1 3 2 1 等 4 种出栈序列 4 循环队列的优点是什么 在循环队列中 仅依据头尾指针相等 无法判断队列是 空 还 是 满 要解决这个问题 常用的两种方法是什么 循环队列的优点有两点 一是可以避免发生顺序队列的 假上溢 现象 二是充分利 用队列的存储空间 两种判断队列是 空 还是 满 的方法 一是约定少用一个元素空间 二是使用计 数器 size 记录当前队列的实际长度 5 简述在链接栈中插入一个元素的操作过程 链接栈的插入操作 先将待进栈结点的指针域指向原来的栈顶结点 然后将栈顶指针 top 修改指向该结点 使进栈元素结点成为新的栈顶结点 6 请列举出一些可以用栈和队列表示的实际问题 所有 后进先出 LIFO Last In First Out 的实际问题都可以用栈表示 栈的应用主要 有 数制的转换 括号的匹配检查 行编辑处理 表达式求解 走迷宫以及高级语言中函 数的嵌套调用和递归的实现等 所有 先进先出 FIFO First In First Out 的实际问题都可以用队列表示 如日常中的 排队问题 队列的应用主要有 操作系统中各种资源请求排队和各种缓冲区的先进先出管 理 各种应用系统中的事件规划和事件模拟 树的层次遍历和图的广度优先遍历等 第 4 章 数组 字符串与广义表 1 具有什么特征的数据结构被称为数组 数组可以看成是形如 index value 的数据集合 其中 index 是元素的索引 表示 数据的逻辑位置 任意两个数据的 index 都不相同 value 表示数据元素的值 2 设有二维数组 a 5 6 每个元素占相邻的 8 个字节 存储器按字节编址 已知 a 的起始 地址是 1000 试计算 1 数组 a 的最后一个元素起始地址 1000 30 1 8 1232 2 按行序优先时 元素 a 3 5 的起始地址 1000 3 6 5 8 1184 3 按行列序优先时 元素 a 4 3 的起始地址 1000 3 5 4 8 1152 3 请简述数组和矩阵的关系 矩阵是指纵横排列的二维数据表格 在高级语言编程中 通常用二维数组来描述一个 矩阵 从而可以对矩阵中的元素进行随机存取 但矩阵的索引通常从 1 而不是像数组那样 从 0 开始 并且使用 A i j 而不是 A i j 的形式来引用矩阵中的元素 4 矩阵有哪些基本运算 矩阵的操作包括转置 加法 减法和乘法等 5 稀疏矩阵的特点是什么 为什么要对稀疏矩阵采用压缩存储技术 稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数 采用压缩存储技术主要是为了节省空间 6 设 A 和 B 是稀疏矩阵 都以三元组作为存储结构 请写出矩阵相加的算法 C A B 稀疏矩阵的三元组表示 include using namespace std define M 50 define N 50 define MaxSize 20 typedef int ElemType typedef struct int r int c ElemType d TupNode typedef struct int rows int cols int nums TupNode data MaxSize TSMatrix int A M N B M N 建立三元组 void CreateMat int A M N TSMatrix t rows row t cols col t nums 0 for i 0 i M i for j 0 j N j if A i j 0 t data t nums r i t data t nums c j t data t nums d A i j t nums 矩阵相加 int MatAdd TSMatrix ElemType v if a rows b rows a cols b cols return 0 c rows a rows c cols a cols while i a nums c data k c b data j c c data k d b data j d j k else v a data i d b data j d if v 0 c data k r a data i r c data k c a data i c c data k d v k i j else if a data i r b data j r c data k r a data i r c data k c a data i c c data k d a data i d i k else c data k r b data j r c data k c b data j c c data k d b data j d j k if i a nums while j b nums c data k r b data j r c data k c b data j c c data k d b data j d j k if j b nums while i a nums c data k r a data i r c data k c a data i c c data k d a data i d i k c nums k return 1 输出三元组 void DispMat TSMatrix t int i if t nums 0 cout 此矩阵所有元素都为 endl return cout t rows t t cols t t nums endl cout endl for i 0 i t nums i cout t data i r t t data i c t t data i d endl endl 主函数 int main int row col i j TSMatrix a b c cout row col cout 请输入矩阵 A 的元素 n for i 0 i row i for j 0 j A i j cout 请输入矩阵 B 的元素 n for i 0 i row i for j 0 j B i j CreateMat A a row col CreateMat B b row col cout 矩阵 A 的三元组表示为 n DispMat a cout 矩阵 B 的三元组表示为 n DispMat b if MatAdd a b c cout 矩阵 A B 相加后得到的三元组表示为 n DispMat c return 0 7 简述字符串与一维字符型数组的区别与联系 字符串简称串 它是一种以字符为元素的特殊线性表 字符串可以看成是以字符为元素 的一维数组 具体实现时 在 C C 中的字符串使用为字符型数组来表示 为了便于确定 字符串的结尾 在字符型数组中使用 0 就是 0 作为字符串的截止符 8 列举一些需要进行字符串模式匹配的应用场景 例如 在文本编辑中经常要查找某一特定单词或者一段话在整篇文章中出现的位置 按 照姓名查找某个学生 员工 居民 有效的模式匹配能极大地提高文本编辑程序的能力 9 列举几个字符串的其他操作 求字符串中某个子串出现的次数 删除满足条件的子串 字符串字符移位等 10 什么是广义表 广义表与线性表的区别是什么 广义表又称列表 是由 n n 0 个元素组成的有穷序列 GL e 1 e 2 e n 但 与线性表不同的是 广义表中的元素允许以不同的形式出现 它可以是一个原子 逻辑上 不能再分解的元素 也可以是另一个广义表 11 一个广义表是 a a b c d e m n w i j x 请问该广义表的长度 深度分别是多少 请画出该广义表的单链表存储结构示意图 该广义表的深度是 3 长度是 6 该广义表的单链表存储结构示意图如下 1 1 2 a 2 1 d 1 w h e a d 0 h e a d 0 a 1 e 1 b 1 c 1 m h e a d 0 1 n 2 1 i h e a d 0 1 j 2 1 x 12 请列举出一些可以归纳成数组 矩阵 字符串和广义表数据结构的实际问题 线性表的顺序存储 学生编号和姓名的问题 各班级的学生编号和姓名的问题等 都 可以归结为数组 不同物品所需原材料的数量 不同产地原材料的价格 不同类型的住宅需要的物品数 量等 不同学生的计算机成绩 不同职工的工资等都可以归结为矩阵 学生的姓名和学号 学校或各单位的名称 国家名称 一篇文章 一个高级语言源程 序等 都可归结为字符串 应用高斯消元法求解方程组可以归结为广义表 第 5 章 树和二叉树 1 请简述树 二叉树 满二叉树和完全二叉树的结构特性 树 只有最顶层的结点没有前驱 其余结点都有且只有一个前驱 一个结点可以没有 后继 也可以有一个或多个后继 二叉树 一种特殊形态的树 每个结点至多有两个后继 满二叉树 一种特殊形态的二叉树 除了最后一层的结点为叶子结点外其它结点都有 左 右两棵子树的二叉树 完全二叉树 一种特殊形态的二叉树 其结点与相同深度的满二叉树中的结点编号完 全一致 即对于深度为 k 的完全二叉树 其前 k 1 层与深度为 k 的满二叉树的前 k 1 层完 全一样 只是在第 k 层上有可能缺少右边若干个结点 2 请解释结点的度 树的度 结点的层 树的深度 分支 路径 路径长度 树的路径长 度 叶子结点 分支结点 内部结点 孩子 双亲 兄弟 堂兄弟 祖先 子孙 有序树 无序树和森林等基本术语的含义 结点的度和树的度 一个结点的后继的数目称为该结点的度 树中各结点度的最大值 称为树的度 结点的层和树的深度 树的根结点所在的层为第 1 层 其余结点的层等于其前驱结点 的层加 1 树中各结点的层的最大值称为树的深度 分支 路径 路径长度和树的路径长度 从一个结点到其后继结点之间的连线称为一 个分支 从一个结点 X 到另一个结点 Y 所经历的所有分支构成结点 X 到结点 Y 的路径 一条路径上的分支数目称为路径长度 从树的根结点到其他各个结点的路径长度之和称为 树的路径长度 叶子结点 分支结点和内部结点 树中度为 0 的结点称为叶子结点 或终端结点 度不为 0 的结点称为分支结点 或非终端结点 除根结点以外的分支结点也称为内部结 点 孩子和双亲 在树中 一个结点的后继结点称为该结点的孩子 相应地 一个结点的 前驱结点称为该结点的双亲 即一个结点是其孩子结点的双亲 其双亲结点的孩子 兄弟和堂兄弟 同一双亲的孩子结点之间互称为兄弟 不同双亲但在同一层的结点之 间互称为堂兄弟 祖先和子孙 从树的根结点到某一个结点 X 的路径上经历的所有结点 包括根结点但 不包括结点 X 称为结点 X 的祖先 以某一结点 X 为根的子树上的所有非根结点 即除结 点 X 外 称为结点 X 的子孙 有序树和无序树 对于树中的任一结点 如果其各棵子树的相对次序被用来表示数据 之间的关系 即交换子树位置会改变树所表示的内容 则称该树为有序树 否则称为无序 树 森林 m m 0 棵互不相交的树的集合就构成了森林 3 请简述二叉树的五条基本性质 性质 1 在二叉树的第 i 层上至多有 2i 1 个结点 i 1 性质 2 深度为 k 的二叉树至多有 2k 1 个结点 性质 3 在二叉树中 若度为 0 的结点 即叶子结点 数为 n0 度为 2 的结点数为 n2 则 n0 n2 1 性质 4 具有 n 个结点的完全二叉树其深度为 log2n 1 其中 log2n 表示不大于 log2n 的最大整数 性质 5 采用顺序编号的完全二叉树具有如下性质 若一个分支结点的编号为 i 则其 左子树的根结点 即左孩子结点 编号为 2 i 右子树的根结点 即右孩子结点 编号为 2 i 1 反之 若一个非根结点的编号为 i 则其双亲结点的编号为 i 2 其中 i 2 表示不 大于 i 2 的最大整数 4 请简述二叉树的常用操作及各操作的含义 创建一棵空二叉树 创建一棵没有任何结点的二叉树 在顺序表示中 根据树的深度 为结点分配内存 在二叉链表表示中 将指向根结点的指针赋值为 NULL 删除一棵二叉树 将二叉树各结点所占据的内存释放 清空二叉树 将二叉树的所有结点删除 使之成为一棵空二叉树 以指定元素值创建根结点 创建根结点 并以指定值作为根结点的元素值 将一个结点作为指定结点的左孩子插入 根据指定元素值生成一个新结点 并将其作 为指定结点的左孩子 将一个结点作为指定结点的右孩子插入 根据指定元素值生成一个新结点 并将其作 为指定结点的右孩子 先序遍历二叉树 也称为先根遍历 其访问方式递归定义如下 对于一棵二叉树 先 访问其根结点 再访问根结点的左 右子树 对于左 右子树中的结点仍然是按照先序遍 历方式访问 即先访问根结点 再访问根结点的左 右子树 中序遍历二叉树 也称为中根遍历 其访问方式递归定义如下 对于一棵二叉树 先 访问根结点左子树 再访问根结点 最后访问右子树 对于左 右子树中的结点仍然是按 照中序遍历方式访问 后序遍历二叉树 也称为后根遍历 其访问方式递归定义如下 对于一棵二叉树 先 访问根结点的左子树 后访问右子树 最后访问根结点 对于左 右子树中的结点仍然是 按照后序遍历方式访问 逐层遍历二叉树 从第 1 层开始依次对每层中的结点按照从左至右的顺序进行访问 获取指定结点的双亲结点 根据指定结点获取其双亲结点 在顺序表示中 可以直接 根据指定结点的位置计算双亲结点的位置 在二叉链表表示中 则需要从根结点开始遍历 二叉树直至找到指定结点的双亲结点 删除以指定结点为根的子树 将以指定结点为根结点的子树上的所有结点 包括指定 结点 删除 按关键字查找结点 按照某种规则 先序 中序 后序或逐层 依次访问二叉树中的 每一结点 直至找到与关键字匹配的结点 判断二叉树是否为空 判断一棵二叉树是否为空二叉树 修改指定结点的元素值 将指定结点的元素值修改为指定值 计算二叉树的深度 按照某种规则依次访问二叉树中的每一结点 计算各结点所在层 的最大值 计算二叉树的叶子结点数 按照某种规则依次访问二叉树中的每一结点 计算度为 0 的结点数 5 请简述顺序表示的二叉树中各结点的编号规则 顺序表示的二叉树中各结点的编号与相同深度的完全二叉树中对应结点的编号相同 6 请简述二叉链表表示和三叉链表表示的二叉树中结点的结构 在二叉链表表示中 双亲结点有指向其孩子结点的指针 而孩子结点不包含指向其双 亲结点的指针 在三叉链表表示中 双亲结点有指向其孩子结点的指针 而孩子结点也包 含指向其双亲结点的指针 7 请简述二叉树的四种遍历方式及每一种遍历方式中结点的访问顺序 先序遍历二叉树 也称为先根遍历 其访问方式递归定义如下 对于一棵二叉树 先 访问其根结点 再访问根结点的左 右子树 对于左 右子树中的结点仍然是按照先序遍 历方式访问 即先访问根结点 再访问根结点的左 右子树 中序遍历二叉树 也称为中根遍历 其访问方式递归定义如下 对于一棵二叉树 先 访问根结点左子树 再访问根结点 最后访问右子树 对于左 右子树中的结点仍然是按 照中序遍历方式访问 后序遍历二叉树 也称为后根遍历 其访问方式递归定义如下 对于一棵二叉树 先 访问根结点的左子树 后访问右子树 最后访问根结点 对于左 右子树中的结点仍然是 按照后序遍历方式访问 逐层遍历二叉树 从第 1 层开始依次对每层中的结点按照从左至右的顺序进行访问 8 已知一棵二叉树的先序遍历结果为 A B D G C E F H I 中序遍历结果为 D G B A E C H F I 请给出该二叉树的后序遍历结果 G D B E H I F C A 9 已知一棵二叉树的中序遍历结果为 D G B A E C H F I 后序遍历结果为 G D B E H I F C A 请给出该二叉树的先序遍历结果 A B D G C E F H I 10 已知一棵二叉树的先序遍历结果为 A B D G C E F H I 后序遍历结果为 G D B E H I F C A 请给出该二叉树的中序遍历结果 D G B A E C H F I 11 请简述哈夫曼树的结构特性 哈夫曼树 又称最优二叉树 是指在由 n 个叶子结点构成的一类二叉树中具有最短带 权路径长度的二叉树 12 请简述结点的权 结点的带权路径长度 树的带权路径长度等基本术语的含义 结点的权和结点的带权路径长度 在实际应用中 往往给树中的结点赋予一个具有某 种意义的实数 该实数就称为是结点的权 结点的带权路径长度是指从树根到该结点的路 径长度与结点的权的乘积 树的带权路径长度 是指树中所有叶子结点的带权路径长度之和 记为 其中 n 为叶子结点的数目 W i为第 i 个叶子结点的权 L i为根结点到 iiLWP1 第 i 个叶子结点的路径长度 可知 WiLi为第 i 个叶子结点的带权路径长度 13 请简述哈夫曼树的构造方法 哈夫曼树的构造方法如下 a 已知 n 个权值为 Wi i 1 2 n 的结点 将每个结点作为根结点生成 n 棵只 有根结点的二叉树 Ti 形成森林 F T1 T2 Tn b 从森林 F 中选出根结点权值最小的两棵二叉树 Tp和 Tq 并通过添加新的根结点 将它们合并为一棵新二叉树 新二叉树中 Tp和 Tq分别作为根结点的左子树和右子树 且 根结点的权值等于 Tp和 Tq两棵二叉树的根结点权值之和 以合并后生成的新二叉树替代 森林 F 中的原有二叉树 Tp和 Tq 重复该步骤直至森林 F 中只存在一棵二叉树 14 请简述哈夫曼码的作用及其编码方法 哈夫曼编码是指将用其他编码法表示的字符序列转成用哈夫曼码表示以减少存储空间 其具体方法为 a 以要编码的字符集 C c1 c2 cn 作为叶子结点 字符出现的频度或次数 W w1 w2 wn 作为结点的权 构造哈夫曼树 b 规定哈夫曼树中 从根结点开始 双亲结点到左孩子结点的分支标为 0 双亲结 点到右孩子结点的分支标为 1 从根结点到某一叶子结点经过的分支形成的编码即是该叶 子结点所对应字符的哈夫曼码 15 请简述树的四种常用表示方式 双亲表示法 在孩子结点中设置一个指针域记录其双亲结点的存储位置 孩子表示法 在双亲结点中设置指向孩子结点的指针域来表示一棵树 孩子双亲表示法 综合了孩子表示法和双亲表示法的特点 既在孩子结点中设置记录 双亲结点位置的指针域 又在双亲结点中设置记录孩子结点位置的指针域 孩子兄弟表示法 又称为二叉链表表示法 与二叉树的二叉链表表示法存储结构完全 相同 只是结点中指针域的含义有所不同 一个指针域指向该结点的第一个孩子结点 另 一个指针域指向该结点的下一个兄弟结点 16 请简述森林转换为二叉树的具体步骤 将森林中的每棵树都用二叉链表表示法表示 并将各棵二叉树的根结点看做是兄弟结 点 在它们之间加上连线 将结点到第一个孩子结点的连线作为左子树的边 结点到兄弟 结点的连线作为右子树的边 17 请简述二叉树转化为树或森林的具体步骤 将一个结点左子树的边作为该结点指向第一个孩子结点的连线 右子树的边作为该结 点到兄弟结点的连线 在双亲结点和它的各孩子结点之间加上连线 并删除兄弟结点之间 的连线 得到一棵树或一个包含若干棵树的森林 第 6 章 图 1 请简述图的结构特性 图 G 由顶点 图中通常将结点称为顶点 的非空有限集合 V 和边的集合 E 组成 记 为 G V E 每一个顶点偶对就是图中的一条边 所以 E 用于表示 V 上的连接关系 在 一个图中 至少要包含一个顶点 但可以没有任何边 2 请解释有向图 无向图 弧 弧尾 弧头 顶点的度 顶点的入度 顶点的出度 路径 路径长度 回路 简单回路 连通图 单向连通图 强连通图 子图 连通分量 强连通 分量 权 带权图 生成树 最小生成树等基本术语的含义 有向图 弧 弧尾和弧头 若 E G 中的顶点偶对是有序的 则这些有序偶对就形成了 有向边 此时图 G 称为有向图 其中 有向边也简称为弧 在有向图 G 中 对于一条从顶 点 vi 到顶点 vj 的弧 记为并有 E G 称 vi 为弧尾 v j 为弧头 无向图 若 E G 中的顶点偶对是无序的 则这些无序偶对就形成了无向边 此时图 G 称为无向图 顶点的度 顶点的入度和顶点的出度 在无向图中 与顶点 vi 相关联的边的数目称为 顶点 vi 的度 在有向图中 以顶点 vi 为弧头的弧的数目称为顶点 vi 的入度 以顶点 vi 为弧 尾的弧的数目称为 vi 的出度 顶点 vi 的入度和出度之和称为 vi 的度 路径和路径长度 在图 G 中 若存在一个顶点序列 使得对于任意0i11 ni 0 j n 1 有 若 G 为有向图 或 若 G 为无向图 则该E v 1ji E v ji 序列是从顶点 到顶点 的一条路径 一条路径中边的数目称为路径长度 0i1 ni 回路和简单回路 在一条路径中 若组成路径的顶点序列中第一个顶点与最后一个顶 点相同 则该路径称为回路 或环 在一个回路中 若除第一个顶点与最后一个顶点外 其他顶点只出现一次 则该回路称为简单回路 或简单环 连通图 无向图 G 中 若任意两个顶点都是连通的 则称 G 为连通图 单向连通图和强连通图 有向图 G 中 若任意两个顶点都是单向连通的 则称 G 是单 向连通图 若任意两个顶点都是强连通的 则称 G 为强连通图 子图 对于图 G G 若满足 且 则 G 是 G 的子图 V E 连通分量和强连通分量 一个无向图的极大连通子图称为该无向图的连通分量 一个 有向图的极大强连通子图称为该有向图的强连通分量 权和带权图 可以为一个图中的每条边标上一个具有某种意义的实数 该实数就称为 是边的权 边上带权的图就称为带权图 生成树和最小生成树 若无向图 G 的一个子图 G 是一棵包含图 G 所有顶点的树 则 G 称为图 G 的生成树 在所有形式的生成树中 边上的权之和最小的生成树 称为最小生 成树 3 请列举可以用图来描述的实际问题 请参考例 6 1 和例 6 2 4 请简述图的基本操作及各操作的含义 创建图 创建不包含任何顶点和边的空图 对图作深度优先遍历 类似于树的先序遍历 即从某一个顶点开始访问 访问后将该 顶点去除得到若干子图 对每个子图再依次进行深度优先遍历 对图作广度优先遍历 类似于树的逐层遍历 即先从某一个顶点开始访问 然后访问 与该顶点相邻接且未被访问过的顶点集 V1 G 再访问与 V1 G 中顶点相邻接且未被访 问过的顶点集 V2 G 重复该过程直至与初始顶点连通的所有顶点都被访问完 对于 非连通图或非强连通图 还要从某一个未被访问的顶点开始重复上一过程 直至所有 顶点访问完毕 获取顶点数目 获取图中所包含的顶点的数目 获取边的数目 获取图中所包含的边的数目 获取与指定顶点相关联的第一条边 对无向图 获取到与指定顶点相关联的第一条边 对有向图 获取到以指定顶点作为弧尾的第一条弧 不同表示方法获取到的结果会有 所不同 邻接矩阵法按顶点编号顺序 邻接压缩表和邻接链表按边的添加顺序 获取与指定边有相同关联顶点的下一条边 对无向图 获取到与指定边 nV1 nV2 有 相同关联顶点 nV1 的下一条边 对有向图 获取到与指定弧有相同弧尾 nV1 的下一条弧 不同表示方法获取到的结果会有所不同 邻接矩阵法按顶点编号顺 序 邻接压缩表和邻接链表按边的添加顺序 添加一个顶点 向图中添加一个新顶点 添加一条边 对无向图 向图中添加一条新边 对有向图 向图中添加一条新弧 获取一个顶点中存储的数据 根据顶点编号获取该顶点中存储的数据 判断一条边是否存在 对无向图 判断两个顶点 nV1 和 nV2 之间是否存在边 对有向 图 判断是否存在从顶点 nV1 到顶点 nV2 的弧 设置一条边的权 对无向图 设置指定边 nV1 nV2 上的权 对有向图 设置指定弧 上的权 获取一条边的权 对无向图 获取指定边 nV1 nV2 上的权 对有向图 获取指定弧 上的权 5 请简述图的三种常用表示方法 邻接矩阵法 用矩阵来表示各顶点之间的连接关系 对于有 n 个顶点的图 G V E 其邻接矩阵 A 为 n n 的方阵 元素 A i j 0 i j n 定义为 i j w jiA 对无向图存在 GEvvGEvv jiji 对有向图存在 反之 其中 w ij 为边 v i vj 或上的权 邻接压缩表 邻接矩阵的一种压缩表示形式 使用 3 个顺序表来表示图中顶点之间的 连接关系和权 设图中共有 n 个顶点 v 0 v1 vn 1 3 个顺序表分别为 s w 和 h 在 s 中 依次记录与顶点 vi i 0 1 n 1 相关联的顶点 在 w 中依次记录 s 中存储的各条边的 权 在 h 中依次记录与顶点 vi 相关联的顶点在 s 中的起始存储位置 邻接链表 图的一种链式存储结构 每个顶点中设置一个指向链表头的指针 在链表 中保存与该顶点相邻接的顶点信息 包括顶点位置及两个顶点形成的边的权 6 请简述图的两种常用遍历方法及每一种遍历方法中结点的访问顺序 广度优先遍历 类似于树的逐层遍历 即先从某一个顶点开始访问 然后访问与该顶 点相邻接且未被访问过的顶点集 V1 G 再访问与 V1 G 中顶点相邻接且未被访问过的顶点 集 V2 G 重复该过程直至与初始顶点连通的所有顶点都被访问完 对于非连通图或非强 连通图 还要从某一个未被访问的顶点开始重复上一过程 直至所有顶点访问完毕 深度优先遍历 类似于树的先序遍历 即从某一个顶点开始访问 访问后将该顶点去 除得到若干子图 对每个子图再依次进行深度优先遍历 7 请列举最小生成树和最短路径可以用于解决什么应用问题 请参考例 6 1 和例 6 2 8 请简述 Prim 算法的作用和具体步骤 Prim 算法用于最小生成树问题求解 对于有 n 个顶点的图 G V E Prim 算法从空树 T 开始 按照以下规则将 n 个顶点和 n 1 条边依次添加到树中 形成最小生成树 a 从某一顶点 v0 开始 将该顶点作为树的根结点加入到 T 中 使得 T 中的数据元 素集合 D v0 数据元素关系集合 R b 对于一个顶点在集合 D 中 另一个顶点在集合 V D 中的那些边 找出权最小的 一条边 将该边在集合 V D 中的顶点 vi i 1 2 n 1 加入到集合 D 中 并将顶点间关系 jD vj vi D vi vk 则表明路径 vj vi vk 的长度更短 此时令 D vj vk D vj vi D vi vk 并 更新从顶点 vj 到顶点 vk 的路径 第 7 章 排序算法 1 请简述排序的作用 排序的作用是将一个待排序元素集合按关键字递增 或递减 顺序整理为一个有序序 列 2 请简述稳定排序和不稳定排序的含义 若采用某种排序算法对任一组元素进行排序 在排序前后 那些具有相同关键字值的 元素之间的相对次序都保持不变 则将这种排序算法称为是稳定的 否则称为是不稳定的 3 请简述各种排序算法的适用范围 排序算法的适用范围如下 a 直接插入排序 简单选择排序和冒泡排序都是简单排序算法 它们的时间复杂度 和空间复杂度分别为 O n2 和 O 1 若待排序元素数量 n 较小 可以选用直接插入排序和 冒泡排序 另外 当待排序元素基本有序时 也应选用直接插入排序和冒泡排序 此时时 间复杂度都能达到 O n 若元素本身数据量较大 元素移动操作代价较高 则应选用平均 移动元素次数最少的简单选择排序 希尔排序是对直接插入排序算法的改进 大大降低了 时间复杂度 但它是一种不稳定的排序算法 b 堆排序 快速排序和归并排序主要适用于待排序元素数量 n 较大的情况 当待排 序元素数量 n 较小时 它们的性能有可能劣于简单排序算法 因此 在实际应用时 快速 排序算法和归并排序算法经常与简单排序算法结合使用 例如 可以先用快速排序算法将 集合划分为规模更小的子集合 对于元素数量较小的子集合 则用直接插入排序算法进行 排序 在所有平均时间复杂度为 O nlog2n 的算法中 尽管快速排序在最坏情况下时间复 杂度较高 但它通常被认为是平均性能最好的一种算法 并且通过优化可以降低最坏情况 出现的概率 归并排序是一种稳定的排序算法 其时间性能一般要优于堆排序 但它所需 要的辅助空间较多 当应用环境要求排序前后具有相同值的元素相对次序不能改变时可以 考虑使用 堆排序所需的辅助空间最少 当可用空间非常有限时可以考虑使用 c 箱排序和基数排序的时间复杂度最低 但它们的空间复杂度最高 箱排序主要适 用于待排序元素长度 即 d 值 较小的情况 在实际中应用不多 基数排序是箱排序的改 进 主要适用于整数或字符串的排序 或者与其他排序算法结合进行实数的排序 例如 可以先用基数排序算法按整数部分将元素分成若干个子集合 再对每个子集合应用直接插 入排序算法进行排序 5 请简述插入排序 选择排序 交换排序 归并排序和分配排序的原理 插入排序 按关键字大小每次将一个待排序的元素插入到已排序的序列中 直至所有 元素都插入完毕 选择排序 每次从待排序的元素中选择具有最小 或最大 关键字的元素放到已排序 序列的尾部 或头部 直至所有元素都排序完毕 交换排序 从待排序的元素中选择两个次序相反的元素进行交换 直至任意两个元素 的次序都正确 K 路归并排序 每次将 K K 2 个已排序的子序列组合在一起 形成一个有序的序 列 重复该过程直至得到一个包含所有待排序元素的有序序列 分配排序 根据元素本身所具有的值将各元素逐一映射到一组有序空间中 最后再依 次从有序空间中将各元素取出即形成了排序结果 5 请简述直接插入排序的具体步骤 直接插入排序是一种简单排序算法 其具体步骤为 a 初始已排序区为空 将第一个待排序的元素插入到已排序区中 b 将后继每一个待排序的元素依次取出 并按照关键字大小将其插入到已排序区中 的适当位置 使该序列仍然有序 c 重复上一步骤直至将待排序的元素都插入到已排序序列中 6 请简述希尔排序的具体步骤 希尔排序 又称为 缩小增量排序 其具体步骤为 a 令 n 为待排序元素数目 设置增量序列 d 0 d1 dk 其中 n d0 d1 dk 1 b 按增量 di i 依次取值为 0 1 k 将待排序元素分为 di 组 将所有下标距离为 di 的倍数的元素放在同一组中 即 R 1 R 1 di R 1 2 di 在第一组中 R 2 R 2 di R 2 2 di 在第二组中 依此类推 然后分别在各组内进行直接插入排序 c 重复上一步骤直至最后以 1 为增量对所有待排序元素进行直接插入排序 7 请简述简单选择排序的具体步骤 简单选择排序是一种简单排序算法 其具体步骤为 a 初始已排序区为空 待排序区包含所有待排序元素 b 从待排序区中选择具有最小关键字的元素 将其与待排序区的第一个元素交换位 置 并将该位置加到已排序区中 c 重复上一步骤直至所有元素都排序完毕 8 请简述堆的定义和堆的构建过程 堆的定义 对于包含 n 个元素的集合 R R 1 R 2 R n 若满足 1 R i R 2 i 且 R i R 2 i 1 即 R 所表示的完全二叉树中每一棵子树的根结点的 值均不大于其孩子结点的值 2 或 R i R 2 i 且 R i R 2 i 1 即 R 所表示的完全二叉树中每一棵子树的根结 点的值均不小于其孩子结点的值 则称集合 R 为堆 若满足前一个条件则称 R 为小根堆 满足后一个条件则称 R 为大根 堆 堆的构建过程 堆一般采用自底向上的构建方法 即在将以某一结点为根结点的二叉树构建成堆之前 先将其左子树和右子树构建成堆 以叶子结点为根的子树必然是堆 因此 对于由 n 个元 素构成的完全二叉树 其对应的堆的构建过程从 R n 2 作为根结点的子树开始 依次对 R n 2 1 R n 2 2 R 1 作为根结点的树进行堆的构建 在将一棵 R i 作为根结点的子树整理为堆时 只有根结点不满足堆的条件 因此 需 将根结点与后继层中的结点依次比较并不断将根结点下移直至该子树满足堆的条件 这里 以大根堆构建为例介绍其具体过程 a 若 R i 存在左孩子 R 2 i 则令 j 2 i 若 R i 存在右孩子 R 2 i 1 且 R 2 i 1 R 2 i 则令 j 2 i 1 将 R j 与 R i 比较 若 R i 较小 则将 R i 和 R j 交换 并令 i j b 重复上述步骤直至 R i 无孩子结点或 R i 比其孩子结点都大 此时该子树即为堆 9 请简述堆排序的具体步骤 堆排序的具体过程 a 采用自底向上的方法将包含 n 个元素的待排序集合 R R 1 R 2 R n 整理 为大根堆 其元素数目 i n 初始时已排序集合 R 为空集 b 将 R 1 与 R i 交换 并将 i 算作已排序集合中的元素位置 更新待排序集合中最 后一个元素的位置 i i 1 此时待排序集合 R R 1 R 2 R i 已排序集合 R R i 1 R i 2 R n 显然 待排序集合 R R 1 R 2 R i 中只有根结点 R 1 不满足大根 堆的条件 通过下移 R 1 重新将 R 整理为大根堆 c 重复上一步骤直至待排序集合 R R 1 此时直接将 R 1 作为已排序集合 R 中 的元素 堆排序过程结束 10 请简述冒泡排序的具体步骤 冒泡排序是一种简单排序算法 其具体步骤为 a 初始已排序区为空 待排序区包含所有待排序元素 b 在一轮排序中 对待排序区所有相邻元素从前至后进行两两比较 若相邻两个元 素次序相反 即前一个元素的关键字值大于后一个元素的关键字值 则交换它们的位置 每轮排序后 待排序区中的最大元素会移到待排序区的尾部 将待排序区的最后一个元素 放到已排序区的头部 c 重复上一步骤直至待排序区中只剩下一个元素或者在一轮排序中没有出现相邻元 素交换的情况 此时直接将待排序区中的所有元素按原次序放到已排序区的头部 冒泡排 序结束 11 请简述快速排序中划分的含义和过程 划分的含义 划分是以指定元素 x 为基准将一个集合 R 分为两个子集 R1 和 R2 其中 R1 中的元素都 小于或等于 x R 2 中的元素都大于或等于 x 划分的过程 对于包含 high low 1 个元素的待排序集合 R R low R low 1 R high 以 R k low k high 为基准对其进