国家二级公共基础知识（数据结构与算法）模拟试卷19
单项选择题
1.设一棵完全二叉树共有700个结点，则此二叉树中的叶子结点数为(D)
A. 85
B. 120
C. 250
D. 350
解析：①具有n个结点的完全二叉树的深度为[long2n]+1，计算出该完全二叉树的深度为10。②设度为0的结点(即叶子结点)为n0，度为1的结点为n1，度为2的结点为n2，总结点数为n，深度为k。n=n1+n2+n0，由于n0=n2+1则n2=n0-1，故n=n1+n0-1+n0=n1+2n0-1。由于完全二叉树中度为1的结点数只有两种可能：0或1。③假设度为1的结点数为0即满二叉树，根据满二叉树的定义，其2m-1个结点，根据以上计算所得的深度10来计算，应有210一1=1024-1=1023个结点，显然与题目中700个结点不符。因此，度为1的结点数必然为I。故n=n1+2n0-1=1+2n0-1=2n0，则n0=n／2=700／2=350。
2.在深度为7的满二叉树中，叶子结点的个数为(C)
A. 32
B. 31
C. 64
D. 63
解析：所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。也就是在满二叉树中，每一层上的结点数都是最大结点数，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。对于深度为7的满二叉树，叶子结点所在的是第7层，一共有27-1=64个叶子结点。全部结点共27-1=127个。
3.对下列二叉树
(C)
A. DYBEAFCZX
B. YDEBFZXCA
C. ABDYECFXZ
D. ABCDEFXYZ
解析：二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则：①访问根结点；②前序遍历左子树；⑨前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。
4.对如下二叉树
(D)
A. ABCDEF
B. DBEAFC
C. ABDECF
D. DEBFCA
解析：所谓后序遍历是指在访问根据结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根点。因此，后序遍历二叉树的过程也是一个递归过程。其简单描述为：若二叉树为空，则结束返回；否则，先后序遍历左子树，然后后序遍历右子树，最后访问根结点。对于后序遍历，第一个访问的结点一定是最左下的结点，最后一个访问的结点一定是根结点，所以选项D为正确答案。
5.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为(C)
A. log2n
B. n／2
C. n
D. n+l
解析：在进行顺序查找过程中，如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中的所有元素进行比较，这是顺序查找的最坏情况，需要比较的次数为n次。
6.在长度为64 有序线性表中进行顺序查找，最坏情况下需要比较的次数为(B)
A. 63
B. 64
C. 6
D. 7
解析：顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法是：从线性表的第一元素开始，依次将线性表中的元素与被查找的元素进行比较，若相等则表示找到(即查找成功)，若线性表中所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素(即查找失败)。如果线性表中的第一个元素就是要查找的元素，则只需要做一次比较就查找成功；但如果要查找的元素是线性表中的最后一个元素，或者要查找元素不在线性表中，则需要与线性表中所有元素进行比较，这是顺序查找的最坏情况，比较次数为线性表的长度。
7.下列叙述中正确的是(A)
A. 对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B. 对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n／2)
C. 对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)
D. 对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)
解析：本题主要考查的知识点为查找技术。顺序查找的使用情况：①线性表为无序表；②表采用链式存储结构。二分法查找只适用于顺序存储的有序表，并不适用于线性链表。
8.在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是(C)
A. O(n)
B. O(n2)
C. O(log2n)
D. O(nlog2n)
解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。
9.下列数据结构中，能用二分法进行查找的是(A)
A. 顺序存储的有序线性表
B. 线性链表
C. 二叉链表
D. 有序线性链表
解析：二分法查找只适应于顺序存储的有序表。有序表是指线性表中的元素按值非递减排序(即从小到大，但允许相邻元素值相等)的表。
10.冒泡排序在最坏情况下的比较次数是(C)
A. n(n+1)／2
B. nlog2n
C. n(n一1)／2
D. n／2
解析：对n个结点的线性表采用冒泡排序，在最坏情况下，冒泡排序需要经过n／2遍的从前往后的扫描和n／2遍的从后往前的扫描，需要的比较次数为n(n-1)／2。
11.对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为(C)
A. 9
B. 10
C. 45
D. 90
解析：线性表的长度为n，最坏情况下冒泡排序需要比较的次数为n(n-1)／2。
12.对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是(D)
A. 冒泡排序为n／2
B. 冒泡排序为n
C. 快速排序为n
D. 快速排序为n(n一1)／2
解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后的扫描和n／2遍的从后往前的扫描，需要的比较次数为n(n-1)／2。快速排序法也是一种互换类的排序方法，但由于它
本文档预览：3600字符，共7864字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
