软件设计师培训数据结构

1、数据结构1考点分析 模拟练习考纲解读主 要 内 容数据结构知识点复习2考 纲 解 读考纲要求数组、线性表（链表：单向链表、双向链表、循环链表）、队列、栈、树（二叉树、查找树、平衡树、线索树、堆）、图等的定义、存储和操作。Hash（存储地址计算、冲突的处理）。排序算法、查找算法、数值计算方法、字符串处理方法、数据压缩算法、递归算法、图的相关算法。算法与数据结构的关系、算法效率、算法设计、算法描述、算法复杂性。3考 纲 解 读考点分布时间分值考核要点2016.510栈、二叉排序树、二叉树的性质、图的遍历、折半查找、动态规划算法、贪心算法2015.510队列、栈、二叉树的遍历、折半查找、简单选择排序

2、、快速排序2015.1111栈、队列、矩阵的压缩存储、二叉树、图的遍历、关键路径、折半查找、插入排序、基数排序、算法时间复杂度2014.59队列、线性表、二叉树的顺序存储、折半查找、算法的时间复杂度、贪心算法2014.118线性表、二叉查找树、模式匹配、快速排序算法、哈夫曼树2013.59线性结构的时间复杂度、栈、队列、贪心算法和背包问题、分治算法、二叉树、哈希查找2013.119线性表的存储结构、循环队列、有向图拓扑序列、哈夫曼树、哈希表、插入排序、快速排序、动态规划算法、回溯法4考 点 分 析常用数据结构的性质、定义方式和存储方法；重要数据结构（树、二叉树、图）的性质、存储结构和访问方式；

3、排序算法、查找算法的基本过程及效率；各种算法（如贪心算法、回溯法等）的基本思想。5第一部分 线性表分值：0 1分 （每年） 分数比重：0% 10%重要知识点： 1、顺序表的结构特点 2、单链表的结构特点 3、双向链表的插入删除 4、循环链表的结构特点6第一部分 线性表线性表的特点：1）存在唯一的一个称为“第一个”的数据元素；2）存在唯一的一个称为“最后一个”的数据元素；3）除第一个之外，每个数据元素有且仅有一个前驱；4）除最后一个之外，每个数据元素有且仅有一个后继。7第一部分 线性表顺序表特点： 利用物理存储位置的相邻关系反应元素之间的次序关系优点： 1.无需为表示结点间的逻辑关系而增加额外的

4、存储空间； 2.可方便地随机存取表中的任一元素。缺点： 1.插入或删除运算不方便，需要移动大量的结点，其效率较低； 2.需要预先确定顺序表的最大表长，由于顺序表要求占用连续的存储 空间，存储分配只能预先进行静态分配。因此当表长变化较大时， 难以确定合适的存储规模。8第一部分 线性表单链表lista1d1a2d2a3d3a4d4物理状态逻辑状态d2d1d3d4a2a3a4a1d3d4d2优点： 1.链表动态存储分配的结构，能有效利用存储空间；。 2. 插入或删除时只需要修改指针，而不需要进行大量元素的移动。缺点： 1.必需为表示结点间的逻辑关系而增加额外的存储空间； 2.不能随机存取、访问数据元

5、素。特点：单链表中逻辑上相邻的数据元素在物理上不一定相邻。数据元素之间的逻辑关系通过链指针间接地反映出来。9第一部分 线性表双向链表特点：双向链表中查找某结点的直接前驱结点和直接后继结点的运算的 时间复杂度均为O(1) es bp a s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s; p-prior-next = p-next; p-next-prior = p-prior; a b c插入：删除：p10第一部分 线性表循环链表 循环链表(Circular Linked List)：链表中最后一个结点的指针域指向整 个链

6、表的头结点，从而使链表形成一个首尾相接的环形链表。特点：从链表尾部到链表头部比较方便。从表中任一结点出发均可找到 表中其它结点。判空：表尾判断：La1L an L-next= = L;p-next = L;reara1 aiai-1 an 采用尾指针的循环单链表开始结点的存储位置：rear-next-next 终端结点的存储位置：rear11第一部分 线性表真题 2011年11月 对于线性表(由n个同类元素构成的线性序列)，采用单向循环链表存储的特点之一是_。 A从表中任意结点出发都能遍历整个链表B对表中的任意结点可以进行随机访问C对于表中的任意一个结点，访问其直接前驱和直接后继结点所用时间相

