1、国家二级 ACCESS 机试选择题（数据结构与算法）模拟试卷 17 及答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：32，分数：64.00)1.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f，a) 该数据结构为（分数：2.00）A.非线性结构B.循环队列C.循环链表D.线性结构2.下列排序法中，每经过一次元素的交换会产生新的逆序的是（分数：2.00）A.快速排序B.冒泡排序C.简单插入排序D.简单选择排序3.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退
2、队操作后，front=rear=10。该队列中的元素个数为（分数：2.00）A.1B.0C.1 或 0D.不确定4.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为（分数：2.00）A.ABDHECFGB.ABCDEFGHC.HDBEAFCGD.HDEBFGCA5.下列叙述中正确的是（分数：2.00）A.有的二叉树也能用顺序存储结构表示B.有两个指针域的链表就是二叉链表C.多重链表一定是非线性结构D.顺序存储结构一定是线性结构6.下列各排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序B.快速排序C.希尔排序D.冒泡排序7.某带链队列
3、初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定B.5C.4D.68.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFGHB.HFDBGECAC.HGFEDCBAD.ACEGBDFH9.某带链栈初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为（分数：2.00）A.不确定B.10C.1D.010.设表的长度为
4、15。则在最坏情况下，快速排序所需要的比较次数为（分数：2.00）A.105B.55C.15D.7511.设循环队列的存储空间为 Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为（分数：2.00）A.不确定B.49C.51D.5012.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的中序序列为（分数：2.00）A.HDBEAFCGB.HDEBFGCAC.ABDHECFGD.ABCDEFGH13.下列叙述中正确的是（分数：2.00）A.解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的B.解决一个问题可
5、以有不同的算法，但它们的时间复杂度必定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关14.设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找B.顺序查找C.寻找最大项D.寻找最小项15.某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为（分数：2.00）A.1B.0C.20D.不确定16.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树的后序序列为（分数：2.00）A.HFDBGECAB.ABCDEFG
6、HC.HGFEDCBAD.ACEGBDFH17.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与问题规模无关B.算法的时间复杂度与计算机系统无关C.算法的时间复杂度与空间复杂度没有必然的联系D.算法的空间复杂度与算法运行输出结果的数据量无关18.设表的长度为 20。则在最坏情况下，冒泡排序的比较次数为（分数：2.00）A.90B.20C.19D.19019.在带链栈中，经过一系列正常的操作后，如果 top=bottom，则栈中的元素个数为（分数：2.00）A.1B.0C.0 或 1D.栈满20.设一棵树的度为 3，共有 27 个结点，其中度为 3，2，0 的结点数分别为 4，1，10
7、。该树中度为 1 的结点数为（分数：2.00）A.11B.12C.13D.不可能有这样的树21.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(f，a)，(d，b)，(c，d)，(c，e)，(a，c) 该数据结构为（分数：2.00）A.线性结构B.循环队列C.循环链表D.非线性结构22.下列叙述中错误的是（分数：2.00）A.循环队列空的条件是队头指针与队尾指针相同B.若二叉树没有叶子结点，则为空二叉树C.带链栈的栈底指针是随栈的操作而动态变化的D.若带链队列中只有一个元素，则队头指针与队尾指针必定相同23.带链栈空的条件是（分数：2.00）A.top=bottom=NUL
8、LB.top=-1 且 bottom=NULLC.top=NULL 且 boaom-1D.too=bottom=-124.设一棵度为 3 的树，其中度为 2，1，0 的结点数分别为 3，1，6。该树中度为 3 的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树25.下列数据结构中，不能采用顺序存储结构的是（分数：2.00）A.栈B.堆C.队列D.非完全二叉树26.设二叉树共有 375 个结点，其中度为 2 的结点有 187 个。则度为 1 的结点个数是（分数：2.00）A.0B.1C.188D.不可能有这样的二叉树27.在带链队列中，经过一系列正常的操作后，如果 front=r
9、ear，则队列中的元素个数为（分数：2.00）A.0 或 1B.0C.1D.人列满28.设一棵树的度为 3，其中没有度为 2 的结点，且叶子结点数为 5。该树中度为 3 的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树29.设二叉树共有 500 个结点，其中叶子结点有 250 个。则度为 2 的结点个数是（分数：2.00）A.0B.1C.249D.不可能有这样的二叉树30.下列叙述中正确的是（分数：2.00）A.带链栈的栈底指针是固定的B.带链栈的栈底指针是随栈的操作而动态变化的C.若带链队列的队头指针与队尾指针相同，则队列为空D.若带链队列的队头指针与队尾指针相同，则队列中
10、至少有一个元素31.带链队列空的条件是（分数：2.00）A.front=rear=NULLB.front=rear=-1C.front=NULL 且 rear=-1D.front=-1 且 rear=NULL32.设一棵树的度为 3，其中没有度为 2 的结点，且叶子结点数为 6。该树中度为 3 的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树国家二级 ACCESS 机试选择题（数据结构与算法）模拟试卷 17 答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：32，分数：64.00)1.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(a，
11、b)，(b，c)，(c，d)，(d，e)，(e，f)，(f，a) 该数据结构为（分数：2.00）A.非线性结构 B.循环队列C.循环链表D.线性结构解析：解析：该逻辑结构为非线性结构，在 R=(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f，a)中，各结点之间形成一个循环链。2.下列排序法中，每经过一次元素的交换会产生新的逆序的是（分数：2.00）A.快速排序 B.冒泡排序C.简单插入排序D.简单选择排序解析：解析：冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本
12、轮比较结束。故选项 A 正确。3.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为（分数：2.00）A.1 B.0C.1 或 0D.不确定解析：解析：循环队列用数组 A0；m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是(rear-front+m)m=1，所以选项 A 正确。4.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为（分数：2.00）A.ABDHECFG B.ABCDEFGHC.HDBEAFCGD.HDEBFG
13、CA解析：解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH，可以得到其结构如下：5.下列叙述中正确的是（分数：2.00）A.有的二叉树也能用顺序存储结构表示 B.有两个指针域的链表就是二叉链表C.多重链表一定是非线性结构D.顺序存储结构一定是线性结构解析：解析：完全二叉树如果“根”从 1 开始编号，则第 i 结点的左孩子编号为 2i，右孩子为 2i+1，双亲编号为(i2)下取整，空间紧密适合顺序存储结构。所以选项 A 正确。 小提示：取整是指取不超过实数 x 的
14、最大整数，称为 x 的整数部分。上取整就是对实数取大于当前实数的第一个整数：下取整就足对当前实数去掉小数取整。6.下列各排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析：解析：快速排序、冒泡排序最坏情况下时间复杂度是 o(n 2 )；希尔排序最坏情况下时间复杂度是0(n 12 )。堆排序最坏情况下时间复杂度是 O(nlog 2 n)，所以选项 A 正确。7.某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定 B.5C.4
15、D.6解析：解析：循环队列用数组 A0：m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是(rear-front+m)m=(5-10+In)m=(m-5)m。因为本题中的 m 值不确定，所以(m-5)m的值不能确定。所以选项 A 正确。8.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFGH B.HFDBGECAC.HGFEDCBAD.ACEGBDFH解析：解析：由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列HFDB
16、ACEG，可以得到，HFDBt 为 A 的左子树，CEG 为 A 的右子树。同理依次对左子树 HFDB 和右子树 CEG 进行同样的推理，得到这个二叉树的结构如下：9.某带链栈初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为（分数：2.00）A.不确定 B.10C.1D.0解析：解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=10，bottom=20 时，不能确定栈中的元素个数，所以选项 A 正确。10.设表的长度为 15。则在最坏情况下，快速排序所需要的比较次数为（分数：2
17、.00）A.105 B.55C.15D.75解析：解析：假设线性表的长度为 n，在最坏情况下，快速排序法的比较次数是 n(n-1)2。题中 n=15，所以 15*142=105。所以选项 A 正确。11.设循环队列的存储空间为 Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为（分数：2.00）A.不确定 B.49C.51D.50解析：解析：循环队列用数组 Q1：100存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是(rear-front+100)100，题目中首指针 rear 的值未知，所以循环队列中的元素个
18、数不能确定。所以选项 A 正确。12.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的中序序列为（分数：2.00）A.HDBEAFCG B.HDEBFGCAC.ABDHECFGD.ABCDEFGH解析：解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。可以得到其结构如下：13.下列叙述中正确的是（分数：2.00）A.解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的 B.解决一个问题可以有不同的算法，但它们的时间复杂度必
19、定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关解析：解析：算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有 10 种左右算法，它们复杂度显然是不一样的。所以选项 A 正确。14.设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找 B.顺序查找C.寻找最大项D.寻找最小项解析：解析：有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x 与线性表的中间项进行比较，若中间项的值等于 x，则说明查到；若小于中间项的值则在线性表的前半部分以
20、相同的方法进行查找；若大于中间项的值则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较 log 2 n 次。顺序查找、寻找最大项、寻找最小项，在最坏情况下，比较次数都是 n 次。所以选项 A 正确。15.某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为（分数：2.00）A.1B.0C.20D.不确定 解析：解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=bottom=20 时，不能确定栈中的元素个数。所以选项 D 正确。16.某二叉树的前序序列为 A
21、BDFHCEG，中序序列为 HFDBACEG。该二叉树的后序序列为（分数：2.00）A.HFDBGECA B.ABCDEFGHC.HGFEDCBAD.ACEGBDFH解析：解析：由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列HFDBACEG，可以得到，HFDB 为 A 的左子树，CEG 为 A 的右子树。同理依次对左子树 HFDB 和右子树 CEG 进行同样的推理，得到这个二叉树的结构如下：17.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与问题规模无关 B.算法的时间复杂度与计算机系统无关C.算法的时间复杂度与空间复杂度没有必然的联系D.算
22、法的空间复杂度与算法运行输出结果的数据量无关解析：解析：一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n)f(n)的极限值为不等于零的常数，则称 f(n)是T(n)的同数量级函数。记作 T(n)=O(f(n)，称 O(f(n)为算法的渐进时间复杂度，简称时间复杂度。所以选项 A 正确。18.设表的长度为 20。则在最坏情况下，冒泡排序的比较次数为（分数：2.00）A.90B.20C.19D.190 解析：解析：假设线性表的长度为 n，则在最坏情况下，冒泡排序的比较次数为 n(n-1)2。本题中，
23、n=20，所以 20*192=190。所以选项 D 正确。19.在带链栈中，经过一系列正常的操作后，如果 top=bottom，则栈中的元素个数为（分数：2.00）A.1B.0C.0 或 1 D.栈满解析：解析：链栈就是没有附加头结点的、运算受限的单链表。栈顶指针就是链表的头指针。如果栈底指针指向的存储单元中存有 1 元素，则当 top=bottom 时，栈中的元素个数为 1；如果栈底指针指向的存储单元中没有存元素，则当 top=bottom 时，栈中的元素个数为 0。所以选项 C 正确。20.设一棵树的度为 3，共有 27 个结点，其中度为 3，2，0 的结点数分别为 4，1，10。该树中度
24、为 1 的结点数为（分数：2.00）A.11B.12 C.13D.不可能有这样的树解析：解析：因为任一棵树中，结点总数=总分支数目+1，所以：27=(0*10+n 1 *1+2*1+3*4)+1。运算结果 n 1 =12。其中，n 1 表示叶子结点，所以选项 B 正确。21.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(f，a)，(d，b)，(c，d)，(c，e)，(a，c) 该数据结构为（分数：2.00）A.线性结构 B.循环队列C.循环链表D.非线性结构解析：解析：由结点之间的关系 R=(ea)，(d，b)，(e，d)，(c，e)，(a，c)可以得到，该数据结构为：“
25、f-a-c-e-d-b”。由此可知结点 f 没有前驱，结点 b 没有后继结点，并且其它的结点只有一个前驱结点和一个后继结点，所以该数据结构为线性结构。所以应选 A 选项。22.下列叙述中错误的是（分数：2.00）A.循环队列空的条件是队头指针与队尾指针相同 B.若二叉树没有叶子结点，则为空二叉树C.带链栈的栈底指针是随栈的操作而动态变化的D.若带链队列中只有一个元素，则队头指针与队尾指针必定相同解析：解析：初始化建空队时，令 front=rear=0，当队空时：front=rear；当队满时：front=rear 亦成立。因此，只凭等式 front=rear 无法判断队空还是队满。有两种方法处
26、理上述问题：另设一个标志位以区别队列是空还是满；少用一个元素空间，约定以“队列头指针 front 在队尾指针 rear 的下一个位置上”作为队列“满”状态的标志。即：队空时：front=rear；队满时：(rear+1)maxsize=front。所以选项 A 正确。23.带链栈空的条件是（分数：2.00）A.top=bottom=NULL B.top=-1 且 bottom=NULLC.top=NULL 且 boaom-1D.too=bottom=-1解析：解析：栈的链式存储结构称为链栈。在链栈中，只会出现栈空和非空两种状态。当栈为空时，有top=bottom=NULL；当栈非空时，top
27、指向链表的第一个结点(栈顶)。所以选项 A 正确。24.设一棵度为 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*n 3 )+1。运算结果 n 3 =1。其中，n 3 表示度为 3 的结点数，所以选项 A 正确。25.下列数据结构中，不能采用顺序存储结构的是（分数：2.00）A.栈B.堆C.队列D.非完全二叉树 解析：解析：堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全
28、二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。26.设二叉树共有 375 个结点，其中度为 2 的结点有 187 个。则度为 1 的结点个数是（分数：2.00）A.0 B.1C.188D.不可能有这样的二叉树解析：解析：二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 2 i-1 个结点；深度为 k 的二叉树至多有 2 k -1 个结点；对任何一棵二叉树 T，如果其终端结点数为 n 0 ，度为 2 的
29、结点数为 n 2 ，则 n 0 =n 2 +1。本题中，度为 2 的结点有 187 个，叶子结点应该有 187+1=188 个，度为 1 的结点个数=375187188=0。27.在带链队列中，经过一系列正常的操作后，如果 front=rear，则队列中的元素个数为（分数：2.00）A.0 或 1 B.0C.1D.人列满解析：解析：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的链式存储也称为链队列。为了便于操作，可给链队列添
30、加 1 个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空(0)或 1 时，front=rear。28.设一棵树的度为 3，其中没有度为 2 的结点，且叶子结点数为 5。该树中度为 3 的结点数为（分数：2.00）A.1B.2 C.3D.不可能有这样的树解析：解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，那么树中最少有一个结点的度为 3。而树中没有度为 2 的结点，叶子结点数为 5，度为 1 的结点下面只有一个叶子结点。因此，该树中含 2 个度为 3 的结点满足题目要求。29.设二叉树共有 500 个结点，其中叶子结
31、点有 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。30.下列叙述中正确的是（分数：2.00）A.带链栈的栈底指针是固定的B.
32、带链栈的栈底指针是随栈的操作而动态变化的 C.若带链队列的队头指针与队尾指针相同，则队列为空D.若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素解析：解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为 0 也可能为 1。
33、31.带链队列空的条件是（分数：2.00）A.front=rear=NULL B.front=rear=-1C.front=NULL 且 rear=-1D.front=-1 且 rear=NULL解析：解析：带链队列空的条件有两个：一个是 front=rear，一个是它们都等于空。32.设一棵树的度为 3，其中没有度为 2 的结点，且叶子结点数为 6。该树中度为 3 的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树 解析：解析：树的度是指一棵树中，最大的结点的度称为树的度。本题史树的度为 3，也就是最少有一个度为 3 的结点。要求没有度为 2 的结点，且叶子结点为 6，如果要有度为 3 的结点，那么最多只有 s 个叶了结点，而画不出 6 个叶子结点。因此这样的树是没有的。
