考研計算機數(shù)據(jù)結構課程講義3-2015kyzyk jsj sjjg ty

散列順序或壓縮索 B．以方式 D．(n- B．O(nlog2n) 5．二分查找和二叉排序樹的時間性能B。相 就表的有序性而言，二叉排序樹無須移動結點，只需修改指針即可完成和刪除操作，且其平均的則表的有序性所花的代價是O(n)。當有序表是靜態(tài)查找表時，宜用向量作為其結構，而采用二分查找實現(xiàn)其查找操作；若有序表里動態(tài)查找表，則應選擇二叉排序樹作為其結構。當二分查找值82為的結點時，C次比較后查找成功。 12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為B。 根據(jù)一組記錄(56,42,50,64,48)依次結點生成一棵AVL（高度平衡的二叉搜索樹）時，當?shù)街禐?0的結點時需要進行旋轉(zhuǎn)調(diào)整。則應把它到根結點右子樹上。根據(jù)一組記錄(56,42,73,50,64,48,22)依次結點生成一棵AVL（高度平衡的二叉搜索樹）時，當?shù)街禐?8的結點時才出現(xiàn)不平衡，需要n的順序表或單鏈表中搜索一個元素時，其時間復雜度為O(n)。子樹高度之差的絕對值不超過1。性表的散列中，裝載因子a又稱為裝載系數(shù)，若用m表示散列表的長度，n表示待散列的元素的個數(shù)，則a等于n/m。以折半搜索方法從長度為 O(log2n)假定一個順序表的長度為4020.5假定要對長度n=100的線性表進行散列，并采用開散列法處理m=20的散列表，每個散列地址的同義詞子表（單鏈表）的長度平均為5。19124816根據(jù)n個元素建立一棵二叉搜索樹(二叉排序樹)O(nlog2n)向左子樹繼續(xù)搜索。假定一個線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個字母進行劃分，使得第一度3。85，平均查找長度為3．7。nO(n)；若采用二分法查找，則時間復雜度為O(log2n)。2331/2，搜索第二個元素的概率為1/3，搜索第三個元素的概率為1/6，則搜索到表中任一元素的平均搜索長度為A。 24、向一棵AVL樹（高度平衡的二叉搜索樹）元素時，可能引起對最小不平衡子樹的雙向旋轉(zhuǎn)的調(diào)整過程，此時需要修改相關C 25、向一棵AVL樹（高度平衡的二叉搜索樹）元素時，可能引起對最小不平衡子樹的調(diào)整過程，此調(diào)整分為C種旋轉(zhuǎn)類型。 26、向一棵AVL樹（高度平衡的二叉搜索樹）元素時，可能引起對最小C個結點指針域 D={016,087,154,170,275,426,503,509,512,612,653,677,703,765,897,進行多少次比較才能得到結論?每次選擇的比較對象是什么元素?3509677:解：設輸入序列為Search_Seq(SSTableST,KeyTypeSem[n]．key=key;//哨for(i=0;!EQ(Sem[i]．key,key);++i);returni;}什么叫靜態(tài)查找？什么叫動態(tài)查找？什么樣的結構適宜于進行靜態(tài)查找？什么樣的結構適宜于進行動態(tài)查找？12的數(shù)據(jù)元素序列為{DecFeb,Nov,Oct,June,SeptAugApr,hashx)=x%11,13,12,34,38,33,27,22到散列表中針對這兩種情況,確定其裝載因子,搜索成功所需的平均探查次數(shù),以及搜索不成功hash(13)=2； ；hash(12)=3；成功；hash(34)=1； hash(33)=0hash(27)=5； hash(27)=6；成功；hash(22)=1； ；hash(22)=7；成功線性探查再散0123456789111134128裝載因子搜索成功所需的平均探查次數(shù)搜索不成功所需的平均探查次數(shù)(2)使用鏈地址法構造的散裝載因子搜索成功所需的平均探查次數(shù)搜索不成功所需的平均探查次數(shù)設有一組關鍵字{9,01,23,14,55,20,84,27}，采用哈希函數(shù)：H（key）=keymod7，表答012345678911123412以關鍵字27為例：H（27）=27%7=6（）H1=（6+1）%10=7（H2=（6+22）%10=0（ H3 所以比較了4次對下面的關鍵字集{30,15,21,40,25,26,36,370.8，采用線性（1）設計哈希函數(shù)；（2）012345678911131126 ASLsucc=16/8=2 {i=k%7；//（1），H（key）=key7if（h[i]==maxint）//maxint解釋成空地址printf（“無關鍵字%d\n”，k）；returnif（h[i]==k）{h[i]=-maxint；return（1）elsefor（d=1；d≤n- if（h[i]==maxint）return(0);//maxintif（h[i]==k）{h[i]=-maxint；return（1）；}}printf（“無關鍵字%d\n”，k）；return}使用開放定址法，Hi=[H(key)+Di]MOD10,在哈希表a中Di用線性探測再散列法，希表a,b中,并分別計算出它們的平均查找長度ASL。01234567891214555012345678921244b:ASLsuccvoidCreat_BST（BiTreebst，datatypeK[]，intif（p->data<K[i]）{f=p；p=p->RLINK；fpelseif（p->data>K[i]）{f=p；p=p->LLINK；}s=（BiTree）mal