国家二级MS Office高级应用机试（数据结构与算法）模拟试卷41
选择题
1.下列叙述中正确的是( )。(B)
A. 算法的时间复杂度与计算机的运行速度有关
B. 算法的时间复杂度与运行算法时特定的输入有关
C. 算法的时间复杂度与算法程序中的语句条数成正比
D. 算法的时间复杂度与算法程序编制者的水平有关
解析：为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。
2.下列叙述中正确的是( )。(A)
A. 数据的存储结构会影响算法的效率
B. 算法设计只需考虑结果的可靠性
C. 算法复杂度是指算法控制结构的复杂程度
D. 算法复杂度是用算法中指令的条数来度量的
解析：采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构很重要。
3.设数据集合为D={1，2，3，4，5}。下列数据结构B=(D，R)中为非线性结构的是( )。
C
解析：A项中，R={(2，5)，(5，4)，(3，1)，(4，3)}，2为根节点，元素顺序为2→5→4→3→1，属于线性结构；同理，B项1为根节点，元素顺序为1→2→3→4→5，D项5为跟节点，元素顺序为5→4→3→2→1，均为线性结构。C项中，元素3有两个前件，属于非线性结构。
4.下列叙述中正确的是( )。(B)
A. 能采用顺序存储的必定是线性结构
B. 所有的线性结构都可以采用顺序存储结构
C. 具有两个以上指针的链表必定是非线性结构
D. 循环队列是队列的链式存储结构
解析：所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存(按层次依次存放到数据元素中)，但完全二叉树属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。
5.设栈的存储空间为S(1：m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=1。现又要将一个元素进栈，栈顶指针top值变为( )。(B)
A. 0
B. 发生栈满的错误
C. m
D. 2
解析：栈的初始状态为top=m+1，说明栈空时top=m+1，入栈时栈顶指针是减操作(top=top-1)，退栈时栈顶指针是加操作(top=top+1)。栈满时top=1，说明栈中不能再进行入栈操作(“上溢”错误)。
6.下列处理中与队列有关的是( )。(B)
A. 二又树的遍历
B. 操作系统中的作业调度
C. 执行程序中的过程调用
D. 执行程序中的循环控制
解析：队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有“先进先出”的特性，体现了“先来先服务”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。
7.循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为( )。(A)
A. 1，或50且产生上溢错误
B. 51
C. 26
D. 2
解析：在循环队列运转起来后，当front=rear=25时可知队列空或者队列满，此后又插入了一个元素，如果之前队列为空，插入操作之后队列里只有一个元素；如果插入之前队列已满(50个元素)，执行插入则会产生溢出错误。
8.设循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为( )。(C)
A. 3
B. 1
C. 2
D. 52
解析：由初始状态为front=rear=50可知此时循环队列为空。经过一系列正常的入队和退队操作，由front=rear=1可知队列空或者队列满，此后又可以正常地插入了两个元素，说明插入前队列为空，则插入后队列元素个数为2。
9.在线性表的链式存储结构中，其存储空间一般是不连续的，并且( )。(C)
A. 前件节点的存储序号小于后件节点的存储序号
B. 前件节点的存储序号大于后件节点的存储序号
C. 前件节点的存储序号可以小于也可以大于后件节点的存储序号
D. 以上三种说法均不正确
解析：在线性表的链式存储结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致，因此前件节点的存储序号与后件节点的存储序号之间不存在大小关系。
10.下列结构中属于线性结构链式存储的是( )。(A)
A. 双向链表
B. 循环队列
C. 二叉链表
D. 二维数组
解析：双向链表也叫双链表，是链表(采用链式存储结构)的一种，它的每个数据节点中都有两个指针，分别指向直接后继和直接前驱。循环队列是队列的一种顺序存储结构。二叉链表和二维数组属于非线性结构。
11.某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为( )。(B)
A. 0
B. 1
C. 20
D. 不确定
解析：带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个节点。栈为空时，头指针和尾指针都为NULL；栈中只有一个元素时，头指针和尾指针都指向这个元素。
12.从表中任何一个节点位置出发就可以不重复地访问到表中其他所有节点的链表是( )。(A)
A. 循环链表
B. 双向链表
C. 单向链表
D. 二叉链表
解析：在循环链表中，所有节点的指针构成了一个环状链，只要指出表中任何一个节点的位置，就可以从它出发不重复地访问到表中其他所有节点。
13.某棵树的度为4，且度为4，3，2，1的节点个数分别为1，2，3，4，则该树中的叶子节点数为( )。(A)
A. 11
B. 9
C. 10
D. 8
解析：根据树中的节点数=树中所有节点的度之和+1，设叶子节点数为n，得4×1+3×2+2×3+1×4+n×0+1=21，则n：21-1-2+3-4=11。
14.某二叉树共有845个节点，其中叶子节点有45个，则度为1的节点数为( )。(C)
A. 400
B. 754
C. 756
D. 不确定
解析：叶子节点有45个，根据在二叉树中度为0的节点(叶子节点)总比度为2的节点多一个，则度为2的节点数为44个，因此度为1的节点数为845-45-44=756个。
15.某二叉树
本文档预览：3600字符，共6473字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
