1、国家二级 C语言机试（选择题）模拟试卷 8及答案与解析 一、选择题 1 对长度为 n的线性表作快速排序，在最坏情况下，比较次数为（ ）。 （ A） n （ B） n-1 （ C） n(n-1) （ D） n(n-1)/2 2 下列叙述中正确的是（ ）。 （ A）有且只有一个根结点的数据结构一定是线性结构 （ B）每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构 （ C）有且只有一个根结点的数据结构一定是非线性结构 （ D）有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构 3 下 列叙述中错误的是（ ）。 （ A）在双向链表中，可以从任何一个结点开始直接遍历到所有结
2、点 （ B）在循环链表中，可以从任何一个结点开始直接遍历到所有结点 （ C）在线性单链表中，可以从任何一个结点开始直接遍历到所有结点 （ D）在二叉链表中，可以从根结点开始遍历到所有结点 4 某二叉树共有 13个结点，其中有 4个度为 1的结点，则叶子结点数为（ ）。 （ A） 5 （ B） 4 （ C） 3 （ D） 2 5 设栈的顺序存储空间为 S(1: 50),初始状态为 top=0。现经过一系列入栈与退栈运算后， top=20，则当前栈中的元素个数为（ ）。 （ A） 30 （ B） 29 （ C） 20 （ D） 19 6 下列叙述中正确的是（ ）。 （ A）栈与队列都只能顺序存储
3、（ B）循环队列是队列的顺序存储结构 （ C）循环链表是循环队列的链式存储结构 （ D）以上说法都不对 7 设某二叉树的前序序列为 ABC，中序序列为 CBA，则该二叉树的后序序列为（ ）。 （ A） BCA （ B） CBA （ C） ABC （ D） CAB 8 下列排序方法中，最坏情况下时间复杂度最小的是（ ）。 （ A）冒泡排序 （ B）快速排序 （ C）堆排序 （ D）直接插入排序 9 为了对有序表进行对分查找，则要求有序表（ ）。 （ A）只能顺序存储 （ B）只能链式存储 （ C）可以顺序存储也可以链式存储 （ D）任何存储方式 10 设某二叉树的后序序列为 CBA，中序序列为
4、ABC，则该二叉树的前序序列为（ ）。 （ A） BCA （ B） CBA （ C） ABC （ D） CAB 11 下列叙述中正确的是（ ）。 （ A）存储空间不连续的所有链表一定是非线性结构 （ B）结点中有多个指针域的所有链表一定是非线性结构 （ C）能顺序存储的 数据结构一定是线性结构 （ D）带链的栈与队列是线性结构 12 算法时间复杂度的度量方法是（ ）。 （ A）算法程序的长度 （ B）执行算法所需要的基本运算次数 （ C）执行算法所需要的所有运算次数 （ D）执行算法所需要的时间 13 设循环队列为 Q(1: m)，初始状态为 front=rear=m。现经过一系列的入队与退队
5、运算后， front=rear=1，则该循环队列中的元素个数为（ ）。 （ A） 1 （ B） 2 （ C） m-1 （ D） 0或 m 14 在最坏情况下（ ）。 （ A）快速排序的时间 复杂度比冒泡排序的时间复杂度要小 （ B）快速排序的时间复杂度比希尔排序的时间复杂度要小 （ C）希尔排序的时间复杂度比直接插入排序的时间复杂度要小 （ D）快速排序的时间复杂度与希尔排序的时间复杂度是一样的 15 在深度为 7的满二叉树中，度为 2的结点个数为（ ）。 （ A） 64 （ B） 63 （ C） 32 （ D） 31 16 设栈的顺序存储空间为 S(1: m)，初始状态为 top=m+1。现
6、经过一系列入栈与退栈运算后， top=20，则当前栈中的元素个数为（ ）。 （ A） 30 （ B） 20 （ C） m-19 （ D） m-20 17 算法空间复杂度的度量方法是（ ）。 （ A）算法程序的长度 （ B）算法所处理的数据量 （ C）执行算法所需要的工作单元 （ D）执行算法所需要的存储空间 18 下面不属于软件开发阶段任务的是（ ）。 （ A）测试 （ B）可行性研究 （ C）设计 （ D）实现 19 设循环队列为 Q(1: m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后， front=15， rear=20。现要在该循环队列中寻找最大值的元素，最坏
7、情况下需要比较的次数为（ ） 。 （ A） 4 （ B） 6 （ C） m-5 （ D） m-6 20 下列叙述中正确的是（ ）。 （ A）循环队列属于队列的链式存储结构 （ B）双向链表是二叉树的链式存储结构 （ C）非线性结构只能采用链式存储结构 （ D）有的非线性结构也可以采用顺序存储结构 21 某二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为（ ）。 （ A） n+1 （ B） n-1 （ C） 2n （ D） n/2 22 下列叙述中错误的是（ ）。 （ A）算法的时间复杂度与算法所处理数据的存储结构有直接关系 （ B）算法 的空间复杂度与算法所处理数据的存储结构有直接关系
8、 （ C）算法的时间复杂度与空间复杂度有直接关系 （ D）以上说法都不对 23 设栈的顺序存储空间为 S(0:49)，栈底指针 bottom=49，栈顶指针 top=30（指向栈顶元素）。则栈中的元素个数为（ ）。 （ A） 30 （ B） 29 （ C） 20 （ D） 19 24 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度（根结点在第 1层）为（ ）。 （ A） 2 （ B） 3 （ C） 4 （ D） 5 25 下列叙述中正确的是 （ ）。 （ A）存储空间连续的数据结构一定是线性结构 （ B）存储空间不连续的数据结构一定是非线性结构 （ C）没有
9、根结点的非空数据结构一定是线性结构 （ D）具有两个根结点的数据结构一定是非线性结构 26 下列叙述中正确的是（ ）。 （ A）带链队列的存储空间可以不连续，但队头指针必须大于队尾指针 （ B）带链队列的存储空间可以不连续，但队头指针必须小于队尾指针 （ C）带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针 （ D）以上说法都不对 27 设循环队列为 Q(1:m)，其 初始状态为 front=rear=m。经过一系列入队与退队运算后， front=20， rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（ ）。 （ A） 5 （ B） 6 （ C
10、） m-5 （ D） m-6 28 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为（ ）。 （ A） EFGDCBA （ B） DCBEFGA （ C） BCDGFEA （ D） DCBGFEA 29 下列叙述中正确的是（ ）。 （ A）在链表中，如果每个结点有两个指针域，则该 链表一定是非线性结构 （ B）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构 （ C）在链表中，如果每个结点有两个指针域，则该链表一定是线性结构 （ D）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构 30 下列叙述中错误的是（
11、 ）。 （ A）在带链队列中，队头指针和队尾指针都是在动态变化的 （ B）在带链栈中，栈顶指针和栈底指针都是在动态变化的 （ C）在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的 （ D）以上说法均不对 31 设数据元素 的集合 D= 1,2,3,4,5 ，则满足下列关系 R的数据结构中为线性结构的是（ ）。 （ A） R= (1,2), (3,4), (5,1) （ B） R= (1,3), (4,1), (3,2), (5,4) （ C） R= (1,2), (2,3), (4,5) （ D） R= (1,3), (2,4), (3,5) 32 下列叙述中正确的是（ ）。 （ A）链
12、表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 （ B）线性表的链式存储结构中，每个结点必须有指向前 件和指向后件的两个指针 （ C）线性表的链式存储结构中，每个结点只能有一个指向后件的指针 （ D）线性表的链式存储结构中，叶子结点的指针只能是空 33 一个栈的初始状态为空。现将元素 A,B,C,D,E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为（ ）。 （ A） ABC （ B） CBA （ C） EDC （ D） CDE 34 某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二
13、叉树的深度（根结点在第 1层）为（ ）。 （ A） 5 （ B） 4 （ C） 3 （ D） 2 35 以下叙述中正确的是（ ）。 （ A）如果企图通过一个空指针来访问一个存储单元，将会得到一个出错信息 （ B）即使不进行强制类型转换，在进行指针赋值运算时，指针变量的基类型也可以不同 （ C）设变量 p是一个指针变量，则语句 p=0;是非法的，应该使用 p=NULL; （ D）指针变量之间不能用关系运算符进行比较 36 结构化程序设计的基本原则不包括（ ）。 （ A）多态性 （ B）自顶向下 （ C）模块化 （ D）逐步求精 37 在面向对象方法中， 不属于 “对象 “基本特点的是（ ）。 （
14、 A）一致性 （ B）分类性 （ C）多态性 （ D）标识唯一性 38 面向对象方法中，继承是指（ ）。 （ A）一组对象所具有的相似性质 （ B）一个对象具有另一个对象的性质 （ C）各对象之间的共同性质 （ D）类之间共享属性和操作的机制 39 结构化程序所要求的基本结构不包括（ ）。 （ A）顺序结构 （ B） GOTO跳转 （ C）选择（分支）结构 （ D）重复（循环）结构 40 定义无符号整数类为 UInt，下面可以作为类 UInt实例化值的是（ ）。 （ A） -369 （ B） 369 （ C） 0.369 （ D）整数集合 1,2,3,4,5 国家二级 C语言机试（选择题）模拟
15、试卷 8答案与解析 一、选择题 1 【正确答案】 D 【试题解析】 在最坏情况下，快速排序需要比较 n(n-1)/2次。 【知识模块】 数据结构与算法 2 【正确答案】 D 【试题解析】 有且只有一个根结点的数据结构可以是线性结构，如队列，也可以是非线性结构，如二叉树，所以选项 D）正确。选项 B）中，如果有两个根结点，则不符合线性结构的条件，说法错误。本题答案 选 D）。 【知识模块】 数据结构与算法 3 【正确答案】 C 【试题解析】 在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点，选项 C）说法错误。 【知识模块】 数据结构与算法 4 【正确答案
16、】 A 【试题解析】 根据题意，该二叉树中叶子结点数和度为 2的结点数的和为 9。根据二叉树的基本性质，叶子结点比度为 2的结点多 1个，则度为 2的结点个数为4，叶子结点的个数为 5，所以答案选 A。 【知识模块】 数据结构与算法 5 【正确答案】 C 【试题解析】 在栈中， top位置直接反映栈中元素的个数， top=20，则说明当前栈中的元素个数为 20。 【知识模块】 数据结构与算法 6 【正确答案】 B 【试题解析】 栈和队列都可以采用链式存储结构，选项 A）错误。队列的顺序存储结构一般采用循环队列的形式，所以循环队列是队列的顺序存储结构，选项 B正确，选项 C）错误。答案选 B）。
17、 【知识模块】 数据结构与算法 7 【正确答案】 B 【试题解析】 前序序列为 ABC，中序序列为 CBA，说明根结点为 A，且 B和 C均在该 A的左子 树上；结点 B和 C的前序序列为 BC，中序序列为 CB，则说明结点 C在结点 B的左子树上，根据以上分析，该二叉树的后序序列为 CBA，答案选B）。 【知识模块】 数据结构与算法 8 【正确答案】 C 【试题解析】 在最坏情况下，堆排序时间复杂度为 O(nlog2n)，其余选项均为O(n2)，所以答案选 C。 【知识模块】 数据结构与算法 9 【正确答案】 A 【试题解析】 对分查找必须满足用顺序存储结构，且线性表是有序表两个条件，答案选
18、 A。 【知识模块】 数据结构与算法 10 【正确 答案】 C 【试题解析】 后序序列为 CBA，中序序列为 ABC，则说明， A为根结点，并且B和 C均在 A的右子树上；结点 B和 C中，后序序列为 CB，中序序列为 BC，则说明结点 C在结点 B的右子树上，根据分析可得，该二叉树的前序序列为 ABC，答案选 C。 【知识模块】 数据结构与算法 11 【正确答案】 D 【试题解析】 判断一个非空的数据结构是否为线性结构必须满足以下两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项 A）、 B）和 C）都不能判定 是否是线性结构，选项 D）正
19、确，答案选 D）。 【知识模块】 数据结构与算法 12 【正确答案】 B 【试题解析】 算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，答案选 B。 【知识模块】 数据结构与算法 13 【正确答案】 D 【试题解析】 在循环队列中，当 front=rear时，有两种情况，一种是队列为空，另一种是队列为满，所以答案选 D。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 在最坏情况 下，快速排序、冒泡排序和直接插入排序所需要的比较次数为 O(n2)，希尔排序所需要的比较次数为 O(n1.5)，所以答案选 C。 【知识模块】 数据
20、结构与算法 15 【正确答案】 B 【试题解析】 根据满二叉树的性质，深度为 7的满二叉树共有 22-1=127个结点。根据二叉树的性质，该满二叉树在第 7层上，共有 27-1=64个结点，即共有 64个叶子结点，那么度为 2的结点个数为 127-64=63个。 【知识模块】 数据结构与算法 16 【正确答案】 C 【试题解析】 初始状态为 top=m+1，经过运算之后， top=20，则当前栈中元素个数为 m+1-20=m-19个。 【知识模块】 数据结构与算法 17 【正确答案】 D 【试题解析】 算法的空间复杂度，一般是指执行这个算法所需要的内存空间，答案选 D。 【知识模块】 数据结构
21、与算法 18 【正确答案】 B 【试题解析】 可行性研究是属于软件定义阶段的任务，所以答案选 B。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 初始状态为 front=rear=m，说明初始状态为空。经过一系 列入队与退队运算后， front=15， rear=20，则当前共有 5个元素，则在最坏情况下，需要比较的次数为 4次，答案选 A。 【知识模块】 数据结构与算法 20 【正确答案】 D 【试题解析】 循环队列属于队列的顺序存储结构，选项 A）错误；二叉树的存储结构为二叉链表，选项 B）错误；非线性结构也可以采用顺序存储结构，因此选项 C）错误，选项 D）正确，答
22、案为 D）。 【知识模块】 数据结构与算法 21 【正确答案】 B 【试题解析】 根据二叉树的性质，叶子结点的个数比度为 2的结点数多一 个，因此答案为 B)。 【知识模块】 数据结构与算法 22 【正确答案】 C 【试题解析】 算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，并且两者之间美欧直接关系，因此答案选 C。 【知识模块】 数据结构与算法 23 【正确答案】 C 【试题解析】 栈底指针 bottom=49，栈顶指针 top=30，则栈中的元素个数为 49-30+1=20个，答案选 C。
23、【知识模块】 数据结构与 算法 24 【正确答案】 C 【试题解析】 该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知 A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上；并且结点 B、 C、 D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树深度为 4，答案选 C。 【知识模块】 数据结构与算法 25 【正确答案】 D 【试题解析】 判断一个非空的 数据结构是否为线性结构必须满足以下两个条件： 有且只
24、有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项 A）、 B）和 C）都不能判定是否是线性结构，选项 D）正确，答案选 D）。 【知识模块】 数据结构与算法 26 【正确答案】 C 【试题解析】 带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，答案选 C。 【知识模块】 数据结构与算法 27 【正确答案】 D 【试题解析】 该循环队列的容量为 m，队列中共有 15-20+m=m-5个 元素，如果想找出其中的最小值，最坏情况下需要比较 m-5-1=m-6次。 【知识模块】 数据结构与算法 28 【正确答案】 D 【试题解析】 该二叉树的前序序
25、列为 ABCDEFG，中序序列为 DCBAEFG，可知 A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上；并且结点 B、 C、 D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的后序遍历序列为 DCBGFEA，答案选 D。 【知识模块】 数据结构与算法 29 【正确答案】 B 【试题解析】 判断一个非空的数据结构是否为线性结构必须满足以下两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。选项
26、B）中，如果有两个结点的同一个指针域的值相等，则说明至少有一个结点有两个前件，不符合线性结构的定义，所以答案选 B）。 【知识模块】 数据结构与算法 30 【正确答案】 B 【试题解析】 在栈结构中，插入和删除操作都是在栈顶进行操作，相对应的在带链栈中， 栈顶指针是在动态变化的，但栈底指针是不变的，所以选项 B）说法错误。 【知识模块】 数据结构与算法 31 【正确答案】 B 【试题解析】 关系 R中的每个结点由两个部分构成，分别是数据域和指针域。选项 B）中可以看出，元素序列为 54132 ，符合线性结构的条件。选项A）、选项 C）和选项 D）中分别有两个根结点，不符合线性结构的条件。所以答
27、案选 B）。 【知识模块】 数据结构与算法 32 【正确答案】 A 【试题解析】 在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域 用于指向该节点的前一个或后一个结点，所以选项 B）、 C）、 D）说法错误。选项 A）中，例如双向链表就具有两个指针，也属于线性结构，所以答案选A）。 【知识模块】 数据结构与算法 33 【正确答案】 C 【试题解析】 栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为E、 D、 C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为 E、D、 C，答案选 C。 【知识模块】 数据结构与算法 34 【正确答案】 B 【试题解析】 该二叉树
28、的中序序列为 DCBAEFG，后序序列为 DCBGFEA，可知 A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上；并且结点 B、 C、 D在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为 4，答案选 B。 【知识模块】 数据结构与算法 35 【正确答案】 A 36 【正确答案】 A 【试题解析】 结构化程序设计的思想包括：自顶向下、逐步求精、模块化、限制使用 goto语句，所以选择 A。 【知识模块】 程序设计基础
29、 37 【正确答案】 A 【试题解析】 对象有如下一些基本特点：标识唯一性、分类性、多态性、封装性、模块独立性好。所以选择 A)。 【知识模块】 程序设计基础 38 【正确答案】 D 【试题解析】 继承是面向对象的方法的一个主要特征，是使用已有的类的定义作为基础建立新类的定义技术。广义的说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们，所以说继承是指类之间共享属性和操作的机制。 【知识模块】 程序设计基础 39 【正确答案】 B 【试题解析】 1966年 Boehm和 Jacopini证明了程序设计语言仅仅使用顺序、选择和重复三种基本控制结构就足以表达出各种其他形式结构的程序设计方法。 【知识模块】 程序设计基础 40 【正确答案】 B 【试题解析】 只有 B）选项 369可以用无符号整数来表示和存储。 A）选项 369有负号，选项 C） 0.369是小数都不能用无符号整数类存储。选项 D）是一个整数集合得用数组来存储。 【知识模块】 程序设计基础
