DS笔试算法与数据结构复习资料 (2)

《算法与数据结构》复习重点 1、 第2章 程序性能 1、 给出一个程序段，会写出该程序段的时间复杂度； 2、 第3章 线性表 1、 顺序存储结构的特点 1 表中元素可以随机访问； 2 非表尾的插入和删除操作需要移动元素； 3 表空间无法动态扩充，需预先按最大空间分配，存储空间利用率低； 4 相邻元素的物理位置相邻 5 无需为维护表中元素的逻辑关系增加额外的存储空间 2、 若用数组实现表，设表元素总数为n，在第k个元素后插入一个新元素，需要后移的元素数目为n-k。设在表的任何合法位置上插入元素的概率均等，则插入操作所需要的元素移动平均次数为n/2。 3、 若用数组实现表，设表元素总数为n，删除第k个元素，需要前移的元素数目为n-k。设删除表的任何元素的概率均等，则删除操作所需要的元素移动平均次数为（n-1）/2。 4、 链式存储结构的特点 1 表元素分散存放，物理位置不一定相邻； 2 每个结点包含指向下一结点的指针域； 3 只能顺序搜索，不能随机访问； 4 插入和删除操作只需要通过修改指针实现，效率较高 5 不需为表预留空间，存储空间利用率高，表容量可动态扩充 6 每个结点中的指针域需占用额外空间 5、 在带哨兵结点的单循环链表中，设置尾指针last指向链尾结点，每个结点中的后继指针域为next，则判断表空的表达式为last->next==last；在带哨兵结点的双循环链表中，设置指针header指向哨兵结点，每个结点中的后继指针域为next,前驱指针域为prior，则判断表空的表达式为header->next==header或header->prior==header。 6、 在带哨兵结点的单链表的插入和删除操作中，链指针的修改 7、 理解静态链表 1 静态链表中的指针域又称为游标或模拟指针，存放下一元素在数组中的下标 2 多条静态链表可共用一个数组空间 3 在数组空间中，静态链表中的元素可以分散存放，即相邻元素的下标不一定相邻 4 静态链表的扩充受到数组空间容量的限制 3、 第4章 栈 1、 栈的操作原则为先进后出或后进先出，插入和删除操作均在栈顶方向上进行。 2、 用数组实现栈的入栈和出栈函数； 3、 用数组实现栈的优缺点： 1 栈上的基本操作都能在常量时间内完成，效率较高； 2 为避免栈发生溢出，通常需要预置一个较大栈空间，存储空间利用率较低； 为提高空间利用率，可让多栈共享数组空间； 4、 用链表实现栈的特点：链栈空间可以动态扩充 4、 第5章 队列 1、 队列的操作原则是先进先出或后进后出，插入操作在队尾进行，删除操作在队头进行 2、 若用循环数组实现队列，设置front指向队头元素前一单元，rear指向队尾元素，并采用总剩一个单元不利用的方法区分满空状态，则当front和rear满足什么关系时队列为空，满足什么关系时队列为满？ 3、 用循环数组实现队列的入队和出队函数。 5、 第6章 树 1、 树的基本概念，包括树的度、叶结点或终端结点、分支结点、内部结点、兄弟、堂兄弟、祖先、子孙、树的高度、有序树、无序树。 2、 树的表示法 1 父结点数组表示法可以快速找到结点的父结点，但查询儿子结点和兄弟结点可能要遍历整个数组； 2 在儿子表示法中，若采用定长结点的多重链表结构，则表示一棵有n个结点度为d的树必有nd-(n-1)个空链域 3 儿子链表表示法适合于查找子结点，但不适合于查找父结点和兄弟结点 4 带双亲的儿子链表表示法适合于查找子结点、父结点和兄弟结点 5 左儿子右兄弟表示法方便查找子结点和兄弟结点，但不方便查找父结点 6 给出一棵树，会用父结点数组表示法、儿子链表表示法、左儿子右兄弟表示法表示它。 3、 二叉树的概念 1 二叉树是有序树 2 度为2的树不一定是二叉树 3 度为2的有序树不一定是二叉树 4 子树有严格左右次序之分，且度≤2的树是二叉树 4、 具有3个结点的树有5种形态，具有3个结点的二叉树有3种形态。 5、 满二叉树的特点： 1 所有叶结点都集中在最底层 2 不存在度为1的结点 3 每一层上的结点数均达到最大值 4 所有分支结点都存在左子树和右子树 例题： ① 高度为8的满二叉树的结点总数为 255 。 6、 完全二叉树的特点： 1 叶结点只可能在层次最大的两层上出现 2 最下层的叶结点一定集中在该层的左端 3 度小于2的结点只可能位于最下两层 4 除最下层外，其余各层均满 5 度为1的结点只可能出现在倒数第二层 6 对任一结点，若其右分支下的子孙最大层次为s，则其左分支下的子孙的最大层次必为s或s+1 7、 二叉树的性质 1 具有n个结点的非空二叉树共有n-1个分支 2 非空二叉树的第i层上至多有2i-1个结点（i≥1） 3 高度为h的非空二叉树至多有2h-1个结点 4 高度为h的完全二叉树至多有2h-1个结点，至少有2h-1个结点 5 若非空二叉树有n0个叶结点，n2个度为2的结点，则n0= n2+1 6 具有n个结点的完全二叉树的高度为h= log2n +1。 7 具有n个结点的二叉树的最小高度为 log2n +1，最大高度为n。 8 若对具有n个结点的完全二叉树按照层次从上到下，每层从左到右的顺序进行编号，则编号为i的结点具有下列性质: ⅰ如果i=1，则结点i是二叉树的根，无父结点；否则父结点是 i/2 ⅱ如果2i>n，则结点i无左孩子（结点i为叶结点）；否则左孩子编号为2i ⅲ如果2i+1>n，则结点i无右孩子；否则右孩子为结点2i+1 例题：（以下题均设仅含一个结点的二叉树的高度为1） ①具有74个结点的完全二叉树，高度为 7 ，叶结点有 37 个。（设仅含一个结点的二叉树的高度为1） ② 已知二叉树中叶子数为40，仅一个孩子的结点数为20，则总结点数_99 _。 ③ 在含30个结点的完全二叉树中，对所有结点按层序从1开始编号（从上层到下层，每层从左到右），则编号为10的结点的左子结点编号为 20 ，右子结点编号为 21 ，父结点编号为 5 。 ④ 高度为11的完全二叉树至多有 2047 个结点，至少有 1024 个结点。 ⑤ 具有70个结点的完全二叉树的高度为 7 。 ⑥ 具有43个结点的二叉树的最小高度为 6 ，最大高度为 43 。 ⑦ 设在高度为h的二叉树（设仅有一个结点的二叉树高度为1）中只有叶结点和度为2的结点（没有度为1的结点），则该二叉树至多有 2h-1 个结点，至少有 2h-1 个结点。 8、 二叉树的存储结构 1 在二叉树的链式存储结构中，含有n个结点的二叉链表有n+1个空链域，含有n个结点的三叉链表有n+2个空链域。 9、 二叉树的前序、中序、后序遍历 1 给定一棵二叉树，能写出它的前序、中序、后序遍历序列； 2 给定一棵二叉树的前序和中序序列，能画出该二叉树并写出它的后序序列； 或给定一棵二叉树的后序和中序序列，能画出该二叉树并写出它的前序序列； 10、 线索二叉树 1 线索二叉树结点的lchild、ltag、rchild、rtag各域的含义 2 如何利用中序线索链表进行二叉树的中序遍历？如何利用后序线索链表进行二叉树的后序遍历？如何利用前序线索链表进行二叉树的前序遍历？ 11、 树、二叉树、森林的相互转换中的几个结论 1 前序遍历树与前序遍历与该树对应的二叉树具有相同的遍历结果 2 后序遍历树与中序遍历与该树对应的二叉树具有相同的遍历结果 3 前序遍历森林与前序遍历与该森林对应的二叉树具有相同的遍历结果 4 后序遍历森林与中序遍历与该森林对应的二叉树具有相同的遍历结果 6、 第7章 优先队列 1、 最大堆和最小堆的定义（理解） 2、 初始建堆操作的建堆过程；堆的插入操作中堆的调整过程；删除堆顶元素后堆的调整过程 3、 堆排序的时间复杂度为O(nlogn) 4、 堆排序的方法；堆排序是一种不稳定的排序方法 5、 左偏高树的左子树高度不一定大于右子树高度 6、 具有m个结点的左偏高树和左偏重树的最右路径长度最多为log2(m+1) 7、 左偏树不作为复习要点 7、 第8章 搜索树 1、 二叉搜索树的定义 2、 二叉搜索树的中序遍历序列是升序序列 3、 二叉搜索树上的查找操作过程，插入操作过程，删除操作中树结构的重组（重点掌握当被删结点存在左右子树时，树结构重组策略3。即用被删结点P的左子树中最右下结点S中元素替代被删元素，将S的左子树挂接为其父结点的右子树。） 4、 二叉搜索树上的前驱运算和后继运算的操作过程。 5、 平衡二叉树的定义，平衡因子的定义（平衡二叉树上结点的平衡因子绝对值不大于1） 6、 在含有n个结点的AVL树上执行搜索、插入、删除操作的时间复杂度为O(logn) 7、 AVL树上插入和删除操作中的平衡旋转操作不作为复习要点 8、 第9章 图 1、 图的基本概念，包括无向图、有向图、顶点的度、顶点的入度和出度、完全图、子图、简单路径、简单环、连通图、连通分量、强连通图、强连通分量、生成树。 1 连通分量是无向图中的极大连通子图 2 生成树是无向连通图的极小连通子图 3 在生成树中每两个顶点间有且仅有一条路径 4 具有n个顶点，少于n-1条边的图一定是非连通图 5 具有n个顶点，多于n-1条边的图中必存在环 6 具有n个顶点，n-1条边的图不一定是生成树 7 在无向图中，所有顶点的度数之和是无向边数的2倍 8 在有向图中，所有顶点的出度或入度之和等于有向边数 9 具有n个顶点的无向完全图具有n(n-1)/2条边；具有n个顶点的有向完全图具有n(n-1)条弧 例题： ① 具有18个顶点的无向完全图具有 153 条边。 ② 若含有32个顶点的无向图是一个环，则它有 32 棵生成树。 ③ 具有n个顶点的无向连通图的生成树含有 n-1 条边。 2、 图的存储结构 1 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵不一定对称。 2 有向图邻接矩阵的第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行和第i列非零元素的个数之和。 3 用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。 4 在无向图的邻接表中，第i个顶点的度为第i条链表中的结点数；在无向图的邻接表中，所有链表的结点总数是图中边数的2倍 5 在有向图的邻接表中，第i个顶点的出度为第i条链表中的结点数，为求结点的入度需要遍历整个邻接表。在有向图的邻接表中，所有链表的结点总数等于图中的有向边数 6 在有向图的逆邻接表中，第i个顶点的入度为第i条链表中的结点数 7 在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任两个顶点i、j间是否有边或弧相连，则需搜索第i条或第j条链表。 8 邻接表更适合于表示稀疏图，邻接矩阵更适合于表示稠密图。 9 给出一个图，会用邻接表或邻接矩阵表示该图 例题： ①含有n个顶点，e条边的无向图对应的邻接表中有 2e 个链结点（不包括邻接表的表头结点）。 ②含有n个顶点，e条弧的有向图对应的邻接表中有 e 个链结点（不包括邻接表的表头结点）。 3、 图的广度优先搜索和深度优先搜索 1 给出一个无向连通图，会写出它的深度优先序列和广度优先序列，会画出它的深度优先生成树和广度优先生成树。 2 广度优先搜索类似于树的层次遍历，深度优先搜索类似于树的先序遍历 3 从无向连通图的任一顶点出发进行一次深度优先搜索或广度优先搜索即可访问所有顶点 4 进行图的广度优先搜索时，需要用到队列这种数据结构 4、 求最小生成树的Prim算法 1 给出一个无向连通网，会使用Prim算法求出它的最小生成树，并能写出求解过程。理解课件中在Prim算法这一节给出的例题 5、 求单源最短路径的Dijkstra算法 给出一个有向赋权图，会使用Dijkstra算法求从指定源点到其余顶点的最短路径和最短路径长度，并能写出求解过程。理解课件中在Dijkstra算法这一节给出的例题 6、 拓扑排序 1 会对一个有向无环图进行拓扑排序 2 检查有向图是否存在回路的一种方法是对有向图进行拓扑排序。若所有顶点均包含在拓扑序列中，则有向图中必不存在环。 3 也可利用深度优先遍历进行拓扑排序，由某顶点出发进行深度优先遍历时，最先退出dfs过程的即出度为0的顶点，是拓扑序列中最后一个顶点。但深度优先遍历算法会忽略图中有向环的存在，对于存在有向环的图不能检测出环的存在。 7、 关键路径 1 对给定的AOE网，能计算出各顶点所代表事件的最早和最晚发生时间，各活动的最早开始时间、最晚开始时间和时间余量，能找出关键活动和关键路径，求出工程的工期。理解课件中在关键路径这一节给出的例题 2 只有在不改变关键路径的情况下，提高关键活动的速度才有效 3 提前完成非关键活动并不能加快工程的进度 8、二部图的完全匹配一定是最大匹配，但最大匹配不一定是完全匹配 9、 第10章 排序与选择 1、 给定一个乱序序列，能使用直接插入排序法、冒泡排序法、快速排序法、直接选择排序法、2路归并排序法、堆排序法对该序列进行排序，并写出每一趟排序的结果。 2、 直接插入排序法是稳定的，希尔排序法是不稳定的，冒泡排序法是稳定的，快速排序法是不稳定的，直接选择排序法是不稳定的，堆排序法是不稳定的，2路归并排序法是稳定的，基数排序法是稳定的。 考试题型及分值： 单选题 15个，每个2分，共30分 填空题 15空，每空1分，共15分 判断题 10个，每个1分，共10分 综合题 6个，共45分 PAGE 6