等级考试二级公共基础历年试题.doc

全国计算机等级考试（二级公共基础知识）考试大纲♦基木要求1. 掌握算法的基木概念2. 掌握基本数据结构及其操作3. 掌握基本排序和查找算法4. 掌握逐步求精的结构化程序设计方法5. 掌握软件工程的基木方法，具有初步应用相关技术进行软件开发的能力6. 掌握数据库的基木知识，了解关系数据库的设计♦考试内容一、 基木数据结构与算法1. 算法的基木概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与 非线性结构的概念3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算4. 栈和队列的定义；栈和队列的顺序存储结构及其基木运算5. 线性单链表、双向链表与循坏链表的结构及其基木运算6. 树的基木概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历7•顺序查找与二分法查找算法；基木排序算法（交换类排序，选择类排序，插入类排 序）二、 程序设计基础1. 程序设计方法与风格2. 结构化程序设计3•面向对象的稈序设计方法，对象，方法，属性及继承与多态性三、 软件丁•程基础1. 软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。

2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书3・结构化设计方法，总体设计与详细设计4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测 试、集成测试和系统测试5. 程序的调试，静态调试与动态调试四、 数据库设计基础1. 数据库的基木概念：数据库，数据库管理系统，数据库系统2. 数据模型，实体联系模型及E・R图，从E・R图导出关系数据模型3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论4. 数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略♦考试方式公共基础知识有10道选择题和5道填空题共三I分2005年4月一、选择题（1） 数据的存储结构是指A） 存储在外存中的数据B） 数据所片的存储空间量C） 数据在计算机中的顺序存储方式D） 数据的逻辑结构中计算机中的表示答案:D（2） 下列关于栈的描述中，错误的是A） 栈是先进后出的线性表B） 栈只能顺序存储C） 栈具有记忆作用D） 对栈的插入与删除操作中，不需要改变栈底指针答案：B（3） 对于长度为n的线性表，在最坏情况下，下列备排序法所对应的比较次数中正确的是A） 冒泡排序为n/2B） 冒泡排序为nC） 快速排序为nD） 快速排序为n （n-1） /2答案：D（4） 对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为A） log2nB） n/2C） nD ） n+1答案:C（5） 下列对于线性链表的描述中正确的是A） 存储空间不一定是连续，且备元素的存储顺序是任意的B） 存储空间不一定是连续，且前件元素一定存储在后件元素的前面C） 存储空间必须连续，且前件元素一定存储在后件元素的前面D） 存储空间必须连续，且各元素的存储顺序是任惫的答案:A（6） 下列对于软件测试的描述中，正确的是A） 软件测试的目的是证明程序是否正确B） 软件测试的目的是使程序运行结果正确C） 软件测试的目的是尽可能多地发现程序中的错误D） 软件测试的日的是使程序符合结构化原则答案：C（7） 为了使模块尽可能独立，要求A） 模块的内聚程序要尽量高，且各模块间的耦合程序要尽量强B） 模块的内聚稈序要尽量高，且各模块间的耦合稈序要尽量弱C） 模块的内聚程序要尽量低，且各模块间的耦合稈序要尽量弱D）模块的内聚稈序要尽量低，且各模块间的耦合稈序要尽量强答案:B（8） 下列描述中正确的是A） 程序就是软件B） 软件开发不受计算机系统的限制C） 软件既是逻辑实体，又是物理实体D） 软件是稈序、数据与相关文档的集合答案：D（9） 数据独立性是数据库技术的重要特点乙一。

