【计算机类职业资格】国家二级ACCESS机试选择题（数据结构与算法）模拟试卷15及答案解析.doc

《【计算机类职业资格】国家二级ACCESS机试选择题（数据结构与算法）模拟试卷15及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】国家二级ACCESS机试选择题（数据结构与算法）模拟试卷15及答案解析.doc（10页珍藏版）》请在麦多课文档分享上搜索。

1、国家二级 ACCESS 机试选择题（数据结构与算法）模拟试卷 15 及答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：32，分数：64.00)1.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.00）A.4B.6C.m-5D.m-62.下列叙述中正确的是（分数：2.00）A.循环队列属于队列的链式存储结构B.双向链表是二叉树的链式存储结构C.非线性结构只能采用链式存储结构D.有的非线性结构也可以采用顺序存储结构3.某二

2、叉树中有 n 个叶子结点，则该二叉树中度为 2l 的结点数为（分数：2.00）A.n+1B.n-1C.2nD.n24.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与算法所处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算法的时间复杂度与空间复杂度有直接关系D.算法的时间复杂度与空间复杂度没有必然的联系5.设栈的顺序存储空间为 S(0：49)，栈底指针 bottom=49，栈顶指针 top=30(指向栈顶元素)。则栈中的元素个数为（分数：2.00）A.30B.29C.20D.196.某二叉树的前序序列为：ABCDEFG，中序序列为：DCBAEF

3、G，则该二叉树的深度(根结点在第 1 层)为（分数：2.00）A.2B.3C.4D.57.下列叙述中正确的是（分数：2.00）A.存储空间连续的数据结构一定是线性结构B.存储空间不连续的数据结构一定是非线性结构C.没有根结点的非空数据结构一定是线性结构D.具有两个根结点的数据结构一定是非线性结构8.下列叙述中正确的是（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针D.以上三项都错误9.设循环队列为 Q(1：m)，其初始状态为 front

4、=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（分数：2.00）A.5B.6C.m-5D.m-610.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为（分数：2.00）A.EFGDCBAB.DCBEFGAC.BCDCGFEAD.DCBGFEA11.下列叙述中正确的是（分数：2.00）A.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构C.在链表中，如果每个结点有两个指针域，则

5、该链表一定是线性结构D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构12.下列叙述中错误的是（分数：2.00）A.在带链队列中，队头指针和队尾指针都是在动态变化的B.在带链栈中，栈顶指针和栈底指针都是在动态变化的C.在带链栈中，栈顶指针是在动态变化的曼但栈底指针是不变的D.以上三项都错误13.设数据元素的集合 D=112，3，4，5)，则满足下列关系 R 的数据结构中为线性结构的是（分数：2.00）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)，(

6、3，5)14.下列叙述中正确的是 （分数：2.00）A.链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构B.线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针C.线性表的链式存储结构中，每个结点只能有一个指向后件的指针D.线性表的链式存储结构中，叶子结点的指针只能是空15.一个栈的初始状态为空，现将元素 A、B、C、D、E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为（分数：2.00）A.ABCB.CBAC.EDCD.CDE16.某二叉树中序序列为 DCBAEFG，后序序列为 DCBGF

7、EA，则该二叉树的深度(根结点在第 1 层)为（分数：2.00）A.5B.4C.3D.217.下列叙述中正确的是（分数：2.00）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间18.下列各序列中不是堆的是（分数：2.00）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)19.深度为 5 的完全二叉树的结点数不可能是（分数：2.00）A.15B.16C.

8、17D.1820.有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH21.下列叙述中正确的是（分数：2.00）A.循环队列是顺序存储结构B.循环队列是链式存储结构C.循环队列是非线性结构D.循环队列的插入运算不会发生溢出现象22.下列叙述中正确的是（分数：2.00）A.所有数据结构必须有根结点B.所有数据结构必须有终端结点(即叶予结点)C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结点的数据结构一定是非线性结构23.下列关于算法的描述中错误的是（分数：2.00）A.算法强调动态的执行过

