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

《计算机二级公共基础及c语言结构基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、及基本运算；    6.树的基本概念；二叉树的定义及存储结构；二叉树的前序、中序和后序遍历；    7.顺序查找与二分法算法；基本排序算法；    二、程序设计基础    1.程序设计方法与风格；    2.结构化程序设计；    3.面向对象的程序设计方法，对象，方法，属性及继承与多态性；    三、软件工程基础    1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境；    2.结构化的分析方法，数据流图，数据字典，软件需求规格说明书；    3.结构化设计方法，总体设计与详细设计；    4.软件测试的方法，白盒测试与黑盒测试，测试用

3、例设计，软件测试的实施，单元测试，集成测试和系统测试；    5.程序的调试，静态调试和动态调试。    四、数据库设计基础    1.数据库的基本概念：数据库，数据库管理系统，数据库系统；    2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型；    3.关系代数运算，包含集合运算及选择，投影，连接等运算；    4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 第1章数据结构与算法 　　1.1算法    1.1.1算法的基本概念    所谓算法是指解题方案的准确而完整的描述。   　1.算法的基本特征　 

4、   作为一个算法，一般应具有以下几个基本特征。    （1）可行性（effectiveness）    算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。    （2)确定件(definiteness）    算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。    (3)有穷性(finiteness)    算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。    算法的有穷性还应包括合理的执行时间的含义。    (4)拥有足够的情报    一个算法执行

5、的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。    综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。    2．算法的基本要素    一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。　　(1)算法中对数据的运算和操作    通常，计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。在一般的计算机系统中，基本的运算和操

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

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

8、递推技术    所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术