全国计算机2级公共基础知识近三次考试真题

1、二级公共基础知识总结 （30 分：前 10 选择+ 前 5 填空） 下面分为四个部分进行组织。文中标注了三个星号的，表示非常重要，基本每次考试都是必考；标注 了两个星号或一个星号的，表示也较重要，很容易考到。出现在【】括号中的内容，表示要很精确的 背下来的。整个文档中的五页，建议考前都要认真的记忆。第一部分算法与数据结构 （ 历年比例 41%）1、算法问题处理方案的正确而完整的描述称为【算法】。算法分析的目的是，分析算法的效率以求改进。算法的基本特征是【可行性】、【确定性】、【有穷性】和拥有足够情报。 算法的有穷性是指：算法程序的运行时间是有限的。 算法的复杂度是衡量算法好坏的度量，分为【时间

2、复杂度】和【空间复杂度】。 时间复杂度是指执行算法所需要的【计算工作量】；算法的空间复杂度是指算法执行过程中所 需的【存储空间】。 算法时间复杂度或空间复杂度中的一项的值，没有办法推出另一项的值。2、数据结构 数据结构分为【逻辑结构】和【存储结构】 。线性结构和非线性结构属于逻辑结构；顺序、链式、 索引属于存储结构 （物理结构 ） 。循环队列属于【存储结构】 。 数据的存储结构又称为物理结构，是数据的逻辑结构在计算机存储空间中的存放形式 。 一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率。程序执行的效率与数 据的存储结构密切相关。 数据结构分为线性结构和非线性结构，带链的队列

3、属于【线性结构】。 线性表的存储结构主要分为顺序存储结构和链式存储结构。顺序存储结构的存储一定是连续的， 链式存储的存储空间不一定是连续的。 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。 队列是一种特殊的线性表，循环队列按照【先进先出】原则组织数据。循环队列是队列的【顺序】 存储结构。数据的独立性分为【物理独立】性和【逻辑独立性】。当数据的存储结构改变时，其逻辑结构可 以不变，因此，基于逻辑结构的应用程序可以不用修改，称为【物理独立性】。3、栈和队列栈是一种只能在一端进行插入和删除 的线性表，特点是后进先出假定让元素a,b,c,d,e,f栈具有记忆作用；对栈的插入与删除操作中，

4、不需要改变【栈底指针】依次入栈，则岀栈的顺序是：f,e,d,c,b,a出桂帰丸人1R栈的模型 队列是一种只允许在表的前端（front ）进行删除操作，而在表的后端（rear）进行插入操作的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时， 称为空队列。栈与队列都是线性结构，树是非线性结构。支持子程序调用的数据结构是【栈】栈与队列的共同点是，都只允许在【端点处】插入和删除元素。栈只能顺序存储的描述是错误的。栈可以有【顺序和链式】两种存储方式。队列是允许在一段插入，在另一端进行删除的线性表，其特点是【先进先岀】。循环队列中元素的个数是 由队头指针和队尾指针共同决定 。循

5、环队列的头指针为front ，尾指针 为rear，容量为maxSize，则循环队列中元素的个数是 尾指针减头指针，若为负数，再加其容 量即可。4、线性链表线性链表是线性表的链式存储结构。用 链表表示线性表的优点 是【便于插入和删除操作】线性链表的存储空间不一定连续，且个元素的存储顺序是任意的。5、树与二叉树树是一种简单的 非线性结构，其存储结构采用 链式存储结构，其所有元素之间具有明显的 层次特 性。在树结构中，一个结点所拥有的后继的个数称为该结点的度，所有结点中最大的度称为树的度。二叉树各结点的度只可能取值0、1、2,不可能是其它值最简单二叉树模型没有前继的结点只有一个，称为树的根结点，简称

