B:①前序遍历②中序(对称)遍历③后序遍历 ④层次遍历 C:①除最下二层可以不满外,其余都是充满的 ②除最下一层可以不满外,其余都是充满的 每个结点的左右子树的高度之差的绝对值不大于1④最下层的叶子必须在最左边 谷案:A 9.【92程P6】从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在 答卷的对应栏内。 散列法存储的基本思想是根据A来决定B,碰撞(冲突)指的是C,处理碰撞的两类 主要方法是 供选择的答案 A,B:①存储地址②元素的符号③元素个数④关键码值 ⑤非码属性⑥平均检素长度⑦负载因子⑨散列表空间 C:①两个元素具有相同序号②两个元素的关键码值不同,而非码属性相同 ③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多 :①线性探查法和双散列函数法②建溢出区法和不建溢出区法 ⑧除余法和折叠法 ④拉链法和开地址法 答案:A=⑨B= C=③ 10.【91程P4】考虑具有如下性质的二叉树:除叶子结点外,每个 结点的值都大于其左子树上的一切结点的值。并小于等于其右子树 上的一切结点的值 现把9个数1,2,3,…,8,9填入右图所示的二叉树的9个 结点中,并使之具有上述性质。此时,n1的值是A,n2的值 是B,p的值是C。现欲把√10放入此树并使该树保持 前述性质,增加的一个结点可以放在D或E。 供选择的答案 2 ④4 ⑥6⑦7 ⑨9 D~E:①n7下面 ②n8下面 ⑧n9下面 ④n6下面 ⑤n1与n2之间⑥n2与n4之间⑦n6与n9之间⑧n3与n6之间 答案:A=_⑦ 画出二又排序树如下: 、简答题(每小题4分,共16分)3 B: ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历 C：① 除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的 ③ 每个结点的左右子树的高度之差的绝对值不大于 1 ④ 最下层的叶子必须在最左边 答案：A＝ ① B＝ ② C＝ ② 9. 【92 程 P6】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在 答卷的对应栏内。 散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类 主要方法是 D 。 供选择的答案 A，B： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值 ⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间 C: ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属性相同 ③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法 答案：A＝ ④ B＝ ① C＝ ③ D＝ ④ 10.【91 程 P4】考虑具有如下性质的二叉树：除叶子结点外，每个 结点的值都大于其左子树上的一切结点的值。并小于等于其右子树 上的一切结点的值。 现把 9 个数 1，2，3，…，8，9 填入右图所示的二叉树的 9 个 结点中，并使之具有上述性质。此时，n1 的值是 A ，n2 的值 是 B ，n9 的值是 C 。现欲把 10 放入此树并使该树保持 前述性质，增加的一个结点可以放在 D 或 E 。 供选择的答案 A～C： ①1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9 D～E： ① n7 下面 ② n8 下面 ③ n9 下面 ④ n6 下面 ⑤ n1 与 n2 之间 ⑥ n2 与 n4 之间 ⑦ n6 与 n9 之间 ⑧ n3 与 n6 之间 答案：A＝ ⑦ B＝ ④ C＝ ⑥ D＝ ② E＝ ⑥ 三、简答题（每小题 4 分，共 16 分）