工程硕士专业课复习提纲

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

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

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

3、=O(1)常量阶②for(i=1;i<=n;++i){++x;s+=x;}→f(n)=3n+1;T1(n)=O(f(n))=O(n)线性阶③for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}→f(n)=3n2+2n+1;T3(n)=O(f(n))=O(n2)平方阶④for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}→f(n)=2n3+3n2+2n+1;T4(n)=O

4、(f(n))=O(n3)立方阶第一章线性表基本概念:线性表，栈，队列，循形链表，双向链表，单链表、广义表存贮结构及在计算机内的表示：顺序存贮（数组），链式存贮基本操作：插入，删除，查找，栈的压入、弹出操作，队列的循环数组表示，队列的假溢出栈，队列的特殊性及出栈序列单链表的表头作用，空链表的表示数组的地址计算（二维，三角矩阵），稀疏矩阵的存贮方法串的定义崆串与空白串的区别广义表的长度，深度第二章树基本概念：树，二元树，森林完全二元树，满二元树，哈夫曼树存贮结构：二元树的四种结构：顺序，左右链，游标，线索树的三种：父链法（数组），左

5、右链，邻接表遍历算法（递归与非递归）：前序，中序，后序，按层，线索二元树求前导与后继二元树的性质（5个）森林与二元树之间的转换。哈夫曼树的构造方法及哈夫曼编码。弟五章图及有关算法基本概念：图，最小生成树，关键路径，拓扑分类，连通分量存贮结构：邻接矩阵，邻接表搜索算法：先深、先广，最小生成树，拓扑分类，关键路径，单源最短路径出度，入度，先深序列，先广序列第六章查找掌握线性查找、折半查找、分块查找、二元查找树，散列法的定义，算法思想及时间复杂性散列冲突的处理，散列函数。第七章分类掌握简单分类，快速分类，归并分类、堆分类的定义，算法思

6、想，内存空间及时间复杂性。第八章外部分类及文件掌握外部分类的定义，磁盘文件的归并分类技术（K路归并，并行操作、初始归并段的生成），文件的组织方法及各类组织文件的特点。