《數(shù)據(jù)結(jié)構(gòu)與算法》三

《數(shù)據(jù)結(jié)構(gòu)與算法》三您的姓名：[填空題]*_________________________________一、單項(xiàng)選擇題散列表的地點(diǎn)區(qū)間為0-17,散列函數(shù)為H(K)=Kmod17。采納線性探測(cè)法辦理矛盾，并將重點(diǎn)字序列43，42，89，55，25，35，76挨次儲(chǔ)存到散列表中。則元素76寄存在散列表中的地點(diǎn)是（）.[單項(xiàng)選擇題]*911(正確答案)1082.將5個(gè)元素散列到200000個(gè)單元的哈希表中，則（）產(chǎn)生矛盾。[單項(xiàng)選擇題]*仍可能會(huì)(正確答案)必定不會(huì)必定會(huì)以上答案均不對(duì)3.一組長(zhǎng)度為11的整型重點(diǎn)字為{22,32,23,45,54,56,65,76,78,89,100}，經(jīng)過(guò)哈希函數(shù)H（key）=keyMOD11映照到長(zhǎng)度為11的哈希表中，裝填因子為（）.[單項(xiàng)選擇題]*1(正確答案)23D.44.對(duì)包含n個(gè)元素的散列表進(jìn)行查找，時(shí)間度雜度為（）.[單項(xiàng)選擇題]*O(n*n)O(log2n)O(n)不直接依靠于n(正確答案)矛盾指的是（）.[單項(xiàng)選擇題]*兩個(gè)元素?fù)碛型瑯有蛱?hào)兩個(gè)元素的鍵值不一樣不一樣鍵值對(duì)應(yīng)同樣的儲(chǔ)存地點(diǎn)(正確答案)兩個(gè)元素的鍵值同樣在哈希表里，裝填因子的計(jì)算公式為（）.[單項(xiàng)選擇題]*填入記錄數(shù)/哈希表的長(zhǎng)度(正確答案)1-（表中填入的記錄數(shù)/哈希表的總長(zhǎng)度）哈希表未填空白處/哈希表的長(zhǎng)度以上都不正確對(duì)于線性表（7,34,55,25,64,46,20,10）進(jìn)行散列儲(chǔ)存時(shí)，若使用H（K）=K%9作為散列函數(shù)，則散列地點(diǎn)為1的元素有（）個(gè)。[單項(xiàng)選擇題]*1234(正確答案)8.哈希表長(zhǎng)為

16，散列函數(shù)

H(key)=key%11,表中已有的重點(diǎn)字為

26，49，72，95共4個(gè)，將

60的結(jié)點(diǎn)裝入表中，用二次探測(cè)再散列法解決矛盾，地點(diǎn)是（）。