所谓数据独立性是指A） 数据与程序独立存放B） 不同的数据被存放在不同的文件中C） 不同的数据只能被对应的应用稈序所使用D） 以上三种说法都不对答案：D（10） 用树形结构表示实体Z间联系的模型是A） 关系模型B） 网状模型C） 层次模型D） 以上三个都是答案：C二、填空题（1） 某二叉树中，度为2的结点有18个，则该二叉树中有 个叶子结点答案：19（2） 在面向对象的方法中，类的实例称为 o答案：对彖（3） 诊断和改正稈序中错误的工作通常称为 o答案：程序调试（4） 在关系数据库中，把数据表示成二维表，每一个二维表称为 o答案：关系（5） 问题处理方案的正确而完整的描述称为 答案：算法2005年9月一、选择题（1） 下列叙述中正确的是A） 程序设计就是编制稈序B） 程序的测试必须由程序员白己去完成C） 稈序经调试改错后还应进行再测试D） 程序经调试改错示不必进行再测试 答案：C（2） 下列数据结构中，能用二分法进行查找的是A） 顺序存储的有序线性表B） 线性链表C） 二叉链表D） 有序线性链表答案:A（3） 下列关于栈的描述正确的是A） 在栈中只能插入元素而不能删除元素B） 在栈中只能删除元素而不能插入元素C） 栈是特殊的线性表，只能在一端插入或删除元素D） 栈是特殊的线性表，只能在一端插入元索，而在另一端删除元索 答案:C（4） 下列叙述中正确的是A） 一个逻辑数据结构只能有一种存储结构B） 数据的逻辑结构属于线性结构，存储结构属于非线性结构C） 一个逻辑数据结构可以有多种存储结构，且备种存储结构不煤响数据处理的效率D） 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 答案:D（5） 下列描述中正确的是A） 软件工程只是解决软件项目的管理问题B） 软件工程主要解决软件产品的生产率问题C） 软件工程的主要思想是强调在软件开发过稈中需要应用工稈化原则D） 软件工程只是解决软件开发中的技术问题答案：C（6） 在软件设计中，不属于过程设计工具的是A） PDL （过程设计语言）B） PAD 图C） N-S 图D ） DFD 图答案：D（7） 下列叙述中正确的是A） 软件交付使用后还需要进行维护B） 软件一旦交付使用就不需要再进行维护C） 软件交付使用后其生命周期就结束D） 软件维护是指修复程序中被破坏的指令 答案:A（8） 数据库设计的根木日标是要解决A） 数据共享问题B） 数据安全问题C） 大最数据存储问题D） 简化数据维护答案:A（9） 设有如下关系表：ABC112123RABC313SABC112223313T则下列操作中正确的是A） T=RDSB） T=RUSC） T=RXSD） T=R/S答案:B（10）数据库系统的核心是A） 数据模型B） 数据库管理系统C） 数据库D） 数据库管理员答案：B二、填空题（1） 数据管理技术发展过程经过人工管理、文件系统和数据库系统三个阶段，其中数据独立性最高的阶段是 。

答案：数据库系统（2） 算法复杂度主要包括时间复杂度和 复杂度答案：空间（3） 在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块（桩模块）其中 的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果答案：驱动模块（4） 一棵二叉树第六层（根结点为第一层）的结点数最多为 个答案：32（5） 数据结构分为逻辑结构和存储结构，循环队列属于 结构答案：存储2006年4月一、选择题（1）下列选项不属于结构化程序设计方法的是A） 自顶向下B） 逐步求精C） 模块化D） 可复用答案:D（2） 两个或两个以上模块之间关联的紧密程度称为A） 耦合度B） 内聚度C） 复杂度D） 数据传输特性答案:A（3） 下列叙述中正确的是A） 软件测试应该由程序开发者來完成B） 程序经调试后一般不需要再测试C） 软件维护只包括对程序代码的维护D） 以上三种说法都不对答案：D（4） 按照“后进先出”原则组织数据的数据结构是A） 队列B） 栈C） 双向链表D） 二叉树答案：B（5） 下列叙述中正确的是A） 线性链表是线性表的链式存储结构B） 栈与队列是非线性结构C） 双向链表是非线性结构D） 只有根结点的二叉树是线性结构答案：A（6） 对如下二叉树，进行后序遍历的结果为A） ABCDEFB） DBEAFCC） ABDECFD） DEBFCA答案：D（7）在深度为7的满二叉树中，叶了结点的个数为A） 32B） 31C） 64D ） 63答案：C（8） “商品”与“顾客”两个实体集Z间的联系一般是A） 一对一B） 一对多C） 多对一D） 多对多答案:D（9） 在E・R图中，用来表示实体的图形是A） 矩形B） 椭圆形C） 菱形D） 三角形答案：A（10） 数据库DB、数据库系统DBS、数据库管理系统DBMS ZluJ的关系是A） DB 包含 DBS 和 DBMSB） DBMS 包含 DB 和 DBSC） DBS 包含 DB 和 DBMSD） 没有任何关系答案：C二、填空题（1） 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 。

答案:45（2） 在面向对象方法中， 描述的是具有相似属性与操作的一组对象答案：类（3） 在关系模型中，把数据看成是二维表，每一个二维表称为一个 o答案：关系（4） 稈序测试分为静态分析和动态测试其中 是指不执行程序，而只是对程序文本进行检杳，通过阅读和讨论，分析和发现稈序中的错误答案：静态分析（5） 数据独立性分为逻辑独立性与物理独立性当数据的存储结构改变时，加逻笹结构可以不变，因此基于逻辑结构的应用程序不必修改，称为 答案：物理独立性2006年9月一、选择题（1）下列选项中不符合良好程序设计风格的是A. 源稈序要文档化B. 数据说明的次序要规范化C. 避免滥用goto语句D. 模块设计要保证高耦合、高内聚答案：D（2）从工程管理角度，软件设计一般分为两步完成，它们是A. 概要设计与详细设计B. 数据设计与接口设计C. 软件结构设计与数据设计D. 过程设计与数据设计答案:A（3） 下列选项中不属于软件生命周期开发阶段任务的是A. 软件测试B. 概要设计C. 软件维护D. 详细设计答案:C（4） 在数据库系统中，用户所见的数据模式为A. 概念模式B. 外模式C. 内模式D. 物理模式答案:B（5） 数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和A. 编码设计B. 测试阶段C. 运行阶段D. 物理设计答案：D6）设有如下三个关系表RB。