7、同D第一个结点必须是头结点12第一部分 线性表真题 2013年11月以下关于线性表存储结构的叙述，正确的是(57)。A线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级B线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级C线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级D线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级13第一部分 线性表真题 2013年5月51采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为_。AO(1)、O(I) BO(1)、O(n)CO(n)、

8、O(1) DO(n)、O(n)14第一部分 线性表真题 2014年5月5715第一部分 线性表真题 2014年11月16分值：0 1分 （每年） 分数比重：0% 10%重要知识点： 1、栈的结构特点 2、队列的结构特点 3、双端队列与循环队列 4、串的存储结构、基本操作和模式匹配第二部分 栈、队列和字符串 17栈特点： 后进先出的线性表双向栈： 使两个栈共享一维数组SMAXNUM，利用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为0 和 MAXNUM-1，而它们的栈顶都往中间方向延伸的栈称为双向栈。在一端进行插入和删除操作的线性表。栈顶：允许插入和删除的一端。栈底：不允许插入

9、和删除的一端。a1a2a3an-1an入栈出栈栈顶元素栈底元素 概念：第二部分 栈、队列和字符串 自由区0MAXNUM-1lefttoprighttop18队列特点： 先进先出的线性表队列是只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。队尾(rear)：允许插入的一端叫做队尾。队头(front)：允许删除的一端叫做队头。第二部分 栈、队列和字符串 a1 a2 a3 an-1 an入队列出队列队尾元素队头元素概念：19双端队列分类： 1、 输出受限的双端队列（即一个端点允许插入和删除，另一个端点只 允许插入）； 2、 输入受限的双端队列（即一个端点允许插入和删除，另一个端点只 允

10、许删除）。 3、限定双端队列从某个端点插入的元素只能从该端点删除，则双端队 列就蜕变为两个栈底相邻接的栈了。第二部分 栈、队列和字符串 双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。a1a2aia0an-1端1端220优先级队列优先级队列是一种不同于先进先出队列的另一种队列，每次出队的是队列中最高优先级的元素。通常采用堆来实现。第二部分 栈、队列和字符串 21串的定义和基本运算第二部分 栈、队列和字符串 仅由字符组成的有限序列，是取值范围受限的线性表。空串；空格串；子串和子串的位置；主串；串相等。22串的存储结构第二部分 栈、队列和字符串 （1）定长顺序串：按照

11、预定义的大小，为每个定义的串变量分配一个固定长度的存储区（2）块链串：用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。例：串值为abcdef的结点大小为4的链串块链串注意事项：为了提高存储密度，可使每个结点存放多个字符。当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。会给串的连接操作带来一定的方便，对模式匹配操作不方便。虽然提高结点的大小使得存储密度增大，但是插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。a b c de f # # S23串的基本操作难掌握的部分第二部分 栈、队列和字符串 （1）串比较：

12、StrCompare (S, T) 若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0。 例如：StrCompare(data , state) 0（2）串联接：Concat (&T, S1, S2) 用 T 返回由 S1 和 S2联接而成的新串。 例如： Concate( T, man , kind ) 求得 T = mankind （3）求子串:SubString (&Sub, S, pos, len) 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。例如：SubString( sub, commander, 4, 3)求得 sub = man

13、 ；（4）串定位：Index (S, T, pos) 若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置；否则函数值为0。 假设 S = abcaabcaaabc, T = bca Index(S,T,1) = 2； Index(S,T,3) = 6；（5）串替换：Replace (&S, T, V) 用V替换主串S中出现的所有与（模式串）T 相等的不重叠的子串 假设 S = abcaabcaaabca ，T = bca ，若 V = x ， 则经置换后得到 S = axaxaax 24真题 2011年11月57第二部分 栈、队列和字符串 25

14、真题 2012年5月58在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示，若模式串p为“aaabaaa”，则其next函数值为（58）A. 0123123 B. 0123210C.0123432 D. 0123456第二部分 栈、队列和字符串 26真题 2012年11月57第二部分 栈、队列和字符串 27真题 2013年5月52设元素序列a,b,c,d,e,f经过初始为空的栈S后，得到出栈序列cedfba,则栈S的最小容量为 (52) A.3 B.4 C.5 D.6第二部分 栈、队列和字符串 28真题 2013年5月53 输出受限的双端队列是指元素可以从队列的两