9、程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境24.设有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH25.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（分数：2.00）A.节省存储空间B.插入与删除运算效率高C.便于查找D.排序时减少元素的比较次数26.深度为 7 的完全二叉树中共有 125 个结点，则该完全二叉树中的叶子结点数为（分数：2.00）A.62B.63C.64D.6527.下列叙述中正确的是（分数：2.00）A.

10、所谓有序表是指在顺序存储空间内连续存放的元素序列B.有序表只能顺序存储在连续的存储空间内C.有序表可以用链接存储方式存储在不连续的存储空间内D.任何存储方式的有序表均能采用二分法进行查找28.设有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH29.下列叙述中正确的是（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C.二叉树只能采用链式存储结构D.循环链表是非线性结构30.设某二叉树中共有 140 个结点，其中有 40 个度为 1 的结点。则（分数

11、：2.00）A.该二叉树中有 51 个叶子结点B.该二叉树中有 50 个叶子结点C.该二叉树中有 51 个度为 2 的结点D.不可能有这样的二叉树31.带链的栈与顺序存储的栈相比，其优点是（分数：2.00）A.入栈与退栈操作方便B.可以省略栈底指针C.入栈操作时不会受栈存储空间的限制而发生溢出D.所占存储空间相同32.某二叉树的前序序列为 ABCD，中序序列为 DCBA，则后序序列为（分数：2.00）A.BADCB.DCBAC.CDABD.ABCD国家二级 ACCESS 机试选择题（数据结构与算法）模拟试卷 15 答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：32，分数

12、：64.00)1.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.00）A.4 B.6C.m-5D.m-6解析：解析：初始状态为：front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾 rear 减队头 front 等于 5 个元素。此时队列中有 5 个元素，而查找最大项至少要比较 n1 次，就是 4 次。因此选项 A 正确。2.下列叙述中正确的是

13、（分数：2.00）A.循环队列属于队列的链式存储结构B.双向链表是二叉树的链式存储结构C.非线性结构只能采用链式存储结构D.有的非线性结构也可以采用顺序存储结构 解析：解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。3.某二叉树中有 n 个叶子结点，则该二叉树中度为 2l 的结点数为（分数：2.00）A.n+1B.n-1 C.2nD.n2解析：解析：任意一棵二叉树，如果叶结点数为 N 0 ，而度数为 2 的结点总数为 N 2 ，则 N 0 =N 2 +1；N 2 =N 0 -1。所以如果二叉树中有 n 个叶子

14、结点，则该二叉树中度为 2 的结点数为 n-1。因此选项 B 正确。4.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与算法所处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算法的时间复杂度与空间复杂度有直接关系 D.算法的时间复杂度与空间复杂度没有必然的联系解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项 C 错误。5.设栈的顺序存储空间为 S(0：49)，栈底指针 bottom=49，栈顶指针 top

15、=30(指向栈顶元素)。则栈中的元素个数为（分数：2.00）A.30B.29C.20 D.19解析：解析：在操作系统中，栈是向下生长的，如下图如示：6.某二叉树的前序序列为：ABCDEFG，中序序列为：DCBAEFG，则该二叉树的深度(根结点在第 1 层)为（分数：2.00）A.2B.3C.4 D.5解析：解析：该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知 A 为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上；并且结点 B、C、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺

16、序未变，则说明这三个结点依次位于前一个结点的右子树上。所以得到的二叉树为：7.下列叙述中正确的是（分数：2.00）A.存储空间连续的数据结构一定是线性结构B.存储空间不连续的数据结构一定是非线性结构C.没有根结点的非空数据结构一定是线性结构D.具有两个根结点的数据结构一定是非线性结构 解析：解析：数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项 A)、B)和 C)都不能判定是否是线性结构。8.下列叙述中正确的是

17、（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针 D.以上三项都错误解析：解析：带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项 C 正确。9.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（分数：2.00）A.5B.6C.m-5D.m-6 解析：解析：在循环队列中元素的

