[计算机类试卷]国家二级MS Office高级应用机试（选择题）模拟试卷88及答案与解析.doc

《[计算机类试卷]国家二级MS Office高级应用机试（选择题）模拟试卷88及答案与解析.doc》由会员分享，可在线阅读，更多相关《[计算机类试卷]国家二级MS Office高级应用机试（选择题）模拟试卷88及答案与解析.doc（18页珍藏版）》请在麦多课文档分享上搜索。

1、国家二级 MS Office高级应用机试（选择题）模拟试卷 88及答案与解析 一、选择题 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=1，此后又正常地插入了两个元素。最后该队列中的元素个数为 ( )。 （ 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 下列叙述中正确的是 ( )。 （ A）带链栈的栈底指针是随栈的操作而动态变化的 （ B）若带链队列的队头指针与队尾指针相同，则队列为空 （ C）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元

11、素 （ D）不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的 26 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=bottom=20。该栈中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 20 （ D）不确定 27 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=10， bottom=20。该栈中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 10 （ D）不确定 28 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队

12、操作后， front=rear=10。该队列中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 1或 0 （ D）不确定 29 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后， front=10， rear=5。该队列中的元素个数为 ( )。 （ A） 4 （ B） 5 （ C） 6 （ D）不确定 30 下列叙述中错误的是 ( )。 （ A）循环链表中有一个表头结点 （ B）循环链表是循环队列的存储结构 （ C）循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 （ D）循环 链表实现了空表与非空表运算的统一 31 某棵树中共

13、有 25个结点，且只有度为 3的结点和叶子结点，其中叶子结点有 7个，则该树中度为 3的结点数为 ( )。 （ A） 6 （ B） 7 （ C） 8 （ D）不存在这样的树 32 度为 3的一棵树共有 30个结点，其中度为 3， 1的结点个数分别为 3， 4。则该树中的叶子结点数为 ( )。 （ A） 14 （ B） 15 （ C） 16 （ D）不可能有这样的树 33 深度为 7的二叉树共有 127个结点，则下列说法中错误的是 ( )。 （ A）该二叉树是满二叉树 （ B）该二叉树有一个度为 1的结点 （ C）该二叉树是完全二叉树 （ D）该二叉树有 64个叶子结点 34 深度为 5的完全二

14、叉树的结点数不可能是 ( )。 （ A） 15 （ B） 16 （ C） 17 （ D） 18 35 某完全二叉树共有 256个结点，则该完全二叉树的深度为 ( )。 （ A） 7 （ B） 8 （ C） 9 （ D） 10 36 在具有 2n个结点的完全二叉树中，叶子结点个数为 ( )。 （ A） n （ B） n+1 （ C） n-1 （ D） n 2 国家二级 MS Office高级应 用机试（选择题）模拟试卷 88答案与解析 一、选择题 1 【正确答案】 B 【试题解析】 算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有

15、穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的，。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。 2 【正确答案】 A 【试题解析】 算法复杂度 是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。 3 【正确答案】 B 【试题解析】 为了能够比较客观地反映出一个算法的效率，在度量一个

16、算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。 4 【正确答案】 C 【试题解析】 算法的空间复杂度是指算法在执行过程中所需要的内存空间。算法执行期间所需的存储空间包括 3个部分：输入 数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通产采用压缩存储技术，以便尽量减少不必要

17、的额外空间。 5 【正确答案】 D 【试题解析】 对于算法的空间复杂度，如果额外空间量相对于问题规模 (即输人数据所占的存储空间 )来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。 6 【正确答案】 A 【试题解析】 如果一个非空的数据结构满足下列两个条件： 有且只有一个根结点； 每一个结点最多有一个前件， 也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都可以是空的数据结构。树只有一个根结点，但不论有几个叶子结点，树都是非线性结构。 7 【正确答案】 A 【试题解析】 数据的逻辑结构有两个要素：一是数

18、据元素的集合，通常记为 D；二是 D上的关系，它反映了 D中各数据元素之间的前后件关系，通常记为 R。即一个数据结构可以表示成 B=(D， R)。其中 B表示数据结构。为了反映 D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设 a与 b是 D中的 两个数据，则二元组 (a， b)表示 a是 b的前件， b是 a的后件。本题中 R中的根结点为 f，元素顺序为 facedb ，满足线性结构的条件。 8 【正确答案】 B 【试题解析】 矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作

19、。 9 【正确答案】 C 【试题解析】 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。 10 【正确答 案】 B 【试题解析】 所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存 (按层次依次存放到数据元素中 )，但完全二叉树不属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。 11 【正确答案】 A 【试题解析】 在栈中，通常用指针 top来指示栈顶的位置，用指针 bottom指向栈底。栈顶指针 top动态反应了栈中元素的变化情况。在循环队列中，队

20、头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据结点 的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。 12 【正确答案】 C 【试题解析】 栈为空时，栈顶指针 top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为 top=0，当栈满 top=m，无法继续入栈， top值不可能为m+1。 13 【正确答案】 C 【试题解析】 栈的顺序存储空间为 s(1： m)，初始状态 top=m+1，所以这个栈是m在栈底 (也可理解为开口向下的栈 )。经过一系列入栈与退栈操作后 top=m，则 栈中有 1个元素

