国家二级MS Office高级应用机试（数据结构与算法）模拟试卷42
选择题
1.下列叙述中正确的是( )。(C)
A. 算法的空间复杂度是指算法程序中指令的条数
B. 压缩数据存储空间不会降低算法的空间复杂度
C. 算法的空间复杂度与算法所处理的数据存储空间有关
D. 算法的空间复杂度是指算法程序控制结构的复杂程度
解析：算法的空间复杂度是指算法在执行过程中所需要的内存空间。算法执行期间所需的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通产采用压缩存储技术，以便尽量减少不必要的额外空间。
2.下列叙述中正确的是( )。(A)
A. 非线性结构可以为空
B. 只有一个根节点和一个叶子节点的必定是线性结构
C. 只有一个根节点的必定是线性结构或二叉树
D. 没有根节点的一定是非线性结构
解析：如果一个非空的数据结构满足下列两个条件：①有且只有一个根节点；②每一个节点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称为非线性结构。线性结构和非线性结构都可以是空的数据结构。树只有一个根节点，但不论有几个叶子节点，树都是非线性结构。
3.设数据结构B=(D，R)，其中
D={a，b，c，d，e，f}
R={(f，a)，(d，A)，(e，d)，(c，e)，(a，c)}
该数据结构为( )。(A)
A. 线性结构
B. 循环队列
C. 循环链表
D. 非线性结构
解析：数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R。即一个数据结构可以表示成B=(D，R)。其中，B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设a与b是D中的两个数据，则二元组(a，b)表示a是b的前件，b是a的后件。本题中R中的根节点为f，元素顺序为f→a→c→e→d→b，满足线性结构的条件。
4.下列叙述中正确的是( )。(A)
A. 在栈中，栈顶指针的动态变化决定栈中元素的个数
B. 在循环队列中，队尾指针的动态变化决定队列的长度
C. 在循环链表中，头指针和链尾指针的动态变化决定链表的长度
D. 在线性链表中，头指针和链尾指针的动态变化决定链表的长度
解析：在栈中，通常用指针top来指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。
5.设栈的顺序存储空间为S(1：m)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为( )。(C)
A. 0
B. m
C. 不可能
D. m+1
解析：栈为空时，栈顶指针top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=0，当栈满top=m，无法继续入栈，top值不可能为m+1。
6.设有栈S和队列Q，初始状态均为空。首先依次将A，B，C，D，E，F入栈，然后从栈中退出三个元素依次入队，再将X，Y，Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为( )。(B)
A. DEFXYZABC
B. FEDZYXCBA
C. FEDXYZCBA
D. DEFZYXABC
解析：栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将A，B，C，D，E，F入栈后，栈中元素为ABCDEF；退出三个元素入队，队列元素为FED；将X，Y，Z入栈后，栈中元素为ABCXYZ；退栈全部入队后，队列元素为FEDZYXCBA。
7.设循环队列的存储空间为Q(1：m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m-1，rear=m，此后再向该循环队列中插入一个元素，则队列中的元素个数为( )。(D)
A. m
B. m-1
C. 1
D. 2
解析：该题中m-1＜m，即rear-front＞0，则该循环队列中的元素个数为m-(m-1)=1。此后，从该循环队列中插入一个元素，则队列中的元素个数为1+1=2。
8.循环队列的存储空间为Q(1：40)，初始状态为front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为( )。(D)
A. 14
B. 15
C. 40
D. 39，或0且产生下溢错误
解析：当front=rear=15时，可知队列空或者队列满。此后又退出一个元素，如果之前队列为空，退出操作会产生错误，队列里有0个元素；如果退出之前队列已满(40个元素)，执行退出后，队列里还有39个元素。
9.下列叙述中正确的是( )。(B)
A. 节点中具有两个指针域的链表一定是二叉链表
B. 节点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C. 循环链表是循环队列的链式存储结构
D. 循环链表是非线性结构
解析：节点中具有两个指针域的链表既可以是双向链表又可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环链表是循环队列的一种顺序存储结构。
10.带链栈空的条件是( )。(A)
A. top=bottom=NULL
B. top=-1 且 bottom=NULL
C. top=NULL 且 bottom=-1
D. top=bottom=-1
解析：在带链的栈中，只会出现栈空和非空两种状态。当栈为空时，有top=bottom=NULL；当栈为非空时，top指向链表的第一个节点(栈顶)。
11.某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为( )。(D)
A. 0
B. 1
C. 10
D. 不确定
解析：带链的栈使用了链表来表示栈，而链表中的元素存储在不连续的地址中，因此当top=10，bottom=20时，不能确定栈中元素的个数。
12.非空循环链表所表示的数据结构( )。(A)
A. 有根节点，也有叶子节点
B. 没有根节点，但有叶子节点
C. 有根节点，但没有叶子节点
D. 没有根节点，也没有叶子节点
解析：循环链表表头节点为根节点，链表的最后一个节点为叶子节点，虽然它含有一个指向表头节点的指针，但是表头节点并不是它的一个后件。
13.设一棵度为3的树，其中度为2，1，0的节点数分别为3，1，6。该树中度为3的节点数为( )。(A)
A. 1
本文档预览：3600字符，共6476字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载