18、个数为“(rear-front+M)M”，式中 rear 为队尾指针，front 为队首指针，M 为存储容量，为取余符号。对于找最小值的最坏情况下的比较次数，为循环队列中元素值个数减一。所以对于这个题目来说初始时元素个数为 0；运算后，元素个数为 m-5，找最小值的最坏情况下的比较次数为 m-5-1=m-6。10.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为（分数：2.00）A.EFGDCBAB.DCBEFGAC.BCDCGFEAD.DCBGFEA 解析：解析：该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知 A 为根结点，结点

19、 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上；并且结点 B、C、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下：11.下列叙述中正确的是（分数：2.00）A.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构 C.在链表中，如果每个结点有两个指针域，则该链表一定是线性结构D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表

20、一定是线性结构解析：解析：选项 A 叙述是错误的，如在双向链表中，每个结点有两个指针域，但该链表是线性结构；选项 C 叙述也是错误的，如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项 D 叙述也是错误的，线性结构只有唯一的一个前驱和唯一的一个后继(头、尾除外)；排除法可判断选项 B 正确。12.下列叙述中错误的是（分数：2.00）A.在带链队列中，队头指针和队尾指针都是在动态变化的B.在带链栈中，栈顶指针和栈底指针都是在动态变化的 C.在带链栈中，栈顶指针是在动态变化的曼但栈底指针是不变的D.以上三项都错误解析：解析：栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈顶，另

21、一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项 C 的说法正确，选项 B 的说法是错误的。队列是允许在队列的头和尾都可以进行操作的线性表，所以在带链队列中，队头指针和队尾指针都是在动态变化的选项 A 这一说法是正确的。13.设数据元素的集合 D=112，3，4，5)，则满足下列关系 R 的数据结构中为线性结构的是（分数：2.00）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)解析：解析：把每个答案中的第一个元素集合取出来，例如

22、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；选项 C 是：123 和 45；选项 D 是 135，24 所以选项 B 正确。14.下列叙述中正确的是 （分数：2.00）A.链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 B.线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针C.线性表的链式

23、存储结构中，每个结点只能有一个指向后件的指针D.线性表的链式存储结构中，叶子结点的指针只能是空解析：解析：在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项 B、C、D 说法错误。选项 A 中，例如双向链表就具有两个指针，也属于线性结构，所以选项 A 正确。15.一个栈的初始状态为空，现将元素 A、B、C、D、E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为（分数：2.00）A.ABCB.CBAC.EDC D.CDE解析：解析：栈是根据先进后出的原则组织数据，所以退栈

24、三次的元素依次为 E、D、C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为 E、D、C，所以选项 C 正确。16.某二叉树中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度(根结点在第 1 层)为（分数：2.00）A.5B.4 C.3D.2解析：解析：该二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，可知 A 为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上；并且结点 B、C、D 在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上：结点 E、F、G 顺序颠倒，则说明这三个结点依次

25、位于前一个结点的右子树上。根据以上分析，该二叉树的深度为 4，所以选项 B 正确。17.下列叙述中正确的是（分数：2.00）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法 C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间解析：解析：算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选项 A 和选项 C 不正确。程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故选项 B 正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以选项 D

26、错误。18.下列各序列中不是堆的是（分数：2.00）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)解析：解析：堆可以看成一棵完全二叉树：任一根节点=左右孩子(或者=)，(大的叫大根堆，小的叫小根堆)。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显 91 是最大的根，而选项 C 是“左根右”的排序，那么 91 的左边只有 47，其他都在右边，

27、而右边无法按照此顺序排列，所以选项 C 不是堆。19.深度为 5 的完全二叉树的结点数不可能是（分数：2.00）A.15B.16 C.17D.18解析：解析：对于满二叉树，叶子结点的数目等于 2 (n-1) ，n 为深度，这里就是 2 的 5-1=4 次方，就是16。所以选项 A 为正确答案。20.有二叉树如下图所示： （分数：2.00）A.ABDEGCFH B.DBGEAFHCC.DGEBHFCAD.ABCDEFGH解析：解析：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故选项 A 正确，选项 B 为中序遍历，选

