1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 24及答案与解析 一、选择题 1 下列叙述中正确的是 ( )。 （ A）所谓算法就是计算方法 （ B）程序可以作为算法的一种描述方法 （ C）算法设计只需考虑得到计算结果 （ D）算法设计可以忽略算法的运算时间 2 下列叙述中正确的是 ( )。 （ A）算法的时间复杂度与计算机的运行速度有关 （ B）算法的时间复杂度与运行算法时特定的输入有关 （ C）算法的时间复杂度与算法程序中的语句条数成正比 （ D）算法的时间复杂度与算法 程序编制者的水平有关 3 为了降低算法的空间复杂度，要求算法尽量采用原地工作 (in place)。
2、所谓原地工作是指 ( )。 （ 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）线性结构 （ B）循环队列 （ C）循环链表 （ D）非线性结构 5 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数 ( )。
3、 （ A）不同，但元素的存储顺序与逻辑顺序一致 （ B）不同，且其元素的存储顺序可以与逻辑顺序不一致 （ C）相同，元素的存储顺序与逻辑顺序一致 （ D）相同，但其元素的存储顺序可以与逻辑顺序不一致 6 下列叙述中正确的是 ( )。 （ A）在栈中，栈顶指针的动态变化决定栈中元素的个数 （ B）在循环队列中，队尾指针的动态变化 决定队列的长度 （ C）在循环链表中，头指针和链尾指针的动态变化决定链表的长度 （ D）在线性链表中，头指针和链尾指针的动态变化决定链表的长度 7 设栈的存储空间为 S(1： m)，初始状态为 top=m+1。经过一系列入栈与退栈操作后， top=m。现又在栈中退出一个
4、元素后，栈顶指针 top值为 ( )。 （ A） 0 （ B） m一 1 （ C） m+1 （ D）产生栈空错误 8 下列处理中与队列有关的是 ( )。 （ A）二叉树的遍历 （ B）操作系统中的作业调度 （ C）执行程序中的过程调用 （ D） 执行程序中的循环控制 9 下列叙述中正确的是 ( )。 （ A）循环队列是顺序存储结构 （ B）循环队列是链式存储结构 （ C）循环队列空的条件是队头指针与队尾指针相同 （ D）循环队列的插入运算不会发生溢出现象 10 循环队列的存储空间为 Q(1： 40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后， front=rea
5、r=15，此后又退出一个元素，则循环队列中的元素个数为 ( )。 （ A） 14 （ B） 15 （ C） 40 （ D） 39，或 0且产生下溢错误 11 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有 ( )。 （ A）节省存储空间 （ B）插入与删除运算效率高 （ C）便于查找 （ D）排序时减少元素的比较次数 12 下列叙述中正确的是 ( )。 （ A）结点中具有两个指针域的链表一定是二叉链表 （ B）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 （ C）循环链表是循环队列的链式存储结构 （ D）循环链表是非线性结构 13 下列叙述中正确的是 ( )。 （
6、 A）带链栈的栈底指针是随栈的操作而动态变化的 （ B）若带链队列的队头指针与队尾指针相同，则队列为空 （ C）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素 （ D）不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的 14 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=10， bottom=20。该栈中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 10 （ D）不确定 15 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后， front=10， real=5。该
7、队列中的元素个数为 ( )。 （ A） 4 （ B） 5 （ C） 6 （ D）不确定 16 某棵树中共有 25个结点，且只有度为 3的结点和叶子结点，其中叶子结点有 7个，则该树中度为 3的结点数为 ( )。 （ A） 6 （ B） 7 （ C） 8 （ D）不存在这样的树 17 深度为 7的二叉树共有 127个结点，则下列说法中错误的是 ( )。 （ A）该二叉树是满二叉树 （ B）该二叉树有一个度为 1的结点 （ C）该二叉树是完全二叉树 （ D）该二叉树有 64个叶子结点 18 某完全二叉树共有 256个结点，则该完全二叉树的深度为 ( )。 （ A） 7 （ B） 8 （ C） 9
8、（ D） 10 19 下列叙述中正确的是 ( )。 （ A）非完全二叉树可以采用顺序存储结构 （ B）有两个指针域的链表就是二叉链表 （ C）有的二叉树也能用顺序存储结构表示 （ D）顺序存储结构一定是线性结构 20 设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为 ( )。 （ A） JIHGFEDCBA （ B） DGHEBIJFCA （ C） GHIJDEFBCA （ D） ABCDEFGHIJ 21 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度 (根结点在第 1层 )为 ( )。 （ A） 2 （ B） 3
9、 （ C） 4 （ D） 5 22 某完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。该完全二叉树的前序序列为 ( )。 （ A） ABCDEFGH （ B） ABDHECFG （ C） HDBEAFCG （ D） HDEBFGCA 23 设二叉树中共有 15个结点，其中的结点值互不相同。如果该二叉 树的前序序列与中序序列相同，则该二叉树的深度为 ( )。 （ A） 4 （ B） 6 （ C） 15 （ D）不存在这样的二叉树 24 在长度为 n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平
10、均情况下需要比较的次数大约为 ( )。 （ A） n （ B） 3n 4 （ C） n 2 （ D） n 4 25 线性表的长度为 n。在最坏情况下，比较次数为 n一 1的算法是 ( )。 （ A）顺序查找 （ B）同时寻找最大项与最小项 （ C）寻找最大项 （ D）有序表的插入 26 在快速排序法中，每经过一次数据交换 (或移动 )后 ( )。 （ A）只能消除一个逆序 （ B）能消除多个逆序 （ C）不会产生新的逆序 （ D）消除的逆序个数一定比新产生的逆序个数多 27 下列各组排序法中，最坏情况下比较次数相同的是 ( )。 （ A）简单选择排序与堆排序 （ B）简单插入排序与希尔排序 （
11、 C）冒泡排序与快速排序 （ D）希尔排序与堆排序 28 在长度为 97的顺序有序表中作二分查找，最多需要的比较次数为 ( )。 （ A） 48 （ B） 96 （ C） 7 （ D） 6 国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 24答案与解析 一、选择题 1 【正确答案】 B 【试题解析】 算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的，算
12、法在实现时需要用具体的程序设计语言描述，所 以程序可以作为算法的一种描述方法。 【知识模块】 数据结构与算法 2 【正确答案】 B 【试题解析】 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。 【知识模块】 数据结构与算法 3 【正确答案】 D 【试题解析】 对于算法的空间复杂度，如果额外空间量相
13、对于问题规模 (即输入数据所占的存储空间 )来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。 【知识模块】 数据结构与算法 4 【正确答案】 A 【试题解析】 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D；二是 D上的关系，它反映了 D中各数据元素之间的前后件关系，通常记为 R。即一个数据结构可以表示成 B=(D， R)。其中 B表示数据结构。为了反映 D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设 a与 b是 D中的两个数据，则二元组 (a， b)表示 a是 b的前件， b是 a的后件。本题中 R中的根结点为 f，元素顺序为 faced
14、b ，满足线性结构的条件。 【知识模块】 数据结构与算法 5 【正确答案】 C 【试题解析】 在 线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。 【知识模块】 数据结构与算法 6 【正确答案】 A 【试题解析】 在栈中，通常用指针 top来指示栈顶的位置，用指针 bottom指向栈底。栈顶指针 top动态反应了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。 【 知识
15、模块】 数据结构与算法 7 【正确答案】 C 【试题解析】 栈的顺序存储空间为 S(1： m)，初始状态 top=m+1，所以这个栈是m在栈底 (也可理解为开口向下的栈 )。经过一系列入栈与退栈操作后 top=m，则栈中有 1个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到 m+1的位置。 【知识模块】 数据结构与算法 8 【正确答案】 B 【试题解析】 队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有 “先进先出 ”的特性，体现了 “先来先服务 ”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取
16、某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。 【知识模块】 数据结构与算法 9 【正确答案】 A 【试题解析】 循环队列是队列的一种顺序存储结构。在循环队列中，在队列满和队列为空时，队头指针与队尾指针均相同；当需要插入的数据大于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象。 【知识模块】 数据结构与算法 10 【正确答案】 D 【试题解析】 当 front=real=15时可知队列空或者队列满，此后又退出一个元素，如果之前队列为空，退出操作会产生错误，队列里有 0个元素；如果退出之前队列已满 (40个元素 )，执行退出后，队列里还有 39个元素。 【知识模块】 数
17、据结构与算法 11 【正确答案】 B 【试题解析】 线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。【知识模块】 数据结构与算法 12 【正确答案】 B 【试题解析】 结点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是 线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。 【知识模块】 数据结构与算法 13 【正确答案】 A 【试题解析】 由于带链栈利用的是计算机存储空间中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则
18、头指针与尾指针相同。 【知识模块】 数据结构与算法 14 【正确答案】 D 【试题解析】 带链的栈使用了链表来表示栈，而链表中的元素存储在不连续的地址中，因此 当 top=10， bottom=20时，不能确定栈中元素的个数。 【知识模块】 数据结构与算法 15 【正确答案】 D 【试题解析】 带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当 front=10， rear=5时，不能确定队列中元素的个数。 【知识模块】 数据结构与算法 16 【正确答案】 D 【试题解析】 根据题意，树中只有度为 3的结点和叶子结点 (7个 )，则度为 3的结点有 257=18个；又根
19、据树中的结点数 =树中所有结点的度之和 +1，设度为 3的结点 数为 n，则 3n+1=25，得 n=8。两种方式得到的度为 3的结点数不同，故不存在这样的树。 【知识模块】 数据结构与算法 17 【正确答案】 B 【试题解析】 满二叉树满足深度为 m的二叉树最多有 2m一 1个结点，本题中二叉树深度为 7且有 127个结点，满足 27一 1=127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第 k层上有 2k 1结点，则该二叉树的叶子结点数为 27 1=64个。满二叉树不存在度为 1的结点。 【知识模块】 数据结构与算法 18 【正确答案】 C 【试题解析】 根据完全二叉树的
20、性质：具有 n个结点的完全二叉树的深度为log2n+1。本题中完全二叉树共有 256个结点，则深度为 log2256+1=8+1=9。 【知识模块】 数据结构与算法 19 【正确答案】 C 【试题解析】 在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此 A项错误， c项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此 D项错误。双向链表也有两个指针域，因此 B项错误。 【知识模块】 数据结构与算法 20 【正确答案】 B 【试题解析】 二叉树的前序序列为 ABDEGHCFIJ，由于前序遍历首先访问根结
21、点，可以确定该二叉树的根结点是 A。再由中序序列为 DBGEHACIFJ，可以得到结点 D、 B、 G、 E、 H位于根结点的左子树上，结点 C、 I、 F、 J位于根结点的右子树上。由于中序遍历和后序遍历都是先遍历左子树，故本题后序遍历首先访问D结点；再由后序遍历是最后访问根结点，故本题后序遍历最后访问的结点是根结点 A。采用排除法可知，后续序列为 DGHEBIJFCA。 【知识模块】 数据结构与 算法 21 【正确答案】 C 【试题解析】 二叉树的前序序列为 ABCDEFG，则 A为根结点；中序序列为DCBAEFG，可知结点 D、 C、 B位于根结点的左子树上，结点 E、 F、 G位于根结
22、点的右子树上。另外，结点 B、 C、 D在前序序列和中序序列中顺序相反，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。故二叉树深度为 4。 【知识模块】 数据结构与算法 22 【正确答案】 B 【试题解析】 完全二叉树的特点是除最后一层外，每一层上 的结点数均达到最大值；在最后一层上只缺少右边的若干结点。根据这一特点，再根据题意输出序列为 ABCDEFGH，可以得到该二叉树的结构如下： 故此完全二叉树的前序序列为 ABDHECFG。 【知识模块】 数据结构与算法 23 【正确答案】 C 【试题解析】 在具有 n个结点的
23、二叉树中，如果各结点值互不相同，若该二叉树的前序序列与中序序列相同，则说明该二叉树只有右子树，左子树为空，二叉树的深度为 n；若该二叉树的后序序列与中序序列相同，则说明该二叉树只有左子树，右子树为空，二叉树的深度为 n。故本题中二叉 树的深度为 15。 【知识模块】 数据结构与算法 24 【正确答案】 B 【试题解析】 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为 n。这是找到元素的情况。如果没有找到元素，则要比较 n次。因此，平均需要比较：找到元素的情况 +未找到元素的情况 =(1+2+n) n +n 。 【知
24、识模块】 数据结构与算法 25 【正确答案】 C 【试题解析】 顺序查找要逐个查看所有元素，会比较 n次。在最坏情况 下，寻找最大项无论如何需要查看表中的所有元素， n个元素比较次数为 n1。同时寻找最大项和最小项，需要为判断较大值和较小值分别进行比较，会有更多的比较次数。有序表的插入最坏情况下是插入到表中的最后一个元素的后面位置，则会比较 n次。 【知识模块】 数据结构与算法 26 【正确答案】 B 【试题解析】 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序的思想是：从线性表中选取一个元素，设为 T，将线性表中后面小于 T的元素移
25、到前面，而前面大于 T的元素移到后面，结果就将线性表分成两部分 (称两个子表 )， T插入到其分割线的位置处，这个过程称为线性表的分割，然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较，可以实线通过一次交换而消除多个逆序，但由于均与 T(基准元素 )比较，也可能会产生新的逆序。 【知识模块】 数据结构与算法 27 【正确答案】 C 【试题解析】 对于长度为 n的线性表，最坏情况下查找或排序的次数如下表：【知识模块】 数据结构与算法 28 【正确答案】 C 【试题解析】 对于长度为 n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。本题中 n=97，最多需要的比较次数为 log297， 6 log297 7，故需要比较 7次。 【知识模块】 数据结构与算法
