1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 12及答案与解析 一、选择题 1 带链栈空的条件是 （ A） top=bottom=NULL （ B） top=-1bottom=NULL （ C） top=NULL且 bottom-1 （ D） top=bottom=-1 2 设一棵度为 3的树，其中度为 2， 1， 0的结点数分别为 3， 1， 6。该树中度为 3的结点数为 （ A） 1 （ B） 2 （ C） 3 （ D）不可能有这样的树 3 下列数据结构中，不能采用顺序存储结构的是 （ A）栈 （ B）堆 （ C）队列 （ D）非完全二叉树 4 设二叉树共有 375个结点，其
2、中度为 2的结点有 187个。则度为 1的结点个数是 （ A） 0 （ B） 1 （ C） 188 （ D）不可能有这样的二叉树 5 在带链队列中，经过一系列正常的操作后，如果 front=rear，则队列中的元素个数为 （ A） 0或 1 （ B） 0 （ C） 1 （ D）队列满 6 设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。该树中度为 3的结点数为 （ A） 1 （ B） 2 （ C） 3 （ D）不可能有这样的树 7 设二叉树共有 500个结点，其中叶子结点有 250个。则度为 2的结点个数是 （ A） 0 （ B） 1 （ C） 249 （ D）不可能有这样的二
3、叉树 8 下列叙述中正确的是 （ A）带链栈的栈底指针是固定的 （ B）带链栈的栈底指针是随栈的操作而动态变化的 （ C）若带链队列的队头指针与队尾指针相同，则队列为空 （ D）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素 9 带链队列空的条件是 （ A） front=rear=NULL （ B） front=rear=一 1 （ C） from=NULL且 rear=-1 （ D） front=-1且 rear=NULL 10 设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 6。该树中度为 3的结点数为 （ A） 1 （ B） 2 （ C） 3 （ D）不可能有这样
4、的树 11 下列叙述中正确的是 （ A）循环队列是线性结构 （ B）循环队列是线性逻辑结构 （ C）循环队列是链式存储结构 （ D）循环队列是非线性存储结构 12 设某棵树的度为 3，其中度为 3、 2、 1的结点个数分别为 3、 0、 4。则该树中的叶子结点数为 （ A） 7 （ B） 8 （ C） 6 （ D）不可能有这样的 树 13 设有一个栈与一个队列的初始状态均为空。现有一个序列 A,B,C,D,E,F,G,H。先分别将序列中的前 4个元素依次入栈，后 4个元素依次入队；然后分别将栈中的元素依次退栈；再将队列中的元素依次退队。最后得到的序列为 （ A） D,C,B,A,E,F,G,H
5、 （ B） D,C,B,A， H,G,F,E （ C） A,B,C,D,E,F,G,H （ D） A,B,C,D,H,G,EE 14 下列叙述中错误的是 （ A）具有两个根结点的数据结构一定属于非线性结构 （ B）具有两个以上指针域的链式结构一定属于非 线性结构 （ C）具有两个以上叶子结点的数据结构一定属于非线性结构 （ D）具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构 15 下列结构中属于线性结构链式存储的是 （ A）双向链表 （ B）循环队列 （ C）二叉链表 （ D）二维数组 16 下列叙述中错误的是 （ A）循环链表中有一个表头结点 （ B）循环链表的存储空间是连续的
6、 （ C）循环链表实现了空表与非空表运算的统一 （ D）循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 17 度为 3的一棵树共有 30个结点 ，其中度为 3、 1的结点个数分别为 3、 4。则该树中的叶子结点数为 （ A） 14 （ B） 15 （ C） 16 （ D）不可能有这样的树 18 在长度为 97的顺序有序表中作二分查找，最多需要的比较次数为 （ A） 7 （ B） 96 （ C） 48 （ D） 6 19 下列结构中属于非线性结构的是 （ A）二叉链表 （ B）二维数组 （ C）循环队列 （ D）双向链表 20 从表中任何一个结点位置出发就可以不重复地访问到表中其
7、他所有结点的链表是 （ A）循环链表 （ B）双向链表 （ C）单向链表 （ D）二 叉链表 21 设二叉树的前序序列与中序序列均为 ABCDEFGH，则该二叉树的后序序列为 （ A） HGFEDCBA （ B） ABCDEFGH （ C） ABCDHGFE （ D） DCBAHGFE 22 设某棵树的度为 3，其中度为 3、 1、 0的结点个数分别为 3、 4、 15。则该树中总结点数为 （ A） 22 （ B） 30 （ C） 35 （ D）不可能有这样的树 23 下列叙述中正确的是 （ A）矩阵是非线性结构 （ B）数组是长度固定的线性表 （ C）对线性表只能作插入与删除运算 （ D）线
8、性表中各元素的数 据类型可以不同 24 在快速排序法中，每经过一次数据交换 (或移动 )后 （ A）能消除多个逆序 （ B）只能消除一个逆序 （ C）不会产生新的逆序 （ D）消除的逆序个数一定比新产生的逆序个数多 25 线性表的长度为 n。在最坏情况下，比较次数为 n-1的算法是 （ A）顺序查找 （ B）有序表的插入 （ C）寻找最大项 （ D）同时寻找最大项与最小项 26 设某棵树的度为 3，其中度为 2、 1、 0的结点个数分别为 3、 4、 15。则该树中总结点数为 （ A） 22 （ B） 30 （ C） 35 （ D）不可能有 这样的树 27 下列叙述中错误的是 （ A）向量是线
9、性结构 （ B）非空线性结构中只有一个结点没有前件 （ C）非空线性结构中只有一个结点没有后件 （ D）只有一个根结点和一个叶子结点的结构必定是线性结构 28 在希尔排序法中，每经过一次数据交换后 （ A）能消除多个逆序 （ B）只能消除一个逆序 （ C）不会产生新的逆序 （ D）消除的逆序个数一定比新产生的逆序个数多 29 设二叉树的后序序列与中序序列均为 ABCDEFGH，则该二叉树的前序序列为 （ A） HGFEDCBA （ B） ABCDEFGH （ C） ABCDHGFE （ D） DCBAHGFE 30 下列叙述中正确的是 （ A）循环队列是队列的链式存储结构 （ B）能采用顺序存
10、储的必定是线性结构 （ C）所有的线性结构都可以采用顺序存储结构 （ D）具有两个以上指针的链表必定是非线性结构 31 设循环队列的存储空间为 Q(1： m)，初始状态为 front=rear=m。经过一系列正常的操作后， front=1， rear=m。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为 （ A） m （ B） m-1 （ C） m-2 （ D） 1 32 设二叉树的后序序列为 DGHEBIJFCA，中序序列为 DBGEHACIFJ。则前序序列为 （ A） ABDEGHCFIJ （ B） JIHGFEDCBA （ C） GHIJDEFBCA （ D） ABCDEFG
11、HIJ 国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 12答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 栈的链式存储结构称为链栈。在链栈中，只会出现栈空和非空两种状态。当栈为空时，有 too=bottom=NuLL；当栈非空时， top指向链表的第一个结点 (栈顶 )。 所以选项 A正确。 【知识模块】 数据结构与算法 2 【正确答案】 A 【试题解析】 因为任一棵树中，结点总数 =总分支数目 +1，所以： 6+1+3+n3=(0*6+1*1+2*3+3*n3)+1。运算结果 n3=1。其中， n3表示度为 3的结点数，所以选项 A正确。 【知识模块】 数据结构与算
12、法 3 【正确答案】 D 【试题解析】 堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是 一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。 【知识模块】 数据结构与算法 4 【正确答案】 A 【试题解析】 二叉树的每个结点至多只有二棵子树 (不存在度大于 2的结点 )，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i层至多有 2i-1个结点；深度为 k的二叉树至多有 2k-1个结点：对任何一棵二叉树 T，如果其终端结点数为n0，度为 2的结点数为 n2，则 n
13、0=n2+1。本题中，度为 2的结点有 187个，叶子结点应该有 187+1=188个，度为 1的结点个数 =375一 187-188=0。 【知识模块】 数据结构与算法 5 【正确答案】 A 【试题解析】 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端 (rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的链式存储也称为链队列 .为了便于操作，可给链队列添加 1个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空 (0)或 1
14、时， front=rear。 【知识 模块】 数据结构与算法 6 【正确答案】 B 【试题解析】 树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，那么树中最少有一个结点的度为 3。而树中没有度为 2的结点，叶子结点数为 5，度为 1的结点下面只有一个叶子结点。因此，该树中含 2个度为 3的结点满足题目要求。 【知识模块】 数据结构与算法 7 【正确答案】 C 【试题解析】 二叉树的每个结点至多只有二棵子树 (不存在度大于 2的结点 )，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i层至多有 2i-1个结点；深度为 k的二叉树 至多有 2k1个结点；对任何一棵二叉树 T，
15、如果其终端结点数为n0，度为 2的结点数为 n2，则 n0=n2+1。本题中，叶子结点有 250个，度为 2的结点数为 n2=n0-1=250-1=249。 【知识模块】 数据结构与算法 8 【正确答案】 B 【试题解析】 栈 (stack)又名堆栈 ，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈项元素；从一个栈删除元素又称作出栈或退栈，它是把栈项元素删除掉，使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链
16、队列的队头指针与队尾指针相同，则队列可能为 0也可能为 1。 【知识模块】 数据结构与算法 9 【正确答案】 A 【试题解析】 带链队列空的条件有两个： 一个是 front=rear，一个是它们都等于空。 【知识模块】 数据结构与算法 10 【正确答案】 D 【试题解析】 树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，也就是最少有一个度为 3的结点。要求没有度为 2的结点，且叶子结点为6，如果要有度为 3的结点，那么最多只有 5个叶子结点，而画不出 6个叶子结点。因此这样的树是没有的。 【知识模块】 数据结构与算法 11 【正确答案】 A 【试题解析】 为充分利用向量空间，
17、克服 “假溢出 ”现象的方法是：将向量空间想象为一个 首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列 (CircularQueue)。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。 【知识模块】 数据结构与算法 12 【正确答案】 A 【试题解析】 树的度是指一棵树中，最大的结点的度称为 “树的度 ”。根据题目可知本树中没有度为 2的结点。树的总结点 =(度 1*个数 +度 2*个数 )+1 ，这里我们设总结点数为 n，那么 n=3*3+2*0+1*4+1=1
18、4。树的叶子结点数等于总结点减去所有度不为 0的结点，也就是 14-3-4=7。 【知识模块】 数据结构与算法 13 【正确答案】 A 【试题解析】 栈 (stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是D,C,B,A。 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端 (front)进行删除操作，而在表的后端 (rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插 入操作的端称为队尾，进行删除操作的端称为队头。因此，队的出队顺序是，先入先出，所以顺序是 E， F,G,H。最后的顺序是：
19、D,C,B,A,E,F,G,H。 【知识模块】 数据结构与算法 14 【正确答案】 B 【试题解析】 非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 数据元素之间的关系有两种不同的表示方法：顺 序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方
20、式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。 【知识模块】 数据结构与算法 16 【正确答案】 B 【试题解析】 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它 不一定要是连续的存储空间，也可以是断开的空间。 【知识模块】 数据结构与算法 17 【正确答案】 B 【试题解析】 根据题目可知本树中还有度为 2的结点。树的总结点 =(度 1*个数 +度 2*个数 )+1 ，这里我们设度为 2的结点数为 x，那么30=3*3+2*x+1*4+1=2*x+14，由此可计算出 x=8。树的叶子结点数等
21、于总结点减去所有度不为 0的结点，也就是 30 384=15。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题解析】 二分查找又称折半查找，优点是比较次数 少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式： k=log2n。其中 n代表长度， k为比较次数。本题中可以计算出 k=7。 【知识模块】 数据结构与算法 19 【正确答案】 B 【试题解析】 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串：常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。循环队列、双向链表和二叉链
22、表都是线性结构，而二维数组是非线性结构。 【知识模块】 数据结构与算法 20 【正确答案】 A 【试题解析】 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，循环一圈就访问到了表中其它所有结点而不重复。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 前序遍历 (DLR)是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右；中序遍历 (LDR)是二叉树遍历的一种，也叫做中根遍历、中序周游，可记做左根右，后序遍历 (LRD)是二叉树遍历的一种，也叫做后根遍历、后序周游，可 记做左右根。根据题中前序和中序序列
23、均为ABCDEFGH，可画出二叉树，该二叉树是一个子结点全部在右侧二叉树，然后根据后序遍历方法，可得出后序遍历为 HGFEDCBA。 【知识模块】 数据结构与算法 22 【正确答案】 B 【试题解析】 本题采用画图法来求出结果。首先先画出包含 3个度为 3的结点；然后再添加 4个度为 1的结点，此时最大度为 0的结点数为 8。根据题目中描述的度为 0的结点数有 15个，这时要在书中添加度为 2的结点，直到度为 0的结点数位 15。画图结束后，不管是什么样的树，总结点数都是 30。 【知识模块】 数据结构与算法 23 【正确答案】 B 【试题解析】 所谓数组，就是相同数据类型的元素按一定顺序排列
24、的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分它们的变量的集合，这个名字称为数组名，编号称为下标。 【知识模块】 数据结构与算法 24 【正确答案】 A 【试题解析】 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个 数据变成有序序列。 【知识模块】 数据结构与算法 25 【正确答案】 C 【试题解析】 寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为 n-1。 【知识模块】 数据结构与算法 26
25、【正确答案】 D 【试题解析】 本题采用画图法来求出结果。首先先画出包含 3个度为 2的结点；然后再添加 4个度为 1的结点。根据题目中描述的度为 0的结点数有 15个，这时要在书中添加度为 3的结点，不管怎么添加都不能添加出 15个度为 0的结点，因此不可能有这样的树 。 【知识模块】 数据结构与算法 27 【正确答案】 D 【试题解析】 线性结构是 n个数据元素的有序 (次序 )集合。 集合中必存在唯一的一个 “第一个元素 ”； 集合中必存在唯一的一个 “最后的元素 ”； 除最后元素之外，其它数据元素均有唯一的 “后件 ”； 除第一元素之外，其它数据元素均有唯一的 “前件 ”。相对应于线性
26、结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。向量符合线性结构特点。非线性结构也会存在只有一个根结点和叶子结点的情况。 【知识模块】 数据结构与算法 28 【正确答案】 A 【试题解析】 希尔排序法 (缩小增量法 )属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。插入排序能够消除多个逆序，也会产生新的逆序。消除的逆序与新产生的逆序有多有少。 【知识模块】 数据结构与算法 29 【正确答案】 A 【试题解析】 后序遍历中，最后一个字母是根结点，也就是 H是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树， H后面没有，因此该树没有右子
27、树。同理，可判断出该树是第一个完全的左子树。由此可画出这个二叉树，然后根据二叉 树可的前序序列为 HGFEDCBA。 【知识模块】 数据结构与算法 30 【正确答案】 C 【试题解析】 根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。所有的线性结构都可以采用顺序存储结构。 【知识模块】 数据结构与算法 31 【正确答案】 C 【试题解析】 经过一系列正常的操作后， front=1， rear=m，那么最坏情况下需要的比较次数为 rear-front-1=m-1一 1=m-2。 【知识
28、模块】 数据结构与算法 32 【正确答案】 A 【试题解析】 后序遍历中，最后一个字母是根结点，也就是 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的右结点。由此可画出这个二叉树，然后根据二叉树可的前序序列为 ABDEGHCFIJ。 【知识模块】 数据结构与算法
