1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 9及答案与解析 一、选择题 1 在最坏情况下 （ A）快速排序的时间复杂度比冒泡排序的时间复杂度要小 （ B）快速排序的时间复杂度比希尔排序的时间复杂度要小 （ C）希尔排序的时间复杂度比直接插入排序的时间复杂度要小 （ D）快速排序的时间复杂度与希尔排序的时间复杂度是一样的 2 在深度为 7的满二叉树中，度为 2的结点个数为 （ A） 64 （ B） 63 （ C） 32 （ D） 31 3 设栈的顺序存储空间为 S(1： m)，初始状态为 top=m+1。现经过一系列入栈与退栈运算后， top=20，则当前栈中的元素个数为 （ A
2、） 30 （ B） 20 （ C） m-19 （ D） m-20 4 算法空间复杂度的度量方法是 （ A）算法程序的长度 （ B）算法所处理的数据量 （ C）执行算法所需要的工作单元 （ D）执行算法所需要的存储空间 5 设循环队列为 Q(1： m)，其初始状态为 front=reax=m。经过一系列入队与退队运算后， front=15， rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为 （ A） 4 （ B） 6 （ C） m-5 （ D） m-6 6 下列叙述中正确的是 （ A）循环队列属于队列的链式存储结构 （ B）双向链表是二叉树的链式存储结构 （ C）非
3、线性结构只能采用链式存储结构 （ D）有的非线性结构也可以采用顺序存储结构 7 某二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为 （ A） n+1 （ B） n-1 （ C） 2n （ D） n 2 8 下列叙述中错误的是 （ A）算法的时间复杂度与算法所处理数据的存储结构有直接关系 （ B）算法的空间复杂度与算法所处理数据的存储结构有直接关系 （ C）算法的时间复杂度与空间复杂度有直接关系 （ D）算法的时间复杂度与空间复杂度没有必然的联系 9 设栈的顺序存储空间为 S(0： 49)，栈底指针 bottom=49，栈顶指针 top=30(指向栈顶元素 )。则栈中的元素个数为 （ A
4、） 30 （ B） 29 （ C） 20 （ D） 19 10 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度 (根结点在第 1层 )为 （ A） 2 （ B） 3 （ C） 4 （ D） 5 11 下列叙述中正确的是 （ A）存储空间连续的数据结构一定是线性结构 （ B）存储空间不连续的数据结构一定是非线性结构 （ C）没有根结点的非空数据结构一定是线性结构 （ D）具有两个根结点的数据结构一定是非线性结构 12 下列叙述中正确的是 （ A）带链队列的存储空间可以不连续，但队头指针必须大于队尾指针 （ B）带链队列的存储空间可以不连续，但队头指针必须小于队
5、尾指针 （ C）带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针 （ D）以上三项都错误 13 设循环队列为 Q(1： m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后 ， front=20， rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为 （ A） 5 （ B） 6 （ C） m-5 （ D） m-6 14 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为 （ A） EFGDCBA （ B） DCBEFGA （ C） BCDGFEA （ D） DCBGFEA 15 下列叙述中正确
6、的是 （ A）在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构 （ B）在链表中，如果有两个结点的同一个指针域的值相等，则该链表 一定是非线性结构 （ C）在链表中，如果每个结点有两个指针域，则该链表一定是线性结构 （ D）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构 16 下列叙述中错误的是 （ A）在带链队列中，队头指针和队尾指针都是在动态变化的 （ B）在带链栈中，栈顶指针和栈底指针都是在动态变化的 （ C）在带链栈中，栈项指针是在动态变化的，但栈底指针是不变的 （ D）以上三项都错误 17 设数据元素的集合 D=1， 2,3,4,5，则满足下列关系
7、 R、的数据结构中为线性结构的是 （ A） R=(1， 2)， (3， 4)， (5， 1) （ B） R=(1， 3)， (4， 1)， (3， 2)， (5， 4) （ C） R=(1， 2)， (2,3)， (4,5) （ D） R=(1， 3)， (2,4)， (3,5) 18 下列叙述中正确的是 （ A）链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 （ B）线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针 （ C）线性表的链式存储结构中，每个结点只能有一个指向后件的指针 （ D）线性表的链式存储结构中，叶子结点的指针只能是空 19 一个栈的初
8、始状态为空，现将元素 A、 B、 C、 D、 E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队 (原队列为空 )，最后将队列中的元素全部退出。则元素退队的顺序为 （ A） ABC （ B） CBA （ C） EDC （ D） CDE 20 某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度 (根结点在第 1层 )为 （ A） 5 （ B） 4 （ C） 3 （ D） 2 21 下列叙述中正确的是 （ A）所谓算法就是计算方法 （ B）程序可以作为算法的一种描述方法 （ C）算法设 计只需考虑得到计算结果 （ D）算法设计可以忽略算法的运算时间 22 下列
9、各序列中不是堆的是 （ A） (91， 85,53,36,47,30,24， 12) （ B） (91， 85,53,47,36,30,24， 12) （ C） (47,91， 53,85,30,12,24,36) （ D） (91， 85,53,47,30,12,24,36) 23 深度为 5的完全二叉树的结点数不可能是 （ A） 15 （ B） 16 （ C） 17 （ D） 18 24 有二叉树如下图所示： 则前序序列为 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 25 下列叙述中正确的是 （ A）循环队列是顺序存储结构
10、 （ B）循环队列是链式存储结构 （ C）循环队列是非线性结构 （ D）循环队列的插入运算不会发生溢出现象 26 下列叙述中正确的是 （ A）所有数据结构必须有根结点 （ B）所有数据结构必须有终端结点 (即叶子结点 ) （ C）只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构 （ D）没有根结点或没有叶子结点的数据结构一定是非线性结构 27 下列关于算法的 描述中错误的是 （ A）算法强调动态的执行过程，不同于静态的计算公式 （ B）算法必须能在有限个步骤之后终止 （ C）算法设计必须考虑算法的复杂度 （ D）算法的优劣取决于运行算法程序的环境 28 设有二叉树如下图所示： 则中序
11、序到为 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 29 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有 （ A）节省存储空间 （ B）插入与删除运算效率高 （ C）便于查找 （ D）排序时减少元素的比较 次数 30 深度为 7的完全二叉树中共有 125个结点，则该完全二叉树中的叶子结点数为 （ A） 62 （ B） 63 （ C） 64 （ D） 65 31 设表的长度为 n。在下列算法中，最坏情况下时间复杂度最高的是 （ A）堆排序 （ B）希尔排序 （ C）有序链表查找 （ D）循环链表中寻找最大项 32
12、设循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。经过一系列正常的操作后， front=rear-1。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为 （ A） 0 （ B） 1 （ C） 49 （ D） 50 国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 9答案与解析 一、选择题 1 【正确答案】 C 【试题解析】 按平均时间将排序分为四类： 平方阶 (O(n2)排序：各类简单排序，例如直接插入、直接选择和冒泡排序； 线性对数阶 (O(nlog2n)排序：如快速排序、堆排序和归并排序； O(nl+)排序： 是介于 0和 1之间的常数。
13、希尔排序便是一种； 线性阶 (O(n)排序：本程序中的基数排序，此外还有桶、箱排序。 【知识模块】 数据结构与算法 2 【正确答案】 B 【试题解析】 因为在任意的二叉树中，度为 0的结点 (即叶子结点 )总比度为 2的结点的个数多 1个，而度为 0的结点数 n0=2Tm-1(其中 m为二叉树的深度 )。本题的度为 0的结点个数 n0=27-1=26=64。因此，度为 2的结点数 n2=n0-1=63。所以选项 B正确 【知识模块】 数据结构与算法 3 【正确答案】 C 【试题解析】 根据题意，栈空间如下图所示。 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位。 当压入第一个元
14、素时， TOP指针指向m+11=m；当压 入第二个元素时， TOP指针指向 m+1-2=m1； 以此类推，当压入第 N个元素时， TOP指针指向 m+1-N=20；则 N=m+1-20=m-19。因此选项C正确。 【知识模块】 数据结构与算法 4 【正确答案】 D 【试题解析】 算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项 D正确。 【知识模块】 数据结构与算法 5 【正确答案】 A 【试题解析】 初始状态为： front=rear=m， rear-front=0，此时队列为空，经过一系列入队与退队运算 后， front=15， rear=20。队尾大于队头，则队
15、尾 rear减队头 front等于 5个元素。此时队列中有 5个元素，而查找最大项至少要比较 n-1次，就是 4次。因此选项 A正确。 【知识模块】 数据结构与算法 6 【正确答案】 D 【试题解析】 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。 【知识模块】 数据结构与算法 7 【正确答案】 B 【试题解析】 对于任意一棵二叉树，如果其叶结点数为 N0，而 度数为 2的结点总数为 N2，则 N0=N2+1； N2=Nn-1。所以如果二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为 n-1。因此选项 B
16、正确。 【知识模块】 数据结构与算法 8 【正确答案】 C 【试题解析】 算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项 C错误。 【知识模块】 数据结构与算法 9 【正确答案】 C 【试题解析】 在操作系统中，栈是向下生长的，如下图如示： 所以当栈底指针 bottom=49，栈顶指针 top=30时，栈中的元素个数为：栈底一栈顶 +1=4930+1=20。因此选项 C正确。 【知识模块】 数据结构与算法 10 【正确答案】 C 【试题解析】 该二叉树的前序序列为
17、 ABCDEFG，中序序列为 DCBAEFG，可知A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上；并且结点 B、 C、 D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树 上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。所以得到的二叉树为： 所以这个二叉树的深度为 4。选项 C为正确答案。 【知识模块】 数据结构与算法 11 【正确答案】 D 【试题解析】 数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以
18、下两个条件： 有且只有一个根结点； 每一个结占最多有一个前件，也最多有一个后件。根据这两个条件，可知选项 A)、 B)和 C)都不能判定是否是线性结构。 【知识模块】 数据结构与算法 12 【正确答案】 C 【试题解析】 带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项 C正确。 【知识模块】 数据结构与算法 13 【正确答案】 D 【试题解析】 在循环队列中元素的个数为 “(rear-front+M) M”，式中 rear为队尾指针， front为队首指针， M为存储容量，为取余符号。对于找最小值的最坏情况下的比较次数，为循环队列中元素值个数减一。所以对于这个颢目来说初
19、始时元素个数为 0；运算后，元素个数为 m一 5， 找最小值的最坏情况下的比较次数为 m-5-1=m一 6。 【知识模块】 数据结构与算法 14 【正确答案】 D 【试题解析】 该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上；并且结点 B、 C、 D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下： 根据该二叉树，可 得出后序遍历序
20、列为： DCBGFEA，选项 D正确。 【知识模块】 数据结构与算法 15 【正确答案】 B 【试题解析】 选项 A叙述是错误的，例如在双向链表中，每个结点有两个指针域，但该链表是线性结构；选项 C叙述也是错误的，例如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项 D叙述也是错误的，线性结构只有唯一的一个前驱和唯一的一个后继 (头、尾除外 )；排除法可判断选项 B正确。 【知识模块】 数据结构与算法 16 【正确答案】 B 【试题解析】 栈是只在一端进行增加和删除 的线性表，进行操作的那端称为栈顶，另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项
21、C的说法正确，选项 B的说法是错误的。队列是允许在队列的头和尾都可以进行操作的线性表，所以在带链队列中，队头指针和队尾指针都是在动态变化的选项 A这一说法是正确的。 【知识模块】 数据结构与算法 17 【正确答案】 B 【试题解析】 把每个答案中的第一个元素集合取出来，例如 A： (1， 2)，先写下来就是 12，然后看后面的 (3， 4)，在 (1， 2)中找不到前驱和后继，只能和 (1， 2)暂时先 并列，然后是 (5， 1)，这里我们已经写过 12了，那么 5在 1前面就是 512，但是 34要单排，所以 A就是两个根节点 3和 5，两个顺序是 512， 34。同理选项 B是 541，
22、32；选项 C是： 123和 45：选项 D是 1 35， 24所以选项 B正确。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题解析】 在链式存储方式中，每仑结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项 B、 C、 D说法错误。选项A中，例如双向链表就具有两个指针，也属于线性结构，所以选项 A正确。 【知识模块】 数据结构与算法 19 【正确答案】 C 【试题解析】 栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为E、 D、 C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为 E、D、 C，所以选项 C正确。 【知识模块
23、】 数据结构与算法 20 【正确答案】 B 【试题解析】 该二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，可知 A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上；并且结点 B、 C、 D在中序序列和后序序列 中顺序未变，则说明这三个结点依次位于前一个结点的左子树上：结点 E、 F、 G顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为 4，所以选项 B正确。 【知识模块】 数据结构与算法 21 【正确答案】 B 【试题解析】 算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是
24、计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选项 A和选项 C不正确。程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故选项 B正确。算法 要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以选项 D错误。 【知识模块】 数据结构与算法 22 【正确答案】 C 【试题解析】 堆可以看成一棵完全二叉树：任一根节点 =左右孩子 (或者 =)， (大的叫大根堆，小的叫小根堆 )。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显 91是最大的根，而选项 C是
25、 “左根右 ”的排序，那么 91的左边只有 47，其他都在右边，而右边无法按照此顺序排列，所以选项 C不是堆。 【知识模块】 数据结构与算法 23 【正确答案】 A 【试题解析】 对于满二叉树，叶子结点的数目等于 2(n-1)， n为深度，这里就是 2的 5-1=4次方，就是 16。所以选项 A为正确答案。 【知识模块】 数据结构与算法 24 【正确答案】 A 【试题解析】 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故选项 A正确，选项 B为中序遍历，选项 C为后序遍历，选项 D不正确。 【知识模块】 数据结构
26、与算法 25 【正确答案】 A 【试题解析】 循环队列属于队列的特例和栈同属于线性结构，所以选项 C不正确。在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾 rear的值和队头 front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺序队列通常都采用顺序循环队列结构：栈的存储方式有顺序存储和链式存储，故选项 A正确，选项 B不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而
27、产生的真溢出，故选项 D不正确。 【知识模块】 数据结构与算法 26 【正确答案】 D 【试题解析】 只有一个空节点的结构也属数据结构，所以选项 A和选项 B不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故选项 C不正确，选项 D正确。 【知识模块】 数据结构与算法 27 【正确答案】 D 【试题解析】 算法的优劣取决自身的运 行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故选项 D错误。 【知识模块】 数据结构与算法 28 【正确答案】 B 【试题解析】 中序遍历 (LDR)是指首先遍历左子树，然后访问根
28、结点，最后遍历右子树，选项 B正确。 【知识模块】 数据结构与算法 29 【正确答案】 B 【试题解析】 顺序存储时，相邻数据元素的存放地址也相邻 (逻辑与物理统一 )；要求内存中可用存储单元的地址必须是连续的。优点是存储密度大 (=1)，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储 时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点是插入或删除元素时很方便效率高，使用灵活。缺点是存储密度小 ( 1)，存储空间利用率低，故选项 B正确。 【知识模块】 数据结构与算法 30 【正确答案】 B 【试题解析】 对于满二叉树，结点的数
29、目等于 2n-1，叶子结点数目为 2n-1， n为深度，这里就是 2的 7次方 -1，就是 127个结点，叶子结点是 64个。然而题目中只有 125个结点，说明少了两个结点，那么就少了一个叶子结点，即 63个。 【知 识模块】 数据结构与算法 31 【正确答案】 B 【试题解析】 希尔排序 (Shell Son)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。排序方法最坏时间复杂度：直接插入为 O(n2)、简单选择为 O(n2)、起泡排序为 O(n2)、快速排序为 O(n2)、堆排序为O(nlog2n)、归并排序为 O(nlog2n)。 【知识模块】 数据结构与算法 32 【正确答案】 A 【试题解析】 front指定队头位置，删除一个元素就将 front顺时针移动一位；rear指尾 指针，指向元素要插入的位置，插入一个元素就将 rear顺时针移动一位；操作后，循环队列的队头指针等于尾指针 -1，说明此时队列已经是空队列，那么就不用比较了。 【知识模块】 数据结构与算法
