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