《全国计算机二级公共基础知识讲义》由会员分享,可在线阅读,更多相关《全国计算机二级公共基础知识讲义(86页珍藏版)》请在金锄头文库上搜索。
1、目录全国二级C语言考试大纲1全国二级公共基础知识考试大纲3公共基础知识讲义4第一讲 数据结构与算法4第二讲 数据库设计基础11第三讲 软件工程基础18第四讲 程序设计基础25公共基础知识习题28数据结构与算法习题28数据库设计基础习题33软件工程基础习题38程序设计基础习题412009年3月二级C语言笔试真题432009年3月二级C语言笔试答案542008年9月二级C语言笔试真题552008年9月二级C语言笔试答案642008年4月二级C语言笔试真题652008年4月二级C语言笔试答案732007年9月二级C语言笔试真题742007年9月二级C语言笔试答案86全国二级C语言考试大纲 基本要求1
2、.熟悉 Visual C+ 6.0 集成开发环境。2.掌握结构化程序设计的方法,具有良好的程序设计风格。3.掌握程序设计中简单的数据结构和算法并能阅读简单的程序。4.在 Visual C+ 6.0 集成环境下,能够编写简单的C程序,并具有基本的纠错和调试程序的能力 考试内容一、C语言程序的结构1.程序的构成,main函数和其他函数。2.头文件,数据说明,函数的开始和结束标志以及程序中的注释。3.源程序的书写格式。4.C语言的风格。二、数据类型及其运算1.C的数据类型(基本类型,构造类型,指针类型,无值类型)及其定义方法。2.C运算符的种类、运算优先级和结合性。3.不同类型数据间的转换与运算。4
3、.C表达式类型(赋值表达式,算术表达式,关系表达式,逻辑表达式,条件表达式,逗号表达式)和求值规则。三、基本语句1.表达式语句,空语句,复合语句。2.输入输出函数的调用,正确输入数据并正确设计输出格式。四、选择结构程序设计1.用if语句实现选择结构。2.用switch语句实现多分支选择结构。3.选择结构的嵌套。五、循环结构程序设计1.for循环结构。2.while和do-while循环结构。3.continue语句和break语句。4.循环的嵌套。六、数组的定义和引用1.一维数组和二维数组的定义、初始化和数组元素的引用。2.字符串与字符数组。七、函数1.库函数的正确调用。2.函数的定义方法。3
4、.函数的类型和返回值。4.形式参数与实在参数,参数值传递。5.函数的正确调用,嵌套调用,递归调用。6.局部变量和全局变量。7.变量的存储类别(自动,静态,寄存器,外部),变量的作用域和生存期。八、编译预处理1.宏定义和调用(不带参数的宏,带参数的宏)。2.“文件包含”处理。九、指针1.地址与指针变量的概念,地址运算符与间址运算符。2.一维、二维数组和字符串的地址以及指向变量、数组、字符串、函数、结构体的指针变量的定义。通过指针引用以上各类型数据。3.用指针作函数参数。4.返回地址值的函数。5.指针数组,指向指针的指针。十、结构体(即“结构”)与共同体(即“联合”)1.用typedef说明一个新
5、类型。2.结构体和共用体类型数据的定义和成员的引用。3.通过结构体构成链表,单向链表的建立,结点数据的输出、删除与插入。十一、位运算1.位运算符的含义和使用。2.简单的位运算。十二、文件操作 只要求缓冲文件系统(即高级磁盘I/O系统),对非标准缓冲文件系统(即低级磁盘I/O系统)不要求。1.文件类型指针(FILE类型指针)。2.文件的打开与关闭(fopen,fclose)。3.文件的读写(fputc,fgetc,fputs,fgets,fread,fwrite,fprintf,fscanf函数的应用),文件的定位(rewind,fseek函数的应用)。 考试方式1.笔试:90分钟,满分100分
6、,其中含公共基础知识部分的30分。2.上机:90分钟,满分100分3、上机操作包括:(1)填空。(2)改错。(3)编程。全国二级公共基础知识考试大纲 基本要求1.掌握算法的基本概念。2.掌握基本数据结构及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的结构化程序设计方法。5.掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。6.掌握数据库的基本知识,了解关系数据库的设计。 考试内容一、 基本数据结构与算法1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。3.
7、 线性表的定义;线性表的顺序存储结构及其插入与删除运算。4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。7. 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。二、 程序设计基础1. 程序设计方法与风格。2. 结构化程序设计。3. 面向对象的程序设计方法,对象,方法,属性及继承与多态性。三、 软件工程基础1. 软件工程基本概念,软件生命周期概念,软件工具与软件开发环境。2. 结构化分析方法,数据流图,数据字典,软件需求规格说明
8、书。3. 结构化设计方法,总体设计与详细设计。4. 软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统测试。5. 程序的调试,静态调试与动态调试。四、 数据库设计基础1. 数据库的基本概念:数据库,数据库管理系统,数据库系统。2. 数据模型,实体联系模型及E-R图,从E-R图导出关系数据模型。3. 关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理论。4. 数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式公共基础知识有10道选择题和5道填空题共三十分公共基础知识讲义第一讲 数据结构与算法1.1 算法1、算法
9、是指解题方案的准确而完整的描述。换句话说,算法是对特定问题求解步骤的一种描述。*:算法不等于程序,也不等于计算方法。程序的编制不可能优于算法的设计。2、算法的基本特征(1)可行性。针对实际问题而设计的算法,执行后能够得到满意的结果。(2)确定性。每一条指令的含义明确,无二义性。并且在任何条件下,算法只有唯一的一条执行路径,即相同的输入只能得出相同的输出。(3)有穷性。算法必须在有限的时间内完成。有两重含义,一是算法中的操作步骤为有限个,二是每个步骤都能在有限时间内完成。(4)拥有足够的情报。算法中各种运算总是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这就是算法执行的起点或依
10、据。因此,一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的结果输出。当输入不够或输入错误时,算法将无法执行或执行有错。一般说来,当算法拥有足够的情报时,此算法才是有效的;而当提供的情报不够时,算法可能无效。*:综上所述,所谓算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。3、算法复杂度主要包括时间复杂度和空间复杂度。(1)算法时间复杂度是指执行算法所需要的计算工作量,可以用执行算法的过程中所需基本运算的执行次数来度量。(2)算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本概念1、数据结构是指相互有关
11、联的数据元素的集合。2、数据结构主要研究和讨论以下三个方面的问题:(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构。数据的逻辑结构包含:1)表示数据元素的信息;2)表示各数据元素之间的前后件关系。(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。数据的存储结构有顺序、链接、索引等。1)顺序存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。2)链接存储。它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存
12、储结构。3)索引存储:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。*:数据的逻辑结构反映数据元素之间的逻辑关系,数据的存储结构(也称数据的物理结构)是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构,但影响数据处理效率。(3)对各种数据结构进行的运算。3、数据结构的图形表示一个数据结构除了用二元关系表示外,还可以直观地用图形表示。在数据结构的图形表示中,对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,并简称为结点;为了进一步表示各数据元素之间的前后件关系,对于关系R中的每一个二元组,用一条有向线段从前件结点指向
13、后件结点。4、数据结构分为两大类型:线性结构和非线性结构。(1)线性结构(非空的数据结构)条件:1)有且只有一个根结点;2)每一个结点最多有一个前件,也最多有一个后件。*:常见的线性结构有线性表、栈、队列和线性链表等。(2)非线性结构:不满足线性结构条件的数据结构。*:常见的非线性结构有树、二叉树和图等。1.3 线性表及其顺序存储结构1、线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。线性表是由n(n0)个数据元素组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。线性表中数据元素的个数称为线性表的
14、长度。线性表可以为空表。*:线性表是一种存储结构,它的存储方式:顺序和链式。2、线性表的顺序存储结构具有两个基本特点:(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。*:由此可以看出,在线性表的顺序存储结构中,其前后件两个元素在存储空间中是紧邻的,且前件元素一定存储在后件元素的前面,可以通过计算机直接确定第i个结点的存储地址。3、顺序表的插入、删除运算(1)顺序表的插入运算:在一般情况下,要在第i(1in)个元素之前插入一个新元素时,首先要从最后一个(即第n个)元素开始,直到第i个元素之间共n-i+1个元素依次向后移动一个位置,移动结束
15、后,第i个位置就被空出,然后将新元素插入到第i项。插入结束后,线性表的长度就增加了1。*:顺性表的插入运算时需要移动元素,在等概率情况下,平均需要移动n/2个元素。(2)顺序表的删除运算:在一般情况下,要删除第i(1in)个元素时,则要从第i+1个元素开始,直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后,线性表的长度就减小了1。*:进行顺性表的删除运算时也需要移动元素,在等概率情况下,平均需要移动(n-1)/2个元素。插入、删除运算不方便。1.4 栈和队列1、栈及其基本运算栈是限定在一端进行插入与删除运算的线性表。在栈中,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,栈底元素总是最先被插入的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。栈具有记忆作用。栈的基本运算:1)插入元素称为入栈运算;2)删除元素称为退栈运算;3)读栈