数据结构试卷数据结构考研试题分析PPT课件.ppt

数据结构 1 命题思路分析 由于今年专业课的考试是三门课为一张试卷 所以题量会比02年真题小一些 但考查形式不会有太大的变化 而且会更加侧重于创新型的重点知识 所以大家一定注意把握基础的前提下做一些有难度的习题 锻炼自己的解题能力 市面上数据结构的书籍也有很多 大家可以参考一下 2 2002年真题 1 论述线性表关于顺序分配 或称为顺序分配实现 和链接分配 或称为链接分配实现 的优缺点 顺序分配与链接分配 3分 2 设树形T在中根次序 或称为中跟序 和后根次序 或称为后根序 下的节点排列如下 4分 树的遍历 考过数次 中根次序 EFCABDGHKIJ后根次序 FEAGDBCIJKH 1 试画出T的结构图 2 给出以先根次序遍历T时 T之节点被访问的次序 3 2002年真题 3 试问包含12个节点的高度平衡二叉树 通常又称为平衡二叉树 的最大高度是多少 试画出一棵这样的树 5 4 试给出冒泡排序 快速排序和堆排序的平均时间复杂性和最坏情况下的时间复杂性 6 5 给定一组权值5 6 7 9 10 12 15 18 25 试用Huffman树建造算法画出相应的Huffiman树 并计算出该Huffman树的加权路径长度 4 4 2002年真题 6 给出下图的最小支撑树 4分 或称为最小代价生成树 1 2 10 15 5 2 3 5 8 4 5 2002年真题 二按要求编写算法1 假设单链表的结点结构为 其中 KEY字段是节点的关键词域 LINK字段是节点的链接域 设两个单链表的头指针分别为F和R 在F所指的单链表中 各节点已按关键词升序排列 在R所指的单链表中 各节点已按关键词降序排列 试设计一个算法 将R所指单链表中所有结点都插入到F所指的单链表中 使插入完成后得到的单链表 F指向的 之结点仍按关键词升序排列 要求算法的时间复杂性为O m n 其中m和n分别是F和R所指的两个单链表包含的结点个数 2 设有序树形在先根次序下的节点排列为A 1 N 共N个节点 相应节点的次数为T 1 N 试给出查找A i 1 i N 的父亲节点的算法 3 图G是一个连通的无权无向图 并假设图G的邻接表以给定 试设计一个寻找从顶点i到顶点j的一条简单路径的算法 6 真题分析 基础题目特点 基础题目主要考察树 图 查找 算法当中的经典算法 算法的某个重要操作步骤等在实际解题中的应用 针对这些题目 需要掌握 1 理解重要算法的要达到的目的 2 会使用重要算法解题 3 会使用答案进行验证其正确性 7 真题分析 算法编写 是整个计算机考研初试的难点 往往对于题目考察的知识点同学们都能掌握 但是不知道如何运用 遇到这种题目需要学会分析 学会联系相关的知识点 这部分题目出题比较灵活 一般会出在树 图 查找 排序上 但是有时候会结合链表来出 希望大家多多练习 通过练习提高自己的解题能力 8 真题分析 考试知识点分布 9 真题解答 1 1 1 顺序存储即按逻辑次序将线性表的节点依次存放在一组地址连续的存储单元中 其优点是存储空间的利用率高 存取速度快 缺点是要对线性表进行插入或者删除操作时 需要调整一批节点的地址 链表存储即用链式结构来存储节点 前一个节点保存后一个节点的地址 其在进行插入或删除操作时只需修改相应指针即可 缺点是必须顺序访问各元素 10 真题解答 1 2 2 此题考查了对遍历以及递归的理解 非常的重要 11 真题解答 1 3 3 最大高度是4 其树形示例如下 本题考察了对高度平衡树算法以及概念的理解 对于高度平衡树的画法不是唯一的 12 真题解答 1 4 4 此题考察了对排序的复杂度的理解 复试的时候有可能会问道相关的问题 所以对于这部分大家一定要记住 并且理解 13 真题解答 1 5 5 根据算法画出Huffman树已经考过很多此 是比较基础的算法 也比较简单 大家要学会画huffman树 其加权路径长度为323 14 真题解答 1 6 6 此题目考察对基本的最小支撑树的理解 需要掌握其算法 1 2 8 5 3 4 2 15 真题解答 2 1 二大题一 算法思想 这里结合链表考察排序 这也是研究生考试经常考的一种题型 对于本题的思想是首先逆转降序排列的链表 其复杂度为O n 然后再把两个升序排列的链表合并为一个 其复杂度为O m n 其整个算法的复杂度为O m n 相当于归并排序 题目分析从下边几个方面 1分析当前具备的数据结构以及需要达到的目标 2题目考察的知识点在那里 3题目具有那些变化和那些约束 即题目具有那些自身的特点 16 真题解答 2 1 解题思路 1分析当前具备的数据结构以及需要达到的目标 2题目考察的知识点在那里 3题目具有那些变化和那些约束 即题目具有那些自身的特点 4结合题目的特点以及所用到的知识点设计算法 并写出 17 真题解答 2 1 算法FRLINK F R M N 链接两个链表并使其结点仍按关键词升序排列 FRLINK1 逆转链表R 利用三个指针实现pf NEXT L pm NEXT pf pr NEXT pm NEXT pf NULL WHILE NEXT pr DO 依次逆转NEXT pm pf pf pm pm pr pr NEXT pr NEXT pm pf NEXT pr pm r pr 逆转剩余节点 18 真题解答 2 1 FRLINK2 合并有序表 PRI R PR FRF F WHILE PRI NULL WHILE KEY PRI KEY PRF PRF PR PR NEXT PR IF RF NULL NEXT RF PRI EXIT WHILE 19 真题解答 2 1 ELSE 插入当前节点NEXT PR PRI NEXT PRI PRF FRF PRI PRI NEXT PRI 20 真题解答 2 2 2本题目考察书上的一个定理 即利用次数和先根序列来秋初某一个节点的父亲节点 此题有一定的难度 解答此题的关键在于弄清楚某一个节点与其父亲节点之间的关系是什么 对于先根而言 I节点的父亲肯定是在其前边 从I 1开始查找I的父亲 对于次数为不为0的节点而言 要么其为I节点父亲 要么其儿子在I节点与该节点之间 弄清楚了这一点 就可以很清楚的写算法了 21 真题解答 2 2 解题思路 1分析当前具备的数据结构以及需要达到的目标 2题目考察的知识点在那里 3题目具有那些变化和那些约束 即题目具有那些自身的特点 4结合题目的特点以及所用到的知识点设计算法 并写出 22 真题解答 2 2 算法FINDFATHER T I J 查找I的父亲存放在J里 FIND1 初始化 I I 1 COUNT 0 FIND2 搜索父节点 WHILE I 0 DO IF T I 0 为叶子节点Count count 1 IF T I 0ANDT I count 为非叶子节点 为子树Count 1 节点IF T I 0ANDT I count J I RETURNJ RETURN0 23 真题解答 2 3 3 对于此题目来说主要考察深度遍历算法 对无权无向图从I节点出发进行深度优先遍历 并且记录当前寻找的路径 如果找到J 则打印该路径 否则则不存在由I到J的简单路径 这里需要注意的是约束条件很多 第一要求邻接表存储 第二要求找到一条简单路径 本题目考察对图的遍历算法的掌握程度 掌握了对图的遍历算法 在遍历的同时记录遍历的路径即可解答此题 24 真题解答 2 2 解题思路 1分析当前具备的数据结构以及需要达到的目标 2题目考察的知识点在那里 3题目具有那些变化和那些约束 即题目具有那些自身的特点 4结合题目的特点以及所用到的知识点设计算法 并写出 25 真题解答 2 3 解法1 采用图的深度优先遍历策略 算法PATH HEAD MARK DEPTH I J GRAPH 采用递归算法深度度优先遍历该有向图 将有向图中I到J的通路记录在数组里 PATH1 深度优先遍历寻找J GRAPH DEPTH I IFI JTHENRERUEN1 ELSEMRAK I 1 PP HEAD i WHILE PP DO IFMARK VERTEX PP 0THEN IFPATH GRAPH DEPTH 1 I J MARK N 1THENRETURN1 PP LINK PP RETURN0 26 真题解答 2 3 解法2 采用图的深度优先遍历策略的非递归算法 算法PATH HEAD I J MARK GRAPH 非递归深度优先遍历该有向图寻找I到J的简单路径 将有向图中I到J的通路记录在数组里 PATH 初始化 CREATS S MARK I 1 depth 1 GRAPH depth I S I depth DSF2 寻找I到J的简单路径 WHILENOT ISEMTS S DO t p depth S IFP THENP HEAD t 27 真题解答 2 3 depth depth 1 WHILEP DO IFVERTEX P JTHENRETURN ELSEIFMARK VERTEX P 1THEN MARK VERTEX P 1 IFLINK P THENGRAPH depth VERTEX P S VERTEX P depth 回溯EXIT P LINK P 28 第一章基本概念 基本概念 1数据 是计算机程序要处理的 原料 它可以被计算机识别 存储和加工处理 2数据结构的定义 1 按某种逻辑关系将一批数据元素组织起来 2 按一定的存储方式把它们存储起来 3 在数据上定义一个运算集合 就得到 或者说形成了 一个数据结构 3数据结构重点强调的三个部分 逻辑结构 存储方式和运算集合 29 第一章基本概念 线性结构 1数据的逻辑结构常用的逻辑结构包括线性结构和非线性结构 非线性结构又包括图形 树形和网形 这里网形我们不做要求 常用的线性结构是 线性表 线性表可以用链表或者数组表示 链表的存储结构是非连续的 而数组的存储结构是连续的 对于链表的操作已经考过不少此了 包括排序 逆转等等 而且可能附加复杂性要求 是考试的重点 需要大家认真的掌握其基本操作 典型例题 请编写一个算法 功能为逆转链表 不允许使用辅助链表 30 第一章基本概念 线性结构 典型题目分析 根据链表操作的特点 知道对于链表的操作主要是进行指针的操作 而不允许使用其他辅助的链表就使得需要设置更多的指针来记录当前操作的位置 第一要记录当前已经调整完了的最后一条记录 需要一个指针 第二要记录当前头一个需要调整的记录 第三在调整的过程中 一旦调整了一个节点 其后序节点就无法找到 所以还需要一个指针记录当前正在调整的节点的后序节点 通过分析确定了需要三个辅助的指针 31 第一章基本概念 线性结构 算法LinkList resverse L L 输入一个链表 输出此链表 但此时已经逆置 假设表的长度大于2LR1 初始化 p next L q next p s next q next p NULL LR2 循环逆置 WHILE next s DO next q p p q q s s next s LR3 结束 next q p next s q next L s 32 第一章基本概念 非线性结构 2非线性结构结构中可能有多个前驱节点和多个后继节点 数据结构最重要就是学习非线性结构 因为在现实生活中的问题往往是非线性结构的题目 而且对于此类问题的解决也最能考查一个人的能力 所以这部分是考场的重中之重 需要大家在这方面多多练习 最重要和常用的非线性数据结构是 树 图 33 第一章基本概念 非线性结构 给定一个二叉树形 试用ADL语言给出一个复制二叉树形的算法 问题分析 从题目当中看出考察的知识点是二叉树形的遍历操作 而题目本身的特点是需要记录并且复制每个节点 然后设置其左右子树 此题目可以用三种遍历算法当中的任何一个来实现 实现的方法也很多 这里给出两种 从这个算法当中 可以体会栈和队列的用处 34 第一章基本概念 非线性结构 解法1 拷贝树的递归实现算法COPY TREE OldTree newTree 后根遍历拷贝原树CT1 初始化 newLeft NULL newRight NULL CT2 后根遍历递归实现 IFOldTree NULLTHENRETURNNULL IFleft OldTree NULLTHEN 35 第一章基本概念 非线性结构 COPY TREE left OldTree newLeft IFright OldTree NULLTHENCOPY TREE right OldTree newRight newNode AVAIL data newNode data OldTree left newNode newLeft right newNode newRight 36 第一章基本概念 非线性结构 这里给出树形拷贝的非递归算法 算法COPY TREE OldTree newTree 先根遍历拷贝原树CP1 初始化 CREATS S IFOldTree THEN newTree RETURN newNode AVAIL 复制父亲节点data newNode data oldTree IFRLINK OldTree THENRLINK newNode ELSES RLINKOldTree newNode R 37 第一章基本概念 非线性结构 IFLLINK OldTree THENLLINK newNode ELSES LLINK OldTree newNode L CP2 拷贝 WHILE ISEMTS S copyNode father TAG S newNode AVAIL data newNode data copyNode 38 第一章基本概念 非线性结构 IF TAG R RLINK father newNode IF TAG L LLINK father newNode IFRLINK copyNode THENRLINK newNode ELSES RLINK copyNode newNode R IFLLINK copyNode THENLLINK newNode ELSES LLINK copyNode newNode L 39 第一章基本概念 算法复杂性 评估算法的标准 时间复杂性 复杂性记法 如果存在两个正常数c和n0 使得对所有的n n n0 有 f n cg n 则有 f n g n 重要的时间复杂性排序为 O 1 O log2n O n O nlog2n O n O n O 2 40 第二章基础知识 历年真题 1论述线性表关于顺序分配 或称为顺序分配实现 和链接分配 或称为链接分配实现 的优缺点 3分 2002 本题目主要考察顺序分配与链接分配的比较 是考试的这几年中少有的概念题目 说明对于顺序分配和链接分配的概念非常重要 需要认真体会 41 第二章基础知识 历年真题 2设合并拉链表由T 0 T 1 T M 1 组成 表中每个地址T i 用来存储一个记录和一个LINK域 M为最大记录个数 某一表地址的LINK域值为 1表示其连接为空 试设计一算法Dchaining T M i 该算法删除合并拉链表中地址T i 处的记录 使删除后的合并拉链表不会出现记录 遗忘 1999 12分 题目解析 本题是结合基础知识来考察合并链表的算法 对于本章知识的考察主要通过结合排序 查找这两章来实现的 而对于堆栈的考察主要是通过在相关非递归算法当中树 图的操作而言的 需要认真的体会 42 第二章基础知识 历年真题解答 算法Dchaining T M i 合并拉链表中删除元素 Dch1 查找是否有指向I的链接 LinkI 1 FORJ 0TOM 1DOIFLINK T J I THEN LINKI J EXITFOR Dch2 调整指针 IFLINK T I 1THEN IFLINKI 1THENLINK T LINKI 1 RETURN 43 第二章基础知识 历年真题解答 ELSEIFLINKI 1THENLINK T LINKI LINK T I Dch3 删除该元素 LINK T I 1 DELETE T i 44 第二章基础知识 历年真题 3有一个长度为12的有序表 按对半查找法对该表进行查找 在表内各元素等概率情况下 查找成功所需的平均比较次数是多少 2001 3分 题目分析 本题目关键在于理解二叉查找树的概念 结合有序表来看平均的比较次数是多少 平均比较次数 2 3 3 2 3 0 2 3 1 3 2 3 12 2 25 次 45 第二章基础知识 历年真题 2001 编写一个算法来交换单链表中指针P所指的节点与其后继节点 HEAD是该链表的头指针 P指向该链表中的某一个节点 7分 题目分析 考察基本的链表操作 主要需要注意对于临界条件的判断 46 第二章基础知识 历年真题 算法SWAP HEAD P HEAD指向链表头部 交换P与其后续 SWAP1 临界判断 NEXT P THEN PRINT NONEXT RETURN SWAP2 交换 PF HEAD IFPF PTHEN P指向头部 P NEXT P PR NEXT P NEXT P PF NEXT PF PR HEAD PF RETURN 47 第二章基础知识 历年真题 ELSEWHILE NEXT PF P PF NEXT PF PR NEXT P NEXT P NEXT PR 交换NEXT PR P NEXT PF PR RETURN 48 第二章基础知识 典型题目 已知链表A为有序顺序存储型表 请设计一个算法 使得该函数能删除对于同时存在在两个表B C中的A表中的相同元素 49 第二章基础知识 典型题目 解题思路 本题目通过三个有序链表考察对于查找的理解 A B C三个表都是有序表 查找A中元素时候需要同时记录B C表中已经查找到了那个位置 任意一个表查找结束 那么整个查找过程结束 删除以后对于A还需要进行紧凑 50 第二章基础知识 典型题目解答 算法SqList Intersect delete A B C D1 初始化 i 1 j 1 k 1 D2 标识相同的元素 WHILEEXIST B i ANDEXIST C j DO IFB i C j THENj ELSE u B i WHILEA k uDOk 51 第二章基础知识 典型题目解答 IFA k uDO k A k INFINITY WHILEB i uDOi WHILEC j uDOj SID3 删除被标记的元素 并将后面的元素紧凑 FORi length A TO1STEP 1DO 52 第二章基础知识 典型题目解答 IF A i INFINITY THEN j i 1 WHILEj length A A i A j i i 1 j j 1 length A length A 1 53 第二章基础知识 失败函数 若 t1t2 tn 为一模式 则其失败函数定义如下 f j 小于j的最大i 且满足 t1t2 ti tj i 1tj i 2 tj 0 若不存在这样的i 54 例如 第二章基础知识 失败函数 55 第三章树 历年真题 历年真题 2000年 已知一棵二叉树的中序 或中根 遍历节点排列为DGBAECHIF 后序 或后根 遍历节点排列为GDBEIHFCA 5分 1 试画出该二叉树 2 试画出该二叉树的中根穿线 或线索 树 3 试画出该二叉树 自然 对应的森林 56 第三章树 历年真题 题目考察知识点 1 树的遍历以及遍历之间的内在关系2 二叉穿线树的定义 3 树与森林的关系 57 第三章树 历年真题解答 题目解析 答案 1 根据其后序找到主根 然后根据主根在中序中分出左右子树 然后递归看左右子树 画出树形 58 第三章树 历年真题解答 题目解析 答案 2 根据中根穿线树的定义 画出中根穿线树 59 第三章树 历年真题解答 题目解析 答案 3 根据树与森林的关系 画出其对应的森林 60 第三章树 历年真题知识点遍历 先序遍历中序遍历后序遍历层次遍历 61 第三章树 历年真题知识点遍历 先根递归过程为 若二叉树为空 遍历结束 否则 1 访问根结点 2 先序遍历根结点的左子树 3 先序遍历根结点的右子树 要会写其非递归算法 在使用先根序遍历的时候如果没有做要求能递归的一定使用递归 62 第三章树 历年真题知识点遍历 先序遍历二叉树的递归算法 voidPreOrder BiTreebt if bt NULL return Visit bt data PreOrder bt lchild PreOrder bt rchild 63 第三章树 历年真题知识点遍历 中根次序遍历 设指针T指向以LLINK RLINK链接表示的一棵二叉树形 这里体会栈的应用 1 初始化 CREATS A P T 2 WHILEP DO A P P LLINK P 3 IFISEMTS A THENRETURNELSEP S 4 PRINT INFO P P RLINK P GOTO 2 64 第三章树 历年真题知识点遍历 层次遍历从二叉树的根结点开始 首先将根节点指针入队列 然后从对头取出一个元素 每取一个元素 执行下面两个操作 1 访问该元素所指结点 2 若该元素所指结点的左 右孩子结点非空 则将该元素所指结点的左孩子指针和右孩子指针顺序入队 注 如果是先把左孩子放在队列中就实现了从左到右的遍历过程 否则亦然 65 第三章树 历年真题知识点遍历 对于树的遍历几个重要的结论 1已知先根遍历的次序和后根遍历其中一种加上中根可以唯一确定一颗树 2已知先根或者后根和各节点次数可以唯一确定一颗树 关于这两个知识点已经考过数次 在后边的真题讲解中会详细的给大家讲解 66 第三章树 历年真题知识点线索二叉树 需要掌握的内容 线索二叉树的定义 线索二叉树的存储结构 在中序线索二叉树上的更新操作 67 第三章树 历年真题知识点线索二叉树 线索二叉树的定义 利用某结点空的左指针域 lchild 指出该结点在某种遍历序列中的直接前驱结点的存储地址 利用结点空的右指针域 rchild 指出该结点在某种遍历序列中的直接后继结点的存储地址 对于那些非空的指针域 则仍然存放指向该结点左 右孩子的指针 68 第三章树 历年真题知识点线索二叉树 0lchild指向结点的左孩子1lchild指向结点的前驱结点 ltag 0rchild指向结点的右孩子1rchild指向结点的后继结点 rtag 线性表的存储结构 69 第三章树 历年真题知识点线索二叉树 在中序线索二叉树上的插入 对于删除大家自己看 1 若s的右子树为空 如图 a 所示 则插入结点p之后成为图 b 所示的情形 在这种情况中 s的后继将成为p的中序后继 s成为p的中序前驱 而p成为s的右孩子 二叉树中其它部分的指针和线索不发生变化 2 若s的右子树非空 如图 c 所示 插入结点p之后如图 d 所示 S原来的右子树变成p的右子树 由于p没有左子树 故s成为p的中序前驱 p成为s的右孩子 又由于s原来的后继成为p的后继 因此还要将s原来的本来指向s的后继的左线索 改为指向p 70 第三章树 历年真题知识点线索二叉树 71 第三章树 历年真题知识点线索二叉树 72 第三章树 历年真题知识点森林 主要考察树与森林的对应关系 这里给出了相应的递归定义 设F T1 T2 Tn 表示由树形T1 T2 构成的森林 自然对应下的森林F的二叉树形B F 递归定义如下 1若n 0 则B F 为空 2如果n 0 则B F 的根是root T1 B F 的子树形是B T2 T3 Tn 左子树形为B T11 T12 T1m 其中B T11 T12 T1m 是root T1 的诸子树形 73 第三章树 历年真题知识点森林 将树转化成二叉树的算法 a 树中所有相邻兄弟之间加一条连线 b 对树中的每个结点 只保留它与第一个孩子结点之间的连线 删去它与其它孩子结点之间的连线 c 以树的根结点为轴心 将整棵树顺时针转动一定的角度 使之结构层次分明 74 第三章树 历年真题知识点森林 a 相邻兄弟加连线 树 75 第三章树 历年真题知识点森林 b 删去双亲与其它孩子的连线 c 转换后的二叉树 76 第三章树 历年真题知识点森林 二叉树转化为树和森林的情况 a 若某结点是其双亲的左孩子 则把该结点的右孩子 右孩子的右孩子 都与该结点的双亲结点用线连起来 b 删去原二叉树中所有的双亲结点与右孩子结点的连线 c 整理由 a b 两步所得到的树或森林 使之结构层次分明 77 第三章树 历年真题知识点森林 二叉树还原为森林的示意图 78 第三章树 历年真题知识点森林 二叉树还原为森林的示意图 79 第三章历年真题 2001 设树形T在后根次序下的节点排列和各节点相应得次序如下 后根次序 BDEFCGJKILHA 次数 000030002024 请画出T的树形结构图 题目分析 本题目考察了在已知后跟或者前根情况和次数的情况下如何来构造树形 80 第三章树历年真题解答 解题思路 由于是后序遍历 那么其总根节点肯定是先左后右的 首先从最前边找到第一个次数非0的节点 那么它前边与之次数相同几个为0的节点依次是它的儿子 依次类推 得出树形 本题目考察了对于遍历和次数关系的理解 如何找到他们的对应关系是解题的关键 81 第三章树历年真题 2001 写出增长树的内节点数T与外节点数S之间的关系 3分 考察增长树的概念以及树的基本性质 82 第三章树历年真题解答 本题考察了增长树的概念 增长树是为了处理方便 让没有左子树和右子树的所有节点增加特殊节点称为外节点作为其子树 原来的节点成为内节点 显然 所有的外节点都是叶子节点 所有的内节点都是非叶节点 所以其关系为 S T 1 83 第三章树历年真题 2002 设树形T在中根次序 或称为中跟序 和后根次序 或称为后根序 下的节点排列如下 中根次序 EFCABDGHKIJ后根次序 FEAGDBCIJKH 1 试画出T的结构图 2 给出以先根次序遍历T时 T之节点被访问的次序 本题目同样考察遍历与还原 是第三此出现 几乎是每年必考的题目 84 第三章树历年真题 2000 给定一组权值2 3 5 7 11 13 17 19 23 29 31 37 41 试画出Huffman算法建造的Huffman树 2002 给定一组权值5 6 7 9 10 12 15 18 25 试用Huffman树建造算法画出相应的Huffiman树 并计算出该Huffman树的加权路径长度 解题思路 Huffman树是非常经典的编码方式 所以经常考察 需要会使用Huffman算法 85 第三章树历年真题解答 对于huffman树 需要会画 而且知道其性质是具有最短的树的加权路径长度 其加权路径长度定义为叶子节点的带权路径长度之和 其计算公式为 wi li其中wi和li为叶子节点ki的权值和根到ki的路径长度 86 第三章树历年真题解答Huffman树 基本概念 带权路径长度 如果二叉树有n个带权值的叶结点 那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和即为带权路径长度 哈夫曼树 指对于一组带有确定权值的叶结点 构造出的具有最小带权路径长度的二叉树 87 第三章树历年真题解答Huffman树 1 由给定的n个权值 W1 W2 Wn 构造n棵只有一个叶结点的二叉树 从而得到一个二叉树的集合F T1 T2 Tn 2 在F中选取根结点的权值最小和次小的两棵二叉树作为左 右子树构造一棵新的二叉树 这棵新的二叉树根结点的权值为其左 右子树根结点权值之和 3 在集合F中删除作为左 右子树的两棵二叉树 并将新建立的二叉树加入到集合F中 4 重复 2 3 两步 当F中只剩下一棵二叉树时 这棵二叉树便是所要建立的哈夫曼树 88 第三章树历年真题解答Huffman树 Huffman H m 1 初始化 FORi 1TOmDoLLINK H i RLINK H i 2 组合过程 FORi 1TOm 1Do t AVAIL P1 H i P2 H i 1 Weight t Weight P1 Weight P2 LLINK t P1 RLINK t P2 p t 89 第三章树历年真题解答Huffman树 把新组合节点t的地址p插入到数组H中 使得Weight H i 1 Weight m j i 2 WHILEWeight p Weight j Do H j 1 H j j j 1 H j 1 p 90 第三章树历年真题解答Huffman树 91 第三章树历年试题 2001 试给出二叉树的自下而上 自右而左的层次遍历算法 8分 题目分析 本题目考察树的层次遍历算法 其要求的是一个层次遍历算法的逆过程 所以只需要层次遍历的结果存放在一个栈当中 然后弹栈的时候遍历 就实现了这个逆过程 92 第三章树历年试题解答 算法WDF TREE 1 初始化 CREATQ Q CREATS S IFTREE THENRETURN Q TREE 2 WHILEISEMTQ Q DO PS IFLLINK P THENLLINK P Q IFRLINK P THENRLINK P Q 3 WHILEISEMTS S DO P S PRINT INFO P 93 第三章树历年试题 2002 设有序树形在先根次序下的节点排列为A 1 N 共N个节点 相应节点的次数为T 1 N 试给出查找A i 1 i N 的父亲节点的算法 8分 题目分析 本题目考察对于知道次数和知道先根序列确定树形的算法 而同样对于前边知道先根和中根构造树形的算法也需要掌握 94 第三章树历年试题解答 答案在前边已经给出 95 第三章树历年试题 1999 已知指针p指向带表头的中根次序穿线二叉树的某节点 试写一算法FFA p q 该算法寻找结点p的父节点q 设穿线二叉树的节点结构 表头节点结构和空树结构分别为图示 且规定穿线树的最左下节点的LLINK域和最右下节点的RLINK域指向表头 8分 96 第三章树历年试题解答 本题主要考察对于穿线二叉树的性质的掌握 首先分析节点P和其父亲节点的关系 1 如果P在q的右子树上 那么要么P的左链接指向q 要么P的子树上的最左边的叶子节点的左链接指向q 2 如果p在q的左子树上 那么P向左的第一个叶子节点 有可能是自己 指向q的祖先 并且顺着这个祖先的右儿子的左子树可以找到P 97 第三章树历年试题解答 P 98 第三章树历年试题解答 算法FFA P q 该算法找到P的父亲节点 FFA1 如果节点左链接为空 IFLTAG P THENWHILE LTAG PF DOPF LLINK PF PF LLINK P IF PF HEAD THEN 找到表头 WHILE LLINK PF P DOPF LLINK PF q PF RETURN 99 第三章树历年试题解答 ELSEIFRLINK PF PTHENq PF RETURN ELSEPF RLINK PF WHILE LLINK PF P DOPF LLINK PF q PF RETURN 100 第三章树历年试题 2002 设一棵二叉树的节点结构为 ROOT为指向该二叉树根节点的指针 p和q分别为指向该二叉树中任意两个节点的指针 试编写一算法ANCESTOR ROOT p q r 该算法找到p和q的最近的共同祖先节点r 12分 题目分析 本算法实际也是在考遍历 首先需要分析两个节点的共同父亲节点的关系 它们要么具有父子关系 要么处于最近共同祖先的不同子树 101 第三章树历年试题解答 算法思想 首先给出一个判断某节点是否为一个树的节点的算法 然后从根出发 如果P q节点都在同一个子树上 那么就到那个子树上去找寻 最后找到p q分别在左右子树上的时候 那么这个节点就是要找的节点 算法思想包含了特殊情况 102 第三章树历年试题解答 算法BOOLIsChildInTree child tree 递归判断child是否为树tree的节点 IFtree NULLTHENRETURNFALSE IFINFO child INFO tree THENRETURNTRUE ELSERETURNIsChildInTree child LLINK tree ORIsChildInTree child RLINK tree 103 第三章树历年试题解答 算法ANCESTOR ROOT p q r 返回p q的最近的祖先节点 ptr ROOT endFlag false WHILENOTendFlag endFlag TRUE IFIsChildInTree p LLINK ptr ANDIsChildInTree q LLINK ptr THEN 如果p q都在左子树 104 第三章树历年试题解答 ptr LLINK ptr endFlag False IFIsChildInTree p RLINK ptr ANDIsChildInTree q RLINK ptr THEN 如果p q都在左子树 ptr RLINK ptr endFlag False r ptr 105 第三章树历年试题解答 解法2 找到根到P的路径和根到Q的路径 然后找出P和Q的路径当中最后一个相同的节点 就是他们共同的祖先节点 算法FINDPATH TREE P PATH I 在TREE树中寻找TREE到节点P的路径 存储在PATH中 IFTREE P FOUND TRUE RETURN PATH I TREE IF LLINK TREE THENFINDPATH LLINK TREE P PATH I 1 IF RLINK TREE THENFINDPATH RLINK TREE P PATH I 1 IFFOUND FALSEPATH I 106 第三章树历年试题解答 算法ANCESTOR ROOT p q R 寻找p q的共同祖先 FINDPATH ROOT p PATHP 1 FINDPATH ROOT q PATHQ 1 I 1 WHILEPATHP I PATHQ I DOI I 1 R PATH I 1 107 第三章树考试预测 考试预测 树这一章是非常重要的一章 几乎每年都有大题 对于小题基本考察遍历 树与森林关系 穿线树的操作以及huffman树 对于难点的题目可能出现在运用树的遍历为手段 在解答的时候从两个方面考虑 第一个方面是如何使用堆栈 第二个方面是如何使用遍历 第三个方面题目的各个节点之间的关系 108 第三章树典型例题 以二叉链为存储结构 求二叉树的深度 题目分析 对于此题目没有要求是否使用递归调用 而此题是可以使用递归调用的绝佳例子 109 第三章树典型例题解答 算法BTreeDepth BT out 求树高度 IFBT THEN OUT 0 RETURN IFLLINK BT ANDRLINK BT THEN OUT 1 RETURN ELSEBTreeDepth LLINK BT Dep1 BTreeDepth RLINK BT Dep2 IFdep1 dep2THEN out dep1 1 RETURN ELSE out dep2 1 RETURN 110 第三章树典型例题 编写一算法 判定给出的二叉树是否为完全二叉树 题目分析 本题目是考察你对层次遍历的理解 只需要进行层次遍历 然后判断在遍历的过程中是否有空指针即可 111 第三章树典型例题 算法JUDGE TREE ISORNOT 判断TREE是否为完全二叉树 这里TREE的节点树为N 1 初始化 CREATQ Q IFTREE THEN ISORNOT TRUE RETURN Q TREE 2 WHILEISEMTQ Q ANDN 0DO PQ RLINK P Q 3 ISORNOT TRUE RETURN 112 第三章树典型例题 已知一个二叉树的先根序存在数组A 1 n 中 其中根序存放在B 1 n 编写算法建立一个二叉树的二叉链表 自己练习 提示 采用递归 在先根找到根 利用根划分中根节点为两个部分 然后找出这两个部分在先根中对应的位置 然后递归调用 根据节点数判断 113 第三章树典型例题 如果用大写字母标识二叉树节点 则一颗二叉树可以用符号下面语法图的字符序列表示 试写一个递归算法 由这种形式的字符序列 由这种形式的字符序列 建立相应的二叉树的二叉链表存储结构 二叉树的符号存储在数组中 114 第三章树典型例题 A B D C E F 115 第四章图 1 基本概念与性质2 存储结构邻接表 邻接矩阵3 遍历算法 要求熟练掌握 广度 深度优先4 几类典型问题拓扑排序 关键路径 最短路径 最小支撑树5 几个典型算法Dijkstra算法 kruskal算法 Prim算法 116 1 基本概念与性质 1 有关图的各种定义 2 一些关于图的性质 117 有关图的各种定义 有向图 无向图子图 支撑子图出度 入度简单路径 简单回路最大连通分量权图 118 2 存储结构 1 邻接矩阵 有权图 119 无权图 120 2 邻接表 有权图 121 3 遍历算法 广度优先遍历从图中某顶点v出发 访问v 依次访问v的各个未曾访问过的邻接点 分别从这些邻接点出发依次访问它们的邻接点 并使 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问 若图中尚有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 重复 直至图中所有顶点都被访问到为止 即 以v为起始点 由近至远依次访问和v有路径相通且路径长度为1 2 的顶点 122 广度优先遍历示例 从v1出发 V1V2V3V4V5V6V7V8 123 广度优先非递归程序 voidBFSTraverse GraphG Status Visit intv 按广度优先非递归遍历图G 使用辅助队列Q和访问标志数组visited for v 0 v G vexnum v visited v FALSEInitQueue Q 置空的国债队列Q if visited v v尚未访问 EnQucue Q v v入队列 while QueueEmpty Q DeQueue Q u 队头元素出队并置为u visited u TRUE visit u 访问u for w FistAdjVex G u w w NextAdjVex G u w if visited w EnQueue Q w u的尚未访问的邻接顶点w入队列Q BFSTraverse 124 2 深度优先遍历 假设初始状态时图中所有顶点未曾被访问 则 从图中某个顶点v出发 访问此顶点 依次从v的未被访问的邻接点出发深度优先遍历图 直至图中所有和v有路径相通的顶点都被访问到 若此时图中尚有顶点未被访问 则另选图中一个未曾被访问的顶点作起始点 重复上述过程 直至图中所有顶点都被访问到为止 125 深度遍历示例 从V1出发 126 voidDFSTraverseAL ALGraph G 深度优先遍历以邻接表存储的图G inti for i 0 in i visited i FALSE 标志向量初始化 for i 0 in i if visited i DFSAL G i vi未访问过 从vi开始DFS搜索 voidDFSAL ALGraph G inti 以Vi为出发点对邻接表存储的图G进行DFS搜索 EdgeNode p printf visitvertex V c n G adjlist i vertex 访问顶点Vi visited i TRUE 标记Vi已访问 p G adjlist i firstedge 取Vi边表的头指针 while p 依次搜索Vi的邻接点Vj j p adjva if visited p adjvex 若Vj尚未访问 则以Vj为出发点向纵深搜索DFSAL G p adjvex p p next 找Vi的下一个邻接点 127 DSF HEAD n s MARK MARK 深度优先的非递归遍历算法 s V G 其它说明同算法Depth 1 初始化 CREATS S MARK s 1 S s 2 WHILENOT ISEMTS S DO t p S IFP THENP HEAD t WHILEP DO IFMARK VERTEX P 1THEN MARK VERTEX P 1 IFLINK P THEN 回朔点 S VERTEX P EXIT P LINK P 128 第四章图历年真题 1对于如下的加权有向图 给出算法Dijkstra产生的最短路径的支撑树 设定点A为原点 并写出生成过程 题目分析 考察Dijkstra算法 129 Dijkstra 算法 按路径长度递增的次序产生最短路径的算法算法的基本思想是 1 设置两个顶点的集合S和T V S 集合S中存放已找到最短路径的顶点 集合T存放当前还未找到最短路径的顶点 2 初始状态时 集合S中只包含源点v0 然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中 130 Dijkstra 算法 3 集合S每加入一个新的顶点u 都要修改顶点v0到集合T中剩余顶点的最短路径长度值 集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值 4 此过程不断重复 直到集合T的顶点全部加入到S中为止 131 Dijkstra算法描述 1 用带权的邻接矩阵edges来表示带权有向图 edges i j 表示弧 vi vj 上的权值 若 vi vj 不存在 则置edges i j 为 S为已找到从v出发的最短路径的终点的集合 它的初始状态为空集 那么 从v出发到图上其余各顶点 终点 vi可能达到最短路径长度的初值为 D i edges LocateVex G v i vi V 2 选择vj 使得D j Min D i vi V S vj就是当前求得的一条从v出发的最短路径的终点 令S S j 132 Dijkstra算法描述 3 修改从v出发到集合V S上任一顶点vk可达的最短路径长度 如果D j edges j k D k 则修改D k 为D k D j edges j k 重复操作 2 3 共n 1次 由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列 133 Dijkstra算法描述 Dijkstra HEAD s n d 1 初始化 FORv 1TOnDOd v d s 0 L s U V s S 2 WHILES VDO deletemin L v S S v P HEAD v WHILEP DO u VERTEX P IFd u THEN d u d v W P insert L u IFd u Andd v w p d u THENdecreate L u d v W P p LINK P 134 例子 135 例子 136 试写出用克鲁斯卡尔 kruskal 算法构造下图的一棵最小支撑 或生成 树的过程 本题考察kruskal算法 137 1 构造最小生成树的Kruskal算法 是一种按照网中边的权值递增的顺序构造最小生成树的方法 138 Kruskal算法构造最小生成树的过程示意 Kruskal算法构造最小生成树的过程示意图 139 3给出下图的最小支撑树 或称为最小代价