国家二级MS Office高级应用机试（选择题）模拟试卷265
选择题
1.在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是(C)
A. O(n)
B. O(n2)
C. O(log2n)
D. O(nlog2n)
解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。
2.算法的有穷性是指(A)
A. 算法程序的运行时间是有限的
B. 算法程序所处理的数据量是有限的
C. 算法程序的长度是有限的
D. 算法只能被有限的用户使用
解析：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
3.算法的时间复杂度是指(C)
A. 设计该算法所需的工作量
B. 执行该算法所需要的时间
C. 执行该算法时所需要的基本运算次数
D. 算法中指令的条数
解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。
4.下列关于二叉树的叙述中，正确的是(B)
A. 叶子结点总是比度为2的结点少一个
B. 叶子结点总是比度为2的结点多一个
C. 叶子结点数是度为2的结点数的两倍
D. 度为2的结点数是度为l的结点数的两倍
解析：由二叉树的性质可以知道在二叉树中叶子结点总是比度为2的结点多一个。
5.设循环队列的存储空间为Q(1：35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为(D)
A. 15
B. 16
C. 20
D. 0或35
解析：循环队列的队头指针和尾指针都等于15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达15，此时元素个数为O；第二种情况是队头指针第一次到达15，而尾指针第二次到达15，此时元素个数为35。
6.下列叙述中正确的是(D)
A. 一个算法的空间复杂度大，则其时间复杂度也必定大
B. 一个算法的空间复杂度大，则其时间复杂度必定小
C. 一个算法的时间复杂度大，则其空间复杂度必定小
D. 算法的时间复杂度与空间复杂度没有直接关系
解析：算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中n是问题的规模；算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。
7.对长度为n的线性表作快速排序，在最坏情况下，比较次数为(D)
A. n
B. n—l
C. n(n-1)
D. n(n-1)／2
解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n／2遍的从后往前的扫描，需要的比较次数为n(n-1)／2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。
8.下列排序方法中，最坏情况下时间复杂度最小的是(C)
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 直接插入排序
解析：排序方法中最坏情况下时间复杂度的大小如下表，根据下表可知选项C正确。
9.在深度为7的满二叉树中，度为2的结点个数为(B)
A. 64
B. 63
C. 32
D. 31
解析：因为在任意的二叉树中，度为O的结点(即叶子结点)总比度为2的结点的个数多1个，而度为O的结点数n0=2m-1(其中m为二叉树的深度)。本题的度为O的结点个数n0=27-1=26=64。因此，度为2的结点数n2=n0—1=63。所以选项B正确。
10.设栈的顺序存储空间为S(0：49)，栈底指针bottom=49，栈顶指针top=30(指向栈顶元素)。则栈中的元素个数为(C)
A. 30
B. 29
C. 20
D. 19
解析：在操作系统中，栈是向下生长的，如下图如示：
11.下列叙述中错误的是(B)
A. 在带链队列中，队头指针和队尾指针都是在动态变化的
B. 在带链栈中，栈顶指针和栈底指针都是在动态变化的
C. 在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的
D. 以上三项都错误
解析：栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈顶，另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项C的说法正确，选项B的说法是错误的。队列是允许在队列的头和尾都可以进行操作的线性表，所以在带链队列中，队头指针和队尾指针都是在动态变化的选项A这一说法是正确的。
12.深度为5的完全二叉树的结点数不可能是(A)
A. 15
B. 16
C. 17
D. 18
解析：对于满二叉树，叶子结点的数目等于2n-1,n为深度，这里就是2的5-1=4次方，就是16。所以选项A为正确答案。
13.深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为(B)
A. 62
B. 63
C. 64
D. 65
解析：对于满二叉树，结点的数目等于21-1，叶子结点数目为2n-1，n为深度，这里就是2的7次方-1，就是127个结点，叶子结点是64个。然而题目中只有125个结点，说明少了两个结点，那么就少了一个叶子结点，即63个。
14.下列叙述中正确的是(A)
A. 算法的时间复杂度与运行算法时特定的输入有关
B. 算法的时间复杂度与计算机的运行速度有关
C. 算法的时间复杂度与算法程序中的语句条数成正比
D. 算法的时间复杂度与算法程序编制者的水平有关
解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项A正确。
15.循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为(A)
A. 1，或50且产生上溢错误
B. 5l
C. 26
本文档预览：3600字符，共6644字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载