国家二级MS Office高级应用机试（数据结构与算法）模拟试卷9
选择题
1.对长度为n的线性表排序，存最坏情况下，比较次数不是n(n一1)／2的排序方法是(D)
A. 快速排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
解析：各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序n(n-1)／2、快速排序n(n-1)／2、简单插入排序n(n-1)／2、希尔排序O(n1．5)、简单选择排序n(n-1)／2、堆排序O(nlog2n)。
2.对于循环队列，下列叙述中正确的是(D)
A. 队头指针是固定不变的
B. 队头指针一定大于队尾指针
C. 队头指针一定小于队尾指针
D. 队头指针可以大于队尾指针，也可以小于队尾指针
解析：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置。循环队列的主要操作是：入队运算和退队运算。每进行一次入队运算，队尾指针就进一。每进行一次退队运算，队头指针就进一。当rear或front等于队列的长度加1时，就把rear或front值置为1。所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。
3.下列叙述中正确的是(D)
A. 栈是“先进先出”的线性表
B. 队列是“先进后出”的线性表
C. 循环队列是非线性结构
D. 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
解析：本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。
4.下列叙述中正确的是(C)
A. 在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B. 在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
C. 在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
D. 上述三种说法都不对
解析：在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈跟队列不同，元素只能在栈顶压入或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循后进先出的规则。
5.下列叙述中正确的是(B)
A. 循环队列是队列的一种链式存储结构
B. 循环队列是队列的一种顺序存储结构
C. 循环队列是非线性结构
D. 循环队列是一种逻辑结构
解析：本题主要考查循环队列的概念，循环队列作为队列的一种也应该是线性结构。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列。
6.设二叉树共有150个结点，其中度为1的结点有10个，则该二叉树中的叶子结点数为(D)
A. 71
B. 70
C. 69
D. 不可能有这样的二叉树
解析：根据二叉树的性质3，在任意一颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。即有n0=n2+1。对于这个题来说，总结点数150=n0+n1+n2=n2+1+10+n2=2n2+11，所以2n2=139，度为2个结点个数不能确定。选项D正确。
7.一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为(B)
A. 219
B. 229
C. 230
D. 231
解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个，故总结点数=叶子节点数+度为2的节点数+度为1的节点数=80+79+70=229。
8.下列叙述中错误的是(C)
A. 在双向链表中，可以从任何一个结点开始直接遍历到所有结点
B. 在循环链表中，可以从任何一个结点开始直接遍历到所有结点
C. 在线性单链表中，可以从任何一个结点开始直接遍历到所有结点
D. 在二叉链表中，可以从根结点开始遍历到所有结点
解析：线性队列是一种线性单链表，对线性队列的遍历只能从队列的头开始，从中间的结点开始不能够遍历到所有的结点。选项C的描述是错误的。
9.设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为(C)
A. BCA
B. CBA
C. ABC
D. CAB
解析：二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。
本题根据后序，可以确定A为根结点；根据B在中序中的位置，可以确定A没有左子树，BC为A的右子树，C为B的右子树。本题的具体二叉树如下，因此，这棵二叉树的前序是ABC，选项C正确。
10.算法空间复杂度的度量方法是(D)
A. 算法程序的长度
B. 算法所处理的数据量
C. 执行算法所需要的工作单元
D. 执行算法所需要的存储空间
解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。
11.下列叙述中正确的是(D)
A. 存储空间连续的数据结构一定是线性结构
B. 存储空间不连续的数据结构一定是非线性结构
C. 没有根结点的非空数据结构一定是线性结构
D. 具有两个根结点的数据结构一定是非线性结构
解析：数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件：
①有且只有一个根结点；
②每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A、B和C都不能判定是否是线性结构，选项D正确。
12.下列叙述中正确的是(A)
A. 链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构
B. 线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针
C. 线性表的链式存储结构中，每个结点只能有一个指向后件的指针
D. 线性表的链式存储结构中，叶子结点的指针只能是空
解析：在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项B、C、D说法错误。选项A中，例如双向链表就具有两个指针，也属于线性结构，所以选项A正确。
13.下列叙述中正确的是(A)
A. 循环队列是顺序存储结构
B. 循环队列是链式存储结构
C. 循环队列是非线性结构
D. 循环队列的插入运算不会发生溢出现象
解析：循环队列属于队列的特例和栈
本文档预览：3600字符，共7791字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
