數(shù)據(jù)結(jié)構(gòu)考研試題及第9章查找

數(shù)據(jù)構(gòu)造考研試題及第9章查找數(shù)據(jù)構(gòu)造考研試題及第9章查找8/8數(shù)據(jù)構(gòu)造考研試題及第9章查找第9章會(huì)集一．選擇題二．判斷題1.√2.√3.×4.×5.×6.√7.√8.×9.×10.11.12.××√13.14.15.16.17.18.19.20.21.22.23.24.√×××√×√×××××25.26.27.28.29.30.31.32.33.34.35.36.√××√√××√√×√√部分答案講解以下。4．不能夠說哪一種哈希函數(shù)的采用方法最好，各種采用方法有自己的適用范圍。8．哈希表的結(jié)點(diǎn)中能夠包括指針，指向其元素。11．單鏈表不能夠使用折半查找方法。20．按插入后中序遍歷是遞加序列的原則，若某結(jié)點(diǎn)只有右子樹，而插入元素的要點(diǎn)字小于該結(jié)點(diǎn)的要點(diǎn)字，則會(huì)插入到該結(jié)點(diǎn)的左側(cè)，成為其左孩子。這種插入就不是插入到葉子下面。21．從平衡因子定義看，完好二叉樹任一結(jié)點(diǎn)的平衡因子的絕對(duì)值確實(shí)是小于等于1。但是，平衡二叉樹實(shí)質(zhì)上是二叉排序樹，完好二叉樹不用然是排序樹。故不能夠說完好二叉樹是平衡二叉樹。23．某結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)不用然是它的中序前驅(qū)，其右子樹根結(jié)點(diǎn)也不用然是它的中序后繼。24．在等概率下，查找成功時(shí)的平均查找長度相同，查找失敗時(shí)的平均查找長度不相同。26．只有被刪除結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)命題才正確。三．填空題1．nn+12．43．6,9,11,124．55．26（第4層是葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)兩個(gè)要點(diǎn)字）6．1,3,6,8,11,13,16,197．5,968．m-1,「m/2-19．2,4,310．(1)哈希函數(shù)(2)解決矛盾的方法(3)選擇好的哈希函數(shù)(4)辦理矛盾的方法(5)平均(6)簡(jiǎn)單11．AVL樹（高度平衡樹，高度平衡的二叉排序樹），或?yàn)榭斩鏄?，或二叉樹中任意結(jié)點(diǎn)左子樹高度與右子樹高度差的絕對(duì)值小于等于1。12．小于等于表長的最大素?cái)?shù)或不包括小于20的質(zhì)因子的合數(shù)13．1614．㏒2n」+115．(1)45(2)45(3)46（塊內(nèi)序次查找）16．k(k+1)/217．30，31.5（塊內(nèi)序次查找）18．(1)序次儲(chǔ)藏或鏈?zhǔn)絻?chǔ)藏(2)序次儲(chǔ)藏且有序(3)塊內(nèi)序次儲(chǔ)藏，塊間有序(4)散列儲(chǔ)藏19．(n+1)/220

．(n+1)/n*log

2(n+1)-1

21．點(diǎn)的左子的高度減去點(diǎn)的右子的高度22．(1)

序表

(2)

表(3)

哈希表

(4)

開放定址方法

(5)地址方法

(6)再哈希(7)

