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