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

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

k

-1)

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

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

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

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

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

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

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

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

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

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

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

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

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

，且分布如下：

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

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

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

時(shí)，ASLb。取最小值。本題每塊長(zhǎng)度10(說(shuō)明，本題每塊長(zhǎng)1011可，對(duì)索