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

全国计算机2级公共基础知识+近三次考试真题全国计算机2级公共基础知识+近三次考试真题16/16全国计算机2级公共基础知识+近三次考试真题二级公共基础知识总结(30分：前10选择+前5填空)下面分为四个部分进行组织。文中标注了三个星号的，表示特别重要，基本每次考试都是必考；标注了两个星号或一个星号的，表示也较重要，很简单考到。出现在【】括号中的内容，表示要很精确的背下来的。整个文档中的五页，建议考前都要仔细的记忆。第一部分算法及数据结构(历年比例41%)1,算法◆问题处理方案的正确而完整的描述称为【算法】。算法分析的目的是，分析算法的效率以求改进。算法的基本特征是【可行性】,【确定性】,【有穷性】和拥有足够情报。◆算法的有穷性是指：算法程序的运行时间是有限的。◆算法的困难度是衡量算法好坏的度量，分为【时间困难度】和【空间困难度】。★★时间困难度是指执行算法所须要的【计算工作量】；算法的空间困难度是指算法执行过程中所需的【存储空间】。◆算法时间困难度或空间困难度中的一项的值，没有方法推出另一项的值。2,数据结构◆数据结构分为【逻辑结构】和【存储结构】。线性结构和非线性结构属于逻辑结构；依次,链式,索引属于存储结构(物理结构)。循环队列属于【存储结构】。★数据的存储结构又称为物理结构，是数据的逻辑结构在计算机存储空间中的存放形式。◆一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率。程序执行的效率及数据的存储结构亲密相关。◆数据结构分为线性结构和非线性结构，带链的队列属于【线性结构】。◆线性表的存储结构主要分为依次存储结构和链式存储结构。依次存储结构的存储肯定是连续的，链式存储的存储空间不肯定是连续的。◆有序线性表既可以采纳依次存储结构，也可以采纳链式存储结构。◆队列是一种特别的线性表，循环队列依据【先进先出】原则组织数据。循环队列是队列的【依次】存储结构。◆数据的独立性分为【物理独立】性和【逻辑独立性】。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序可以不用修改，称为【物理独立性】。3,栈和队列★★栈是一种只能在一端进行插入和删除的线性表，特点是后进先出★★栈具有记忆作用；对栈的插入及删除操作中，不须要改变【栈底指针】。假定让元素a,b,c,d,e,f依次入栈，则出栈的依次是：f,e,d,c,b,a。栈的模型◆队列是一种只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。◆栈及队列都是线性结构，树是非线性结构。支持子程序调用的数据结构是【栈】。◆栈及队列的共同点是，都只允许在【端点处】插入和删除元素。◆栈只能依次存储的描述是错误的。栈可以有【依次和链式】两种存储方式。★★队列是允许在一段插入，在另一端进行删除的线性表，其特点是【先进先出】。◆循环队列中元素的个数是由队头指针和队尾指针共同确定。循环队列的头指针为front，尾指针为rear，容量为maxSize，则循环队列中元素的个数是“尾指针减头指针”，若为负数，再加其容量即可。4,线性链表◆线性链表是线性表的链式存储结构。用链表表示线性表的优点是【便于插入和删除操作】。★线性链表的存储空间不肯定连续，且个元素的存储依次是随意的。5,树及二叉树◆树是一种简单的非线性结构，其存储结构采纳链式存储结构，其全部元素之间具有明显的层次特性。在树结构中，一个结点所拥有的后继的个数称为该结点的度，全部结点中最大的度称为树的度。二叉树各结点的度只可能取值0,1,2，不可能是其它值。LLDR最简单二叉树模型◆没有前继的结点只有一个，称为树的根结点，简称树的根，非空二叉树只有一个根结点。二叉树中每一个结点最多可以有两个后继，称为该结点的子结点，且分别称为该结点的左子树及右子树。没有后继的结点称为叶子结点。◆树的最大层次称为树的深度。满二叉树是指除最终一层外，每一层上的全部结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最终一层外，每一层上的结点数均达到最大值，在最终一层上只缺少右边的若干结点。★★★对随意的二叉树，叶子结点的数量，比度为2的结点数量多一个即n0=n2+1◆满二叉树第K层上的结点数量为2K-1；深度为K的满二叉树，结点总数为2K-1。★★★二叉树的前（先）序遍历,中序遍历,后续遍历：前中后三个词是相对于根来讲的，前序遍历(DLR):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(LDR):按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。LDRLDRLDRLDR前序遍历中序遍历后序遍历二叉树的遍历是一个递归的过程，对如图所示进行先序遍历步骤为：从大到小：把B及其孩子节点看为一个整体称为b,C及其孩子节点为c则先序遍历为Abc，在对b和c进一步先序遍历，b为BdE,c为CFG,再对d进行先序遍历为DHI则最终结果为ABDHIECFG，也可以从小到大写。6,查找技术◆对于长度为n的线性表，依次查找最坏状况下须要比较n次。(对数据是否有序没有要求)。◆依次查找最好状况下查询次数是1，最坏状况下是n，平均为(1+n)/2。★★对于长度为n的有序线性表，二分法最坏状况下只须要比较log2n次。(数据必需有序)◆能用二分法进行查找的是【依次存储的有序线性表】。7,排序技术◆排序是指将一个无序序列整理成按值非递减依次排列的有序序列。★★交换类排序法：（1）冒泡排序法，须要比较的次数为n(n-1)/2；(2)快速排序法。插入类排序法：（1）简单插入排序法，最坏状况须要n(n-1)/2次比较；(2)希尔排序法，最坏状况须要O(n1.5)次比较。选择类排序法：（1）简单选择排序法,最坏状况须要n(n-1)/2次比较；(2)堆排序法，最坏状况须要O(nlog2n)次比较。相比以上几种(除希尔排序法外)，堆排序法的时间困难度最小。实在记不住就写n(n-1)/2,概率大点。◆已知数据表A中每个元素距最终位置不远，为节约时间，应当采纳的算法是【直接插入排序】。选择排序,插入排序,快速排序,归并排序中对内存要求最大的是【归并排序】。第二部分软件工程基础(历年比例27%)1,软件工程基本概念★★软件是包括【程序】,【数据】及【相关文档】的完整集合，软件是一种逻辑产品。软件工程三要素包括【方法,工具和过程】，其中【过程】支持软件开发的各个环节的限制和管理。◆软件工程的核心思想：把软件产品当作是一个工程产品来处理，强调在软件开发过程中应用【工程化】原则。◆从工程管理角度，软件设计一般分为两步完成，它们是【概要设计】和【具体设计】。★★软件生命周期可分为多个阶段，一般分为【定义】阶段,【开发】阶段和【维护】阶段，编码和测试属于【开发阶段】。◆需求分析阶段产生的主要文档是【软件需求规格说明书】。软件需求的规格说明书应当有完整性,无歧义性,正确性,可验证性,可修改性等特征，其中最重要的是【正确性】。2,结构化分析及设计★★需求分析的分发有：【结构化】需求分析方法，【面对对象】的分析方法。数据流图（DFD）是【需求分析阶段】可以运用的工具之一。◆结构化分析的常用工具：数据流图(DFD)；数据字典；判定树；判定表。◆在结构化分析运用数据流图(DFD)时候，利用【数据字典】对其中的图形元素进行准确的说明。【数据字典】是结构化分析的核心。◆典型的数据流类型有两种，【交换性】和【事务型】。◆常见的过程设计工具有：图形工具(程序流程图,N-S，PAD，HIPO),表格工具(判定表),语言工具(PDL伪码)。◆内聚性是模块内部的联系，耦合性模块之间的相互联系的紧密程度。★★★追求目标是：模块的内聚程度要高，模块间的耦合程度要尽量弱。即高内聚低耦合。★★程序流程图中带有箭头的线段表示的是【限制流】。【平行四边形】代表输入输出，【矩形】代表处理，菱形代表【推断】(留意，数据流图中的箭头，代表【数据流】)。◆符合结构化原则的三种基本限制结构是：【依次结构】，【选择结构】和【循环结构】。3,软件测试及维护★★软件测试的目的是尽可能多的发觉程序中的错误，但是不包括改正错误。(软件调试的目的才是改正错误)★★软件测试分为静态测试和动态测试，其中【静态测试】是指不执行程序，只对程序文本进行检查。软件的动态测试主要包括【黑盒测试】和【白盒测试】。◆黑盒测试的方法有等价类划分法，边界值分析法，错误推想法，因果图；白盒测试主要方法有逻辑覆盖,基本路径测试。(考试时给出一种方法的名字，你要知道属于白盒还是黑盒)【白盒测试】的原则之一是保证所测模块的每一个独立路径至少要执行一次。白盒测试将程序看做是【路径的集合】。◆软件测试一般依据四个步骤进行：单元测试，集成测试，验收测试和系统测试。集成测试应当在【单元测试】之后进行。◆在模块测试中，须要为每个被测试的模块设计【驱动模块】和【承接模块】。其中，驱动模块的作用是将测试的数据传给被测试的模块，并显示结果。◆【测试用例】是为某个目标而编制的一组测试输入,执行条件及预期结果。测试用例包括输入值集和【输出值集】。★★诊断和改正程序中的错误称为【程序调试】(或软件调试)，通常也称为Debug。软件调试可分为【静态调试】和【动态调试】。◆在软件已经交付运用之后，为了改正错误或满意新的须要而修改软件的过程称为【软件维护】。留意软件维护不属于软件生命周期【开发阶段】的任务。第三部分数据库设计基础(历年比例24%)1,数据库系统基本概念◆数据库设计的根本目标是要解决【数据共享问题】。在数据库管理技术发展的三个阶段中，数据共享最好的是【数据库系统阶段】。数据独立性最高的阶段是【数据库系统阶段】。◆数据库系统及文件系统的区分是前者具有【特定的数据模型】。◆数据库系统常见的数据模型有层次模型，网络模型和【关系模型】。★★数据库系统的核心是【数据库管理系统】。◆数据库应用系统的核心是【数据库维护】。◆

