工程硕士专业课复习提纲.doc

《工程硕士专业课复习提纲.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、工程硕士专业课复习提纲第一章绪论抽象数据类型定义，数据结构研究内容，数据结构定义，数据定义第二章算法及时间复杂性时间复杂性定义，常用时间复杂性比较，简单程序的时间复杂性判断算法(Algorithm)：是对特定问题求解步骤的一种描述，它是指令(规则)的有限序列，其中每一条指令表示一个或多个操作。算法的特征:%1有穷性、②确定性、③能行性、④输入、⑤输出算法描述:①自然语言；②程序设计语言；③类语言;常见的时间复杂性及其比较0(1)v0(loglogn)v0(logn)<0(n)<0(nlogn)

2、)),则加法规则：Tl(n)+T2(n)=0(max{f(n),g(n)})乘法规则：Tl(n)*T2(n)=0(f(n)*g(n))1.表达式和赋值语句：O(1)2.语句序列:用加法规则，取耗时最多语句.3.条件语句:O(1)3.FOR语句:O(N*M)N为循环次数,M为体内时间最多的语句4.WHILE语句:找出与循环次数有关的变量，通过计算找出上下限.例：x=n;y=0;while(x>=(y+l)(y+l))y=y+i;时间复杂性为o(扁)①s=0;—f(n)=1;T2(n)=O(f(n))=0(1)常量阶%1for(i=l;i<=n;++i)(++x;s+=x;}—f(n

3、)=3n+l;Tl(n)=O(f(n))=O(n)线性阶%1for(i=l;i<=n;++i)for(j=l;j<=n;++j){++x;s+=x;}—f(n)=3n2+2n+l;T3(n)=O(f(n))=O(n2)平方阶%1for(i=l;i<=n;++i)for(j=l;j<=n;++j)(c[i]U]=0;for(k=l;k<=n;++k)c[i]U]+=a[i][k]*b[k]OJ;}f(n)=2n3+3n2+2n+l;T4(n)=O(f(n))=O(n3)立方阶第三章线性表基本概念:线性表，栈，队列，循形链表，双向链表，单链表、广义表存贮结构及在计算机内的表示:顺序存

4、贮（数组），链式存贮基本操作:插入，删除，查找，栈的压入、弹出操作，队列的循环数组表示,队列的假溢出III栈，队列的特殊性及出栈序列单链表的表头作用，空链表的表示数组的地址计算（二维，三角矩阵），稀疏矩阵的存贮方法串的定义峻串与空白串的区别广义表的长度，深度第四章树基本概念：树，二元树，森林完全二元树，满二元树，哈夫曼树存贮结构：二元树的四种结构：顺序，左右链，游标，线索树的三种：父链法（数组），左右链，邻接表11?.遍历算法（递归与非递归）：前序，中序，后序，按层，线索二元树求前导与后继二元树的性质（5个）森林与二元树之间的转换。哈夫曼树的构造方法及哈夫曼编码。弟五章图及有关算

5、法基本概念:图，最小生成树，关键路径，拓扑分类，连通分量存贮结构：邻接矩阵，邻接表搜索算法：先深、先广，最小生成树，拓扑分类，关键路径，单源最短路径出度，入度，先深序列，先广序列第六章查找掌握线性查找、折半查找、分块查找、二元查找树，散列法的定义,算法思想及时间复杂性=J散列冲突的处理，散列函数。第七章分类掌握简单分类，快速分类，归并分类、堆分类的定义，算法思想，内存空间及时间复杂性。第八章外部分类及文件掌握外部分类的定义，磁盘文件的归并分类技术（K路归并，并行操作、初始归并段的生成），文件的组织方法及各类组织文件的特点。