计算机二级公共基础及C语言结构基础

1、2011全国计算机等级二级公共基础精讲班第1讲：课程介绍、算法特征讲义前言公共基础只是的考核方式是笔试，与程序设计语言的笔试部分组合成一张试卷，公共基础占30分（选择题10个和填空题5个）； 一、基本数据结构与算法 1.算法概念；算法复杂度的概念和意义（时间复杂度和空间复杂度）； 2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3.线性表的定义；线性表的顺序存储结构及基本运算。 4.栈和队列的定义；栈和队列的顺序存储及基本运算； 5.线性单链表与循环链表的结构及基本运算； 6.树的基本概念；二叉树的定义及存储结构；二叉树的前序、中序和后序遍历；

2、7.顺序查找与二分法算法；基本排序算法； 二、程序设计基础 1.程序设计方法与风格； 2.结构化程序设计； 3.面向对象的程序设计方法，对象，方法，属性及继承与多态性； 三、软件工程基础 1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境； 2.结构化的分析方法，数据流图，数据字典，软件需求规格说明书； 3.结构化设计方法，总体设计与详细设计； 4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试，集成测试和系统测试； 5.程序的调试，静态调试和动态调试。 四、数据库设计基础 1.数据库的基本概念：数据库，数据库管理系统，数据库系统； 2.数据模型，实体联

