数据结构课程 课后习题答案

练习题及参考答案 答：B

（6）折半查找与二叉排序树的时间性能（ ）。 A.相同 B.完全不同 C.有时不相同 D.数量级都是O(log2n) 答：C

（7）用n个关键字构造一棵二叉排序树，其最低高度为（ ）。 A. n/2 B. n C. ?log2n? D. ?log2n+1? 答：D

（8）在二叉排序树中，关键字最小的结点，它的（ ）。 A.左指针一定为空 B.右指针一定为空 C.左、右指针均为空 D.左、右指针均不为空 答：A

（9）在二叉排序树中，每个结点的关键码值（ ① ），（ ② ）一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是（ ③ ）。

①：A.比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 B.比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 C.比左右子树的所有结点的关键码值都大 D.与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 ②：A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 ③：A.除最下两层可以不满外，其余都是充满的 B.除最下一层可以不满外，其余都是充满的 C.每个结点的左右子树的高度之差的绝对值不大于1 D.最下层的叶子结点必须在最左边 答：①A ②B ③B （10）哈希法存储的基本思想是根据（ ① ）来决定（ ② ），碰撞（冲突）指的是（ ③ ），处理碰撞的两类主要方法是（ ④ ）。

①②： A.存储地址 B.元素的符号 C.元素个数 D.关键字值 E.非关键字属性 F.平均查找长度 G.装填因子 H.哈希表空间 ③：A.两个元素具有相同序号 B.两个元素的关键字值不同，而非关键字属性相同 C.不同关键字值对应到相同的存储地址 D.装填因子过大 E.数据元素过多

④：A.线性探测法和双散列函数法 B.建溢出区法和不建溢出区法 C.除余法和折叠法 D.拉链法和开放地址法 答：①D ②A ③C ④D

（11）假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行（ ）次探测。

A. k-1 B. k C. k+1 D. k(k+1)/2

49

数据结构简明教程

答：D

（12）哈希表在查找成功时的平均查找长度（ ）。 A.与处理冲突方法有关，而与装填因子α无关 B.与处理冲突方法无关，而与装填因子α有关 C.与处理冲突方法有关和装填因子α都有关 D.与处理冲突方法无关，也与装填因子α无关 答：C

（13）在一棵平衡二叉树中，每个结点的平衡因子的取值范围是（ ）。 A. -1~1 B. -2~2 C. 1~2 D. 0~1 答：A

（14）具有5层结点的AVL树至少有（ ）个结点。

A. 10 B. 12 C. 15 D. 17 答：B

（15）下述叙述中（ ）是不成立的。

A. m阶B-树中的每个分支结点的子树个数都小于或等于m B. m阶B-树中的每个分支结点的子树个数都大于或等于?m/2? C. m阶B-树中的任何一个结点的子树高度都相等

D. m阶B-树具有k个子树的非叶子结点含有k-1个关键字 答：B

（16）下列叙述中，不符合m阶B树定义要求的是（ ）。 A. 根结点最多有m棵子树 B. 所有叶子结点都在同一层上 C. 各结点内关键字均升序或降序排列 D. 叶子结点之间通过指针链接 答：D

（17）高度为5的3阶B-树至少有（ ）个结点。

A. 32 B. 31 C. 64 D. 108 答：B

（18）下面关于B-树和B+树的叙述中，不正确的是（ ）。

A. B-树和B+树都能有效地支持顺序查找 B. B-树和B+树都能有效地支持随机查找 C. B-树和B+树都是平衡的多分树 D. B-树和B+树都可用于文件索引结构 答：A 2. 填空题

（1）顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为（ ① ）次；若查找不成功，则比较关键字的次数为（ ② ）次。

答：①n ②n

（2）假设在有序顺序表A[1..20]上进行折半查找，比较1次查找成功的记录数为（ ① ），比较2次查找成功的记录数为（ ② ），比较3次查找成功的记录数为（ ③ ），比较4次查找成功的记录数为（ ④ ），比较5次查找成功的记录数为（ ⑤ ），等概率情况下成功查找的平均查找长度约为（ ⑥ ）。