15、端输入，但只能从队列的一端输出，如下图所示，若有e1,e2,e3,e4依次进入输出受限的双端队列，则得不到输出序列 (53)A.e4,e3,e2,e1 B.e4,e2,e1,e3 C.e4,e3,e1,e2 D.e4,e2,e3,e1第二部分 栈、队列和字符串 29真题 2013年11月58题设循环队列的定义中有front和size两个域变量，其中front表示队头元素的指针，size表示队列的长度，如下图所示（队列长度为3，队头元素为X，队尾元素为Z）。设队列的存储空间容量为M，则队尾元素的指针为（58）。（58）A.（Q.front+Q.size-1）B(Q.front+Q.size-1+

16、M)MC(Q.front-Q.size)D(Q.front-Q.size+M)M答案为B第二部分 栈、队列和字符串 30真题 2014年5月50第二部分 栈、队列和字符串 A 双端队列 B 31真题 2014年11月第二部分 栈、队列和字符串 32真题 2014年11月60第二部分 栈、队列和字符串 33真题 2015年5月57第二部分 栈、队列和字符串 34真题 2015年5月58第二部分 栈、队列和字符串 35真题 2015年5月62、63第二部分 栈、队列和字符串 36真题 2015年11月57第二部分 栈、队列和字符串 37真题 2016年5月57题?第二部分 栈、队列和字符串 38分

17、值：0 1分 （每年） 分数比重：0% 10%重要知识点： 1、数组的地址计算 2、数组的压缩存储 3、广义表的表示 4、广义表的表头、表尾第三部分 数组与广义表 39数组特点： 1.数组中的数据元素具有相同的数据类型。 2.数组是一种随机存取结构，只要给定一组下标，就可以访问与其对应的数组元素。 3.数组中的元素个数是固定的。基本操作存取、修改 对于数组A，一旦给定其维数 n 及各维长度bi（1in），则该数组中元素的个数和元素之间的关系就不再发生变化了，既不可以对数组做插入和删除操作，也不涉及移动元素操作。 第三部分 数组与广义表 多维数组和广义表是对线性表的扩展线性表中的数据元素本身又是

18、一个多层次的线性表。40数组的地址计算第三部分 数组与广义表 Locaij = Loca00 + ( n i + j ) size a00 a02 a03 a0j a0,n-1 a10 a11 a12 a1j a1,n-1 a20 a21 a22 a2j a2,n-1 Amn = ai,0 ai,1 aij am-1,0 am-1,1 am-1,2 am-1,n-1Locaij = Loca00 + ( m j + i ) size行序为主序：列序为主序：41特殊矩阵的压缩存储对称矩阵三角矩阵对角矩阵稀疏矩阵第三部分 数组与广义表 421、A = ( )2、B = ( e )3、C = ( a

19、, ( b , c , d ) )4、D = ( A , A , ( ) )5、E = ( A , B , C )6、F = ( a , F )表示广义表A是一个空表，其长度为0表示广义表B长度为1，只有一个原子项e表示广义表C长度为2，两个元素分别为原子项a 和子表(b , c , d)。表示广义表D长度为3，三个元素都是广义表，分别为A、A 和( )。表示广义表E长度为3，三个元素A、B、C都是广义表，代入值以后E=( ( ) , (e) , ( a, ( b , c , d ) ) )。表示广义表F长度为2，两个元素分别是原子项a和子表F。这是一个递归表，相当于无穷广义表 F=（a ,

20、F）= (a, (a, (a, , ) ) )。广义表的表示第三部分 数组与广义表 43广义表的长度定义为最外层包含元素个数。广义表的深度定义为所含括弧的重数;“原子结点”的深度为 0 ; “空表”的深度为 1 。广义表的表头、表尾第三部分 数组与广义表 任何一个非空广义表 GL = ( d1, d2, , dn )均可分解为 表头 Head(GL) = d1 和 表尾 Tail(GL) = ( d2, , dn)例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = (

21、 ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )44真题 2011年11月21若二维数组arr1.M，1.N的首地址为base，数组元素按列存储且每个元素占用K个存储单元，则元素arri，j在该数组空间的地址为_。Abase+(i-1)*M+j-1)*KBbase+(i-1)*N+j-1)*KCbase+(j-1)*M+i-1)*KDbase+(j-1)*N+i-1)*K

