国家二级MS Office高级应用机试（数据结构与算法）模拟试卷13
选择题
1.下列叙述中正确的是(D)
A. 循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
B. 在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
C. 在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D. 循环队列中元素的个数是由队头指针和队尾指针共同决定
解析：循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。
2.支持子程序调用的数据结构是(A)
A. 栈
B. 树
C. 队列
D. 二叉树
解析：栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。
3.一棵完全二叉树共有360个结点，则在该二叉树中度为1的结点个数为(B)
A. 0
B. 1
C. 180
D. 181
解析：对于一个具有n个结点的完全二叉树，其深度为[log2n]+1。本题中这个二叉树的深度为[log2360]+1=8+1=9。根据满二叉树的性质，深度为8的满二叉树其结点数为28-1=256-1=255。这个完全二叉树的第9层的结点数为360-255=105。完全二叉树的性质非叶子结点的子结点都为2，105除以2其商为52余数为1。因此该二叉树中度为1的结点个数为1。选项B正确。
4.下列叙述中正确的是(B)
A. 有一个以上根结点的数据结构不一定是非线性结构
B. 只有一个根结点的数据结构不一定是线性结构
C. 循环链表是非线性结构
D. 双向链表是非线性结构
解析：在数据结构中，树这类的数据结构只有一个根结点，但它不是线性结构。
5.下列链表中，其逻辑结构属于非线性结构的是(A)
A. 二叉链表
B. 循环链表
C. 双向链表
D. 带链的栈
解析：二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。
6.一个栈的初始状态为空。现将元素1，2,3，A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是(C)
A. 1，2，3，A，B，C
B. C，B，A，1，2，3
C. C，B，A，3，2，1
D. 1，2，3，C，B，A
解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是CBA321。
7.某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为(根结点在第1层)(D)
A. 3
B. 6
C. 8
D. 12
解析：根据二叉树的性质，度为0的结点(即叶子结点)总是比度为2的结点多一个。题目中的二叉树的叶子结点为1，因此度为2的结点的数目为0，故该二叉树为12层，每层只有一个结点。
8.设某二叉树的前序序列为ABC，中序序列为CBA，则该二叉树的后序序列为(B)
A. BCA
B. CBA
C. ABC
D. CAB
解析：二叉树的前序遍历的顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历的顺序为首先访问左结点，然后依次访问右结点和根结点。
根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。对于本题根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。确定A之后，再看中序第二个值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。本题的具体二叉树如下，因此，后序是CBA。
9.在最坏情况下(C)
A. 快速排序的时间复杂度比冒泡排序的时间复杂度要小
B. 快速排序的时间复杂度比希尔排序的时间复杂度要小
C. 希尔排序的时间复杂度比直接插入排序的时间复杂度要小
D. 快速排序的时间复杂度与希尔排序的时间复杂度是一样的
解析：按平均时间将排序分为四类：
①平方阶(O(n2))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；
②线性对数阶(O(n1og2n))排序：如快速排序、堆排序和归并排序：
③O(nl+§))排序：§是介于0和1之间的常数。希尔排序便是一种；
④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。根据以上4点，可以判断选项C正确。
10.下列叙述中错误的是(C)
A. 算法的时间复杂度与算法所处理数据的存储结构有直接关系
B. 算法的空间复杂度与算法所处理数据的存储结构有直接关系
C. 算法的时间复杂度与空间复杂度有直接关系
D. 算法的时间复杂度与空间复杂度没有必然的联系
解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项C错误。
11.下列叙述中正确的是(B)
A. 在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构
B. 在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构
C. 在链表中，如果每个结点有两个指针域，则该链表一定是线性结构
D. 在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构
解析：选项A叙述是错误的，例如在双向链表中，每个结点有两个指针域，但该链表是线性结构；选项C叙述也是错误的，例如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项D叙述也是错误的，线性结构只有唯一的一个前驱和唯一的一个后继(头、尾除外)；排除法可判断选项B正确。
12.下列各序列中不是堆的是(C)
A. (91，85，53，36，47，30，24，12)
B. (91，85，53，47，36，30，24，12)
C. (47，91，53，85，30，12，24，36)
D. (91，85，53，47，30，12，24，36)
解析：堆可以看成一棵完全二叉树：任一根节点＞=左右孩子(或者＜=)，(大的叫大根堆，小的叫小根堆)。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显91是最大的根，而选项C是“左根右”的排序，那么91的左边只有47，其他都在右边，而右边无法按照此顺序排列，所以选项C不是堆。
13.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有(B)
A. 节省存储空间
B. 插入与删除运算效率高
C. 便于查找
D. 排序时减少元素的比较次数
解析：顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可
本文档预览：3600字符，共7658字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
