计算机专业考研必备数据结构考研要点解析ppt课件.ppt

1 数据结构考研要点解析 数据结构辅导 2 数据结构考研要点解析 概述第一章知识点第二章知识点第三章知识点第四章知识点第五章知识点第六章知识点 3 考试的要求 研究生考试主要从两个方面进行考查 知识和技能 知识方面从数据结构的结构定义和使用 以及存储表示和操作的实现两个层次 系统地考查 掌握常用的基本数据结构 包括顺序表 链接表 栈与队列 数组 二叉树 堆 树与森林 图 查找结构 索引结构 散列结构 及其不同的实现 4 2 掌握分析 比较和选择不同数据结构 不同存储结构 不同算法的原则和方法 技能方面系统地掌握基本数据结构的设计方法 掌握选择结构的方法和算法设计的思考方式及技巧 提高分析问题和解决问题的能力 5 复习的纲领 数据结构课程是计算机专业的专业基础课程 为业界做系统开发提供了不可或缺的技术和知识 是计算机专业考研的重头科目 数据结构课程复习有几点重要的体会提供给大家参考 注重概念抓住特点学会算法拓展应用 6 注重概念从考研情况分析 试题涉及的内容都很基本 没有很深很难的内容 所以要重视概念的复习 牢记定义 结构定义有规范写出的 有言外隐藏的和引伸的概念 注意传承 某些结构与其他结构间有传承关系 有变种关系 区分层次 分清逻辑的和物理的结构 以及它们之间的关系 挖掘细节 细节可提供更多解题的知识 7 抓住特点每种结构有它的特点和用途 这对于在解题中应使用哪种结构 who 在何时 when 何种场合 where 使用 以及如何 how 使用有重要作用 理解结构的行为特征 明确每种结构的行为特征 例如栈是先进后出 队列是先进先出的 可帮助在解题时作出选择 理解结构的应用背景 知道每种结构常在什么场合做什么用 可适时作出适当选择 理解结构的声明方式 在适当时机合理地定义它们 可减少算法逻辑的混乱 8 学会算法包括结构必要操作 初始化 建立 销毁 遍历 插入 删除 的实现和常用算法 查找 排序 算法设计 迭代 递归 分治 回溯 的设计与分析 基本数据结构的实现方式 主要是数据结构的存储方式定义和相应操作的程序实现 常用算法的设计 包括设计的三阶段 基本思想 算法框架 程序实现 算法的简单分析 掌握时间复杂性的分析技能和附加存储空间的计算 9 拓展应用每种结构都有许多应用场合 有不同应用目的和应用方式 每种算法也可变通以适用于不同的问题求解 明确问题求解的步骤 掌握问题求解的三阶段 分析 弄懂题意 设计 考虑解决方案 实现 算法设计与分析 坚持算法设计与分析的步骤 算法设计三阶段 基本思想 算法框架 程序实现 结构和算法的不同应用 这是最繁杂 范围最广的部分 通过多练习达到熟练应用 10 复习的范围 根据2009年考试分析和历年考试经验 可以对今后考试作一个简单评估 单项选择题覆盖了考试大纲涉及的所有各章 主要考查对各个数据结构的定义和特点的理解 以及相应延伸的概念 综合应用题分为两个部分 算法分析题和算法设计题 编程题 主要考查分析问题和解决问题的能力 算法分析题的重点在图 查找 排序部分 算法设计题的重点在线性表 树与二叉树 查找和排序部分 11 为在有限的时间内复习好这门课程 应当注意以下几点 注意复习用C C Java语言编写小程序时的语法规则和方法 为算法分析和算法设计题的求解打下基础 函数定义和参数使用 算法一般以函数形式给出 函数编写需要注意的问题包括函数类型 函数参数传递 函数返回值类型等 以及传值参数和引用参数在使用上的区别 函数中局部变量的作用域 特别注意在函数中对局部变量的任何改变 在函数外不能使用 12 算法设计所用数据结构的自定义 算法设计时不能忽视所用数据结构的声明 2009年考试42题有关链表的题 在答案中不写链表结点定义是扣了分的 C C 中的动态存储分配和回收方式 涉及链表结构的地方都可能有动态存储分配和回收操作 要掌握正确使用相关语句的方法 在C C 中输入 输出文件的定义和使用 特别注意正确使用文件的打开 关闭 读入 写出操作的使用 在复习数据结构时 要注意知识体系 13 数据结构课程中的知识本身具有良好的结构性 有些结构面向应用 有些结构面向实现 在复习时要注意这两个层次以及它们之间的联系 注意循序渐进在复习数据结构时 首先需要复习数据结构的定义和特点 数据结构的使用范围 再复习各种操作的实现 在阅读算法之前 要先弄清其基本设计思想 基本步骤 并通过事例学习了解每个算法的处理流程以加深理解 最后再阅读程序代码 14 注意比较在复习中应当注意从 横向 和 纵向 进行对比以加深理解 纵向对比将一种结构与它的各种不同的实现加以比较 理解不同实现方式的优点和问题 如二叉树的顺序和链表实现 横向对比是对属于同一类逻辑结构的不同数据结构 如线性表 栈 队列 加以比较 对具有相同功能的不同算法进行比较等 了解数据结构与算法实现间的关系 15 注意练习只看书不做题 不能真正学会有关知识 不能达到技能培养的目的 做题是自我检查的重要手段 在做算法设计类型的习题时 应考虑数据结构的定义 提高算法设计的能力 编写算法的题可能是学生比较棘手的问题 特别是在考试这样一个氛围 时间又短促 想编出一个好算法不太容易 16 一个建议是首先仔细阅读试题题目 了解它到底要你干什么 然后用一个简单的例子走一下 总结每一步向下走可用什么语句实现 再做归纳 整理出处理流程 按照结构化程序设计的方法 搭建框架 再根据例子填入细节 在设计一个算法时 要考虑问题解决方案的多样性 算法的适用性 问题对算法选择的限制 选择合适的数据结构 设计有效的算法 17 本章 线性表 的知识点有5个 线性表的定义和特点 由数据元素组成 惟一直接前驱与后继 线性表的基本操作 查找 定位 遍历 插入 删除 线性表的存储表示 顺序存储 链表存储 循环链表和双向链表 定义和基本运算 线性表的应用 掌握使用线性表基本操作实现应用算法 第一章知识点解析 18 线性表的定义和特点 问题1 如果一个元素集合中每个元素都有1个且仅有1个直接前驱和1个直接后继 它是线性表吗 解析 答案 否 该元素集合是一个回路 环 引伸 循环链表是一个 环 它符合线性表的定义吗 问题的关键是 线性表是逻辑结构 线性表和非线性表是从逻辑上划分的 而循环链表是存储结构 是线性表的一种特殊的表示 是线性链表的一种扩展 它在形态上有线性的特征 在行为上有线性表的循序访问的特点 19 问题2 如果一个元素集合有一个元素仅有1个直接后继而没有直接前驱 另一个元素仅有1个直接前驱而没有直接后继 其他每个元素都仅有1个直接前驱和1个直接后继 但其中各个元素可能数据类型不同 该元素集合是线性表吗 解析 答案 是 它符合线性表的定义和特性 只要把元素定义为Union类型即可 因为线性表的定义只规定了元素间的关系及每个表元素是原子类型 并未规定每个表元素的类型必须相同 Union是一种等价类型 它允许不同类型数据共享同一存储空间 可保证每个表元素所占空间相同 20 线性表的基本操作 问题3 我们可以为线性表定义查找 插入 删除等操作吗 它们如何实现 解析 可以为线性表定义这些操作 也可以在程序中直接使用这些操作 但它们的实现与线性表选用何种存储结构有关 在定义了线性表的存储表示之后 必须为相关操作定义它们的实现代码 具体的线性表实例一定与某一存储表示相联系 因此 要使用相应的基于该存储结构实现的操作 21 线性表的存储表示 问题4 线性表的顺序存储表示是一维数组吗 解析 答案 否 应是顺序表 其区别在顺序表中元素是相继连续存放的 而一维数组只能有两个操作 按下标存 按下标取 它不一定是相继存放 不适宜存储顺序的 连续的序列元素 问题5 想要以O 1 的时间代价存取第i个表元素 线性表应采用顺序表还是单链表 解析 顺序表 因为单链表只能顺序地逐个访问 顺序表可以直接访问第i个元素 22 问题6 为了统一空链表和非空链表的操作 简化链表的插入删除操作 需要给链表增加点什么 解析 增加表头结点 问题7 在何种场合选用顺序表 链表呢 解析 从时间角度来看 需要经常查看不需经常增删的场合使用顺序表 因它可直接存取 但增删要大量移动存储块 反之 选择链表 因它在增删元素时不需移动存储 修改指针即可 但只能顺序访问 存取速度慢 从空间角度来看 顺序表存储密度 有效存储 总存储 高 空间利用率好 链表存储密度较低 空间利用率差一些 23 循环链表和双向链表 问题8 想要以O 1 的时间代价把两个链表连接起来可采用何种链表结构 解析 循环链表 若设两个循环链表头指针为p和q 用r p link p link q link q link r 即可把这两个连接起来 p q 24 问题9 想要判断一个带表头结点的循环链表L是否为空 应采用何种语句 解析 L link L 空表还需保留一个表头结点 它的下一个结点还是它自己 问题10 想要以O 1 的时间代价访问第i个表元素的直接前驱和 或直接后继 应采用何种链表结构 解析 双向链表 只要事先定位于该表结点 通过该结点的前驱指针和后继指针 直接能够找到该元素的直接前驱或直接后继 25 第二章知识点解析 本章 栈 队列与数组 的知识点有8个 栈和队列的定义及其特点栈的存储表示及其基本运算的实现队列的存储表示及其基本运算的实现栈的应用队列的应用多维数组特殊矩阵稀疏矩阵 26 栈和队列的定义及其特点 问题1 元素1 2 3 4依次进栈 可能的出栈序列有多少种 队列呢 解析 用catalan函数计算有8 4 4 5 14种 用队列是1种 因栈有FILO 队列有FIFO特性 问题2 当元素以A B C D E顺序进栈 D B C E A是可能的出栈顺序吗 解析 否 因序列的进出栈顺序为IAIBICIDOD 当D出栈后 栈顶为C 不能让B先出来 所以D B C E A不是可能的出栈顺序 27 问题3 可否用两个栈模拟一个队列 反过来呢 解析 可以 一个栈把全部数据反过来 另一个栈再把这些数据反过去即可 而队列不能 问题4 栈 队列对线性表加了什么限制 解析 限制了存取位置 栈要求只能在表的一端 栈顶 访问 插入和删除 队列要求只能在表的一端 队尾 插入 在另一端 队头 访问和删除 不能在表的中间做上述运算 这决定了在栈和队列上只能顺序访问 不能直接存取 无论采用何种存储表示 这表现了它们优秀的 结构化 特性 28 栈的存储表示及其基本运算的实现 问题5 当栈空时顺序栈的栈顶指针top 1 当栈非空时top是否指示最后元素加入的位置 解析 是 每当新元素进栈时让栈顶指针top先加1 再按top指示位置把新元素加入 所以栈非空时栈顶指针总是指示最后加入元素的位置 问题6 顺序栈的进栈 出栈的先决条件是什么 解析 进栈的先决条件是栈未满 栈满再进栈就会产生溢出 出栈的先决条件是栈不空 栈空再退栈可报告操作失败 29 问题7 当两个栈共享同一个存储空间V m 时 可设栈顶指针数组t 2 和栈底指针数组b 2 如果进栈采用两个栈相向前行的方式 则任一栈的栈满条件是什么 解析 t 0 1 t 1 设0号栈正向进栈 1号栈反向进栈 t 0 与t 1 碰头即栈满 问题8 链式栈的栈顶指针是指在链头还是链尾 解析 链头 链式栈一般采用单链表 栈顶指针即为链头指针 进栈出栈均在链头进行 每次都要修改栈顶指针 链空即栈空 top NULL 30 问题9 链式栈只能顺序存取 而顺序栈不但能顺序存取 还能直接存取 这话对吗 解析 不对 顺序栈不能直接存取 问题10 理论上链式栈没有栈满问题 但在进栈操作实现时 还要判断一个先决条件 是何条件 解析 每创建新的栈结点时还要判断是否动态分配成功 若不成功则进栈操作失败 StackNode s newStackNode if s NULL cerr 结点存储分配失败 endl exit 0 31 队列的存储表示及其基本运算的实现 问题11 当用牺牲一个单元的方式组织循环队列时 队空和队满的条件是什么 进队 出队的策略是什么 解析 队空条件 Q front Q rear 队满条件 Q rear 1 maxSize Q front 进队 Q rear Q rear 1 m Q elem Q rear x 出队 x Q elem Q front Q front Q front 1 m 32 问题12 当用队头指针front和长度length组织循环队列时 队空和队满的条件是什么 进队和出队的策略是什么 设表长度为m 解析 队空条件 Q length 0 队满条件 Q length maxSize 进队 Q elem Q front Q length m x Q length 出队 Q length x Q elem Q front Q length m 问题13 链式队列的队头和队尾在链表的什么地方 33 解析 链式队列的队头在链头 队尾在链尾 问题14 链式队列的队空条件是什么 解析 队空条件Q front NULL 因队头指针为空则说明链表为空 用 Q front Q rear 是不对的 问题15 同时使用多个队列时需采用何种队列结构 如何组织 解析 采用多个链式队列 并设置队头指针数组fr n 和队尾指针数组re n 分别指示各队列的队头和链尾 其中n是队列个数 34 问题16 链式队列的每个结点是否还可是队列 解析 可以 如果每个结点是顺序 循环 队列则是简单的情形 如果每个结点又链接出一个链式队列 则出现 表中套表 是广义表了 例题17 当一个循环队列已满 如何才能扩充队列长度 使得客户程序能够继续使用这个队列 解析 用指针动态定义存放队列元素的数组 当队列已满时 可创建一个更大的同类型的新数组 把队列元素全部复制到新数组 然后修改队列指针 释放老数组 注意区分Q rear Q front和Q front Q rear的情形 35 栈的应用 问题18 在后缀表达式求值过程中用栈存放什么 在中缀表达式求值过程中又用栈存放什么 解析 后缀表达式求值时用栈存放操作数或运算结果 中缀表达式求值时用OPND栈存放操作数或运算结果 用OPTR栈存放操作符 问题19 在递归算法中采用何种结构来存放递归过程每层的局部变量 返回地址和实参副本 解析 栈 因递归调用时需为每层分配 在退出时逐层释放 这正是后进先出的机制 可用栈来组织 36 问题20 为判断表达式中的括号是否配对 可采用何种结构辅助进行判断 解析 栈 扫描表达式 每当遇到左括号进栈 遇到右括号再判断栈顶所存括号是否配对 确定是否有错 问题21 在回溯法中采用何种结构来记录回退路径 解析 栈 在沿某条路径前进时用栈记下回退路径以便回溯之用 比在路径上各个结点中增加访问标识更方便 例如图的深度优先搜索 采用在每个边结点中增加标志域的非递归算法比用栈的递归算法更复杂 37 问题22 若进栈序列为1 2 3 4 5 6 出栈序列为2 4 3 6 5 1 问栈容量至少多大 解析 3 可实验画图得出 问题23 常用的一种链式栈是基于静态链表的 用一个整数数组S n 存放链接指针 游标 设初始时top 1 表示栈空 则其进栈 出栈 判栈空等操作如何实现 解析 判栈空 top 1 设表中第k个元素进栈 S k top top k 设出栈元素是第k个元素 k top top S top 38 队列的应用 问题24 在逐层处理一个分层结构的数据时 需采用何种辅助结构来组织数据 解析 队列 在从队列中退出当前层元素 头 时把相关下层元素进队 尾 在当前层元素处理完后下一层元素已经在队头了 问题25 为实现输入 处理 输出并行操作需建立多个输入缓冲区队列 这些队列是按数组方式组织的还是按链表方式组织的 解析 按链表方式组织的 各个队列的增长速度不一 按链表组织可以自由增长 39 问题26 在操作系统中一种进程调度策略是先来先服务 为此使用了何种辅助结构 解析 队列 其特性是先进先出 问题27 在对一个无序单链表进行排序时 可先把链表截出一段段有序的子链表 再对它们做两路归并排序 为此定义队列来辅助排序 此队列的元素的数据类型是什么 解析 链表结点指针 存放各有序子链表的头指针 每次从队列中退出两个子链表的头指针 归并后把结果子链表的头指针进队列 如此重复 直到队列中只剩下一个链表指针为止 40 多维数组 问题28 二维数组可以视为数组元素为一维数组的一维数组 因此二维数组是线性结构吗 解析 否 二维数组是一维数组的扩展 每个元素最多有两个直接前驱和两个直接后继 不符合线性表的特性 问题29 二维数组每个元素的存取时间都相同吗 解析 是 按照下标确定每个元素存储地址的计算时间都相同 按地址存取任一元素的时间也相同 41 问题30 数组是逻辑结构还是物理结构 解析 既是逻辑结构也是物理结构 问题31 动态数组用指针来定义 假定数组指针为a 可否用 a取出数组元素的值 可否用a 进到下一数组元素 解析 可以 这是C C 语法文本明确定义的 例如 定义inta 5 1 3 5 7 9 int data a 有int elem newint 5 while data 0 elem data elem data for intk 0 k n k cout elem k 42 问题32 链表也是动态结构 假定链表指针为 a 可否用 a取出链表结点的值 可否用a 进到下一链表结点 解析 不可以 因为a所指结点有两个域 a不能取出结点内的数据 只能用a data取出结点数据 同样不能用a 进到下一结点 因为a 是进到物理上的下一个结点 而链表中逻辑上的下一个不见得是物理上的下一个 所以要进到逻辑上的下一个 只能用a a link 43 特殊矩阵 问题33 如果用下三角压缩存储对称矩阵 B 0 存放A 0 0 如何存取A i j 解析 当i j时 A i j 在B 中的位置是i i 1 2 j 当i j时 A i j 在B 中不存在 问题34 两个对称矩阵相加 结果矩阵还对称吗 两个对称矩阵相乘 结果矩阵还对称吗 解析 两个对称矩阵相加的结果矩阵是对称矩阵 相乘的结果矩阵一般不对称 除非二个对称矩阵是相同的 44 问题35 两个三对角矩阵相加 结果矩阵还是三对角矩阵吗 相乘的情况又如何 解析 相加的结果矩阵还是三对角矩阵 相乘的结果矩阵一般不是 45 稀疏矩阵 问题36 三对角矩阵是否稀疏矩阵 解析 否 三对角矩阵也有大量零元素 但其分布有规律 不符合稀疏矩阵定义 问题37 两个稀疏矩阵相加 结果矩阵还是稀疏矩阵吗 两个稀疏矩阵相乘 结果矩阵又如何 解析 相加的结果矩阵不一定是稀疏矩阵 相乘的结果矩阵肯定不是稀疏矩阵 问题38 用三元组表存储稀疏矩阵的非零元素 是否失去了直接存取的特性 如何改进 46 解析 是 原稀疏矩阵的元素可通过行列下标直接存取 而三元组表只能顺序存取 改进的方法是采用带行指针的二元组表 可以直接找到某行 且消除了三元组表中冗余的行号 在二元组表内搜索某列元素还需顺序查找 但个数少得多 47 第三章知识点解析 本章 树与二叉树 的知识点有10个 树与二叉树的定义和性质二叉树的存储结构二叉树的遍历线索二叉树树与森林二叉树的应用 二叉排序树 平衡二叉树 并查集 Huffman树 堆 48 树与二叉树的定义和性质 问题1 二叉树是树吗 解析 否 树的定义是从图来的 要求结点至少有1个 二叉树则可以是空树 另外二叉树必为有序树 树可有序 也可无序 问题2 树的叶结点无子女 是否可称它无子树 解析 是 树的定义是递归的 递归结束于只有一个结点的树 问题3 二叉树的叶结点无子女 它是否无子树 解析 否 二叉树的定义是递归的 递归到空树为止 所以结点无子女 应称它子树为空 49 问题4 树和二叉树的高度与深度如何理解 解析 树的高度与深度的值相等 但树中某个结点的高度与深度的值可能不同 深度是从上向下计算的 高度是从下向上计算的 问题5 一棵二叉树有1024个结点 其中465个是叶结点 那么树中度为2和度为1的结点各有多少 解析 由n0 n2 1的性质 度为2的结点有465 1 464个 度为1的结点有1024 465 464 95个 问题6 计算深度的公式 log2 n 1 是针对何种二叉树的 解析 针对完全二叉树 但对理想平衡树也可用 50 问题7 二叉树求深度的公式 log2 n 1 与 log2n 1有何不同 解析 推导有些差异 都可计算二叉树深度 只不过后者对于n 0不适用 问题8 完全二叉树有何用处 解析 后续讨论可知 堆 胜者树 败者树等都按完全二叉树组织 何况完全二叉树最省存储 问题9 n0 n2 1公式有何用途 解析 对于完全二叉树最有用 例如组织对抗赛可用胜者树 已知选手有n个人 取n0 n 直接可求得比赛场次n2 n0 1 是否有人轮空 51 二叉树的存储 问题10 顺序存储适用于何种二叉树 解析 适用于完全二叉树 可充分利用存储 并可方便地找到某结点的双亲 兄弟和子女 问题11 完全二叉树的结点从1开始编号和从0开始编号有何不同 解析 C C 与Pascal不同 数组下标从0开始 完全二叉树从0开始编号是合理的 这时某结点i的双亲是 i 1 2 左子女是2i 1 右子女是2i 2 完全二叉树结点从1开始编号是传承了Pascal的做法 52 问题12 通常使用二叉链表存储二叉树 为何还选用三叉链表 解析 使用二叉链表找某结点的左子女和右子女比较方便 找双亲比较麻烦 三叉链表每个结点增设一个父指针 可方便地找双亲 当然 如果结点数n很大 不如使用二叉链表加一个栈 用栈也可记忆结点的双亲 所需空间仅O log2n 问题13 使用二叉链表存储有n个结点的二叉树 空的指针域有多少 解析 n个结点的二叉树有2n个指针域 其中n 1个指针域被使用 有n 1个空指针域 53 二叉树的遍历 问题14 已知二叉树的前序序列abdcef 中序序列dbaecf 其后序序列是什么 解析 由二叉树的前序序列和中序序列可唯一确定此二叉树 根据问题要求构造出的二叉树如右图 后序序列为dbefca 问题15 前序序列与中序序列相同的是什么二叉树 解析 要求VLR LVR 应是左子树均为空的单支树 或空树 54 问题16 前序序列与后序序列相同的是什么二叉树 解析 要求VLR LRV 应是只有根结点的二叉树或空树 问题17 前序序列与层次序序列相同的又是什么二叉树 解析 应是右子树均为空的单支树 或左子树均为空的单支树 或空树 问题18 后序序列与层次序序列相同的是何二叉树 解析 只有根结点的二叉树或空树 55 问题19 前序序列与中序序列正好相反的是什么二叉树 解析 要求VLR与LVR相反 即 当右子树均为空时 或空树时满足要求 问题20 前序序列与后序序列正好相反的是什么二叉树 解析 要求VLR与LRV相反 即 当右子树都空时 或左子树都空时 或空树时满足要求 56 问题21 一棵二叉树的前序序列的最后一个结点是否是它中序序列的最后一个结点 解析 不一定是 右图即反例 二叉树前序序列abdce 中序序列dbaec 问题22 一棵二叉树的前序序列的最后一个结点是否是它层次序序列的最后一个结点 解析 是 问题23 一棵有n个结点的二叉树的前序序列固定 可能的不同二叉树有多少种 解析 用catalan函数求 57 问题24 二叉树的前序 中序 后序遍历所走的路线都相同 只是访问时机不同 这种说法对吗 解析 对 从给出的二叉树的前序 中序 后序的递归遍历算法就可以清楚看到 问题25 二叉树的层次序遍历是按二叉树层次进行逐层访问 其遍历算法需要使用何种辅助结构 解析 队列 使用队列 在逐层访问过程中一旦当前层次的结点出队进行处理 就需把它下一层的结点进队列 当当前层的结点全部退出队列并处理完后下一层结点已经在队头了 58 线索二叉树 问题26 如何构造一棵中序线索二叉树 解析 通过中序遍历 把二叉树改造为中序线索二叉树voidcrt inthtree ThreadNode p ThreadNode 59 pre p crt inthtree p right pre 在主程序中pre NULL crt inthtree root pre pre right NULL pre rtag 1 问题27 如何在一棵中序线索二叉树中寻找某结点p为根的子树上的中序第一个结点 解析 沿结点p的左子树链一直走下去 直到遇到其左指针为左线索的结点为止 该结点即所求 60 ThreadNode inFirst ThreadNode p ThreadNode q p while q 61 returnq 问题29 如何在一棵中序线索二叉树中寻找某结点p的中序下的后继 解析 若结点p有右线索 则其右线索所指结点即为其中序后继 若无右线索 则其右子树中中序第一个结点即为它的中序后继 ThreadNode inNext ThreadNode p ThreadNode q p right if q 62 问题30 如何在一棵中序线索二叉树中寻找某结点p的中序下的前驱 解析 镜像情况 若结点p有左线索 则其左线索所指结点即为其中序前驱 若无左线索 则其左子树中中序最后一个结点即为它的中序前驱 ThreadNode inPrior ThreadNode p ThreadNode q p left if q 63 问题31 如何在一棵中序线索二叉树中寻找某结点p的前序下的后继 解析 右图二叉树前序遍历的结果是abdgcef 分析这个事例可知 a有左子女b a的前序后继为b d无左子女但有右子女g d的前序后继是g g既无左子女又无右子女 g的前序后继为c c可从g沿右线索链到a a的右子女即为g的前序后继 64 ThreadNode preNext ThreadNode p ThreadNode q if p ltag q p left elseif p rtag q p right else q p while q 65 问题32 如何在一棵中序线索二叉树中寻找某结点p的前序下的前驱 解析 右图二叉树前序遍历的结果是abdgcef 为寻找p的前驱 需找p的双亲q 确定双亲原则 若p是q的左子女 则q是p右子树中序最后一个结点的右线索 若p是q的右子女 则q是p左子树中序第一个结点的左线索 ThreadNode inParent ThreadNode p if p 66 ThreadNode q inLast p right if q returnq right else q inFirst p left if q returnq left returnNULL 找到b的双亲a后 判断 若b是a的左子女 则b的前序前驱是a 否则若c是a的右子女 则c的前序前驱是 67 a a的左子树空 或a的左子树 非空 前序最后一个结点 ThreadNode prePrior ThreadNode p ThreadNode q inParent p if p q left returnq p是q的左子女if q left returnq p是q的右子女while q ltag q rtag while q rtag q q right while q ltag q q left returnq 68 问题33 如何构造一棵前序线索二叉树 解析 类似于构造中序线索二叉树 可通过前序遍历 把二叉树改造为前序线索二叉树 voidcrt prethtree ThreadNode p ThreadNode 69 crt prethtree p right pre 在主程序中pre NULL crt prethtree root pre pre right NULL pre rtag 1 问题34 如何在一棵前序线索二叉树中寻找某结点p为根的子树上的前序第一个结点 解析 以结点p为根的子树上前序的第一个结点就是它自己 70 ThreadNode preFirst ThreadNode p returnp 问题35 如何在一棵前序线索二叉树中寻找某结点p的前序最后一个结点 解析 若结点p有右子树 则其前序最后一个结点一定是其右子树上前序最后一个结点 若其右子树为空 则其前序最后一个结点一定是其左子树上前序最后一个结点 若其左 右子树都为空 则其前序最后一个结点即为它自己 ThreadNode preLast ThreadNode p 71 if p if p rtag returnpreLast p right elseif p ltag returnpreLast p left elsereturnp 问题36 如何在一棵前序线索二叉树中寻找某结点p的前序下的后继 解析 若结点p有右线索 则其前序后继即为右线索所指结点 否则若结点p有左子女 则前序后继即为其左子女指针所指结点 否则为 72 其右子女指针所指结点 ThreadNode preNext ThreadNode p if p if p ltag returnp left elsereturnp right 问题37 如何在一棵前序线索二叉树中寻找某结点p的前序下的前驱 解析 若结点p有左线索 则其前序下的前驱即其左线索所指结点 否则需要找到它的双亲q 若p是q的左子女 则其前序下的前驱即为q 否则到 73 q的左子树中寻找其前序下最后一个结点 它就是结点p前序下的前驱 ThreadNode prePrior ThreadNode p if p if p ltag returnp left else ThreadNode q preParent p if q left p returnq elsereturnpreLast q left 如何找双亲留给大家自己考虑 74 树与森林 问题38 在一棵m叉树 设根在第1层 并从0开始自上向下分层给各个结点编号 问 1 第i层最多有多少结点 2 高度为h的m叉树最多有多少结点 3 编号为k的结点的父结点编号是多少 4 编号为k的结点的第1个子结点编号是多少 5 编号为k的结点在第几层 解析 1 第i层最多有mi 1个结点 2 高度为h的m叉树最多有 mh 1 m 1 个结点 3 当k 0时结点k是根 没有父结点 当k 0时结点k 75 的父结点是 k 1 m 4 结点k的第1个子女是k m 1 5 设结点k在第i层 到第i层为止的m叉树最多有 mi 1 m 1 个结点 第i层最后一个结点编号k mi 1 m 1 1 由此可得层次号i logm k 1 m 1 1 问题39 使用树的双亲表示 寻找某结点i的双亲 所有子女 兄弟的时间复杂性是多少 76 解析 使用树的双亲表示 寻找某结点i的双亲的时间复杂度为O 1 而寻找其他要看结点存放的顺序 如果所有结点按层次序存放 寻找所有兄弟的时间为O 1 寻找所有子女的时间为O n 如果所有结点按先根序存放 寻找所有子女和兄弟的时间都是O n 其中n是结点个数 问题40 树的先根次序序列的特性是什么 解析 在树的先根次序序列中 第一个元素一定是树的根 如果树的结点个数大于1 它后面紧跟的一定是第一棵子树的根 子树又是树 同样满足上述特性 77 问题41 n个结点的树有多少种 解析 可通过树的二叉树表示来估计 在树的二叉树表示中 根的右指针一定是空的 因此 估计有多少种形态看根的左子树的n 1个结点能构成多少种二叉树 根据在二叉树中的分析可知 它服从catalan函数 等于问题42 森林中树T1 T2 T3的结点数为m1 m2 m3 在该森林的二叉树表示中 根的左子树和右子树各有多少结点 二叉树表示 78 解析 在森林的二叉树表示中根是T1的根 其左子树是T1的根的子树森林 有m1 1个结点 其右子树是除T1外其他树T2 T3构成的森林 有m2 m3个结点 问题43 在一个有n个结点的森林的二叉树表示中 左指针为空的结点有m个 那么右指针为空的结点有多少个 解析 左指针为空的都是森林中各棵树的叶结点 非叶结点有n m个 每个非叶结点的子女 兄弟链都有一个右指针为空的结点 加上根结点的右指针为空 故右指针为空的结点有n m 1个 79 二叉排序树 问题44 一棵有n个结点的二叉排序树有多少种不同形态 解析 二叉排序树的中序排列一定 不同的前序序列得到不同的二叉排序树 不同二叉排序树的总数服从catalan函数问题45 若想把二叉排序树上所有结点的数据从小到大排列 采用何种遍历算法 从大到小排列 又采用何种算法 80 解析 采用中序遍历算法 若想得到从小到大排列的遍历结果 采用LVR的方式 若想得到从大到小的遍历结果 采用RVL的方式 问题46 每次插入一个新元素到二叉排序树中应插入到什么地方 树的高度最大是多少 解析 在插入之前应先调用查找算法从根开始查找插入位置 如果查找成功 说明树中已有要插入的元素 新元素不插入 如果查找失败 则把新结点插入到查找失败的位置 注意 新结点将作为叶结点插入 二叉排序树是向下增长的 最高是单支树情形 若树结点数为n 最大高度为n 81 问题47 衡量一棵二叉排序树的查找性能要计算其查找成功的平均查找长度和查找不成功的平均查找长度 此时可借助的辅助结构是什么 解析 扩充二叉树 或称判定树 内结点代表二叉排序树原有的数据 查找成功时查找指针停留在内结点上 外结点代表二叉排序树原来没有的数据 查找失败时查找指针走到外结点 a b d e g h j l 0 q r t x z 82 问题48 对下图所示二叉排序树 查找成功的平均查找长度和查找不成功的平均查找长度是多少 解析 查找成功的平均查找长度为查找不成功的平均查找长度为扩充二叉树的内结点的度为2 外结点的度为0 n0 n2 1 83 问题49 对一棵二叉排序树做中序遍历 再基于得到的中序序列重新构造二叉排序树 这两棵二叉排序树是否相同 解析 一般不相同 对一棵二叉排序树做中序遍历得到一个有序的序列 再顺序用序列中的数据构造二叉排序树 得到一棵单支树 每个结点的左子树均为空 中序遍历 h k p s y 顺序插入 84 平衡二叉树 问题50 二叉树 二叉排序树和平衡二叉树之间是何关系 解析 二叉排序树是二叉树的特殊情形 平衡二叉树又是二叉排序树的特殊情形 平衡二叉树是高度平衡的二叉排序树 问题51 有n个结点的平衡二叉树的最小高度和最大高度是多少 解析 让平衡二叉树每层结点达到最大数目 就得到它的最小高度 n 2h 1 h log2 n 1 若让根的左右子树的结点个数达到最少 可得 85 最大高度 设高度为h的平衡二叉树的最少结点数为Nh 则有N0 0 N1 1 Nh Nh 1 Nh 2 1 h 1 由此推出N2 2 N3 4 N4 7 N5 12 对照斐波那契数F0 0 F1 1 F2 1 F3 2 F4 3 F5 5 F6 8 F7 13 有Nh Fh 2 1 另外 斐波那契数满足渐进公式 由此可得 86 两边取对数由换底公式log X log2X log2 及log2 0 694和可得h 1 44 log2 Nh 1 0 33 1 44 log2 n 1 此即平衡二叉树的最大高度 问题52 在高度为h的平衡二叉树中离根最近的叶结点在第几层 解析 计算平衡二叉树离根最近的叶结点所在层次的方法与推导高度为h的平衡二叉树最少结点 87 个数的过程类似 设高度为h的平衡二叉树的离根最近的叶结点所在层次为Lh 则有L1 1 L2 2 Lh min Lh 1 Lh 2 1 Lh 2 1 h 2直接计算Lh h 2 1 88 问题53 Huffman树是一棵扩充二叉树 外结点 叶结点 有n个 那么总共有多少结点 解析 总共有2n 1个结点 因它只有度为0和度为2的结点 由n0 n2 1 当n0 n时 n0 n2 n n 1 2n 1 问题54 在构造Huffman树的过程中 每次从森林中选根的关键字值最小和次小的两棵树合并 在合并时是最小的做左子树还是次小的做左子树 解析 都可以 可参考算法的实现代码 但手工构造时没有限制 Huffman树 89 问题55 用Huffman树构造最佳判定树 内 外结点各起什么作用 带权路径长度表示什么意思 解析 内结点是比较过程中的中间结果 外结点是比较的最终结果 带权路径长度表明可能的比较次数 或总比较次数的期望值 问题56 用Huffman树构造不等长的Huffman编码 一段报文的总 二进制 编码数用什么衡量 解析 首先根据报文中各字符出现的频度和每个字符的Huffman编码 计算带权路径长度 它就是该报文的总 二进制 编码数 也叫做总编码长度 90 问题57 并查集 mfsetorUFSetsordisjoint 主要用在什么地方 解析 一是判断和构造等价类 二是判断和构造图的连通分量 问题58 并查集有哪几种操作 解析 并查集以双亲表示为其存储结构 操作有 1 Find S x 寻找x所在子树的根 2 Union S s1 s2 合并以s1和s2为根的子树 s1并入s2 还是s2并入s1 根据算法的具体实现而定 3 UFSets S 把集合S初始化为一个森林 并查集 91 问题59 堆作为优先级队列的实现 插入和删除在堆得什么位置实施 解析 插入在队尾 即堆的最后元素的后面 删除在队头 即堆顶 最前面的位置 问题60 堆用数组作为其存储 那么它是线性结构还是非线性结构 解析 即使使用数组作为存储结构 它也是非线性结构 逻辑结构才区分线性还是非线性 因为堆是用完全二叉树组织 可以利用二叉树性质很容易地找某结点的双亲 子女和兄弟 堆 heap 92 问题61 若想把数组中的100个元素调整为小根堆 或大根堆 需做多少次关键字比较 解析 堆按完全二叉树组织 当n 100为偶数时 堆有1个度为1的结点 50个叶结点 49个度为2的结点 堆的高度为h log2 100 1 7 上面5层是满的 有25 1 31个结点 第6层度为2的结点有49 31 18个结点 则形成初始堆的最大关键字比较次数为 第6层 18 2 1 1 1 1 37 第5层 10 2 2 6 2 1 52 第4层 5 2 3 3 2 2 42 18 2 1 24 10 23 5 93 第3层 22 2 4 32 第2层 21 2 5 20 第1层 20 2 6 12 总比较次数12 20 32 42 52 37 195次 时间复杂度O n 如果借助公式这是最大估计 94 第四章知识点解析 本章 图 的知识点有7个 图的基本概念图的存储结构图的遍历最小生成树图的最短路径图的活动网络 拓扑排序 关键路径 95 图的基本概念 问题1 是否有 空图 的概念 解析 图的定义要求顶点集合不能为空 边集合可以为空 严格地讲 没有 空图 这个定义 问题2 有n个顶点的无向图最多有多少条边 最少有多少条边 无向连通图的情形呢 解析 n个顶点的无向图最多有n n 1 2条边 最少有0条边 如果是连通图 最多有n n 1 2条边 最少有n 1条边 问题3 有n个顶点的有向图最多有多少条边 最少 96 有多少条边 强连通图的情形呢 解析 n个顶点的有向图最多有n n 1 条边 最少有0条边 如果是强连通图 最多有n n 1 条边 最少有n条边 环 特别情形 n 1时最少边数为0 问题4 试讨论顶点的度与边的关系 解析 无向图情形 所有顶点的度数总和等于边数的2倍 这是因为一条边与两个顶点关联 它们在计算度数时做了重复计算 有向图情形 所有顶点的出度总和等于入度总和 还等于边数 因为总体来看 边的出 入平衡 97 问题5 图中任意两顶点间的路径是用顶点序列标识的 还是用边序列标识的 解析 是用顶点序列标识的 如最短路径 最长路径都如此 但在某些算法 如求关键路径 中 用求组成路径的边更方便些 即便如此 还是要标出顶点序列 问题6 图中各个顶点的序号是规定的 还是人为可改变的 解析 图中各个顶点的序号是人为的 可以根据需要改变这些编号 并改变存放顺序 而且每个顶点都可与其他顶点用边连接 98 问题7 有n个顶点 e条边的无向图的邻接矩阵有多少矩阵元素 其中有多少零元素 有向图的情形呢 解析 n个顶点的无向图的邻接矩阵有n2个矩阵元素 因为是对称矩阵 所以有e条边时有2e个非零元素 n2 2e个零元素 有向图的邻接矩阵也有n2个矩阵元素 因为不对称 有e个非零元素 n2 e个零元素 问题8 为什么在有向图的邻接矩阵中 统计某行1的个数 得到顶点的出度 统计某列1的个数 图的存储结构 99 得到某顶点的入度 解析 邻接矩阵中某矩阵元素Edge i j 1表明从顶点vi到vj有一条有向边 是从行读到列的 统计第i行1的个数 得到从顶点vi到其他顶点有多少条边 即计算出度 统计第j列1的个数 表明有多少条边从其他顶点进入 即计算入度 无向图则不区分它们了 问题9 有一个存储n个顶点e条边的邻接表 某个算法要求检查每个顶点 并扫描每个顶点的边链表 那么这样的算法的时间复杂度是O n e 还是O n e 100 解析 算法对邻接表的每个顶点都做了检查 时间复杂度O n 在处理每个顶点时又检查了该顶点的边链表 然而所有边链表都检查一遍才是O e 这样 访问顶点和访问边不是典型的嵌套关系了 时间复杂度是O n e 而不是O n e 问题10 设每个顶点数据占4个字节 顶点号码占2字节 每条边的权值占4个字节 每个指针占2个字节 若一个无向图有n个顶点e条边 请问使用邻接矩阵经济还是使用邻接表经济 解析 邻接矩阵表示中顶点向量需要n 4个字节 邻接矩阵需要n2 4个字节 共4 n n2 字节 101 邻接表表示中顶点向量需要n 4 2 个字节 边链表需要e 2 4 2 个字节 共6 n 8 e字节 4 n n2 6 n 8 e 4 n2 2 n 8 e 在稠密图的情形 即e与n2等数量级 邻接矩阵与邻接表的存储耗费差不多 在稀疏图的情形 即e远小于n2 使用邻接表经济 问题11 有向图的邻接表与逆邻接表组合起来形成十字链表 它适合于什么场合 解析 适合于往复处理的场合 例如 求强连通分量时需要正反向判断 求关键路径需要正反向求事件的最早和最迟时间等 102 问题12 图的遍历针对顶点 要求按一定顺序访问图中所有顶点 且每个顶点仅访问一次 可否针对边也使用遍历算法 解析 可以 例如欧拉回路问题 只要满足 所有顶点的度数均为偶数 的条件 可以从任一顶点出发 经过所有边恰巧一次 最后再回到原出发点 采用邻接表存储图 用深度优先搜索算法即可解决问题 问题13 图的深度优先搜索类似于树的前序遍历 可归属于哪一类算法 图的遍历 103 解析 都属于回溯算法 但图的深度优先搜索有可能在访问过某个顶点后 沿着某条路径向前搜索又回到这个顶点 所以必须设置一个访问标志数组visited 记录已访问过的顶点 以避免重复访问 树的前序遍历没有这种情形 问题14 图的遍历对无向图和有向图都适用吗 解析 对无向图和有向图都适用 但如果无向图不是连通的 或有向图不是强连通的 调用一次遍历算法只能遍历一个连通分量或强连通分量 为了访问所有顶点 必须检查visited 数组 找到未被访问的顶点 再次使用遍历算法进行遍历 104 问题15 图的深度优先遍历如何体现 回溯 解析 递归算法 visited 为全局量 顶点号 1 voidDFS Graph 其中 FirstAdjvex G v