1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 19及答案与解析 一、选择题 1 下列关于排序的说法错误的是 ( )。 （ A）排序是指将一个无序序列整理成按值递增的顺序排列的有序序列的过程 （ B）交换类排序主要包括冒泡排序和快速排序 （ C）插入类排序主要包括简单插入和希尔排序 （ D）选择类排排序包括简单排序和堆排序 2 下列关于交换类排序叙述错误的是 ( )。 （ A）冒泡排序是通过两两相邻元素之间比较和交换，不断消除逆序，直到所有元素有序 （ B）快速排序是在线性 表中逐个选取元素，对表进行分割，直到所有的元素全部选取完毕 （ C）冒泡排序平均时间复杂度是 O(n
2、2)，最坏情况下时间复杂度是 O(n2) （ D）快速排序平均时间复杂度是 O(log2n)，最坏情况下时间复杂度是 O(n2) 3 在长度为 n的有序线性表中进行二分法查找，最坏情况下需要比较的次数是( )。 （ A） O(n) （ B） O(n2) （ C） O(log2n) （ D） O(nlog2n) 4 冒泡排序在最坏的情况下的比较次数是 ( )。 （ A） n （ B） (n-1)n 2 （ C） nlog2n （ D） n 2 5 对长度为 8的线性表进行冒泡排序，最坏情况下的比较次数是 ( )。 （ A） 36 （ B） 28 （ C） 8 （ D） 64 6 对于长度为 n的
3、线性表，在最坏情况下，下列各排序算法所对应的比较次数正确的是 ( )。 （ A）冒泡排序是 n （ B）冒泡排序是 log2n （ C）快速排序是 n(n-1) 2 （ D）快速排序是 n 7 对长度为 n的线性表做快速排序，在平均情况下时间复杂度是 ( )。 （ A） O(n2) （ B） O(n) （ C） O(log2n) （ D） O(nlog2n) 8 对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n-1) 2的排序方法是 ( )。 （ A）冒泡排序 （ B）快速排序 （ C）简单插入排序 （ D）堆排序 9 下列排序方法中，最坏情况下比较次数最少的是 ( )。 （ A）
4、冒泡排序 （ B）快速排序 （ C）简单插入排序 （ D）堆排序 10 下列数据结构不能用顺序存储的是 ( )。 （ A）栈 （ B）队列 （ C）非完全二叉树 （ D）堆 11 一个二叉树的总节点是 218个，其中度为 2的节点 是 100个，则度为 1的节点数是 ( )。 （ A） 17 （ B） 19 （ C） 18 （ D）不存在这样的二叉树 12 判定 “带头节点的链队列为空 ”的条件是 ( )。 （ A） Q front=NULL （ B） Q rear=NULL （ C） Q front=Q rear （ D） Q front!=Q rear 13 设二叉树共有 500个节点，其
5、中叶子节点有 250个，那么度为 2的节点有 ( )个。 （ A） 1 （ B） 0 （ C） 249 （ D）没有这样的二叉树 14 用链表表示 线性表的突出特点是 ( )。 （ A）节省存储空间 （ B）查找速度快 （ C）插入和删除不必移动数据 （ D）以上都不对 15 冒泡排序在最好情况下需要交换的次数是 ( )。 （ A） 1 （ B） 0 （ C） n （ D） n 2 16 下列二叉树的后序遍历结果是 ( )。 （ A） ABCDEF （ B） BDAECF （ C） ABDCEF （ D） DBEFCA 17 下列对线性链表的描述中正确的是 ( )。 （ A）存储空间不一定是连
6、续，且各元素的存储顺序是任意的 （ B）存储空间不一定 是连续，且前件元素一定存储在后件元素的前面 （ C）存储空间必须连续，且前件元素一定存储在后件元素的前面 （ D）存储空间必须连续，且各元素的存储顺序是任意的 18 线性表若采用链式存储结构时，要求内存中可用的存储单元地址 ( )。 （ A）必须是连续的 （ B）一定不是连续的 （ C）部分是连续的 （ D）可以是连续的，也可以是不连续的 19 在待排序的元素序列基本有序的前提下，效率最高的排序方法是 ( )。 （ A）插入排序 （ B）选择排序 （ C）快速排序 （ D）归并排序 20 栈和队列的共同点是 ( )。 （ A）都是 “先进
7、先出 ” （ B）都是 “后进先出 ” （ C）都只允许在端点处插入和删除元素 （ D）没有共同点 21 某二叉树的前序遍历是 cedba，中序遍历结果是 debac，那么它的后序遍历结果是 ( )。 （ A） abcde （ B） dabec （ C） decab （ D） cedba 22 算法的时间复杂度是指 ( )。 （ A）执行算法程序所需要的时间 （ B）算法程序的长度 （ C）算法执行过程中所需要的基本运算次数 （ D）算法程序中的指令条数 23 树是节点的集合，它的根节点数目是 ( )。 （ A）有且只有 1 （ B） 1或多于 1 （ C） O或 1 （ D）至少 2 24
8、入栈序列是 ABCD，则出栈顺序可能是 ( )。 （ A） DCBA （ B） ABCD （ C） BADC （ D）都有可能 25 链表不具有的特点是 ( )。 （ A）不必事先估计存储空间 （ B）可随机访问任一元素 （ C）插入或删除不需要移动元素 （ D）所需空间与线性表长度成正比 26 希尔排序属于 ( )。 （ A）交换排序 （ B）选择排序 （ C）归并排序 （ D）插入排序 国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 19答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 排序是指将一个无序序列整理成按值非递减的顺序排列的有序序列的过程。非递减是
9、指后面一项大于或等于前面一项，递增是指后面一项大于前面一项。序列中有可能有相同的值。 【知识模块】 数据结构与算法 2 【正确答案】 D 【试题解析】 冒泡排序的平均和最坏情况下时间复杂度都是 O(n2)，快速排序平均和最坏的情况下时间复杂度是 O(nlog2n)和 O(n2)，简单插入平均和最坏情况下时间复杂度都是 O(n2)，简单选择排序平均和最坏情况下时间复杂度都是 O(n2)，堆排序在平均和最坏情况下时间复杂度都是 O(nlog2n)。 【知识模块】 数据结构与算法 3 【正确答案】 C 【试题解析】 只有顺序存储的有序表才能进行二分法查找，题目中指出了用二分法查找，因此认为这个有序表
10、是顺序存储的，二分法查找时闻复杂度是 O(log2n)。 【知识模块】 数据结构与算法 4 【正确答案】 B 【试题解析】 冒泡排序是比较前后 2个元素，如果前一个元素大，则交换 2个元素的位置，直到将最大元素排在末尾，然后再比较前 n-1个元素，直到所有元素都是有序的。第一次比较 n-1次，第二次比较 n-2次，最后一次比较 1次。总的次数是 n-1+n-2+1=n(n -1) 2。 【知识模块】 数据结构与算法 5 【正确答案】 B 【试题解析】 冒泡排序在最坏情况下比较次数是 n(n-1) 2， 87 2=28。 【知识模块】 数据结构与算法 6 【正确答案】 C 【试题解析】 快速排序
11、 在最坏情况下会退化为冒泡排序，比较次数是 n(n-1)2。 【知识模块】 数据结构与算法 7 【正确答案】 D 【试题解析】 快速排序平均和最坏的情况下时间复杂度是 O(nlog2n)和 O(n2)。 【知识模块】 数据结构与算法 8 【正确答案】 D 【试题解析】 在最坏情况下，冒泡排序、快速排序和简单插入排序的时间复杂度都是 O(n2)，堆排序的时间复杂度在最坏和平均情况下都是 O(nlog2n)。 【知识模块】 数据结构与算法 9 【正确答案】 D 【试题解析】 在最坏情况 下，比较次数最少的是堆排序 O(nlog2n)，其他的都是O(n2)。 【知识模块】 数据结构与算法 10 【正
12、确答案】 C 【试题解析】 堆一般是用完全二叉树表示。栈、队列和堆都可以用顺序存储，而非完全二叉树不能用顺序存储。 【知识模块】 数据结构与算法 11 【正确答案】 A 【试题解析】 二叉树的一个性质：叶子节点的个数比度为 2的节点多 1。设度为1的节点数是 x，则 x+100+100+1=218， x=17。 【知识模块】 数据结构与算法 12 【正确答案】 C 【试题解析】 当带头节点的链队为空时，只有一个头节点，头、尾指针均指向头节点，因此有 Q front=Q rear。 【知识模块】 数据结构与算法 13 【正确答案】 C 【试题解析】 二叉树的一个性质：叶子节点的个数比度为 2的节
13、点多 1。叶子节点数为 250，那么度为 2的节点为 249。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 链表存储线性表，每个节点有一个数值域和指针域，指针域指向后面一个节点的地址，因此链表存储浪费空间，在查找的时候需要从头向后遍 历，直到找到查找的元素，速度并不快，链表在插入和删除的时候。只需要把新节点的指针指向插入位置的后一个节点，然后改变插入位置前面一个节点的指针域指向插入的新节点。 【知识模块】 数据结构与算法 15 【正确答案】 B 【试题解析】 最好情况下就是数据已经是有序的，交换次数为 0。 【知识模块】 数据结构与算法 16 【正确答案】 D 【试题解
14、析】 二叉树的后序遍历是先遍历左子树，后遍历右子树，最后访问根节点。遍历左右子树也采用的是后序遍历方法，因此遍历的顺序是 DBEFCA。本题也 可以用排除法，最后访问根节点，那么 A一定是在最后，这样能快速选出答案是 D项。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 链表的存储空间不一定是连续的，由于每个节点都有一个指针域指向下一个节点，因此各元素的存储顺序也没有固定的要求。 【知识模块】 数据结构与算法 18 【正确答案】 D 【试题解析】 链式存储时内存地址可以是连续的也可以不是连续的。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 插入排序
15、通过数据元素 的交换来逐步消除线性表中的逆序，所以关键字比较的次数与记录的初始排列次序有关，在待排序的元素序列基本有序的前提下，效率最高。而选择排序和堆排序的关键字比较的次数与记录的初始排列次序无关。快速排序虽然与记录的初始排列次序有关，但在待排序的元素序列基本有序的前提下，效率低于插入排序。 【知识模块】 数据结构与算法 20 【正确答案】 C 【试题解析】 栈和队列都是操作受限的线性表，栈只允许在一端进行入栈退栈操作，队列允许在一端进行出队操作。另一端允许入队操作；栈是先进后出，队列是先进先出。 【知识模块】 数据结构与算法 21 【正确答案】 B 【试题解析】 前序遍历是 cedba，说
16、明根节点是 c，中序遍历结果是 debac，说明这个二叉树没有右子树，左子树的前序遍历是 edba，说明左子树的根节点是 e，中序遍历是 deba，则 d是左子树的左叶子节点， ba是左子树的右子树节点，且 a是 b的右叶子节点，故这个二叉树如图 4。其后序遍历是 dabec。本题也可以用快速排除法，根节点是 c，那么后序遍历 c一定是在最后，可以得知只有 B项正确。【知识模块】 数据结构与算法 22 【正确答案】 C 【试题解析】 算法的时间复杂度是指算法执行过程中所需要的基本运算次数。 【知识模块】 数据结构与算法 23 【正确答案】 C 【试题解析】 树的根节点最多只有 1个，当是空树的
17、时候，也可以为 0个。 【知识模块】 数据结构与算法 24 【正确答案】 D 【试题解析】 出栈的顺序可有多种情况，本题只能用排除法。 DCBA这种是可能的， ABCD全部入栈之后退栈。退栈的顺序结果就是 DCBA； ABCD这个顺序也是可能的， A入栈退栈， B入栈退栈， C入栈退栈， D入栈退栈，退栈的顺序就是ABCD； BADC也是可能的， A入栈 B入栈，然后 B退栈 A退栈， C入栈 D入栈，然后 D退栈 C退栈，退栈顺序就是 BADC。因此答案是 D项。 【知识模块】 数据结构与算法 25 【正确答案】 B 【试题解析】 链表是指链式存储的线性表。由于不是顺序存储因此内存可以不连续，也就不需要事先估算存储空间，插入和删除元素只要改变相关节点的指针指向地址即可。随机访问是指知道了线性表的第一个元素存储位置，然后可以计算出线性表中任意一个元素所在的位置，根据位置直接访问该元素。而链表存储的元素其位置是不确定的，因此不能 随机访问。 【知识模块】 数据结构与算法 26 【正确答案】 D 【试题解析】 希尔排序是插入排序的一种高效版本，它按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1时，整个序列恰被分成一组，算法便终止。 【知识模块】 数据结构与算法
