2014数据结构复习.pdf

《2014数据结构复习.pdf》由会员分享，可在线阅读，更多相关《2014数据结构复习.pdf（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！2014 下数据结构复习提纲 第 1 章 绪论 有关术语；算法、算法复杂度的分析和计算方法 例题：1下面算法的时间复杂度为 O(n)。int f(unsigned int n)if(n=0|n=1)return 1;else returen n*f(n 1);2for（i=1，s=0；i=n；i+）t=1；for(j=1；jnext=s;s-next=p）；注意在某个已知结点前插需要执行的语句？欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！2注意循环（链

2、）队列的判空和判满的条件？（看书理解！）3对于一个具有 n 个结点的单链表，在已知的结点 p 后插入一个新结点的时间复杂度为 O(1)，在给定值为 x 的结点后插入一个新结点的时间复杂度为 O(n)。4.在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头指针和队尾指针，则判断队满的条件为(rear+l)n=front。执行出队操作后其头指针 front 如何?5.线性表采用链式存储时，结点的存储地址连续与否均可;6.链式栈删除栈顶元素的操作序列为 top=top-next.7.在单链表中，指针 p 指向元素为 x 的结点，实现“删除 x 的后继”的语句是p-n

3、ext=p-next-next.8.判定“带头结点的链队列为空”的条件是 Q.front=Q.rear.9.假设以数组 seqnm存放循环队列的元素，设变量 rear 和 quelen 分别指示循环队列中队尾元素的位置和元素的个数。则队满的条件表达式为 quelen=m；队空的条件表达式 quelen=0；队头元素位置的表达式(rear-quelen+m)%m 第 6 章 树和二叉树 树和二叉树的定义、完全二叉树及其性质、存储表示及遍历算法（递归和非递归）、哈夫曼树的概念。例题：1在一棵二叉树中，度为 0 的结点个数为 n0，度为 2 的结点个数为 n2，则 n0=n2+1。欢迎您阅读并下载本

4、文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！（完全二叉树性质）例：二叉树上叶结点数等于（双分支结点数加 1）;对于一棵具有 n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 2n 个，其中 n-1 个用于链接孩子结点，n+1 个空闲着。2.n 个权构成一棵 Huffman 树，其节点总数为 2n-1.3.设用权 6，10，13，14，20，37 构造 Huffman 树，则该 Huffman 树的根结点的权值为 100.（仔细验算构造 Huffman 树）4.一棵深度为 k 的满二叉树的结点总数为 2k-1，一棵深度为 k 的完全二叉树的结点总

5、数的最小值为 2k-1，最大值为 2k-1。5.深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树.6.设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF，则该二叉树的前序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，后序遍历序列为 DEBFCA.7.一棵完全二叉树中共有 768 结点，则该树中共有 384 个叶子结点。8.深度为 k 的完全二叉树中最少有 2k-1个结点。9.二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是任一结点无右孩子 第 7 章 图 图的存储及遍历算法，图的有关概念，最短路径,（最小）生成树 例题：1由一个具有 n 个顶

6、点的连通图生成的最小生成树中，具有 n-1 条边。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！2有向图 G 的存储结构用邻接矩阵 A 来表示，则 A 中第 i 行中所有非零元素个数之和等于顶点 i 的出度，第 i 列中所有非零元素个数之和等于顶点 i 的入度。3.若要把 n 个顶点连接为一个连通图，则至少需要 n-1 条边。4.连通图 G 中有 n 个顶点 e 条边，则对应的最小生成树上有 n-1 条边 5在一个图中，所有顶点的度数之和等于所有边数的 2 倍。6.在一个具有 n 个顶点的无向完全图中，包含有 n(n-1)/2 条边，在一个具有

7、n 个顶点的有向完全图中，包含有 n(n-1)条边。7.无向图 G 中有 n 个顶点 e 条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为 O(n2);用邻接表作为图的存储上述复杂度 O(n+e).8.在含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为 n22e.9.设有向图 G 中有 n 个顶点 e 条有向边，所有的顶点入度数之和为 d，则 e 和 d 的关系为 d=e.10.设某无向图中顶点数和边数分别为 n 和 e，所有顶点的度数之和为 d，则 e=d/2 11.掌握最小生成树算法.例如使用普里姆（Prim）算法以A为源点，构造下图的最小代价生成

8、树，画出各步的结果。12.已知有向图 G 如下所示，根据迪杰斯特拉算法求顶点 v0 到其他顶点的最短距离。终点 从 v0 到各终点的 d 值和最短路径的求解过程 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！i=1 i=2 i=3 i=4 v1 12(v0,v1)12(v0,v1)7(v0,v4,v1)v2 4(v0,v2)v3 9(v0,v3)8(v0,v2,v3)7(v0,v4,v3)7(v0,v4,v3)v4 5(v0,v4)5(v0,v4)vj v2 v4 v1 v3 s v0,v2 v0,v4 v0,v4,v1 v0,v4,v3 第 9

9、 章 查找 掌握二分（折半）查找，二叉排序树的概念及其上的插入和删除有何特点，掌握哈希查找。例题：1.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素 26 的比较次数为 4。2.有序表中进行二分查找，则比较一次查找成功的结点数有 1 个，比较两次查找成功有结点数有 2 个,比较三次 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！3理解并掌握二叉排序树的概念，会构造二叉排序树及查找、插入和删除操作。4.中序遍历二叉排序树可以得到一个从小到大的有序序列。5.设哈希表 HT 表长 m 为 13，哈

10、希函数为 H(k)=k MOD m，给定的关键值序列为19,14,23,10,68,20,84,27,55,11。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度 ASL。(1)表形态：(2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6 6.设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是 19/7.第 10 章 内部排序 掌握基本排序方法的实现思想。例题：1.假定对元素序列（7,3,5,9,1,12,8,15）进行快速排序，则进行第一次划分后，得到的左

11、区间中元素的个数为 3。2设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字 45为基准而得到的一趟快速排序结果是 42，40，55，60，80，85 考试题型：一.单项选择题（152 分=30 分）欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！二.填空题（102 分=20 分）1.实现数据 x 进栈程序填空；2.二叉树中各类结点个数及关系；3.关于无向图的度；4.无向图邻接矩阵中找邻接点；5.二叉树遍历;6.顺序循环队列元素个数;7.二叉排序树平均查找长度;8.哈夫曼树构造和哈夫曼树的高度;9.最小生成树构造及其

12、上权值之和;10.二叉排序树中插入一个新结点算法填空。三.解答题（56 分=30 分）1循环队列在特定设置下判满判空,计算元素位置；2.给出邻接矩阵,画出该图,画出深度优先生成树；3.填写出散列表和平均查找长度;4.求某顶点到其余各顶点的最短路径;5.构造一棵二叉排序树,画出删去结点之后的二叉排序树.四.算法阅读题（26 分=12 分）1.在带头结点的单链表中，删除数据元素的算法;2.中序遍历二叉树过程中实现对一些节点的其他操作.五、算法设计题（8 分）1.将一个简单的递归程序改写成非递归,实现相同功能.以上各例题中的答案并不保证完全正确，希望自己亲自验证。找到并对照书本上的相应内容仔细阅读 3 遍以上。切实理解和掌握每个知识点的实质，决不可以似是而非，侥幸过关。祝同学们考出好成绩！2020-2-8