【计算机类职业资格】国家二级C语言机试（数据结构与算法）-试卷2-1及答案解析.doc

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

1、国家二级 C 语言机试（数据结构与算法）-试卷 2-1 及答案解析(总分：76.00，做题时间：90 分钟)一、选择题(总题数：38，分数：76.00)1.对长度为 10 的线性表进行冒泡排序，最坏情况下需要比较的次数为（ ）。（分数：2.00）A.9B.10C.45D.902.下列叙述中正确的是（ ）。（分数：2.00）A.算法的效率只与问题的规模有关，而与数据的存储结构无关B.算法的时间复杂度是指执行算法所需要的计算工作量C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关3.下列叙述中正确的是（ ）。（分数：2.00）A.线性表链式存储结构的存储空间一般要少于

2、顺序存储结构B.线性表链式存储结构与顺序存储结构的存储空间都是连续的C.线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D.以上说法都不对4.某二叉树共有 12 个结点，其中叶子结点只有 1 个。则该二叉树的深度为（根结点在第 1 层）（ ）。（分数：2.00）A.3B.6C.8D.125.对长度为 n 的线性表作快速排序，在最坏情况下，比较次数为（ ）。（分数：2.00）A.nB.n-1C.n(n-1)D.n(n-1)/26.下列叙述中正确的是（ ）。（分数：2.00）A.有且只有一个根结点的数据结构一定是线性结构B.每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构

3、C.有且只有一个根结点的数据结构一定是非线性结构D.有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构7.下列叙述中错误的是（ ）。（分数：2.00）A.在双向链表中，可以从任何一个结点开始直接遍历到所有结点B.在循环链表中，可以从任何一个结点开始直接遍历到所有结点C.在线性单链表中，可以从任何一个结点开始直接遍历到所有结点D.在二叉链表中，可以从根结点开始遍历到所有结点8.某二叉树共有 13 个结点，其中有 4 个度为 1 的结点，则叶子结点数为（ ）。（分数：2.00）A.5B.4C.3D.29.设栈的顺序存储空间为 S(1: 50),初始状态为 top=0。现经过一系列入栈与

4、退栈运算后，top=20，则当前栈中的元素个数为（ ）。（分数：2.00）A.30B.29C.20D.1910.下列叙述中正确的是（ ）。（分数：2.00）A.栈与队列都只能顺序存储B.循环队列是队列的顺序存储结构C.循环链表是循环队列的链式存储结构D.以上说法都不对11.设某二叉树的前序序列为 ABC，中序序列为 CBA，则该二叉树的后序序列为（ ）。（分数：2.00）A.BCAB.CBAC.ABCD.CAB12.下列排序方法中，最坏情况下时间复杂度最小的是（ ）。（分数：2.00）A.冒泡排序B.快速排序C.堆排序D.直接插入排序13.为了对有序表进行对分查找，则要求有序表（ ）。（分数：

5、2.00）A.只能顺序存储B.只能链式存储C.可以顺序存储也可以链式存储D.任何存储方式14.设某二叉树的后序序列为 CBA，中序序列为 ABC，则该二叉树的前序序列为（ ）。（分数：2.00）A.BCAB.CBAC.ABCD.CAB15.下列叙述中正确的是（ ）。（分数：2.00）A.存储空间不连续的所有链表一定是非线性结构B.结点中有多个指针域的所有链表一定是非线性结构C.能顺序存储的数据结构一定是线性结构D.带链的栈与队列是线性结构16.算法时间复杂度的度量方法是（ ）。（分数：2.00）A.算法程序的长度B.执行算法所需要的基本运算次数C.执行算法所需要的所有运算次数D.执行算法所需要

6、的时间17.设循环队列为 Q(1: m)，初始状态为 front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为（ ）。（分数：2.00）A.1B.2C.m-1D.0 或 m18.在最坏情况下（ ）。（分数：2.00）A.快速排序的时间复杂度比冒泡排序的时间复杂度要小B.快速排序的时间复杂度比希尔排序的时间复杂度要小C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的19.在深度为 7 的满二叉树中，度为 2 的结点个数为（ ）。（分数：2.00）A.64B.63C.32D.3120.设

