1、国家二级 C语言（数据结构与运算）机试模拟试卷 2及答案与解析 一、选择题 1 下列各组的排序方法中，最坏情况下比较次数相同的是 （ A）冒泡排序与快速排序 （ B）简单插入排序与希尔排序 （ C）堆排序与希尔排序 （ D）快速排序与希尔排序 2 下列叙述中正确的是 （ A）循环队列是队列的一种链式存储结构 （ B）循环队列是队列的一种顺序存储结构 （ C）循环队列是非线性结构 （ D）循环队列是一种逻辑结构 3 下列关于线性链表的叙述中，正确的是 （ A）各数据结点的存储空间可以不连续，但它们的 存储顺序与逻辑顺序必须一致 （ B）各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必
2、须连续 （ C）进行插入与删除时，不需要移动表中的元素 （ D）以上都不正确 4 一棵二叉树共有 25个结点，其中 5个是叶子结点，则度为 1的结点数为 （ A） 16 （ B） 10 （ C） 6 （ D） 4 5 设循环队列存储空间为 Q(1:50)。初始状态为 front=rear=50。经过一系列入队和退队操作后， front=14， rear=19，则该循环队列中的元素个数为 （ A） 46 （ B） 45 （ C） 6 （ D） 5 6 下列链表中，其逻辑结构属于非线性结构的是 （ A）二叉链表 （ B）循环链表 （ C）双向链表 （ D）带链的栈 7 设循环队列的存储空间为 Q(
3、1:35)，初始状态为 front=rear=35。现经过一系列入队与退队运算后， front=15， rear=15，则循环队列中的元素个数为 （ A） 15 （ B） 16 （ C） 20 （ D） 0或 35 8 下列关于栈的叙述中，正确的是 （ A）栈底元素一定是最后入栈的元素 （ B）栈顶元素一定是最先入栈的元素 （ C）栈操作遵循先进后出的原 则 （ D）以上三种说法都不对 9 设二叉树共有 150个结点，其中度为 1的结点有 10个，则该二叉树中的叶子结点数为 （ A） 71 （ B） 70 （ C） 69 （ D）不可能有这样的二叉树 10 下列叙述中正确的是 （ A）程序执行
4、的效率与数据的存储结构密切相关 （ B）程序执行的效率只取决于程序的控制结构 （ C）程序执行的效率只取决于所处理的数据量 （ D）以上都不正确 11 下列与队列结构有关联的是 （ A）函数的递归调用 （ B）数组元素的引用 （ C）多重循环的执行 （ D）先到先服务的 作业调度 12 一个栈的初始状态为空。现将元素 1,2,3,A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是 （ A） 1,2,3,A,B,C （ B） C,B,A,1,2,3 （ C） C,B,A,3,2,1 （ D） 1,2,3,C,B,A 13 下列叙述中正确的是 （ A）一个算法的空间复杂度大，则其时间复杂度也必
5、定大 （ B）一个算法的空间复杂度大，则其时间复杂度必定小 （ C）一个算法的时间复杂度大，则其空间复杂度必定小 （ D）算法的时间复杂度与空间复杂度没有直接关系 14 下列叙述中正 确的是 （ A）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 （ B）循环队列中的元素个数随队头指针的变化而动态变化 （ C）循环队列中的元素个数随队尾指针的变化而动态变化 （ D）循环队列中的元素个数不会变化 15 一棵二叉树中共有 80个叶子结点与 70个度为 1的结点，则该二叉树中的总结点数为 （ A） 219 （ B） 229 （ C） 230 （ D） 231 16 对长度为 10的线性表进
6、行冒泡排序，最坏情况下需要比较的次数为 （ A） 9 （ B） 10 （ C） 45 （ D） 90 17 下列叙述中正确的是 （ A）算法的效率只与问题的规模有关，而与数据的存储结构无关 （ B）算法的时间复杂度是指执行算法所需要的计算工作量 （ C）数据的逻辑结构与存储结构是一一对应的 （ D）算法的时间复杂度与空间复杂度一定相关 18 下列叙述中正确的是 （ A）线性表链式存储结构的存储空间一般要少于顺序存储结构 （ B）线性表链式存储结构与顺序存储结构的存储空间都是连续的 （ C）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的 （ D）以上都不正确 19 某二叉树共有 12
7、个结点，其中叶 子结点只有 1个。则该二叉树的深度为（根结点在第 1层） （ A） 3 （ B） 6 （ C） 8 （ D） 12 20 对长度为 n的线性表作快速排序，在最坏情况下，比较次数为 （ A） n （ B） n-1 （ C） n(n-1) （ D） n(n-1)/2 21 下列叙述中正确的是 （ A）有且只有一个根结点的数据结构一定是线性结构 （ B）每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构 （ C）有且只有一个根结点的数据结构一定是非线性结构 （ D）有且只有一个根结点的数据结构可能是线性结构，也可 能是非线性结构 22 下列叙述中错误的是 （ A）在双向
8、链表中，可以从任何一个结点开始直接遍历到所有结点 （ B）在循环链表中，可以从任何一个结点开始直接遍历到所有结点 （ C）在线性单链表中，可以从任何一个结点开始直接遍历到所有结点 （ D）在二叉链表中，可以从根结点开始遍历到所有结点 23 某二叉树共有 13个结点，其中有 4个度为 1的结点，则叶子结点数为 （ A） 5 （ B） 4 （ C） 3 （ D） 2 24 设栈的顺序存储空间为 S(1:50)，初始状态为 top=0。现经过一系列入栈与退栈运算后 ， top=20，则当前栈中的元素个数为 （ A） 30 （ B） 29 （ C） 20 （ D） 19 25 下列叙述中正确的是 （
9、A）栈与队列都只能顺序存储 （ B）循环队列是队列的顺序存储结构 （ C）循环链表是循环队列的链式存储结构 （ D）以上三项均错误 26 设某二叉树的前序序列为 ABC，中序序列为 CBA，则该二叉树的后序序列为 （ A） BCA （ B） CBA （ C） ABC （ D） CAB 国家二级 C语言（数据结构与运算）机试模拟试卷 2答案与解析 一、选择题 1 【正确答案】 A 【 试题解析】 最坏情况下冒泡排序需要比较 n(n-1)/2次，即序列逆序的情况。简单插入排序，无论是否最坏情况，都需要 n(n-1)/2次。直接插入排序，最坏情况需要比较次 n(n-1)/2次。堆排序，无论是否最坏都
10、要比较 O(nlog2n)次。快速排序，最坏情况退化为冒泡排序，需要比较 n(n-1)/2次。在最坏情况下，希尔排序所需要的比较次数为 O(n1.5)。 【知识模块】 数据结构与运算 2 【正确答案】 B 【试题解析】 本题主要考查循环队列的概念，循环队列作为队列的一种也应该是线性结构。队列是 一种逻辑结构，而循环队列是一种顺序存储结构的队列。 【知识模块】 数据结构与运算 3 【正确答案】 C 【试题解析】 线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
11、 【知识模块】 数据结构与运算 4 【正确答案】 A 【试题解析】 根据二叉树的性质，在任意二叉树中，度为 0的结点（即叶子结点）总是比度为 2的结点多一个，故此度为 1的结点个数 =总结点数 -叶子节点数 -度为 2的节点数 =25-5-4=16。 【知识模块】 数据结构与运算 5 【正确答案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指针 front指向排头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间所有的元素为队列中的元素。本题中的元素个数是从队列的索引 15位置开始到索引 19位置，共有 5元
12、素。 【知识模块】 数据结构与运算 6 【正确答案】 A 【试题解析】 二叉链表作为树 的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。 【知识模块】 数据结构与运算 7 【正确答案】 D 【试题解析】 循环队列的队头指针和尾指针都等于 15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达 15，此时元素个数为 0；第二种情况是队头指针第一次到达 15，而尾指针第二次到达 15，此时元素个数为 35。 【知识模块】 数据结构与运算 8 【正确答案】 C 【试题解析】 栈 是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进先
13、出 ”的规则操作元素。 【知识模块】 数据结构与运算 9 【正确答案】 D 【试题解析】 根据二叉树的性质 3，在任意一颗二叉树中，度为 0的结点（即叶子结点）总是比度为 2的结点多一个。即有 n0=n2+1。对于这个题来说，总结点数150=n0+n1+n2=n2+1+10+n2=2n2+11，所以 2n2=139，度为 2个结点个数不能确定。 【知识模块】 数据结构与运算 10 【正确答案】 A 【试题解析】 影响程序执行效率的因 素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别。其中，链式存储结构的效率要高一些。
14、【知识模块】 数据结构与运算 11 【正确答案】 D 【试题解析】 队列中最先插入的元素将最先被删除，最后插入的元素将最后被删除。 【知识模块】 数据结构与运算 12 【正确答案】 C 【试题解析】 栈是按照 “先进后出 ”或 “后进先出 ”的原则组织数据的。所以出栈顺序是 CBA321。 【知识模块】 数据结构与运算 13 【正确答案】 D 【试题解析】 算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中 n是问题的规模；算法的空间
15、复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。 【知识模块】 数据结构与运算 14 【正确答案】 A 【试题解析】 所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针 rear指向队列中的队尾元素，用队头指针 front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针 front指向的后一个位置与队尾指针 rear指向位置之间的元素数量。 【知识
16、模块】 数据结构与运算 15 【正确答案】 B 【试题解析】 根据二叉树的性质，在任意二叉树中，度为 0的结点（即叶 子结点）总是比度为 2的结点多一个，故总结点数 =叶子节点数 +度为 2的节点数 +度为1的节点数 =80+79+70=229。 【知识模块】 数据结构与运算 16 【正确答案】 C 【试题解析】 线性表的长度为 n，最坏情况下冒泡排序需要比较的次数为 n(n-1)/2。 【知识模块】 数据结构与运算 17 【正确答案】 B 【试题解析】 算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；
17、算法的空间复杂 度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。 【知识模块】 数据结构与运算 18 【正确答案】 C 【试题解析】 线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将 存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用
18、于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。 【知识模块】 数据结构与运算 19 【正确答案】 D 【试题解析】 根据二叉树的性质，度为 0的结点（即叶子结点）总是比度为 2的结点多一个。题目中的二叉树的叶子结点为 1，因此度为 2的结点的数目为 0，故该二叉树为 12层，每层只有一个结点。 【知识模块】 数据结构与运算 20 【正确答案】 D 【试 题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n/2遍的从前往后的扫描和 n/2遍的从后往前的扫描，需要的比较次数为 n(n-1)/2。快速排序法也是一种互换类的排序方法
19、，但由于它比冒泡排序法的速度快，因此，称为快速排序法。 【知识模块】 数据结构与运算 21 【正确答案】 D 【试题解析】 根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分这两大类型：线性结构与非线性结构。如果一个非空的数据结构满足两个条件： 有且只有一个根结点； 每一个结点最多有一个前件， 也最多有一个后件。称该数据结构为线性结构，又称为线性表。对于这个题目来说，有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构。具有一个根结点的树就是一个非线性结构，选项 D正确。 【知识模块】 数据结构与运算 22 【正确答案】 C 【试题解析】 线性队列是一种线性单链表，
20、对线性队列的遍历只能从队列的头开始，从中间的结点开始不能够遍历到所有的结点。选项 C的描述是错误的。 【知识模块】 数据结构与运算 23 【正确答案】 A 【试题解析】 根据二叉树性质，在任意一颗二叉树 中，度为 0的结点（即叶子结点）总是比度为 2的结点多一个，即有 n0=n2+1。本题总结点数：13=n0+n1+n2=n2+1+4+n2=2n2+5， n2=4，所以叶子结点数等于 4+1=5，选项 A正确。 【知识模块】 数据结构与运算 24 【正确答案】 C 【试题解析】 栈是允许在栈顶进行插入和删除的线性表，不允许在栈底进行插入与删除。通常用指针 top来指示栈顶的位置，用指针 bot
21、tom指向栈底。对栈的操作有入栈和退栈两种。入栈运算：首先将栈顶指针进一（即 top加 1），然后将新元素插入到栈顶指针 指向的位置。退栈运算：首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针退一（即 top减 1）。因为初始状态为 top=0，经过入栈和退栈操作后栈中的元素个数就是 top指针指向的位置。选项C正确。 【知识模块】 数据结构与运算 25 【正确答案】 B 【试题解析】 栈和队列是按数据的逻辑结构划分是线性结构。数据在内存或磁盘上的存储分为顺序存储结构和链式存储结构。线性结构的数据可以按顺序存储结构存储，也可以按链式存储结构存储，而循环队列是队列的顺序存储
22、结构。选项B正确。 【知识模块】 数据结构与运算 26 【正确答案】 B 【试题解析】 二叉树的前序遍历的顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历的顺序为首先访问左结点，然后依次访问右结点和根结点。根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。对于本题根据前序，可以确定 A为根， A在中序中的位置，可以确定 CB为 A的左子树上的结点，没有右子树。确定 A之后，再 看中序第二个值为 B，查看 B在中序中的位置， C在 B左边，确定 C为 B的左子树。因此，后序是 CBA。 【知识模块】 数据结构与运算