3、系模型及E-R图，从E-R图导出关系数据模型； 3.关系代数运算，包含集合运算及选择，投影，连接等运算； 4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 第1章 数据结构与算法1.1算法 1.1.1算法的基本概念 所谓算法是指解题方案的准确而完整的描述。1.算法的基本特征作为一个算法，一般应具有以下几个基本特征。 （1）可行性（effectiveness） 算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。 （2)确定件(definiteness） 算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。 (

4、3)有穷性(finiteness) 算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 算法的有穷性还应包括合理的执行时间的含义。 (4)拥有足够的情报一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。 综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 2算法的基本要素 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。(1)算法中对数据的运算和操作 通常，计算机可以执行的基

5、本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。在一般的计算机系统中，基本的运算和操作有以下四类： 算术运算：主要包括加、减、乘、除等运算。 逻辑运算：主要包括“与”、“或”、“非”等运算。 关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。 数据传输：主要包括赋值、输入、输出等操作。 (2)算法的控制结构 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-s结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基

6、本控制结构组合而成。 3算法设计基本方法 工程上常用的几中算法设计方法有： （1）列举法 根据所需要解决的问题，把所有可能的情况一一列举出来，并用问题中给定的条件来检验哪些是需要的，哪些是不需要的. 通常用来解决“有多少种可能”等类型的问题。(不能解决无线复杂的问题) (2)归纳法（从特殊到一般） 通过列举少量的特殊情况，经过分析，最后找出一般的关系。（解决列举量为无限的问题） (3)递推 从条件到结论，逐次推出所要求的各种中间结果和最终结果。 (4)递归 函数的自调用：将问题逐层分解，最后归结为一些最简单的问题。 (5)减半递推技术 所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递

7、推技术。所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。 (6)回溯法 通过对问题的分析，出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到f题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。回溯法在处理复杂数据结构方面有着广泛的应用。 算法复杂度112算法复杂度 算法的复杂度主要包括时间复杂度和空间复杂度。 1算法的时间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 度量算法工作量时：排除计算机、语言、程序员、算法实现过程的细节影响。 用算法在执行过程中所需基本运算的执行次数

8、来度量算法的工作量。 算法所执行的基本运算次数与问题的规模有关。 综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f(n) 其中n是问题的规模。 在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量。 (1)平均性态(AverageBehavior) 所谓平均性态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 设x是所有可能输入中的某个特定输入，P(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的

9、平均性态定义为(2)最坏情况复杂性(Worst-CaseComplexity) 所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为显然，W(n)的计算要比A(n)的计算方便得多。由于w(n)实际上是给出了算法工作量的一个上界，因此，它比A(n)更具有实用价值。 2算法的空间复杂度 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。2011全国计算机等级考试二级C语言精讲班第1讲：C语言程序结构讲义二级C考试大纲一、2010年计算机等级考试二级C考

10、试大纲基本要求1.熟悉VisualC+6.0集成开发环境。2.掌握结构化程序设计的方法，具有良好的程序设计风格。3.掌握程序设计中简单的数据结构和算法并能阅读简单的程序。4.在VisualC+6.0集成环境下，能够编写简单的C程序，并具有基本的纠错和调试程序的能力。考试内容，如下表考试方式1.笔试：90分钟，满分100分，其中含公共基础知识部分的30分。2.上机：90分钟，满分100分3.上机操作包括：（1）填空。（2）改错。（3）编程。二、最近3次二级C真题分析（考核内容、题型及分数分布）2010年3月二级C真题考核内容、题型及分数分布2009年9月二级C真题考核内容、题型及分数分布2009

11、年3月二级C真题考核内容、题型及分数分布考试要点总结三、第一章考核知识点分析 第1章 程序设计基本概念1.1程序和程序设计1.1.1C程序连续执行的一条条指令的集合称为“程序”。计算机并不能直接识别由高级语言编写的程序，它只能接受和处理由0和1的代码构成的二进制指令或数据。这种形式的指令称为“机器语言”。每条C语句，经过编译(Compile)最终都将转换成二进制的机器指令。由C语言构成的指令序列称为C源程序。C源程序经过C编译程序编译之后生成一个后缀为OBJ的二进制文件(称为目标文件)，然后由“连接程序”(Link)，把此OBJ文件与C语言提供的各种库函数连接起来生成一个后缀为EXE的可执行文

12、件。在操作系统环境下，只需点击或输入此文件的名字(而不必输入后缀EXE)，该可执行文件就可运行。1.1.2程序设计简单的程序设计一般包含以下几个部分：确定数据结构、确定算法、编码、在计算机上调试程序、整理并写出文档资料。【例题分析】（2007.4试题）下列叙述中错误的是( D )A）计算机不能直接执行用C语言编写的源程序B）C程序经C编译程序编译后，生成后缀为.obj的文件是一个二进制文件C）后缀为.obj的文件，经连接程序生成后缀为.exe的文件是一个二进制文件D）后缀为.obj和.exe的二进制文件都可以直接运行（2009.9试题）以下叙述中正确的是( D )A）程序设计的任务就是编写程序

13、代码并上机调试B）程序设计的任务就是确定所用数据结构C）程序设计的任务就是确定所用算法D）以上三种说法都不完整1.2算法 学习计算机程序设计语言的目的，是要用语言作为工具，设计出可供计算机运行的程序。有了一个好的算法，就可以用任何一种计算机高级语言把算法转换为程序 (编写程序)。算法是指为解决某个特定问题而采取的确定且有限的步骤。一个算法应当具有以下五个特性：有穷性、确定性、可行性、有零个或多个输入、有一个 或多个输出。算法可以用各种描述方法来进行描述，最常用的是伪代码、流程图和N-S流程图。1.3结构化程序设计和模块结构1.3.1结构化程序结构化程序由三种基本结构组成：顺序结构、选择结构、循

14、环结构。1.3.2模块化结构 当计算机在处理较复杂的任务时常常把这个复杂的任务分解为若干个子任务，每个子任务又分成很多个小子任务，每个小子任务只完成一项简单的功能。在程序设 计时，用一个个小模块来实现这些功能，每个程序设计人员分别完成一个或多个小模块。我们称这样的程序设计方法为“模块化”的方法，由一个个功能模块构成的 程序结构为模块化结构。在进行程序设计时，首先应当集中考虑主程序中的算法，写出主程序后再动手逐步完成子程序的调用。对于这些子程序也可用调试主程序的同样方法逐步完成其下一层子程序的调用。这就是自顶向下、逐步细化、模块化的程序设计方法。 c语言是一种结构化程序设计语言。它提供了三种基本

15、结构的语句；提供了定义“函数”的功能，在c语言中没有子程序的概念，它提供的函数可以完成子程序的 所有功能；C语言允许对函数单独进行编译，从而可以实现模块化。另外，c语言还提供了丰富的数据类型。这些都为结构化程序设计提供了有力的工具。 第一章补充知识点四、第一章补充知识点1、C语言由函数组成，有且仅有一个主函数-main()，一个程序总是从主函数开始执行；2、C语言的语句由“;”结束，书写格式自由，一行可写多个语句，一个语句可分多行书写；3、C程序是大小写敏感的（严格区分字母大小写）；【例题分析】（2010.3试题）以下叙述正确的是( B )A）C语言程序是由过程和函数组成的B）C语言函数可以嵌套调用的，例如：fun(fun(x)C）C语言函数不可以单独编译D）C语言中除了main函数，其他函数不可作为单独文件形式存在（习题）以下说法中正确的是( C )A)C语言程序总是从第一个定义的函数开始执行B)在C语言程序中，要调用的函数必须在main()函数中定义C)C语言程序总是从main()函数开始执行D)C语言程序中的main()函数必须放在程序的开始部分4、C程序的文件扩展名必须是.c；5、C语言的两种注释方式：/