1、国家二级 C语言（数据结构与运算）机试模拟试卷 6及答案与解析 一、选择题 1 某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出（同一层从左到右）的序列为 （ A） ABCDEFGH （ B） HFDBGECA （ C） HGFEDCBA （ D） ACEGBDFH 2 某带链栈初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=10， bottom=20。该栈中的元素个数为 （ A）不确定 （ B） 10 （ C） 1 （ D） 0 3 设表的 长度为 15。则在最坏情况下，快速排序所需要的比较次数为 （ A） 10
2、5 （ B） 55 （ C） 15 （ D） 75 4 设循环队列的存储空间为 Q(1:100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为 （ A）不确定 （ B） 49 （ C） 51 （ D） 50 5 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH。该完全二叉树的中序序列为 （ A） HDBEAFCG （ B） HDEBFGCA （ C） ABDHECFG （ D） ABCDEFGH 6 下列叙述中正确的是 （ A）解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的 （ B）解决一个问题可以有不同的算法，但它们的时间复
3、杂度必定是相同的 （ C）解决一个问题的算法是唯一的 （ D）算法的时间复杂度与计算机系统有关 7 设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是 （ A）有序表的二分查找 （ B）顺序查找 （ C）寻找最大项 （ D）寻找最小项 8 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=bottom=20。该栈中的元素个数为 （ A） 1 （ B） 0 （ C） 20 （ D）不确定 9 某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树的后序序列为 （ A） HFDBGECA （ B） ABCDEFG
4、H （ C） HGFEDCBA （ D） ACEGBDFH 10 下列叙述中错误的是 （ A）算法的时间复杂度与问题规模无关 （ B）算法的时间复杂度与计算机系统无关 （ C）算法的时间复杂度与空间复杂度没有必然的联系 （ D）算法的空间复杂度与算法运行输出结果的数据量无关 11 设 表的长度为 20。则在最坏情况下，冒泡排序的比较次数为 （ A） 90 （ B） 20 （ C） 19 （ D） 190 12 在带链栈中，经过一系列正常的操作后，如果 top=bottom，则栈中的元素个数为 （ A） 1 （ B） 0 （ C） 0或 1 （ D）栈满 13 设一棵树的度为 3，共有 27个结
5、点，其中度为 3， 2， 0的结点数分别为 4， 1，10。该树中度为 1的结点数为 （ A） 11 （ B） 12 （ C） 13 （ D）不可能有这样的树 14 设数据结构 B=(D,R)，其中 D=a,b,c,d,e,f R=(f,a),(d,b),(e,d),(c,e),(a,c) 该数据结构为 （ A）线性结构 （ B）循环队列 （ C）循环链表 （ D）非线性结构 15 下列叙述中错误的是 （ A）循环队列空的条件是队头指针与队尾指针相同 （ B）若二叉树没有叶子结点，则为空二叉树 （ C）带链栈的栈底指针是随栈的操作而动态变化的 （ D）若带链队列中只有一个元素，则队头指针与队尾
6、指针必定相同 16 带链栈空的条件是 （ A） top=bottom=NULL （ B） top=-1且 bottom=NULL （ C） top=NULL且 bottom-1 （ D） top=bottom=-1 17 设一棵度为 3的树，其中度为 2， 1， 0的结点数分别为 3， 1， 6。该树中度为 3的结点数为 （ A） 1 （ B） 2 （ C） 3 （ D）不可能有这样的树 18 下列数据结构中，不能采用顺序存储结构的是 （ A）栈 （ B）堆 （ C）队列 （ D）非完全二叉树 19 设二叉树共有 375个结点，其中度为 2的结点有 187个。则度为 1的结点个数是 （ A）
7、0 （ B） 1 （ C） 188 （ D）不可能有这样的二叉树 20 在带链队列中，经过一系列正常的操作后，如果 front=rear，则队列中的元素个数为 （ A） 0或 1 （ B） 0 （ C） 1 （ D）队列满 21 设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。该树中度为 3的结点数为 （ A） 1 （ B） 2 （ C） 3 （ D）不可能有这样的树 22 设二叉树共有 500个结点，其中叶子结点有 250个。则度为 2的结点个数是 （ A） 0 （ B） 1 （ C） 249 （ D）不可能有这样的二叉树 23 下列叙述中正确的是 （ A）带链栈的栈底指针是
8、固定的 （ B）带链栈的栈底指针是随栈的操作而动态变化的 （ C）若带链队列的队头指针与队尾指针相同，则队列为空 （ D）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素 24 带链队列空的条件是 （ A） front=rear=NULL （ B） front=rear=-1 （ C） front=NULL且 rear=-1 （ D） front=-1且 rear=NULL 25 设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 6。该树中度为 3的结点数为 （ A） 1 （ B） 2 （ C） 3 （ D）不 可能有这样的树 26 下列叙述中正确的是 （ A）循环队列是线
9、性结构 （ B）循环队列是线性逻辑结构 （ C）循环队列是链式存储结构 （ D）循环队列是非线性存储结构 27 设某棵树的度为 3，其中度为 3、 2、 1的结点个数分别为 3、 0、 4。则该树中的叶子结点数为 （ A） 7 （ B） 8 （ C） 6 （ D）不可能有这样的树 28 设有一个栈与一个队列的初始状态均为空。现有一个序列 A,B,C,D,E,F,G,H。先分别将序列中的前 4个元素依次入栈，后 4个元素依次入队；然后分别将栈中的元素依次退栈，再 将队列中的元素依次退队。最后得到的序列为 （ A） D,C,B,A,E,F,G,H （ B） D,C,B,A,H,G,F,E （ C）
10、 A,B,C,D,E,F,G,H （ D） A,B,C,D,H,G,F,E 国家二级 C语言（数据结构与运算）机试模拟试卷 6答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列 HFDBACEG，可以得到， HFDB为 A的左子树， CEG为A的右子树。同理依次对左子树 HFDB和右子树 CEG进行 同样的推理，得到这个二叉树的结构如下： 该二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH，所以选项 A正确。 【知识模块】 数据结构与运算 2 【正确答案】 A 【试题解析】 对于链栈而言，
11、使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当 top=10， bottom=20时，不能确定栈中的元素个数，所以选项 A正确。 【知识模块】 数据结构与运算 3 【正确答案】 A 【试题解析】 假设线性表的长度为 n，在最坏情况下，快速排序法的比较次数是n(n-1)/2。题 中 n=15，所以 15*14/2=105。所以选项 A正确。 【知识模块】 数据结构与运算 4 【正确答案】 A 【试题解析】 循环队列用数组 Q1:100存放其元素值，已知其头尾指针分别是front和 rear，则当前队列的元素个数是 (rear-front+100)%100，题目中首指针rear的值未知
12、，所以循环队列中的元素个数不能确定。所以选项 A正确。 【知识模块】 数据结构与运算 5 【正确答案】 A 【试题解析】 完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值； 在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH。可以得到其结构如下： 所以此完全二叉树的中序序列是 HDBEAFCG。所以选项 A正确。 【知识模块】 数据结构与运算 6 【正确答案】 A 【试题解析】 算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有 10种左右算法，它们复杂度显然是不一样
13、的。所以选项 A正确。 【知识模块】 数据结构与运算 7 【正确答案】 A 【试 题解析】 有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x与线性表的中间项进行比较，若中间项的值等于 x，则说明查到；若小于中间项的值则在线性表的前半部分以相同的方法进行查找；若大于中间项的值则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较 log2n次。顺序查找、寻找最大项、寻找最小项，在最坏情况下，比较次数都是 n次。所以选项 A正确。 【知识模块】 数据结构与运算 8 【正确答案】 D 【试题解析】 对于链栈而言，使用了链表来实现栈，链表中的元素存储在
14、不连续的地址。所以当 top=bottom=20时，不能确定栈中的元素个数。所以选项 D正确。 【知识模块】 数据结构与运算 9 【正确答案】 A 【试题解析】 由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列 HFDBACEG，可以得到， HFDB为 A的左子树， CEG为A的右子树。同理依次对左子树 HFDB和右子树 CEG进行同样的推理，得到这个二叉树的结构如下： 对该二叉树的后序遍历序列为 HFDBGECA，所以选项 A正确。 【知识模块】 数据结构与运算 10 【正确答案】 A 【试题解析】 一般情况下，算法中基本操作重复执行的次数是问题规模 n
15、的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n趋近于无穷大时， T(n)/f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作T(n)=O(f(n)，称 O(f(n)为算法的渐进时间复杂度，简称时间复杂度。所以选项 A正确。 【知识模块】 数据结构与运算 11 【正确答案】 D 【试题解析】 假设 线性表的长度为 n，则在最坏情况下，冒泡排序的比较次数为n(n-1)/2。本题中， n=20，所以 20*19/2=190。所以选项 D正确。 【知识模块】 数据结构与运算 12 【正确答案】 C 【试题解析】 链栈就是没有附加头结点的、运算受限的单
16、链表。栈顶指针就是链表的头指针。如果栈底指针指向的存储单元中存有 1元素，则当 top=bottom时，栈中的元素个数为 1；如果栈底指针指向的存储单元中没有存元素，则当top=bottom时，栈中的元素个数为 0。所以选项 C正确。 【知识模块】 数据结构 与运算 13 【正确答案】 B 【试题解析】 因为任一棵树中，结点总数总分支数目 1，所以：27=(0*10+n1*1+2*1+3*4)+1。运算结果 n1=12。其中， n1表示叶子结点，所以选项 B正确。 【知识模块】 数据结构与运算 14 【正确答案】 A 【试题解析】 由结点之间的关系 R=(f,a),(d,b),(e,d),(c
17、,e),(a,c)可以得到，该数据结构为： “f-a-c-e-d-b”。由此可知结点 f没有前驱，结点 b没有后继结点，并且其它的结点只有一个前驱结点和一 个后继结点，所以该数据结构为线性结构。所以应选 A选项。 【知识模块】 数据结构与运算 15 【正确答案】 A 【试题解析】 初始化建空队时，令 front=rear=0，当队空时： front=rear；当队满时： front=rear亦成立。因此，只凭等式 front=rear无法判断队空还是队满。有两种方法处理上述问题： 另设一个标志位以区别队列是空还是满； 少用一个元素空间，约定以 “队列头指针 front在队尾指针 rear的下一
18、个位置上 ”作为队列“满 ”状态的标志。即：队空时： front=rear；队满时： (rear+1)%maxsize=front。所以选项 A正确。 【知识模块】 数据结构与运算 16 【正确答案】 A 【试题解析】 栈的链式存储结构称为链栈。在链栈中，只会出现栈空和非空两种状态。当栈为空时，有 top=bottom=NULL；当栈非空时， top指向链表的第一个结点（栈顶）。所以选项 A正确。 【知识模块】 数据结构与运算 17 【正确答案】 A 【试题解析】 因为任一棵树中，结点总数总分支数目 1，所以：6+1+3+n3=(0*6+1*1+2*3+3*n3)+1。运算结果 n3=1。其中
19、， n3表示度为 3的结点数，所以选项 A正确。 【知识模块】 数据结构与运算 18 【正确答案】 D 【试题解析】 堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。 【知识模块】 数据结构与运算 19 【正确答案】 A 【试题解析】 二叉树的每个结点至多只有二棵子树（不存 在度大于 2的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i层至多有 2i-1个结点；深度为 k的二叉树至多有 2k-1个结点；对
20、任何一棵二叉树 T，如果其终端结点数为n0，度为 2的结点数为 n2，则 n0=n2+1。本题中，度为 2的结点有 187个，叶子结点应该有 187+1=188个，度为 1的结点个数 =375-187-188=0。 【知识模块】 数据结构与运算 20 【正确答案】 A 【试题解析】 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（ front）进行删除操作，而在表的后端（ rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的链式存储也称为链队列。为了便于操作，可给链队列添加 1个头结点，并令头指针指向头结点。队列为空
21、的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空（ 0）或 1时， front=rear。 【知识模块】 数据结构与运算 21 【正确答案】 B 【试题解析】 树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，那么树中最少有一个结点的度为 3。而树中没有度为 2的 结点，叶子结点数为 5，度为 1的结点下面只有一个叶子结点。因此，该树中含 2个度为 3的结点满足题目要求。 【知识模块】 数据结构与运算 22 【正确答案】 C 【试题解析】 二叉树的每个结点至多只有二棵子树（不存在度大于 2的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i层至多有 2i
22、-1个结点；深度为 k的二叉树至多有 2k-1个结点；对任何一棵二叉树 T，如果其终端结点数为n0，度为 2的结点数为 n2，则 n0=n2+1。 本题中，叶子结点有 250个，度为 2的结点数为 n2=n0-1=250-1=249。 【知识模块】 数据结构与运算 23 【正确答案】 B 【试题解析】 栈（ stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使
23、其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为 0也可 能为 1。 【知识模块】 数据结构与运算 24 【正确答案】 A 【试题解析】 带链队列空的条件有两个：一个是 front=rear，一个是它们都等于空。 【知识模块】 数据结构与运算 25 【正确答案】 D 【试题解析】 树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，也就是最少有一个度为 3的结点。要求没有度为 2的结点，且叶子结点为6，如果要有度为 3的结点，那么最多只有 5个叶子结点，而画不出 6个叶子结点。因此这样的树是没有的。 【知识模
24、块】 数据结构与运算 26 【正确答案】 A 【试题解析】 为充分利用向量空间，克服 “假溢出 ”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（ Circular Queue）。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。 【知识模块】 数据结构与运算 27 【正确答案】 A 【试题解析】 树的度是指一棵树中，最大的结点的度称为 “树的度 ”。 根据题目可知本树中没有度为 2的结点。树的总结点 =（度 1*个数 +度 2*
25、个数 ） +1，这里我们设总结点数为 n，那么 n=3*3+2*0+1*4+1=14。树的叶子结点数等于总结点减去所有度不为 0的结点，也就是 14-3-4=7。 【知识模块】 数据结构与运算 28 【正确答案】 A 【试题解析】 栈（ stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是 D,C,B,A。 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端 （ front）进行删除操作，而在表的后端（ rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。因此，队的出队顺序是，先入先出，所以顺序是 E,F,G,H。最后的顺序是：D,C,B,A,E,F,G,H。 【知识模块】 数据结构与运算
