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