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