22、第三部分 数组与广义表 45真题 2012年5月21第三部分 数组与广义表 46真题 2015年11月58第三部分 数组与广义表 47分值：1 7分 （每年） 分数比重：2% 20%重要知识点： 1、树和二叉树的定义 2、二叉树的重要性质 3、二叉树的遍历、线索二叉树 4、树与二叉树的转换 5、二叉树的应用哈夫曼树第四部分 树与二叉树 48树和二叉树的定义树的概念和逻辑特点： 1、有且仅有一个结点没有前驱结点,该结点为树的根结点。 2、除了根结点外,每个结点有且仅有一个直接前驱结点。 3、包括根结点在内，每个结点可以有多个后继结点。二叉树的概念和逻辑特点 1、每个结点的度都不大于2； 2、每个

23、结点的孩子结点次序不能任意颠倒。第四部分 树与二叉树 相关术语：结点、结点的度、叶子结点、分支结点、结点的层次、结点的层序编号、树 的度、树的高度（深度）、双亲结点、孩子结点、兄弟结点、堂兄弟结点、子孙结点、祖先结点。完全二叉树、满二叉树。49二叉树的重要性质性质1：在二叉树的第i层上至多有2i-1个结点(i1)。 性质2：深度为k的二叉树至多有2k-1个结点（k1）。 性质3：对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结 点数为n2，则n0= n2+1 。性质4：具有n个结点的完全二叉树深度为 log2n +1 。 性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左 到

24、右的顺序对二叉树中的所有结点从1开始顺序编号，则对 于任意的序号为i的结点有： (1)若i = 1, 则 i 无双亲结点 若i 1, 则 i 的双亲结点为i /2 (2)若2*i n, 则 i 无左孩子 若2*in, 则 i 结点的左孩子结点为2*i (3)若 2*i+1 n ,则i 无右孩子 若 2*i+1n, 则i的右孩子结点为2* i+1第四部分 树与二叉树 50二叉树的遍历第四部分 树与二叉树 ABCDKFGIJEH前序遍历序列: A, B, D, K, J, G, C, F, I, E, H中序遍历序列: D, B, G, J, K, A, F, I, E, C, H后序遍历序列:

25、D, G, J, K, B, E, I, F, H, C, A按层次遍历序列: A, B, C, D, K, F, H, J, I, G, E51例：已知结点的先序序列和中序序列先序序列：A B D E J C F I G中序序列：D B J E A F I C G 则可按上述分解求得整棵二叉树。 ADCIFGJBE第四部分 树与二叉树 例：已知结点的中序序列和后序序列中序序列：A B C E F G H D后序序列：A B F H G E D C 则可按上述分解求得整棵二叉树。 CADGEHFB52二叉树的存储结构1、二叉树的顺序存储结构2、二叉树的链式存储结构第四部分 树与二叉树 53线索

26、二叉树第四部分 树与二叉树 一.什么是线索二叉树 二.线索二叉树的构造 利用二叉链表中空的指针域指出结点在遍历序列中的直接前驱和直接后继;这些指向前驱和后继的指针称为线索, 加了线索的二叉树称为线索二叉树. 利用结点的空的左指针域存放该结点的直接前驱的地址,空的右指针域存放该结点直接后继的地址; 而非空的指针域仍然存放结点的左孩子或右孩子的地址.注：每棵二叉树都可以构造先序、中序和后序三种线索二叉树。54树的存储第四部分 树与二叉树 1、双亲表示法2、孩子表示法3、孩子兄弟表示法55树、森林与二叉树的转换第四部分 树与二叉树 树转换成二叉树： 1、树中所有相邻兄弟之间加一条连线。 2、对树中的

27、每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。 森林转换为二叉树的方法为： 1、将森林中的每棵树转换成相应的二叉树。 2、第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，即为由森林转换得到的二叉树。 ABECDFGHABCDEFIJGH56带权路径长度： 设二叉树有n个带权值的叶子结点，定义从二叉树的根结点到二叉树中所有叶子结点的路径长度li与相应叶子结点权值wi的乘积之和称作该二叉树的带权路径长度。WPL(T) =72+52+23+43+92 = 6075249ACBIGFDEHWPL =

