1、国家二级 C语言（公共基础知识）机试模拟试卷 10及答案与解析 一、选择题 1 有二叉树如下图所示： 则前序序列为 ( )。 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 2 设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为 ( )。 （ A） JIHGFEDCBA （ B） DGHEBIJFCA （ C） GHIJDEFBCA （ D） ABCDEFGHIJ 3 某二叉树的中序遍历序列为 CBADE，后序遍历序 列为 CBEDA，则前序遍历序列为 ( )。 （ A） CBADE （ B
2、） CBEDA （ C） ABCDE （ D） EDCBA 4 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度(根结点在第 1层 )为 ( )。 （ A） 2 （ B） 3 （ C） 4 （ D） 5 5 某完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。该完全二叉树的前序序列为 ( )。 （ A） ABCDEFGH （ B） ABDHECFG （ C） HDBEAFCG （ D） HDEBFGCA 6 设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树
3、的遍历结果为有序序列的是 ( )。 （ A）前序序列 （ B）中序序列 （ C）后序序列 （ D）前序序列或后序序列 7 设二叉树中共有 15个结点，其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为 ( )。 （ A） 4 （ B） 6 （ C） 15 （ D）不存在这样的二叉树 8 在长度为 n的顺序表中查找一个元素，假设需要 查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为( )。 （ A） n 4 （ B） n （ C） 3n 4 （ D） (n+1) 2 9 在长度为 n的顺序表中查找一个元素，假设需要查找
4、的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为 ( )。 （ A） n （ B） 3n 4 （ C） n 2 （ D） n 4 10 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度 相同的是 ( )。 （ A）在顺序存储的线性表中寻找最大项 （ B）在顺序存储的线性表中进行顺序查找 （ C）在顺序存储的有序表中进行对分查找 （ D）在链式存储的有序表中进行查找 11 线性表的长度为 n。在最坏情况下，比较次数为 n-1的算法是 ( )。 （ A）顺序查找 （ B）同时寻找最大项与最小项 （ C）寻找最
5、大项 （ D）有序表的插入 12 下列叙述中正确的是 ( )。 （ A）二分查找法只适用于顺序存储的有序线性表 （ B）二分查找法适用于任何存储结构的有序线性表 （ C）二 分查找法适用于有序循环链表 （ D）二分查找法适用于有序双向链表 13 在快速排序法中，每经过一次数据交换 (或移动 )后 ( )。 （ A）只能消除一个逆序 （ B）能消除多个逆序 （ C）不会产生新的逆序 （ D）消除的逆序个数一定比新产生的逆序个数多 14 下列序列中不满足堆条件的是 ( )。 （ A） (98， 95， 93， 94， 89， 90， 76， 80， 55， 49) （ B） (98， 95， 93
6、， 94， 89， 85， 76， 64， 55， 49) （ C） (98， 95， 93， 94， 89， 90， 76， 64， 55， 49) （ D） (98， 95， 93， 96， 89， 85， 76， 64， 55， 49) 15 下列各组排序法中，最坏情况下比较次数相同的是 ( )。 （ A）简单选择排序与堆排序 （ B）简单插入排序与希尔排序 （ C）冒泡排序与快速排序 （ D）希尔排序与堆排序 16 设顺序表的长度为 16，对该表进行简单插入排序。在最坏情况下需要的比较次数为 ( )。 （ A） 120 （ B） 60 （ C） 30 （ D） 15 17 下面属于良好
7、程序设计风格的是 ( )。 （ A）源程序文档化 （ B）程序效率第一 （ C）随意使用无条件转移语句 （ D）程序输入输出的随意性 18 下面不属于结构化程序设计原则的是 ( )。 （ A）逐步求精 （ B）自顶向下 （ C）模块化 （ D）可继承性 19 结构化程序的三种基本控制结构是 ( )。 （ A）顺序、选择和调用 （ B）过程、子程序和分程序 （ C）顺序、选择和重复 (循环 ) （ D）调用、返回和转移 20 下面对 “对象 ”概念描述正确的是 ( )。 （ A）属性就是对象 （ B）操作是对象的动态属性 （ C）任何对象都必须 有继承性 （ D）对象是对象名和方法的封装体 21
8、 下面不属于对象主要特征的是 ( )。 （ A）对象唯一性 （ B）对象分类性 （ C）对象多态性 （ D）对象可移植性 22 将自然数集设为整数类 ，则下面属于类 实例的是 ( )。 （ A） -518 （ B） 5 18 （ C） 518 （ D） 518E-2 23 下面对软件描述错误的是 ( )。 （ A）文档是不可执行的 （ B）程序和数据是可执行的 （ C）软件文档是与程序开发、维护和应用无关的资料 （ D）软件是程序、数据及相关 文档的集合 24 下面对软件特点描述正确的是 ( )。 （ A）软件具有明显的制作过程 （ B）软件在使用中存在磨损、老化问题 （ C）软件复制不涉及知
9、识产权 （ D）软件是一种逻辑实体，具有抽象性 25 下面属于系统软件的是 ( )。 （ A） UNIX系统 （ B） ERP系统 （ C）办公自动化系统 （ D）学生成绩管理系统 26 下列叙述中正确的是 ( )。 （ A）软件工程是为了解决软件生产率问题 （ B）软件工程的三要素是方法、工具和进程 （ C）软件工程是用于软件的定义、开 发和维护的方法 （ D）软件工程是用工程、科学和数学的原则与方法研制、维护计算机软件的有关技术及管理方法 27 下列叙述中正确的是 ( )。 （ A）软件过程是软件开发过程 （ B）软件过程是软件维护过程 （ C）软件过程是软件开发过程和软件维护过程 （ D
10、）软件过程是把输入转化为输出的一组彼此相关的资源和活动 28 软件生命周期是指 ( )。 （ A）软件的运行和维护 （ B）软件的需求分析、设计与实现 （ C）软件的实现和维护 （ D）软件产品从提出、实现、使用维护到停止使用退役的过程 29 软件生命周期可分为定义阶段、开发阶段和维护阶段，下面属于定义阶段任务的是 ( )。 （ A）软件设计 （ B）软件测试 （ C）可行性研究 （ D）数据库设计 30 软件生存周期中，解决软件 “做什么 ”的阶段是 ( )。 （ A）需求分析 （ B）软件设计 （ C）软件实现 （ D）可行性研究 国家二级 C语言（公共基础知识）机试模拟试卷 10答案与解
11、析 一、选择题 1 【正确答案】 A 【试题解析】 前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时， 仍然先访问根结点，然后遍历左子树，最后遍历右子树。故本题前序序列是 ABDEGCFH。 中序遍历首先遍历左子树，然后访问跟结点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟结点，最后遍历右子树。故本题的中序序列是 DBGEAFHC。 后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。故本题的后序序列是 DGEBHFCA。 【知识模块】 公共基础知识 2 【正确答案】 B
12、【试题解析】 二叉树的前序序列为 A。 BDEGHCFIJ，由于前序遍历首先访问根结点，可以确定该二叉树的根结点是 A。再由中序序列为 DBGEHACIFJ，可以得到结点 D、 B、 G、 E、 H位于根结点的左子树上，结点 C、 I、 F、 J位于根结点的右子树上。由于中序遍历和后序遍历都是先遍历左子树，故本题后序遍历首先访问 D结点；再由后序遍历是最后访问根结点，故本题后序遍历最后访问的结点是根结点 A。采用排除法可知，后续序列为 DGHEBIJFCA。 【知识模块】 公共基础知识 3 【正确答案】 C 【试题解析】 二叉树的后序遍历序列为 CBEDA，由于后序遍历最后访问根结点，可以确定
13、该二叉树的根结点是 A。再由中序遍历序列为 CBADE，可以得到子序列 (CB)一定在左子树中，子序列 (DE)一定在右子树中。结点 C、 B在中序序列和后序序列中顺序未变，说明结点 B是结点 C的父结点；结点 D、 E在中序序列和后序序列中顺序相反，说明结点 D是结点 E的父结点。因此该二叉树的前序遍历序列为 ABCDE。 【知识模块】 公共基础知识 4 【正确答案】 C 【试题解析】 二叉树的前序序列为 ABCDEFG，则 A为根结点；中序序列为DCBAEFG，可知结点 D、 C、 B位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上。另外，结点 B、 C、 D在前序序列和中序
14、序列中顺序相反，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。故二叉树深度为 4。 【知识模块】 公共基础知识 5 【正确答案】 B 【试题解析】 完全二叉树的特点是除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。根据这一特点，再根据题意输出序列为 ABCDEFGH，可以得到该二叉树的结构如下： 故此完全二 叉树的前序序列为 ABDHECFG。 【知识模块】 公共基础知识 6 【正确答案】 B 【试题解析】 中序遍历的次序是先遍历左子树，再遍历根结点，最后遍历右子树。而在排序二叉树中，左子
15、树结点值根结点值 右子树结点值，要使对排序二叉树的遍历结果为有序序列，只能采用中序遍历。 【知识模块】 公共基础知识 7 【正确答案】 C 【试题解析】 在具有 n个结点的二叉树中，如果各结点值互不相同，若该二叉树的前序序列与中序序列相同，则说明该二叉树只有右子树，左子树为空，二叉树的深度为 n；若该二叉树的后序序列与中序序列相同，则说明该二叉树只有左子树，右子树为空，二叉树的深度为 n。故本题中二叉树的深度为 15。 【知识模块】 公共基础知识 8 【正确答案】 D 【试题解析】 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1；在最坏情况下，最后一个元素才是要找的元素
16、，则比较次数为 n。则平均比较次数： (1+2+n) n=(n(n+1) 2) n=(n+1) 2。 【知识模块】 公共基础知识 9 【正确答案】 B 【试题解析】 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为 n。这是找到元素的情况。如果没有找到元素，则要比较 n次。因此，平均需要比较：找到元素的情况 +未找到元素的情况 =(1+2+ -+n) n ，大约为 3n 4。 【知识模块】 公共基础知识 10 【正确答案】 A 【试题解析】 寻找最大项，无论如何都要查看所有 的数据，与数据原始排列顺序没有多大关系，无
17、所谓最坏情况和最好情况，或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找，都与要找的数据和原始的数据排列情况有关，最好情况是第 1次查看的一个数据恰好是要找的数据，只需要比较 1次；如果没有找到再查看下一个数据，直到找到为止，最坏情况下是最后一次查看的数据才是要找的，顺序查找和对分查找在最坏情况下比较次数分别是 n和 log2n，平均情况则是 “1最坏情况 ”的平均，因而是不同的。 【知识模块】 公共基础知识 11 【正确答案】 C 【试题解析】 顺序查找要逐个查看所有元素，会比较 n次。在最坏情况下，寻找最大项无论如何需要查看表中的所有元素， n个元素比较次数
18、为 n-1。同时寻找最大项和最小项，需要为判断较大值和较小值分别进行比较，会有更多的比较次数。有序表的插入最坏情况下是插入到表中的最后一个元素的后面位置，则会比较 n次。 【知识模块】 公共基础知识 12 【正确答案】 A 【试题解析】 二分查找法 (又称对分查找法 )只适用于顺序存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列 (即从小到大，但允许相邻元素 值相等 )。 【知识模块】 公共基础知识 13 【正确答案】 B 【试题解析】 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序的思想是：从线性表中选取一个元素，设为
19、 T，将线性表中后面小于 T的元素移到前面，而前面大于 T的元素移到后面，结果就将线性表分成两部分 (称两个子表 )， T插入到其分割线的位置处，这个过程称为线性表的分割，然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较，可以实线通过一次交换而消除多 个逆序，但由于均与 T(基准元素 )比较，也可能会产生新的逆序。 【知识模块】 公共基础知识 14 【正确答案】 D 【试题解析】 根据堆的定义， n个元素的序列 (h1， h2， h n)，当且仅当 hih2i；且 hih2i+1时为小顶堆，当且仅当 hih2i且 hih2i+1时为大顶堆。 D项中， h2=
20、95，h4=96， h2 h4，但 h5=89， h2 h5，不满足小顶堆和大顶堆条件。 【知识模块】 公共基础知识 15 【正确答案】 C 【试题解析】 对于长度为 n的线性表，最坏情况下查找或排序 的次数如下表：【知识模块】 公共基础知识 16 【正确答案】 A 【试题解析】 简单插入排序在最坏情况下，即初始排序序列是逆序的情况下，比较次数为 n(n-1) 2，移动次数为 n(n-1) 2。本题中 n=16， 16(16-1)2=815=120。 【知识模块】 公共基础知识 17 【正确答案】 A 【试题解析】 要形成良好的程序设计风格，主要应注意和考虑：源程序文档化；数据说明的次序规范化
21、，说明语句中变量安排有序化，使用注释来说明复杂数据的结构；程序编写要做到清晰第一 、效率第二，先保证程序正确再要求提高速度，避免不必要的转移；对所有的输入数据都要进行检验，确保输入数据的合法性。 【知识模块】 公共基础知识 18 【正确答案】 D 【试题解析】 结构化程序设计方法的原则包括：自顶向下、逐步求精、模块化、限制使用 goto语句。可继承性是面向对象方法的特点。 【知识模块】 公共基础知识 19 【正确答案】 C 【试题解析】 1966年 Boehm和 Jacopini证明了程序设计语言仅仅使用顺序、选择和重复三种基本控制结构就足以表达出各种其他形式结 构的程序设计方法。 【知识模块
22、】 公共基础知识 20 【正确答案】 B 【试题解析】 对象是由描述该对象属性的数据以及可以对这些数据施加的所有操作封装在一起构成的统一体。对象可以做的操作表示它的动态行为，通常也称为方法或服务，属性即对象所包含的信息。对象名唯一标识一个对象。对象可以有继承性，但并不是任何对象都必须有继承性。 【知识模块】 公共基础知识 21 【正确答案】 D 【试题解析】 对象有如下一些基本特点： 标识唯一性：指对象是可区分的，并且由对象的内在本质来区分，而 不是通过描述来区分。 分类性：指可以将具有相同属性和操作的对象抽象成类。 多态性：指同一个操作可以是不同对象的行为，不同对象执行同一类操作产生不同的结
23、果。 封装性：从外面看只能看到对象的外部特征，对象的内部对外是不可见的。 模块独立性好。 【知识模块】 公共基础知识 22 【正确答案】 C 【试题解析】 类是具有共同属性、共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。自然数集是全体非负整数组成的集合， A项是负数实例， B项是浮点数实例，D项是用科学计数法表示的浮点数实例。 【知识模块】 公共基础知识 23 【正确答案】 C 【试题解析】 软件是程序、数据及相关文档的集合。程序、数据和相关文档又称为软件的三要素。其中，程序是软件开发人员根据用户需求开发的、用程序设计语言描述的
24、、适合计算机执行的指令 (语句 )序列；数据是使程序能正常操纵信息的数据结构；文档是与程序开发、维护和使用有关的图文资料。可见，软件有两部分组成：一是机器可执行的程序和数据；二是机器不可执行的文档。 【知识模块】 公共基础知识 24 【正确答案】 D 【试题解析】 软件具有以下特点：软件是一种逻辑实体，而不是物理实体，具有抽象性；软件的生产与硬件不同，它没有明显的制作过程；软件在运行、使用期间不存在磨损、老化问题；软件的开发、运行对硬件和环境具有依赖性；软件复杂性高，成本昂贵；软件开发涉及诸多的社会因素 (包括软件知识产权及法律等问题 )。 【知识模块】 公共基础知识 25 【正确答案】 A
25、【试题解析】 软件按功能可以分为应用软件、系统软件和支撑软件 (或工具软件 )。系统软件是管理计算机的资源，提高计算机使用效率并服 务于其他程序的软件，如操作系统，编译程序，汇编程序，数据库管理系统和网络软件等。应用软件是为解决特定领域的应用而开发的软件。例如，事务处理软件，工程与科学计算软件，实时处理软件，嵌入式软件，人工智能软件等应用性质不同的各种软件。支撑软件是介于系统软件和应用软件之间，协助用户开发的工具性软件。 【知识模块】 公共基础知识 26 【正确答案】 D 【试题解析】 软件工程是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法，是应用于计算机软件的定
26、义、开发和维护的一整套方法、 工具、文档、实践标准和工序。软件工程的目标是在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品，追求这些目标有助于提高软件产品的质量和开发效率，减少维护的困难。软件工程包含 3个要素：方法、工具和过程。 【知识模块】 公共基础知识 27 【正确答案】 D 【试题解析】 软件过程是把输入转化为输出的一组彼此相关的资源和活动。软件过程是为了获得高质量软件所需要完成的一系列任务的框架，它规定了完成各项任务的工 作步骤。软件过程所进行的基本活动主要有软件规格说明、软件开发或软件设计
27、与实线、软件确认、软件演进。在过程结束时，将输入 (用户要求 )转化为输出 (软件产品 )。 【知识模块】 公共基础知识 28 【正确答案】 D 【试题解析】 通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。也就是说，软件产品从考虑其概念开始，到该软件产品不能使用为止的整个时期都属于软件生命周期。 【知识模块】 公共基础知识 29 【正确答案】 C 【试题解析】 软件生命周期可分为定义阶 段、开发阶段和维护阶段。 软件定义阶段的任务是：确定软件开发工作必须完成的目标；确定工程的可行性。 软件开发阶段的任务是：具体完成设计和实现定义阶段所定义的软件，通常包括总体设计、详细设计、编码和测试。其中总体设计和详细设计又称为系统设计，编码和测试又称为系统实现。 软件维护阶段的任务是：使软件在运行中持久地满足用户的需要。 【知识模块】 公共基础知识 30 【正确答案】 A 【试题解析】 软工生命周期可细化为可行性研究和计划制定、需求分析、软件设计 (总体设计和详细设计 )、编码、软件测试、运 行和维护等阶段。需求分析是对待开发软件提出的需求进行分析并给出详细定义，是解决软件 “做什么 ”的阶段。软件设计是解决软件 “怎么做 ”的阶段。 【知识模块】 公共基础知识
