數(shù)據(jù)結(jié)構(gòu)（Java語言版）-習(xí)題及答案 第10章查找習(xí)題答案

第10章查找習(xí)題參考答案 一、單選題ABCABCDnn/2C.n+/2.n/2ABCABCD1nn/2.n+/2.對長度為3的順序表進行順序查找，若查找第1個元素的概率是1/2，查找第2個元素的概率是1/3，查找第3個元素的概率是1/6，則成功查找表中任一元素的平均查找長度是 。AABCD./3.2C./3.3ABCABCD以順序方式存儲以鏈接方式存儲以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序以鏈表方式存儲，且結(jié)點按關(guān)鍵字有序排序ABCABCD一次成功查找過程終止的結(jié)點一次失敗查找過程終止的結(jié)點一次成功查找過程中經(jīng)過的中間結(jié)點一次失敗查找過程中經(jīng)過的中間結(jié)點ABCD已知一個長度為的有序順序表ABCD5476AB設(shè)有100個元素的有序順序表，采用折半查找方法，不成功時最大的比較次數(shù)是 。AB2550CDCD7有一個長度為的有序表，按折半查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為 。ABCD.ABCD./2C./2./2有一個長度為的有序表，按折半查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找不成功所需的平均比較次數(shù)為 。ABCD.ABCD./2C./2./3<gye="xdh:%;"rc="hp://cdnqngnene/deebdbdcdbpng"/>有一個有序表為（1，3，9，12，32，41，45，62，75，77，82，95，99），當(dāng)采用折半查找法查找關(guān)鍵字為82的元素時， 次比較后查找成功。AABCD1248ABCD有一個長度為n的有序順序表，采用折半查找，經(jīng)過ABCDi+111ABCABCD數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑年P(guān)鍵字組成索引塊數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑年P(guān)鍵字組成索引塊數(shù)據(jù)分成若干塊，每塊中的數(shù)據(jù)個數(shù)必須相同ABCABCD.0.0C.0.g0設(shè)待查關(guān)鍵字為47，且已存入變量k中，如果在查找過程中，和k進行比較的元素依次是47、32、46、25、47，則所采用的查找方法 。AABCD是一種錯誤的方法可能是分塊查找可能是順序查找可能是折半查找設(shè)待查關(guān)鍵字為47，且已存入變量k中，如果在查找過程中，和k進行比較的元素依次是27、72、16、84、47，則所采用的查找方法是 。AABCD二叉排序樹查找分塊查找順序查找折半查找ABCABCD折半查找分塊查找順序查找二叉排序樹查找ABCD以下ABCD二叉排序樹是動態(tài)樹表，在插入新結(jié)點時會引起樹的重新分裂和合并對二叉排序樹進行層次遍歷可以得到一個有序序列在構(gòu)造二叉排序樹時，若關(guān)鍵字序列有序，則二叉排序樹的高度最大在二叉排序樹中進行查找，關(guān)鍵字的比較次數(shù)最多不超過結(jié)點數(shù)的一半ABCD由一個關(guān)鍵字序列建立一棵二叉排序樹，ABCD該序列的存儲結(jié)構(gòu)序列中的關(guān)鍵字的取值范圍關(guān)鍵字的輸入次序使用的計算機的軟、硬件條件在任意一棵非空二叉排序樹T1中，刪除某結(jié)點v之后形成二叉排序樹T2，再將v插入T2形成二叉排序樹T3。下列關(guān)于T1與T3的敘述中，正確的是 。I.若v是的葉子結(jié)點，則與不同II.若v是的葉子結(jié)點，則與相同III.若v不是的葉子結(jié)點，則與不同I.若v不是T1的葉子結(jié)點，則T1與T3相同AABCD僅I、III僅I、IV僅II、III僅II、ABCD對于下列關(guān)鍵字序列，不可能構(gòu)成ABCD.，，，，，1.，，，，，5C.，，，，，8.，，，，，4ABCDABCD樹形未定，無法確定.，，，，，，9C.，，，，，，7.，，，，，，7以下查找方法中速度最快的是AABCD順序查找分塊查找二叉排序樹查找

。 含有20個結(jié)點的AVL樹的最大高度是AABCD567

