資源描述：
《若對大小均為n的有序順序表和無序順序表分別進行順序查》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、第九章查找9.1若對大小均為n的有序順序表和無序順序表分別進行順序查找，試在下列三種情況下分別討論兩者在等概率時平均查找長度是否相同？（1）查找不成功，即表中沒有關鍵字等于給的值K的記錄；（2）查找成功，且表中只有一個關鍵字等于給定值K的記錄；（3）查找成功，且表中有若干關鍵字等于給定值K的記錄，要求找出所有這些記錄。答：(1)相同，有序n+1;無序n+1(2)相同，有序；無序(3)不相同，對于有序表，找到了第一個與K相同的元素后，只要再找到與K不同的元素，即可停止查找；對于無序表，則要一直查找到最后一個元
2、素。9.3畫出對長度為13的有序表進行折半查找的判定樹，并分別求其等概率時查找成功和查找不成功的ASL。答：查找成功：查找失?。海≒220:查找不成功的過程就是走了一條從根節(jié)點到外部節(jié)點的路徑，和給定值進行比較的關鍵字個數(shù)等于該路徑上內(nèi)部結(jié)點個數(shù)）注：在折半查找判定樹中，查找不成功時的比較次數(shù)即是查找相應外結(jié)點時與內(nèi)結(jié)點的比較次數(shù)。整個判定樹代表的有序表在查找失敗時的平均查找長度即為查找每個外結(jié)點的比較次數(shù)之和除以外結(jié)點的個數(shù)。例如，長度為10的有序表在查找失敗時的平均查找長度為： ASL=(3×5+4×
3、6)/11=39/11第二次作業(yè)9.4已知如下所示長度為12的表(Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec)每個元素的查找概率分別為（0.1，0.25，0.05，0.13，0.01，0.06，0.11，0.07，0.02，0.03，0.1，0.07）（1），Pi為查找表中第i個記錄的概率，ASL=0.1+0.25*2+3*0.05+4*0.13+5*0.01+6*0.06+7*0.11+8*0.07+9*0.02+10*0.03+11*0.1+12*0
4、.07=5.43或者ASL=12*0.1+11*0.25+10*0.05+9*0.13+8*0.01+7*0.06+6*0.11+5*0.07+4*0.02+3*0.03+0.1*2+0.07=7.57（2）畫出初始為空，依次插入結(jié)點，生成的二叉排序樹（3）該二叉排序樹查找成功的平均查找長度。ASL=0.1+2*(0.25+0.05)+3*(0.13+0.01+0.06)+4*(0.11+0.07+0.02)+(0.03+0.07)*5+6*0.1=3.2（4）將二叉排序樹中的結(jié)點Mar刪除，畫出經(jīng)過刪除處
5、理后的二叉排序樹方法（1）方法（2）9.5在地址空間為0~16的散列區(qū)中，對以下關鍵字序列構造兩個哈希表：(Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec)（1）用線性探測開放定址法處理沖突；（2）用鏈地址法處理。分別求這兩個哈希表在等概率情況下查找成功和不成功時的平均查找長度。設哈希表函數(shù)為H(x)=︱i/2︳,其中i為關鍵字中第一個字母在字母表中的序號。（1）線性探測法當發(fā)生沖突時，線性探測法從沖突位置的下一個位置起，依次尋找空的散列地址，即：Hi=(H
6、(key)＋di)%m（di=1，2，…，m-1）。012345678910111213141516AprAugFebDecJanJunMarMayJulySepOctNov等概率情況查找成功的ASL=（5*1+3*2+5+4+6+3）/12=29/12查找不成功的ASL定義：查找不成功是需和給定值進行比較的關鍵字個數(shù)的期望值。等概率情況查找不成功的ASL=（13+12+…+1+4*1）/17=95/17（2）拉鏈法（鏈地址法）用拉鏈法處理沖突構造的散列表叫做開散列表等概率情況查找成功的ASL=（7*1+3
7、*2+2*3）/12=19/12等概率情況查找不成功的ASL=（10*1+4*2+1*3+2*4）/17=29/179.7寫出判斷一棵二叉樹是否是二叉排序樹的算法，設二叉排序樹中不存在關鍵字值相同的結(jié)點二叉排序樹定義如下，二叉排序樹或者是一棵空樹；或者是具有下列性質(zhì)的樹。??1，若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值??2，若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值??3，它的左右子樹也分別為二叉排序樹intlast=0,flag=1;intIs_BSTree(Bit
8、reeT)//判斷二叉樹T是否二叉排序樹,是則返回1,否則返回0{??if(T->lchild&&flag)Is_BSTree(T->lchild);??if(T->datadata;??if(T->rchild&&flag)Is_BSTree(T->rchild);??returnflag;}//Is_BSTree??根據(jù)遞規(guī)定義，如下的遞規(guī)算
