2011年9月计算机二级C语言公共基础知识点及考点

计算机二级公共基础知识点：

1.算法的4个特性是：确定性，可行性，有穷性，拥有足够的情报

2.一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 3.算法设计的基本方法主要有：列举法，归纳法，递推，递归和减半递推技术 4. 常用的存储结构有：顺序，链接，索引 5. 堆排序：nlog2(n) 快速排序：n(n-1)/2 最坏 6. 数据流程图中：箭头 数据流 程序流程图中：箭头 事物流

7.数据库系统在其内部三级模式：概念模式，内部模式，外部模式； 8. 过程设计语言（PDL）是结构化的英语和伪码，是一种混合语言 9.用户参与物理设计的内容有索引设计，集簇设计和分区设计等三种 10.衡量模块独立程度的度量标准：耦合和内聚

11.程序设计主要经过了结构化的程序设计和面向对象的程序设计 12.数据库设计包括：概念设计和逻辑设计

13.数据库的物理结构主要指数据库的存储记录格式，存储记录安排和存取方法 14.数据库的建立包括数据模式的建立与数据加载 15.数据库设计一般采用生命周期法

16.源程序文档化时程序应加注释。注释一般分为序言性注释和功能性注释 17.结构化程序设计的主要特点是每个控制结构只有一个入口和一个出口

18.结构化程序设计的主要方法是自顶向下，逐步求精，模块化，限制使用GOTO语句 19.在面向对象的方法中，类的实例成为对象

20.在面向对象的方法中，直接反映了用户对目标系统的要求的模型是功能模型 21.对象有三种成分：标识，属性和方法

22.软件工程研究的主要内容：软件开发技术和软件工程管理 23.软件工程的三要素：方法，工具和过程 24.软件是程序，数据和文档的集合

25.软件工程的原则包括：抽象，信息隐蔽，模块化，局部化，确定性，一致性，完备性和可验证性 26.结构化方法的核心和基础是结构化程序设计理论

27.软件需求分析阶段的工作：需求获取，需求分析，编写需求规格说明书，需求评审 28.在结构化分析方法中，用于描述系统中所用到的全部数据和文件的文档称为数据字典

29.软件需求规格说明书是需求分析阶段的最后成果

30.软件设计的基本原则：抽象，模块化，信息隐蔽，模块独立性 31.数据流程图的类型：变换型和事务型

32.好的软件设计结构通常顶层高扇出，中间扇出较少，底层高扇出 33.详细设计的方法主要是结构化程序设计

34.常用图形描述工具有程序流程图，盒图盒问题分析图 35.详细设计的典型语言描述工具是PDL 36.结构化程序设计主要强调的是程序的易读性

37.在软件生命周期中，能准确的确定软件系统必须做什么和必须具备哪些功能的阶段是需求分析 38.关系表中每一个横行称为一个元组

39.对象是属性和方法的封装体，操作是对象的动态性属性

40.在数据管理技术的发展过程中，经历了人工管理阶段，文件系统阶段和数据库系统阶段，其中数据独立性最高的是数据库系统

41.用树形结构来表示实体之间联系的模型成为层次模型

42.关系数据库管理系统能使现的专门关系运算包括选择，投影，连接 43.数据的存储结构是指数据的逻辑结构在计算机中的表示 44.检查软件产品是否符合需求定义的过程称为确认测试 45.需求分析常用工具DFD 46.索引属于内模式

47.在关系数据库中，用来表示实体之间关系的是二维表 48.将E－R图转换到关系模式时，实体与联系都可以表示成关系 49.希尔排序法属于插入类排序法

50.诊断和改正程序中错误的工作通常称为程序调试 51.问题处理方案的正确而完整的描述称为算法 52.白盒测试一般适用于单元测试 53.数据就是描述事物的符号记录

54. 数据库应用系统由数据库系统，应用软件和应用界面组成 55.数据模型所描述的内容：数据结构，数据操作，数据约束。

