• 1. 数据结构 2016MSE考研冲刺
  • 2. 课程安排课程介绍 栈、队列和向量 树 查找 排序 图
  • 3. 课程目的(以最小代价)通过考试! 不是成为专家 不是初学授课
  • 4. 试题结构考试满分60分 考试题型:问答、分析、编程
  • 5. 样题-问答和编程题插入排序、选择排序、冒泡排序、快速排序中最快的排序方法是________ 试论述什么叫Hash冲突及有那些处理方法 编程实现对二叉树所有节点的统计
  • 6. 课程安排课程介绍 栈、队列和向量 树 查找 排序 图
  • 7. 链表、栈和队列大纲描述: 单链表,双向链表,环形链表,带哨兵节点的链表 栈的基本概念和性质,栈ADT及其顺序,链接实现;栈的应用;栈与递归; 队列的基本概念和性质,队列ADT及其顺序,链接实现;队列的应用; 向量基本概念和性质;向量ADT及其数组、链接实现;
  • 8. 线性表基本概念和性质线性表 是n个数据元素的有限序列 常见线性表包括数组、链表、栈、队列等 线性表的两种实现方式 顺序 链式 对比:插入(有序、无序)、删除、查找、读取
  • 9. 环形链表环形链表 又称循环列表,是另一种形式的链式存储结构。它的特点是表中最后一个元素的指针域指向头结点
  • 10. 栈的基本概念和性质栈: 栈是限定仅在表尾进行插入和删除操作的线性表 后进先出特性(LIFO) 栈顶、栈底、出栈、入栈
  • 11. 例题设有一个栈S,元素S1, S2, S3, S4, S5, S6依次进栈,如果6个元素的出栈顺序为S2, S3, S4, S6, S5, S1,则栈的容量至少应为多少? 答案:3
  • 12. 栈的基本概念和性质设计递归问题的非递归算法一般需要用到栈机制 三个数a、b、c进栈,不可能出现c、a、b顺序出栈
  • 13. 例题若某栈的输入序列为a、b、c,则所有可能的出栈序列有___种,所有不可能的出栈序列有____种。 答案:5,1
  • 14. 例题若栈的输入序列为1,2,3,4,则——是不可能的栈输出序列之一。 答案:4,3,1,2
  • 15. 习题若某栈的输入序列为a、b、c、d,则所有可能的出栈序列有___种,所有不可能的出栈序列有____种。 请写出所有可能的序列和不可能的序列。
  • 16. 栈的应用数制转换 十进制数字与d进制数字的转换 N = ( N div d) × d + N mod d 其中div为整除,mod为求余。 算法: 将算法3.1中8换成d
  • 17. 例题十进制数1167等于八进制数——? 答案: 2217 思路: 计算方法:除余倒排法 验证方法:指数相加法
  • 18. 习题十进制数1167等于七进制数——?
  • 19. 栈的应用表达式求值: 中缀表达式转后缀表达式 后缀表达式求值 三种表达式: 前缀表达式 + a b 中缀表达式 a + b 后缀表达式 a b +
  • 20. 例题中缀表达式a + b × c – d转为后缀表达式是————? 答案: a b c×+d-
  • 21. 例题中缀表达式(a + b) × c – d转为后缀表达式是————? 答案: a b + c×d- 思路: 数字位序不变,运算符位置改变 后缀表达式无括号,运算顺序同中缀表达式
  • 22. 习题中缀表达式A-(B+C)*D/E的后缀形式是_________________。
  • 23. 练习中缀表达式a * ( b + c ) / d转为后缀表达式是————?
  • 24. 例题计算后缀表达式1 2 + 4 * 2 /的值为——? 答案:6 思路: 顺序计算 或 转换为中缀表达式计算
  • 25. 习题计算后缀表达式3 2 - 4 * 2 / 3+的值为——?
  • 26. 递归一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称为递归函数 优点:结构清晰、程序易读、正确性容易得到证明 缺点:效率相对较低
  • 27. 队列的基本概念和性质队列: 队列是限定仅在表的一头进行插入、另一头进行删除操作的线性表 先进先出特性(FIFO) 队尾、队头、入队、出队
  • 28. 例题在初始为空的队列中插入元素a,b,c,d以后,紧接着作了两次删除操作,此时的队头元素是——,队尾元素是————。 答案:c,d
  • 29. 双向队列双向队列: 亦称双端队列(Deque) 是限定插入和删除操作在表的两端进行的线性表 可以用于包装产生栈和队列
  • 30. 课程安排课程介绍 栈、队列和向量 树 查找 排序 图
  • 31. 树 大纲描述: 树的基本概念和术语;树的前序、中序、后序、层次序遍历; 二叉树及其性质;普通树与二叉树的转换; 树的存储结构,标准形式;完全树(complete tree)的数组形式存储; 树的应用,Huffman树 。
  • 32. 树的基本概念和术语树: 是n(n≥0)个结点的有限集 在任意一棵非空树中: 有且仅有一个特定的称为根的结点 当n>1时,其余结点可以分为m(m>0)个互不相交的有限集,其中每个集合本身又是一棵树,并且称为根的子树 树属于层次结构数据结构
  • 33. 树的基本概念和术语节点 标签 父节点、子节点、兄弟节点、祖先节点、子孙节点 路径、树枝 根、叶子 次数 内部节点、外部节点 树的次数、K次树 节点层次、树的高度和深度 子树 有序树、无序树 森林、果园
  • 34. 例题
  • 35. 例题列出如上图所示树的所有叶子结点 答案:K,L,F,G,M,I,J 列出如上图所示树的所有分支结点 答案:A,B,C,D,E,H 树A为几次树?子树B呢? 答案:3,2 前页图所示树的高度为多少? 答案:4
  • 36. 树的基本概念和术语如果将树中结点的各子树看作从左到右有序的,则该树为有序树(ordered tree),否则为无序树。 森林(forest)是m棵互不相交的树的集合。 如果把一棵树的根砍去,剩下的部分就是森林。 如果原来的树是有序的,则砍去根后的森林也是有序的,此时称该森林为有序森林或果园。
  • 37. 二叉树及其性质二叉树(Binary Tree) 另一种树形结构,特点是每个结点至多只有二棵子树,且子树有左右之分,其次序不能任意颠倒 二叉树可能的五种基本形态
  • 38. 二叉树及其性质在二叉树的第i层上至多有2i-1个结点(i≥1)
  • 39. 例题一棵二叉树第五层上至多有多少个结点?至少多少? 答案:16,1
  • 40. 二叉树及其性质深度为k的二叉树至多有2k-1个结点(k≥1)
  • 41. 例题深度为n(n>0)的二叉树最多有_____个结点。 答案:2n-1
  • 42. 例题一棵深度为5的二叉树至多有多少个结点?至少多少? 答案:31,5
  • 43. 例题高度为h(h>0)的二叉树最少有________个结点? 答案:h
  • 44. 二叉树及其性质对于任何二叉树,如果叶子节点数为n0,度为2的节点数为n2,则n0=n2+1
  • 45. 例题在一棵二叉树中有n0个叶结点,有n2个度为2的结点,则n2=________。 答案: n0 -1
  • 46. 例题若一棵二叉树有10个叶结点,则该二叉树中度为2的结的点个数为______________。 答案:9
  • 47. 例题若一二叉树有2度结点100个,则其叶结点有多少个? 答案:101
  • 48. 例题若二叉树中度为2的结点有15个,度为1的结点有10个,共有多少个结点? 答案:41
  • 49. 例题在一棵度为3的树中,度为3的结点有2个,度为2的结点有1个,度为1的结点有2个,那么,该树有__________个叶结点。 答案:6 构造法
  • 50. 二叉树及其性质满二叉树: 一棵深度为k且有2k-1个结点的二叉树 可以对满二叉树的结点进行连续编号,约定编号从根开始,自上而下,自左而右。 完全二叉树: 深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时,称为完全二叉树。
  • 51. 二叉树及其性质完全二叉树特点: 叶子结点只可能出现在层次最大的两层上 对任一结点,若其右分支下子孙的最大层次为l,其左下分支的子孙的最大层次必为l或者l+1。 深度为k的完全二叉树第k层最少1个结点,最多2k-1-1个结点;整棵树最少2k-1个结点,最多2k-2个结点
  • 52. 例题若某完全二叉树的深度为h,则该完全二叉树中至少有______个结点。 答案:2h-1
  • 53. 例题若深度为6的完全二叉树的第6层有3个叶结点,则该二叉树一共有______个结点。 答案:25-1+3=34
  • 54. 例题一个具有767个结点的完全二叉树,其叶子结点个数为____。 答案:384 分析:可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知:n0=n2+1,则n= n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n= 2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2,合并成一个公式:n0=[(n+1)/2 ],就可根据完全二叉树的结点总数计算出叶子结点数。本题计算得:384。
  • 55. 二叉树及其性质具有n个结点的完全二叉树的深度为[log2n]+1
  • 56. 例题具有2000个结点的二叉树,其深度至少为_________。 答案:11
  • 57. 二叉树及其性质如果含有n 1个节点的二叉树的高度为[log2n]+1,将其所有结点按层次序编号,则对于任一节点j(1j  n),有 如果j=1,则节点j是树的根,无双亲;如果j>1,则其父节点parent(j)是节点[j/2] 如果2j>n,则节点j无左子节点;否则其左子节点为2j 如果2j+1>n,则节点j无右子节点;否则其右子节点为2j+1 证明
  • 58. 完全树的数组形式存储完全树的数组形式存储算法 将其编号为i的结点元素存储在一维数组下标为i-1的分量中
  • 59. 例题已知数组[20,30,19,87,30,40]表示一棵完全二叉树,请画出该树。
  • 60. 练习答案
  • 61. 树的遍历树的遍历 按某种搜索路径巡访树中每个结点,使每个结点均被访问一次仅且一次 二叉树的遍历可分为前序、中序、后序、层次序等 普通树的遍历可以分为先根、后根、层次序等
  • 62. 树的遍历二叉树的遍历 前序、中序、后序定义 层次序:从上而下,从左至右 常见问题 已知树写遍历结果 已知遍历结果画树 依据:二叉树的前序和中序遍历可以唯一确定一棵二叉树 思路:前序定根,中序定左右 递归和非递归算法实现
  • 63. 例题写出左图所示二叉树的前序、中序、后序、层次序遍历结果
  • 64. 例题答案前序:ABDCEFG 中序:DBAECFG 后序:DBEGFCA 层次序:ABCDEFG
  • 65. 例题假设一棵二叉树的前序遍历为EBADCHGFIKJ,中序遍历为ABCDEFGHIJK,请画出该树。
  • 66. 例题答案
  • 67. 树的遍历普通树的遍历 前根:先遍历根结点,再依次前根遍历各棵子树 后根:先后根遍历各课子树,再遍历根结点 已知树写遍历结果 已知遍历结果画树 思路:先根定根,后根定子树
  • 68. 例题写出如右图所示树的先根、后根、层次序遍历结果
  • 69. 例题答案前序: ABECFGHD 后序:EBFHGCDA 层次序:ABCDEFGH
  • 70. 练习给出如图所示树的先根、后根和层次序遍历结果
  • 71. 练习答案前根:ABEFHIGCJKLDMNOQP 后根:EHIFGBKLJCNQOPMDA 层次序:ABCDEFGJMHIKLNOPQ
  • 72. 例题画出和下列已知序列对应的树T: 树的先根次序访问序列为GFKDAIEBCHJ 树的后根次序访问序列为DIAEKFCJHBG
  • 73. 例题答案
  • 74. 普通树与二叉树的转换对于任意k次树到相应二叉树的转换算法 对于具有子节点n1,n2…nk的节点n,将n1作为其左子节点,且kj+1作为kj(1 j  k-1)的右子节点 思路:“不同层在左,同层在右”
  • 75. 普通树与二叉树的转换对于任意森林到相应二叉树的转换算法为 设T=(T1,T2…..Tm)为m(m0)棵树的序列,而BT (T1,T2…..Tm)为相应的二叉树,则 如果m=0,则BT为空树 如果m>0,则T1的根节点就是BT的根节点,而BT的左子树是T1的子树T11,T12…T1K转换成的BTl(T11,T12…T1K),其右子树为BTr(T2…..Tm)
  • 76. 例题将下页图所示森林转换为等价的二叉树
  • 77. 例题
  • 78. 例题答案
  • 79. 练习将如图所示树转换为二叉树
  • 80. 练习答案
  • 81. Huffman树Huffman树: 又称最优树,是一类带权路径长度最短的树 基本概念: 树的路径长度:从根到每一结点的路径长度之和。 结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度:树中所有叶子结点的带权路径长度之和,通常记做WPL。
  • 82. Huffman树基本概念: 假设有n个权值wi,试构造一棵有n个叶子结点的二叉树,每个叶子的结点带权为wi,则其中WPL最小的二叉树称为最优二叉树或赫夫曼树 算法 见下页
  • 83. Huffman算法(1) 由给定的n个权值{w0, w1, w2, …, wn-1},构造具有n棵二叉树的集合F = {T0, T1, T2, …, Tn-1},其中每一棵二叉树Ti只有一个带有权值wi的根结点,其左、右子树均为空。 (2) 在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3) 在F中删去这两棵二叉树,加入新得的树。 (4) 重复(2) (3),直到F只含一棵树为止。这棵树就是赫夫曼树
  • 84. ZKFCUDL E2724323742421202 Z7 K24 F32 C37 U42 D42 L120 EStep 12 Z7 K24 F32 C37 U42 D42 L120 E92 Z7 K24 F32 C37 U42 D42 L120 E933Round 1Round 2例题
  • 85. 2 Z7 K24 F32 C37 U42 D42 L120 E93365Round 3
  • 86. 2 Z7 K24 F32 C37 U42 D42 L120 E9336579Round 4
  • 87. 2 Z7 K24 F32 C37 U42 D42 L120 E9336579107Round 5
  • 88. 2 Z7 K24 F32 C37 U42 D42 L120 E9336579107186Round 6
  • 89. 2 Z7 K24 F32 C37 U42 D42 L120 E9336579107186306Round 7 (final)
  • 90. Huffman编码编码:等长编码/不等长编码 前缀编码:若要设计长短不等的编码,则必须是任一个字符的编码抖不是另一个字符编码的前缀,这种编码叫做前缀编码 Huffman编码:以n种字符出现的频率做权,设计一棵赫夫曼树,由此得到的前缀编码称为Huffman编码
  • 91. 例题LetterFreqCodeBitsC3211104D421013E12001F24111115K71111016L421103U371003Z211110062 Z7 K24 F32 C37 U42 D42 L120 E933657910718630600000111111001
  • 92. 习题某通讯系统只使用8种字符a、b、c、d、e、f、g、h,其使用频率是0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11。构造以字符使用频率为权值的Huffman树,并给出相应的Huffman编码。
  • 93. 习题答案
  • 94. 习题答案A:0110 B:10 C:1110 D:1111E:110 F:00 G:0111 H:010
  • 95. 课程安排课程介绍 栈、队列和向量 树 查找 排序 图
  • 96. 查找 大纲描述: 查找的基本概念;对线性关系结构的查找,顺序查找,二分查找; Hash查找法,常见的Hash函数(直接定址法,随机数法),hash冲突的概念, 解决冲突的方法(开散列方法/拉链法,闭散列方法/开址定址法),二次聚集现象; BST树定义,性质,ADT及其实现,BST树查找,插入,删除算法; 平衡树 (AVL) 的定义,性质,ADT及其实现,平衡树查找,插入算法,平衡因子的概念; 优先队列与堆,堆的定义,堆的生成,调整算法;范围查询;
  • 97. 查找的基本概念查找表(search table): 具有同一类型数据元素(经常称为记录)的集合 查找表的基本操作有: 查找某个“特定”记录是否在表中 查找到后取出某个“特定”记录的各个数据项 向表中插入记录 从表中删除记录
  • 98. 查找的基本概念静态查找表(static search table): 仅用于查询的查找表。 动态查找表(dynamic search table): 若在查找过程中需同时插入表中不存在的记录;或者需要删除记录,则称之为动态查找表。 关键字/键值(key) : 记录某个数据项的值,用其可以标示该记录 当记录只有一个数据项时,其关键字即为该记录的值 如果一个key可以唯一标示一个就,则称之为主关键字(primary key),否则称之为次关键字(secondary key)
  • 99. 查找的基本概念查找(search): 在一个查找表中找出具有“特定”键值的那些记录 所谓查找成功是指在查找表中找到了满足条件的记录,此时一般会返回找到的记录,或者返回记录的位置信息,或者仅仅返回找到(true) 否则称为查找失败,此时一般返回空指针,或特殊值,或者仅仅返回没有找到(false),有时也会就此插入这个元素
  • 100. BST树定义,性质, 实现二叉排序树(Binary Sorted Tree) 又称二叉搜索树或二叉查找树 或者是一棵空树; 或者是具有下列性质的二叉树: 如果左子树非空,则左子树中所有节点的键值均小于它的根结点的值; 如果右子树非空,则右子树中所有节点的键值均大于它的根结点的值; 它的左右子树也都是二叉排序树。
  • 101. BST树定义,性质, 实现二叉排序树性质 如果对二叉排序树进行中序遍历,则得到一个从小到大排好序的列表,所以可以得到一种简单的排序方法叫做“树排序”(treesort)。 我们也可以根据这个性质定义二叉排序树为:如果一棵树按中序遍历为排好序的,则这棵树是二叉排序树。
  • 102. BST树查找,插入,删除算法BST树查找,插入,删除算法 画图 算法
  • 103. 例题已知BST树如左,请画出插入16,再删除36之后的BST树
  • 104. 例题答案
  • 105. 例题试求按关键字序列(12,1,4,3,7,8,1O,2)插入生成的二叉排序树
  • 106. 例题答案
  • 107. 练习假设结点序列F=(60,30,90,50,120,70,40,80),试用BST的插入算法,用F中的结点依次进行插入,画出由F中结点所构成的BST树T1;再用删除算法,依次删除40,70,60,画出删除后的BST树T2。
  • 108. 练习答案
  • 109. 平衡树平衡因子(balanced factor) 二叉树上任一节点的左子树高度减去右子树高度的差 AVL Tree,根据其三位发明者(Adelson-Velskii and Landis)的名字命名 一棵BST树中每个节点平衡因子的绝对值不超过1
  • 110. 平衡树基本思想 : 在插入或删除节点后对新树进行判断,如果新树已经变得不平衡,则通过旋转(rotation)的方法对树进行重组/改组(re-arrange),使得重组后的树在保持查找树特性的同时保持平衡 所谓旋转: 通过改变支撑点来维持平衡 顺时针旋转为右旋;逆时针旋转为左旋 可以进行连续的多次旋转
  • 111. 平衡树
  • 112. 算法代码及基本的时间复杂度分析查找方法平均时间顺序查找O(n)二分查找O(logn)BST查找O(logn)AVL查找O(logn)
  • 113. Hash查找法,常见的Hash函数哈希(Hash)函数: 在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。这个对应关系f为哈希函数。按这个思想建立的表为哈希表。 哈希函数的设定可以很灵活,只要使得任何关键字的哈希函数值都落在表长允许范围之内即可。
  • 114. Hash查找法,常见的Hash函数练习: 已知线性表关键字集合为:S = { and, begin, do, end, for, go, if, repeat, then, until, while},求哈希函数。 答案: H(key)=key[0] – ‘a’;即为关键字key中的第一个字母在字母表{a, b, c, ..., z}中的序号
  • 115. Hash查找法,常见的Hash函数直接定址法 直接取key或者key的某个线性函数值 h(key) = a*key +b, a,b为常数 如前面的例子,又如人口普查时使用年龄,出生年份等
  • 116. Hash查找法,常见的Hash函数除留余数法 选择一个适当的正整数P,用P去除关键字,取所得得余数作为散列地址,即:H(key) = key%P 方法的关键是选取适当的P。选择P最好不要是偶数,也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大素数比较好。 缺点: 整数相除速度较慢
  • 117. Hash查找法,常见的Hash函数如: m = 8,16,32,64,128,256,512,1024 P = 7,13,31,61,127,251,503,1019
  • 118. 解决冲突的方法对不同的关键字可能得到同一哈希地址,这种现象称冲突。具有相同函数值的关键字对该哈希函数来说称作同义词。 在一般情况下,冲突只能尽可能的少,而不能完全避免。
  • 119. 解决冲突的方法共同思想: 将具有相同函数值的记录存作一个链 闭散列方法/开址定址法 冲突记录存储在表内 开散列方法/链地址法 冲突记录存储在表外
  • 120. 解决冲突的方法基本思想 当冲突发生时,使用某种方法在散列表中形成一个探查序列(也称之为"链"),按此序列逐个单元的查找,直到找到一个指定的关键字或碰到一个开放的地址(单元为空)为止。 Hj = ( H(key) + dj ) MOD m 1 j m-1;m为hash表长度 dj为增量数列,各种方法的不同就区别在取不同的增量数列上
  • 121. 解决冲突的方法常用的增量数列: 线性探测法 二次探测法 伪随机法 再哈希法/二次哈希法 桶式散列法
  • 122. 解决冲突的方法线性探测法 取dj = 1,2,…m-1 将散列表看成是一个环形表。若地址为d(即H(key)=d)的单元发生冲突,则依次探查下述地址单元:d+1,d+2,......,m-1,0,1,......,d-1,直到找到一个空单元或查找到关键字为key的结点为止。若沿着该探查序列查找一遍之后,又回到了地址d,则无论是做插入操作还是做查找操作,都意味着失败。
  • 123. 解决冲突的方法线性探测法 缺点: 特别容易产生聚集 链非常长
  • 124. 解决冲突的方法拉链法 若选定的散列函数的值域为0到m-1,则可将散列表定义为一个由m个单链表的链表头指针组成的指针数组HTP(m),凡是散列地址为i的结点,均插入到以HTP(i)为头指针的单链表中。
  • 125. 26416815064436381251250 1 2 3 4 5 6 7 8 9 10 11 12若一组关键字为(26,36,41,38,44,15,68,12,06,51,25),散列函数定义为:H(key) = key%13。用拉练法建立的散列表为:
  • 126. 解决冲突的方法拉链法 优点: 不会堆积,所以平均查找时间较短 动态申请空间,适用于造表前无法确定表长的情况 删除处理简单快速 链长易控制,一般较短
  • 127. 解决冲突的方法负载系数的定义和作用 设key的数量为N,散列表的大小为M,则N/M称负载系数或装填因子(loadfactor),它表现了平均情况下每个链的长度 我们一般预先规定好这个值,然后当不够的时候再增加hash表的长度(re-hash),这样可以保证链的平均长度不超过负载系数
  • 128. 解决冲突的方法增加时一般作两倍的增加,而且增加后需要将所有的表元素全部重新求值放置(因为m变了) 一般取值为0.75
  • 129. 解决冲突的方法聚集(clustering)现象又称"二次聚集",指处理冲突中发生的两个第一个hash地址不同的记录争夺同一个后继hash地址的情况,常发生在有大量key对应于同一Hash函数值的情况下 聚集现象仅出现于使用"闭散列方法"时 当使用"线性探测法"时特别容易发生聚集现象,很容易使散列查询退化为对于链表或者数组的顺序查询
  • 130. 解决冲突的方法假设Hash函数为H(key)=key MOD 11,表中已经有key 17,60,29,此时分别占据6,7,5;然后再插入38 此时可以发现,当表中5,6,7都被占据后,凡是函数值为5,6,7,8的key都将争夺8这个位置!!
  • 131. 例题在初始为空的哈希表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN), 哈希函数为H(k)=i MOD 7,其中,i为关键字k的第一个字母在英文字母表中的序号,地址值域为[0:6],采用线性再散列法处理冲突。插入后的哈希表应该如_________B_______所示。( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON
  • 132. 例题若待散列的序列为(18,25,63,50,42,32,9),哈希函数为H(key)=key MOD 9,哈希表长度为9,与18发生冲突的元素有______________个 答案:2
  • 133. 例题已知一组关键字为(26,36,41,38,44,15,68,12,06,51,25),用线性探查法解决冲突构造这组关键字的散列表,假设利用除余法构造散列函数。
  • 134. 例题答案为了减少冲突,通常令装填因子α<1,在此我们取α=0.75。因为n=11,所以散列表长度m=high(n/α) = 15; 对于除余法,选P=13(小于15的最大素数),即散列函数为:H(key) = key%13。 按顺序插入各个结点:26: H(26) = 26/13 = 0 36: ...=10,41: ...=2,38: ...=12,44: ... =5 插入15时,其散列地址为2,由于2已被关键字为41的元素占用,故需进行探查。按顺序探查法,显然3为开放地址,故可将其放在3单元。类似的,68和12可分别放在4和13单元中
  • 135. 练习在地址空间为0-16的散列区中,对以下关键字构造两个hash表 : (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec) 使用开散列方法(此时请注明装载因子为多少) 使用闭散列方法(此时使用线性探测法) 此处设hash函数为H(x)=[i/2],其中i为关键字中第一个字母在字母表中的序号
  • 136. 练习答案0 A; 1 BC; 2 DE; 3 FG;4 HI;5 JK; 6 LM; 7 NO; 8 PQ; 9 RS; 10 TU; 11 VW; 12 XY; 13 Z Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec
  • 137. 练习答案0->Apr->Aug 2->Dec 3->Feb 5->Jan->Jun->Jul 6->Mar->May 7->Oct->Nov 9->Sep
  • 138. 练习答案012345678910111213141516AprAugDecFebJanMarMayJunJulSepOctNov
  • 139. 范围查询定义: 在指定集合中有多少记录的关键字是落在指定范围中 一维的情况: 记录可以看作直线上的点 问题可以看作有多少点落入指定线段区域中
  • 140. 课程安排课程介绍 栈、队列和向量 树 查找 排序 图
  • 141. 排序 大纲描述: 排序基本概念; 插入排序,希尔排序,选择排序,快速排序,归并排序,基数排序等排序算法基本思想; 算法代码及基本的时间复杂度分析; 堆的定义,堆的生成。
  • 142. 排序基本概念排序(Sorting) : 重排一个记录序列,使之成为按关键字有序 常见排序可分为以下五类: 插入排序(简单插入排序、希尔排序) 交换排序(冒泡排序、快速排序) 选择排序(简单选择排序、堆排序) 归并排序 计数排序(多关键字排序)
  • 143. 插入排序[46] 26 22 68 48 42 36 84 66 22* [26 46] 22 68 48 42 36 84 66 22* [22 26 46] 68 48 42 36 84 66 22* [22 26 46 68] 48 42 36 84 66 22* [22 26 46 48 68] 42 36 84 66 22* [22 26 42 46 48 68] 36 84 66 22* [22 26 36 42 46 48 68] 84 66 22* [22 26 36 42 46 48 68 84] 66 22* [22 26 36 42 46 48 66 68 84] 22* [22 22* 26 36 42 46 48 66 68 84]
  • 144. 希尔排序定义 Shell Sort 又称“缩小增量排序”(Diminishing Increment Sort),也是一种属于插入排序类的算法,但时间效率较其他排序方法有较大改进 基本思想是:先将整个待排记录序列分割为若干子序列分别进行直接插入排序,待整个序列的记录“基本有序”时,再对全体记录进行一次直接插入排序
  • 145. 冒泡排序交换排序的一种 依次比较相邻的两个待排序元素,若为逆序(递增或递减)则进行交换,将待排序元素从左至右比较一遍称为一趟“冒泡” 每趟冒泡都将待排序列中的最大关键字交换到最后(或最前)位置 直到全部元素有序为止/直到某次冒泡过程中没有发生交换为止
  • 146. 快速排序就平均时间而言,快速排序是目前被认为最好的一种内部排序方法,由C. A. R. Hoare发明 分治法(divide and conquer)思想的体现 Unix系统函数库所提供的标准排序方法 C标准函数库中的排序方法直接就命名为qsort()
  • 147. 快速排序基本思想: 是对冒泡排序的一种改进 选取一个轴值,然后根据此轴值通过一趟排序对记录集进行一次分割,然后对分割后产生的两个记录子集分别进行快速排序
  • 148. 快速排序基本概念: 轴值(pivot): 书上称枢轴 用于将记录集"分割"为两个部分的那个键值 分割(partition): 将记录集分为两个部分,前面部分记录的键值都比轴值小,后面部分的键值都比轴值大
  • 149. 快速排序
  • 150. 快速排序4938659776132749’38659776132749’27386597761349’27389776136549’27381397766549’27381376976549’273813 49 76 97 6549’49temp
  • 151. 例题写出对于结点序列(46,26,22,68,48,42,36,84,66)进行第一次分割后序列的情况,注意列出步骤的每一步。
  • 152. 例题答案【】26,22,68,48,42,36,84,66 36,26,22,68,48,42,【】,84,66 36,26,22,【】,48,42,68,84,66 36,26,22, 42, 48,【】, 68,84,66 36,26,22, 42,【】, 48, 68,84,66 36,26,22, 42,46, 48, 68,84,66
  • 153. 练习已知序列(2, 8, 7, 1, 3, 5, 6, 4),如果选用4作为枢轴,那么进行一次分割后序列表现是怎样的? 答案:2,3,1,4,7,5,6,8
  • 154. 练习对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序,以序列的第一个元素为基准元素得到的划分结果是__________________。 答案:13,38,27,49,76,97,65,50
  • 155. 简单 选择 排序 示 例4938659776132749’1338659776492749’1327659776493849’1327389776496549’1327384976976549’1327384949’9765761327384949’6597761327384949’657697
  • 156. 例题对数据元素序列(49,72,68,13,38,50,97,27)进行排序,前三趟排序结束时的结果依次为:第一趟:13,72,68,49,50,97,27;第二趟:13,27,68,49,38,50,97,72;第三趟:13,27,38,49,68,50,97,72;该排序采用的方法是———— 答案:简单选择排序
  • 157. 练习若对序列(49,38,65,97,76,13,27,50)采用选择排序法排序,则第三趟结束后序列的状态是___________________。
  • 158. 练习答案13,38,65,97,76,49,27,50 13,27,65,97,76,49,38,50 13,27,38,97,76,49,65,50
  • 159. 堆的定义,堆的生成1964年威洛姆斯(J. willioms)提出堆排序 属于树型选择排序,仅需要一个记录大小的辅助空间,每个待排序记录仅占有一个存储空间。
  • 160. 堆的定义,堆的生成定义: n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系时,称之为堆: ki≤k2i且ki≤k2i+1 或 ki≥k2i且ki≥k2i+1 等价的树的定义: 如果一棵完全二叉树,其中每个节点的键值不小于(或者不大于)其子树的所有节点的键值,则称这棵二叉树为(最大值/最小值)堆(max/min heap)
  • 161. 堆的定义,堆的生成101556253070101556253070小根堆示例
  • 162. 堆的定义,堆的生成705630251510705630251510大根堆示例
  • 163. 堆的定义,堆的生成堆排序: 若在输出堆顶的最值之后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素中的次小值,如此反腐执行,便能得到一个有序序列,这个过程称为堆排序。
  • 164. 堆的定义,堆的生成堆排序基本思想: 将记录集调整为堆 输出堆顶的最值记录 将剩下记录重新调整为一个堆 重复2,3直至所有记录被输出 堆排序关键问题: 如何将一个记录集调整为堆?
  • 165. 堆的定义,堆的生成堆生成/调整算法: 从树的最后一个非叶子节点开始,也就是从数组的第length/2-1个元素开始调整 每次比较当前节点和及其左右子节点,取三者中最大者作为根 按逆层次序考察,直至根节点,也就是数组的第一个元素
  • 166. 堆的定义,堆的生成堆排序算法: 先将初始堆调整成一个最大值堆; 然后将最值与最后一个元素对调,将去除最后一个元素后剩余的堆重新调整为一个最大值堆; 继续以上过程直至最后一个元素。
  • 167. 91884223241605139188422324160513(a)初始堆R[1]到R[8]堆的定义,堆的生成
  • 168. 13884223241605911388422324160591(b)第一趟排序之后堆的定义,堆的生成
  • 169. (c)重建的堆R[1]到R[7]88244223131605918824422313160591堆的定义,堆的生成
  • 170. 05244223131688910524422313168891(d)第二趟排序之后堆的定义,堆的生成
  • 171. (e)重建的堆R[1]到R[6]42241623130588914224162313058891堆的定义,堆的生成
  • 172. (f)第三趟排序之后05241623134288910524162313428891堆的定义,堆的生成
  • 173. (g)重建的堆R[1]到R[5]24231605134288912423160513428891堆的定义,堆的生成
  • 174. (h)第四趟排序之后13231605244288911323160524428891堆的定义,堆的生成
  • 175. (i)重建的堆R[1]到R[4]23131605244288912313160524428891堆的定义,堆的生成
  • 176. (j)第五趟排序之后05131623244288910513162324428891堆的定义,堆的生成
  • 177. (k)重建的堆R[1]到R[3]16130523244288911613052324428891堆的定义,堆的生成
  • 178. (l)第六趟排序之后05131623244288910513162324428891堆的定义,堆的生成
  • 179. (m)重建的堆R[1]到R[2]13051623244288911305162324428891堆的定义,堆的生成
  • 180. (n)第七趟排序之后05131623244288910513162324428891堆的定义,堆的生成
  • 181. 练习已知序列{88,91,42,23,24,16,5,13},用堆排序方法进行排序,求排序过程中堆的状况。
  • 182. 练习答案91,88,42,23,24,16,5,13 13,88,42,23,24,16,5,91 88,24,42,23,13,16,5,91 5,24,42,23,13,16,88,91 42,24,16,23,13,5,88,91 5,24,16,23,13,42,88,91 24,23,16,5,13,42,88,91 13,23,16,5,24,42,88,91
  • 183. 练习答案23,13,16,5,24,42,88,91 5,13,16,23,24,42,88,91 16,13,5,23,24,42,88,91 5,13,16,23,24,42,88,91 13,5,16,23,24,42,88,91 5,13,16,23,24,42,88,91
  • 184. 练习序列(4, 1, 10, 14, 16, 9, 3, 2, 8, 7 )是否是一个最大值堆?如果不是请将其调整为一个最大值堆,并且使用堆排序算法进行排序,写出过程中每步序列的变化状况。
  • 185. 归并排序Jon von Neumann于1945年提出 彻底的"分治法",完全的等分(相对于快速排序而言) 适用于巨量数据的排序 Java类库所提供的标准排序方法 所谓"归并"是指将两个或两个以上有序表合并为一个有序表的过程
  • 186. 归并排序(25) (57) (48) (37) (12) (92) (86)(25 57) (37 48) (12 92) (86)(25 37 48 57) (12 86 92)(12 25 37 48 57 86 92)
  • 187. 基数排序多关键字排序: 根据排序时首先选取高位低位的不同,可以分为 : 最高位优先(Most Significant Digit First,MSD) 主要通过递归实现 对人而言更自然 最低位优先(Least Significant Digit First,LSD) 主要通过分配,收集过程实现,重点研究 部分单关键字排序也可以当作多关键字排序来做 数字,字符串… 以r为基的排序
  • 188. 基数排序基数排序是一种典型的LSD排序方法,它利用“分配”和“收集”两种运算对单关键字进行排序 此时往往是把单关键字看成是由多个关键字复合而成的,且每个关键字的基都相等
  • 189. 基数排序基本思想: 设每个关键字有d位,基为r,共有n个记录;则开r个队列,每个队列长度为n,将记录分配到每个队列中去,然后再收集起来,做d次结束 共需n×r的空间
  • 190. 各种内部排序方法的比较排序方法平均时间最坏时间辅助存储稳定性简单排序O(n2)O(n2)O(1)稳定快速排序O(nlogn)O(n2)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)不稳定基数排序O(d(n+rd))O(d(n+rd))O(rd)稳定
  • 191. 课程安排课程介绍 栈、队列和向量 树 查找 排序 图
  • 192. 图 大纲描述: 图的基本概念; 图的存储结构,邻接矩阵,邻接表; 图的遍历,广度度优先遍历和深度优先遍历; 最小生成树基本概念,Prim算法,Kruskal算法; 最短路径问题,广度优先遍历算法,Dijkstra算法,Floyd算法;拓扑排序
  • 193. 图的基本概念和术语顶点、弧和边 出弧、入弧 邻接点 度、出度、入度 有向图、无向图 稀疏图、稠密图权、网 带权图、无权图 子图 连通图
  • 194. 图的存储结构常用方法 : 数组表示法/邻接矩阵 (Adjacency Matrix)法 邻接表(Adjacency List)法 邻接多重表** 十字链表法**
  • 195. 邻接矩阵设|V|=n 用一个n维矩阵V存储顶点标签 用一个n*n矩阵E存储顶点邻接关系 对于E中每个元素e[v][w],取值如下: 无权图 : 1 E 0 否则 带权图 : 权值 E且vw 0 v=w  否则
  • 196. 邻接矩阵对于无向图,邻接矩阵呈上/下三角形,可以只存储这部分内容 一般用0表示无向图的不邻接,而用表示有向图的不邻接 合适存储稠密图 合适如果图的主要功能是查询
  • 197. 邻接矩阵在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度,统计第 j 列 1 的个数可得顶点 j 的入度 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度
  • 198. 例题给出指定图的邻接矩阵
  • 199. 例题给出指定图的邻接矩阵
  • 200. 邻接表设|V|=n 对于每个顶点v,使用一个单链表存储所有与其邻接的顶点w 使用一个n维的数组存储所有单链表的表头
  • 201. 邻接表对于链表中每个节点,存储以下信息 : 顶点w的名字;弧的信息(比如说权);指向下个节点的引用 对于数组中每个元素,至少存储以下内容 : 节点v的名字;指向第一个邻接顶点节点的引用 合适如果经常要查询顶点的前驱,后驱以及插入,删除顶点或者弧/边 此外还有逆邻接表
  • 202. 邻接表在有向图的邻接表中,第 i 个边链表链接的边都是顶点 i 发出的边,也叫做出边表. 在有向图的逆邻接表中,第 i 个边链表链接的边都是进入顶点 i 的边,也叫做入边表. 带权图的边结点中须保存该边上的权值 cost
  • 203. 例题给出指定图的邻接表
  • 204. 例题给出指定图的邻接表
  • 205. 例题给出指定图的邻接表
  • 206. 图的遍历图的两种最基本遍历 : 深度优先遍历(depth-first traversal) 广度优先遍历(breadth-first traversal)
  • 207. 图的遍历对于深度优先遍历,顶点集合是一个栈类型集合 其最优先元素为栈顶元素 也可以使用递归方法 对于广度优先遍历,顶点集合为一个队列类型集合 其最优先元素为队列最前元素
  • 208. 例题给出下图的深度优先遍历子图
  • 209. 例题给出下图的广度优先遍历子图
  • 210. 最小生成树生成树 对于连通图G(V,E), 支撑树 T(V’,E’)为包含G中所有顶点的一个无回路连通子图,即具有如下性质: V’ = V E’有|V| -1条边 T是连通的,为一棵树 对于指定图G,其支撑树T不唯一
  • 211. 最小生成树最小生成树: 设有边带权无向图G,则其最小代价支撑树T必须满足: T为G支撑树 T所有边的权之和是G所有支撑树中最小的 图G的最小代价支撑树T不唯一,但所有T的边权和都相等
  • 212. 最小生成树两种算法: Prim算法: 逐步增长的方式建成一棵树 每次挑选一条代价最小且不会构成回路的边加入正在建造的MST树 Kruskal算法: 先建造一个最小代价边构成的森林,最后合并为一棵树 每次挑选顶点落在图中不同连通分量上且不会构成回路的代价最小的边,直至树建成
  • 213. Prim算法从一棵空树 T开始, 随机选一个顶点,然后初始化为U = {1), T ={}
  • 214. Prim算法选取一个顶点w 不在U中,且其到U中某个顶点v的边(v,w)的权最小,此时 U={1,3} T= {(1,3)}
  • 215. Prim算法如此循环往复: V= {1,3,4} E’= {(1,3),(3,4)} V={1,3,4,5} E’={(1,3),(3,4),(4,5)} …. V={1,3,4,5,2,6} E’={(1,3),(3,4),(4,5),(5,2),(2,6)}
  • 216. Prim算法最终得到: V={1,3,4,5,2,6} E’={(1,3),(3,4),(4,5),(5,2),(2,6)} 此时最小代价为: 1 + 3 + 4 + 1 + 1 = 10
  • 217. Kruskal算法
  • 218. Kruskal算法初始时,为6个顶点构成的森林F= {{1},{2},{3},{4},{5},{6}} 所有边都在堆中
  • 219. Kruskal算法选出最低代价边 (2,5) Find(2) = 2, Find (5) = 5 Union(2,5) F= {{1},{2,5},{3},{4},{6}} 1
  • 220. Kruskal算法选择最低代价边 (2,6) Find(2) = 2, Find (6) = 6 Union(2,6) F= {{1},{2,5,6},{3},{4}} 11
  • 221. Kruskal算法选择最低代价边 (1,3) Find(1) = 1, Find (3) = 3 Union(1,3) F= {{1,3},{2,5,6},{4}} 111
  • 222. Kruskal算法选择最低代价边 (3,4) Find(3) = 1, Find (4) = 4 Union(1,4) F= {{1,3,4},{2,5,6}} 1113
  • 223. Kruskal算法选择最低代价边 (4,5) Find(4) = 1, Find (5) = 2 Union(1,2) F= {{1,3,4,2,5,6}} 最后总代价 = 10 在本例中,最小支撑树是唯一的,但并不是所有情况都这样11134
  • 224. 最短路径路径长度(Path Length): 构成路径的边的数目 路径权值(Path Costs/Weights): 构成路径的边上权值之和 对于不带权有向图而言,路径权值即路径长度
  • 225. 最短路径最短路径问题: 单源最短路径问题(single-source shortest path) 有向图中任一顶点s到其他所有顶点路径权值最小的路径 不带权图: 宽度优先遍历算法 带权图: Dijkstra算法 每对顶点间最短路径问题(all-pairs shortest paths) 有向图中任意两顶点间路径权值最小的路径 n(n-1)/2次Dijkstra算法: 稀疏网的较好选择 Floyd算法,涉及求传递闭包问题 : 稠密网的较好选择
  • 226. 最短路径最短路径问题: 我们着重研究前一个问题,尤其是带权图的最短路径 需要考虑的因素: 带权 vs. 不带权 有回路 vs. 无回路 权仅为正值 vs. 权为任意值 ……
  • 227. Dijkstra算法v1v7v6v2v5v3v441210364228510Cost(起始顶点) = 0Cost(所有其他顶点) = 
  • 228. Dijkstra算法v1v7v6v2v5v3v44121036422851021Cost(v2) = 2 Cost(v4) = 1
  • 229. Dijkstra算法v1v7v6v2v5v3v44121036422851021
  • 230. Dijkstra算法v1v7v6v2v5v3v441210364228510233195Cost(v3) = 1 + 2 = 3 Cost(v5) = 1 + 2 = 3 Cost(v6) = 1 + 8 = 9 Cost(v7) = 1 + 4 = 5
  • 231. Dijkstra算法v1v7v6v2v5v3v4412103642285133195注意 : cost(v4)没有被修改是因为v4已经在U中了, 而cost(v5)也没有被修改,则是因为新的计算值并没有比原来更大02
  • 232. Dijkstra算法v1v7v6v2v5v3v441210364228513319502
  • 233. Dijkstra算法v1v7v6v2v5v3v441210364228513318502
  • 234. Dijkstra算法v1v7v6v2v5v3v441210364228513316502
  • 235. Dijkstra算法v1v7v6v2v5v3v441210364228510233165
  • 236. 拓扑排序321143322326341370378401421142找到一个合适的次序来进行 选课 比如: 142  143  378 370  321  341  322 326  421  401
  • 237. 拓扑排序基本概念: 设S为一个集合,R为S上一个关系,a,b,c为S中元素 若有(a,b) R和(b,c) R,则必有(a,c) R,R为传递关系 若没有(a,a) R,则称反自反关系 R为传递加反自反关系,则为半序关系 设R为S上一个半序关系,A=a1,a2,a3..an为S中元素一个序列,且当(ai,aj) R时有i
  • 238. 拓扑排序基本概念: 获得拓扑序列的过程称之为拓扑排序 只有有向无环图(directed acyclic graph/DAG图)才可能进行拓扑排序 对于一个特定的DAG图,拓扑排序不唯一 AOV (Activity On Vertices)网络: 对于一个图,用顶点表示活动,用有向边表示活动的前后次序(Vi 必须先于活动Vj进行)
  • 239. 拓扑排序算法基本思想: 在AOV网络中任选一个没有前驱的顶点v输出 从网络中删去v及所有以v为尾的有向边 重复1,2,直至 所有顶点都被输出,拓扑排序成功结束 所有留下顶点都有前驱顶点,此时说明该AOV网中存在回路,不是一个DAG图,拓扑排序失败
  • 240. 拓扑排序ABCFDE
  • 241. 拓扑排序ABCFDE选择顶点A
  • 242. 拓扑排序ABCFDEA
  • 243. 拓扑排序ABCFDE
  • 244. 拓扑排序ABCFDEB
  • 245. 拓扑排序ACFDEBC
  • 246. 拓扑排序AFDEBCD
  • 247. 拓扑排序AFEBCDEF
  • 248. 拓扑排序ABCDEFABCFDE算法结束
  • 249. Thank You! Good Luck!