28、项 C 为后序遍历，选项 D 不正确。21.下列叙述中正确的是（分数：2.00）A.循环队列是顺序存储结构 B.循环队列是链式存储结构C.循环队列是非线性结构D.循环队列的插入运算不会发生溢出现象解析：解析：循环队列属于队列的特例和栈同属于线性结构，所以选项 C 不正确。在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾 rear 的值和队头 front 的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺

29、序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项A 正确，选项 B 不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生的真溢出，故选项 D 不正确。22.下列叙述中正确的是（分数：2.00）A.所有数据结构必须有根结点B.所有数据结构必须有终端结点(即叶予结点)C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结点的数据结构一定是非线性结构 解析：解析：只有一个空节点的结构也属数据结构，所以选项 A 和选项 B 不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结

30、构，其它的都属于非线性结构，故选项 C 不正确，选项 D 正确。23.下列关于算法的描述中错误的是（分数：2.00）A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境 解析：解析：算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故选项 D 错误。24.设有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHC C.DGEBHFCAD.ABCDEFGH解析：解析：中序遍历(LDR)是指首先遍历左子树，然后访问根结点，最后遍历右子树，选项

31、B 正确。25.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（分数：2.00）A.节省存储空间B.插入与删除运算效率高 C.便于查找D.排序时减少元素的比较次数解析：解析：顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)：要求内存中可用存储单元的地址必须是连续的。优点是存储密度大(=1)，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点是插入或删除元素时很方便效率高，使用灵活。缺点是存储密度小(1)，存储空间利用率低，故选项 B 正确。26.深度为 7 的

32、完全二叉树中共有 125 个结点，则该完全二叉树中的叶子结点数为（分数：2.00）A.62B.63 C.64D.65解析：解析：对于满二叉树，结点的数目等于 2 n -1，叶子结点数目为 2 n-1 ，n 为深度，这里就是 2 的7 次方-1，就是 127 个结点，叶子结点是 64 个。然而题目中只有 125 个结点，说明少了两个结点，那么就少了一个叶子结点，即 63 个。27.下列叙述中正确的是（分数：2.00）A.所谓有序表是指在顺序存储空间内连续存放的元素序列B.有序表只能顺序存储在连续的存储空间内C.有序表可以用链接存储方式存储在不连续的存储空间内 D.任何存储方式的有序表均能采用二分

33、法进行查找解析：解析：有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项 C 正确。28.设有二叉树如下图所示： （分数：2.00）A.ABDEGCFHB.DBGEAFHCC.DGEBHFCA D.ABCDEFGH解析：解析：后序遍历(LRD)首先遍历左子树，然后访问遍历右子树，最后访问根结点，可知选项 C 正确。29.下列叙述中正确的是（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线

34、性结构 C.二叉树只能采用链式存储结构D.循环链表是非线性结构解析：解析：结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故选项 A 不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构，故选项 C 不正确；循环链表是在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开始结点的线性结构，故选项 D 不正确；当结点中两个指针分别指向前驱结点和后继结点时为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故选项 B 正确。30.设某二叉树中共有 140 个结点，其中有 40 个度为 1 的结点。则（分数：

35、2.00）A.该二叉树中有 51 个叶子结点B.该二叉树中有 50 个叶子结点C.该二叉树中有 51 个度为 2 的结点D.不可能有这样的二叉树 解析：解析：140 个结点除去 40 个度为 1 的结点，说明有 100 个度为 2 的结点，而根据二叉树性质，这个数值无法得出一棵二叉树，故本题答案选 D。31.带链的栈与顺序存储的栈相比，其优点是（分数：2.00）A.入栈与退栈操作方便B.可以省略栈底指针C.入栈操作时不会受栈存储空间的限制而发生溢出 D.所占存储空间相同解析：解析：带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故选项 C 正确。32.某二叉树的前序序列为 ABCD，中序序列为 DCBA，则后序序列为（分数：2.00）A.BADCB.DCBA C.CDABD.ABCD解析：解析：在二叉树前序遍历中 ABCD 中 A 是根节点，而在后序遍历中根结点位于最后，所以选项 B 正确。