1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 6及答案解析(总分：84.00，做题时间：90 分钟)一、选择题(总题数：42，分数：84.00)1.带链栈空的条件是（分数：2.00）A.top=bottom=NULLB.top=-I且 bottom=NULLC.top=NULL且 bottom-1D.top=bottom=-12.设一棵度为 3的树，其中度为 2，1，0 的结点数分别为 3，1，6。该树中度为 3的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树3.下列数据结构中，不能采用顺序存储结构的是（分数：2.00）A.栈B.堆C.队列D.非完全二叉树4.设
2、二叉树共有 375个结点，其中度为 2的结点有 187个。则度为 1的结点个数是（分数：2.00）A.0B.1C.188D.不可能有这样的二叉树5.在带链队列中，经过一系列正常的操作后，如果 front=rear，则队列中的元素个数为（分数：2.00）A.0或 1B.0C.1D.队列满6.设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。该树中度为 3的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树7.设二叉树共有 500个结点，其中叶子结点有 250个。则度为 2的结点个数是（分数：2.00）A.0B.1C.249D.不可能有这样的二叉树8.下列叙述中正确的是
3、（分数：2.00）A.带链栈的栈底指针是固定的B.带链栈的栈底指针是随栈的操作而动态变化的C.若带链队列的队头指针与队尾指针相同，则队列为空D.若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素9.带链队列空的条件是（分数：2.00）A.front=rear=NULLB.front=rear=-1C.front=NULL且 rear=-1D.front=-1且 rear=NULL10.设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 6。该树中度为 3的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树11.下列叙述中正确的是（分数：2.00）A.循环队列是线性
4、结构B.循环队列是线性逻辑结构C.循环队列是链式存储结构D.循环队列是非线性存储结构12.设某棵树的度为 3，其中度为 3、2、1 的结点个数分别为 3、0、4。则该树中的叶子结点数为（分数：2.00）A.7B.8C.6D.不可能有这样的树13.设有一个栈与一个队列的初始状态均为空。现有一个序列 A,B,C,D,E,F,G，H。先分别将序列中的前 4个元素依次入栈，后 4个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为（分数：2.00）A.D,C,B,A，E,F,G,HB.D,C,B,A，H,G,EEC.A,B,C,D,E,F,G,HD.A,B,C,D,
5、H,G,EE14.下列叙述中错误的是（分数：2.00）A.具有两个根结点的数据结构一定属于非线性结构B.具有两个以上指针域的链式结构一定属于非线性结构C.具有两个以上叶子结点的数据结构一定属于非线性结构D.具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构15.下列结构中属于线性结构链式存储的是（分数：2.00）A.双向链表B.循环队列C.二叉链表D.二维数组16.下列叙述中错误的是（分数：2.00）A.循环链表中有一个表头结点B.循环链衷的存储空间是连续的C.循环链表实现了空表与非空表运算的统一D.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点17.度为 3的一棵树
6、共有 30个结点，其中度为 3、1 的结点个数分别为 3、4。则该树中的叶子结点数为（分数：2.00）A.14B.15C.16D.不可能有这样的树18.在长度为 97的顺序有序表中作二分查找，最多需要的比较次数为（分数：2.00）A.7B.96C.48D.619.下列结构中属于非线性结构的是（分数：2.00）A.二叉链表B.二维数组C.循环队列D.双向链表20.从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是（分数：2.00）A.循环链表B.双向链表C.单向链表D.二叉链表21.设二叉树的前序序列与中序序列均为 ABCDEFGH，则该二叉树的后序序列为（分数：2.00）A
7、.HGFEDCBAB.ABCDEFGHC.ABCDHGFED.DCBAHGFE22.设某棵树的度为 3，其中度为 3、1、0 的结点个数分别为 3、4、15。则该树中总结点数为（分数：2.00）A.22B.30C.35D.不可能有这样的树23.下列叙述中正确的是（分数：2.00）A.矩阵是非线性结构B.数组是长度固定的线性表C.对线性表只能作插入与删除运算D.线性表中各元素的数据类型可以不同24.在快速排序法中，每经过一次数据交换(或移动)后（分数：2.00）A.能消除多个逆序B.只能消除一个逆序C.不会产生新的逆序D.消除的逆序个数一定比新产生的逆序个数多25.线性表的长度为 n。在最坏情况
8、下，比较次数为 n-1的算法是（分数：2.00）A.顺序查找B.有序表的插入C.寻找最大项D.同时寻找最大项与最小项26.设某棵树的度为 3，其中度为 2、1、0 的结点个数分别为 3、4、15。则该树中总结点数为（分数：2.00）A.22B.30C.35D.不可能有这样的树27.下列叙述中错误的是（分数：2.00）A.向量是线性结构B.非空线性结构中只有一个结点没有前件C.非空线性结构中只有一个结点没有后件D.只有一个根结点和一个叶子结点的结构必定是线性结构28.在希尔排序法中，每经过一次数据交换后（分数：2.00）A.能消除多个逆序B.只能消除一个逆序C.不会产生新的逆序D.消除的逆序个数
9、一定比新产生的逆序个数多29.设二叉树的后序序列与中序序列均为 ABCDEFGH，则该二叉树的前序序列为（分数：2.00）A.HGFEDCBAB.ABCDEFGHC.ABCDHGFED.DCBAHGFE30.下列叙述中正确的是（分数：2.00）A.循环队列是队列的链式存储结构B.能采用顺序存储的必定是线性结构C.所有的线性结构都可以采用顺序存储结构D.具有两个以上指针的链表必定是非线性结构31.下列叙述中正确的是（分数：2.00）A.算法的复杂度是指算法所处理的数据量B.算法的复杂度是指算法程序中指令的数量C.算法的复杂度是指算法控制结构的复杂程度D.算法的复杂度包括时间复杂度与空间复杂度32
10、.设二叉树的前序序列为ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则按层次输出(从上到下，同一层从左到右)的序列为（分数：2.00）A.ABCDEFGHIJB.DGHEBIJFCAC.JIHGFEDCBAD.GHIJDEFBCA33.设循环队列的存储空间为 Q(1：50)，初始状态为。front=rear=50。经过一系列正常的操作后，front-1=rear。为了在该队列中寻找值最大元素，在最坏情况下需要的比较次数为（分数：2.00）A.0B.1C.48D.4934.设顺序表的长度为 40，对该表进行冒泡排序。在最坏情况下需要的比较次数为（分数：2.00）A.780B.820C.
11、40D.4135.设表的长度为 n。在下列算法中，最坏情况下时间复杂度最高的是（分数：2.00）A.堆排序B.希尔排序C.有序链表查找D.循环链表中寻找最大项36.设循环队列的存储空间为 Q(1：50)，初始状态为 front=rear=50。经过一系列正常的操作后，front=rear-1。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为（分数：2.00）A.0B.1C.49D.5037.设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为（分数：2.00）A.DGHEBIJFCAB.JIHGFEDCBAC.GHIJDEFBCAD.ABCDE
12、FGHIJ38.设顺序表的长度为 16，对该表进行简单插入排序。在最坏情况下需要的比较次数为（分数：2.00）A.1 5B.30C.60D.12039.下列结构中为非线性结构的是（分数：2.00）A.树B.向量C.二维表D.矩阵40.设表的长度为 n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是（分数：2.00）A.堆排序B.有序链表查找C.希尔排序D.循环链表中寻找最大项41.设循环队列的存储空间为 Q(1：m)，初始状态为 front=rear=m。经过一系列正常的操作后，front=1，rear=m。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为（分数：2.00）
13、A.mB.m-1C.m2D.142.设二叉树的后序序列为 DGHEBIJFCA，中序序列为 DBGEHACIFJ。则前序序列为（分数：2.00）A.ABDEGHCFIJB.JIHGFEDCBAC.GHIJDEFBCAD.ABCDEFGHIJ国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 6答案解析(总分：84.00，做题时间：90 分钟)一、选择题(总题数：42，分数：84.00)1.带链栈空的条件是（分数：2.00）A.top=bottom=NULL B.top=-I且 bottom=NULLC.top=NULL且 bottom-1D.top=bottom=-1解析：解析：栈的链
14、式存储结构称为链栈。在链栈中，只会出现栈空和非空两种状态。当栈为空时，有top=bottom=NULL；当栈非空时，top 指向链表的第一个结点(栈顶)。所以选项 A正确。2.设一棵度为 3的树，其中度为 2，1，0 的结点数分别为 3，1，6。该树中度为 3的结点数为（分数：2.00）A.1 B.2C.3D.不可能有这样的树解析：解析：因为任一棵树中，结点总数=总分支数目+1，所以：6+1+3+n 3 =(0*6+1*1+2*3+3*n3)+1。运算结果 n 3 =1。其中，n 3 表示度为 3的结点数，所以选项 A正确。3.下列数据结构中，不能采用顺序存储结构的是（分数：2.00）A.栈B
15、.堆C.队列D.非完全二叉树 解析：解析：堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。4.设二叉树共有 375个结点，其中度为 2的结点有 187个。则度为 1的结点个数是（分数：2.00）A.0 B.1C.188D.不可能有这样的二叉树解析：解析：二叉树的每个结点至多只有二棵子树(不存在度大于 2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i层至多有 2 i-1 个结点；深度为 k的二叉树至多有
16、 2k一 1个结点；对任何一棵二叉树 T，如果其终端结点数为 n 0 ，度为 2的结点数为 n 2 ，则 n 0 =n 2 +1。本题中，度为 2的结点有 187个，叶子结点应该有 187+1=188个，度为 1的结点个数=375187-188=0。5.在带链队列中，经过一系列正常的操作后，如果 front=rear，则队列中的元素个数为（分数：2.00）A.0或 1 B.0C.1D.队列满解析：解析：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除
17、操作的端称为队头。队列的链式存储也称为链队列。为了便于操作，可给链队列添加 1个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空(0)或 1时，front=rear。6.设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。该树中度为 3的结点数为（分数：2.00）A.1B.2 C.3D.不可能有这样的树解析：解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，那么树中最少有一个结点的度为 3。而树中没有度为 2的结点，叶子结点数为 5，度为 1的结点下面只有一个叶子结点。因此，该树中含 2个度为 3的结点满足题
18、目要求。7.设二叉树共有 500个结点，其中叶子结点有 250个。则度为 2的结点个数是（分数：2.00）A.0B.1C.249 D.不可能有这样的二叉树解析：解析：二叉树的每个结点至多只有二棵子树(不存在度大于 2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i层至多有 2 i-1 个结点；深度为 k的二叉树至多有 2 k-1 个结点；对任何一棵二叉树 T，如果其终端结点数为 n 0 ，度为 2的结点数为 n 2 ，则 n 0 =n 2 +1。本题中，叶子结点有250个，度为 2的结点数为 n 2 =n 0 -1=250-1=249。8.下列叙述中正确的是（分数：2.00）A.
19、带链栈的栈底指针是固定的B.带链栈的栈底指针是随栈的操作而动态变化的 C.若带链队列的队头指针与队尾指针相同，则队列为空D.若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素解析：解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行桶入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈项元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队
20、列可能为 0也可能为 1。9.带链队列空的条件是（分数：2.00）A.front=rear=NULL B.front=rear=-1C.front=NULL且 rear=-1D.front=-1且 rear=NULL解析：解析：带链队列空的条件有两个：一个是 front=rear，一个是它们都等于空。10.设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 6。该树中度为 3的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树 解析：解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，也就是最少有一个度为 3的结点。要求没有度为 2的结点，且叶子结点为
21、 6，如果要有度为 3的结点，那么最多只有 5个叶子结点，而画不出 6个叶子结点。因此这样的树是没有的。11.下列叙述中正确的是（分数：2.00）A.循环队列是线性结构 B.循环队列是线性逻辑结构C.循环队列是链式存储结构D.循环队列是非线性存储结构解析：解析：为充分利用向量空间，克服“假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。12.设某棵
22、树的度为 3，其中度为 3、2、1 的结点个数分别为 3、0、4。则该树中的叶子结点数为（分数：2.00）A.7 B.8C.6D.不可能有这样的树解析：解析：树的度是指一棵树中，最大的结点的度称为“树的度”。根据题目可知本树中没有度为 2的结点。树的总结点=(度 1*个数+度 2*个数)+1，这里我们设总结点数为 n，那么 n=3*3+2*0+1*4+1=14。树的叶子结点数等于总结点减去所有度不为 0的结点，也就是 1434=7。13.设有一个栈与一个队列的初始状态均为空。现有一个序列 A,B,C,D,E,F,G，H。先分别将序列中的前 4个元素依次入栈，后 4个元素依次入队；然后分别将栈中
23、的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为（分数：2.00）A.D,C,B,A，E,F,G,H B.D,C,B,A，H,G,EEC.A,B,C,D,E,F,G,HD.A,B,C,D,H,G,EE解析：解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是 D,C,B,A。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。因此，队的出队
24、顺序是，先入先出，所以顺序是：E,F,G,H。最后的顺序是：D,C,B,A，E，F，G，H。14.下列叙述中错误的是（分数：2.00）A.具有两个根结点的数据结构一定属于非线性结构B.具有两个以上指针域的链式结构一定属于非线性结构 C.具有两个以上叶子结点的数据结构一定属于非线性结构D.具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构解析：解析：非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。15.下列结构中属于线性结构链式存储的是（分数：2.00）A.双向链表 B.循环队列C.二叉
25、链表D.二维数组解析：解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。16.下列叙述中错误的是（分数：2.00）A.循环链表中有一个表头结点B.循环链衷的存储空间是连续的 C.循环链表实现了空表与非空表运算的统一D.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点解析：解析：循环链表是另一
26、种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。17.度为 3的一棵树共有 30个结点，其中度为 3、1 的结点个数分别为 3、4。则该树中的叶子结点数为（分数：2.00）A.14B.15 C.16D.不可能有这样的树解析：解析：根据题目可知本树中还有度为 2的结点。树的总结点=(度 1*个数+度 2*个数)+1，这里我们设度为 2的结点数为 x，那么 30=3*3+2*x+1*4+1=2*x+14，由此可计算出 x=8。树的叶子结点数等于总结点减去所有度不为 0的结点，也就是 3
27、0384=15。18.在长度为 97的顺序有序表中作二分查找，最多需要的比较次数为（分数：2.00）A.7 B.96C.48D.6解析：解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式：k=log 2 n。其中 n代表长度，k 为比较次数。本题中可以计算出 k=7。19.下列结构中属于非线性结构的是（分数：2.00）A.二叉链表B.二维数组 C.循环队列D.双向链表解析：解析：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串；常见的非线性结构有：二维数组，多维数组，广义
28、表，树(二叉树等)，图。循环队列、双向链表和二叉锌表都是线性结构，而二维数组是非线性结构。20.从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是（分数：2.00）A.循环链表 B.双向链表C.单向链表D.二叉链表解析：解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，循环一圈就访问到了表中其它所有结点而不重复。21.设二叉树的前序序列与中序序列均为 ABCDEFGH，则该二叉树的后序序列为（分数：2.00）A.HGFEDCBA B.ABCDEFGHC.ABCDHGFED.DCBAHGFE解析：解析：前序遍历(DLR
29、)是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右；中序遍历(LDR)是二叉树遍历的一种，也叫做中根遍历、中序周游，可记做左根右；后序遍历(LRD)是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根：根据题中前序和中序序列均为ABCDEFGH，可画出二叉树，该二叉树是一个子结点全部在右侧二叉树，然后根据后序遍历方法，可得出后序遍历为 HGFEDCBA。22.设某棵树的度为 3，其中度为 3、1、0 的结点个数分别为 3、4、15。则该树中总结点数为（分数：2.00）A.22B.30 C.35D.不可能有这样的树解析：解析：本题采用画图法来求出结果。首先先画出包含 3
30、个度为 3的结点；然后再添加 4个度为 1的结点，此时最大度为 0的结点数为 8。根据题目中描述的度为 0的结点数有 15个，这时要在书中添加度为 2的结点，直到度为 0的结点数位 15。画图结束后，不管是什么样的树，总结点数都是 30。23.下列叙述中正确的是（分数：2.00）A.矩阵是非线性结构B.数组是长度固定的线性表 C.对线性表只能作插入与删除运算D.线性表中各元素的数据类型可以不同解析：解析：所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分它们的变量的集合，这个名字称为数组名，编号称为下标。24.在快速排序法中，每经过一
31、次数据交换(或移动)后（分数：2.00）A.能消除多个逆序 B.只能消除一个逆序C.不会产生新的逆序D.消除的逆序个数一定比新产生的逆序个数多解析：解析：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。25.线性表的长度为 n。在最坏情况下，比较次数为 n-1的算法是（分数：2.00）A.顺序查找B.有序表的插入C.寻找最大项 D.同时寻找最大项与最小项解析：解析：寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因
32、此，比较次数为 n-1。26.设某棵树的度为 3，其中度为 2、1、0 的结点个数分别为 3、4、15。则该树中总结点数为（分数：2.00）A.22B.30C.35D.不可能有这样的树 解析：解析：本题采用画图法来求出结果。首先先画出包含 3个度为 2的结点；然后再添加 4个度为 1的结点。根据题目中描述的度为 0的结点数有 15个，这时要在书中添加度为 3的结点，不管怎么添加都不能添加出 15个度为 0的结点，因此不可能有这样的树。27.下列叙述中错误的是（分数：2.00）A.向量是线性结构B.非空线性结构中只有一个结点没有前件C.非空线性结构中只有一个结点没有后件D.只有一个根结点和一个叶
33、子结点的结构必定是线性结构 解析：解析：线性结构是 n个数据元素的有序(次序)集合。集合中必存在唯一的一个“第一个元素”；集合中必存在唯一的一个“最后的元素”：除最后元素之外，其它数据元素均有唯一的“后件”；除第一元素之外，其它数据元素均有唯一的“前件”。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。向量符合线性结构特点。非线性结构也会存在只有一个根结点和叶子结点的情况。28.在希尔排序法中，每经过一次数据交换后（分数：2.00）A.能消除多个逆序 B.只能消除一个逆序C.不会产生新的逆序D.消除的逆序个数一定比新产生的逆序个数多解析：解析：希尔排序法(缩
34、小增量法)属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。插入排序能够消除多个逆序，也会产生新的逆序。消除的逆序与新产生的逆序有多有少。29.设二叉树的后序序列与中序序列均为 ABCDEFGH，则该二叉树的前序序列为（分数：2.00）A.HGFEDCBA B.ABCDEFGHC.ABCDHGFED.DCBAHGFE解析：解析：后序遍历中，最后一个字母是根结点，也就是 H是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树，H 后面没有，因此该树没有右子树。同理，可判断出该树是第一个完全的左子树。由此可画出这个二叉树，然后根据二叉树可的前序序列为 HGFEDCB
35、A。30.下列叙述中正确的是（分数：2.00）A.循环队列是队列的链式存储结构B.能采用顺序存储的必定是线性结构C.所有的线性结构都可以采用顺序存储结构 D.具有两个以上指针的链表必定是非线性结构解析：解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。所有的线性结构都可以采用顺序存储结构。31.下列叙述中正确的是（分数：2.00）A.算法的复杂度是指算法所处理的数据量B.算法的复杂度是指算法程序中指令的数量C.算法的复杂度是指算法控制结构的复杂程度D.算法的复杂度包括时间复杂度与
36、空间复杂度 解析：解析：算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。32.设二叉树的前序序列为ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则按层次输出(从上到下，同一层从左到右)的序列为（分数：2.00）A.ABCDEFGHIJ B.DGHEBIJFCAC.JIHGFEDCBAD.GHIJDEFBCA解析：解析：前序遍历中，第一个字母是根结点，也就是 A是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树。前序中，B 在 A的后面，中序中在左子树中，可知 B为 A的左结点。中序中 D在B的前面，前序中在 B的后面，可知 D为
37、B的左结点，GEH 为 B的右子树。前序中顺序为 EGH，由此可知，E为 B的右结点，G 为 E的左结点、H 为 E的右结点。右子树中，前序中 C在最前，因为右子树根结点，也就是 A的右结点，根据前序中的子树 FIJ和中序中的 IFJ子树可知 F为 C的右结点，I 为 F的左结点、J为 F的右结点。由此可画出这个二叉树，然后根据二叉树，可知按层次输出(从上到下，同一层从左到右)的序列为：ABCDEFGHIJ。33.设循环队列的存储空间为 Q(1：50)，初始状态为。front=rear=50。经过一系列正常的操作后，front-1=rear。为了在该队列中寻找值最大元素，在最坏情况下需要的比较
38、次数为（分数：2.00）A.0B.1C.48 D.49解析：解析：front 指向队头位置，删除一个元素就将 front顺时针移动一位：rear 指尾指针，指向元素要插入的位置，插入一个元素就将 rear顺时针移动一位：操作后，循环队列的队头指针一 1等于尾指针，说明出队一位，那么总数就是 49了。在该队列中寻找最大值元素，最多比较次数是总数一 1，因此是491=48次。34.设顺序表的长度为 40，对该表进行冒泡排序。在最坏情况下需要的比较次数为（分数：2.00）A.780 B.820C.40D.41解析：解析：冒泡排序(Bubble Sort)，是一种计算机科学领域的较简单的排序算法。冒泡
39、排序算法的运作如下：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。冒泡排序的最坏时间复杂度为(n*(n-1)2=780。35.设表的长度为 n。在下列算法中，最坏情况下时间复杂度最高的是（分数：2.00）A.堆排序B.希尔排序 C.有序链表查找D.循环链表中寻找最大项解析：解析：希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的
40、改进版本。排序方法最坏时间复杂度：直接插入为 O(n 2 )、简单选择为 O(n 2 )、起泡排序为O(n 2 )、快速排序为 O(n 2 )、堆排序为 O(nlog 2 n)、归并排序为 O(nlog 2 n)。36.设循环队列的存储空间为 Q(1：50)，初始状态为 front=rear=50。经过一系列正常的操作后，front=rear-1。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为（分数：2.00）A.0 B.1C.49D.50解析：解析：front 指定队头位置，删除一个元素就将 front顺时针移动一位；rear 指尾指针，指向元素要插入的位置，插入一个元素就将
41、rear顺时针移动一位；操作后，循环队列的队头指针等于尾指针-1，说明此时队列己经是空队列，那么就不用比较了。37.设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为（分数：2.00）A.DGHEBIJFCA B.JIHGFEDCBAC.GHIJDEFBCAD.ABCDEFGHIJ解析：解析：前序遍历中，第一个字母是根结点，也就是 A是根结点：在中序遍历中，根结点前面的是左子树、后面的是右子树。前序中，B 在 A的后面，中序中在左子树中，可知 B为 A的左结点。中序中 D在B的前面，前序中在 B的后面，可知 D为 B的左结点，GEH 为 B的右子树。前序
42、中顺序为 EGH，由此可知，E为 B的右结点，G 为 E的左结点、H 为 E的右结点。右子树中，前序中 C在最前，因为右子树根结点，也就是 A的右结点，根据前序中的子树 FIJ和中序中的 IFJ子树可知 F为 C的右结点，I 为 F的左结点、J为 F的右结点。由此可画出这个二叉树，然后根据二叉树可的后序序列为 DGHEBIJFCA。38.设顺序表的长度为 16，对该表进行简单插入排序。在最坏情况下需要的比较次数为（分数：2.00）A.1 5B.30C.60D.120 解析：解析：插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为
43、止。最坏情况计算方法(n*(n1)2=16*152=120。39.下列结构中为非线性结构的是（分数：2.00）A.树 B.向量C.二维表D.矩阵解析：解析：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。40.设表的长度为 n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是（分数：2.00）A.堆排序B.有序链表查找C.希尔排序D.循环链表中寻找最大项 解析：解析：在循环链表中寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为 n1。4
44、1.设循环队列的存储空间为 Q(1：m)，初始状态为 front=rear=m。经过一系列正常的操作后，front=1，rear=m。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为（分数：2.00）A.mB.m-1C.m2 D.1解析：解析：经过一系列正常的操作后，front=1，rear=m，那么最坏情况下需要的比较次数为 rearfront-1=m-1-1=m-2。42.设二叉树的后序序列为 DGHEBIJFCA，中序序列为 DBGEHACIFJ。则前序序列为（分数：2.00）A.ABDEGHCFIJ B.JIHGFEDCBAC.GHIJDEFBCAD.ABCDEFGHIJ解
45、析：解析：后序遍历中，最后一个字母是根结点，也就是 A是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树。后序中 C在 A前面、中序中 C在 A的后面，说明 C是 A的右结点；后序中 F在 C的前面、中序中在 C后面，且后序和中序中，I 均在 F前面由此可确定，I 为 F的左结点，F 为 C的右结点。同 C理 J为 F的右结点。后续中 B为左子树的根结点，因此 B为 A的左结点，以此划分，在中序中 B前面的 D为左结点，后面的 GEH为右子树，后序中，E 在最后，应为剩下 3个结点的根结点，也就是B的右子树，再根据中序中的顺序，可得出 G为 E的左结点，H 为 E的右结点。由此可画出这个二叉树，然后根据二叉树可的前序序列为 ABDEGI-ICFIJ。