[單選題]*A.8B.9(正確答案)C.5D.3二、多項(xiàng)選擇題下邊屬于結(jié)構(gòu)哈希函數(shù)的方法是（）.*直接定址法(正確答案)數(shù)字剖析法(正確答案)除留余數(shù)法(正確答案)平方取中法(正確答案)使用再哈希法的特色有（）.*A.在同義詞產(chǎn)生地點(diǎn)矛盾時(shí)計(jì)算另一個(gè)哈希函數(shù)的地點(diǎn)，直到矛盾不再發(fā)生(正確答案)B.這類方法不易產(chǎn)生“齊集”(正確答案)C.該方法增添了計(jì)算的時(shí)間(正確答案)該方法呈線性探測(cè)再散列對(duì)于哈希表的裝填因子，以正確的有（）.*A.裝填因子的值越小，發(fā)生矛盾的概率越小(正確答案)裝填因子越大，表中填入的記錄越多，在填入的時(shí)候發(fā)生矛盾的可能性就越大，在進(jìn)行查找時(shí)候，查找的次數(shù)也就越多。(正確答案)裝填因子=表中填入的記錄數(shù)/哈希表的總長(zhǎng)度(正確答案)裝填因子的值越小，就能夠防止矛盾的發(fā)生在哈希表進(jìn)行查找時(shí)，以下不是解決矛盾的方法包含（）.*數(shù)字剖析法(正確答案)除留余數(shù)法(正確答案)直接地點(diǎn)法(正確答案)線性探測(cè)再散列法屬于辦理哈希矛盾的主要方法是（）.*開(kāi)放定址法(正確答案)再哈希法(正確答案)除留余數(shù)法直接定址法三、判斷題哈希表的一個(gè)重要參數(shù)——裝填因子，它反應(yīng)哈希表的裝滿程度。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)哈希函數(shù)是依據(jù)重點(diǎn)字確立儲(chǔ)存地點(diǎn)的函數(shù)。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)16.哈希矛盾是不一樣重點(diǎn)字由哈希函數(shù)獲得同樣儲(chǔ)存地點(diǎn)的現(xiàn)象。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)哈希法的查找效率主要取決于哈希表結(jié)構(gòu)時(shí)選用的哈希函數(shù)和辦理矛盾的方法。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)18.哈希表是一種將重點(diǎn)字變換為儲(chǔ)存地點(diǎn)的儲(chǔ)存方法。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)選擇好的哈希函數(shù)就能夠防止矛盾的發(fā)生。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)20.散列儲(chǔ)存法的基本思想是由重點(diǎn)字的值決定數(shù)據(jù)的儲(chǔ)存地點(diǎn)。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)一、單項(xiàng)選擇題1.以下（）不是利用查找表中數(shù)據(jù)元素的關(guān)系進(jìn)行查找的方法。.[單項(xiàng)選擇題]*均衡二叉樹(shù)有序表的查找散列查找(正確答案)二叉排序樹(shù)的查找2.數(shù)據(jù)結(jié)構(gòu)與算法中，假設(shè)有

k個(gè)重點(diǎn)字互為同義詞，若用線性探測(cè)法把這

k個(gè)關(guān)鍵字存入散列表中，起碼要進(jìn)行多少次探測(cè)？（）。

[單項(xiàng)選擇題]*A.k-1

