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