28、哈夫曼树第四部分 树与二叉树 5752310515782511110000(011)(010)(10)(11)(00) 字符： s t a e c 字符出现的次数： 3 8 7 5 2 c: 010s: 011e: 00a: 10t: 11哈夫曼编码第四部分 树与二叉树 58堆第四部分 树与二叉树 1、堆的定义 大根堆或小根堆（大顶堆、小顶堆）2、堆的判断方法3、堆的应用 堆排序59真题 2011年5月12、20、21、59第四部分 树与二叉树 60真题 2011年5月12、20、21、59第四部分 树与二叉树 61真题 2011年11月60、61第四部分 树与二叉树 62真题 2012年5月

29、59第四部分 树与二叉树 63真题 2012年11月58若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKFEACD，则该二叉树为（58）第四部分 树与二叉树 64真题 2013年5月64 一个高度为h的满二叉树的结点总数为2h-1，从根结点开始，自上而下、同层次结点从左至右，对结点按照顺序依次编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4，5，6，7，依此类推。那么，在一棵满二叉树中，对于编号为m和n的两个结点，若n=2m+1,则 (64) A. m是n的左孩子 B. m是n的右孩子 C. n是m的左孩子 D. n是m的右孩子第四部分 树与二叉

30、树 65真题 2013年11月60以下关于哈夫曼树的叙述，正确的是（60）A.哈夫曼树一定是满二叉树，其每层结点树都达到最大值B.哈夫曼树一定是平衡二叉树，其每个结点左右子树高度差为-1，0，1C.哈夫曼树中左右孩子结点的权值小于父结点，右孩子结点的权值大于父结点D. 哈夫曼树中叶子结点的权值越小则距离树根越远，叶子结点的权值越大，则距离树根越近第四部分 树与二叉树 66真题 2014年5月58、59某二叉树如下图所示，若进行顺序存储（即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为i 的结点，其左孩子的下标为2i，右孩子的下标为2i+1），则该数组的大小至少为

31、（58）；若采用三叉链表存储该二叉树（各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针），则该链表的所有结点中空指针的数目为（59）。第四部分 树与二叉树 58：59：67真题 2014年11月第四部分 树与二叉树 68真题 2014年11月第四部分 树与二叉树 69真题 2015年5月59第四部分 树与二叉树 70真题 2015年11月59第四部分 树与二叉树 71真题 2016年5月58、59第四部分 树与二叉树 72真题 2016年5月59一棵二叉树的高度（即层数）为h，则该二叉树（59）A. 有2h个结点B. 有2h1一个结点C. 最少有2h1个结点D. 最多有2h1个结点第

32、四部分 树与二叉树 73分值：0 5分 （每年） 分数比重：6%重要知识点： 1、图的基本概念和存储结构 2、图的遍历 3、拓扑排序和最小生成树 4、关键路径 5、最短路径第五部分 图 74图的基本概念和存储结构图的基本概念： 无向图、有向图、无向完全图、有向完全图、稀疏图、稠密图、子图、有向图与无向图的顶点的度、网、回路和环、路径长度、简单路径、简单回路、连通图、连通分量、强连通图、强连通分量。图的存储结构 邻接矩阵(数组)表示法； 邻接表第五部分 图 BACDG1BADEG2C75图的遍历深度优先搜索：是指按照深度方向搜索，它类似于树的先根遍历。广度优先搜索：是指按照广度方向搜索，它类似于

33、树的按层次遍历。第五部分 图 v1v2v3v4v5v6v7v8v9v1v2v4v7v9v5v3v6v8BAEDCA B C D Ev1v2v3v4v5v9v6v8v7A B C E D76拓扑排序拓扑排序 将一个有向图中的所有结点排成一个序列，使得图中所有结点应存在的前驱和后继关系都能在队列中体现（前驱在前，后继在后）。过程 从AOV网中选择一个没有前驱的顶点并且输出； 从AOV网中删去该顶点并且删去所有以该顶点为尾的弧； 重复上述两步，直到全部顶点都被输出; 第五部分 图 C1C2C3C4C6C5C7拓扑序列：C1, C2, C3, C4, C5, C6, C7 77最小生成树概念 生成树是

34、连通图上的一个极小连通子图。最小生成树是一个连通网中所有生成树中各边权值之和最小的生成树。最小生成树的算法： 1、普里姆算法 2、克鲁斯卡尔算法第五部分 图 abdcef6155542663abdcef15342abdcef153255478关键路径概念 从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键路径上的活动叫关键活动。 关键路径的求法： 事件的最早发生时间 vek 事件的最迟发生时间 vlk 活动的最早开始时间 ei 活动的最晚开始时间 li第五部分 图 v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4

