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