1、国家二级 C+机试（数据结构与算法）模拟试卷 13及答案与解析 一、选择题 1 下列数据结构中，不能采用顺序存储结构的是 （ A）栈 （ B）堆 （ C）队列 （ D）非完全二叉树 2 设二叉树共有 375个结点，其中度为 2的结点有 187个。则度为 1的结点个数是 （ A） 0 （ B） 1 （ C） 188 （ D）不可能有这样的二叉树 3 在带链队列中，经过一系列正常的操作后，如果 front=rear，则队列中的元素个数为 （ A） 0或 1 （ B） 0 （ C） 1 （ D）队列满 4 设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。该树中度为 3的结点数为 （
2、A） 1 （ B） 2 （ C） 3 （ D）不可能有这样的树 5 设二叉树共有 500个结点，其中叶子结点有 250个。则度为 2的结点个数是 （ A） 0 （ B） 1 （ C） 249 （ D）不可能有这样的二叉树 6 T列叙述中正确的是 （ A）带链栈的栈底指针是固定的 （ B）带链栈的栈底指针是随栈的操作而动态变化的 （ C）若带链队列的队头指针与队尾指针相同，则队列为空 （ D）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元 素 7 带链队列空的条件是 （ A） front=rear=NULL （ B） front=rear-=-1 （ C） front=NULL且 re
3、ar=-1 （ D） front=-1且 rear=NULL 8 设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 6。该树中度为 3的结点数为 （ A） 1 （ B） 2 （ C） 3 （ D）不可能有这样的树 9 下列叙述中正确的是 （ A）循环队列是线性结构 （ B）循环队列是线性逻辑结构 （ C）循环队列是链式存储结构 （ D）循环队列是非线性存储结构 10 设某棵树的度为 3，其中度为 3、 2、 1的结点个数分别为 3、 0、 4。则该树中的叶子结点数为 （ A） 7 （ B） 8 （ C） 6 （ D）不可能有这样的树 11 设有一个栈与一个队列的初始状态均为空。现有一
4、个序列 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， B， C， D， H， G， F， E 12 下列叙述中错误的是 （ A）具有两个根结点的数据结构一定属于非线性结构 （ B）具有两个以上指针域的链式结构一定属于非线性结构 （ C）具有两个以上叶子结点的数据结构一定属于非线性结构
5、 （ D）具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构 13 设一棵完全二叉树共有 700个结点，则此二叉树中的叶子结点数为 （ A） 85 （ B） 120 （ C） 250 （ D） 350 14 在深度为 7的满二叉树中，叶子结点的个数为 （ A） 32 （ B） 31 （ C） 64 （ D） 63 15 对下列二叉树 进行前序遍历的结果是 （ A） DYBEAFCZX （ B） YDEBFZXCA （ C） ABDYECFXZ （ D） ABCDEFXYZ 16 对如下二叉树 进行后序遍历的结果为 （ A） ABCDEF （ B） DBEAFC （ C） ABDECF
6、 （ D） DEBFCA 17 对长度为 n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 （ A） log2n （ B） n 2 （ C） n （ D） n+1 18 在长度为 64的有序线性表中进行顺序查找，最坏情况下需要 比较的次数为 （ A） 63 （ B） 64 （ C） 6 （ D） 7 19 下列叙述中正确的是 （ A）对长度为 n的有序链表进行查找，最坏情况下需要的比较次数为 n （ B）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (n 2) （ C）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (log2n) （ D）对长度为 n的
7、有序链表进行对分查找，最坏情况下需要的比较次数为 (nlog2n) 20 在长度为 n的有序线性表中进行二分查找，最坏情况下需要比较的次数是 （ A） O(n) （ B） O(n2) （ C） O(log2n) （ D） O(nlog2n) 21 下列数据结构中，能用二分法进行查找的是 （ A）顺序存储的有序线性表 （ B）线性链表 （ C）二叉链表 （ D）有序线性链表 22 冒泡排序在最坏情况下的比较次数是 （ A） n(n+1) 2 （ B） nlog2n （ C） n(n-1) 2 （ D） n 2 23 对长度为 10的线性表进行冒泡排序，最坏情况下需要比较的次数为 （ A） 9 （
8、 B） 10 （ C） 45 （ D） 90 24 对于长度为 n的线性表，在最坏情况下 ，下列各排序法所对应的比较次数中正确的是 （ A）冒泡排序为 n 2 （ B）冒泡排序为 n （ C）快速排序为 n （ D）快速排序为 n(n-1) 2 25 对长度为 n的线性表作快速排序，在最坏情况下，比较次数为 （ A） n （ B） n-1 （ C） n(n-1) （ D） n(n-1) 2 26 对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n-1) 2的排序方法是 （ A）快速排序 （ B）冒泡排序 （ C）直接插入排序 （ D）堆排序 27 下列排序方法中，最坏情况下比较次数最
9、少的是 （ A）冒泡排序 （ B）简单选择排序 （ C）直接插入排序 （ D）堆排序 国家二级 C+机试（数据结构与算法）模拟试卷 13答案与解析 一、选择题 1 【正确答案】 D 【试题解析】 堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种：栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。 【知识模块】 数据结构与算法 2 【正确答案】 A 【试题解析】 二叉树的 每个结点至多只有二棵子树 (不存在度大于 2的结点 )，二叉树的子树有左右之分，次序不能颠倒。二叉
10、树的第 i层至多有 2i-1个结点；深度为 k的二叉树至多有 2k-1个结点；对任何一棵二叉树 T，如果其终端结点数为n0，度为 2的结点数为 n2，则 n0=n2+1。本题中，度为 2的结点有 187个，叶子结点应该有 187+1=188个，度为 1的结点个数 =375-187-188=0。 【知识模块】 数据结构与算法 3 【正确答案】 A 【试题解析】 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端 (rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的链式存储也称为链队
11、列。为了便于操作，可给链队列添加 1个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空 (0)或 1时， front=rear。 【知识模块】 数据结构与算法 4 【正确答案】 B 【试题解析】 树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，那么树中最少有一个结点的 度为 3。而树中没有度为 2的结点，叶子结点数为 5，度为 1的结点下面只有一个叶子结点。因此，该树中含 2个度为 3的结点满足题目要求。 【知识模块】 数据结构与算法 5 【正确答案】 C 【试题解析】 二叉树的每个结点至多只有二棵子树 (不存在度大于 2的
12、结点 )，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i层至多有 2i-1个结点；深度为 k的二叉树至多有 2k-1个结点；对任何一棵二叉树 T，如果其终端结点数为n0，度为 2的结点数为 n2，则 n0=n2+1。本题中，叶子结点有 250个，度为 2的结点数为 n2=n0-1=250-1=249。 【知识模块】 数据结构与算法 6 【正确答案】 B 【试题解析】 栈 (stack)又名堆栈 ，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成
13、为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为 0也可能为 1。 【知识模块】 数据结构与算法 7 【正确答案】 A 【试题解析】 带链队列空的条件有两个： 一个是 front=rear，一个是他们都等于空。 【知识模块】 数据结构与算法 8 【正确答案】 D 【试题解析】 树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，也就是最少有一个度为 3的结点。要求没有度为 2的结点，且叶子结点为6，如果要有度为 3的结点，那么最多只有
14、5个叶子结点，而画不出 6个叶子结点。因此这样的树是没有的。 【知识模块】 数据结构与算法 9 【正确答案】 A 【试题解析】 为充分利用向量空间，克服 “假溢出 ”现象的方法是：将向量空间想象为一 个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列 (Circular Queue)。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。 【知识模块】 数据结构与算法 10 【正确答案】 A 【试题解析】 树的度是指一棵树中，最大的结点的度称为 “树的度 ”。根据题目可
15、知本树中没有度为 2的结点。树的总结点 =(度 1*个数 +度 2*个数 )+1 ，这里我们设总结点数为 n，那么 n=3*3+2*0+1*4+1=14。树的叶子结点数等于总结点减去所有度不为 0的结点，也就是 14-34=7。 【知识模块】 数据结构与算法 11 【正确答案】 A 【试题解析】 栈 (stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是D， C， B， A。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端 (rear)进行插入操作，和栈一样，队列足一种操
16、作受限制的线性表。进行插入操作的 端称为队尾，进行删除操作的端称为队头。因此，队的出队顺序是，先入先出，所以顺序是 E， E， G， H。最后的顺序是： D， C， B， A， E， E， G， H。 【知识模块】 数据结构与算法 12 【正确答案】 B 【试题解析】 非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。 【知识模块】 数据结构与算法 13 【正确答案】 D 【试题解析】 具有 n个结点的完全二叉树的深度为 long2n+1，计算出该完全二叉树的深度为 10。 设度为 0的结点
17、(即叶子结点 )为 n0,度为 1的结点为 n1，度为2的结点为 n2，总结点数为 n，深度为 k。 n=n1+n2+n0，由于 n0=n2+1则 nv=n0-1，故 n=n1+n0-1+n0=n1+2n0-1。由于完全二叉树中度为 1的结点数只有两种可能：0或 1。 假设度为 1的结点数为 0即满二叉树，根据满二叉树的定义，其 2m-1个结点，根据以上计算所得的深度 10来计算，应有 2m-1=1024-1=1023个结点，显然与题目中 700个结点不符。因此，度为 1的结点数必然为 1。 故 n=n1+2n0-1=1+2n0-1=2n0，则 n0=-n 2=700 2=350。 【知识模块
18、】 数据结构与算法 14 【正确答案】 C 【试题解析】 所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。也就是在满二叉树中，每一层上的结点数都是最大结点数，即在满二叉树的第 k层上有 2k-1个结点，且深度为 m的满二叉树有 2m-1个结点。对于深度为 7的满二叉树，叶子结点所在的是第 7层，一共有 27-1=64个叶子结点。全部结点共 27-1=127个。 【知识模块】 数据结构与算法 15 【正确答案】 C 【试题解析】 二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则： 访问根结点； 前序遍历左子树； 前序遍历右子树。可见，前序遍历二叉树的过程
19、是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是 ABDYECFXZ。 【知识模块】 数据结构与算法 16 【正确答案】 D 【试题解析】 所谓后序遍历是指在访问根据结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然 先遍历左子树，然后遍历右子树，最后访问根点。因此，后序遍历二叉树的过程也是一个递归过程。其简单描述为：若二叉树为空，则结束返回；否则，先后序遍历左子树，然后后序遍历右子树，最后访问根结点。对于后序遍历，第一个访问的结点一定是最左下的结点，最后一个访问的结点一定是根结点，所以选项 D)为正确答案。
20、【知识模块】 数据结构与算法 17 【正确答案】 C 【试题解析】 在进行顺序查找过程中，如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中的所有元 素进行比较，这是顺序查找的最坏情况，需要比较的次数为 n次。 【知识模块】 数据结构与算法 18 【正确答案】 B 【试题解析】 顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法是：从线性表的第一元素开始，依次将线性表中的元素与被查找的元素进行比较，若相等则表示找到 (即查找成功 )，若线性表中所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素 (即
21、查找失败 )。如果线性表中的第一个元素就是要查找的元素，则只需要做一次比较就查找成功；但如果要查找的元素是线 性表中的最后一个元素，或者要查找元素不在线性表中，则需要与线性表中所有元素进行比较，这是顺序查找的最坏情况，比较次数为线性表的长度。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 本题主要考查的知识点为查找技术。顺序查找的使用情况： 线性表为无序表； 表采用链式存储结构。二分法查找只适用于顺序存储的有序表，并不适用于线性链表。 【知识模块】 数据结构与算法 20 【正确答案】 C 【试题解析】 对于长度为 n的有序线性表，在最坏情况下，二分法查找只需比较log2n
22、次，而顺序查找需要比较 n次。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 二分法查找只适应于顺序存储的有序表。有序表是指线性表中的元素按值非递减排序 (即从小到大，但允许相邻元素值相等 )的表。 【知识模块】 数据结构与算法 22 【正确答案】 C 【试题解析】 对 n个结点的线性表采用冒泡排序，在最坏情况下，冒泡排序需要经过 n 2遍的从前往后的扫描和 n 2遍的从后往前的扫描，需要的比较次数为n(n-1) 2。 【知识模块】 数据结构与算法 23 【正确答案】 C 【试题解析】 线性表的长度为 n，最坏情况下冒泡排序需要比较的次数为 n(n-1) 2。 【知识模块
23、】 数据结构与算法 24 【正确答案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后的扫描和 n 2遍的从后往前的扫描，需要的比较次数为 n(n-1）2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。 【知识模块】 数据结构与算法 25 【正确答案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后的扫描和 n 2遍的从后往前的扫描，需要的比较次数为 n(n-1)2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。 【知识模块】 数据结构与算法 26 【正确答案】 D 【试题解析】 各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序 n(n-1) 2、快速排序 n(n-1) 2、简单插入排序 n(n-1) 2、希尔排序 O(n1.5)、简单选择排序 n(n-1) 2、堆排序 O(nlog2n)。 【知识模块】 数据结构与算法 27 【正确答案】 D 【试题解析】 冒泡排序、简单选择排序和直接插入排序法在最坏的情况下比较次数为： n(n-1) 2。而堆排序法在最坏的情况下需要比较的次数为 O(nlog2n)。其中堆排序的比较次数最少。 【知识模块】 数据结构与算法
