1、国家二级 C语言机试（数据结构与算法）模拟试卷 9及答案与解析 一、选择题 1 下列叙述中错误的是 （ A）循环链表中有一个表头结点 （ B）循环链表的存储空间是连续的 （ C）循环链表实现了空表与非空表运算的统一 （ D）循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 2 度为 3的一棵树共有 30个结点，其中度为 3、 1的结点个数分别为 3、 4。则该树中的叶子结点数为 （ A） 14 （ B） 15 （ C） 16 （ D）不可能有这样的树 3 在长度为 97的顺序有序表中作二分查找，最多需要 的比较次数为 （ A） 7 （ B） 96 （ C） 48 （ D） 6 4
2、 下列结构中属于非线性结构的是 （ A）二叉链表 （ B）二维数组 （ C）循环队列 （ D）双向链表 5 从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是 （ A）循环链表 （ B）双向链表 （ C）单向链表 （ D）二叉链表 6 设二叉树的前序序列与中序序列均为 ABCDEFGH，则该二叉树的后序序列为 （ A） HGFEDCBA （ B） ABCDEFGH （ C） ABCDHGFE （ D） DCBAHGFE 7 设某棵树的度为 3，其中度为 3、 1、 0的结点个数分别为 3、 4、 15。则该树中总结点数为 （ A） 22 （ B） 30 （ C） 35 （
3、D）不可能有这样的树 8 下列叙述中正确的是 （ A）矩阵是非线性结构 （ B）数组是长度固定的线性表 （ C）对线性表只能作插入与删除运算 （ D）线性表中各元素的数据类型可以不同 9 在快速排序法中，每经过一次数据交换 (或移动 )后 （ A）能消除多个逆序 （ B）只能消除一个逆序 （ C）不会产生新的逆序 （ D）消除的逆序个数一定比新产生的逆序个数多 10 线性表的长度为 n。在最坏情况下，比较次数为 n 1的算法是 （ A）顺序查找 （ B）有序表的插入 （ C）寻找最大项 （ D）同时寻找最大项与最小项 11 设某棵树的度为 3，其中度为 2、 1、 0的结点个数分别为 3、 4
4、、 15。则该树中总结点数为 （ A） 22 （ B） 30 （ C） 35 （ D）不可能有这样的树 12 下列叙述中错误的是 （ A）向量是线性结构 （ B）非空线性结构中只有一个结点没有前件 （ C）非空线性结构中只有一个结点没有后件 （ D）只有一个根结点和一个叶子结点的结构必定是 线性结构 13 在希尔排序法中，每经过一次数据交换后 （ A）能消除多个逆序 （ B）只能消除一个逆序 （ C）不会产生新的逆序 （ D）消除的逆序个数一定比新产生的逆序个数多 14 设二叉树的后序序列与中序序列均为 ABCDEFGH，则该二叉树的前序序列为 （ A） HGFEDCBA （ B） ABCDE
5、FGH （ C） ABCDHGFE （ D） DCBAHGFE 15 下列叙述中正确的是 （ A）循环队列是队列的链式存储结构 （ B）能采用顺序存储的必定是线性结构 （ C）所有的线性结构都可以采用顺 序存储结构 （ D）具有两个以上指针的链表必定是非线性结构 16 下列叙述中正确的是 （ A）算法的复杂度是指算法所处理的数据量 （ B）算法的复杂度是指算法程序中指令的数量 （ C）算法的复杂度是指算法控制结构的复杂程度 （ D）算法的复杂度包括时间复杂度与空间复杂度 17 设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则按层次输出 (从上到下，同一层从左到右
6、 )的序列为 （ A） ABCDEFGHIJ （ B） DGHEBIJFCA （ C） JIHGFEDCBA （ D） GHIJDEFBCA 18 设循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。经过一系列正常的操作后， front一 1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为 （ A） 0 （ B） 1 （ C） 48 （ D） 49 19 设顺序表的长度为 40，对该表进行冒泡排序。在最坏情况下需要的比较次数为 （ A） 780 （ B） 820 （ C） 40 （ D） 41 20 设表的长度为 n。在下列算法中，最坏情况
7、下时间复杂度最高的是 （ A）堆排序 （ B）希尔排序 （ C）有序链表查找 （ D）循环链表中寻找最大项 21 设循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。经过一系列正常的操作后， front=rear-1。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为 （ A） 0 （ B） 1 （ C） 49 （ D） 50 22 设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为 （ A） DGHEBIJFCA （ B） JIHGFEDCBA （ C） GHIJDEFBCA （ D） ABCDEFGHIJ 23
8、 设顺序表的长度为 16，对该表进行简单插入排序。在最坏情况下需要的比较次数为 （ A） 15 （ B） 30 （ C） 60 （ D） 120 24 下列结构中为非线性结构的是 （ A）树 （ B）向量 （ C）二维表 （ D）矩阵 25 设表的长度为 n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是 （ A）堆排序 （ B）有序链表查找 （ C）希尔排序 （ D）循环链表中寻找最大项 26 设循环队列的存储空间为 Q(1： m)，初始状态为 front=rear=m。经过一系列正常 的操作后， front=1， rear=m。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较
9、次数为 （ A） m （ B） m一 1 （ C） m一 2 （ D） 1 27 设二叉树的后序序列为 DGHEBIJFCA，中序序列为 DBGEHACIFJ。则前序序列为 （ A） ABDEGHCFIJ （ B） JIHGFEDCBA （ C） GHIJDEFBCA （ D） ABCDEFGHIJ 国家二级 C语言机试（数据结构与算法）模拟试卷 9答案与解析 一、选择题 1 【正确答案】 B 【试题解析】 循环链表是另一种 形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，他不一定要是连续的存储空间，也可以是断开的空间。 【知识模
10、块】 数据结构与算法 2 【正确答案】 B 【试题解析】 根据题目可知本树中还有度为 2的结点。树的总结点 =(度 1*个数 +度 2*个数 )+1 ，这里我们设度为 2的结点数为 x，那么30=3*3+2*x+1*4+1=2*x+14，由此可计算出 x=8。树的叶子结点数等于总结点减去所有度不为 0的结点，也就是 30-3-8-4=15。 【知识模块】 数据结构与算法 3 【正确答案】 A 【试题解析】 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式： k=log2n。其中 n代表长度， k为比较次数。本题中
11、可以计算出 k=7。 【知识模块】 数据结构与算法 4 【正确答案】 B 【试题解析】 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串：常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树一等 )，图。循环队列、双向链表和二叉链表都是线性结构，而二维数组是非线性结构。 【知识模块】 数据结构与算法 5 【正确答案】 A 【试题解析】 循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，循环一圈就访问到了表中其他所有结点而不重复。 【知识模块】 数据结构与算法 6 【正确答案】 A 【试题解析】 前
12、序遍历 (DLR)是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根芹右；中序遍历 (LDR)是二叉树遍历的一种， 也叫做中根遍历、中序周游，可记做左根右；后序遍历 (LRD)是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。根据题中前序和中序序列均为ABCDEFGH，可画出二义树，该二叉树是一个子结点全部在右侧二义树，然后根据后序遍历方法，可得出后序遍历为 HGFEDCBA。 【知识模块】 数据结构与算法 7 【正确答案】 B 【试题解析】 本题采用画图法来求出结果。首先先画出包含 3个度为 3的结点；然后再添加 4个度为 1的结点，此时最大度为 0的结点数为 8。根
13、据题目中描述的度为 0的结点数有 15个，这时 要在书中添加度为 2的结点，直到度为 0的结点数位 15。画图结束后，不管是什么样的树，总结点数都是 30。 【知识模块】 数据结构与算法 8 【正确答案】 B 【试题解析】 所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标。 【知识模块】 数据结构与算法 9 【正确答案】 A 【试题解析】 通过一 趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，
14、整个排序过程可以递归进行，以此达到整个数据变成有序序列。 【知识模块】 数据结构与算法 10 【正确答案】 C 【试题解析】 寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为 n-1。 【知识模块】 数据结构与算法 11 【正确答案】 D 【试题解析】 本题采用画图法来求出结果。首先先画出包含 3个 度为 2的结点；然后再添加 4个度为 1的结点。根据题目中描述的度为 0的结点数有 15个，这时要在书中添加度为 3的结点，不管怎么添加都不能添加出 15个度为 0的结点，因此不可能有这样的树。 【知识模块】 数据结构与算法 12 【正确答案】 D 【
15、试题解析】 线性结构是 n个数据元素的有序 (次序 )集合。 集合中必存在唯一的一个 “第一个元素 ”； 集合中必存在唯一的一个 “最后的元素 ”； 除最后元素之外，其它数据元素均有唯一的 “后件 ”； 除第一元素之外，其它数据元素均有唯一的 “前件 ”。相对应于线性结构，非线性结 构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。向量符合线性结构特点。非线性结构也会存在只有一个根结点和叶子结点的情况。 【知识模块】 数据结构与算法 13 【正确答案】 A 【试题解析】 希尔排序法 (缩小增量法 )属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。插入排序能够消
16、除多个逆序，也会产生新的逆序。消除的逆序与新产生的逆序有多有少。 【知识模块】 数据结构与算法 14 【正确答案】 A 【试题解析】 后序遍历中，最后一个字母是根结点， 也就是 H是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树， H后面没有，因此该树没有右子树。同理，可判断出该树是第一个完全的左子树。由此可画出这个二叉树，然后根据二叉树可的前序序列为 HGFEDCBA。 【知识模块】 数据结构与算法 15 【正确答案】 C 【试题解析】 根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采
17、用链式存储结构。所有的线性结构都可以采用顺序存储结构。 【知识模块 】 数据结构与算法 16 【正确答案】 D 【试题解析】 算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 前序遍历中，第一个字母是根结点，也就是 A是根结点：在中序遍历中，根结点前面的是左子树、后面的是右子树。前序中， B在 A的后面，中序中在左子树中，可知 B为 A的左结点。中序中 D在 B的前面，前序中在 B的后面，可知 D为 B的左结点， GEH为 B的右子树。前序中顺序为 EGH，由此可知， E为 B的右结
18、点， G为 E的左结点、 H为 E的右结点。右子树中，前序中 C在最前，因为右子树根结点，也就是 A的右结点，根据前序中的子树 FIJ和中序中的 IFJ子树可知 F为 C的右结点， I为 F的左结点、 J为 F的右结点。由此可画出这个二叉树，然后根据二叉树，可知按层次输出 (从上到下，同一层从左到右 )的序列为： ABCDEFGHIJ。 【知识模块】 数据结构与算法 18 【正确答案】 C 【试题解析】 front指定队头位置，删除个元素就将 font顺时针移动一位：rear指尾指针，指向元素要插入的位置，插 入一个元素就将 rear顺时针移动一位：操作后，循环队列的队头指针 -1等于尾指针，
19、说明出队一位，那么总数就是49了。在该队列中寻找最大值元素，最多比较次数是总数 -1，因此是 49-1=48次。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 冒泡排序 (Bubble Sort)，是一种计算机科学领域的较简单的排序算法。冒泡排序算法的运作如下：比较相邻的元素。如果第一个比第二个大，就交换他们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该 会是最大的数；针对所有的元素重复以上的步骤，除了最后一个：持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。冒泡排序的最坏时间复杂度为 (n*(n1) 2=
20、780。 【知识模块】 数据结构与算法 20 【正确答案】 B 【试题解析】 希尔排序 (Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。排序方法最坏时间复杂度：直接插入为 O(n2)、简单选择为 O(n2)、起泡排序为 O(n2)、快速排序为 O(n2)、堆排序为O(nlog2n)、归并排序为 O(nlog2n)。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 front指定队头位置，删除一个元素就将 front顺时针移动一位：real指尾指针，指向元素要插入的位置，插入一个元素就将 rear顺时针移动一位；操作后，循
21、环队列的队头指针等于尾指针 -1，说明此时队列已经是空队列，那么就不用比较了。 【知识模块】 数据结构与算法 22 【正确答案】 A 【试题解析】 前序遍历中，第一个字母是根结点，也就是 A是根结点：在中序遍历中，根结 点前面的是左子树、后面的是右子树。前序中， B在 A的后面，中序中在左子树中，可知 B为 A的左结点。中序中 D在 B的前面，前序中在 B的后面，可知 D为 B的左结点， GEH为 B的右子树。前序中顺序为 EGH，由此可知， E为 B的右结点。 G为 E的左结点、 H为 E的右结点。右子树中，前序中 C在最前，因为右子树根结点，也就是 A的右结点，根据前序中的子树 FIJ和中
22、序中的 IFJ子树可知 F为 C的右结点， I为 F的左结点、 J为 F的右结点。由此可画出这个二叉树，然后根据二叉树可的后序序列为 DGHEBIJFCA。 【知识模块】 数据结构与算 法 23 【正确答案】 D 【试题解析】 插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。 最坏情况计算方法 (n*(n-1) 2=16*15 2=120。 【知识模块】 数据结构与算法 24 【正确答案】 A 【试题解析】 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组
23、，多维数组，广义表。树 (二叉树等 )，图。 【知识模块】 数 据结构与算法 25 【正确答案】 D 【试题解析】 在循环链表中寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为 n-1。 【知识模块】 数据结构与算法 26 【正确答案】 C 【试题解析】 经过一系列正常的操作后， front=1， rear=m，那么最坏情况下需要的比较次数为 rear-front-1=m-1-1=m-2。 【知识模块】 数据结构与算法 27 【正确答案】 A 【试题解析】 后序遍历中，最后一个字母是根结点， 也就是 A是根结点；在中序遍历中，根结点前面的是左子树、
24、后面的是右子树。后序中 C在 A前面、中序中 C在 A的后面，说明 C是 A的右结点；后序中 F在 C的前面、中序中在 C后面，且后序和中序中， I均在 F前面由此可确定， I为 F的左结点， F为 C的右结点。同 C理 J为 F的右结点。后续中 B为左子树的根结点，因此 B为 A的左结点，以此划分，在中序中 B前面的 D为左结点，后面的 GEH为右子树，后序中， E在最后，应为剩下 3个结点的根结点，也就是 B的右子树，再根据中序中的顺序，可得出 G为 E的左结点， H为 E的右结点。由此可画出这个二叉树，然后根 据二叉树可的前序序列为 ABDEGHCFIJ。 【知识模块】 数据结构与算法
