国家二级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）A.14B.15 √C.16D.不可能有这样的树解析：解析：根据题目可知本树中还有度为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。
4.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为（分数：2.00）A.7 √B.96C.48D.6解析：解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
最多比较次数的计算方式：k＝log 2 n。
其中n代表长度，k为比较次数。
本题中可以计算出k＝7。
5.下列结构中属于非线性结构的是（分数：2.00）A.二叉链表B.二维数组√C.循环队列D.双向链表解析：解析：线性结构是一个有序数据元素的集合。
常用的线性结构有：线性表，栈，队列，双队列，数组，串；常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
循环队列、双向链表和二叉链表都是线性结构，而二维数组是非线性结构。
6.从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是（分数：2.00）A.循环链表√B.双向链表C.单向链表D.二叉链表解析：解析：循环链表是另一种形式的链式存储结构。
它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，循环一圈就访问到了表中其它所有结点而不重复。
7.设二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为（分数：2.00）A.HGFEDCBA √B.ABCDEFGHC.ABCDHGFED.DCBAHGFE解析：解析：前序遍历(DLR)是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右；中序遍历(LDR)是二叉树遍历的一种，也叫做中根遍历、中序周游，可记做左根右；后序遍历(LRD)是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。
根据题中前序和中序序列均为ABCDEFGH，可画出二叉树，该二叉树是一个子结点全部在右侧二叉树，然后根据后序遍历方法，可得出后序遍历为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.下列叙述中正确的是（分数：2.00）A.矩阵是非线性结构B.数组是长度固定的线性表√C.对线性表只能作插入与删除运算D.线性表中各元素的数据类型可以不同解析：解析：所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分它们的变量的集合，这个名字称为数组名，编号称为下标。
10.在快速排序法中，每经过一次数据交换(或移动)后（分数：2.00）A.能消除多个逆序√B.X能消除一个逆序C.不会产生新的逆序D.消除的逆序个数一定比新产生的逆序个数多解析：解析：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
11.线性表的长度为n。
在最坏情况下，比较次数为n－1的算法是（分数：2.00）A.顺序查找B.有序表的插入C.寻找最大项√D.同时寻找最大项与最小项解析：解析：寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。
因此，比较次数为n．1。
12.设某棵树的度为3，其中度为2、1、0的结点个数分别为3、4、15。
则该树中总结点数为（分数：2.00）A.22B.30C.35D.不可能有这样的树√解析：解析：本题采用画图法来求出结果。
首先先画出包含3个度为2的结点；然后再添加4个度为1的结点。
根据题目中描述的度为0的结点数有15个，这时要在书中添加度为3的结点，不管怎么添加都不能添加出15个度为0的结点，因此不可能有这样的树。
13.下列叙述中错误的是（分数：2.00）A.向量是线性结构B.非空线性结构中只有一个结点没有前件C.非空线性结构中只有一个结点没有后件D.只有一个根结点和一个叶子结点的结构必定是线性结构√解析：解析：线性结构是n个数据元素的有序(次序)集合。
①集合中必存在唯一的一个“第一个元素”；②集合中必存在唯一的一个“最后的元素”；③除最后元素之外，其它数据元素均有唯一的“后件”；④除第一元素之外，其它数据元素均有唯一的“前件”。
相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。
向量符合线性结构特点。
非线性结构也会存在只有一个根结点和叶子结点的情况。
14.在希尔排序法中，每经过一次数据交换后（分数：2.00）A.能消除多个逆序√B.只能消除一个逆序C.不会产生新的逆序D.消除的逆序个数一定比新产生的逆序个数多解析：解析：希尔排序法(缩小增量法)属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。
插入排序能够消除多个逆序，也会产生新的逆序。
消除的逆序与新产生的逆序有多有少。
15.设二叉树的后序序列与中序序列均为ABCDEFGH，则该二叉树的前序序列为（分数：2.00）A.HGFEDCBA √B.ABCDEFGHC.ABCDHGFED.DCBAHGFE解析：解析：后序遍历中，最后一个字母是根结点，也就是H是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树，H后面没有，因此该树没有右子树。
同理，可判断出该树是第一个完全的左子树。
由此可画出这个二叉树，然后根据二叉树可的前序序列为HGFEDCBA。
16.下列叙述中正确的是（分数：2.00）A.循环队列是队列的链式存储结构B.能采用顺序存储的必定是线性结构C.所有的线性结构都可以采用顺序存储结构√D.具有两个以上指针的链表必定是非线性结构解析：解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。
所有的线性结构都可以采用顺序存储结构。
17.下列叙述中正确的是（分数：2.00）A.算法的复杂度是指算法所处理的数据量B.算法的复杂度是指算法程序中指令的数量C.算法的复杂度是指算法控制结构的复杂程度D.算法的复杂度包括时间复杂度与空间复杂度√解析：解析：算法分析的目的在于选择合适算法和改进算法。
一个算法的评价主要从时间复杂度和空间复杂度来考虑。
18.设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。
则按层次输出(从上到下，同一层从左到右)的序列为（分数：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的右结点，根据前序中的子树FIJ和中序中的IFJ子树可知F为C的右结点，I为F的左结点、J为F 的右结点。
由此可画出这个二叉树，然后根据二叉树，可知按层次输出(从上到下，同一层从左到右)的序列为：ABCDEFGHIJ。
19.设循环队列的存储空间为Q(1：50)，初始状态为front＝rear＝50。
经过一系列正常的操作后，front －1＝rear。
为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为（分数：2.00）A.0B.1C.48 √D.49解析：解析：front指向队头位置，删除一个元素就将front顺时针移动一位；rear指尾指针，指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；操作后，循环队列的队头指针－1等于尾指针，说明出队一位，那么总数就是49了。
在该队列中寻找最大值元素，最多比较次数是总数－1，因此是49－1＝48次。
20.设顺序表的长度为40，对该表进行冒泡排序。
在最坏情况下需要的比较次数为（分数：2.00）A.780 √B.820C.40D.41解析：解析：冒泡排序(Bubble Son)，是一种计算机科学领域的较简单的排序算法。
冒泡排序算法的运作如下：比较相邻的元素。
如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
在这一点，最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的最坏时问复杂度为(n*(n－1))／2＝780。