（1） 若查找关键字63，需要依次与哪些关键字进行比较？
（2） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解：
（1） 查找63，需要比较6次。分别为：31，46, 47, 32, 17, 63。
8 2
（2） ASL=1/11（1×6＋2×1＋3×3＋6×1）＝23/11=≈2.1
3． 对于给定结点的关键字集合K={1，12，5，8，3，10，7，13，9}， （1）试构造一棵二叉排序树；
（2）如何依据此二叉排序树得到D的有序序列。 解：（1）构造二叉排序树： 1 12
513
8 3
7 10
9
（2）按中序遍历二叉排序树可以得到D的有序序列。
4． 对于给定结点的关键字集合K={15，9，20，12，17，4，18，10，29，6}，构成一棵二叉排序树，并写出该二叉排序树中序遍历的结点序列。 解：
（1） 构造二叉排序树
15
9 20 4 12 1729 18 6 10
（2）中序遍历的结点序列：4，6，9，10，12，15，17，18，20，29。
5． 给定结点的关键字序列为：47，7，29，11，16，92，22，8，3，哈希表的长度为11。 设散列函数为：H（K）=K % 11。
试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。
解：（1） 线性探测再散列解决冲突时所构造的散列表：
0 11 1 22 2 3 47 4 92 5 16 6 3 7 7 8 29 9 8 10 ① ② ① ① ① ④ ① ② ②
（2） 平均查找长度ASL=（1*5+2*3+4*1）/9 = 15/9 =5/3 （或1.67）
6． 给定结点的关键字序列为：87，25，11，8，27，28，68，95，70，6，83，63，47，已知设散列函数为：H（K）=K % 13。
试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。 解：
（1） 链地址法解决冲突时所构造的哈希表。
0 ∧ 1 2 3 4 5 6 8 9 11 12
27 ∧ 28 ∧ 68 ∧ 95 ∧ 70 6 ∧ 8 83 ∧
7 ∧ 47 ∧
87 ∧ 11 10 ∧ 63 ∧
25 ∧
（2） 平均查找长度ASL=（1*10+2*3）/13 = 16/13 （或1.23）
查找程序填空
1．从键盘输入若干个整数，以回车为间隔，以-1为结束符号，建立一个顺序存储的线性表，然后按提示输入一个待查找的数进行查找。若找到，则显示找到的数据在线性表中的位置；否则显示“找不到”，试填空完成下列程序。
void SeqSearch() {int a[n],i,x,y;
cout<<\建立整数的顺序表(以回车为间隔，以-1结束)：\ for (i=1;i<=MAXLEN;i++) {cin>>a[i];
if (a[i]== -1 )
{ y=i; break; }
}
cout<<\请输入要查找的数据：\ cin>>x; i=y-1;
while (i>=0 && a[i]!=x )
if ( i==0 )
cout<< \没有找到\else
cout<<\已找到，在第\个位置上\}
2． 对有序表R[0]至R[n-1]进行二分查找，查找成功时返回记录在表中的位置；查找失败时显示：“没有找到！”，试编写此程序。
void BinSearch()
{ int R[MAXLEN],i,low,high,mid,n,x; char ch;
cout<< \请输入要查找的数据: \ cin>> x ; low=0; high= n-1 ;
while (low<= high ) { mid= (low+high)/2 ;
if (R[mid]>x)
high= mid-1 ; else
if (R[mid] low= mid+1 ; else break; } if ( low>high ) { cout<< \没有找到！\ if (R[mid] mid++ ; cout<< \可将此数插入到\的位置上。\ i-- ; （或 i=i+1 ） else } cout<< \要找的数据\在第\的位置上\