計算機專業(yè)基礎綜合數(shù)據(jù)結構歷年真題試卷匯編8

計算機專業(yè)基礎綜合數(shù)據(jù)結構（集合）歷年真題試卷匯編8（總分:70.00，做題時間：90分鐘）一、綜合題（總題數(shù)：26，分數(shù)：54.00）巳知長度為11的表（xal，wan，wil，zol，yo，xul，yum，wen，wim，zi，yon），按表中元素順序依次插入一棵初始為空的平衡二叉排序樹，畫出插入完成后的平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度?！旧綎|大學2001七（7分）】（分數(shù)：2.00）正確答案：（正確答案:解析：SLsucc正確答案：（正確答案:解析：SLsucc=(1*1+2*2+4*3+4*4)/11=33/11)用關鍵字1，2,3,4的四個結點（1）能構造出幾種不同的二叉排序樹?其中（2）最優(yōu)查找樹有幾種？（3）AVL樹有幾種？（4）完全二叉樹有幾種?試畫出這些二叉排序樹?！颈本┕I(yè)大學1997二、3（5分）】（分數(shù)：2.00）正確答案：（正確答案：（1）本題的實質是給定中序序列1、2、3、4,有幾種不同的二叉排序樹，即該中序序列相當于多少不同的前序序列，這是樹的計數(shù)問題櫻中序序列中元素數(shù)為n，則二又數(shù)的數(shù)目為1/（n+1）C2nn，這里n=4,故有14種。圖示如下： 2）最優(yōu)查找樹有4種，圖中（10）、（11）、（12）、（13）。（3）AVL樹也有4種，圖中（10）、（11）、（12）、（13）。（4）完全二叉樹有1種，圖中（10）。）解析：可以生成下圖所示的二叉排序樹的關鍵字初始序列有幾種?試寫出其中的任意4種?！倦娮涌萍即髮W2005A三、2（6分）】-I（分數(shù)：2.00）正確答案：（正確答案：8種（1）8,9,4,2,6（2）8,9,4,6,2（3）8,4,2,6,9（4）8,4,2,9,6（5）8，4，6,2,9（6）8,4,6,9,2（7）8,4,9,2,6（8）8,4,9,6,2）解析：設二叉排序樹中關鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關鍵字為363的結點，下述關鍵字序列哪一個不可能是在二叉排序樹中查到的序列？說明原因。（1）51，250，501，390，320，340，382,363（2）24,877，125，342，501，623，421，363【東北大學2002一、3（4分）】（分數(shù)：2.00）正確答案：（正確答案：序列（2）不可能是二叉排序樹中查到363的序列。查到501后，因363<501，后面應出現(xiàn)小于501的數(shù)，但序列中出現(xiàn)了623，故不可能。）解析：一棵具有m層的AVL樹至少有多少個結點，最多有多少個結點？【浙江大學1995六（8分）】（分數(shù)：2.00）正確答案：（正確答案：設以N.正確答案：（正確答案：設以N.表示深度為m的AVL樹中含有的最少結點數(shù)。顯然，N°=0，N1=LN2=2,且N=N+N+1（mN2）。這個關系與斐波那契序列類似，用歸納法可以證明：當mN0時，N=Fm+2 m m數(shù)）。當，層的AVL樹是滿二叉樹時，結點數(shù)為最大值2m一1。）解析：設T是一棵高度平衡樹（又稱平衡樹），給定關鍵詞K,如果在T中查找K失敗，且查找路徑上的任一結點的平衡系數(shù)皆為零，試回答用高度平衡樹插入算法在T中插入關鍵詞為K的新結點后，樹T的高度是否一定增加?并回答為什么?！炯执髮W1996四、2（7分）】（分數(shù)：2.00）正確答案：（正確答案：樹的高度一定增加。因為“查找路徑上的任一結點的平衡系數(shù)皆為零”，從根結點開始查找，根結點的平衡因子為零，說明根的左右子樹等高（不一定是滿二叉樹）。沿左（或右）子樹向下查找時，查找路徑上所有結點的平衡因子皆為零，說明任一結點的左右子樹等高，查找失敗是在葉子結點，插入也是在葉子結點，樹的高度自然增加。）解析：試畫出從空樹開始，由字符序列（t，d，e，s，u，g，b,—j，k，r，i）構成的二叉平衡樹，并為每一次的平衡處理指明旋轉類型?！厩迦A大學1994三（10分）】在B一樹和B+樹中查找關鍵字時，有什么不同？【東北大學2002一、5（2分）】（分數(shù)：2.00）正確答案：（正確答案：在B一樹中查找關鍵字從根結點開始，從根往下查找結點，然后在結點內查找關鍵字，得出查找成功與否的結論。B+樹的非終端結點是索引部分，其查找從根開始，從根往下查到關鍵字后，要繼續(xù)查到最下層結點，得到查找成功與否的結論。另外，B+樹還可以在最下層從最小關鍵字開始，從左往右進行順序查找，B一樹則不能作順序查找。）解析：簡要敘述B樹（有些教材中稱為B一樹）與B+樹的區(qū)別?！灸暇┖娇蘸教齑髮W1999六（5分）】（分數(shù)：2.00）正確答案：（正確答案：m階的B+樹和B一樹主要區(qū)別有三：（1）有n棵子樹的結點中含有n（B一樹中n—1）個關鍵字；（2）B+樹葉子結點包含了全部關鍵字信息，及指向含關鍵字記錄的指針，且葉子結點本身依關鍵字大小自小到大順序鏈接，B一樹的葉子結點是失敗結點，實際不存在；（3）B+樹的非終端結點可以看成是索引部分，結點中只含其子樹（根結點）中最大（或最?。╆P鍵字。B+樹的查找既可以順序查找，也可以隨機查找，B一樹只能隨機查找。）解析：當B一樹作為文件的索引時，一個結點除了包含關鍵字和指向孩子結點的指針外，還包含指向文件記錄的指針。假設一個結點占用的最大空間被限定為4096字節(jié)，每個關鍵字和每個指針都占2字節(jié)。如果采用n階B樹作為文件的索引，則它的最大的階數(shù)應該是多少？【北京理工大學2006十一、5（5分）】（分數(shù)：2.00）正確答案：（正確答案：因為每個非終端結點中包含下列信息數(shù)據(jù)（n，P0，K1，P1，K2，P2，…，Kn，Pn），其中n是關鍵字個數(shù)，P0指向關鍵字比K1小的結點，（Kj，Pi）（1WiWn）成對出現(xiàn)，按題意，，結點中還包含指向文件記錄的指針，即一個關鍵字要占用6字節(jié)：每個結點還包括該結點的關鍵字個數(shù)和小于第一個關鍵字的指針。故最大階數(shù)應是（4096—4）/6=682。）解析：證明：高為h（不含葉子層）的m階B一樹上最多有mh一1個關鍵字?！颈本┙煌ù髮W2006四、2（5分）】（分數(shù)：2.00）正確答案：（正確答案：m階正確答案：（正確答案：m階B樹的每個結點最多有m1個關鍵字，第一層m—1個關鍵字，第二層m（m一1）個關鍵字，第三層m2（m—1）個關鍵字，……，第h層mi（m—1）個關鍵字。將各層關鍵字數(shù)相加，得證。）解析：滿二叉檢索樹符合B樹定義嗎?B樹的插入和刪除算法適用于滿二叉檢索樹嗎?為何？【東南大學1995五（6分）】（分數(shù)：2.00）正確答案：（正確答案：滿二叉檢索樹可以看作是三階B一樹（2—3樹）。B一樹的插入和刪除算法不適合滿二叉檢索樹。滿二叉檢索樹插入和刪除結點后均破壞了“多路平衡查找樹”“葉子在同一層上”（查找失敗結點）的定義。）解析：含9個葉子結點的3階B一樹中至少有多少個非葉子結點?含10個葉子結點的3階B一樹中至多有多少個非葉子結點？【東南大學2005一、1（5分）】【北京輕工業(yè)學院2000八（10分）】（分數(shù)：2.00）正確答案：（正確答案：含9個葉子結點的3階B一樹至少有4個非葉子結點，當每個非葉子結點均含3棵子樹，第三層是葉子結點時就是這種情況。當4層3階B一樹有10個葉子結點時，非葉子結點達到最大值8個：其中第一層1個，第二層2個，第三層5個。）解析：設依以下次序給出關鍵字：34，16，19，21，5，49，24，62，3，17，45，8，構造3階B一樹。要求從空樹開始，每插入一個關鍵字，畫出一個樹形?！灸祥_大學1997六（10分）】15.對下面的3階15.對下面的3階B一樹，依次執(zhí)行下列操作，畫出各步操作的結果?！竞戏使I(yè)大學1999四、3（5分）】（1）插入90（2）插入25（3）插入45⑷刪除60（5）刪除80（分數(shù)：2.00）正確答案：（正確答案：解析：（2）.對樹（b），請分別畫出（分數(shù)：2.00）正確答案：（正確答案：解析：（2）.對樹（b），請分別畫出先后刪除53,37兩個結點后的樹形。（分數(shù)：2.00）16.階B樹中（如圖所示），插入關鍵字87,試畫出插入調整后樹的形狀。【東南大學1999五（15分）】（分數(shù)：2.00）設有關鍵碼序列10,20,35,40,44,51,65,70,85,91,93,95。試按照最大關鍵碼復寫原則繪出相應的2階B+樹?！旧綎|工業(yè)大學1996二、1（6分）】回答問題并填空。（1）（2分）散列表存儲的基本思想是什么？（2）（4分）散列表存儲中解決碰撞的基本方法有哪些?其基本思想是什么？（3）（4分）用分離的同義詞子表解決碰撞和用結合的同義詞表解決碰撞屬于哪種基本方法?他們各有何特點？（4）（3分）用線性探查法解決碰撞時，如何處理被刪除的結點?為什么？（5）（2分）散列法的平均檢索長度不隨（）的增加而增加，而是隨（）的增大而增加?！旧綎|工業(yè)大學1999四（15分）】（分數(shù)：2.00）正確答案：（正確答案：（1）哈希表存儲的基本思想是用關鍵字的值決定數(shù)據(jù)元素的存儲地址。（2）哈希表存儲中解決碰撞的基本方法：①開放定址法。形成地址序列的公式是：H「=（H（key）+dj）%m，其中m是表長，d「是增量。根據(jù)d「取法不同，又分為三種：a.d「=1,2,…，m—1稱為線性探測再哈希，其特點是逐個探測表空間，只要哈希表中有空閑空間，就可解決碰撞，缺點是容易造成“聚集”，即不是同義詞的關鍵字爭奪同一哈希地址。b.d.=12,一-12,22,一-22,..?，土k2（kWm/2）稱為二次探測再哈希，它減少了聚集，但不容易探測到全部表空間，只有當表長為形如4j+3（,為整數(shù)）的素數(shù)時才有可能。c.d.=偽隨機數(shù)序列，稱為隨機探測再哈希。②再哈希法。H.=RH.（key）i=1,2,…，k,是不同的哈希函數(shù)，即在同義詞產生碰撞時，用另一哈希函數(shù)計算哈希地址，直到解決碰撞。該方法不易產生“聚集”，但增加了計算時間。③鏈地址法。將關鍵字為同義詞的記錄存儲在同一鏈表中，哈希表地址區(qū)間用研0—..m—1］表示，哈希表元素初始值為空指針。凡哈希地址為f（0WiWm—1）的記錄均插在以研［i］為頭指針的鏈表中。這種解決方法中數(shù)據(jù)元素個數(shù)不受表長限制，插入和刪除操作方便，但增加了指針的空間開銷。這種哈希表常稱為開哈希表，“開”的含義是哈希表無邊界，元素個數(shù)沒限制，哈希表不會溢出，只受存儲空間限制。而①中的哈希表稱閉哈希表，“閉”含義是元素個數(shù)受表長限制。④建立公共溢出區(qū)。設H［0一m一1］為基本表，凡關鍵字為同義詞的記錄，都填入溢出區(qū)O［0..m—1］。（3）用分離的同義詞表和結合的同義詞表解決碰撞均屬于鏈地址法。鏈地址向量空間中的每個元素不是簡單的地址，而是關鍵字和指針兩個域，哈希地址為i（0WiWm—1）的第一個關鍵字存儲在地址空間向量下標為i的“關鍵字”域。前者的指針域是動態(tài)指針，指向同義詞的鏈表，具有上面③的優(yōu)缺點；后者實際是靜態(tài)鏈表，同義詞存在同一地址向量空間（從最后向前找空閑單元），以靜態(tài)指針（下標）相連。這節(jié)省了空間，但易產生“堆積”，查找效率低。（4）要在被刪除結點的哈希地址處作標記，不能物理地刪除。否則，中斷了查找通路。（5）記錄、負載因子）解析：如何衡量Hash函數(shù)的優(yōu)劣?簡要敘述Hash表技術中的沖突概念，并指出三種解決沖突的方法?！灸暇┖娇蘸教齑髮W1996九、2（6分）】（分數(shù)：2.00）