35、a5=1a6=2a3=5a2=479第五部分 图 v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4vekv2v7v6v5v4v1v3v9v8064577161418a2a7a6a5a4a1a3a9a8ei000645777a10a11161480第五部分 图 v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4li10778663201614a2a7a6a5a4a1a3a9a8a10a11v2v7v6v5v4v1v3v9v8vlk18141

36、6107866081最短路径分类1、求图中的一个结点到其他结点的最短路径。2、求图中任意两点间的最短路径。最短路径的求法： 迪杰斯特拉(Dijkstra)算法 Floyd算法第五部分 图 BAEDC105030101002060S=A, B, D, C, EAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60BAEDC10503010100206082最短路径分类1、求图中的一个结点到其他结点的最短路径。2、求图中任意两点间的最短路径。最短路径的求法： 迪杰斯特拉(Dijkstra)算法 Floyd算法第五部分 图 abd53863c1

37、2283真题 2011年5月60第五部分 图 84真题 2011年11月59第五部分 图 85真题 2012年5月60第五部分 图 86真题 2012年11月60拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点Vi到Vj有一条路径，则顶点Vi必然在顶点Vj之前。对于下图所示的有向图，（60）是其拓扑排序。第五部分 图 A. 1234576B. 1235467C. 2135476D. 213456787真题 2013年11月59第五部分 图 88真题 2014年5月第五部分 图 89真题 2014年11月53、54第五部分 图 90真题 2015年11月6

38、1第五部分 图 91真题 2016年5月61第五部分 图 92分值：5 15分 （每年） 分数比重：10%重要知识点： 1、静态表查找顺序查找、折半查找 2、动态表查找二叉排序树 3、哈希表 4、插入类排序 5、交换类排序 6、选择类排序 7、分配类排序第六部分 排序与查找 93查找基本概念： 静态查找 ：不涉及插入和删除操作的查找 。 动态查找 ：涉及插入和删除操作的查找。 平均查找长度：将查找算法进行的关键码的比较次数的数学期望 值定义为平均查找长度。计算公式为： 其中：n ：问题规模，查找集合中的记录个数； pi ：查找第i个记录的概率； ci ：查找第i个记录所需的关键码的比较次数。第

39、六部分 排序与查找 94静态查找顺序查找：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。折半查找：在有序表中，取中间元素作为比较对象 1、若给定值与中间记录的关键字相等，则查找成功； 2、若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。 3、不断重复上述过程，直到查找成功，或所查找的区域无记录(lowhigh)，查找失败。 前提：线性表中的记录必须按关键字有序；必须采用顺序存储。第六部分 排序与查找 95

40、动态查找二叉排序树定义：一棵二叉树中，每一个结点的左子树上的结点都比它小，右子树 上的结点都比它大。这种二叉树称为二叉排序树。二叉排序树的查找：从根结点开始比较，如果比根结点的值小，则到根结点的左子树上去查找；比根结点大，到根结点的右子树上去查找；与根结点相等，说明查找成功。依此类推，直到所要查找的结点为空，说明查找失败。二叉排序树的构造：将二叉排序树初始化为一棵空树，然后按照顺序逐个读入元素，每读入一个元素，就建立一个新的结点插入到当前已生成的二叉排序树中，即调用上述二叉排序树的插入算法将新结点插入。直到所有结点插入完成，二叉排序树就构造完成了。 注：若二叉排序树为空树，则新插入的结点为新的

41、根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。第六部分 排序与查找 96动态查找二叉排序树结论：对同样一组数据元素，如果输入的顺序不同，则所建的二叉树 形态也不同。特点： 1、一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列; 2、每次插入的新结点都是二叉排序树上新的叶子结点; 3、找到插入位置后，不必移动其它结点，仅需修改某个结点的指针； 4、在左子树/右子树的查找过程与在整棵树上查找过程相同； 5、新插入的结点没有破坏原有结点之间的关系。第六部分 排序与查找 练习：关键字的输入顺序为：45, 24 , 53 , 12 , 28 , 90，和 24, 53

