《全国计算机二级公共基础知识讲义》由会员分享，可在线阅读，更多相关《全国计算机二级公共基础知识讲义（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）读栈