DBS包括DB和DBMS。完整讲，数据库系统DBS由数据库DB,数据库管理系统DBMS,数据库管理员DBA,硬件平台和软件平台组成。◆数据库系统的三级模式结构：内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式；概念模式处于中层，它放映了设计者的数据全局逻辑要求，及软硬件环境无关；外模式处于最外层，它反映了用户对数据的要求。◆在数据库系统中，用户所见的数据模式为【外模式】。◆数据库设计的四个阶段是：需求分析,概念设计,【逻辑设计】和【物理设计】。将E-R图转换成关系数据模型属于【逻辑设计】阶段。◆数据库管理系统供应的数据语言：数据定义语言DDL，数据操纵语言DML，数据限制语言DCL。SQL的全称是StructuredQueryLanguage，中文意思是【结构化查询语言】。2,数据模型★★★实体之间的联系用树形结构来表示的模型是【层次模型】。采纳二维表来表示的是【关系模型】。在关系数据库中，把数据表示成二维表，每一个二维表称为【关系】。◆在关系数据库中，用来表示实体之间联系的是【关系】。◆将E-R图转化为关系模式时，实体和联系都可以表示为【关系】。★★★确定两个实体之间是一对一,一对多,还是多对多的方法是：选择实体A，看是否有多个实体B及之对应；选择实体B，看是否有多个实体A及之对应。例如在“学生学习课程”中的两个实体，学生及课程，一个学生可以学习多门课程，一门课程可以被多个学生学习，所以二者是一种多对多的关系。★★在E-R图中，用来表示实体的图形是【矩形】。用来表示【属性】的图形是椭圆。用菱形来表示联系。★★一个关系表的行称为【元组】(或记录)，列称为【属性】(或字段)。◆在二维表中，元组的【重量】不能再分为更小的数据线。◆为了建立一个关系，首先要构造数据的【逻辑关系】。3,关系代数◆在交,差,投影中，不改变关系表中的属性个数但是能削减元组个数的是【交】运算。★★★关系运算的规则(下面介绍的7种运算，考试的时候一般会考察一种，都要背)(1)并运算R∪S：并运算是两个表行上的合并，重复的行只出现一次。(2)交运算R∩S：交运算是选出两个表中的公共行。(3)差运算R-S：差运算是从表R中，删除R及S中都出现过的行。(4)选择运算：选出二维表【部分的行】称为选择运算。(5)投影运算：选出二维表【部分的列】称为投影运算。(6)连接运算：依据两个表的共同属性的值，将它们连接起来，无需去除共同属性。假如去掉了重复属性，就称为自然连接。(7)笛卡尔乘积：将关系R中的每一行依次及关系S中的每一行进行排列组合。留意：除了选择运算和投影运算操作的是单个表之外，其余的元算都须要两个表(两个关系)。其中，并运算,交运算和差运算要求两个关系R及S要具有相同个数的属性。第四部分程序设计基础(历年比例8%)★★程序设计总体原则：清楚第一,效率第二。◆良好程序风格包括：源程序要文档化，数据说明的次序要规范化，避开滥用goto语句。◆结构化程序设计的核心是算法，面对对象的核心是对象(类)。★★结构化程序设计的基本原则是：【自顶向下】,【逐步求精】,【模块化】,【限制运用Goto语句】。★★类是一组具有相同属性和相同操作的对象的集合。面对对象模型中，最基本的概念是对象和【类】。在面对对象方法中，类的实例称为【对象】，实现信息隐藏是通过对象的【封装】。★★面对对象的特征包括抽象，【封装】,【继承】,【多态】。◆继承提高了软件的【可重用性】。◆对象是【属性和方法】的封装体，对象间的通讯靠【消息传递】，操作是对象的动态性属性。公共知识部分仅占30%分，题目相对简单。因此，在答题过程中，这部分要争取速度快,精确度高。

