D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法
③ 除余法和折叠法 ④ 拉链法和开地址法
答案：A＝ B＝ C＝ D＝
9. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。
现把9个数1，2，3， ，8，9填入下图所示的二叉树的9个结点中，并使之具有上述
性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把放入此树并使该树保持前述性质，增加的一个结点可以放在 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＝
四、简答题（每小题5分，共25分）
1. 说明线性表、栈与队的异同点。
2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列
3. 假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？
4. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
5. 给定二叉树的两种遍历序列，分别是：
前序遍历序列：D，A，C，E，B，H，F，G，I；
中序遍历序列：D，C，B，E，H，A，G，I，F，
试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
五、阅读理解（每小题5分，共20分）
1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在
P