42、, 90, 12, 28, 45 ，分别构造二叉排序树97动态查找二叉排序树的删除1. 若结点p是叶子，则直接删除结点p；2. 若p结点只有左子树，或只有右子树，则 因为该结点只有左子树或只有右子树，也就是说，其后继只有一个分支。删除该结点时，只要将被删除结点的唯一后继（左子树或右子树）直接链接到被删除结点的位置即可。3. 若结点p的左右子树均不空： 首先找到p结点在中序序列中的直接前驱s结点，然后用s结点的值，替代p结点的值，再将s结点删除,因为s的右指针一定为空，所以只要把s的左孩子链接到s结点本身的位置即可。第六部分 排序与查找 98 哈希表定义： 在元素的关键字k 和元素的存储位置p

43、之间建立一个对应关系H，使得p=H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关键字直接存取元素的目的。这种查找的方法称为哈希法。 哈希函数设计原则： 计算简单。哈希函数不应该有很大的计算量，否则会降低查找效率。 函数值即哈希地址分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。第六部分 排序与查找 99 哈希表冲突：对于两个不同关键码 kikj，有H(ki)H (kj)，即两个不同的记录需要存放在同一个存储位置。哈希函数冲突的处

44、理方法： 1、开放定址法 (再散列法)：线性探测再散列、二次探测再散列； 2、再哈希法：同时构造多个不同的哈希函数，当哈希地址发生冲突时，再用其他哈希函数来计算地址，直到冲突不再产生。 3、链地址法：将所有哈希地址为i的元素构成一个单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在这个链中进行。 4、建立公共溢出区法：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。 第六部分 排序与查找 100 哈希表装填因子：哈希法中影响关键字比较次数的因素有三个：哈希函数、处理冲突的方法以及哈希表的装填因子。哈希表的装填因子的定义如下： 可描述哈希

45、表的装满程度。 越小，发生冲突的可能性越小； 越大，发生冲突的可能性也越大。 第六部分 排序与查找 哈希表中元素个数哈希表的长度101 基本概念内部排序：整个排序过程完全在内存中进行，称为内部排序。 外部排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。排序的稳定性：相同关键字的相对位置关系在排序过程中没有发生变化者，则称所用的排序方法是稳定的 ；反之，则称为不稳定的。第六部分 排序与查找 102 插入类排序直接插入排序：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全

46、部记录排好序为止。折半插入排序：以折半查找和直接插入排序两种方法结合起来实现排序；希尔排序：根据不同的间距di 将元素分成组，在各组内进行直接插入排序，di 的值是由大到小，最后为1，即将所有元素放在一组里进行排序第六部分 排序与查找 103第六部分 排序与查找 直接插入46741653142640388665273414674165314264038866527342164674531426403886652734316465374142640388665273441416465374264038866527345141626465374403886652734614162640465374

47、38866527347141626384046537486652734814162638404653748665273491416263840465365748627341014162627384046536574863411141626273438404653657486希尔排序467416531426403886652734126341653142740388665467422614164034275338746546863141626273438404653657486104 交换类排序冒泡排序：快速排序：第六部分 排序与查找 快速排序46741653142640388665273413

48、42716381426404686655374226271614343840467465538631416262734384046536574864141626273438404653657486105 选择类排序：简单选择排序、堆排序第六部分 排序与查找 简单选择 4674165314264038866527341147416534626403886652734214167453462640388665273431416265346744038866527344141626274674403886655334514162627347440388665534661416262734384074

49、866553467141626273438407486655346814162627343840468665537491416262734384046536586741014162627343840465365867411141626273438404653657486106归并排序基本思想：将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到 n/2 个长度为2的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。第六部分 排序与查找 (19) (13) (05)

50、 (27) (01) (26) (31) (16) (13,19) (05,27) (01,26) (16,31) (05,13,19,27) (01,16,26,31) ( 01, 05 , 13 , 16 , 19 , 26 , 27 , 31 )107分配类排序基本思想：设待排序的数据元素关键字是m 位d 进制整数（不足m位的关键字在高位补0），设置d个桶，分别编号为0,1,2,d-1。 1、首先按关键字最低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为

51、一次基数排序； 2、 再对一次基数排序得到的序列按关键字次低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素； 这样的过程重复进行，当完成了第m 次基数排序后，就得到了排好序的数据元素序列。第六部分 排序与查找 108数据元素的关键字序列为710,342,045,686,006,841,429,134,068,2648411342231342644045568600667068871004299放置710142921343841342045452640686768680060900671042913484134204526406

