数据结构（思政版）习题解答 第8章查找

PAGE第8章查找一、选择题1、B；2、D；3、A；4、D；5、C；6、B；7、D；8、A；9；D、10、C；11、D；12、D；13、A；14、D,C；15、C；16、C,G；17、B；18、B；19、D；20、A；21、C。二、填空题１、1,3,5,1;２、给出一个冲突尽可能少的Hash函数，给出解决冲突的方案；3、哈希查找；４、16，５、16，16；（）６、ëlog2nû+1７、；8、3；9、54；10、查入，删除；11、顺序，树表，散列；开放定址法，再哈希法，链地址法，建立公共溢出区12、low<=high,k<=A[mid],Binsch(A,mid+1,high,K),return–1三、问答题与算法题1、等概率时想找成功的查找长度：ASL=2、ASL成功＝11/4,ASL失败＝10/3.3、等概率时想找成功的查找长度：ASL=3.24、用这组关键字以不同的次序输入后建立起来的二叉排序树的形态是不相的。右图是以（1，2，3，4，5，6）的次序输入得到的二叉排序树。当以中序遍历这些二叉排序树时，其遍历结果是相同的，其结果都是由小到大的输出顺序。5、插入8后如下：插入3后如下：6、删除5如下图：删除6有三种情形：7、8、9、10、H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=611、H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….冲突H(15)=15mod7=1;….冲突H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….冲突（1）01234566336152240（2）ASL=12、H(15)=15MOD13=2H(22)=22MOD13=9H(50)=50MOD13=11H(13)=13MOD13=0H(20)=20MOD13=7H(36)=36MOD13=10H(28)=28MOD13=2….冲突H1(28)=(2+1)MOD16=3H(48)=48MOD13=9….冲突H1(48)=(9+1)MOD16=10….冲突H2(48)=(9-1)MOD16=8H(31)=31MOD13=5H(41)=41MOD13=2….冲突H1(41)=(2+1)MOD16=10….冲突H2(41)=(2-1)MOD16=1H(18)=18MOD13=5….冲突H1(18)=(5+1)MOD16=6I0123456789101112131415K1341152831182048223650SL=13、I0123456789K30714118189M1111131ASL=UASL=14、(1)线性探测I012345678910K413493813243221M11121212ASL=UASL=（2）链地址法ASL==UASL==15、BiTreesearch(BiTreeBT,keytypekey){P=BT;while(P)if(P->R.key==key)returnP;elseif(P->R.key<key)P=P->lchild;elseP=P->rchild;returnNULL;}16、图略，ASL=42/1217、用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第i个）单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。typedefstructnode{keytypekey；structnode*next；}HSNode；*HSListtypedefstructnode*HLK；voidDelete（HLKHT[]，keytypeK）//用链地址法解决冲突，从哈希表中删去关键字为K的记录{i=H（K）；//用哈希函数确定关键字K的哈希地址if（HT[i]==null）{printf（“无被删除记录\n”）；exit（0）；}HLKp,q;p=H[i]；q=p；//p指向当前记录（关键字），q是p的前驱while（p&&p->key！=k）{q=p；p=p->next；}if（p==null）{printf（“无被删除记录”）；exit(0);}if（q==H[i]）//被删除关键字是链表中第一个结点{HT[i]=HT[i].next；free（p）；}else{q->next=p->next；free（p）；}}//结束Delete18、利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。typedefstructnode{intdata；structnode*left，*right;}BiTNode，*BSTree；voidDelTree(BSTreer）//非递归删除以r为根的二叉排序树{BSTreeS[]；//栈，容量足够大，栈中元素是二叉排序树结点的指针top=0；while（r!=null||top>0）{while（r!=null）//沿左分枝向下{S[++top]=r；r=r->left；}if（top>0）//退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间{p=S[top--]；r=p->right；free（p）；}}}//DelTreevoidDeleteAllx(BSTreeＴ，intx）//在BST中删除所有不大寓于x的结点{BSTreep=T，q；while（T&&T->data≤x）//根结点的值小于等于x{p=T；T=T->right；p->right=null；DelTree（p）；}//删除二叉树p,删除持续到“根”结点值大于x或T为空树为止if(T){q=T；p=T->left；while（p&&p->data>x）//沿根结点左分枝向下，查小于等于x的结点{while（p&&p->data>x）{q=p；p=p->lef