国家二级ACCESS机试（选择题）模拟试卷326
选择题
1.下列叙述中正确的是( )。(B)
A. 所谓算法就是计算方法
B. 程序可以作为算法的一种描述方法
C. 算法设计只需考虑得到计算结果
D. 算法设计可以忽略算法的运算时间
解析：算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。
2.下列叙述中正确的是( )。(A)
A. 算法的复杂度包括时间复杂度与空间复杂度
B. 算法的复杂度是指算法控制结构的复杂程度
C. 算法的复杂度是指算法程序中指令的数量
D. 算法的复杂度是指算法所处理的数据量
解析：算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。
3.下列叙述中正确的是( )。(B)
A. 算法的时间复杂度与计算机的运行速度有关
B. 算法的时间复杂度与运行算法时特定的输入有关
C. 算法的时间复杂度与算法程序中的语句条数成正比
D. 算法的时间复杂度与算法程序编制者的水平有关
解析：为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。
4.下列叙述中正确的是( )。(C)
A. 算法的空间复杂度是指算法程序中指令的条数
B. 压缩数据存储空间不会降低算法的空间复杂度
C. 算法的空间复杂度与算法所处理的数据存储空间有关
D. 算法的空间复杂度是指算法程序控制结构的复杂程度
解析：算法的空间复杂度是指算法在执行过程中所需要的内存空间。算法执行期间所需的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通产采用压缩存储技术，以便尽量减少不必要的额外空间。
5.为了降低算法的空间复杂度，要求算法尽量采用原地工作(in place)。所谓原地工作是指( )。(D)
A. 执行算法时不使用额外空间
B. 执行算法时不使用任何存储空间
C. 执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化
D. 执行算法时所使用的额外空间固定(即不随算法所处理的数据空间大小的变化而变化)
解析：对于算法的空间复杂度，如果额外空间量相对于问题规模(即输入数据所占的存储空间)来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。
6.下列叙述中正确的是( )。(A)
A. 非线性结构可以为空
B. 只有一个根节点和一个叶子节点的必定是线性结构
C. 只有一个根节点的必定是线性结构或–X树
D. 没有根节点的一定是非线性结构
解析：如果一个非空的数据结构满足下列两个条件：①有且只有一个根节点；②每一个节点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都可以是空的数据结构。树只有一个根节点，但不论有几个叶子节点，树都是非线性结构。
7.设数据结构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，满足线性结构的条件。
8.下列叙述中正确的是( )。(B)
A. 矩阵是非线性结构
B. 数组是长度固定的线性表
C. 对线性表只能作插入与删除运算
D. 线性表中各元素的数据类型可以不同
解析：矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。
9.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数( )。(C)
A. 不同，但元素的存储顺序与逻辑顺序一致
B. 不同，且其元素的存储顺序可以与逻辑顺序不一致
C. 相同，元素的存储顺序与逻辑顺序一致
D. 相同，但其元素的存储顺序可以与逻辑顺序不一致
解析：在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。
10.下列叙述中正确的是( )。(B)
A. 能采用顺序存储的必定是线性结构
B. 所有的线性结构都可以采用顺序存储结构
C. 具有两个以上指针的链表必定是非线性结构
D. 循环队列是队列的链式存储结构
解析：所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存(按层次依次存放到数据元素中)，但完全二叉树属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。
11.下列叙述中正确的是( )。(A)
A. 在栈中，栈顶指针的动态变化决定栈中元素的个数
B. 在循环队列中，队尾指针的动态变化决定队列的长度
C. 在循环链表中，头指针和链尾指针的动态变化决定链表的长度
D. 在线性链表中，头指针和链尾指针的动态变化决定链表的长度
解析：在栈中，通常用指针top来指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。
12.设栈的顺序存储空间为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+l。
13.设栈的存储空间为s(1：m
本文档预览：3600字符，共8024字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
