1、国家二级 C语言（数据结构与运算）机试模拟试卷 4及答案与解析 一、选择题 1 下列各序列中不是堆的是 （ A） (91,85,53,36,47,30,24,12) （ B） (91,85,53,47,36,30,24,12) （ C） (47,91,53,85,30,12,24,36) （ D） (91,85,53,47,30,12,24,36) 2 深度为 5的完全二叉树的结点数不可能是 （ A） 15 （ B） 16 （ C） 17 （ D） 18 3 有二叉树如下图所示： 则前序序列为 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABC
2、DEFGH 4 下列叙述中正确的是 （ A）循环队列是顺序存储结构 （ B）循环队列是链式存储结构 （ C）循环队列是非线性结构 （ D）循环队列的插入运算不会发生溢出现象 5 下列叙述中正确的是 （ A）所有数据结构必须有根结点 （ B）所有数据结构必须有终端结点（即叶子结点） （ C）只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构 （ D）没有根结点或没有叶子结点的数据结构一定是非线性结构 6 下列关于算法的 描述中错误的是 （ A）算法强调动态的执行过程，不同于静态的计算公式 （ B）算法必须能在有限个步骤之后终止 （ C）算法设计必须考虑算法的复杂度 （ D）算法的优劣取决
3、于运行算法程序的环境 7 设有二叉树如下图所示： 则中序序列为 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 8 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有 （ A）节省存储空间 （ B）插入与删除运算效率高 （ C）便于查找 （ D）排序时减少元素的比较次数 9 深度为 7的完全二叉树中共有 125个结点，则该完全二叉树中的叶子结点数为 （ A） 62 （ B） 63 （ C） 64 （ D） 65 10 下列叙述中正确的是 （ A）所谓有序表是指在顺序存储空间内连续存放的元素序列 （ B）有序表只能顺序存储
4、在连续的存储空间内 （ C）有序表可以用链接存储方式存储在不连续的存储空间内 （ D）任何存储方式的有序表均能采用二分法进行查找 11 设有二叉树如下图所示： 则后序序列为 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 12 下列叙述中正确的是 （ A）结点中具有两个指针域的链表一定是二叉链表 （ B）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 （ C）二叉树只能采用链式存储结构 （ D）循环链表是非线性结构 13 设某二叉树中共有 140个结点，其中有 40个度为 1的结点。则 （ A）该二叉树中有 51个叶
5、子结点 （ B）该二叉树中有 50个叶子结点 （ C）该二叉树中有 51个度为 2的结点 （ D）不可能有这样的二叉树 14 带链的栈与顺序存储的栈相比，其优点是 （ A）入栈与 退栈操作方便 （ B）可以省略栈底指针 （ C）入栈操作时不会受栈存储空间的限制而发生溢出 （ D）所占存储空间相同 15 某二叉树的前序序列为 ABCD，中序序列为 DCBA，则后序序列为 （ A） BADC （ B） DCBA （ C） CDAB （ D） ABCD 16 下列叙述中正确的是 （ A）算法的时间复杂度与运行算法时特定的输入有关 （ B）算法的时间复杂度与计算机的运行速度有关 （ C）算法的时间复杂
6、度与算法程序中的语句条数成正比 （ D）算法的时间复杂度与算法程序编制者的水平有关 17 下 列各排序法中，最坏情况下的时间复杂度最低的是 （ A）堆排序 （ B）快速排序 （ C）希尔排序 （ D）冒泡排序 18 设栈的存储空间为 S(1:50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后， top=50，则栈中的元素个数为 （ A） 1 （ B） 0 （ C） 50 （ D） 49 19 某二叉树共有 399个结点，其中有 199个度为 2的结点，则该二叉树中的叶子结点数为 （ A）不存在这样的二叉树 （ B） 200 （ C） 198 （ D） 199 20 下列叙述中
7、错误的是 （ A）对 于各种特定的输入，算法的时间复杂度是固定不变的 （ B）算法的时间复杂度与使用的计算机系统无关 （ C）算法的时间复杂度与使用的程序设计语言无关 （ D）算法的时间复杂度与实现算法过程中的具体细节无关 21 在长度为 n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为 （ A） (n+1)/2 （ B） n （ C） 3n/4 （ D） n/4 22 设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值 均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历
8、结果为有序序列的是 （ A）中序序列 （ B）前序序列 （ C）后序序列 （ D）前序序列或后序序列 23 循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后， front=rear=25，此后又插入一个元素，则循环队列中的元素个数为 （ A） 1，或 50且产生上溢错误 （ B） 51 （ C） 26 （ D） 2 24 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的 是 （ A）在顺序存储的线性表中寻找最大项 （ B）在顺序存储的线性表中进行顺序查找 （ C）在顺序存储的有序表中进行对分查找 （ D）在链
9、式存储的有序表中进行查找 25 在具有 2n个结点的完全二叉树中，叶子结点个数为 （ A） n （ B） n+1 （ C） n-1 （ D） n/2 26 下列叙述中正确的是 （ A）在栈中，栈顶指针的动态变化决定栈中元素的个数 （ B）在循环队列中，队尾指针的动态变化决定队列的长度 （ C）在循环链表中，头指针和链尾指针的动态变化决定链表的长度 （ D）在线性链表中，头 指针和链尾指针的动态变化决定链表的长度 27 循环队列的存储空间为 Q(1:40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后， front=rear=15，此后又退出一个元素，则循环队列中的元
10、素个数为 （ A） 39，或 0且产生下溢错误 （ B） 14 （ C） 40 （ D） 15 国家二级 C语言（数据结构与运算）机试模拟试卷 4答案与解析 一、选择题 1 【正确答案】 C 【试题解析】 堆可以看成一棵完全二叉树：任一根节点 =左右孩子（或者=），（大的叫大根堆，小的叫 小根堆）。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显 91是最大的根，而选项 C是 “左根右 ”的排序，那么 91的左边只有 47，其他都在右边，而右边无法按照此顺序排列，所以选项 C不是堆。 【知识模块】 数据结构与运
11、算 2 【正确答案】 A 【试题解析】 对于满二叉树，叶子结点的数目等于 2n-1， n为深度，这里就是 2的5-1=4次方，就是 16。所以选项 A为正确答案。 【知识模块】 数据结构与运算 3 【正确 答案】 A 【试题解析】 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故选项 A正确，选项 B为中序遍历，选项 C为后序遍历，选项 D不正确。 【知识模块】 数据结构与运算 4 【正确答案】 A 【试题解析】 循环队列属于队列的特例和栈同属于线性结构，所以选项 C不正确。在顺序队列中，由于数组空间不够而产生的溢出
12、叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是 由于队尾 rear的值和队头 front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项 A正确，选项 B不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生的真溢出，故选项 D不正确。 【知识模块】 数据结构与运算 5 【正确答案】 D 【试题解析】 只有一个空节点的结构也属数据结构，所以选项 A和
13、选项 B不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故选项 C不正确，选项 D正确。 【知识模块】 数据结构与运算 6 【正确答案】 D 【试题解析】 算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故选项 D错误。 【知识模块】 数据结构与运算 7 【正确答案】 B 【知识模块】 数据结构与运算 8 【正确 答案】 B 【试题解析】 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点是存储密度大（1），存储空间利用率高；缺点是插
14、入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点是插入或删除元素时很方便效率高，使用灵活。缺点是存储密度小（ 1），存储空间利用率低，故选项 B正确。 【知识模块】 数据结构与运算 9 【正确答案】 B 【试题解析】 对于满二叉 树，结点的数目等于 2n-1，叶子结点数目为 2n-1， n为深度，这里就是 2的 7次方 -1，就是 127个结点，叶子结点是 64个。然而题目中只有 125个结点，说明少了两个结点，那么就少了一个叶子结点，即 63个。 【知识模块】 数据结构与运算 10 【正确答案】 C 【试
15、题解析】 有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项 C正确。 【知识模块】 数据 结构与运算 11 【正确答案】 C 【试题解析】 后序遍历（ LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点，可知选项 C正确。 【知识模块】 数据结构与运算 12 【正确答案】 B 【试题解析】 结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故选项 A不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可
16、采用顺序存储结构和链式存储结构，故选项 C不正确；循环链表是在单链表中，将终端结点的指针域 NULL改为指向表头结点或开始结点的 线性结构，故选项 D不正确；当结点中两个指针分别指向前驱结点和后继结点时为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故选项 B正确。 【知识模块】 数据结构与运算 13 【正确答案】 D 【试题解析】 140个结点除去 40个度为 1的结点，说明有 100个度为 2的结点，而根据二叉树性质，这个数值无法得出一棵二叉树，故本题答案选 D。 【知识模块】 数据结构与运算 14 【正确答案】 C 【试题解析】 带链的栈与顺序存储的栈相比优点是不受连续存储空间
17、大小的限制，即不需考虑栈 满的问题，故选项 C正确。 【知识模块】 数据结构与运算 15 【正确答案】 B 【试题解析】 在二叉树前序遍历中 ABCD中 A是根节点，而在后序遍历中根结点位于最后，所以选项 B正确。 【知识模块】 数据结构与运算 16 【正确答案】 B 【试题解析】 算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项 A正确。 【知识模块】 数据结构与运算 17 【正确答案】 A 【试题解析】 堆排序法 ，最坏情况需要 O(nlog2n)次比较。相比以上几种 “除希尔排序法外 ”，堆排序法的时间复
18、杂度最小，故选项 A正确。 【知识模块】 数据结构与运算 18 【正确答案】 A 【试题解析】 栈的存储空间为 S(1:50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后， top=50，则栈中有 51-50=1个元素，因此选项 A正确。 【知识模块】 数据结构与运算 19 【正确答案】 B 【试题解析】 在二叉树中，设叶子结点个数为 n0，度为 2的结点个数为 n2，叶子结点的个数计算方法 n0=n2+1=199+1=200，所以选项 B正确。 【知识模块】 数据结构与运算 20 【正确答案】 A 【试题解析】 一般情况下，算法的基本操作重复执行的次数，是模块 n的某一个函
19、数 f(n)。因此，算法的时间复杂度记做 T(n)=O(f(n)）。随着模块 n的增大，算法执行的时间的增长率和 f(n)的增长率成正比，所以 f(n)越小，算法的时间复杂度越低，算法的效率越高。因此算法会随着输入数据的不同而有执行效率的不同，有时候会快点儿，有时候会慢点儿。因此选项 A正确。 【知识模块】 数据结构与运 算 21 【正确答案】 A 【试题解析】 在一个长度为 n的线性表中顺序查找值为 x的元素时，在等概率情况下查找成功时平均查找长度为 (n+1)/2，所以选项 A正确。 【知识模块】 数据结构与运算 22 【正确答案】 A 【试题解析】 中序遍历的次序是先遍历左子树，再遍历根
20、节点，最后遍历右子树。而左子树结点值根节点节点值 右子树节点值，是有序序列，因此选项 A正确。 【知识模块】 数据结构与运算 23 【正确答案】 A 【试题解析】 循环队列初始状态 front=rear=50，经过一系列入队和出队操作后，结束状态还是 front=rear=25，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0就是 50，即要么队空（ 0个元素），要么队满（ 50个元素）。这时进行入队操作，如果是队空（ 0个元素）的情况，此时元素个数为 1；如果是队满（ 50个元素）的情况，就会产生上溢错误。 【知识模块】 数据结构与运算 2
21、4 【正确答案】 A 【试题解析】 最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最 坏情况下的时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况更长。 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准。 在顺序存储的线性表中寻找最大项，其平均情况与最坏情况下的时间复杂度都是n/2。 【知识模块】 数据结构与运算 25 【
22、正确答案】 A 【试题解析】 在具有 2n个结点的完全二叉树中，叶子结点个数为： (2n+1)/2取整，其值等于 n。所以选项 A正确。 【知识模块】 数据结构与运算 26 【正确答案】 A 【试题解析】 栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶；表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。在栈中，栈顶指针动态反映了栈中元素的变化情况。所以选项 A正确。 【知识模块】 数据结构与运算 27 【正确答案 】 A 【试题解析】 循环队列初始状态 front=rear=40 ，经过一系列入队和出队操作后，结束状态还是 front=rear=15，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0就是 40，即要么队列为空（ 0个元素），要么队列为满队列（ 40个元素）。这时进行出队操作，如果是队列满（ 40个元素）的情况，此时队列中的元素个数为 39，如果是队列空（ 0个元素）的情况，此时就会产生下溢错误。因此选项 A正确。 【知识模块】 数据结构与运算
