1、国家二级 C语言（数据结构与运算）机试模拟试卷 5及答案与解析 一、选择题 1 某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBADE，则前序遍历序列为 （ A） EDABC （ B） CBEDA （ C） CBADE （ D） EDCBA 2 下列叙述中正确的是 （ A）在循环队列中，队头指针和队尾指针的动态变化决定队列的长度 （ B）在循环队列中，队尾指针的动态变化决定队列的长度 （ C）在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度 （ D）在带链的栈中，栈顶指针的动态变化决定栈中元素 的个数 3 设栈的存储空间为 S(1:60)，初始状态为 top=61。现经过一
2、系列正常的入栈与退栈操作后， top=1，则栈中的元素个数为 （ A） 60 （ B） 59 （ C） 0 （ D） 1 4 设顺序表的长度为 n。下列排序方法中，最坏情况下比较次数小于 n(n-1)/2的是 （ A）堆排序 （ B）快速排序 （ C）简单插入排序 （ D）冒泡排序 5 在长度为 n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要 比较的次数大约为 （ A） (3 n)/4 （ B） n （ C） n/2 （ D） n/4 6 设一棵树的度为 3，其中度为 3， 2， 1的结点个数分别为
3、 4， 1， 3。则该棵树中的叶子结点数为 （ A） 10 （ B） 11 （ C） 12 （ D）不可能有这样的树 7 设栈的存储空间为 S(1:50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后， top=51，则栈中的元素个数为 （ A）不可能 （ B） 50 （ C） 0 （ D） 1 8 设顺序表的长度为 n。下列算法中，最坏情况下比较次数等于 n(n-1)/2的是 （ A）快速排序 （ B）堆排序 （ C）顺序查找 （ D）寻找最大项 9 设表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是 （ A）二分查找法 （ B）堆排序 （ C）快速排序 （ D）顺序
4、查找法 10 下列叙述中错误的是 （ A）循环链表是循环队列的存储结构 （ B）二叉链表是二叉树的存储结构 （ C）栈是线性结构 （ D）循环队列是队列的存储结构 11 设一棵树的度为 4，其中度为 4， 3， 2， 1的结点个数分别为 2， 3， 3， 0。则该棵树中的叶子结点数为 （ A） 16 （ B） 15 （ C） 17 （ D）不可能有这样的树 12 循环队列的存储空间为 Q(1:100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后， front=rear=99，则循环队列中的元素个数为 （ A） 0或 100 （ B） 1 （ C） 2 （ D）
5、99 13 设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是 （ A）寻找最大项 （ B）堆排序 （ C）快速排序 （ D）顺序查找法 14 设栈的顺序存储空间为 S(1:m)，初始状态为 top=m+1。现经过一系列正常 的入栈与退栈操作后， top=0，则栈中的元素个数为 （ A）不可能 （ B） m+1 （ C） 1 （ D） m 15 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出（同一层从左到右）的序列为 （ A） FEDCBA （ B） CBAFED （ C） DEFCBA （ D） ABCDEF 16 循环队列的存储空间为 Q(1:20
6、0)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后， front=rear=1，则循环队列中的元素个数为 （ A） 0或 200 （ B） 1 （ C） 2 （ D） 199 17 设栈的顺序存储空间为 S(1:m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后， top=m+1，则栈中的元素个数为 （ A）不可能 （ B） m+1 （ C） 0 （ D） m 18 下列排序法中，最坏情况下时间复杂度最小的是 （ A）堆排序 （ B）快速排序 （ C）希尔排序 （ D）冒泡排序 19 某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF，则按
7、层次输出（同一层从左到右）的序列为 （ A） ABCDEF （ B） BCDEFA （ C） FEDCBA （ D） DEFABC 20 下列叙述中正确的是 （ A）对数据进行压缩存储会降低算法的空间复杂度 （ B）算法的优化主要通过程序的编制技巧来实现 （ C）算法的复杂度与问题的规模无关 （ D）数值型算法只需考虑计算结果的可靠性 21 设数据结构 B=(D,R)，其中 D=a,b,c,d,e,f R=(a,b),(b,c),(c,d),(d,e),(e,f),(f,a) 该数据结构为 （ A）非线性结构 （ B）循环队列 （ C）循环链表 （ D）线性结构 22 下列排序法中，每经 过一
8、次元素的交换会产生新的逆序的是 （ A）快速排序 （ B）冒泡排序 （ C）简单插入排序 （ D）简单选择排序 23 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后， front=rear=10。该队列中的元素个数为 （ A） 1 （ B） 0 （ C） 1或 0 （ D）不确定 24 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH。该完全二叉树的前序序列为 （ A） ABDHECFG （ B） ABCDEFGH （ C） HDBEAFCG （ D） HDEBFGCA 25 下列叙述中正确的是 （ A）有的二叉树也能用顺序存储结构表
9、示 （ B）有两个指针域的链表就是二叉链表 （ C）多重链表一定是非线性结构 （ D）顺序存储结构一定是线性结构 26 下列各排序法中，最坏情况下时间复杂度最小的是 （ A）堆排序 （ B）快速排序 （ C）希尔排序 （ D）冒泡排序 27 某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后， front=10， rear=5。该队列中的元素个数为 （ A）不确定 （ B） 5 （ C） 4 （ D） 6 国家二级 C语言（数据结构与运算）机试模拟试卷 5答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 后序遍历次序是 “左右根 ”，中序遍历次序是
10、“左根右 ”。由定义可知： 后序遍历中最后一个就是树根结点，即 E结点； 在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 CBAD是根结点 E的左子树集合。问题就会转化为：求后序遍历是 CBAD，中序遍历是 CBAD的子树，方法同上。因为中序遍历中， D结点右边没有结点了，所以 D结点不包含右子树，否则就会被分为 2个子问题。以下是这道题的详细推理过 程：步骤 1：由 CBADE得出根结点为 E，由中序遍历可知 CBADE，右子树为空；步骤 2：由 CBAD得出左子树集合的根节点为 D，由中序可知 CBAD，右子树为空；步骤 3：同理，二叉树更新后如下图所示。 【知识模块】 数据结
11、构与运算 2 【正确答案】 A 【知识模块】 数据结构与运算 3 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。当压入第一个元素时， TOP指针指向 60+1-1 = 60；当压入第二个元素时， TOP指针指向 60+1-2 = 59； ；以此类推，当压入第 N个元素时，TOP指针指向 60+1-N = 1，则 N=60。所以选项 A正确。 【知识模块】 数据结构与运算 4 【正确答案】 A 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n/2遍的从前往后扫描和 n/2遍的从后往前扫描，需要比较次数为
12、n(n-1)/2。快速排序法的最坏情况比较次数也是 n(n-1)/2。简单插入排序，无论是否最坏都需要 n(n-1)/2比较。堆排序，无论是否最坏都需要比较 O(nlog2n)次。所 以选项 A正确。 【知识模块】 数据结构与运算 5 【正确答案】 A 【试题解析】 在长度为 n的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个， n次找到。那么平均长度为：(1+2+.+n)/n=(n(n+1)/2)/n=(n+1)/2 本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为 (1+n)/2+1)/2=(3 n)/4。所以选项 A正确。 【
13、知识模块】 数据结构与运算 6 【正确答案】 A 【试题解析】 因为任一棵树中 ,结点总数总分支数目 1，所以：n0+4+1+3=(n0*0 + 3*4 + 2*1 + 1*3)+1，计算结果 n0=10。其中， n0表示叶子结点。所以选项 A正确。 【知识模块】 数据结构与运算 7 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 0，此时入栈一个元素， top值减 1，即 0-1=-1，发生下溢错误，所以选项 A正确。 【知识模块】 数据结构与运算 8 【正确答案】 A 【试题解析】 假设线
14、性表的长度为 n，则在最坏情况下，快速排序法的最坏情况比较次数也是 n(n-1)/2；堆排序，无论是否最坏都是比较 O(nlog2n)次，所以选项A正确。 【知识模块】 数据结构与运算 9 【正确答案】 A 【试题解析】 二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x与线性表的中间项进行比较，若中间项的值等于 x，则说明查到；若小于中间项的值则在线性表的前半部分；以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进 行查找。在最坏情况下，二分查找需要比较 log2n次。所以选项 A正确。 【知识模块】 数据结构与运算 10 【正确答案】 A 【试
15、题解析】 循环队列属于逻辑结构，其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可分为：分散的链表和连续的线性表，与其逻辑结构实现功能无关。所以选项 A正确。 【知识模块】 数据结构与运算 11 【正确答案】 A 【试题解析】 因为任一棵树中 ,结点总数总分支数目 1，所以： n0+2+3+3+0=（ n0*0 + 4*2 + 3*3 + 2*3+1*0） +1。计算得出 n0=16。其中， n0表示叶子结点，所以选项 A正确。 【知识模块】 数据结构与运算 12 【正确答案】 A 【试题解析】 循环队列中，由于入队时尾指针 rear向前追赶头指针 front；出队时头指针 f
16、ront向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。因此，无法通过条件 front=rear来判别队列是 “空 ”还是 “满 ”。对于这个题目来说，经过一系列正常的入队与退队操作后， front=rear=99，此时，要么队列为空（元素个数为 0），要么队列为满（元素个数 为 100），因此选项 A正确。 【知识模块】 数据结构与运算 13 【正确答案】 A 【试题解析】 如果顺序表是线性存储的（不包括线性的链式表），那么元素要不就是从大到小，要不就是小到大的顺序，假设第一个数就是最大值，那么需要比较 1次， n-1应该是最坏情况下要比较的次数，所以选项 A正确。 【知识模块】
17、数据结构与运算 14 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 m+1，此时入 栈一个元素， top值减 1，即 m+1-1=m，依次类推，当栈满时， top的值等于 1，不会出现 top的值等于 0。所以选项 A正确。 【知识模块】 数据结构与运算 15 【正确答案】 A 【试题解析】 后序遍历次序：左右根；中序遍历次序：左根右。由定义可知： 后序遍历中最后一个是树的根结点，即 F结点； 在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 ABCDE是根结点 F的左子树集合。问
18、题就会转化为：求后序遍历是 ABCDE，中序遍历是 ABCDE的子树。方法同上，因为中序遍历中， E结点右边没有结点 了，所以 E结点不包含右子树，否则就会被分为 2个子问题。以下是这道题的详细推理过程：步骤 1：由 ABCDEF得出根结点为 F，由中序遍历可知 : ABCDEF，右子树为空；步骤 2：由 ABCDE得出左子树集合的根节点为 E，由中序可知： ABCDE，右子树为空；步骤 3：同理，二叉树更新后如下。 所以按层次输出 (同一层从左到右 )的序列为 FEDCBA。 【知识模块】 数据结构与运算 16 【正确答案】 A 【知识模块】 数据结构与运算 17 【正确答案】 A 【试题解
19、析】 栈是向上增长的，每 次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 0，此时入栈一个元素， top值减 1，即 0-1=-1，出现下溢错误，所以选项 A正确。 【知识模块】 数据结构与运算 18 【正确答案】 A 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n/2遍的从前往后扫描和 n/2遍的从后往前扫描，需要比较次数为 n(n-1)/2。快速排序法的最坏情况比较次数也是 n(n-1)/2。简单插入排序，无论是否最坏都需要 n(n-1)/2比较。堆排序，无论是否最 坏情况都是比较 O(nlog2n)次。所以选
20、项 A正确。 【知识模块】 数据结构与运算 19 【正确答案】 A 【试题解析】 前序遍历次序：根左右；中序遍历次序：左根右。由定义可以知道： 前序遍历中第一个就是树根结点，即 A结点； 在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 BCDEF是根结点 A的右子树集合。问题就会转化为：求前序遍历是 BCDEF，中序遍历是 BCDEF的子树，方法同上。详细推理过程：步骤 1：由 ABCDEF得出根结点为 A，由中序遍历可知：左子树为空， ABCDE F ；步 骤 2：由 BCDEF得出右子树集合的根节点为 B，由中序可知：左子树为空， BCDEF；步骤 3：同理，二叉树更新后如下。
21、 所以按层次输出 (同一层从左到右 )的序列为 ABCDEF，选项 A正确。 【知识模块】 数据结构与运算 20 【正确答案】 A 【知识模块】 数据结构与运算 21 【正确答案】 A 【试题解析】 该逻辑结构为非线性结构，在 R=(a,b),(b,c),(c,d),(d,e),(e,f),(f,a)中，各结点之间形成一个循环链。 【知识模块】 数据结构与运算 22 【正确答案】 A 【试题解析】 冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。故选项 A正确。 【知
22、识模块】 数据结构与运算 23 【正确答案】 A 【试题解析】 循环队列用数组 A0;m-1存放其元素值，已知其头尾指针分别是front和 rear，则当前队列的元素个数是 (rear-front+m)%m=1，所以选项 A正确。 【知识模块】 数据结构 与运算 24 【正确答案】 A 【试题解析】 完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH，可以得到其结构如下： 所以此完全二叉树的前序序列是 ABDHECFG，选项 A正确。 【知识模块】 数据结构与运算 25
23、 【正确答案】 A 【试题解析】 完全二叉树如果 “根 ”从 1开始编号，则第 i结点的左孩子编号为2i，右孩子为 2i+1，双亲编号为（ i/2）下取整，空间紧密 ，适合顺序存储结构。所以选项 A正确。 小提示：取整是指取不超过实数 x的最大整数，称为 x的整数部分。上取整就是对实数取大于当前实数的第一个整数；下取整就是对当前实数去掉小数取整。 【知识模块】 数据结构与运算 26 【正确答案】 A 【试题解析】 快速排序、冒泡排序最坏情况下时间复杂度是 O(n2)；希尔排序最坏情况下时间复杂度是 O(n1.2) 。堆排序最坏情况下时间复杂度是 O(nlog2n)，所以选项 A正确。 【知识模块】 数据结构与运算 27 【正确答案】 A 【试题解析】 循环 队列用数组 A0:m-1存放其元素值，已知其头尾指针分别是front和 rear，则当前队列的元素个数是 (rear-front+m)%m=(5-10+m)%m=(m-5)%m。因为本题中的 m值不确定，所以 (m-5)%m的值不能确定。所以选项 A正确。 【知识模块】 数据结构与运算
