全国计算机等级考试复习.ppt

《全国计算机等级考试复习.ppt》由会员分享，可在线阅读，更多相关《全国计算机等级考试复习.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国计算机等级考试二级（C语言）考试内容1.算法的时间复杂度算法的时间复杂度即算法的工作量大小，指该算法所以耗费的时间。算法的时间复杂度可分为最坏时间复杂度和平均时间复杂度。2.算法的空间复杂度算法的空间复杂度指该算法所耗费的存储空间。包括程序本身大小和程序执行所占的空间。线性表的逻辑结构为线性结构相邻逻辑结点的物理位置也相邻的线性表为顺序表。顺序表的存储结构即线性表的顺序存储结构：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。顺序表的插入运算i=1时，结点的移动次数为n-1，算法的时间复杂度为O（n）。i=n时，结点的移动次数为0，算法的时间复杂度为O（1）。因而算法的时间复杂度=

2、结点移动次数+1线性表的插入运算插入到第P+1的位置，S-next=p-next;P-next=s;运算线性表的删除运算删除结点PP-next=q-next;Free(q);树是N个结点的有限集特点：1.有且仅有一个根节点。2.其余结点为m个互不交集的子集。每个子集称为根节点的子树。树中一个结点的子树个数称为该结点的度树的度=树中结点度的最大数二叉树是n个结点的有限集，它或者为空或者由根结点和互不交集的左右子树构成。二叉树的性质：深度为n的满二叉树结点数2（n）-1在第K层上2（n-1）在任意一棵二叉树上，若终端结点个数为M,度为2的结点数为N。M=N+1二叉树的的深度为lgn+1或lg(n+

3、1)二叉树的遍历1.前序遍历：根左右2.中序遍历：左根右3.后序遍历：左右根二分法查找要求：线性表有序，要用向量作为表的存储结构。例题？插入类排序1.直接插入排序：每次有序增加一个数，新插入的数与原来的数逐个比较大小。正序输入，移动次数为0，比较次数为n-1,时间的复杂度为O(n)逆序输入，移动次数为(n-1)(n+4)/2,比较次数为(n+2)(n-1)/2,这时的时间复杂度为O(n平方)第二章程序设计基础程序设计风格：清晰第一，效率第二。常用程序设计方法有：结构化程序设计方法和面向对象的程序设计方法。结构化程序设计方法：自顶向下，逐步细化，模块化设计，结构化编码。结构化程序特征1.一个程序单元由顺序，分支，循环三种结构组成。2.一个大程序由若干个不同功能的模块构成。3.每一个模块只有一个入口和出口。面向对象的程序设计面向对象特征：对象的唯一性，分类性，继承性，多态性面向对象建立的三模块，核心模块为 对象模块结构关系分：一般具体结构整体部分结构（组装结构）程序中的注释分 序言性注释与功能性注释