6、树的根，非空二叉树只有一个根结点。二叉树中每一个结点最多可以有两个后继，称为该结点的子结点，且分别称为该结点的 左子树与右子树。没有后继的结点称为 叶子结点。树的最大层次称为树的深度。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外,每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结 点。对任意的二叉树， 叶子结点的数量，比度为 2的结点数量多一个 即n0=n2+1K 1k满二叉树第K层上的结点数量为2-;深度为K的满二叉树，结点总数为2-1二叉树的前(先)序遍历、中序遍历、后续遍历：前中

7、后三个词是相对于根来讲的前序遍历(D L R):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(L D R):按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历(L R D):按后序遍历左子树，按后序遍历右子树，访问根结点。前序遍历中序遍历后序遍历二叉树的遍历是一个 递归的过程，对如图所示进行先序遍历步骤为:从大到小：把B及其孩子节点看为一个整体称为b,C及其孩子节点为c则先序遍历为Abe，在对b和c进一步先序遍历，b为BdE,c为CFG,再对d进行先序遍历为 DHI则最后结 果为ABDHIECFG，也可以从小到大写。6、查找技术对于长度为n的线性表，顺序查找最坏情况下需要 比

8、较n次。(对数据是否有序没有要求)顺序查找最好情况下查询次数是1最坏情况下是n,平均为(1+ n)/2。对于长度为n的有序线性表，二分法最坏情况下只需要比较log 2n次。(数据必须有序) 能用二分法进行查找的是【顺序存储的有序线性表】。7、排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。交换类排序法：(1)冒泡排序法，需要比较的次数为|n(n-1)/2 |;(2 )快速排序法。插入类排序法：(1 )简单插入排序法，最坏情况需要|n(n-1)/2|次比较；(2) 希尔排序法，最坏情况需要O(n 1.5 )I次比较。选择类排序法：(1 )简单选择排序法，最坏情况需要n(n-1)

