国家二级MS Office高级应用机试（数据结构与算法）模拟试卷10
选择题
1.下列关于栈的叙述正确的是(B)
A. 栈按“先进先出”组织数据
B. 栈按“先进后出”组织数据
C. 只能在栈底插入数据
D. 不能删除数据
解析：栈是限定在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。
2.算法的空间复杂度是指(A)
A. 算法在执行过程中所需要的计算机存储空间
B. 算法所处理的数据量
C. 算法程序中的语句或指令条数
D. 算法在执行过程中所需要的临时工作单元数
解析：算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
3.下列数据结构中，能够按照“先进后出”原则存取数据的是(B)
A. 循环队列
B. 栈
C. 队列
D. 二叉树
解析：栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据；队列是“先进先出”(FIFO)或“后进后出”(LIL0)的线性表。
4.某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层)(D)
A. 3
B. 4
C. 6
D. 7
解析：根据二叉树的性质，度为0的结点(即叶子结点)总是比度为2的结点多一个。题目中的二叉树的叶子结点为1，因此度为2的结点的数目为0，故该二叉树为7层，每层只有一个结点。
5.下列关于线性链表的叙述中，正确的是(C)
A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C. 进行插入与删除时，不需要移动表中的元素
D. 以上都不正确
解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据冗素之间的逻辑关系是由指针域来确定的。
6.下列叙述中正确的是(A)
A. 程序执行的效率与数据的存储结构密切相关
B. 程序执行的效率只取决于程序的控制结构
C. 程序执行的效率只取决于所处理的数据量
D. 以上都不正确
解析：影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别。其中，链式存储结构的效率要高一些。
7.对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为(C)
A. 9
B. 10
C. 45
D. 90
解析：线性表的长度为n，最坏情况下冒泡排序需要比较的次数为n(n-1)／2。
8.某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为(A)
A. 5
B. 4
C. 3
D. 2
解析：根据二叉树的性质3，在任意一颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个，即有n0=n2+1。本题总结点数：13=n0+n1+n2=n2+1+4+n2=2n2+5，n2=4，所以叶子结点数等于4+1=5，选项A正确。
9.下列叙述中正确的是(D)
A. 存储空间不连续的所有链表一定是非线性结构
B. 结点中有多个指针域的所有链表一定是非线性结构
C. 能顺序存储的数据结构一定是线性结构
D. 带链的栈与队列是线性结构
解析：计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。而数据在内存或磁盘中的存储，可以分为顺序存储和链式存储。数据的逻辑结构与存储结构之间没有对应的关系。所以选项ABC都是错误的，栈和队列按照数据的逻辑划分都是线性结构。
10.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为(A)
A. 4
B. 6
C. m-5
D. m-6
解析：初始状态为front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾rear减队头front等于5个元素。此时队列中有5个元素，而查找最大项至少要比较n-1次，就是4次。因此选项A正确。
11.下列叙述中正确的是(C)
A. 带链队列的存储空间可以不连续，但队头指针必须大于队尾指针
B. 带链队列的存储空间可以不连续，但队头指针必须小于队尾指针
C. 带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针
D. 以上三项都错误
解析：带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项C正确。
12.一个栈的初始状态为空，现将元素A、B、C、D、E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为(C)
A. ABC
B. CBA
C. EDC
D. CDE
解析：栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为E、D、C；一队列是根据先进先出的原则组织数据的，所以退队的顺序依次为E、D、C，所以选项C正确。
13.下列叙述中正确的是(D)
A. 所有数据结构必须有根结点
B. 所有数据结构必须有终端结点(即叶子结点)
C. 只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构
D. 没有根结点或没有叶子结点的数据结构一定是非线性结构
解析：只有一个空节点的结构也属数据结构，所以选项A和选项B不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故选项C不正确，选项D正确。
14.下列叙述中正确的是(B)
A. 结点中具有两个指针域的链表一定是二叉链表
B. 结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C. 二叉树只能采用链式存储结构
D. 循环链表是非线性结构
解析：结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故选项A小正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。
它可采用顺序存储结构和链式存储结构，故选项C不正确；循环链表是在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点的线性结构，故选NULL不正确；当结点中两个指针分别指向前驱结点和后继结点时为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故选项B正确。
15.某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为(B)
A. 不存在这样的二叉树
B. 200
C. 198
D. 199
本文档预览：3600字符，共7283字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
