1、国家二级 ACCESS机试选择题（公共基础知识）模拟试卷 2及答案与解析 一、选择题 1 下列叙述中正确的是 ( )。 （ A）所谓算法就是计算方法 （ B）程序可以作为算法的一种描述方法 （ C）算法设计只需考虑得到计算结果 （ D）算法设计可以忽略算法的运算时间 2 下列叙述中正确的是 ( )。 （ A）算法的复杂度包括时间复杂度与空间复杂度 （ B）算法的复杂度是指算法控制结构的复杂程度 （ C）算法的复杂度是指算法程序中指令的数量 （ D）算法的复杂度是指算法所处理的数据量 3 下列叙述中正确的是 ( )。 （ A）算法的时间复杂度与计算机的运行速度有关 （ B）算法的时间复杂度与运行
2、算法时特定的输入有关 （ C）算法的时间复杂度与算法程序中的语句条数成正比 （ D）算法的时间复杂度与算法程序编制者的水平有关 4 下列叙述中正确的是 ( )。 （ A）算法的空间复杂度是指算法程序中指令的条数 （ B）压缩数据存储空间不会降低算法的空间复杂度 （ C）算法的空间复杂度与算法所处理的数据存储空间有关 （ D）算法的空间复杂度是指算法程序控制结构的复杂程度 5 为了 降低算法的空间复杂度，要求算法尽量采用原地工作 (in place)。所谓原地工作是指 ( )。 （ A）执行算法时不使用额外空间 （ B）执行算法时不使用任何存储空间 （ C）执行算法时所使用的额外空间随算法所处理
3、的数据空间大小的变化而变化 （ D）执行算法时所使用的额外空间固定 (即不随算法所处理的数据空间大小的变化而变化 ) 6 下列叙述中正确的是 ( )。 （ A）非线性结构可以为空 （ B）只有一个根结点和一个叶子结点的必定是线性结构 （ C）只有一个根结点的必定是线性结构或二叉树 （ D）没有根结点的一定是非线性结构 7 设数据结构 B=(D， R)，其中 D=a， b， c， d， e， f R=(f， a)， (d， b)， (e， d)， (c， e)， (a， c) 该数据结构为 ( )。 （ A）线性结构 （ B）循环队列 （ C）循环链表 （ D）非线性结构 8 下列叙述中正确的是
4、 ( )。 （ A）矩阵是非线性结构 （ B）数组是长度固定的线性表 （ C）对线性表只能作插入与删除运算 （ D）线性表中各元素的数据类型可以不同 9 在线性表的顺序存储结构中，其存储空间连续，各 个元素所占的字节数 ( )。 （ A）不同，但元素的存储顺序与逻辑顺序一致 （ B）不同，且其元素的存储顺序可以与逻辑顺序不一致 （ C）相同，元素的存储顺序与逻辑顺序一致 （ D）相同，但其元素的存储顺序可以与逻辑顺序不一致 10 下列叙述中正确的是 ( )。 （ A）能采用顺序存储的必定是线性结构 （ B）所有的线性结构都可以采用顺序存储结构 （ C）具有两个以上指针的链表必定是非线性结构 （
5、 D）循环队列是队列的链式存储结构 11 下列叙述中正确的是 ( )。 （ A）在栈中 ，栈顶指针的动态变化决定栈中元素的个数 （ B）在循环队列中，队尾指针的动态变化决定队列的长度 （ C）在循环链表中，头指针和链尾指针的动态变化决定链表的长度 （ D）在线性链表中，头指针和链尾指针的动态变化决定链表的长度 12 设栈的顺序存储空间为 S(1： m)，初始状态为 top =0。现经过一系列正常的入栈与退栈操作后， top=m+1，则栈中的元素个数为 ( )。 （ A） 0 （ B） m （ C）不可能 （ D） m+1 13 设栈的存储空间为 S(1： m)，初始状态为 top=m+1。经过
6、一系列 入栈与退栈操作后， top=m。现又在栈中退出一个元素后，栈顶指针 top值为 ( )。 （ A） 0 （ B） m 1 （ C） m+1 （ D）产生栈空错误 14 设栈的存储空间为 S(1： 50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后， top=20，则栈中的元素个数为 ( )。 （ A） 31 （ B） 30 （ C） 21 （ D） 20 15 下列处理中与队列有关的是 ( )。 （ A）二叉树的遍历 （ B）操作系统中的作业调度 （ C）执行程序中的过程调用 （ D）执行 程序中的循环控制 16 设有栈 S和队列 Q，初始状态均为空。首先依次将 A，
7、 B， C， D， E， F入栈，然后从栈中退出三个元素依次入队，再将 X， Y， Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为 ( )。 （ A） DEFXYZABC （ B） FEDZYXCBA （ C） FEDXYZCBA （ D） DEFZYXABC 17 下列叙述中正确的是 ( )。 （ A）循环队列是顺序存储结构 （ B）循环队列是链式存储结构 （ C）循环队列空的条件是队头指针与队尾指针 相同 （ D）循环队列的插入运算不会发生溢出现象 18 设循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。现经过一系列入队
8、与退队操作后， front=rear=l，此后又正常地插入了两个元素。最后该队列中的元素个数为 ( )。 （ A） 3 （ B） 1 （ C） 2 （ D） 52 19 循环队列的存储空间为 Q(1： 40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后， front=rear=15，此后又退出一个元素，则循环队列中的元素个数为 ( )。 （ A） 14 （ B） 15 （ C） 40 （ D） 39，或 0且产生下溢错误 20 设循环队列的存储空间为 Q(1： m)，初始状态为空。现经过一系列正常的入队与退队操作后， front=m， rear： m 1，此后从该
9、循环队列中删除一个元素，则队列中的元素个数为 ( )。 （ A） m 1 （ B） m 2 （ C） 0 （ D） 1 21 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有 ( )。 （ A）节省存储空间 （ B）插入与删除运算效率高 （ C）便于查找 （ D）排序时 减少元素的比较次数 22 在线性表的链式存储结构中，其存储空间一般是不连续的，并且 ( )。 （ A）前件结点的存储序号小于后件结点的存储序号 （ B）前件结点的存储序号大于后件结点的存储序号 （ C）前件结点的存储序号可以小于也可以大于后件结点的存储序号 （ D）以上三种说法均不正确 23 下列叙述中正确的是 (
10、 )。 （ A）结点中具有两个指针域的链表一定是二叉链表 （ B）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 （ C）循环链表是循环队列的链式存储结构 （ D）循环链表是非线性结构 24 带链的栈与顺序存储的栈相比，其优点是 ( )。 （ A）入栈与退栈操作方便 （ B）可以省略栈底指针 （ C）入栈操作时不会受栈存储空间的限制而发生溢出 （ D）所占存储空间相同 25 由关系 R1和 R2得到关系 R3的操作是 ( )。（ A）笛卡尔积 （ B）并 （ C）等值连接 （ D）交 26 在进行逻辑设计时，将 E R图中实体之间联系转换为关系数据库的 ( )。 （ A）元组 （
11、 B）关系 （ C）属性 （ D）属性的值域 27 定义学生、教师和 课程的关系模式： S(S#， Sn， Sd， Sa)(属性分别为学号、姓名、所在系、年龄 )； C(C#， Cn， P#)(属性分别为课程号、课程名、先修课 )；SC(S#， C#， G)(属性分别为学号、课程号和成绩 )。则该关系为 ( )。 （ A） BCNF范式 （ B）第一范式 （ C）第二范式 （ D）第三范式 国家二级 ACCESS机试选择题（公共基础知识）模拟试卷 2答案与解析 一、选择题 1 【正确答案】 B 【试题解析】 算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序 。算法
12、设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。 【知识模块】 公共基础知识 2 【正确答案】 A 【试题解析】 算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算 法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。 【知识模块】 公共基础知识 3
13、 【正确答案】 B 【试题解析】 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。 【知识模块】 公共基础知识 4 【正确答案】 C 【试题解析】 算法的空间复杂度是指算法在执行过程中所需要的内存空间。算法执行期间所需的存储空间包括 3个部分：输人数据所占的存储空间；程序本身所占的存储空间；算法执行
14、过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通产采用压缩存储技术，以便尽量减少不必要的额外空间。 【知识模块】 公共基础知识 5 【正确答案】 D 【试题解析】 对于算法的空间复杂度，如果额外空间量相对于问题规模 (即输人数据所占的存储空间 )来 说是常数，即额外空问量不随问题规模的变化而变化，则称该算法是原地工作的。 【知识模块】 公共基础知识 6 【正确答案】 A 【试题解析】 如果一个非空的数据结构满足下列两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性
15、结构和非线性结构都可以是空的数据结构。树只有一个根结点，但不论有几个叶子结点，树都是非线性结构。 【知识模块】 公共基础知识 7 【正确答案】 A 【试题 解析】 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D;二是 D上的关系，它反映了 D中各数据元素之间的前后件关系，通常记为 R。即一个数据结构可以表示成 B=(D， R)。其中 B表示数据结构。为了反映 D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设 a与 b是 D中的两个数据，则二元组 (a， b)表示 a是 b的前件， b是 a的后件。本题中 R中的根结点为 f，元素顺序为 facedb ，满足线性结构的条
16、件。 【知识模块】 公共基础知识 8 【正确答案】 B 【试题解析】 矩阵也是线性表 ，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。 【知识模块】 公共基础知识 9 【正确答案】 C 【试题解析】 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。 【知识模块】 公共基础知识 10 【正确答案】 B 【试题解析】 所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存 (按 层次依次存放到数据元素中 )，
17、但完全二叉树属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。 【知识模块】 公共基础知识 11 【正确答案】 A 【试题解析】 在栈中，通常用指针 top来指示栈顶的位置，用指针 bottom指向栈底。栈顶指针 top动态反应了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针 无法决定链表长度。 【知识模块】 公共基础知识 12 【正确答案】 C 【试题解析】 栈为空时，栈顶指针 top =0，经过
18、入栈和退栈运算，指针始终指向栈顶元素。初始状态为 top =0，当栈满 top=m，无法继续入栈， top值不可能为m+l。 【知识模块】 公共基础知识 13 【正确答案】 C 【试题解析】 栈的顺序存储空间为 S(1： m)，初始状态 top=m+1，所以这个栈是m在栈底 (也可理解为开口向下的栈 )。经过一系列入栈与退栈操作后 top=m，则栈中有 1个元素，若现在又退出 一个元素，那么栈顶指针下移一位，回到 m+1的位置。 【知识模块】 公共基础知识 14 【正确答案】 A 【试题解析】 栈的初始状态 top =51，故本栈是 51在栈底，入栈时栈顶指针是减操作 (top=top 1)，
19、退栈时栈顶指针是加操作 ( top=top +1)。当 top=20时，元素存储在 (20： 50)空间中，因此共有 50 20 +1=31个元素。 【知识模块】 公共基础知识 15 【正确答案】 B 【试题解析】 队列是指允许在一端进行插入，而在另一端进行删除的线性表。 由于最先进入队列的元素将最先出队，所以队列具有 “先进先出 ”的特性，体现了 “先来先服务 ”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。 【知识模块】 公共基础知识 16 【正确答案】 B 【试题解析】 栈是一种特殊的线性表
20、，它所有的插入与删除都限定在表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将 A， B，C， D， E， F入栈后，栈中元素为 ABCDEF，退出三个元素入队，队 列元素为FED，将 X， Y， Z入栈后栈中元素为 ABCXYZ，退栈全部人队后，队列元素为FEDZYXCBA。 【知识模块】 公共基础知识 17 【正确答案】 A 【试题解析】 循环队列是队列的一种顺序存储结构。在循环队列中，在队列满和队列为空时，队头指针与队尾指针均相同；当需要插入的数据大于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象。 【知识模块】 公共基础知识 18 【正确答案】 C
21、【试题解析】 由初始状态为 front=rear=50可知此时循环队列为空。经过 一系列正常的入队和退队操作，由 front=rear=1可知队列空或者队列满，此后又可以正常地插入了两个元素，说明插入前队列为空，则插入后队列元素个数为 2。 【知识模块】 公共基础知识 19 【正确答案】 D 【试题解析】 当 front=rear=15时可知队列空或者队列满，此后又退出一个元素，如果之前队列为空，退出操作会产生错误，队列里有 0个元素；如果退出之前队列已满 (40个元素 )，执行退出后，队列里还有 39个元素。 【知识模块】 公共基础知识 20 【正确答案】 B 【试题 解析】 在循环队列中，
22、如果 rear front 0，则队列中的元素个数为rear front个；如果 rear front 0，则队列中的元素个数为 rear front+m。该题中 m1 m，即 rear front 0，则该循环队列中的元素个数为(m 1) m+m=m1。此后从该循环队列中删除一个元素，则队列中的元素个数为 m 1 1 =m2。 【知识模块】 公共基础知识 21 【正确答案】 B 【试题解析】 线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为 链表，两者的优缺点如下表所示。【知识模块】 公共基础知识 22 【正确答案】 C 【试题解析】 在线性表的链式存储结构中，各数据结点的存储序号是
23、不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，因此前件结点的存储序号与后件结点的存储序号之间不存在大小关系。 【知识模块】 公共基础知识 23 【正确答案】 B 【试题解析】 结点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线 性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。 【知识模块】 公共基础知识 24 【正确答案】 C 【试题解析】 带链的栈就是用一个线性链表来表示的栈，线性链表不受存储空间大小的限制，因此入栈操作时不会受栈存储空间的限制而发生溢出 (不需考虑栈满的问题 )。 【知识模块】 公共基础知识 25 【正确答案】 C 【试题解析】 关系 R1和关系 R2没有同名列，但关系 R1中的 B列与关系 R2中的 D列有相等值，因此属于等值连接。 【知识模块】 公共基础知识 26 【 正确答案】 B 【试题解析】 ER模型与关系模型间的转换关系如下表所示。【知识模块】 公共基础知识 27 【正确答案】 D 【试题解析】 本题每个关系中每个非主属性既不部分依赖于主键也不传递依赖于主键，满足第三范式。表 C的主键既可以是 “课程号 ”，也可以是 “课程名 ”， “课程号 ”和 “课程名 ”也可相互决定，所以不满足 BCF范式。 【知识模块】 公共基础知识