总的原则是假如一道题在两分钟内没有任何思路，就应当跳过此题，把时间给后面的题目。记住：二级考试是一种合格考试，不是竞赛，及格就行了。2010年9月全国计算机二级C语言笔试试题一,选择题（每小题2分，共70分）下列各题A）,B）,C）,D）四个选项中，只有一个选项是正确的。请将正确选项填涂在答题卡相应位置上，答在试卷上不得分。

（1）下列叙述中正确的是

A）线性表的链式存储结构及依次存储结构所须要的存储空间是相同的

B）线性表的链式存储结构所须要的存储空间一般要多于依次存储结构

C）线性表的链式存储结构所须要的存储空间一般要少于依次存储结构

D）上述三种说法都不对

（2）下列叙述中正确的是

A）在栈中，栈中元素随栈底指针及栈顶指针的变化而动态变化

B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化

C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化

D）上述三种说法都不对

（3）软件测试的目的是

A）评估软件牢靠性

B）发觉并改正程序中的错误

C）改正程序中的错误

D）发觉程序中的错误

（4）下面描述中，不属于软件危机表现的是

A）软件过程不规范

B）软件开发生产率低

C）软件质量难以限制

D）软件成本不断提高

（5）软件生命周期是指

A）软件产品从提出,实现,运用维护到停止运用退役的过程

