《【期末复习、考研备考】数据结构与算法复习资料.docx》由会员分享，可在线阅读，更多相关《【期末复习、考研备考】数据结构与算法复习资料.docx（7页珍藏版）》请在金锄头文库上搜索。
1、考试知识点 1复习考试知识点2 考试方案 题型： 选择题(15*2)填空(10*2) 简答题(6*5) 程序设计题(10*2)考试知识点3重点问题讲解 时间复杂度 对于循环程序,一般看有几重循环例 i nt fun (i nt n) int i=1, s=1; whi le(sn) s+二+i ;/时间复杂度为 0 (n) return i;考试知识点4 for (i=1;i=n;i=2*i) printf ( i=%dn”，i) :/时间复杂度为 0 (Iog2 (n)解释:设循环执行x次i的值执行次数i*01i*12i*23 或X-1X注意：是趋近！用大0i=n 即为 2 (x-1) =
2、n 解得 x= (y+1) * (y+1) /时间复杂度为 0 (n)y+;解释:设循环执行a次y的值执行次数y 二01y=l2y =23 y=xa(y+1) (y+1)0x 即为(a+1) (a+1)=x 解得 a k2(k+1)-1(1)设节点数为n,层次数为k。故有1+2+4+2X=n1 _ 2k+1利用等比数列求和公式 有2*= 2。1,故n=log2(n+1)-11-2(2)设节点数为时2八化+1)-1,层次数为k其中最下层叶结点数为叶结点2,即为Ln/2J倒数第二层以上根结点个数为n-2f=2f-1,即为/2-1考试知识点 13练习：一棵完全二叉树有1000个结点，则它必有个叶子结
3、点，有个度为2的结点, 有个结点只有非空左子树，有个结点只有非空右子树。正确答案：全部叶子数=1000/2=500个。度为2的结点=叶子总数一1=499个。非空左子树二1非空右子树=0解析：因为最后一个结点坐标是奇数，所以必为左子树。有1个结点只有非空左子树，有 。个结点只有非空右子树。考试知识点 14例2：用二叉树表示算术表达式先序遍历结果+ */ABCDE一前缀表示法中序遍历结果A/B*C*D + E一中缀表示法后序遍历结果AB/C*D*E +一后缀表示法 层次遍历结果+ *E*D/CAB考试知识点 15习题：构造二叉树 已知二叉树的 先序序列ABDFCEHG 中序序列DBFAHECG 请
4、构造该二叉树。考试知识点 16习题：构造二叉树 已知二叉树的 后序序列DMFBHELGCA 中序序列DBMFAHECGL 请构造该二叉树。考试知识点 17 假设通信电文使用的字符集为a, b, c, d, e, f,字符在电文中出现的频度分别为：34, 5, 12, 23, 8, 18,试为这6个字符设计哈夫曼编码考试知识点 18图 图的基本概念 图的存储结构 邻接矩阵存储结构 邻接表 图的遍历 深度优先遍历 广度优先遍历 最小生成树 普里姆 克鲁斯卡尔算法 最短路径 狄克斯特拉算法考试知识点 192.邻接表存储结构下图操作的实现A考试知识点 202.邻接表存储结构下图操作的实现/以下3图神排
5、版,考试知识点 21注意看最小生成树的破圈法和避圈法优60只他 403侦_ (a) F Ja 一 cc 1 D G % CF(d)以 50 _40 SOO2 GE r(g)CA CCCB CD CG亍CF_ (b) _A CcS d cg4。?。、F(e)CC曾 D cge代F4050 30%C50xo454003 3(h)F图9-10普里姆算法构造最小生成树的过程考试知识点 22克鲁斯卡尔算法构造最小生成树的过程考试知识点 23至 *% 节狄输特拉算法求从J赞出A到其余各顶，的最短路径的过程考试知识点 24 画出此图，从A点出发，深度遍历该图考试知识点 25 试利用Dijkstra算法求图1中从顶点A到其他各顶点间的最短路径。要求用 图画出求最短路径的过程，并写出从A到其余顶点的最短路径及最短路径长
