計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(集合)歷年真題試卷匯編2

計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（集合）歷年真題試卷匯編(分：64.00做題時間：分鐘)一、填空(總題數(shù)：14，分數(shù)：28.00)1.對于具144個記錄的文件若采用分塊查找法且每塊長度為則平均查找長度為__________【北方交通大學(xué)2001二、__________________________________________________________________________________________正確答案：確答案：14計算過程如下1448=18，索引表順序查找，(18+1)／2+(8+1)／。2.有一個2000項表，欲采用等分區(qū)間順序查找方法進行查找，則每塊的理想長度是(1)，分成(2)塊最為理想，平均查找長度是(3)?！局袊V業(yè)大學(xué)一、)】__________________________________________________________________________________________正確答案：(確答案：(1)45(2)45(3)46(索表順序查找))3.分塊檢索中，若引表和各塊內(nèi)均用順序查找，則有900個元素的線性表分成__________塊好；若分成25塊其平均查找長度為_________?！颈本┕I(yè)大1999一、5(2)__________________________________________________________________________________________正確答案：(確答案：30，31．引表順序查找))4.執(zhí)行順序查找時儲存方式可以(1)，二分法查找時，求線性(2)分塊查找時要求線性(3)而散列表的查找，要求線性表的存儲方式是(4)?！旧綎|大學(xué)1998一、1(3)__________________________________________________________________________________________正確答案：(確答案：(1)序存儲或鏈?zhǔn)酱鎯?2)順序存且有(3)塊順序存儲，塊間有序(4)列存儲)5.查找是非數(shù)值程設(shè)計的一個重要技術(shù)問題基本上分成(1)查(2)找和3)找處理哈希沖突的方法有(4)、(6)和7)?！救A北計機系統(tǒng)工程研究所1999一5分__________________________________________________________________________________________正確答案：(確答案：(1)態(tài)查找表動態(tài)查找表(3)哈希表(4)開放定方法(5)鏈址方法再哈希(7)立公共溢出區(qū)6.如果按關(guān)鍵碼值增的順序依次將關(guān)鍵碼值插入到二叉排序樹中，則對這樣的二叉排序樹檢索時，平均比較次數(shù)為__________【山東大學(xué)二1(4分__________________________________________________________________________________________正確答案：(確答案：（n+1)／2)7.在含有n個結(jié)點的二叉排序樹中查找一個關(guān)鍵字，進行關(guān)鍵字比較次數(shù)的最大值是_________。北京交通大學(xué)2004一、15(2)】__________________________________________________________________________________________正確答案：(確答案：n)8.在二叉排序樹上功地找到一個結(jié)點，在平均情況下的時間復(fù)雜性是：__________，在最壞情下的時間復(fù)雜性是__________【上海交通大學(xué)五1(15／4分)】__________________________________________________________________________________________正確答案：(確答案：O(logn)O(n))9.AVL__________是完全二叉樹；完全二叉樹__________是。【電子科技大學(xué)二、5(1分】__________________________________________________________________________________________正確答案：確答案：不一定，一定。需要說明AVL是平衡二叉樹，各個結(jié)點值之間滿足確定關(guān)系。從樹形上看，完全二又樹任意結(jié)點左右子樹的高度差的絕對值不大于僅從結(jié)點平衡因子角度看，可以說完全二叉樹是平衡二叉樹。)10.一深度為k的平衡二叉樹每個非終端結(jié)點的平衡因子均為該樹共有__________個結(jié)點濟大學(xué)2005一、．)】__________________________________________________________________________________________正確答案：(確答案：2

k

-1)

11.在棵m階B一樹中若在某結(jié)點中插入一個新關(guān)鍵字而引起該結(jié)點分裂則此結(jié)點中原有的關(guān)鍵字的個數(shù)是__________若在某結(jié)點中刪除一個關(guān)鍵字而導(dǎo)致結(jié)點合并，則該結(jié)點中原有的關(guān)鍵字的個數(shù)是__________【中國科技大學(xué)1998、)【南京理工大學(xué)20014(3分)__________________________________________________________________________________________正確答案：(確答案：m-1[m／2]一1)12.高為4的3階B一樹中，最多有__________個鍵字?！竞戏使I(yè)大2000三、9(2分)】__________________________________________________________________________________________正確答案：(確答案：26(第4是葉子，每個結(jié)點兩個關(guān)鍵字)13.高4(不含葉子層)的4階B一樹最少有__________個關(guān)鍵字?！颈本┙煌ù髮W(xué)、分)】__________________________________________________________________________________________正確答案：(確答案：31)14.高為5的平衡二叉樹，其結(jié)點數(shù)最多可以__________個；最少可以__________個【中國科學(xué)技術(shù)大學(xué)1997二、分)】__________________________________________________________________________________________正確答案：(確答案：31，二、判斷(總題數(shù)：10，分數(shù)：20.00)15.若填因子α為，則向列表中散列元素時一定會產(chǎn)生沖突。)【北京郵電大2005、8(1分)】A.確B.誤

√若裝填因子α為1再插入元素一定產(chǎn)生沖突。若α<1也不能避免碰撞的產(chǎn)生。16.若列表的負載因子αA.確B.誤