B）软件从需求分析,设计,实现到测试完成的过程

C）软件的开发过程

D）软件的运行维护过程（6）面对对象方法中，继承是指

A）一组对象所具有的相像性质

B）一个对象具有另一个对象的性质

C）各对象之间的共同性质

D）类之间共享属性和操作的机制

（7）层次型,网状型和关系型数据库划分原则是

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语言中，程序的模块化是利用函数实现的

D）由三种基本结构构成的程序只能解决小规模的问题

二,填空题（每空2分）

（2）在长度为n的线性表中，找寻最大项至少须要比较【2】次。

（3）一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有【3】个结点。

（4）仅由依次,选择（分支）和重复（循环）结构构成的程序是【4】程序。

（5）数据库设计的四个阶段是：需求分析，概念设计，逻辑设计【5】。

一,选择题1-5:BCDAA6-10:DDCCA二,填空题2:13:254:结构化5:物理设计2011年3月全国计算机等级考试二级C语言笔试一,选择题(1)下列关于栈叙述正确的是A)栈顶元素最先能被删除B)栈顶元素最终才能被删除C)栈底元素恒久不能被删除D)以上三种说法都不对(2)下列叙述中正确的是A)有一个以上根结点的数据结构不肯定是非线性结构B)只有一个根结点的数据结构不肯定是线性结构C)循环链表是非线性结构D)双向链表是非线性结构(3)某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层)A)3B)4C)6D)7(4)在软件开发中，需求分析阶段产生的主要文档是A)软件集成测试安排B)软件具体设计说明书C)用户手册D)软件需求规格说明书(5)结构化程序所要求的基本结构不包括A)依次结构B)GOTO跳转C)选择(分支)结构D)重复(循环)结构(6)下面描述中错误的是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)定义无符号整数类为UInt,下面可以作为类UInt实例化值的是A)-369B)369C)0.369D)整数集合{1,2,3,4,5}二,填空题(1)有序线性表能进行二分查找的前提是该线性表必需是【1】存储的。(2)一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为【2】。(3)对软件设计的最小单位(模块或程序单元)进行的测试通常称为【3】测试。(4)实体完整性约束要求关系数据库中元组的【4】属性值不能为空。(5)在关系A(S,SN,D)和关系B(D,CN,NM)中，A的主关键字是S，B的主关键字是D，则称【5】是关系A的外码。2011年9月全国计算机等级考试二级笔试试卷C语言程序设计一,选择题（每小题2分，共70分）下列各题A）,B）,C）,D）四个选项中，只有一个选项是正确的。请将正确选项填涂在答题卡相应位置上，答在试卷上不得分。（1）下列叙述中正确的是A)算法就是程序B)设计算法只须要考虑数据结构的设计C)计算法时只须要考虑结果的牢靠性D)以下三种说法都不对（2）下列关于线性链表的叙述中，正确的是A)各数据结点的存储空间可以不连续，但他们的存储依次及逻辑依次必需一样B)各数据结点的存储依次及逻辑依次可以不一样，但它们的存储空间必需连