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