單元7一、選擇題12345BAADA678910BCACA1112131415BCCBC二、簡(jiǎn)答題1.答：不適合！雖然有序的單鏈表的結(jié)點(diǎn)是按從小到大（或從大到?。╉樞蚺帕?，但因其存儲(chǔ)結(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開(kāi)始逐步搜索，故不能進(jìn)行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時(shí)，則線(xiàn)性查找快；而二分查找則慢得多。2.答：使用二分查找時(shí)，線(xiàn)性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。3.查找元素54，需依次與30,63,42,54等元素比較；ASL＝1/12（1＋2×2＋4×3＋5×4=）＝37/12≈3.084.按照序列得到的二叉排序樹(shù)如下所示：二叉排序樹(shù)中依次刪除57，82，71后的二叉排序樹(shù)如下所示：5.答：③6.平衡二叉排序樹(shù)如下所示：等概率下，查找成功的平均查找長(zhǎng)度：ASL＝1/12（1＋2×2＋4×3＋4×4+5）＝38/12≈3.17三、算法設(shè)計(jì)題1.publicstaticBiTNode<T>searchNode(BiTNode<T>t,KeyTypekx){ while(t!=null){ if(t.data.key==kx){//查找成功 returnt; }elseif(kx<t.data.key){//關(guān)鍵字小于當(dāng)前子樹(shù)的根結(jié)點(diǎn)的關(guān)鍵字 t=t.lchild;//在左子樹(shù)查找 }else{ t=t.rchild;//在右子樹(shù)查找 } } returnnull; }2.publicclassChocolateDistribution{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intn=scanner.nextInt();//巧克力的塊數(shù)intk=scanner.nextInt();//小朋友的人數(shù)int[][]chocolates=newint[n][2];//存儲(chǔ)每塊巧克力的長(zhǎng)和寬for(inti=0;i<n;i++){chocolates[i][0]=scanner.nextInt();chocolates[i][1]=scanner.nextInt();}intleft=1;//二分查找的左邊界，最小邊長(zhǎng)為1intright=getMaxDimension(chocolates);//二分查找的右邊界，最大邊長(zhǎng)為巧克力長(zhǎng)或?qū)挼淖畲笾祑hile(left<right){intmid=(left+right+1)/2;//取中間值，這里向上取整，防止死循環(huán)intcount=0;//記錄當(dāng)前邊長(zhǎng)下能切出的巧克力總數(shù)for(inti=0;i<n;i++){count+=(chocolates[i][0]/mid)*(chocolates[i][1]/mid);//計(jì)算每塊巧克力能切出的邊長(zhǎng)為mid的正方形巧克力數(shù)量if(count>=k){break;//如果已經(jīng)滿(mǎn)足小朋友數(shù)量，無(wú)需繼續(xù)計(jì)算}}if(count>=k){left=mid;//如果當(dāng)前邊長(zhǎng)能滿(mǎn)足小朋友數(shù)量，嘗試更大的邊長(zhǎng)，更新左邊界}else{right=mid-1;//如果當(dāng)前邊長(zhǎng)不能滿(mǎn)足小朋友數(shù)量，嘗試更小的邊長(zhǎng)，更新右邊界}}System.out.println(left);//輸出最大的邊長(zhǎng)scanner.close();}publicstaticintgetMaxDimension(int[][]chocolates){intmax=0;for(inti=0;i<chocolates.length;i++){for(intj=0;j<2;j++){max=Math.max(max,chocolates[i][j]);//找到巧克力長(zhǎng)和寬中的最大值