国家二级MS Office高级应用机试（数据结构与算法）模拟试卷33
选择题
1.下列叙述中正确的是( )。(B)
A. 所谓算法就是计算方法
B. 程序可以作为算法的一种描述方法
C. 算法设计只需考虑得到计算结果
D. 算法设计可以忽略算法的运算时间
解析：算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。
2.下列叙述中正确的是( )。(B)
A. 算法的时间复杂度与计算机的运行速度有关
B. 算法的时间复杂度与运行算法时特定的输入有关
C. 算法的时间复杂度与算法程序中的语句条数成正比
D. 算法的时间复杂度与算法程序编制者的水平有关
解析：为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。
3.为了降低算法的空间复杂度，要求算法尽量采用原地工作(in place)。所谓原地工作是指( )(D)
A. 执行算法时不使用额外空间
B. 执行算法时不使用任何存储空间
C. 执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化
D. 执行算法时所使用的额外空间固定(即不随算法所处理的数据空间大小的变化而变化)
解析：对于算法的空间复杂度，如果额外空间量相对于问题规模(即输入数据所占的存储空间)来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。
4.设数据结构B=(D，R)，其中
D={a，b，c，d，e，f}
R={(f，a)，(d，b)，(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，满足线性结构的条件。
5.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数( )。(C)
A. 不同，但元素的存储顺序与逻辑顺序一致
B. 不同，且其元素的存储顺序可以与逻辑顺序不一致
C. 相同，元素的存储顺序与逻辑顺序一致
D. 相同，但其元素的存储顺序可以与逻辑顺序不一致
解析：在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。
6.下列叙述中正确的是( )。(A)
A. 在栈中，栈顶指针的动态变化决定栈中元素的个数
B. 在循环队列中，队尾指针的动态变化决定队列的长度
C. 在循环链表中，头指针和链尾指针的动态变化决定链表的长度
D. 在线性链表中，头指针和链尾指针的动态变化决定链表的长度
解析：在栈中，通常用指针top来指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。
7.设栈的存储空间为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的位置。
8.下列处理中与队列有关的是( )。(B)
A. 二叉树的遍历
B. 操作系统中的作业调度
C. 执行程序中的过程调用
D. 执行程序中的循环控制
解析：队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有“先进先出”的特性，体现了“先来先服务”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。
9.下列叙述中正确的是( )。(A)
A. 循环队列是顺序存储结构
B. 循环队列是链式存储结构
C. 循环队列空的条件是队头指针与队尾指针相同
D. 循环队列的插入运算不会发生溢出现象
解析：循环队列是队列的一种顺序存储结构。在循环队列中，在队列满和队列为空时，队头指针与队尾指针均相同；当需要插入的数据大于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象。
10.循环队列的存储空间为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个元素。
11.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有( )。(B)
A. 节省存储空间
B. 插入与删除运算效率高
C. 便于查找
D. 排序时减少元素的比较次数
解析：线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。
12.下列叙述中正确的是( )。(B)
A. 节点中具有两个指针域的链表一定是二叉链表
B. 节点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C. 循环链表是循环队列的链式存储结构
D. 循环链表是非线性结构
解析：节点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。
13.下列叙
本文档预览：3600字符，共8084字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