次B.k次k+1次k（k+1）/2次(正確答案)3.一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，（）次比較后查找成功.[單項(xiàng)選擇題]*234(正確答案)5二分查找有序表{4，6，10，12，20，30，50，70，88，100},若查找表中元素58，則它將挨次與表中（）比較大小，查找結(jié)果是失敗.[單項(xiàng)選擇題]*30，88，70，5020，70，30，50(正確答案)20，5030，88，50設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H（key）=key％11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其他地點(diǎn)為空。如用二次探測(cè)再散列辦理矛盾，重點(diǎn)字為49的結(jié)點(diǎn)的地點(diǎn)是（）.[單項(xiàng)選擇題]*8359(正確答案)有一個(gè)長(zhǎng)度為12的有序表，按折半查找法對(duì)其進(jìn)行查找，在表內(nèi)各元素等概率狀況下查找成功所需的均勻比較次數(shù)為（）.[單項(xiàng)選擇題]*35/1237/12(正確答案)39/1243/127.理想狀況下，在散列表中查找一個(gè)元素的時(shí)間復(fù)雜度為：（）.[單項(xiàng)選擇題]*O(n)O(n*n)O(log2n)O(1)(正確答案)在重點(diǎn)字序列（7，10，12，18，28，36，45，92）中，用二分查找重點(diǎn)字92，要比較（）次才找到.[單項(xiàng)選擇題]*234(正確答案)5二、多項(xiàng)選擇題裝填因子的計(jì)算方法不是（）.*A.1-(表中未填入記錄的數(shù)量/哈希表的總長(zhǎng)度)B.表中未填入記錄的數(shù)量/哈希表的總長(zhǎng)度(正確答案)C.(表中未填入的記錄數(shù)-1)/哈希表的總長(zhǎng)度(正確答案)D.表中填入的記錄數(shù)/哈希表的總長(zhǎng)哈希表的查找效率取決于（）.*A.哈希函數(shù)(正確答案)B.辦理矛盾的方法(正確答案)C.哈希表的裝填因子(正確答案)無(wú)正確答案設(shè)散列表（哈希表）中有m個(gè)儲(chǔ)存單元，散列函數(shù)H(key)=key%p，則p不要選擇（）.*A.小于等于m的最大奇數(shù)(正確答案)B.小于等于m的最大素?cái)?shù)C.小于等于m的最大偶數(shù)(正確答案)D.小于等于m的最大合數(shù)(正確答案)二叉排序樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為8個(gè)，則度為2的結(jié)點(diǎn)的數(shù)量不是（）.*5(正確答案)6(正確答案)78(正確答案)以下選項(xiàng)中說(shuō)法不正確的選項(xiàng)是（）.*A.二叉排序樹(shù)能夠含有0個(gè)結(jié)點(diǎn)，這時(shí)它是一棵空二叉排序樹(shù)B.二叉排序樹(shù)能夠含有0個(gè)結(jié)點(diǎn)，這時(shí)它是一棵滿二叉排序樹(shù)(正確答案)C.二叉排序樹(shù)能夠含有0個(gè)結(jié)點(diǎn)，這時(shí)它是一棵完整二叉排序樹(shù)(正確答案)D.無(wú)正確答案(正確答案)三、判斷題折半查找法要求待查表的重點(diǎn)字值一定有序。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)15.對(duì)有序表而言采納折半查找總比采納次序查找法速度快。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)16.二叉排序樹(shù)是一種靜態(tài)查找表。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)哈希表是按散列儲(chǔ)存方式結(jié)構(gòu)的儲(chǔ)存結(jié)構(gòu)。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)在哈希函數(shù)H(key)=key%P中，P一般應(yīng)取偶數(shù)。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)對(duì)二叉排序樹(shù)進(jìn)行查找的方法是用待查的值與根結(jié)點(diǎn)的鍵值進(jìn)行比較，若比根結(jié)點(diǎn)小，則持續(xù)在右子樹(shù)中查找。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)對(duì)于長(zhǎng)度為n的線性表，若采納折半查找，則時(shí)間復(fù)雜度為：O（log2n）。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)一、單項(xiàng)選擇題1.排序算法一般是依據(jù)（）的大小，從頭安排各元素的次序.[單項(xiàng)選擇題]*數(shù)組重點(diǎn)字(正確答案)元素件結(jié)點(diǎn)2.有22個(gè)待排記錄，使用直接插入排序需要（）趟能達(dá)成所有排序.[單項(xiàng)選擇題]*21(正確答案)2220都不對(duì)以下選項(xiàng)中對(duì)于穩(wěn)固排序說(shuō)法正確的選項(xiàng)是（）.[單項(xiàng)選擇題]*A.穩(wěn)固排序是指對(duì)于重點(diǎn)字相等的記錄，排序前后相對(duì)地點(diǎn)不變(正確答案)穩(wěn)固排序是指對(duì)于重點(diǎn)字相等的記錄，排序前后相對(duì)地點(diǎn)能夠變化穩(wěn)固排序是指排序是指將記錄變?yōu)闊o(wú)序的無(wú)正確答案希爾排序與直接插入排序同樣之處是（）.[單項(xiàng)選擇題]*它們都是穩(wěn)固排序它們的時(shí)間復(fù)雜度是同樣的它們都是插入排序大類里的(正確答案)它們都是減小增量排序5.在直接插入排序的算法中，要求被排序的數(shù)據(jù)（）儲(chǔ)存.[單項(xiàng)選擇題]*一定鏈表一定次序(正確答案)次序或鏈表能夠隨意用直接插入排序法對(duì)下邊的四個(gè)序列進(jìn)行由小到大的排序，元素比較次數(shù)最少的是（）.[單項(xiàng)選擇題]*94，32，40，90，80，46，21，6921，32，46，40，80，69，90，94(正確答案)32，40，21，46，69，94，90，8090，69，80，46，21，32，94，40內(nèi)排序是指在排序的整個(gè)過(guò)程中，所有數(shù)據(jù)都在計(jì)算機(jī)的（）中達(dá)成的排序.[單項(xiàng)選擇題]*內(nèi)存(正確答案)外存內(nèi)存和外存寄存器數(shù)據(jù)結(jié)構(gòu)與算法里，直接插入排序的穩(wěn)固性（）.[單項(xiàng)選擇題]*是不穩(wěn)固排序是穩(wěn)固排序(正確答案)有時(shí)是穩(wěn)固的，有時(shí)不穩(wěn)固以上說(shuō)法都不對(duì)二、多項(xiàng)選擇題希爾排序?qū)儆冢ǎ?*穩(wěn)固排序不穩(wěn)固排序(正確答案)選擇排序插入排序(正確答案)排序分為：（）、選擇排序、（）、合并排序四大類排序（）.*互換排序(正確答案)堆排序希爾排序插入排序(正確答案)以部下于插入排序類的排序有（）.*冒泡排序直接插入排序(正確答案)堆排序希爾排序(正確答案)算法中，假如依據(jù)待排記錄能否所有在內(nèi)存中，排序可分為（）.*內(nèi)排序(正確答案)外排序(正確答案)合并排序互換排序依據(jù)排序中擁有同樣重點(diǎn)字的記錄在排序前后的相對(duì)地點(diǎn)能否發(fā)生改變，排序分為（）.*內(nèi)排序外排序穩(wěn)固排序(正確答案)不穩(wěn)固排序(正確答案)三、判斷題直接插入排序，在排序里屬于穩(wěn)固排序。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)在排序算法中，希爾排序算法是不穩(wěn)固排序。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)16.大部分排序算法都有兩個(gè)基本的操作：比較和挪動(dòng)。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)排序分類中，只有內(nèi)排序，沒(méi)有外排序。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)18.假如某種排序算法不穩(wěn)固，則該排序方法就沒(méi)有適用價(jià)值。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)算法中，實(shí)現(xiàn)直接插入排序能夠使用循環(huán)語(yǔ)句。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)外排序是指在排序過(guò)程中，數(shù)據(jù)的主要部分寄存在計(jì)算機(jī)的內(nèi)存中。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)一、單項(xiàng)選擇題1.數(shù)據(jù)結(jié)構(gòu)與算法里，編寫迅速排序算法能夠用（）方式實(shí)現(xiàn).[單項(xiàng)選擇題]*插入選擇遞歸(正確答案)都不對(duì)迅速排序在（）狀況下，不利于發(fā)揮其優(yōu)點(diǎn).[單項(xiàng)選擇題]*完整亂序基本有序(正確答案)凌亂無(wú)章都不對(duì)迅速排序在（）狀況下，最易發(fā)揮其優(yōu)點(diǎn).[單項(xiàng)選擇題]*待排序的數(shù)據(jù)中含有多個(gè)同樣的重點(diǎn)字待排序的數(shù)據(jù)已基本有序待排序的數(shù)據(jù)完整無(wú)序(正確答案)待排序的數(shù)據(jù)中最大值與最小值相差懸殊一趟（）最后要返回中軸所在的地點(diǎn)，而后將小的挪動(dòng)到它的左側(cè)，將大的挪動(dòng)到它的右側(cè).[單項(xiàng)選擇題]*迅速排序(正確答案)直接插入排序冒泡排序都不對(duì)5.從排序的穩(wěn)固性來(lái)看，迅速排序是（）.[單項(xiàng)選擇題]*穩(wěn)固排序不穩(wěn)固排序(正確答案)不確立都不對(duì)迅速排序的方法是（）的排序方法.[單項(xiàng)選擇題]*穩(wěn)固不穩(wěn)固(正確答案)外面選擇7.冒泡排序的方法對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，第一趟排序共需要比較（）次.[單項(xiàng)選擇題]*12n-1(正確答案)n8.對(duì)ｎ個(gè)不一樣的排序碼進(jìn)行冒泡（遞加）排序，在以下（）狀況比較的次數(shù)最多（）.[單項(xiàng)選擇題]*從小到大擺列好的從大到小擺列好的(正確答案)元素?zé)o序元素基本有序一個(gè)數(shù)據(jù)序列的重點(diǎn)字為：（46，79，56，38，40，84），采納迅速排序，并以第一個(gè)數(shù)為基準(zhǔn)獲得第一次區(qū)分的結(jié)果為：（）。[單項(xiàng)選擇題]*38，40，46，56，79，84）38，40，46，79，56，84）40，38，46，56，79，84）(正確答案)40，38，46，79，56，84）迅速排序?qū)儆诨Q排序，它的時(shí)間復(fù)雜度是（）.[單項(xiàng)選擇題]*O（n*n）O（nlog2n）(正確答案)O（1）都不對(duì)二、多項(xiàng)選擇題數(shù)據(jù)結(jié)構(gòu)與算法中，排序能夠分為四大類，主要包含（）.*互換排序(正確答案)插入排序(正確答案)選擇排序(正確答案)合并排序(正確答案)以部下于互換排序類的排序有（）.*冒泡排序(正確答案)直接插入排序迅速排序(正確答案)希爾排序以下算法的均勻時(shí)間復(fù)雜度為O（n*n）的有（）.*冒泡排序(正確答案)直接插入排序(正確答案)迅速排序希爾排序以下算法屬于不穩(wěn)固排序的有（）.*冒泡排序直接插入排序迅速排序(正確答案)希爾排序(正確答案)已知數(shù)據(jù)序列{17，18，60，40，7，32，73，65，85}采納冒泡排序法對(duì)該序列作升序排序時(shí)第一趟的結(jié)果不是（）.*正確答案)正確答案)正確答案)三、判斷題以穩(wěn)固性來(lái)區(qū)分，冒泡排序是不穩(wěn)固的排序。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)17.對(duì)n個(gè)記錄的進(jìn)行迅速排序，所需要的均勻時(shí)間是O(nlog2n)（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)當(dāng)待排序的元素個(gè)數(shù)好多時(shí)，為了互換元素的地點(diǎn)要占用許多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要要素。（）.[單項(xiàng)選擇題]*A.對(duì)(正確答案)錯(cuò)19.迅速排序在任何狀況下都比其他排序方法速度快。（）.[單項(xiàng)選擇題]*對(duì)錯(cuò)(正確答案)20.對(duì)迅速排序來(lái)說(shuō)，初始序列為正序或反序都是最壞狀況。（）.[單項(xiàng)選擇題]*對(duì)(正確答案)錯(cuò)一、單項(xiàng)選擇題1.對(duì)于200個(gè)記錄，進(jìn)行簡(jiǎn)單項(xiàng)選擇擇排序，每趟最多進(jìn)行（）次互換.[單項(xiàng)選擇題]*1(正確答案)2200199下述幾種排序方法中，均勻時(shí)間復(fù)雜度最小的是（）.[單項(xiàng)選擇題]*希爾排序(正確答案)選擇排序插入排序冒泡排序以下排序方法中，重點(diǎn)字比較的次數(shù)與記錄的初始擺列序次沒(méi)關(guān)的是（）.[單項(xiàng)選擇題]*希爾排序選擇排序(正確答案)插入排序冒泡排序排序方法中，從無(wú)序序列中選擇重點(diǎn)字最小的記錄，將其與無(wú)序區(qū)（初始為空）的第一個(gè)記錄互換的排序方法，稱為（）.[單項(xiàng)選擇題]*合并排序插入排序選擇確立(正確答案)希爾排序下述幾種排序方法中，要求內(nèi)存量最大的是：（）.[單項(xiàng)選擇題]*合并排序(正確答案)插入排序選擇確立迅速排序6.10個(gè)記錄進(jìn)行簡(jiǎn)單項(xiàng)選擇擇排序，需要（）趟排序。[單項(xiàng)選擇題]*9(正確答案)81011一組記錄的排序碼為(25，48，16，35，79，82，23，40)，此中含有4個(gè)長(zhǎng)度為2的有序表，按合并排序的方法對(duì)該序列進(jìn)行一趟合并后的結(jié)果為：（）*

.[單項(xiàng)選擇題]正確答案)8.

對(duì)于

n個(gè)記錄的會(huì)合進(jìn)行合并排序，所需要的均勻時(shí)間復(fù)雜度為：（）

.[單項(xiàng)選擇題]*A.O（n）B.O（log2n）C.O（nlog2n）(正確答案D.O（n*n）

)二、多項(xiàng)選擇題簡(jiǎn)單項(xiàng)選擇擇排序的均勻時(shí)間復(fù)雜度不是（）.*O(n)(正確答案)O(