。 ABCABCD4567ABCD若AVL樹的高度為6，且ABCD12203233ABCABCD0123以下關(guān)于m階B-樹的敘述中正確的是 。 AABCD樹中每個結(jié)點至多有/個關(guān)鍵字所有葉子結(jié)點均在同一層上當(dāng)插入一個關(guān)鍵字引起B(yǎng)-樹結(jié)點分裂時，樹增高一層ABCABCD11121314ABCABCDB-樹和B+樹都能有效地支持順序查找B-樹和B+樹都能有效地支持隨機查找B-樹和B+樹都是平衡的多叉樹ABCABCD哈希查找的時間與元素個數(shù)n成正比不管是開放地址法還是拉鏈法，查找時間都與裝填因子α有關(guān)線性探測法存在堆積現(xiàn)象，而拉鏈法不存在堆積現(xiàn)象拉鏈法中裝填因子α必須小于1ABCABCD除留余數(shù)法數(shù)字分析法線性探測法關(guān)鍵字比較法ABCABCD兩個元素具有相同的序號兩個元素的關(guān)鍵字不同，而其他屬性相同數(shù)據(jù)元素過多兩個元素的關(guān)鍵字不同，而對應(yīng)的哈希函數(shù)值相同為提高哈希（Hash）表的查找效率，可以采取的正確措施是象

。Ⅰ增大裝填因子Ⅱ設(shè)計沖突少的哈希函數(shù)Ⅲ處理沖突時避免產(chǎn)生堆積現(xiàn)ABABCD僅Ⅱ僅Ⅰ、Ⅱ采用線性探查法解決沖突的哈希表中，引起的堆積現(xiàn)象的原因是AABCD非同義詞之間發(fā)生沖突同義詞或非同義詞之間發(fā)生沖突哈希表溢出