建立公共溢出區(qū)n123．直接定址法24．logm/2(2)+125．O(N)26．n(n+1)/227．5428．3129．37/1230．主關(guān)字31．左子右子32．插入除33．1434．(1)126(2)64(3)33(4)6535．（1）low<=high(2)(low+hig)DIV2(3)binsrch:=mid(4)binsrch:=036．(1)k(2)I<n+137．(1)rear=mid-1(2)head=mid+1(3)head>rear38．(1)p!=null(2)pf=p(3)p!=*t(4)*t=null四．用1．見解是基本知的主要部分，要牢固掌握。里只列出一部分，目的是引起重，解答略。2．（1）散列表存的基本思想是用關(guān)字的決定數(shù)據(jù)元素的存地址（2）散列表存中解決碰撞的基本方法：①開放定址法形成地址序列的公式是：Hi=（H（key）+di）%m，其中m是表，di是增量。依照di取法不相同，又分三種：a．di=1，2，?，m-1稱性探再散列，其特點(diǎn)是逐個(gè)探表空，只要散列表中有空空，即可解決碰撞，缺點(diǎn)是簡(jiǎn)單造成“齊聚”，即不是同的關(guān)字爭(zhēng)同一散列地址。b．di=12，-12，22，-22，?，k2（k≤m/2）稱二次探再散列，它減少了齊聚，但不簡(jiǎn)單探到全部表空，只有當(dāng)表形如4j+3（j整數(shù)）的素?cái)?shù)才有可能。c．di=隨機(jī)數(shù)序列，稱隨機(jī)探再散列。②再散列法Hi=RH（key）i=1，2，?，k，是不相同的散列函數(shù)，即在同生i碰撞，用另一散列函數(shù)算散列地址，直到解決碰撞。方法不易生“齊聚”，但增加了算。③地址法將關(guān)字同的存在同一表中，散列表地址區(qū)用H[0..m-1]表示，重量初始空指。凡散列地址i（0≤i≤m-1）的均插在以H[i]指的表中。種解決方法中數(shù)據(jù)元素個(gè)數(shù)不受表限制，插入和除操作方便，但增加了指的空開。種散列表常稱開散列表，而①中的散列表稱散列表，含是元素個(gè)數(shù)受表限制。④建立公共溢出區(qū)H[0..m-1]基本表，凡關(guān)字同的，都填入溢出區(qū)O[0..m-1]。（3）用分其余同表和合的同表解決碰撞均屬于地址法。地址向量空中的每個(gè)元素不是的地址，而是關(guān)字和指兩個(gè)域，散列地址i（0≤i≤m-1）的第一個(gè)關(guān)字存在地址空向量第i個(gè)重量的“關(guān)字”域。前者的指域是指，指向同的表，擁有上面③的缺點(diǎn)；后者是靜表，同存在同一地址向量空（從最后向前找空元），以指相。省了空，但易生“堆”，找效率低。（4）要在被除點(diǎn)的散列地址作，不能夠物理的除。否，中斷了找通路。（5）記錄負(fù)載因子3．議論哈希函數(shù)利害的因素有：可否將要點(diǎn)字平均隱射到哈希空間上，有無好的解決矛盾的方法，計(jì)算哈希函數(shù)可否簡(jiǎn)單高效。由于哈希函數(shù)是壓縮映像，矛盾難以防備。解決矛盾的方法見上面2題。4．哈希方法的平均查找路長主要取決于負(fù)載因子（表中實(shí)有元素?cái)?shù)與表長之比），它反響了哈希表的裝滿程度，該值一般取0.65~0.9。解決矛盾方法見上面2題。5．不用然相鄰。哈希地址為i（0≤i≤m-1）的要點(diǎn)字，和為解決矛盾形成的探測(cè)序列i的同義詞，都強(qiáng)搶哈希地址i。6．散列地址0123456789要點(diǎn)字140192384275520比較次數(shù)11123412平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以要點(diǎn)字27為例：H（27）=27%7=6（矛盾）H1=（6+1）%10=7（矛盾）2233）%10=5因此比較了4次。H=（6+2）%10=0（矛盾）H=（6+37．由于裝填因子為0.8，要點(diǎn)字有8個(gè)，因此表長為8/0.8=10。1）用除留余數(shù)法，哈希函數(shù)為H（key）=key%72）散列地址0123456789要點(diǎn)字2115303625402637比較次數(shù)11131126（3）計(jì)算查找失敗時(shí)的平均查找長度，必定計(jì)算不在表中的要點(diǎn)字，當(dāng)其哈希地址為i（0≤i≤m-1）時(shí)的查找次數(shù)。本例中m=10。故查找失敗時(shí)的平均查找長度為：ASLunsucc=（9+8+7+6+5+4+3+2+1+1）succ=16/8=2（4）intDelete（inth[n]，intk）從哈希表h[n]中刪除元素k，若刪除成功返回1，否則返回0{i=k%7；//哈希函數(shù)用上面（1），即H（key）=key%7if（h[i]==maxint）//maxint講解成空地址printf（“無要點(diǎn)字%d\n”，k）；return（0）；}if（h[i]==k）{h[i]=-maxint；return（1）；}//被刪元素?fù)Q成最大機(jī)器數(shù)的負(fù)數(shù)else//采用線性探測(cè)再散列解決矛盾{j=i;for（d=1；d≤n-1；d++）{i=

（j+d）%n；//nif（h[i]==maxint）return(0)if（h[i]==k）{h[i]=-maxint

為表長，此處為10;//maxint講解成空地址；return（1）；}}//for}printf（“無要點(diǎn)字%d\n”，k）；return(0)}8．散列地址0123456789要點(diǎn)字1524101917381840比較次數(shù)11214555哈希表a:ASLsucc=24/8=3；散列地址0123456789要點(diǎn)字1517241019403818比較次數(shù)13121244哈希表b:ASLsucc=18/89．（1）散列地址0123456789101112要點(diǎn)字13225314167465130比較次數(shù)111212111（2）裝填因子（3）ASLsucc=11/9（4）ASLunsucc=29/1310．11．ASL=19/12succ12．常用構(gòu)造哈希函數(shù)的方法有：1）數(shù)字解析法該法早先需知道要點(diǎn)字會(huì)集，且要點(diǎn)字位數(shù)比散列表地址位數(shù)多，應(yīng)選數(shù)字分布平均的位。2）平方取中法將要點(diǎn)字值的平方取中間幾位作哈希地址。3）除留余數(shù)法H（key）=key%p，平時(shí)p取小于等于表長的最大素?cái)?shù)。4）折疊法將要點(diǎn)字分成長度相等（最后一段可不等）的幾部分，進(jìn)行移位疊加或間界疊加，其值作哈希地址。5）基數(shù)變換法兩基數(shù)要互素，且后一基數(shù)要大于前一基數(shù)。在哈希表中刪除一個(gè)記錄，在拉鏈法情況下能夠物理地刪除。在開放定址法下，不能夠物理地刪除，只能作刪除標(biāo)記。該地址可能是該記錄的同義詞查找路徑上的地址，物理的刪除就中斷了查找路徑。由于查找時(shí)碰到空地址就認(rèn)為是查找失敗。散列地址0123456789101112131415要點(diǎn)字140168275519208479231110比較次數(shù)12143113911313．（1）散列地址012345678910要點(diǎn)字412493813243221比較次數(shù)11121212ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11（2）13題圖ASLsucc=11/8ASLunsucc=19/1114題（2）ASLsucc=13/8ASLunsucc=19/11值得指出，對(duì)用拉鏈法求查找失敗時(shí)的平均查找長度有兩種見解。其一，認(rèn)為比較到空指針?biāo)闶?。以本題為例，哈希地址0、2、5、7、9和10均為比較1次失敗，而哈希地址1和3比較2次失敗，其余哈希地址均為比較3次失敗，因此，查找失敗時(shí)的平均查找長度為19/11，我們持這種見解。還有另一種理解，他們認(rèn)為只有和要點(diǎn)字比較才計(jì)算比較次數(shù)，而和空指針比較不計(jì)算。照這種見解，本題的ASL=（1+1+2+2+2）/11=8/11unsucc14．由hashf(x)=xmod11可知，散列地址空間是0到10，由于有8個(gè)數(shù)據(jù)，裝載因子取0.7。（1）散列地址012345678910要點(diǎn)字331131234382722比較次數(shù)11134128ASL=21/8ASLunsucc=47/11succ15．1）ASL=42/122）a：ASLsucc=31/12（2）b：ASLsucc=18/12(注：本題[x]取小于等于x的最大整數(shù))16．17．查找時(shí)，對(duì)要點(diǎn)字49,22,38,32,13各比較一次，對(duì)21,18各比較兩次18．ASLsucc=15/1019．ASLsuss=16/1120．散列地址01234567891011要點(diǎn)字231897925471638825139151比較次數(shù)11112123243ASLsucc=21/1121．散列地址012345678910要點(diǎn)字223346130167415330比較次數(shù)12124511322．（1）散列01234567891011121314151617地址要點(diǎn)3217634924401030314647字比較11631211133次數(shù)2）查找要點(diǎn)字63，H（k）=63MOD16=15，依次與31，46，47，32，17，63比較。3）查找要點(diǎn)字60，H（k）=60MOD16=12，散列地址12內(nèi)為空，查找失敗。4）ASLsucc=23/1123．設(shè)用線性探測(cè)再散列解決矛盾，依照公式Snl≈（1+1/（1-α））/2因子為α=0.67。再依照數(shù)據(jù)個(gè)數(shù)和裝載因子，可求出表長m=15/0.67，取數(shù)H（key）=（要點(diǎn)字首尾字母在字母表中序號(hào)之和）MOD23。

?？汕蟪鲐?fù)載m=23。設(shè)哈希函從上表求出查找成功時(shí)的平均查找長度為ASLsucc=19/15<2.0，滿足要求。24．（1）哈希函數(shù)H（key）=（要點(diǎn)字各字符編碼之和）MOD7（2）散列地址0123456789要點(diǎn)字becdaaabacadbdbcaece比較次數(shù)121111133925．α=0.7，因此表長取m=7/0.7=10散列地址0123456789要點(diǎn)字SATWEDSUNMONTU