1、国家二级 C语言机试（公共基础知识）模拟试卷 13及答案与解析 一、选择题 1 下列关于二叉树的叙述中，正确的是 ( )。 （ A）叶子节点总是比度为 2的节点少一个 （ B）叶子节点总是比度为 2的节点多一个 （ C）叶子节点数是度为 2的节点数的两倍 （ D）度为 2的节点数是度为 1的节点数的两倍 2 下列叙述中正确的是 ( )。 （ A）循环队列是队列的一种链式存储结构 （ B）循环队列是队列的一种顺序存储结构 （ C）循环队列是非线性结构 （ D）循环队列是一种逻辑结构 3 支持子程序调用的数据结 构是 ( )。 （ A）栈 （ B）树 （ C）队列 （ D）二叉树 4 一个栈的初始
2、状态为空。现将元素 1、 2、 3、 4、 5、 A、 B、 C、 D、 E依次入栈，然后再依次出栈，则元素出栈的顺序是 ( )。 （ A） 12345ABCDE （ B） EDCBA54321 （ C） ABCDE12345 （ D） 54321EDCBA 5 下列叙述中错误的是 ( )。 （ A）栈是一种先进后出的线性表 （ B）队列是一种先进先出的线性表 （ C）栈与队列都是线性结构 （ D）栈和队列都是后进后出的线性表 6 下列叙 述中正确的是 ( )。 （ A）有一个以上根节点的数据结构不一定是非线性结构 （ B）只有一个根节点的数据结构不一定是线性结构 （ C）循环链表是非线性结构
3、 （ D）双向链表是非线性结构 7 在深度为 7的满二叉树中，叶子节点的个数为 ( )。 （ A） 32 （ B） 31 （ C） 64 （ D） 63 8 下列对于线性链表的描述中正确的是 ( )。 （ A）存储空间不一定连续，且各元素的存储顺序是任意的 （ B）存储空间不一定连续，且前件元素一定存储在后件元素的前面 （ C）存储空间必须连续，且前件元素 一定存储在后件元素的前面 （ D）存储空间必须连续，且各元素的存储顺序是任意的 9 下列叙述中正确的是 ( )。 （ A）算法的效率只与问题的规模有关，而与数据的存储结构无关 （ B）算法的时间复杂度是指执行算法所需要的计算工作量 （ C）
4、数据的逻辑结构与存储结构是一一对应的 （ D）算法的时间复杂度与空间复杂度一定相关 10 一棵二叉树中共有 70个叶子节点与 80个度为 1的节点，则该二叉树中的总节点数为 ( )。 （ A） 219 （ B） 221 （ C） 229 （ D） 231 11 下列与队列结 构有关联的是 ( )。 （ A）函数的递归调用 （ B）数组元素的引用 （ C）多重循环的执行 （ D）先到先服务的作业调度 12 下列叙述中正确的是 ( )。 （ A）对长度为 n的有序链表进行查找，最坏情况下需要的比较次数为 n （ B）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (n 2) （ C
5、）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (log2n) （ D）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (nlog2n) 13 在软件开发中，需求 分析阶段产生的主要文档是 ( )。 （ A）可行性分析报告 （ B）软件需求规格说明书 （ C）概要设计说明书 （ D）集成测试计划 14 下列描述中，不符合良好程序设计风格要求的是 ( )。 （ A）程序的效率第一，清晰第二 （ B）程序的可读性好 （ C）程序中要有必要的注释 （ D）输入数据前要有提示信息 15 软件 (程序 )调试的任务是 ( )。 （ A）诊断和改正程序中的错误 （ B）尽
6、可能多地发现程序中的错误 （ C）发现并改正程序中的所有错误 （ D）确定程序中错误的性质 16 定义 无符号整数类为 UINT，下面可以作为类 UINT实例化值的是 ( )。 （ A） 369 （ B） 369 （ C） 0 369 （ D）整数集合 1， 2， 3， 4， 5 17 对于长度为 n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 ( )。 （ A）冒泡排序为 n 2 （ B）冒泡排序为 n （ C）快速排序为 n （ D）快速排序为 n(n一 1) 2 18 两个或两个以上模块之间关联的紧密程度称为 ( )。 （ A）耦合度 （ B）内聚度 （ C）复杂度 （
7、 D）数据传输特性 19 数据 库设计中，用 ER图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的 ( )。 （ A）需求分析阶段 （ B）逻辑设计阶段 （ C）概念设计阶段 （ D）物理设计阶段 20 下列描述中正确的是 ( )。 （ A）软件测试应该由程序开发者来完成 （ B）程序经调试后一般不需要再测试 （ C）软件维护只包括对程序代码的维护 （ D）以上三种说法都不对 21 结构化程序设计中，下面对 GOTO语句使用描述正确的是 ( )。 （ A）禁止使用 GOTO语句 （ B）使用 GOTO语句程序效率高 （ C）应避免滥用 GOTO语句 （ D） GOTO语句确实一
8、无是处 22 数据库 DB、数据库系统 DBS、数据库管理系统 DBMS之间的关系是 ( )。 （ A） DB包含 DBS和 DBMS （ B） DBMS包含 DB和 DBS （ C） DBS包含 DB和 DBMS （ D）没有任何关系 23 有三个关系 R、 S和 T如下：则由关系 R和 S得到关系 T的操作是 ( )。 （ A）自然连接 （ B）并 （ C）交 （ D）差 24 数据库系统的三级模式不包括 ( )。 （ A）概念模式 （ B）内模式 （ C）外模式 （ D）数 据模式 25 下面叙述中错误的是 ( )。 （ A）软件测试的目的是发现错误并改正错误 （ B）对被调试的程序进行
9、 “错误定位 ”是程序调试的必要步骤 （ C）程序调试通常也称为 Debug （ D）软件测试应严格执行测试计划，排除测试的随意性 26 若实体 A和 B是一对多的联系，实体 B和 C是一对一的联系，则实体 A和 C的联系是 ( )。 （ A）一对一 （ B）一对多 （ C）多对一 （ D）多对多 27 在数据库设计中，将 ER图转换成关系数据模型的过程属于 ( )。 （ A）需求分析阶段 （ B）概 念设计阶段 （ C）逻辑设计阶段 （ D）物理设计阶段 28 在下列关系运算中，不改变关系表中的属性个数但能减少元组个数的是 ( )。 （ A）并 （ B）交 （ C）投影 （ D）笛卡儿乘积
10、29 下列描述中错误的是 ( )。 （ A）在数据库系统中，数据的物理结构必须与逻辑结构一致 （ B）数据库技术的根本目标是要解决数据的共享问题 （ C）数据库设计是指在已有数据库管理系统的基础上建立数据库 （ D）数据库系统需要操作系统的支持 30 有三个关系 R、 S和 T如下：由关系 R和 S通过运算得到关系 T，则所使用的运算为 ( )。 （ A）笛卡尔积 （ B）交 （ C）并 （ D）自然连接 国家二级 C语言机试（公共基础知识）模拟试卷 13答案与解析 一、选择题 1 【正确答案】 B 【试题解析】 由二叉树的性质可以知道，在二叉树中叶子节点总是比度为 2的节点多一个。 【知识模
11、块】 二级公共基础知识 2 【正确答案】 B 【试题解析】 本题主要考查循环队列的概念。循环队列作为队列的一种也应该是线性结构。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列。 【知识模块】 二 级公共基础知识 3 【正确答案】 A 【试题解析】 栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数的位置，主函数再接着往行，这种过程符合栈的特点。所以一般采用栈式存储方式。 【知识模块】 二级公共基础知识 4 【正确答案】 B 【试题解析】 栈是按照 “先进后出 ”或 “后进先出 ”的原则组织
12、数据的。所以出栈顺序是 EDCBA54321。 【知识模块】 二级公共基础知识 5 【正确 答案】 D 【试题解析】 栈是先进后出的线性表，队列是先进先出的线性表，二者均为线性结构。 【知识模块】 二级公共基础知识 6 【正确答案】 B 【试题解析】 在数据结构中，树这类的数据结构只有一个根节点，但它不是线性结构。 【知识模块】 二级公共基础知识 7 【正确答案】 C 【试题解析】 所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有节点都有两个子节点。也就是在满二叉树中，每一层上的节点数都是最大节点数，即在满二叉树的第 k层上有 2k 1个节点，深度为 m的 满二叉树有 2m 1个
13、节点。对于深度为 7的满二叉树，叶子节点所在的是第 7层，一共有 27 1=64个叶子节点。全部节点共 27一 1=127个。 【知识模块】 二级公共基础知识 8 【正确答案】 A 【试题解析】 一般来说，在线性表的链式存储结构中各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致。在线性链表中，各数据元素之间的前后件关系是由各节点的指针域来指示的。指向线性表中第一个节点的指针 head称为头指针，当 head=NULL(或 0)时称为空表。 【知识模块】 二级公共基础知识 9 【正确答案】 B 【试题解析】 算法的时间复杂度是指执行算法所需要的计算工作量。算法的
14、工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不 仅与问题的规模有关，还与数据的存储结构有关。 【知识模块】 二级公共基础知识 10 【正确答案】 A 【试题解析】 在二叉树中，叶子节点个数为 n0，度为 2的节点数 n2=n0一 1。本题中叶子节点的个数为 70，所以度为
15、 2的节点个数为 69。总节点数 =叶子节点数 +度为 1的节点数 +度为 2的节点数 =70+80+69=219。 【知识模块】 二级公共基础知识 11 【正确答案】 D 【试题解析】 队列中最先插入的元素将最先被删除，最后插入的元素将最后被删除。 【知识模块】 二级公共基础知 识 12 【正确答案】 A 【试题解析】 本题主要考查的知识点为查找技术。顺序查找的使用情况： 线性表为无序表； 表采用链式存储结构。二分法查找只适用于顺序存储的有序表，并不适用于线性链表。 【知识模块】 二级公共基础知识 13 【正确答案】 B 【试题解析】 需求分析的最终结果是生成软件需要规格说明书，可以为用户、
16、分析人员和设计人员之间的交流提供方便，可以直接支持目标与确认，又可以作为控制软件开发进程的依据。 【知识模块】 二级公共基础知识 14 【正确答案】 A 【试题解析】 一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序设计风格总体而言应该强调简单和清晰，程序必须是可以理解的。著名的 “清晰第一，效率第二 ”的论点已成为当今主导的程序设计风格。 【知识模块】 二级公共基础知识 15 【正确答案】 A 【试题解析】 在对程序进行了成功的测试之后将进入程序调试 (通常称 Debug，即排错 )。程序调试的任务是诊断和改正程序中的错误。它与软件测试不同，软件测试是尽可能多地发现软
17、件中的错误。先要发现软件的错误，然后借助于一定的调试工具去 执行并找出错误的具体位置。软件测试贯穿整个软件生命期，调试主要在开发阶段。 【知识模块】 二级公共基础知识 16 【正确答案】 B 【试题解析】 UINT表示的是无符号整数类，所以它的每个实例都是一个无符号整数，所以排除选项 A和选项 C，选项 D是整数集合，所以也排除。 【知识模块】 二级公共基础知识 17 【正确答案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后的扫描和 n 2遍的从后往前的扫描，需要的比较次数为 n(n1)，2。快 速排序法也是一种互换类的排序方法，但由于它比冒
18、泡排序法的速度快，因此，称为快速排序法。 【知识模块】 二级公共基础知识 18 【正确答案】 A 【试题解析】 模块的独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系较少且接口简单。衡量软件的模块独立性使用内聚性和耦合性两个定性度量标准。内聚性是对一个模块内部各个元素彼此结合的紧密程度的度量；耦合性是对模块间互相连接的紧密程度的度量。一般较优秀的软件设计，应尽量做到高内聚、低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。 【知识模块】 二级公共基础知识 19 【正确答案】 C 【试题解析】 ER模型 (实体联系模型 )是将现实世界的要求转化成实体
19、、联系、属性等几个基本概念，以及它们间的两种基本连接关系，并且可用一种图非常直观地表示出来。它属于数据库设计的概念设计阶段。 【知识模块】 二级公共基础知识 20 【正确答案】 D 【试题解析】 为了达到好的测试效果，应该由独立的第三方进行测试工作。因为从心理学角度讲，程序人员或设计方在测试自己的程序时，要采取客观的态度是会不同程 度地存在障碍的，所以选项 A错误。在程序调试时，修改了一个错误的同时可能引入了新的错误。解决的办法是在修改了错误之后，必须进行回归测试，所以选项 B错误。所谓软件维护，就是将交付的软件投入运行，并在运行使用中不断地维护，根据新提出的需求进行必要而且可能的扩充和删改，
20、所以选项C错误。 【知识模块】 二级公共基础知识 21 【正确答案】 C 【试题解析】 滥用 GOTO语句确实有害，应尽量避免；完全避免使用 GOTO语句并非是明智的方法，有些地方使用 GOTO语句会使程序流程更清楚、效率更高；争论的焦点不 应该放在是否取消 GOTO语句，而应该放在用在什么程序结构上。 【知识模块】 二级公共基础知识 22 【正确答案】 C 【试题解析】 数据库系统 (Database System简称 DBS)由下列几个部分组成：数据库 (DB)、数据库管理系统 (DBMS)、数据库管理员 (人员 )、系统平台之 硬件平台 (硬件 )、系统平台之二 软件平台 (软件 )。这
21、五个部分构成了一个以数据库为核心的完整的运行实体，称为数据库系统。其中 DB(DataBase)即数据库，是统一管理的相关数据的集合； DBMS(Database Management System)即数据库管理系统，是位于用户与操作系统之间的一层数据管理软件，为用户或应用程序提供访问 DB的方法。 【知识模块】 二级公共基础知识 23 【正确答案】 D 【试题解析】 由关系 T中的数据可以看出，其数据由属于关系 R但是不属于关系 S的数据组成。所以关系 T是由关系 R和 S通过差运算得到的。 【知识模块】 二级公共基础知识 24 【正确答案】 D 【试题解析】 数据库系统的三级模式包括概念模
22、式、外模式和内模式 (物理模式 )。 【知识模块】 二级公共基础知识 25 【正确答案】 A 【试题解析】 软件测试是为了发现错误而执行程序的过程。软件测试要严格执行测试计划，排除测试的随意性。程序调试通常也称 Debug，对被调试的程序进行“错误 ”定位是程序调试的必要步骤。 【知识模块】 二级公共基础知识 26 【正确答案】 B 【试题解析】 由于 B和 C有一一对应的联系，而 A和 B之间有一对多的联系，则通过关系之间的传递，则 A和 C之间也是一对多的联系。 【知识模块】 二级公共基础知识 27 【正确答案】 C 【试题解析 】 数据库的设计阶段包括需求分析、概念设计、逻辑设计和物理设
23、计，其中将 ER图转换成关系数据模型的过程属于逻辑设计阶段。 【知识模块】 二级公共基础知识 28 【正确答案】 B 【试题解析】 关系 R与 S经交运算后所得到的关系是由那些既在 R内又在 S内的有序组所组成，记为 RS，形式定义如下： RSt R t S=R一 (RS)。所以不改变关系表中的属性个数，但能减少元组个数的是关系表之间的交操作。 【知识模块】 二级公共基础知识 29 【正确答案】 A 【试题解析】 在数据 库系统中，物理独立性是指数据的物理结构 (包括存储结构、存取方式等 )的改变。如存储设备的更换、物理存储的更换、存取方式改变等都不影响数据库的逻辑结构，从而不致引起应用程序的变化。 【知识模块】 二级公共基础知识 30 【正确答案】 D 【试题解析】 在实际应用中，最常用的连接是一个叫自然连接的特例。它满足下面的条件：两关系间有公共域；通过公共域的相等值进行连接。通过观察三个关系 R， S， T的结果可知关系 T是由关系 R和 S进行自然连接得到的。 【知识模块】 二级公共基础知识