。 ABCD假設(shè)有k個關(guān)鍵字互為同義詞，若用線性探測法把這kABCDk-1kk+1.kk+/2ABCABCD查找表為鏈表查找表為有序表關(guān)鍵字集合比地址集合大得多關(guān)鍵字集合與地址集合之間存在對應(yīng)關(guān)系A(chǔ)BC哈希查找的基本思想是根據(jù)（ABC元素的序號元素個數(shù)關(guān)鍵字值D非關(guān)鍵字屬性值DABCABCD數(shù)字分析法除留余數(shù)法平方取中法直接定址法ABCABCD一定會一定不會仍可能會以上都不對ABCABCD用拉鏈法解決沖突易引起堆積現(xiàn)象用線性探測法解決沖突易引起堆積現(xiàn)象哈希函數(shù)選得好可以減少沖突現(xiàn)象哈希函數(shù)Hk=kODp，p通常取小于等于表長的素數(shù)ABCD在含有n個結(jié)點ABCDn/2gngn+1nABCD用n個關(guān)鍵字構(gòu)造的ABCDn/2ngngn+1用n個關(guān)鍵字構(gòu)造的一棵二叉排序樹，經(jīng)過i次關(guān)鍵字比較成功找到的元素個數(shù)最多為（）。AA.iBCD.BCDC.<p><up></up></p>.<p><up></up></p>ABCDABCD左指針一定為空右指針一定為空左、右指針均為空左、右指針均不空ABCDABCD左指針一定為空右指針一定為空左、右指針均為空左、右指針均不空ABCABCD它們的邏輯結(jié)構(gòu)相同施加其上的操作不同所包含的數(shù)據(jù)元素的類型不同存儲實現(xiàn)不同ABCABCD有序順序表二叉排序樹堆二叉平衡樹A如果一個表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，則可采用()。 A有序表BBCD哈希表二叉平衡樹ABCABCD哈希存儲順序存儲或鏈?zhǔn)酱鎯嚎s存儲索引存儲ABCABCDnn/2C.n+/2.n/2二、編程題.HDU2025—查找最大元素時間限制：2000ms，空間限制：65536K。問題描述：對于輸入的每個字符串，查找其中的最大字母，在該字母后面插入字符串x。實例由一行長度不超過100的字符串組成，字符串僅由大小寫字母構(gòu)成。輸出格式：對于每個測試實例輸出一行字符串，輸出的結(jié)果是插入字符串x后的結(jié)果，如果存在多個最大的字母，就在每一個最大字母后面都插入"x"。答：prtvuScnner;pubccsn{pubccvdnSrng]rg){Scnnern=newScnnerSyen;Srng;henhNex){=nnex;chrxc=chr;rnt=;i<engh;++)fchr>xc)xc=chr;rnt=;i<engh;++){Syeuprnchr;fchr==xc)Syeuprn"x";}Syeuprnn;}}}OJ—總和為零的四元組數(shù)時間限制：，空間限制：。問題描述：SUM問題是，給定4個整數(shù)列表A、B、C和D，計算多少個四元組（a，b，c，d）∈A×B×C×D滿足a+b+c+d=0。在下文中，我們假設(shè)所有列表都具有相同的大小n。輸入格式：輸入文件的第一行包含列表的大小n（此值可以大到4000）。然后有n行每行包含四個整數(shù)值（絕對值大到2^28），它們分別屬于A、B、C和D答：prtvuScnner;pubccsn{pubccvdnSrng]rg){Scnnern=newScnnerSyen;Srng;henhNex){=nnex;chrxc=chr;rnt=;i<engh;++)fchr>xc)xc=chr;rnt=;i<engh;++){Syeuprnchr;fchr==xc)Syeuprn"x";}Syeuprnn;}}}.OJ—硬木種類時間限制：，空間限制：。問題描述：硬木是植物樹群，有寬闊的葉子，產(chǎn)生水果或堅果，并且通常在冬天休眠。美國的溫帶氣候產(chǎn)生了數(shù)百種硬木樹種，例如橡樹、楓樹和櫻桃都是硬木樹種，它們是不同的物種。所有硬木樹種共同占美國樹木的40%。利用衛(wèi)星成像技術(shù)，自然資源部編制了一份特定日期的每棵樹的清單。你需要計算每個樹種的百分比。輸入格式：輸入包括衛(wèi)星觀測到的每棵樹的樹種清單。每行表示一棵樹的樹種，樹種名稱不超過個字符。所有樹種不超過種，不超過棵樹。輸出格式：按字母順序輸出每個樹種的名稱，以及對應(yīng)的百分比，百分比精確到第4個小數(shù)位。答：prtvuScnner;prtvu*;pubccsn{creep<SrngIneger>p=newreep<SrngIneger>;pubccvdnSrng]rg){ntSrng;Scnnern=newScnnerSyen;henhNex){=nnexne; //讀取一行字符串fpcnney) //若出現(xiàn)過ppupge+;//對應(yīng)值增加1ee //若沒有出現(xiàn)過ppu; //對應(yīng)值設(shè)置為n++;}Ierr=pkeySeerr;hehNex){Srngkey=Srngnex; //獲取keyntvue=npgekey; //根據(jù)key獲取Syeuprnkey+"";Syeuprn"%\n"vue*/n;}}}H—水果問題時間限制：，空間限制：。問題概述：夏天來了，Je這樣Je就可以很容易掌握所有水果的銷售情況了。輸入格式：第一行正整數(shù)n（0<n≤100）表示有n組測試數(shù)據(jù)。每組測試數(shù)據(jù)的第一行是一個整數(shù)m（0<m≤100），表示共有m次成功的交易。其后有m行數(shù)據(jù)，每行表示一次交易，由水果名稱（由小寫字母組成，長度不超過80）、水果產(chǎn)地（由小寫字母組成，長度不超過80）和交易的水果數(shù)目（正整數(shù)，不超過100）組成。輸出格式：對于每一組測試數(shù)據(jù)，請你輸出一份排版格式正確（請分析樣本輸出）的水果銷售情況明細表。這份明細表包括所有水果的產(chǎn)地、名稱和銷售數(shù)目的信息，水果先按產(chǎn)地分類，產(chǎn)地按字母順序排列，同一產(chǎn)地的水果按照名稱排序，名稱按字母順序排序。兩組測試數(shù)據(jù)之間有一個空行，最后一組測試數(shù)據(jù)之后沒有空行。答：prtvuScnner;prtvu*;pubccsn{pubccvdnSrng]rg){ntSrng;Scnnern=newScnnerSyen;n=nnexIn;rntc=;cs<n;c++){c=) //Syeuprnn;p<Srngp<SrngIneger>>p=newreep<Srngp<SrngIneger>>;p<SrngIneger>p=newreep<SrngIneger>;=nnexIn;rnt=;i<;++) //輸入個列表項{Srngxy;nt=;Inegerx=nnex; //水果產(chǎn)地y=nnex; //水果名稱=nnexIn; //水果銷售數(shù)fpgey==nu)//y在p中不存在，新建一個y的元素ppuynewreep<SrngIneger>;p=pgey; //取p中y對應(yīng)的子p值fpgex==nu)//x在p中不存在時ppux; //置p的值銷售數(shù)目為ntcn=pgex+;/計x的銷售數(shù)目ppuxcn; //再次插入到p中}Ierr=penrySeerr;//迭代p輸出結(jié)果hehNex){pEnry<Srngp<SrngIneger>>enry=pEnrynex;Syeuprnnenrygeey;//輸出水果名稱p=enrygeue;//取該水果名稱對應(yīng)的子p值p2Ierr=penrySeerr;hehNex //迭代p2{pEnry<SrngIneger>enry=pEnrynex; Syeuprnn"| "+enrygeey+""+enrygeue+"";}}}}}.OJ—beh問題時間限制：，空間限制：。問題描述：：你剛從滑鐵盧搬到了一個大城市。這里的人說一種難以理解的外語方言。幸運的是，你有一本字典可以幫助你理解它們。輸入格式：輸入包含最多個字典條目，后跟一個空行，接下來最多個單詞的消息。每個字典條目為一行，包含一個英文單詞，后跟一個空格和一個外來詞。字典中外來詞不會出現(xiàn)多次。該消息是外來詞序列，每行一個外來詞。輸入中的單詞最多包含10個小寫字母。輸出格式：輸出是翻譯成英文的消息，每行一個字。不在字典中的外來詞應(yīng)翻譯為eh。答：prtvuScnner;prtvu*;pubccsn{pubccvdnSrng]rg){Srngerdrd;Scnnern=newScnnerSyen;p<SrngSrng>yp=newHhp<SrngSrng>;henhNex //處理每個字典條目{=nnexne;fengh==) //break;Srng]p=p"";erd=p;rd=p;yppurderd;//向yp中插入<rderd>}henhNex //處理外來詞{=nnexne;fypcnney)//查字典Syeuprnnypge;//查找成功，輸出英文單詞ee //查找不成功Syeuprnn"eh";//輸出"eh"}}}.OJ—爺爺很出名問題時間限制：，空間限制：。問題描述：：每個人都知道爺爺幾十年來一直是一個非常好的橋牌選手，但當(dāng)宣布他成為吉尼斯世界紀(jì)錄中有史以來最佳橋牌選手時，整個家庭都之興奮。國際橋牌協(xié)會（I）多年來一直保持著世界上最佳橋牌選手的每周排名，每周排名中選手的每次出場計一個點，爺爺被提名為有史以來最好選手，因為他獲得了最高點數(shù)。有許多競爭對手，爺爺非常好奇想知道哪個選手獲得了第二名。由于I排名現(xiàn)已在互聯(lián)網(wǎng)上發(fā)布，他向你尋求幫助。你需要編寫一個程序，當(dāng)給出每周排名列表時，根據(jù)點數(shù)找出哪個或者哪些選手獲得第二名。輸入格式：輸入包含幾個測試用例。所有選手編號是到。每個測試用例的第一行包含兩個整數(shù)n（≤n≤）和（≤≤），分別表示可用的排名數(shù)和每個排名中的選手?jǐn)?shù)量。接下來的n行中的每行都包含一周排名的描述，每個描述由m個整數(shù)組成，由空格分隔，標(biāo)識在每周排名中的選手。你可以假設(shè)，在每個測試用例中只有一個最佳選手和至少一個排名第二的選手，每周排名由m個不同的選手組成。輸入由n=m=0表示結(jié)束。輸出格式：對于每個測試用例，你的程序必須生成一行輸出，其中包含所有排名中出現(xiàn)第二多的選手編號，如果有多個這樣的選手，則按選手編號遞增順序輸出，每個選手編號后面有一個空格。答：prtvuScnner;prtvu*;pubccsn{cnlntN=;cn]nu=newnN;cntecndcn //求nu中第大的次數(shù){ntx=x=;rnt=;i<N;++){fnu>x){x=x;x=nu;}eefnu>x)x=nu;}reurnx;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;henhNex){n=nnexIn;=nnexIn;fn==0&==)brek;rrynu;rnt=;i<n;++)rnt=;j<;++){ntx=nnexIn;nux++;}ntx=ecndcn;benr=rue;rnt=;i<N;++){fnu==x){fr==rue){r=e;Syeuprn;}eeSyeuprn""+;}}Syeuprnn;}}}H—二叉排序樹問題時間限制：，空間限制：。問題描述：判斷兩序列是否為同一二叉搜索樹序列輸入格式：開始一個數(shù)n（1≤n≤20)表示有n個需要判斷，n=0的時候輸入結(jié)束。接下去一行是一個序列，序列長度小于10，包含0~9的數(shù)字，沒有重復(fù)數(shù)字，根據(jù)這個序列可以構(gòu)造出一顆二叉搜索樹。接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉搜索樹。輸出格式：如果序列相同則輸出YES，否則輸出NOn（1≤n≤20n個需要判斷，n=0的時候輸入結(jié)束。接下去一行是一個序列，序列長度小于10，包含0~9的數(shù)字，沒有重復(fù)數(shù)字，根據(jù)這個序列可以構(gòu)造出一顆二叉搜索樹。接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉搜索樹。輸出格式：如果序列相同則輸出YES，否則輸出NO答：prtvuScnner;prtvu*;csSNde //二叉排序樹結(jié)點類{pubcchrkey; //存放關(guān)鍵字這里關(guān)鍵字為chr類型pubcSNdechd; //存放左孩子指針pubcSNderchd; //存放右孩子指針BSTNode() //構(gòu)造方法{chd=rchd=nu;}}csSCs //二叉排序樹類{pubcSNder; //二叉排序樹根結(jié)點prveSNde; //用于存放待刪除結(jié)點的雙親結(jié)點pubcSC //構(gòu)造方法{r=nu;}//二叉排序樹的基本運算算法pubcvdInerSchrk) //插入一個關(guān)鍵字為k的結(jié)點{InerSrk;}prveSNdeInerSSNdepchrk)//在以p為根的S中插入為k的結(jié)點{fp==nu) //原樹為空新插入的元素為根結(jié)點{p=newSNde;pkey=k;}eefkpchd=InerSpchdk;//插入到p的左子樹中eefk>pkey)prchd=InerSprchdk;//插入到p的右子樹中p;}pubcvdCreeSSrng) //由關(guān)鍵字序列創(chuàng)建一棵二叉排序樹{r=newSNde; //創(chuàng)建根結(jié)點rkey=chr;rnt=;<engh;++) //創(chuàng)建其他結(jié)點InerSrchr; //插入關(guān)鍵字]}}pubccsOJ3{cbenSeSCsbSCsb)//判斷b與b是否相同{reurnSebrbr;}cbenSeSNdepSNdep)//被Se調(diào)用{fp==nul&p==nu)returntrue;eefp==nul||p==nu)reurne;ee{fpkey=pkey)reurne;bene=Sepchdpchd;benrgh=Seprchdprchd;reurnet&rgh;}}pubccvdnSrng]rg){ntn;Srng;Scnnern=newScnnerSyen;SCsb=newSC;SCsb=newSC;herue){n=nnexIn; //讀取整數(shù)nfn==)brek;=nnex; //讀取一行字符串sbCreeS; //創(chuàng)建第一個STrnt=;i{=nnex; //讀取一行字符串sbCreeS; //創(chuàng)建要比較的STfSebb //判斷相同性Syeuprnn"ES";eeSyeuprnn"NO";}}}}三、簡答題簡述哈希表查找的基本思想。列舉常用的哈希函數(shù)的構(gòu)造方法。 答：哈希表查找的基本思想是：以記錄的關(guān)鍵字k為自變量，通過一個確定的函數(shù)關(guān)系h（稱之為哈希函數(shù)），計算出對應(yīng)的函數(shù)值h(k)，把這個值解釋為記錄的存儲地址，然后到相應(yīng)的單元里去取要找的記錄。常用的哈希函數(shù)的構(gòu)造方法有：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法等。哈希表是一種查找方法，為什么說它是一種存儲結(jié)構(gòu)？ 答：前面介紹的數(shù)據(jù)存儲結(jié)構(gòu)有順序、鏈?zhǔn)胶退饕鎯Y(jié)構(gòu)，它們都支持關(guān)鍵字的順序查找。而哈希表不支持順序查找，通過關(guān)鍵字將記錄直接映射到表中，屬另一種存儲結(jié)構(gòu)。實際上采用開放定址法構(gòu)建的哈希表就是采用順序存儲結(jié)構(gòu)存儲表元素的，采用拉鏈法構(gòu)建的哈希表是采用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)相結(jié)合的方式存儲表元素的。哈希表查找的時間性能可以達到O，為什么在查找時不總是使用哈希表查找？ 答：哈希表查找的時間性能O是理想情況下的性能，在實際應(yīng)用中的時間性能隨數(shù)據(jù)量和數(shù)據(jù)分布情況的變化而變化，極端情況下也是On間性能。而且采用開放定址法構(gòu)造的哈希表要保證一定的空閑單元的比例，是以犧牲空間來換取時間的。什么是哈希沖突？處理沖突的方法是什么？ 答：在哈希表中，若某個哈希函數(shù)h對于不相等的關(guān)鍵字key和key得到相同的哈希地址（即hkey=hkey），將該現(xiàn)象稱為沖突。解決沖突的主要方法有開放定址法和拉鏈法。為什么哈希表不支持元素之間的順序查找？ 答：哈希表是通過哈希地址來查找對應(yīng)關(guān)鍵字的記錄的，對哈希表來說順序查找沒有任何意義，也沒有提供順序查找機制。和折半查找相比，二叉排序樹查找的優(yōu)缺點各是什么？ 答：二叉排序樹的缺點是可能變得非常不平衡，從而導(dǎo)致查找時間退化為On.有一棵二叉排序樹按先序遍歷得到的序列為：?；卮鹨韵聠栴}：（）畫出該二叉排序樹。（）在等概率下，求查找成功的平均查找長度和查找不成功的平均查找長度。答：（）先序遍歷得到的序列為：，中序序列是一個有序序列，所以為：，由先序序列和中序序列可以構(gòu)造出對應(yīng)的二叉樹，如圖所示。由二叉排序樹的構(gòu)造過程可以看出，一棵二叉排序樹的先序序列即為構(gòu)造該樹的序列，因為在二叉排序樹中插入一個結(jié)點的過程是：先和根結(jié)點比較，小于根結(jié)點時插入到左子樹，大于根結(jié)點時插入到右子樹，所以按照構(gòu)造一棵二叉排序樹即可。將二叉排序樹的先序序列中的關(guān)鍵字依次插入到一棵空的二叉排序樹中，所得到的二叉排序樹與是否相同？為什么？ 答：二叉排序樹與相同。因為二叉排序樹屬于二叉樹，其先序序列的第一個元素一定是二叉排序樹的根，而對應(yīng)先序序列的根后面所有元素分為兩組：從根的后一元素開始的其值小于根的值的一組元素就是樹的左子樹的結(jié)點的先序序列，剩下的元素的值大于根的值，即為樹的右子樹的結(jié)點的先序序列。在把先序序列的元素依次插入初始為空的二叉排序樹時，第一個元素就成樹的根，它后面第一組元素的值都小于根結(jié)點的值，可以遞歸建立根的左子樹；第二組元素的值都大于根結(jié)點的值，可以遞歸建立根的右子樹。證明一棵非空二叉排序樹的中序遍歷序列是從小到大有序的。 答：證明：設(shè)中序遍歷序列為：………n（）并假設(shè)＜，根據(jù)二叉排序樹的生成規(guī)則：、一定是以某一結(jié)點k為根的子樹中的結(jié)點。不妨設(shè)在生成二叉排序樹時，先于輸入，而且≥k（＜k的情況類似）。這樣輸入后一定是k右子樹中的結(jié)點。在輸入時，若≥k，則也成為k右子樹的結(jié)點，但由于＜，所以，不可能成為右子樹中的結(jié)點。若＜k，則成為k左子樹中的結(jié)點，這樣按中序遍歷所得序列為：…k………（）或：……k……（）這樣，（）、（）兩式與（）式矛盾，所以當(dāng)＜時命題成立。同理可以證明先于輸入的情況。證明如果一棵非空二叉樹的中序遍歷序列是從小到大有序的，則該二叉樹是一棵二叉排序樹。 答：證明：對于關(guān)鍵字為k的任一結(jié)點a，由中序遍歷過程可知，在中序遍歷序列中，它的左子樹的所有結(jié)點的關(guān)鍵字排在k的左邊，它的右子樹的所有結(jié)點的關(guān)鍵字排在k的右邊，由于中序序列是從小到大排列的，所以結(jié)點a的左子樹中所有結(jié)點的關(guān)鍵字小于k，結(jié)點a的右子樹中所有結(jié)點的關(guān)鍵字大于k，這滿足二叉排序樹的性質(zhì)，所以該二叉樹是一棵二叉排序樹。簡述靜態(tài)查找表和動態(tài)查找表的異同。 答：靜態(tài)查找表和動態(tài)查找表都是數(shù)據(jù)存儲結(jié)構(gòu)，都適合數(shù)據(jù)查找，前者不便于（并不是不能）數(shù)據(jù)修改操作，如插入和刪除元素，后者方便數(shù)數(shù)據(jù)修改操作。.設(shè)有個數(shù)據(jù)d、r、、repe、he，它們排在一個有序表中，其查找概率分別是p=，p=，p=，p=，p=。而查找它們之間不存在數(shù)據(jù)的概率分別為q=，q=，q=，q=，q=，q=，如下圖所示：（1）試畫出對該有序表分別采用順序查找和折半查找時的判定樹。（2）分別計算順序查找的查找成功和不成功的平均查找長度。（3）分別計算折半查找的查找成功和不成功的平均查找長度。答：（）對該有序表分別采用順序查找和折半查找時的判定樹分別如圖和所示。

折半查找對查找的數(shù)據(jù)有什么要求？ 答：從存儲結(jié)構(gòu)來看，折半查找要求數(shù)據(jù)采用具有隨機存取特性的存儲結(jié)構(gòu)來存儲。從數(shù)據(jù)的有序來看，折半查找要求數(shù)據(jù)是有序的。14.設(shè)有一組關(guān)鍵字為{19，1，23，14，55，20，84，27，68，11，10，77}，其哈希函數(shù)為h(key)=key%13，采用答：1.易知m=19，利用線性探測法計算各關(guān)鍵字存儲地址過程如下：h(19)=19%13=6 h(1)=1%13=1 h(23)=23%13=10h(14)=14%13=1（沖突） d0=1，d1=(1+1)%19=2h(55)=55%13=3 h(20)=20%13=7h(84)=84%13=6(沖突) d0=6，d1=(6+1)%19=7(仍沖突) d2=(7+1)%19=8h(27)=27%13=1(沖突)d0=1，d1=(1+1)%19=2(仍沖突) d2=(2+1)%19=3(仍沖突) d3=(3+1)%19=4h(68)=68%13=3(沖突) d0=3，d1=(3+1)%19=4(仍沖突) d2=(4+1)%19=5h(11)=11%13=11h(10)=10%13=10(沖突) d0=10，d1=(10+1)%19=11(仍沖突) d2=(11+1)%19=12h(77)=77%13=12（沖突） d0=12，d1=(12+1)%19=13由上計算得到的哈希表如下表所示：下標(biāo)0123456789101112131415161718K11455276819208423111077探測次數(shù)121431131132ASL成功=(1+2+1+4+3+1+1+3+1+1+3+2)/12=1.92查找不成功的探測次數(shù)如下表所示：下標(biāo)0123456789101112131415161718K11455276819208423111077探測次數(shù)1987654321543211111由于哈希函數(shù)為h(key)=key%13，所以只考慮h(key)=0-12的情況，故ASL不成功=(1+9+8+7+6+5+4+3+2+1+5+4+3)/13=4.4615.設(shè)有一組關(guān)鍵字為{26，36，41，38，44，15，68，12，6，51，25}，用拉鏈法解決沖突。假設(shè)裝填因子α=0.75，哈希函數(shù)為h(k答：(1)這里n=22，α=n/m=0.75，m=n/0.75=15。哈希函數(shù)為h(k)=k%13，哈希地址空間為T[0...12]。h(26)=26%13=0 h(36)=36%13=10 h(41)=41%13=2 h(38)=38%13=12h(44)=44%13=5 h(15)=15%13=2 h(68)=68%13=3 h(12)=12%13=12h(6)=6%13=6 h(51)=51%13=12 h(25)=25%13=12采用拉鏈法解決沖突建立的鏈表如下圖所示：

(2)ASL成功=(7x1+2