√17.隨裝填因子α的增大用閉散列法解決沖突其平均搜索長度比用開散列法解決沖突時的平均搜索長度增長得慢。()【清華大學(xué)2002、12(1分)】A.確B.誤

√18.在列檢索中，“比較”操作一般也是不可避免的。)【華南理工大學(xué)2001、)A.確B.誤

√19.散函數(shù)越復(fù)雜越好，因為這樣隨機性好，沖突概率小。)【京理工大學(xué)1997、分)】A.確B.誤

√不能說哪種哈希函數(shù)的選取方法最好，各種選取方法都有自己的適用范圍。20.Hash的平均查找長度與處理沖突的方法無關(guān)。()【南京航空航天大1997一9(1分)A.確B.誤

√21.負因子填因子)散列表的一個重要參數(shù)，它反映散列表的裝滿程度(【中科院軟件所六(3)(2)【中國海洋大學(xué)2006二13(1分)【上海海事大學(xué)2005、10(2)A.確B.誤

√22.散法的平均檢索長度不隨表中結(jié)點數(shù)目的增加而增加，而是隨負載因子的增大而增大()【山大學(xué)1994一、分)】A.確B.誤

√23.哈表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含任何指針。)【山大學(xué)2001一、6(1分)】A.確B.誤

√哈希表的結(jié)點中可以包括指針，指向其元素。

24.雜表的查找效率主要取決于構(gòu)造雜湊表時選取的雜湊函數(shù)和處理沖突的方法。)吉林大學(xué)一、7(1)A.確√B.誤三、綜合(總題數(shù)：7，分數(shù)16.00)將關(guān)鍵字序列(78，30，1118，9，列存儲到散列表中，散列表的存儲空間是一個下標(biāo)0開始的一維數(shù)組，散列函數(shù)為：H(key)=(key×3)MOD7處理沖突采用線性探測再散列法，要求裝填載)因子為07（分數(shù)：4.00）(1).畫出所構(gòu)造的散列表。__________________________________________________________________________________________正確答案：確答案：因裝填)子為0．有元素，故散列表長m=7／．7=10。造的哈希表如下：)(2).分計算等概率情況下查找成功和查找不成功的平均查找長度。【2010年全國試題41(10)__________________________________________________________________________________________正確答案：(確答案：ASL

=17*(1*4+2*1+3*2)==127ASL

=1／7*(3+2+1+2+l+5+4)=18／計算查找失敗時的平均查找長度計算不在表中的關(guān)鍵字哈希地址為≤m1)時查找次數(shù)。一般情況下分母為表長，但本例哈希地址是6所以分母為哈希地址為的失敗比較次數(shù)是從i開始往右循環(huán)數(shù)到?jīng)]有數(shù)據(jù)的位置(端情況是表長m)。)25.在多查找和排序算法中，經(jīng)常使用“監(jiān)視哨”，其目的是什么順序表上的順序查找為例，說明如何設(shè)置“監(jiān)視哨”?江蘇大學(xué)三8(5分__________________________________________________________________________________________正確答案(確答案監(jiān)視哨的作用是免去查找過程中每次都要檢測整個表是否查找完畢，提高了查找效率。順序表上順序查找時監(jiān)視哨可以設(shè)在低端(下標(biāo)0)或高端標(biāo)n+1)。)26.采比較的方法，從具有n個元素合中找出最大和次最大的元素，需要的最少比較次數(shù)為多少明理由和實現(xiàn)的方法?！旧虾＝煌ù髮W(xué)七10分)__________________________________________________________________________________________正確答案：(確答案：使用堆，選最大元素最多比較不超過次，再選次大素用logn。)27.在度為n的線性表中進行順序查找。查找第數(shù)據(jù)元素的概率為p

，且分布如下：

請求出在該線性表中查找成功的平均查找長度(要求寫成關(guān)于n的簡單表達式形)【北京航空航天大2007一、4(5)__________________________________________________________________________________________正確答案：(確答案：

)28.對一個有序順序表來說，折半查找是否任何時候都比順序查找快什么?上海交通大學(xué)2005三6分)__________________________________________________________________________________________正確答案(確答案：并非在任何情況下折半查找都比順序查找快。例如，若待查元素是該順序表的第一個元素，則順序查找順序表會更快。對有序順序表采用順序查找，若元素存在表中，則在任一位置，查找都可能成功。同樣，若元素不在表中，則在任一位置，查找都可能結(jié)束。折半查找必須經(jīng)一系列計算，方知查找成功還是失敗。盡管如此，一般說來，在大多數(shù)情況下，折半查找還是比順序查找快。29.對度為101的表進行分塊查找確定所在的塊及塊內(nèi)查找均采用順序查找假設(shè)查找表中每個記錄的概率相等。怎樣分塊可以使得小?給出理由?！颈本┙煌ù?006、分)】__________________________________________________________________________________________

正確答案：(確答案：設(shè)有n記錄，每塊內(nèi)有s個錄，容易證明；當(dāng)s

時，ASLb。取最小值。本題每塊長度10(說明，本題每塊長1011可，對索