56.数据库的物理结构主要指数据库的存储记录格式，存储记录安排和存取方法

57.数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。也就是说，数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。 58.面向对象的方法包括：对象，继承，类

59.能够给出数据库物理存储结构与物理存取方法的是内模式 60.软件的调试方法主要有：强行排错法、回溯法和原因排除法

61.数据字典是各类数据描述的集合，它通常包括5个部分，即数据项，是数据的最小单位；数据结构，是若干数据项有意义的集合；数据流，可以是数据项，也可以是数据结构，表示某一处理过程的输入或输出；数据存储，处理过程中存取的数据，常常是手工凭证、手工文档或计算机文件；处理过程。

62.软件具有以下特点：①软件是一种逻辑实体，而不是物理实体，具有抽象性；②软件的生产过程与硬件不同，它没有明显的制作过程；③软件在运行、使用期间不存在磨损、老化问题；④软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致软件移植的问题；⑤软件复杂性高，成本昂贵；⑥软件开发涉及诸多的社会因素。

63.在结构化方法中，软件功能分解属于下列软件开发中的阶段是总体设计 64.SQL语言又称为结构化查询语 65.数据处理的最小单位是数据项 66.数据库设计是数据库应用的核心 67.数据流的类型有变换型和事务型

68.数据库系统中实现各种数据管理功能的核心软件称为数据库管理系统

69.面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是使用现实世界的概念抽象地思考问题从而自然地解决问题

70.数据模型所描述的内容有3个部分，它们是数据结构、数据操作和数据约束。其中，数据模型中的数据结构主要描述数据的类型、内容、性质，以及数据库的联系等；数据操作主要是描述在相应数据结构上的操作类型与操作方式。

71.栈的基本运算有三种：入栈、退栈和读出栈顶元素

72.视图设计一般有3种设计次序，它们分别是自顶向下、自底向上和由内向外 73.在面向对象方法中，信息隐蔽是通过对象的封装性来实现的。

74.软件维护活动包括以下几类：改正性维护、适应性维护、完善性维护和预防性维护。 75.数据库管理系统常见的数据模型有层次模型、网状模型和关系模型 76.顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中

第1章 数据结构与算法

经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。

详细重点学习知识点：

1．算法的概念、算法时间复杂度及空间复杂度的概念 2．数据结构的定义、数据逻辑结构及物理结构的定义

3．栈的定义及其运算、线性链表的存储方式

4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5．二分查找法 6．冒泡排序法

1.1算法

考点1 算法的基本概念

考试链接：

考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法的基本要素：

（1）算法中对数据的运算和操作

一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。

在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。

（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。

描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。

考点2 算法复杂度

考试链接：

考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。

1.算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法\运行工作量\的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。即

算法的工作量=f（n）

2.算法的空间复杂度

算法的空间复杂度是指执行这个算法所需要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。 疑难解答：算法的工作量用什么来计算？

算法的工作量用算法所执行的基本运算次数来计算，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f（n），其中n是问题的规模。

1.2数据结构的基本概念

考点3 数据结构的定义

考试链接：

考点3在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为识记内容，读者还应该识记数据的逻辑结构和存储结构的概念。

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：

（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；

（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。

数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。

数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成

B=（D，R）

其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。

考点4 线性结构与非线性结构

考试链接：

考点4在笔试考试中，虽然说不是考试经常考查的内容，但读者还是对此考点有所了解，在笔试考试中出现的几率为30%，主要是以填空题出现的形式出现，分值为2分，此考点为识记内容。

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：

（1）有且只有一个根结点；

（2）每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。 疑难解答：空的数据结构是线性结构还是非线性结构？

一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数据结构的算法是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。

1.3栈及线性链表

考点5 栈及其基本运算

考试链接：

考点5在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为100%，主要是以选择的形式出现，分值为2分，此考点为重点掌握内容，读者应该掌握栈的运算 。

本文来源：https://www.bwwdw.com/article/iwaf.html