1、国家二级 C语言（数据结构与运算）机试模拟试卷 3及答案与解析 一、选择题 1 下列排序方法中，最坏情况下时间复杂度最小的是 （ A）冒泡排序 （ B）快速排序 （ C）堆排序 （ D）直接插入排序 2 为了对有序表进行对分查找，则要求有序表 （ A）只能顺序存储 （ B）只能链式存储 （ C）可以顺序存储也可以链式存储 （ D）任何存储方式 3 设某二叉树的后序序列为 CBA，中序序列为 ABC，则该二叉树的前序序列为 （ A） BCA （ B） CBA （ C） ABC （ D） CAB 4 下列叙 述中正确的是 （ A）存储空间不连续的所有链表一定是非线性结构 （ B）结点中有多个指针域
2、的所有链表一定是非线性结构 （ C）能顺序存储的数据结构一定是线性结构 （ D）带链的栈与队列是线性结构 5 算法时间复杂度的度量方法是 （ A）算法程序的长度 （ B）执行算法所需要的基本运算次数 （ C）执行算法所需要的所有运算次数 （ D）执行算法所需要的时间 6 设循环队列为 Q(1:m)，初始状态为 front=rear=m。现经过一系列的入队与退队运算后， front=rear=1，则该循环队列中的元素个 数为 （ A） 1 （ B） 2 （ C） m-1 （ D） 0或 m 7 在最坏情况下 （ A）快速排序的时间复杂度比冒泡排序的时间复杂度要小 （ B）快速排序的时间复杂度比希
3、尔排序的时间复杂度要小 （ C）希尔排序的时间复杂度比直接插入排序的时间复杂度要小 （ D）快速排序的时间复杂度与希尔排序的时间复杂度是一样的 8 在深度为 7的满二叉树中，度为 2的结点个数为 （ A） 64 （ B） 63 （ C） 32 （ D） 31 9 设栈的顺序存储空间为 S(1:m)，初始状态为 top=m+1。现经过一系列入栈与退 栈运算后， top=20，则当前栈中的元素个数为 （ A） 30 （ B） 20 （ C） m-19 （ D） m-20 10 算法空间复杂度的度量方法是 （ A）算法程序的长度 （ B）算法所处理的数据量 （ C）执行算法所需要的工作单元 （ D）
4、执行算法所需要的存储空间 11 设循环队列为 Q(1:m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后， front=15， rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为 （ A） 4 （ B） 6 （ C） m-5 （ D） m-6 12 下列叙述中正确的是 （ A）循环队列属于队列的链式存储结构 （ B）双向链表是二叉树的链式存储结构 （ C）非线性结构只能采用链式存储结构 （ D）有的非线性结构也可以采用顺序存储结构 13 某二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为 （ A） n+1 （ B） n-1 （ C） 2
5、n （ D） n/2 14 下列叙述中错误的是 （ A）算法的时间复杂度与算法所处理数据的存储结构有直接关系 （ B）算法的空间复杂度与算法所处理数据的存储结构有直接关系 （ C）算法的时间复 杂度与空间复杂度有直接关系 （ D）算法的时间复杂度与空间复杂度没有必然的联系 15 设栈的顺序存储空间为 S(0:49)，栈底指针 bottom=49，栈顶指针 top=30（指向栈顶元素）。则栈中的元素个数为 （ A） 30 （ B） 29 （ C） 20 （ D） 19 16 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度（根结点在第 1层）为 （ A） 2 （
6、 B） 3 （ C） 4 （ D） 5 17 下列叙述中正确的是 （ A）存储空间连续的数据结构一定是线性结构 （ B）存 储空间不连续的数据结构一定是非线性结构 （ C）没有根结点的非空数据结构一定是线性结构 （ D）具有两个根结点的数据结构一定是非线性结构 18 下列叙述中正确的是 （ A）带链队列的存储空间可以不连续，但队头指针必须大于队尾指针 （ B）带链队列的存储空间可以不连续，但队头指针必须小于队尾指针 （ C）带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针 （ D）以上三项都错误 19 设循环队列为 Q(1:m)，其初始状态为 front=rear=m。经过一
7、系列入队与退队运算后， front=20， rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为 （ A） 5 （ B） 6 （ C） m-5 （ D） m-6 20 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为 （ A） EFGDCBA （ B） DCBEFGA （ C） BCDGFEA （ D） DCBGFEA 21 下列叙述中正确的是 （ A）在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构 （ B）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性 结构 （ C）在链表中，如果每个结点有
8、两个指针域，则该链表一定是线性结构 （ D）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构 22 下列叙述中错误的是 （ A）在带链队列中，队头指针和队尾指针都是在动态变化的 （ B）在带链栈中，栈顶指针和栈底指针都是在动态变化的 （ C）在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的 （ D）以上三项都错误 23 设数据元素的集合 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)
9、（ D） R=(1,3),(2,4),(3,5) 24 下列叙述中正确的是 （ A）链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 （ B）线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针 （ C）线性表的链式存储结构中，每个结点只能有一个指向后件的指针 （ D）线性表的链式存储结构中，叶子结点的指针只能是空 25 一个 栈的初始状态为空，现将元素 A、 B、 C、 D、 E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为 （ A） ABC （ B） CBA （ C） EDC （ D）
10、CDE 26 某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度（根结点在第 1层）为 （ A） 5 （ B） 4 （ C） 3 （ D） 2 27 下列叙述中正确的是 （ A）所谓算法就是计算方法 （ B）程序可以作为算法的一种描述方法 （ C）算法设计只需考虑得到 计算结果 （ D）算法设计可以忽略算法的运算时间 国家二级 C语言（数据结构与运算）机试模拟试卷 3答案与解析 一、选择题 1 【正确答案】 C 【试题解析】 根据上表可知选项 C正确。 【知识模块】 数据结构与运算 2 【正确答案】 A 【试题解析】 有序表的对分查找条件是有序表为顺序存储。 顺
11、序查找： 如果线性表为无序表（即表中元素的排序是无序的），则无论是顺序存储结构还是链式存储结构，都只能用顺序查找； 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。分块查找（ 又称索引顺序查找）：分块有序表结构分为两部分， 线性表本身采用顺序存储结构； 在建立一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。显然索引表关于数据域是有序的。 【知识模块】 数据结构与运算 3 【正确答案】 C 【试题解析】 二叉树的前序遍历顺序为首先访问根结点，再依次访
12、问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历 首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。本题根据后序，可以确定 A为根结点；根据 B在中序中的位置，可以确定 A没有左子树， BC为 A的右子树， C为 B的右子树。本题的具体二叉树如下： 因此，这棵二叉树的前序是 ABC，选项 C正确。 【知识模块】 数据结构与运算 4 【正确答案】 D 【试题解析】 计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结
13、构 。而数据在内存或磁盘中的存储，可以分为顺序存储和链式存储。数据的逻辑结构与存储结构之间没有对应的关系。所以选项 ABC都是错误的，栈和队列按照数据的逻辑划分都是线性结构。 【知识模块】 数据结构与运算 5 【正确答案】 B 【试题解析】 算法的时间复杂度：分析算法时，语句总执行次数 T(n)是关于问题规模 n的函数，进而分析 T(n)随 n的变化情况并确定 T(n)。算法的时间复杂度也就是算法的时间量度，记作 T(n)=O(f(n)。它表示问题输入规模 n的增大，算法执行时间的增长率和 f(n)的增长率相同，因此称作渐近时间复杂度，也称作时间复杂度。 f(n)是问题规模 n的某个函数。选项
14、 B正确。 【知识模块】 数据结构与运算 6 【正确答案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指 针 front指向排头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间，所有的元素为队列中的元素。在循环队列动态变化过程中，当循环队列满时有 front=rear，而当循环队列空时也有front=rear。即在循环队列中，当 front=rear时，不能确定是队列满、还是队列空。当 front=rear=，要么队列为空，队列中的元素个数为 0，要么队列为满，队列中元素个数为 m。选项 D正确。 【知识模
15、块】 数据结构与运算 7 【正确答案】 C 【试题解析】 按 平均时间将排序分为四类： 平方阶 (O(n2)排序：各类简单排序，例如直接插入、直接选择和冒泡排序； 线性对数阶 (O(nlog2n)排序：如快速排序、堆排序和归并排序； O(n1+)排序： 是介于 0和 1之间的常数。希尔排序便是一种； 线性阶 (O(n)排序：本程序中的基数排序，此外还有桶、箱排序。 【知识模块】 数据结构与运算 8 【正确答案】 B 【试题解析】 因为在任意的二叉树中，度为 0的结点（即叶子结点）总比度为 2的结点的个数多 1个，而度为 0的结点数 n0=2m-1（其中 m为二叉树的深 度）。本题的度为 0的结
16、点个数 n0=27-1=26=64。因此，度为 2的结点数 n2=n0-1=63。所以选项 B正确。 【知识模块】 数据结构与运算 9 【正确答案】 C 【试题解析】 根据题意，栈空间如下图所示。 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位。当压入第一个元素时， TOP指针指向m+1-1=m；当压入第二个元素时， TOP指针指向 m+1-2=m-1； ；以此类推，当压入第 N个元素时， TOP指针指向 m+1-N=20；则 N=m+1-20=m-19。因此选项C正确。 【知识模块】 数据结构与运算 10 【正确答案】 D 【试题解析】 算法空间复杂度是对一个算法在运行过程中
17、临时占用存储空间大小的度量，因此选项 D正确。 【知识模块】 数据结构与运算 11 【正确答案】 A 【试题解析】 初始状态为： front=rear=m， rear-front=0，此时队列为空。经过一系列入队与退队运算后， front=15， rear=20。队尾大于队头，则队尾 rear减队头 front等于 5个元素。此时队列中有 5个元素，而查找最大项至少要比较 n-1次，就是 4次。因此选项 A正确。 【知识模块】 数据结构与运算 12 【正确答案】 D 【试题解析】 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是
18、顺序存储方式。 【知识模块】 数据结构与运算 13 【正确答案】 B 【试题解析】 对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2的结点总数为 N2，则 N0=N2+1； N2=N0-1。所以如果二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为 n-1。因此选项 B正确。 【知识模块】 数据结构与运算 14 【正确答案】 C 【试题解析】 算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项 C错误。 【知识模块】 数据结构与运算 15 【正确答案】
19、C 【试题解析】 在操作系统中，栈是向下生长的，如下图如示： 所以当栈底指针 bottom=49，栈顶指针 top=30时，栈中的元素个数为：栈底 -栈顶 +1=49-30+1=20。因此选项 C正确。 【知识模块】 数据结构与运算 16 【正确答案】 C 【试题解析】 该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上；并且结点 B、 C、 D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个
20、结点的右子树上。所以得到的二叉树为： 所以这个二叉树的深度为 4。选项 C为正确答案。 【知识模块】 数据结构与运算 17 【正确答案】 D 【试题解析】 数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项 A、 B和 C都不能判定是否是线性结构。 【知识模块】 数据结构与运算 18 【正确答案】 C 【试题解析】 带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项 C正确。 【知识模块】
21、 数 据结构与运算 19 【正确答案】 C 【试题解析】 在循环队列中元素的个数为 “(rear-front+M)%M” ，式中 rear为队尾指针， front为队首指针， M为存储容量， %为取余符号。对于找最小值的最坏情况下的比较次数，为循环队列中元素值个数减一。所以对于这个题目来说初始时元素个数为 0；运算后，元素个数为 m-5，找最小值的最坏情况下的比较次数为m-5-1=m-6。 【知识模块】 数据结构与运算 20 【正确答案】 D 【试题解析】 该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F
22、、 G位于根结点的右子树上；并且结点 B、 C、 D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下： 根据该二叉树，可得出后序遍历序列为： DCBGFEA，选项 D正确。 【知识模块】 数据结构与运算 21 【正确答案】 B 【知识模块】 数据结构与运算 22 【正确答案】 B 【试题解析】 栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈顶，另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项 C的说法正确，
23、选项 B的说法是错误的。队列是允许在队列的头和尾都可以进行操作的线性表，所以在带链队列中，队头指针和队尾指针都是在动态变化的选项 A这一说法是正确的。 【知识模块】 数据结构与运算 23 【正确答案】 B 【试题解析】 把每个答案中的第一个元素集合取出来，例如 A:(1,2)，先写下来就是 12，然后看后面的 (3,4)，在 (1,2)中 找不到前驱和后继，只能和 (1,2)暂时先并列，然后是 (5,1)，这里我们已经写过 12了，那么 5在 1前面就是 512，但是 34要单排，所以 A就是两个根节点 3和 5，两个顺序是 512,34。同理选项 B是541,32；选项 C是： 123和 4
24、5；选项 D是 135,24所以选项 B正确。 【知识模块】 数据结构与运算 24 【正确答案】 A 【试题解析】 在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项 B、 C、 D说法错误。选项A中，例如双向链表就具有两个 指针，也属于线性结构，所以选项 A正确。 【知识模块】 数据结构与运算 25 【正确答案】 C 【试题解析】 栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为E、 D、 C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为 E、D、 C，所以选项 C正确。 【知识模块】 数据结构与运算 26 【正确答
25、案】 B 【试题解析】 该二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，可知 A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上； 并且结点 B、 C、 D在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为 4，所以选项 B正确。 【知识模块】 数据结构与运算 27 【正确答案】 B 【试题解析】 算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选项 A和选项 C不正确。程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪 代码、流程图来描述，故选项 B正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以选项 D错误。 【知识模块】 数据结构与运算