9、/2次比较；(2)堆排序法，最坏情况需要O(nlog2孑次比较。相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。实在记不住就写n(n-1)/2,概率大点已知数据表A中每个元素距最终位置不远，为节省时间，应该采用的算法是【直接插入排序】 选择排序、插入排序、快速排序、归并排序中对内存要求最大的是【归并排序】。第二部分软件工程基础(历年比例27%)1、软件工程基本概念 软件是包括【程序】、【数据】及【相关文档】的完整集合，软件是一种逻辑产品。软件工程 三要素包括【方法、工具和过程】，其中【过程】支持软件开发的各个环节的控制和管理。软件工程的核心思想：把软件产品当作是一个工程产品来处理，强

10、调在软件开发过程中应用【工程化】原则。 从工程管理角度，软件设计一般分为两步完成，它们是【概要设计】和【详细设计】。 软件生命周期可分为多个阶段，一般分为【定义】阶段、【开发】阶段和【维护】阶段，编码 和测试属于【开发阶段】。 需求分析阶段产生的主要文档是【软件需求规格说明书】。软件需求的规格说明书应该有完整性、 无歧义性、正确性、可验证性、可修改性等特征，其中最重要的是【正确性】。2、结构化分析与设计需求分析的分发有：【结构化】需求分析方法，【面向对象】的分析方法。数据流图（ DFD是 【需求分析阶段】可以使用的工具之一。结构化分析的常用工具：数据流图（DFD）;数据字典；判定树；判定表。在

11、结构化分析使用数据流图（DFD）时候，利用【数据字典】对其中的图形元素进行确切的解释。 【数 据字典】是结构化分析的核心。 典型的数据流类型有两种，【交换性】和【事务型】。常见的过程设计工具有：图形工具 （程序流程图、N-S, PAD HIPO）、表格工具（判定表）、语言工 具（PDL伪码）o 内聚性是模块内部的联系，耦合性模块之间的相互联系的紧密程度。追求目标是：模块的内聚程度要高，模块间的耦合程度要尽量弱 。即高内聚低耦合。程序流程图中带有箭头的线段表示的是【控制流】。【平行四边形】代表输入输岀，【矩形】 代表处理，菱形代表【判断】 （注意，数据流图中的箭头，代表【数据流】 ）o符合结构化

12、原则的三种基本控制结构是：【顺序结构】，【选择结构】和【循环结构】。3、软件测试与维护软件测试的目的是尽可能多的发现程序中的错误，但是不包括改正错误。（软件调试 的目的才是 改正错误 ） 软件测试分为静态测试和动态测试，其中【静态测试】是指不执行程序，只对程序文本进行检 查。软件的动态测试主要包括【黑盒测试】和【白盒测试】。黑盒测试的方法有等价类划分法，边界值分析法，错误推测法，因果图；白盒测试主要方法有逻 辑覆盖、基本路径测试。 （考试时给出一种方法的名字，你要知道属于白盒还是黑盒 ）【白盒测试】的原则之一是保证所测模块的每一个独立路径至少要执行一次。 白盒测试将程序看做是 【路径的集合】。

13、 软件测试一般按照四个步骤进行：单元测试，集成测试，验收测试和系统测试。集成测试应该在 【单元测试】之后进行。 在模块测试中，需要为每个被测试的模块设计【驱动模块】和【承接模块】。其中，驱动模块的 作用是将测试的数据传给被测试的模块，并显示结果。 【测试用例】是为某个目标而编制的一组测试输入、执行条件及预期结果。测试用例包括输入值 集和【输出值集】。诊断和改正程序中的错误 称为【程序调试】（或软件调试），通常也称为Debug。软件调试可分 为【静态调试】和【动态调试】。 在软件已经交付使用之后，为了改正错误或满足新的需要而修改软件的过程称为【软件维护】。 注意软件维护不属于软件生命周期【开发阶

14、段】的任务。第三部分数据库设计基础 （ 历年比例 24%）1、数据库系统基本概念数据库设计的根本目标是要解决【数据共享问题】 。在数据库管理技术发展的三个阶段中，数据 共享最好的是【数据库系统阶段】。数据独立性最高的阶段是【数据库系统阶段】。 数据库系统与文件系统的区别是前者具有【特定的数据模型】。 数据库系统常见的数据模型有层次模型，网络模型和【关系模型】。 数据库系统的核心是【数据库管理系统】。 数据库应用系统的核心是【数据库维护】。 DBS包括DB和DBMS完整讲，数据库系统 DBS由数据库DB数据库管理系统 DBMS数据库管 理员DBA硬件平台和软件平台组成。 数据库系统的三级模式结构

15、：内模式处于最底层，它反映了数据在计算机物理结构中的实际存储 形式；概念模式处于中层，它放映了设计者的数据全局逻辑要求，与软硬件环境无关；夕卜模式处于最外层，它反映了用户对数据的要求。在数据库系统中，用户所见的数据模式为【外模式】。数据库设计的四个阶段是：需求分析、概念设计、【逻辑设计】和【物理设计】。将E-R图转换成关系数据模型属于【逻辑设计】阶段。数据库管理系统提供的数据语言：数据定义语言DDL数据操纵语言DML数据控制语言DCL SQL 的全称是Structured Query Language ，中文意思是【结构化查询语言】。2、数据模型实体之间的联系用 树形结构来表示的模型是【层次模

16、型】。采用 二维表来表示的是【关系模 型】。在关系数据库中，把数据表示成二维表，每一个二维表称为【关系】。在关系数据库中，用来表示实体之间联系的是【关系】。将E-R图转化为关系模式时，实体和联系都可以表示为【关系】。确定两个实体之间是一对一、一对多、还是多对多的方法是：选择实体A,看是否有多个实体B与之对应；选择实体B,看是否有多个实体 A与之对应。例如在“学生学习课程”中的两个实体， 学生与课程，一个学生可以学习多门课程，一门课程可以被多个学生学习，所以二者是一种多对多的 关系。在E-R图中，用来表示实体的图形是【矩形】。用来表示【属性】的图形是椭圆。用菱形来表 一个关系表的行称为【元组】（

17、或记录），列称为【属性】（或字段）在二维表中，元组的【分量】不能再分为更小的数据线 为了建立一个关系，首先要构造数据的【逻辑关系】3、关系代数在交、差、投影中，不改变关系表中的属性个数但是能减少元组个数的是【交】运算。关系运算的规则(下面介绍的7种运算，考试的时候一般会考察一种，都要背 )(1) 并运算RU S:并运算是 两个表行上的合并，重复的行只岀现一次。(2) 交运算RQ S:交运算是选岀两个表中的公共行。(3) 差运算R-S:差运算是从表R中，删除R与S中都岀现过的行。(4) 选择运算：选出二维表【部分的行】称为选择运算。(5) 投影运算：选出二维表【部分的列】称为投影运算。连接运算：

18、根据两个表的共同属性的值，将它们连接起来，无需去除共同属性。如果去掉了重复 属性，就称为自然连接。(7)笛卡尔乘积：将关系R中的每一行依次与关系S中的每一行进行排列组合。其中,Goto注意：除了选择运算和投影运算 操作的是单个表之外，其余的元算都需要 两个表(两个关系) 并运算、交运算和差运算要求两个关系 R与S要具有相同个数的属性。第四部分 程序设计基础(历年比例8%)程序设计总体原则：清晰第一、效率第二。良好程序风格包括：源程序要文档化，数据说明的次序要规范化，避免滥用goto语句。结构化程序设计的核心是算法，面向对象的核心是对象(类)。结构化程序设计的基本原则是：【自顶向下】、【逐步求精

19、】、【模块化】、【限制使用 语句】。类是一组具有相同属性和相同操作的对象的集合。面向对象模型中，最基本的概念是对象和【类】。在面向对象方法中，类的实例称为【对象】，实现信息隐藏是通过对象的【封装】。面向对象的特征包括抽象，【封装】、【继承】、【多态】。继承提高了软件的【可重用性】。对象是【属性和方法】的封装体，对象间的通讯靠【消息传递】，操作是对象的动态性属性。公共知识部分仅占30%分，题目相对简单。因此，在答题过程中，这部分要争取速度快、准确度高。 总的原则是如果一道题在两分钟内没有任何思路，就应该跳过此题，把时间给后面的题目。记住：二 级考试是一种合格考试，不是竞赛，及格就行了。2010年

20、9月全国计算机二级 C语言笔试试题一、选择题（每小题2分，共70分）下列各题A）、B）、C）、D）四个选项中，只有一个选项是正确的。请将正 确选项填涂在答题卡相应位置上，答在试卷上不得分。（1）下列叙述中正确的是A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D）上述三种说法都不对（2）下列叙述中正确的是A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶

21、指针的变化而动态变化D）上述三种说法都不对（3）软件测试的目的是A）评估软件可靠性B）发现并改正程序中的错误C）改正程序中的错误D）发现程序中的错误（4）下面描述中，不属于软件危机表现的是A）软件过程不规范B）软件开发生产率低C）软件质量难以控制D）软件成本不断提高（5）软件生命周期是指A ）软件产品从提出、实现、使用维护到停止使用退役的过程B ）软件从需求分析、设计、实现到测试完成的过程C）软件的开发过程D）软件的运行维护过程（6）面向对象方法中，继承是指A）一组对象所具有的相似性质B）一个对象具有另一个对象的性质C）各对象之间的共同性质D ）类之间共享属性和操作的机制（7）层次型、网状型和

22、关系型数据库划分原则是A ）记录长度B）文件的大小C）联系的复杂程度D）数据之间的联系方式（8）个工作人员可以使用多台计算机，而一台计算机可被多个人使用，则实 体工作人员、与实体计算机之间的联系是A）一对一B）一对多C）多对多D）多对一（9）数据库设计中反映用户对数据要求的模式是A）内模式B）概念模式C）外模式D）设计模式（10）有三个关系R、S和T如下：则由关系R和S得到关系T的操作是A）自然连接B ）交C）投影D ）并（11）以下关于结构化程序设计的叙述中正确的是A）一个结构化程序必须同时由顺序、分支、循环三种结构组成B ）结构化程序使用goto语句会很便捷C）在C语言中，程序的模块化是利

23、用函数实现的D ）由三种基本结构构成的程序只能解决小规模的问题二、填空题（每空2分）（2） 在长度为n的线性表中，寻找最大项至少需要比较【2】次。（3）棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有 【3】个结点。（4） 仅由顺序、选择（分支）和重复（循环）结构构成的程序是【4】程序。（5） 数据库设计的四个阶段是：需求分析，概念设计，逻辑设计【5】。 、选择题1-5: B C D A A6-10: D D C C A二、填空题2: 13: 254:结构化5:物理设计2011年3月全国计算机等级考试二级 C语言笔试一、 选择题（1）下列关于栈叙述正确的是A）栈顶元素最先能被删除

24、B）栈顶元素最后才能被删除C）栈底元素永远不能被删除D）以上三种说法都不对下列叙述中正确的是A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D) 双向链表是非线性结构某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层)A) 3 B)4 C)6 D)7(4) 在软件开发中，需求分析阶段产生的主要文档是A) 软件集成测试计划B)软件详细设计说明书C)用户手册 D)软件需求规格说明书(5) 结构化程序所要求的基本结构不包括A) 顺序结构B)GOTO跳转C)选择(分支)结构D)重复(循环)结构(6) 下

