国家二级MS Office高级应用机试（数据结构与算法）模拟试卷32
选择题
1.下列叙述中正确的是(A)
A. 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的
B. 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构
C. 顺序存储结构能存储有序表，链式存储结构不能存储有序表
D. 链式存储结构比顺序存储结构节省存储空间
解析：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。
2.下列数据结构中，属于非线性结构的是(C)
A. 循环队列
B. 带链队列
C. 二叉树
D. 带链栈
解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。
3.下列关于栈叙述正确的是(A)
A. 栈顶元素最先能被删除
B. 栈顶元素最后才能被删除
C. 栈底元素永远不能被删除
D. 以上三种说法都不对
解析：栈是先进后出的线性表，栈顶的元素最先被删除，栈底的元素最后被删除。
4.下列各组的排序方法中，最坏情况下比较次数相同的是(A)
A. 冒泡排序与快速排序
B. 简单插入排序与希尔排序
C. 堆排序与希尔排序
D. 快速排序与希尔排序
解析：最坏情况下冒泡排序需要比较n(n一1)／2次，即序列逆序的情况。简单插入排序，无论是否最坏情况，都需要n(n-1)／2次。直接捅入排序，最坏情况需要比较次n(n-1)／2次。堆排序，无论是否最坏都要比较O(nlog2n)次。快速排序，最坏情况退化为冒泡排序，需要比较n(n-1)／2次。在最坏情况下，希尔排序所需要的比较次数为O(n1．5)。选项A正确。
5.下列关于栈的叙述中，正确的是(C)
A. 栈底元素一定是最后入栈的元素
B. 栈顶元素一定是最先入栈的元素
C. 栈操作遵循先进后出的原则
D. 以上三种说法都不对
解析：栈是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进先出”的规则操作元素。
6.下列叙述中正确的是(A)
A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化
B. 循环队列中的元素个数随队头指针的变化而动态变化
C. 循环队列中的元素个数随队尾指针的变化而动态变化
D. 循环队列中的元素个数不会变化
解析：所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针front指向的后一个位置与队尾指针rear指向位置之间的元素数量。
7.下列叙述中正确的是(D)
A. 有且只有一个根结点的数据结构一定是线性结构
B. 每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构
C. 有且只有一个根结点的数据结构一定是非线性结构
D. 有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构
解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分这两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。称该数据结构为线性结构，又称为线性表。对于这个题目来说，有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构。具有一个根结点的树就是一个非线性结构，选项D正确。
8.为了对有序表进行对分查找，则要求有序表(A)
A. 只能顺序存储
B. 只能链式存储
C. 可以顺序存储也可以链式存储
D. 任何存储方式
解析：有序表的对分查找条件是有序表为顺序存储。
顺序查找：①如果线性表为无序表(即表中元素的排序是无序的)，则无论是顺序存储结构还是链式存储结构，都只能用顺序查找；②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
分块查找(又称索引顺序查找)：分块有序表结构分为两部分，①线性表本身采用顺序存储结构；②在建立一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。显然索引表关于数据域是有序的。
9.设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为(C)
A. 30
B. 20
C. m－19
D. m－20
解析：根据题意，栈空间如图所示：
10.某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的深度(根结点在第1层)为(C)
A. 2
B. 3
C. 4
D. 5
解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上；并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。
所以得到的二叉树为，所以这个二叉树的深度为4。选项C为正确答案。
11.设数据元素的集合D={1，2，3，4，5}，则满足下列关系R的数据结构中为线性结构的是
B
解析：把每个答案中的第一个元素集合取出来，例如A：(1,2)，先写下来就是12，然后看后面的(3,4)，在(1,2)中找不到前驱和后继，只能和(1,2)暂时先并列，然后是(5,1)，这里我们已经写过12了，那么5在1前面就是512，但是34要单排，所以A就是两个根节点3和5，两个顺序是512,34。
同理选项B是541,32；选项C是：123和45；选项D是135,24所以选项B正确。
12.有二叉树如下图所示，则前序序列为
(A)
A. ABDEGCFH
B. DBGEAFHC
C. DGEBHFCA
D. ABCDEFGH
解析：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故选项A正确，选项B为中序遍历，选项C为后序遍历，选项D不正确。
13.下列叙述中正确的是(C)
A. 所谓有序表是指在顺序存储空间内连续存放
本文档预览：3600字符，共7921字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