21、，若现在又退出一个元素，那么栈顶指针下移一位，回到 m+1的位置。 14 【正确答案】 A 【试题解析】 栈的初始状态 top=51，故本栈是 51在栈底，入栈时栈顶指针是减操作 (top=top一 1)，退栈时栈顶指针是加操作 (top=top+1)。当 top=20时，元素存储在 (20： 50)空间中，因此共有 50一 20+1=31个元素。 15 【正确答案】 B 【试题解析】 队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进人队列的元素将最先出队，所以队列具有 “先进先 出 ”的特性，体现了 “先来先服务 ”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算

22、法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。 16 【正确答案】 B 【试题解析】 栈是一种特殊的线性表，它所有的插人与删除都限定在表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将 A， B，C， D， E， F入栈后，栈中元素为 ABCDEF，退出三个元素人队，队列元素为FED，将 X， Y， Z入栈后栈中元素为 ABCXYZ，退栈全部入队后，队列元素为FEDZYXCBA。 17 【正确答案】 A 【试题解析】 循环队列是队列的一种顺序存储结构。在循环队列中，在队列满和队列为空时，队头指针与队尾指针均相同；当需要插入的数据大

23、于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象。 18 【正确答案】 C 【试题解析】 由初始状态为 front=rear=50可知此时循环队列为空。经过一系列正常的入队和退队操作，由 front=rear=1可知队列空或者队列满，此后又可以正常地插入了两个元素，说明插入前队列为空，则插入后队列元素个数为 2。 19 【正确答案】 D 【试题解析】 当 front=rear=15时可知队列空或者队列满，此后又退出一个元素，如果之前队列为空，退出操作会产生错误，队列里有 0个元素；如果退出之前队列已满 (40个元素 )，执行退出后，队列里还有 39个元素。 20 【正确答案】 B

24、【试题解析】 在循环队列中，如果 rearfront 0，则队列中的元素个数为 rear一 front个；如果 rear一 front 0，则队列中的元素个数为 rearfront+m。该题中 m1 m，即 rearfront 0，则该循环 队列中的元素个数为 (m1)一m+m=m一 1。此后从该循环队列中删除一个元素，则队列中的元素个数为 m一11=m一 2。 21 【正确答案】 B 【试题解析】 线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。22 【正确答案】 C 【试题解析】 在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存

25、储空间中的位置关系与逻辑关系也不一致，因此前件结点的存储序号与后件结点的存储序号之间不存在大小关系。 23 【正确答案】 B 【 试题解析】 结点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。 24 【正确答案】 C 【试题解析】 带链的栈就是用一个线性链表来表示的栈，线性链表不受存储空间大小的限制，因此入栈操作时不会受栈存储空间的限制而发生溢出 (不需考虑栈满的问题 )。 25 【正确答案】 A 【试题解析】 由于带链栈利用的是计算机存储空间

26、中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。 26 【正确答案】 B 【试题解析】 带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为 NULL；栈中只有一个元素时，头指针和尾指针都指向这个元素。 27 【正确答案】 D 【试题解析】 带链的栈使用了链表来表示栈，而链表中的元素存储在不连续的地址中，因此当 top=10， bottom=20时，不能确定栈中元素的个数。 28 【正确答案】 B 【 试题解析】 带链队列空时，头指针和尾指针都为 NULL；队列中只有一个元素时，头指针

27、和尾指针都指向这个元素。 29 【正确答案】 D 【试题解析】 带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当 front=10， rear=5时，不能确定队列中元素的个数。 30 【正确答案】 B 【试题解析】 循环链表是指在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由 NULL改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是 队列的一种顺序存储结构。 31 【正确答案】 D 【试题解析】 根据题意，树中只有度为 3的结点和叶子结点 (7个 )，则度为 3的结点有 257=18个；又根据树中的结点数 =树中

28、所有结点的度之和 +1，设度为 3的结点数为 n，则 3n+1=25，得 n=8。两种方式得到的度为 3的结点数不同，故不存在这样的树。 32 【正确答案】 B 【试题解析】 设叶子结点数为 n，则度为 2的结点数为 30一 34一 n=23一 n，根据树中的结点数 =树中所有结点的度之和 +1，得 33+2(23一n)+14+0n+1=30，则 n=15。 33 【正确答案】 B 【试题解析】 满二叉树满足深度为 m的二叉树最多有 2m一 1个结点，本题中二叉树深度为 7且有 127个结点，满足 27一 1=127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第 k层上有 2k

29、-1结点，则该二叉树的叶子结点数为 27-1=64个。满二叉树不存在度为 1的结点。 34 【正确答案】 A 【试题解析】 设完全二叉树的结点数为 n，根据深度为 k的二叉树至多有 2k一 1个结点，再根据完全二叉树的定义可知， 2k-1一 1 n2k一 1。本题中完全二叉树的深度为 5，则 25-1一 1 n25一 1， 15 n31。因此，结点数不能为 15。 35 【正确答案】 C 【试题解析】 根据完全二叉树的性质：具有 n个结点的完全二叉树的深度为log2n+1。本题中完全二叉树共有 256个结点，则深度为 log2256+1=8+1=9。 36 【正确答案】 A 【试题解析】 由二叉树的定义可知，树中必定存在度为 O的结点和度为 2的结点，设度为 0结点有 a个，根据度为 0的结点 (即叶子结点 )总比度为 2的结点多一个，得度为 2的结点有 a一 1个。再根据完全二叉树的定义 ，度为 1的结点有 0个或 1个，假设度 1结点为 0个， a+0+a一 1=2n，得 2a=2n1,由于结点个数必须为整数，假设不成立；当度为 1的结点为 1个时， a+1+a一 1=2n，得 a=n，即叶子结点个数为 n。