计算机二级考试.ppt

1、计算机二级考试公共基础知识,课时安排,C程序设计（24节）-1公共基础知识（26节）+1上机（30节）,计算机二级考试公共基础知识大纲,数据结构与算法 程序设计基础 软件工程基础 数据库设计基础,1. 掌握算法的基本概念。 2. 掌握基本数据结构及其操作 3. 掌握基本排序和查找算法。 4. 掌握逐步求精的结构化程序设计方法。 5. 掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。 6. 掌握数据库的基本知识，了解关系数据库的设计。,计算机二级考试公共基础知识试卷分析,选择题10个（20分） 填空题5个（10分） 总分的30%,一、 基本数据结构与算法,1. 算法的基本概念；时

2、间复杂度与空间复杂度。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,二、 程序设计基础,1. 程序设计方法与风格。 2. 结构化程序设计。 3. 面向对象的程序设计方法，对象，方法，属性及类、继承与多态

3、性。,三、 软件工程基础,1. 软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。 2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3. 结构化设计方法，总体设计与详细设计。 4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5. 程序的调试，静态调试与动态调试。,四、数据库设计基础,1. 数据库的基本概念：数据库，数据库管理系统，数据库系统。 2. 数据模型：实体联系模型及E-R图，从E-R图导出关系数据模型。 3. 关系代数运算：包括集合运算及选择、投影、连接运算，数据库规范化理论。 4. 数据库设计方法和步骤

4、：需求分析、概念设计、逻辑设计和物理设计的相关策略。,算法 算法的基本概念 2.算法复杂度的概念和意义,一、基本数据结构与算法,数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术,对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。,算法的定义 对解题方案准确而完整的描述算法。,算法是程序设计的核心, 算法的基本概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，

5、都是在实施某种算法。,2 . 算法的基本特征,可行性 有穷性 确定性 输入 输出,拥有足够的情报,3. 算法的表示,传统的算法-图形法，如“流程图”和N-S图 目前常用的方法-使用伪码描述算法。,4. 算法的两个基本要素：,基本运算和操作 算术运算 关系运算 逻辑运算 数据传输,控制结构 顺序 选择 循环,一是对数据对象的运算和操作； 二是算法的控制结构。,算法设计基本方法 列举法 归纳法 递推 递归 减半递推技术 回溯法,根据提出的问题，列举出所有可能的情况,通过列举少量的特殊情况，经过分析，最后找出一般的关系,从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果,将复杂问题逐层分解

6、，最后归结为一些最简单的问题。,将问题的规模减半，然后，重复相同的递推操作,采用试探的方法，通过对问题的分析，找出解决问题的线索,5 算法复杂度,时间复杂度 是指执行算法所需要的计算工作量。 算法在执行过程中所需基本运算的执行次数来度量算法的工作量. 算法所执行的基本运算次数与问题的规模n有关.,例子3：for ( i=2 ;i=n;+i) for (j=2 ;j=i-1;+j) +x ;,基本运算： 基本运算的执行次数：,X增1,i=2 0 i=3 1 i=4 2 i=n n-2,1+2+3+(n-2),= (n-1)(n-2)/2,O（ ）,例子1：+x;,O（ 1 ）,例子2： for

7、(i=1 ;i=n;+i) +x;,O（ n ）,时间复杂度：,O(n*n-3n+2)/2),基本运算： 基本运算的执行次数： 时间复杂度：,1,X增1,基本运算： 基本运算的执行次数： 时间复杂度：,X增1,n,空间复杂度 一般是指执行这个算法所需要的内存空间 一个算法所占用的存储空间包括: 算法程序所占的空间 输入的初始数据所占的存储空间 某种数据结构所需要的附加存储空间,(1) 在计算机中，算法是指_。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法 (2)下列叙述中正确的是 （07年4月） A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)

8、算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关 (3)算法的有穷性是指 (08年4月) A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用,(c),(B),算法习题:,(A),(4) 算法的时间复杂度是指 (2010年3月) A)算法的执行时间 B)算法所处理的数据量 C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数 (5) 算法的空间复杂度是指 (09年9月) A）算法在执行过程中所需要的计算机存储空间 B）算法所处理的数据量 C）算法程序中的语句或指令条数 D）算法在执行过程中所需要的临时工作单元数