1、数据结构与算法练习试卷 6及答案与解析 1 一棵具有 5层的完全二叉树中，结点总数最少是 ( )。 （ A） 15 （ B） 5 （ C） 16 （ D） 31 2 设 n、 m为一棵二叉树上的两个结点，在中序遍历时，若 n在 m的前面，则( )。 （ A） n为树的左子树上的结点， m为右子树上的结点 （ B） n是 m的祖先结点 （ C） n的层次比 m层次高 （ D） n在 m的左方 3 对于深度为 n，结点数为 k，有 m个叶子结点的满二叉树，下列关系正确的是( )。 （ A） k=m+n （ B） k=-2“-1 （ C） n+m=2k （ D） re=k-1 4 快速排序方法在 (
2、 )条件下最不利于发挥其长处。 （ A）待排序序列中含有多个相同关键字 （ B）待排序序列数据基本有序 （ C）待排序序列数据量很大 （ D）待排序序列元素个数为奇数 5 在每一趟排序时，都将待排序序列中最大关键字选出来，并将此关键字从待排序序列中删除，继续对剩余元素进行同样操作的排序方法称之为 ( )。 （ A）快速排序 （ B）堆排序 （ C）起泡捧序 （ D）选择排序 6 设有 1000个无序的元素，希望用最快的方式挑 选出其中前 10个最大元素，效率最高的排序方法是 ( )。 （ A）堆排序 （ B）快速排序 （ C）基数排序 （ D）起泡排序 7 设哈希表长 m=14，哈希函数 H(
3、key)=key%ll，表中已经有 4个结点： addr(13)=4； addr(28)=5 addr(51)=6； addr(77)=7 如果用线性探测再与散列法处理冲突，关键字为 49的结点地址为 ( )。 （ A） 8 （ B） 5 （ C） 9 （ D） 3 8 对于一个序列中的若干元素，若想得到 某个元素之前的部分排序，最好采用什么排序方法 ? ( ) （ A）快速排序 （ B）堆排序 （ C）基数排序 （ D）希尔排序 9 采用顺序查找法查找长度为 n的线性表时，每个元素的平均查找长度为 ( )， （ A） (n+1)/2 （ B） (n-1)/2 （ C） n/2 （ D） n
4、10 一个有序表 2， 4， 7， 12， 23， 45， 62， 76， 77， 89， 93， 95， 100，若采用二分查找法查找值为 93的关键字，需要 ( )次比较才能查找成功。 （ A） 1 （ B） 8 （ C） 2 （ D） 4 11 一棵二叉树的前序遍历结点顺序为 EACBDGF，中序遍历结点顺序为ABCDEFG，则其后序遍历结点顺序为 ( )。 （ A） EGFACDB （ B） EGACDFB （ C） BDCAFGE （ D） BDCFAGE 12 对以下关键字序列用快速排序方法排序速度最慢的是 ( )。 （ A） 15， 21， 5， 12， 9， 20， 31 （
5、B） 5， 9， 12， 15， 20， 21， 31) （ C） 15， 9， 12， 31， 21， 20， 5 （ D） 21， 20， 31， 12， 15， 5， 9) 13 用 堆排序方法，在最坏情况下的时间复杂度为 ( )。 （ A） O(n+1) （ B） O(n2) （ C） O(log2n) （ D） O(n log2n) 14 给定如下一组关键字序列 49， 38， 65， 97， 76， 13， 27， 49， 55， 04，采用希尔排序，则第二趟排序后的结果为 ( )。 （ A） 13， 04， 49， 38， 27， 49， 55， 65， 97， 76 （ B）
6、13， 27， 49， 55， 04， 49， 38， 65， 97， 76 （ C） 04， 13， 27， 49， 49， 38， 55， 65， 76， 97 （ D） 04， 13， 27， 38， 49， 49， 55， 65， 76， 97 15 关于二叉树，下列说法不正确的是 ( )。 （ A）在第 i层上最多有 2i-1个结点 （ B）深度为 k的二叉树最多有 2k-1个结点 （ C）相同层次的满二叉树结点数比完全二叉树结点多 （ D）深度为 k的满二叉树结点数一定为 2k-1个 16 元素 ABCDEF按序进入队列，则队列的出队顺序为 ( )。 （ A） FEDCBA （ B
7、） ABCDEF （ C） DCBAEF （ D） ABFEDC 17 在判断表达式中括号是否匹配的算法中，采用 ( )数据结构最佳。 （ A）线性表的顺序存储结构 （ B）线性表的链式存储结构 （ C）广义表 （ D）栈 18 若待排序序列已基本有序，要使它完全有序，从关键码的比较次数和移动次数考虑，应当采用的排序方法是 ( )。 （ A）直接插入排序 （ B）快速排序 （ C）直接选择排序 （ D）归并排序 19 对一棵二叉树的中序遍历序列中，根结点的左边包括 ( )。 （ A）左子树上的叶子结点 （ B）右子树上的所有结点 （ C）左子树上的所 有结点 （ D）右子树上的叶子结点 20
8、线索二叉树是一种 ( )结构。 （ A）逻辑 （ B）存储 （ C）线性 （ D）物理 21 下图 所示是一棵二叉树，其后序遍历序列是 ( )。（ A） DEBGFCA （ B） ABCDEFG （ C） DEBFGCA （ D） DBEACGF 22 如下图 所示，下列说法正确的是 ( )。（ A）此树不是满二叉树也不是完全二叉树 （ B）中序遍历序列是 HIDBEACFG （ C）此树是完全二叉树，也是满二叉树 （ D）以上说法均不正确 23 栈结构通 常采用的两种存储结构是 ( )。 （ A）顺序存储结构和链表存储结构 （ B）散列方式和索引方式 （ C）后进先出结构和顺序存储结构 （
9、D）线性存储结构和非线性存储结构 数据结构与算法练习试卷 6答案与解析 1 【正确答案】 C 【试题解析】 具有 5层的树结点最少的是完全二叉树，第 5层只有一个结点，其他 4层是由满二叉树构成。 【知识模块】 数据结构与算法 2 【正确答案】 D 【知识模块】 数据结构与算法 3 【正确答案】 B 【知识模块】 数据结构与算法 4 【正确答案】 C 【知识模块】 数据结构与算法 5 【正确答案】 C 【知识模块】 数据结构与算法 6 【正确答案】 A 【知识模块】 数据结构与算法 7 【正确答案】 A 【知识模块】 数据结构与算法 8 【正确答案】 B 【知识模块】 数据结构与算法 9 【正
10、确答案】 A 【知识模块】 数据结构与算法 10 【正确答案】 D 【知识模块】 数据结构与算法 11 【正确答案】 C 【试题解析】 由前序遍历序列得知 E是根结点，由中 序序列可知： A、 B、 C、 D在左子树上，且是左子树的中序序列， A是左子树上的根， C是 A的右子结点，B、 D分别是 C的左右结点， F、 G在右子树上，且是右子树上的中序序列， G是右子树上的根， F是 G的左子结点。由此描绘一下该二叉树，就可得到答案 A。 【知识模块】 数据结构与算法 12 【正确答案】 B 【知识模块】 数据结构与算法 13 【正确答案】 D 【知识模块】 数据结构与算法 14 【正确答案】 A 【知识模块】 数据结构与算法 15 【正确答案】 C 【知识 模块】 数据结构与算法 16 【正确答案】 B 【知识模块】 数据结构与算法 17 【正确答案】 D 【知识模块】 数据结构与算法 18 【正确答案】 A 【知识模块】 数据结构与算法 19 【正确答案】 C 【知识模块】 数据结构与算法 20 【正确答案】 D 【知识模块】 数据结构与算法 21 【正确答案】 A 【知识模块】 数据结构与算法 22 【正确答案】 D 【知识模块】 数据结构与算法 23 【正确答案】 A 【知识 模块】 数据结构与算法
