国家二级MS Office高级应用机试（数据结构与算法）模拟试卷39
选择题
1.下列叙述中正确的是( )。(B)
A. 所谓算法就是计算方法
B. 程序可以作为算法的一种描述方法
C. 算法设计只需考虑得到计算结果
D. 算法设计可以忽略算法的运算时间
解析：算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。
2.为了降低算法的空间复杂度，要求算法尽量采用原地工作(in place)。所谓原地工作是指( )。(D)
A. 执行算法时不使用额外空间
B. 执行算法时不使用任何存储空间
C. 执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化
D. 执行算法时所使用的额外空间固定(即不随算法所处理的数据空间大小的变化而变化)
解析：对于算法的空间复杂度，如果额外空间量相对于问题规模(即输入数据所占的存储空间)来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。
3.下列叙述中错误的是( )。(B)
A. 数据结构中的数据元素可以是另一数据结构
B. 数据结构中的数据元素不能是另一数据结构
C. 空数据结构可以是线性结构，也可以是非线性结构
D. 非空数据结构可以没有根节点
解析：数据元素是一个含义很广泛的概念，它是数据的“基本单位”，在计算机中通常作为一个整体进行考虑和处理。数据元素可以是一个数据，也可以是被抽象出的具有一定结构的数据集合，所以数据结构中的数据元素可以是另一数据结构。满足有且只有一个根节点并且每一个节点最多有一个前件，也最多有一个后件的非空的数据结构认为是线性结构，不满足条件的结构为非线性结构。空数据结构可以是线性结构，也可以是非线性结构。非空数据结构可以没有根节点，如非线性结构“图”就没有根节点。
4.下列叙述中正确的是( )。(B)
A. 矩阵是非线性结构
B. 数组是长度固定的线性表
C. 对线性表只能做插入与删除运算
D. 线性表中各元素的数据类型可以不同
解析：矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。
5.设栈的存储空间为s(1：50)，初始状态为top=-1。现经过一系列正常的入栈与退栈操作后，top=30，则栈中的元素个数为( )。(D)
A. 20
B. 19
C. 31
D. 30
解析：栈的初始状态为top=-1，表示栈为空。经过一系列正常的入栈与退栈操作后top=30，则空间(1：30)中插入了元素，共30个。
6.设栈的存储空间为S(1：m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中退出一个元素后，栈顶指针top值为( )。(C)
A. 0
B. m-1
C. m+1
D. 产生栈空错误
解析：栈的顺序存储空间为S(1：m)，初始状态top=m+1，所以这个栈是m在栈底(也可理解为开口向下的栈)。经过一系列入栈与退栈操作后top=m，则栈中有1个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到m+1的位置。
7.下列叙述中正确的是( )。(B)
A. 在循环队列中，队尾指针的动态变化决定队列的长度
B. 在循环队列中，队头指针和队尾指针的动态变化决定队列的长度
C. 在带链的队列中，队头指针和队尾指针的动态变化决定队列的长度
D. 在带链的栈中，栈顶指针的动态变化决定栈中元素的个数
解析：在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。带链的栈和带链的队列均采用链式存储结构，而在这种结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。
8.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=30，rear=10。现要在该循环队列中做顺序查找，最坏情况下需要比较的次数为( )。(D)
A. 19
B. 20
C. m-19
D. m-20
解析：front=30，rear=10，front＞rear，则队列中有10-30+m=m-20个元素，在做顺序查找时，最坏情况下(最后一个元素才是要找的元素或没有要查找的元素)比较次数为m-20。
9.设循环队列的存储空间为Q(1：m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为( )。(B)
A. m-1
B. m-2
C. 0
D. 1
解析：在循环队列中，如果rear-front＞0，则队列中的元素个数为rear-front个；如果rear-front＜0，则队列中的元素个数为rear-front+m。该题中m-1＜m，即。rear-front＜0，则该循环队列中的元素个数为(m-1)-m+m=m-1。此后从该循环队列中删除一个元素，则队列中的元素个数为m-1-1=m-2。
10.带链的栈与顺序存储的栈相比，其优点是( )。(C)
A. 入栈与退栈操作方便
B. 可以省略栈底指针
C. 入栈操作时不会受栈存储空间的限制而发生溢出
D. 所占存储空间相同
解析：带链的栈就是用一个线性链表来表示的栈，线性链表不受存储空间大小的限制，因此入栈操作时不会受栈存储空问的限制而发生溢出(不需考虑栈满的问题)。
11.带链的队列空的条件是( )。(A)
A. front=rear=NULL
B. frnot=-1且rear=NULL
C. front=NULL 且 rear=-1
D. front=rem=-1
解析：带链的队列就是用一个单链表来表示的队列，队列中的每一个元素对应链表中的一个节点。队列空时，头指针和尾指针都为NULL。
12.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=10，rear=5。该队列中的元素个数为( )。(D)
A. 4
B. 5
C. 6
D. 不确定
解析：带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当front=10，rear=5时，不能确定队列中元素的个数。
13.下叙述中错误的是( )。(B)
A. 循环链表中有一个表头节点
B. 循环链表是循环队列的存储结构
C. 循环链表的表头指针与循环链表中最后一个节点的指针均指向表头节点
D. 循环链表实现了空表与非空表运算的统一
解析：循环链表是指在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点
本文档预览：3600字符，共6382字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
