Question

数据结构第八章作业，求高手给个答案。感激不尽。

9.1 试分别画出在有序的线性表(6，17，20，33，45，50，62，78，87)中进行折半查找，以查关键字20的过程。（画出每次查找时low、high、mid指针所指向的位置）

9.2 依次输入元素：18，15，26，10，12，14，19，29，试生成一棵二叉排序树。(1) 画出建立的二叉排序树。(2) 假定每个元素的查找概率相等，计算查找成功时的平均查找长度。

9.3 试用关键字序列(22，18，38，39，48，35，9，64，29)构造哈希表，设表地址为0~15，哈希函数为H(key)=key MOD 13，其中key为关键字，MOD为取余数运算，处理冲突方法为线性探测再散列。(1) 画出该哈希表的存储结构图。(2) 若查找关键字9，必须依次与表中哪些关键字比较大小？(3) 假定每个元素的查找概率相等，计算查找成功时的平均查找长度。

Answer 1

普通作业八（第九章）专科

9.1

9.2

9.3

27 mod 8 = 3, 17 mod 8 = 1, 9 mod 8 = 1, 19 mod 8 = 3, 16 mod 8 = 0, 43
mod 8 = 3, 53 mod 8 = 5, 8 mod 8 = 0, 63 mod 8 = 7，于是链地址法解决冲突的哈希表为：

Answer 2

1.线性表：78,50,40,60,34,90 2.排序过程：94,(32,40,90,80,46,21)3294(40,90,80,46,21)324094(,90,80,46,21)32409094(80,4621)3240809094(46,21)324046809094(21)21324046809094 3.栈和队列的区别：栈是先进后出，队列先进先出 4.线性表的基本操作：构造一个空表，销毁表，求表长，判空，返回表中第一个元素 5. include voidmain() { intpd; a[]=;dad; pd=hw(dad,3); if(pd==1) { printf(;是回文;); } else {printf(;不是回文;); } } inthw(char a[],intn) { for(i=0;in/2;i ) { if(a[i]==a[n-i]) { return1; } else { reutnr0; } } }