52、8686收集后的新序列:放置1341264234234294568667107841800604506809006045068134264342429686710841收集后的新序列:放置710841342134264045686006068429收集后的新序列:(a)第一趟基数排序 (b)第二趟基数排序 (c)第三趟基数排序 109排序方法最好情况平均时间最坏情况稳定性直接插入O(n)O(n2)O(n2)简单选择O(n2)O(n2)O(n2)冒泡O(n)O(n2)O(n2)快速O(nlog2n)O(nlog2n)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)归并O(n

53、log2n)O(nlog2n)O(nlog2n)基数O(d(n+rd)O(d(n+rd)O(d(n+rd)第六部分 排序与查找 各种排序方法性能比较110真题2011年5月58、61、65 第六部分 排序与查找 111真题2012年5月61 第六部分 排序与查找 112真题2012年11月59、61、62、63在13个元素构成的有序表M1.13中进行折半查找（向下取整），若找到的元素为M4，则被比较的元素一次为（59）.A. M7、M3、M5、M4 B. M7、M5、M4C.M7、M6、M4 D.M7、M4第六部分 排序与查找 113真题2012年11月59、61、62、63下图所示为一棵N阶

54、B树，N最有可能的值为（61）。第六部分 排序与查找 A. 1 B. 2 C. 3 D.4114真题2012年11月59、61、62、63将数组1，1，2，4，7，5从小到大排序，若采用（62）排序算法，则元素之间需要进行的比较次数最少，共需要进行（63）次元素之间的比较。 (62) A.直接插入排序 B.归并 C.堆 D. 快速（63） A.5 B.6 C.7 D. 8第六部分 排序与查找 115真题2013年5月65第六部分 排序与查找 以下关于哈希(Hash,散列)查找叙述中，正确的是(65)。A.哈希函数应尽可能复杂些，以消除冲突B.构造哈希函数时应尽量使关键字的所有组成部分都能起作用

55、C.进行哈希查找时，不再需要与查找表中的元素进行比较D.在哈希表中只能添加元素不能删除元素 116真题2013年11月61、62、63 第六部分 排序与查找 117真题2014年5月61 第六部分 排序与查找 118真题2014年11月61、62、63 第六部分 排序与查找 119真题2015年5月60、61、64、65 第六部分 排序与查找 120真题2015年5月60、61、64、65 第六部分 排序与查找 121真题2015年11月60、64、65 第六部分 排序与查找 122真题2016年5月58、60 第六部分 排序与查找 123真题2016年5月58、60 第六部分 排序与查找 1

56、24分值：2 16分 （每年） 分数比重：22%重要知识点： 1、时间复杂度 2、穷举法、迭代法、递推法、递归法、 分治法、动态规划法、回溯法、贪心法第七部分 算法 125算法第七部分 算法 算法的5个重要特性： 有穷性、确定性、可行性、输入、输出。“好”的算法的目标： 正确性、可读性、健壮性、效率与低存储需求。算法的表示： 自然语言、流程图、程序设计语言、伪代码。时间复杂度： 126 蛮力法（穷举法）蛮力法(brute force method)：也称穷举法(enumerate)法，是蛮力策略的一种表现形式。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有

57、时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。用蛮力法解决问题，通常从两个方面进行算法设计： 1、找出穷举范围：分析问题所涉及的各种情况。 2、找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。应用：顺序查找、简单选择排序、冒泡排序、0/1背包。第七部分 算法 127 迭代法迭代法是用于求方程或方程组近似根的一种常用算法设计方法。设方程为f(x) = 0，用某种数学方法导出等价的形式x= g(x)，然后按以下步骤执行：1）选一个方程的近似根，赋给变量x0;2）将x0的值保存于变量x1，然后计算g

58、(x1)，并将结果存于变量x0;3）当x0与x1的差的绝对值还不小于指定的精度要求时，重复步骤2）的计算；4）若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。第七部分 算法 128 递推法递推法是利用问题本身所具有的一种递推关系求问题的一种方法。所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。可用递推的算法求解的题目一般有以下两个特点： 1）问题可以划分成多个状态； 2）除初始状态外，其他各个状态都可以用固定的递推关系式来表示。如：整数的阶乘、Fib