国家二级MS Office高级应用机试（数据结构与算法）模拟试卷19

国家二级MS Office高级应用机试（数据结构与算法）模拟试卷19

选择题

1.下列关于排序的说法错误的是( )。(A)

A. 排序是指将一个无序序列整理成按值递增的顺序排列的有序序列的过程

B. 交换类排序主要包括冒泡排序和快速排序

C. 插入类排序主要包括简单插入和希尔排序

D. 选择类排排序包括简单排序和堆排序

解析：排序是指将一个无序序列整理成按值非递减的顺序排列的有序序列的过程。非递减是指后面一项大于或等于前面一项，递增是指后面一项大于前面一项。序列中有可能有相同的值。

2.下列关于交换类排序叙述错误的是( )。(D)

A. 冒泡排序是通过两两相邻元素之间比较和交换，不断消除逆序，直到所有元素有序

B. 快速排序是在线性表中逐个选取元素，对表进行分割，直到所有的元素全部选取完毕

C. 冒泡排序平均时间复杂度是O(n²)，最坏情况下时间复杂度是O(n²)

D. 快速排序平均时间复杂度是O(log₂n)，最坏情况下时间复杂度是O(n²)

解析：冒泡排序的平均和最坏情况下时间复杂度都是O(n²)，快速排序平均和最坏的情况下时间复杂度是O(nlog₂n)和O(n²)，简单插入平均和最坏情况下时间复杂度都是O(n²)，简单选择排序平均和最坏情况下时间复杂度都是O(n²)，堆排序在平均和最坏情况下时间复杂度都是O(nlog₂n)。

3.在长度为n的有序线性表中进行二分法查找，最坏情况下需要比较的次数是( )。(C)

A. O(n)

B. O(n²)

C. O(log₂n)

D. O(nlog₂n)

解析：只有顺序存储的有序表才能进行二分法查找，题目中指出了用二分法查找，因此认为这个有序表是顺序存储的，二分法查找时闻复杂度是O(log₂n)。

4.冒泡排序在最坏的情况下的比较次数是( )。(B)

A. n

B. (n-1)n／2

C. nlog₂n

D. n／2

解析：冒泡排序是比较前后2个元素，如果前一个元素大，则交换2个元素的位置，直到将最大元素排在末尾，然后再比较前n-1个元素，直到所有元素都是有序的。第一次比较n-1次，第二次比较n-2次，最后一次比较1次。总的次数是n-1+n-2+…+1=n(n-1)／2。

5.对长度为8的线性表进行冒泡排序，最坏情况下的比较次数是( )。(B)

A. 36

B. 28

C. 8

D. 64

解析：冒泡排序在最坏情况下比较次数是n(n-1)／2，8×7／2=28。

6.对于长度为n的线性表，在最坏情况下，下列各排序算法所对应的比较次数正确的是( )。(C)

A. 冒泡排序是n

B. 冒泡排序是log₂n

C. 快速排序是n(n-1)／2

D. 快速排序是n

解析：快速排序在最坏情况下会退化为冒泡排序，比较次数是n(n-1)／2。

7.对长度为n的线性表做快速排序，在平均情况下时间复杂度是( )。(D)

A. O(n²)

B. O(n)

C. O(log₂n)

D. O(nlog₂n)

解析：快速排序平均和最坏的情况下时间复杂度是O(nlog₂n)和O(n²)。

8.对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)／2的排序方法是( )。(D)

A. 冒泡排序

B. 快速排序

C. 简单插入排序

D. 堆排序

解析：在最坏情况下，冒泡排序、快速排序和简单插入排序的时间复杂度都是O(n²)，堆排序的时间复杂度在最坏和平均情况下都是O(nlog₂n)。

9.下列排序方法中，最坏情况下比较次数最少的是( )。(D)

A. 冒泡排序

B. 快速排序

C. 简单插入排序

D. 堆排序

解析：在最坏情况下，比较次数最少的是堆排序O(nlog₂n)，其他的都是O(n²)。

10.下列数据结构不能用顺序存储的是( )。(C)

A. 栈

B. 队列

C. 非完全二叉树

D. 堆

解析：堆一般是用完全二叉树表示。栈、队列和堆都可以用顺序存储，而非完全二叉树不能用顺序存储。

11.一个二叉树的总节点是218个，其中度为2的节点是100个，则度为1的节点数是( )。(A)

A. 17

B. 19

C. 18

D. 不存在这样的二叉树

解析：二叉树的一个性质：叶子节点的个数比度为2的节点多1。设度为1的节点数是x，则x+100+100+1=218，x=17。

12.判定“带头节点的链队列为空”的条件是( )。(C)

A. Q．front==NULL

B. Q．rear==NULL

C. Q．front==Q．rear

D. Q．front!==Q．rear

解析：当带头节点的链队为空时，只有一个头节点，头、尾指针均指向头节点，因此有Q．front=Q．rear。

13.设二叉树共有500个节点，其中叶子节点有250个，那么度为2的节点有( )个。(C)

A. 1

B. 0

C. 249

D. 没有这样的二叉树

解析：二叉树的一个性质：叶子节点的个数比度为2的节点多1。叶子节点数为250，那么度为2的节点为249。

14.用链表表示线性表的突出特点是( )。(C)

A. 节省存储空间

B. 查找速度快

C. 插入和删除不必移动数据

D. 以上都不对

解析：链表存储线性表，每个节点有一个数值域和指针域，指针域指向后面一个节点的地址，因此链表存储浪费空间，在查找的时候需要从头向后遍历，直到找到查找的元素，速度并不快，链表在插入和删除的时候。只需要把新节点的指针指向插入位置的后一个节点，然后改变插入位置前面一个节点的指针域指向插入的新节点。

15.冒泡排序在最好情况下需要交换的次数是( )。(B)

A. 1

B. 0

C. n

D. n／2

解析：最好情况下就是数据已经是有序的，交换次数为0。

16.下列二叉树的后序遍历结果是( )。

(D)

A. ABCDEF

B. BDAECF

C. ABDCEF

D. DBEFCA

解析：二叉树的后序遍历是先遍历左子树，后遍历右子树，最后访问根节点。遍历左右子树也采用的是后序遍历方法，因此遍历的顺序是DBEFCA。本题也可以用排除法，最

本文档预览：3600字符，共5937字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载