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