7、栈的顺序存储空间为 S(1: m)，初始状态为 top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（ ）。（分数：2.00）A.30B.20C.m-19D.m-2021.算法空间复杂度的度量方法是（ ）。（分数：2.00）A.算法程序的长度B.算法所处理的数据量C.执行算法所需要的工作单元D.执行算法所需要的存储空间22.下面不属于软件开发阶段任务的是（ ）。（分数：2.00）A.测试B.可行性研究C.设计D.实现23.设循环队列为 Q(1: m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环

8、队列中寻找最大值的元素，最坏情况下需要比较的次数为（ ）。（分数：2.00）A.4B.6C.m-5D.m-624.下列叙述中正确的是（ ）。（分数：2.00）A.循环队列属于队列的链式存储结构B.双向链表是二叉树的链式存储结构C.非线性结构只能采用链式存储结构D.有的非线性结构也可以采用顺序存储结构25.某二叉树中有 n 个叶子结点，则该二叉树中度为 2 的结点数为（ ）。（分数：2.00）A.n+1B.n-1C.2nD.n/226.下列叙述中错误的是（ ）。（分数：2.00）A.算法的时间复杂度与算法所处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算

9、法的时间复杂度与空间复杂度有直接关系D.以上说法都不对27.设栈的顺序存储空间为 S(0:49)，栈底指针 bottom=49，栈顶指针 top=30（指向栈顶元素）。则栈中的元素个数为（ ）。（分数：2.00）A.30B.29C.20D.1928.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度（根结点在第 1 层）为（ ）。（分数：2.00）A.2B.3C.4D.529.下列叙述中正确的是（ ）。（分数：2.00）A.存储空间连续的数据结构一定是线性结构B.存储空间不连续的数据结构一定是非线性结构C.没有根结点的非空数据结构一定是线性结构D.具有两个根结点

10、的数据结构一定是非线性结构30.下列叙述中正确的是（ ）。（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针D.以上说法都不对31.设循环队列为 Q(1:m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（ ）。（分数：2.00）A.5B.6C.m-5D.m-632.某二叉树的前序序列为 ABCDEFG，中序序列为 DC

11、BAEFG，则该二叉树的后序序列为（ ）。（分数：2.00）A.EFGDCBAB.DCBEFGAC.BCDGFEAD.DCBGFEA33.下列叙述中正确的是（ ）。（分数：2.00）A.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构C.在链表中，如果每个结点有两个指针域，则该链表一定是线性结构D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构34.下列叙述中错误的是（ ）。（分数：2.00）A.在带链队列中，队头指针和队尾指针都是在动态变化的B.在带链栈中，栈顶指针和栈底指针都是在

12、动态变化的C.在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的D.以上说法均不对35.设数据元素的集合 D= 1,2,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) 36.下列叙述中正确的是（ ）。（分数：2.00）A.链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构B.线性表的链式存储结构中，每个结点必须有指向前件和指

13、向后件的两个指针C.线性表的链式存储结构中，每个结点只能有一个指向后件的指针D.线性表的链式存储结构中，叶子结点的指针只能是空37.一个栈的初始状态为空。现将元素 A,B,C,D,E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为（ ）。（分数：2.00）A.ABCB.CBAC.EDCD.CDE38.某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度（根结点在第 1 层）为（ ）。（分数：2.00）A.5B.4C.3D.2国家二级 C 语言机试（数据结构与算法）-试卷 2-1 答案解析(总分：

14、76.00，做题时间：90 分钟)一、选择题(总题数：38，分数：76.00)1.对长度为 10 的线性表进行冒泡排序，最坏情况下需要比较的次数为（ ）。（分数：2.00）A.9B.10C.45 D.90解析：解析：在最坏情况下，冒泡排序的时间复杂度为 n(n-1)/2，为 45，答案选 C。2.下列叙述中正确的是（ ）。（分数：2.00）A.算法的效率只与问题的规模有关，而与数据的存储结构无关B.算法的时间复杂度是指执行算法所需要的计算工作量 C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关解析：解析：算法的时间复杂度是指执行算法所需要的计算工作量，与数据的存

15、储结构有关，与算法的空间复杂度没有关系。数据的逻辑结构与存储位置无关，即与存储结构无关，所以选择 B。3.下列叙述中正确的是（ ）。（分数：2.00）A.线性表链式存储结构的存储空间一般要少于顺序存储结构B.线性表链式存储结构与顺序存储结构的存储空间都是连续的C.线性表链式存储结构的存储空间可以是连续的，也可以是不连续的 D.以上说法都不对解析：解析：在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的，所以选择 C。4.某二叉树共有 12 个结点，其中叶子结点只有 1 个。则该二叉树的深度为（根

16、结点在第 1 层）（ ）。（分数：2.00）A.3B.6C.8D.12 解析：解析：根据二叉树的性质，叶子结点比度为 2 的结点个数多一个，叶子结点只有 1 个，那么度为 2的结点为 0 个，可以得出共有 11 个度为 1 的结点，那么该二叉树每一层上只能有一个结点，共 12 层，即深度为 12。5.对长度为 n 的线性表作快速排序，在最坏情况下，比较次数为（ ）。（分数：2.00）A.nB.n-1C.n(n-1)D.n(n-1)/2 解析：解析：在最坏情况下，快速排序需要比较 n(n-1)/2 次。6.下列叙述中正确的是（ ）。（分数：2.00）A.有且只有一个根结点的数据结构一定是线性结构

17、B.每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构C.有且只有一个根结点的数据结构一定是非线性结构D.有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构 解析：解析：有且只有一个根结点的数据结构可以是线性结构，如队列，也可以是非线性结构，如二叉树，所以选项 D）正确。选项 B）中，如果有两个根结点，则不符合线性结构的条件，说法错误。本题答案选D）。7.下列叙述中错误的是（ ）。（分数：2.00）A.在双向链表中，可以从任何一个结点开始直接遍历到所有结点B.在循环链表中，可以从任何一个结点开始直接遍历到所有结点C.在线性单链表中，可以从任何一个结点开始直接遍历到所有

18、结点 D.在二叉链表中，可以从根结点开始遍历到所有结点解析：解析：在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点，选项 C）说法错误。8.某二叉树共有 13 个结点，其中有 4 个度为 1 的结点，则叶子结点数为（ ）。（分数：2.00）A.5 B.4C.3D.2解析：解析：根据题意，该二叉树中叶子结点数和度为 2 的结点数的和为 9。根据二叉树的基本性质，叶子结点比度为 2 的结点多 1 个，则度为 2 的结点个数为 4，叶子结点的个数为 5，所以答案选 A。9.设栈的顺序存储空间为 S(1: 50),初始状态为 top=0。现经过一系列入栈与退栈运

19、算后，top=20，则当前栈中的元素个数为（ ）。（分数：2.00）A.30B.29C.20 D.19解析：解析：在栈中，top 位置直接反映栈中元素的个数，top=20，则说明当前栈中的元素个数为 20。10.下列叙述中正确的是（ ）。（分数：2.00）A.栈与队列都只能顺序存储B.循环队列是队列的顺序存储结构 C.循环链表是循环队列的链式存储结构D.以上说法都不对解析：解析：栈和队列都可以采用链式存储结构，选项 A）错误。队列的顺序存储结构一般采用循环队列的形式，所以循环队列是队列的顺序存储结构，选项 B 正确，选项 C）错误。答案选 B）。11.设某二叉树的前序序列为 ABC，中序序列为

20、 CBA，则该二叉树的后序序列为（ ）。（分数：2.00）A.BCAB.CBA C.ABCD.CAB解析：解析：前序序列为 ABC，中序序列为 CBA，说明根结点为 A，且 B 和 C 均在该 A 的左子树上；结点B 和 C 的前序序列为 BC，中序序列为 CB，则说明结点 C 在结点 B 的左子树上，根据以上分析，该二叉树的后序序列为 CBA，答案选 B）。12.下列排序方法中，最坏情况下时间复杂度最小的是（ ）。（分数：2.00）A.冒泡排序B.快速排序C.堆排序 D.直接插入排序解析：解析：在最坏情况下，堆排序时间复杂度为 O(nlog 2 n)，其余选项均为 O(n 2 )，所以答案选

21、 C。13.为了对有序表进行对分查找，则要求有序表（ ）。（分数：2.00）A.只能顺序存储 B.只能链式存储C.可以顺序存储也可以链式存储D.任何存储方式解析：解析：对分查找必须满足用顺序存储结构，且线性表是有序表两个条件，答案选 A。14.设某二叉树的后序序列为 CBA，中序序列为 ABC，则该二叉树的前序序列为（ ）。（分数：2.00）A.BCAB.CBAC.ABC D.CAB解析：解析：后序序列为 CBA，中序序列为 ABC，则说明，A 为根结点，并且 B 和 C 均在 A 的右子树上；结点 B 和 C 中，后序序列为 CB，中序序列为 BC，则说明结点 C 在结点 B 的右子树上，根

22、据分析可得，该二叉树的前序序列为 ABC，答案选 C。15.下列叙述中正确的是（ ）。（分数：2.00）A.存储空间不连续的所有链表一定是非线性结构B.结点中有多个指针域的所有链表一定是非线性结构C.能顺序存储的数据结构一定是线性结构D.带链的栈与队列是线性结构 解析：解析：判断一个非空的数据结构是否为线性结构必须满足以下两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项 A）、B）和 C）都不能判定是否是线性结构，选项 D）正确，答案选 D）。16.算法时间复杂度的度量方法是（ ）。（分数：2.00）A.算法程序的长度B.执行算法所需要的基

23、本运算次数 C.执行算法所需要的所有运算次数D.执行算法所需要的时间解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，答案选 B。17.设循环队列为 Q(1: m)，初始状态为 front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为（ ）。（分数：2.00）A.1B.2C.m-1D.0 或 m 解析：解析：在循环队列中，当 front=rear 时，有两种情况，一种是队列为空，另一种是队列为满，所以答案选 D。18.在最坏情况下（ ）。（分数：2.00）A.快速排序的时间复杂度比冒

24、泡排序的时间复杂度要小B.快速排序的时间复杂度比希尔排序的时间复杂度要小C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小 D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的解析：解析：在最坏情况下，快速排序、冒泡排序和直接插入排序所需要的比较次数为 O(n 2 )，希尔排序所需要的比较次数为 O(n 1.5 )，所以答案选 C。19.在深度为 7 的满二叉树中，度为 2 的结点个数为（ ）。（分数：2.00）A.64B.63 C.32D.31解析：解析：根据满二叉树的性质，深度为 7 的满二叉树共有 2 2 -1=127 个结点。根据二叉树的性质，该满二叉树在第 7 层上，共有 2

25、7-1 =64 个结点，即共有 64 个叶子结点，那么度为 2 的结点个数为 127-64=63 个。20.设栈的顺序存储空间为 S(1: m)，初始状态为 top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（ ）。（分数：2.00）A.30B.20C.m-19 D.m-20解析：解析：初始状态为 top=m+1，经过运算之后，top=20，则当前栈中元素个数为 m+1-20=m-19 个。21.算法空间复杂度的度量方法是（ ）。（分数：2.00）A.算法程序的长度B.算法所处理的数据量C.执行算法所需要的工作单元D.执行算法所需要的存储空间 解析：解析：算法的

26、空间复杂度，一般是指执行这个算法所需要的内存空间，答案选 D。22.下面不属于软件开发阶段任务的是（ ）。（分数：2.00）A.测试B.可行性研究 C.设计D.实现解析：解析：可行性研究是属于软件定义阶段的任务，所以答案选 B。23.设循环队列为 Q(1: m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（ ）。（分数：2.00）A.4 B.6C.m-5D.m-6解析：解析：初始状态为 front=rear=m，说明初始状态为空。经过一系列入队与退队运算后，front=15

27、，rear=20，则当前共有 5 个元素，则在最坏情况下，需要比较的次数为 4 次，答案选 A。24.下列叙述中正确的是（ ）。（分数：2.00）A.循环队列属于队列的链式存储结构B.双向链表是二叉树的链式存储结构C.非线性结构只能采用链式存储结构D.有的非线性结构也可以采用顺序存储结构 解析：解析：循环队列属于队列的顺序存储结构，选项 A）错误；二叉树的存储结构为二叉链表，选项B）错误；非线性结构也可以采用顺序存储结构，因此选项 C）错误，选项 D）正确，答案为 D）。25.某二叉树中有 n 个叶子结点，则该二叉树中度为 2 的结点数为（ ）。（分数：2.00）A.n+1B.n-1 C.2n

28、D.n/2解析：解析：根据二叉树的性质，叶子结点的个数比度为 2 的结点数多一个，因此答案为 B)。26.下列叙述中错误的是（ ）。（分数：2.00）A.算法的时间复杂度与算法所处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算法的时间复杂度与空间复杂度有直接关系 D.以上说法都不对解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，并且两者之间美欧直接关系，因此答案选 C。27.设栈的顺序存储空间为 S(0:49)，栈底指针 bottom=49，栈

29、顶指针 top=30（指向栈顶元素）。则栈中的元素个数为（ ）。（分数：2.00）A.30B.29C.20 D.19解析：解析：栈底指针 bottom=49，栈顶指针 top=30，则栈中的元素个数为 49-30+1=20 个，答案选 C。28.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度（根结点在第 1 层）为（ ）。（分数：2.00）A.2B.3C.4 D.5解析：解析：该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知 A 为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上；并且结点 B、C、

30、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树深度为 4，答案选 C。29.下列叙述中正确的是（ ）。（分数：2.00）A.存储空间连续的数据结构一定是线性结构B.存储空间不连续的数据结构一定是非线性结构C.没有根结点的非空数据结构一定是线性结构D.具有两个根结点的数据结构一定是非线性结构 解析：解析：判断一个非空的数据结构是否为线性结构必须满足以下两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项 A）、B）和

31、 C）都不能判定是否是线性结构，选项 D）正确，答案选 D）。30.下列叙述中正确的是（ ）。（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针 D.以上说法都不对解析：解析：带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，答案选 C。31.设循环队列为 Q(1:m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比

32、较的次数为（ ）。（分数：2.00）A.5B.6C.m-5D.m-6 解析：解析：该循环队列的容量为 m，队列中共有 15-20+m=m-5 个元素，如果想找出其中的最小值，最坏情况下需要比较 m-5-1=m-6 次。32.某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为（ ）。（分数：2.00）A.EFGDCBAB.DCBEFGAC.BCDGFEAD.DCBGFEA 解析：解析：该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知 A 为根结点，结点 B、C、D 位于根结点的左子树上，结点 E、F、G 位于根结点的右子树上；并且结点

33、B、C、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、F、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的后序遍历序列为 DCBGFEA，答案选 D。33.下列叙述中正确的是（ ）。（分数：2.00）A.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构 C.在链表中，如果每个结点有两个指针域，则该链表一定是线性结构D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构解析：解析：判断一个非空的数据结构是否为

34、线性结构必须满足以下两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。选项 B）中，如果有两个结点的同一个指针域的值相等，则说明至少有一个结点有两个前件，不符合线性结构的定义，所以答案选 B）。34.下列叙述中错误的是（ ）。（分数：2.00）A.在带链队列中，队头指针和队尾指针都是在动态变化的B.在带链栈中，栈顶指针和栈底指针都是在动态变化的 C.在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的D.以上说法均不对解析：解析：在栈结构中，插入和删除操作都是在栈顶进行操作，相对应的在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，所以选项 B）说法错误。3

35、5.设数据元素的集合 D= 1,2,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) 解析：解析：关系 R 中的每个结点由两个部分构成，分别是数据域和指针域。选项 B）中可以看出，元素序列为 54132，符合线性结构的条件。选项 A）、选项 C）和选项 D）中分别有两个根结点，不符合线性结构的条件。所以答案选 B）。36.下列叙述中正确的是（ ）。

36、（分数：2.00）A.链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 B.线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针C.线性表的链式存储结构中，每个结点只能有一个指向后件的指针D.线性表的链式存储结构中，叶子结点的指针只能是空解析：解析：在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项 B）、C）、D）说法错误。选项 A）中，例如双向链表就具有两个指针，也属于线性结构，所以答案选 A）。37.一个栈的初始状态为空。现将元素 A,B,C,D,E 依次入栈，然后依次退栈三次，并将退栈的三个元素依

37、次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为（ ）。（分数：2.00）A.ABCB.CBAC.EDC D.CDE解析：解析：栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为 E、D、C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为 E、D、C，答案选 C。38.某二叉树的中序序列为 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 顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为 4，答案选 B。