正確答案：（正確答案：評價哈希函數(shù)優(yōu)劣的因素有：能否將關鍵字均勻影射到哈?？臻g上，有無好的解決沖突的方法，計算哈希函數(shù)是否簡單高效。由于哈希函數(shù)是壓縮映像，沖突難以避免。解決沖突的方法見上面52題（2）。）解析：Hash方法的平均查找路長決定于什么？是否與結點個數(shù)N有關?處理沖突的方法主要有哪些？【中國人民大學2000一、4（4分）】（分數(shù)：2.00）正確答案：（正確答案：哈希方法的平均查找路長主要取決于負載因子（表中實有元素數(shù)與表長之比），它反映了哈希表的裝填程度，該值一般取0.65?0.9。解決沖突方法見上面52題（2）。）解析：在采用線性探測法處理沖突的散列表中，所有同義詞在表中是否一定相鄰？【西安電子科技大學2000計算機應用一、8（5分）】（分數(shù)：2.00）正確答案：（正確答案：不一定相鄰。哈希地址為i（0WiWm—1）的關鍵字，和為解決沖突形成的探測序列i的同義詞，都爭奪哈希地址i。）解析：假定有k個關鍵字互為同義詞，若用線性探測法將這k個關鍵字存入散列表中，至少需要進行多少次探測？【廈門大學2006四、2（25/3分）】（分數(shù)：2.00）正確答案：（正確答案：k（k+1）/2。每次探測的次數(shù)依次是1，2,…，k。）解析：設有一組關鍵字｛9，01，23，14，55，20，84，27），采用哈希函數(shù)：H（key）=keymod7，表長為10，用開放地址法的二次探測再散列方法Hi=（H（key）+di）mod10（di=12，22，32，…）解決沖突。要求：對該關鍵字序列構造哈希表，并計算查找成功的平均查找長度?！緰|北大學2002二、2（5分）】（分數(shù)：2.00）:ASL:ASL=(1+1+1+2+3+4+1+2)/8=15/8以關鍵字27為例:SUCC2=(6+22)%10=0(沖突)，H3=(6+33)%10=5,H（27）=27%7=6（沖突），H1=（6+1）%10=7（沖突），H所以比較了4次。） 1解析：對下面的關鍵字集｛30，15，21，40，25，26，36，37｝，若查找表的裝填因子為0.8，采用線性探測再散列方法解決沖突。（1）設計哈希函數(shù)；（2）畫出哈希表；（3）計算查找成功和查找失敗的平均查找長度;（4）寫出將哈希表中某個數(shù)據(jù)元素刪除的算法?！緰|北大學2001六（18分）】（分數(shù)：2.00）正確答案：（正確答案：由于裝填因子為0.8,關鍵字有8個，所以表長為8/0.8=10。（1）用除留余數(shù)法，哈希函數(shù)為H（key）=key%7。（2）——（3）計算查找失敗時的平均查找長度，必須計算不在表中的關鍵字，當其哈希地址為i（0WiWm—1）時的查找次數(shù)。本例中雖然m=10，但真正的哈希地址是0?6。故查找失敗和查找成功時的平均查找長度分別為：ASL=（9+8+7+6+5+4+3）/7=6ASL=16/8=2（4）intUNSUCC SUCCdelete（inth[n]，intk）//從哈希表h[n]中刪除元素k，若刪除成功返回1，否則返回.｛i=k%7；//哈希函數(shù)用H（key）=key%7if（h[i]==maxint｝//maxint解釋成空地址｛count＜）解析：二、設計題（總題數(shù)：8,分數(shù)：16.00）假設一棵平衡二叉樹的每個結點都標明平衡因子，試設計一個非遞歸算法，利用平衡因子，求平衡二叉樹的高度。【南京航空航天大學2003八（10分）】（分數(shù)：2.00）正確答案：（正確答案：算法的核心語句段如下：while（p）//求平衡二叉樹高度，初值是根結點的指針（1evel++；//樹的高度增1，level初值是0if（p—>bfrchild；llbf=-1沿右分支向下elsep=p一>Ichild；//bf>=0沿左分支向下}//while）解析：在平衡二叉排序樹的每個結點中增設一個lsize域，其值為它的左子樹的結點數(shù)加1。試寫一時間復雜度為D（10gn）的算法，確定樹中第尼個結點的位置。【大連理工大學2005三、2（45/3分）】（分數(shù)：2.00）正確答案：（正確答案：設平衡二叉排序樹根結點的指針是pbst，（1）若pbst一>lsize=k，則根結點即為所求；（2）按根結點的位序與k的關系，k小到左（大到右）子樹去查找：根結點的左右子女分別是第pbst一>lchild—>lsize和pbst->lsize+pbst—>rchild->lsize個結點。）解析：在二又鏈表的每個結點中添加一個域intdepth，表示以該結點為根的子樹的深度（結構編者略）。（1）試編寫一遞歸函數(shù)。BiTreeDepth（BiTreeT），計算二叉樹T中每個結點的depth值，函數(shù)的返回值為樹T的深度。（2）在（1）的基礎上（即巳求出二叉樹中每個結點的depth值），編寫一遞歸函數(shù)BiTreeBalance（BiTreeT），判斷二叉排序樹T是否為平衡二叉樹，如果是平衡二叉樹，則函數(shù)的返回值為真。【北京理工大學2006十^一、2（25/2分）】（分數(shù)：2.00）正確答案：（正確答案：（1）設根的層數(shù)為1，進行遍歷，在遍歷中填寫結點的層數(shù)，結點的最大層次就是所求。（2）若任一結點其左右子女的層次差的絕對值大于1，則不是平衡二叉排序樹。voidBiTreeDep七h（BiTreeT，intdepth）{if（!T）return0else{T—>depth++；if（T—>depth>maxdepth）maxdepth=T—>depth；//maxdepth是全局變量，初值0if（T—>Ichild）BiTreeDepth（T—>Ichild，depth+1）；//左子樹上各結點的層次if（T—>rchild）BiTreeDepth（T—>rchild，depth+1）；//右子樹上各結點的層次}}//使用BiTreeDepth（T，0）調用）解析：（1）設二叉排序樹中關鍵字由1至1000的整數(shù)組成，現(xiàn)要檢索關鍵字為363的結點，下述關鍵字序列中哪些可能是二叉排序樹上搜索到的序列，哪些不可能是二叉排序樹上搜索到的序列？a.2,252,401，398,330，344,397,363b.924,220，911，244,898,258,362,363c.925,202,911，240，912,245,363d.2，399，387,219,266,382,381,278,363（2）通過對（1）的分析，寫一個算法判定給定的關鍵字序列（假定關鍵字互不相同）是否可能是二叉排序樹的搜索序列。若可能是返回真，否則返回假?？杉俣ū慌卸ǖ男蛄兴却嫒霐?shù)組中?！局袊茖W技術大學1998】（分數(shù)：2.00）正確答案：（正確答案：（1）A、B、D有可能是二叉排序樹的查找序列。C不可能是。（2）二叉排序樹的查找走了一條從根結點到子孫結點的路徑。查找開始時首先和根結點的值比較，若根結點的值大于待查結點的值，則到左子樹中查找，否則到右子樹中查找。子樹根結點的值和待查結點值的比較，也遵循如上規(guī)律。在查找過程中逐漸縮小查找范圍。我們用high表示查找的上界，用low表示查找的下界，若low>high,則不是二叉排序樹的查找序列。算法的核心語句段如下：low=preLow=—maxint,high=preHigh=maxint；//max是機器最大數(shù)while（low<high&&ilow&&icn）//相當于沿右子女方向走，在某結點左轉時退出{preLow=low；low=a[i++]）if（i<high&&i<high）；）解析：設二叉樹以二又鏈表形式存放，一棵二又樹的繁茂程度定義為各層結點數(shù)的最大值與樹的高度的乘積。試設計一個高效算法，求二叉樹的繁茂程度。【大連理工大學2008三、3（10分）】（分數(shù)：2.00）正確答案：（正確答案：本題實際是找大于等于item的最小元素，找到就成功。失敗時，若在表尾，則返回0,否則此位置就為所求。算法核心語句段如下：intlow=1，high=n； //必須大于0,否則出錯while（low<=high）｛mid=（10w+high）/2；if（item>R[mid]）low=mid+1；elseif（item解析：請用類C或