25、面描述中错误的是A) 系统总体结构图支持软件系统的详细设计B) 软件设计是将软件需求转换为软件表示的过程C) 数据结构与数据库设计是软件设计的任务之一D) PAD图是软件详细设计的表示工具(7) 负责数据库中查询操作的数据库语言是A) 数据定义语言B) 数据管理语言C) 数据操纵语言D) 数据控制语言(8) 一个教师可讲授多门课程，一门课程可由多个教师讲授。则实体教师和课程间的联 玄阜系是A)1:1联系B)1:m联系C)m:1联系D)m:n联系(9) 有三个关系R、S和T如下：则由关系R和S得到关系T的操作是A)自然连接B)交C)除D)并(10) 定义无符号整数类为Ulnt,下面可以作为类Ul

26、nt实例化值的是A)-369 B)369 C)0.369 D)整数集合1,2,3,4,5二、填空题(1)有序线性表能进行二分查找的前提是该线性表必须是【1】 存储的。一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为 ABDECF，则后序遍历结果为【2。(3) 对软件设计的最小单位(模块或程序单元)进行的测试通常称为【3 测试。(4) 实体完整性约束要求关系数据库中元组的【4属性值不能为空。(5) 在关系A(S,SN,D)和关系B(D,CN,NM)中，A的主关键字是 S, B的主关键字是 D , 则称 【5是关系A的外码。2011年3月全国计算机等级考试二级C等级考试答案公共基础知识部分、

27、选择题：1. A2*B4. D5. B6. A7.C8.D9-C10. B二、填空题1.顺序2.DEBFCA3,单元测试4.主键5.D二级亡语言部分一V选择题：11* A12. D13. A14. A15. A16. A17. D18. C19. A20, D21-B22. D23. B24, C25. D26, C27. D28-C29.C30. C31. B32； B33. B34-D35-B36. C37. D38. D39, C40, E二、填空题6. 37. 12178.039.410. 20 011* iT12. double avg(doublea, double b)13.1371514. emocleur15.1234562011年9月全国计算机等级考试二级笔试试卷C语言程序设计一、选择题（每小题2分，共70分）下列各题A ）、B