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