二级公共基础知识部分

《二级公共基础知识部分》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二级公共基础知识授课时间：2011年10月1一、涉及面广，但难度小你应该知道公共基础知识考题特点计算机等级二级理论考试中有关公共知识部分的题目共有15道，涉及算法及数据结构、程序设计基础、软件工程基础和数据库设计基础等四门学科，但是从整体上分析，考试中的考核内容的难度不大，考点也相对集中些。2二、考核重点为基本概念、基本方法和基本运算你应该知道计算机等级二级理论考试中涉及的题目都是基本概念、基本方法和基本运算，考核以概念和认识性内容为主，理解性、应用性内容极少。3三、考核重点是数据结构和算法你应该知道以下是对以往二级理论考试的大概统计：算法及数据结构：50%程序设计基础：12.5%软件

2、工程基础：18.75%数据库设计基础：18.75%4考试内容基本数据结构与算法程序设计基础软件工程基础数据库设计基础内容2008/92009/42009/92010/42010/910`10`8`2`12`8`4`6`12`8`4`6`10`2`8`10`10`2`8`10`5考试方式1、公共基础的考试方式为笔试，与C语言（VisualBASIC、VisualFoxPro、Java、Access、VisualC++）的笔试部分合为一张试卷。公共基础部分占全卷的30分。2、公共基础知识有10道选择题和5道填空题。6学习方法理解基本概念多做练习适当记忆一些名词与所学的VFPcAcces

3、s程序设计知识结合起来，以增加对知识的理解能力7你应该知道共讲授12个学时，具体安排如下：数据结构与算法（5学时）程序设计基础、软件工程基础（3学时）数据库系统、真题讲解（4学时）本课程授课安排8基本要求1.掌握算法的基本概念。2.掌握基本数据结构及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的结构化程序设计方法。5.掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。6.掌握数据库的基本知识，了解关系数据库的设计。9数据结构与算法一、算法（algorithm）1、算法的基本概念算法是指解题方案的准确而完整的描述。它是指令的有限序列，其中每一条指令表示一个或多个操作

4、。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。101.1算法1算法(algorithm)基本概念一级算法:S1:输入圆的半径r;S2:求周长2∏r;S3:求面积∏r2;S4:输出周长和面积;例题1:已知圆的半径,求周长和面积.程序11算法的基本特征:(1)可行性(2)确定性(3)有穷性(4)输入和输出（拥有足够的情报）122、算法的基本要素对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输算法中各操作之间的执行顺序；描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等；一个算法一般可以用顺序、选择、循环三

5、种基本结构组合而成。算法的控制结构：数据结构与算法133、算法设计的基本方法列举法归纳法递推递归（以简洁的形式设计和描述算法）减半递推技术回溯法数据结构与算法141.2.1时间复杂度是指执行算法所需要的计算工作量。通常有事后统计法和事前分析估算法。★算法在执行过程中所需基本运算的执行次数来度量算法的工作量.★算法所执行的基本运算次数与问题的规模n有关.执行算法所需要的计算工作量和f(n)同步增长，记为:算法的工作量=f(n)时间复杂度=O(f(n))二、算法的复杂度15例子4：for(i=2;i<=n;++i)for(j=2;j<=i-1;++j)++x;基本运算：基本运算的执行次数：

6、X增1i=20i=31i=42…i=nn-21+2+3+…+(n-2)=(n-1)(n-2)/2O（）例子2：++x;O（1）例子3：for(i=1;i<=n;++i)++x;O（n）时间复杂度：O((n*n-3n+2)/2)基本运算：基本运算的执行次数：时间复杂度：1X增1基本运算：基本运算的执行次数：时间复杂度：X增1n16二、算法的复杂度1、时间复杂度在同一问题规模下，如果算法执行所需要的基本运算次数取决于某一特定输入时，可以用以下方法分析工作量：平均性态和最坏情况复杂性。数据结构与算法17算法与数据结构2、空间复杂度一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间

7、包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。18算法的时间复杂度是指A)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基本运算次数D)算法程序中的指令条数算法的基本特征是可行性、确定性、【1】和拥有足够的情报。算法的空间复杂度是