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

1、數(shù)據(jù)結(jié)構(gòu)與算法三您的姓名：填空題*一、單選題1.散列表的地址區(qū)間為0-17，散列函數(shù)為H（K尸K mod 17。采用線性探測(cè)法處理沖 突，并將關(guān)鍵字序列43, 42, 89, 55, 25, 35, 76依次存儲(chǔ)到散列表中。則元素 76存放在散列表中的地址是（ ）.單選題*A. 9B. 11（正確答案）C. 10D. 82.將5個(gè)元素散列到200000個(gè)單元的哈希表中，則（）產(chǎn)生沖突。單選題*A.仍可能會(huì)（正確答案）B. 一定不會(huì)C. 一定會(huì)D.以上答案均不對(duì)3. 一組長度為11的整型關(guān)鍵字為22,32,23,45,54,56,65,76,78,89,100,通過哈希函數(shù)H （key） =ke

2、y MOD 11映射到長度為11的哈希表中，裝填因子為（）.單選題 *A. 1（正確答案）B. 2C. 3D. 44 .對(duì)包含n個(gè)元素的散列表進(jìn)行查找，時(shí)間度雜度為（）.單選題*A. O（n*n）B. O（log2n）C. O（n）D.不直接依賴于n（正確答案）5 .沖突指的是（）.單選題*A.兩個(gè)元素具有相同序號(hào)B.兩個(gè)元素的鍵值不同C.不同鍵值對(duì)應(yīng)相同的存儲(chǔ)地址（正確答案）D.兩個(gè)元素的鍵值相同6 .在哈希表里，裝填因子的計(jì)算公式為（）.單選題*A.填入記錄數(shù)/哈希表的長度（正確答案）B. 1-（表中填入的記錄數(shù)/哈希表的總長度）C.哈希表未填空白處/哈希表的長度D.以上都不正確7.對(duì)于線

3、性表（7,34,55,25,64,46,20,10進(jìn)行散列存儲(chǔ)時(shí)，若使用 H （K） =K%9作 為散列函數(shù)，則散列地址為1的元素有（）個(gè)。單選題*A. 1B. 2C. 3D. 4（正確答案）8.哈希表長為16,散列函數(shù)H（key尸key%11,表中已有的關(guān)鍵字為26, 49, 72, 95共4個(gè)，將60的結(jié)點(diǎn)裝入表中，用二次探測(cè)再散列法解決沖突，位置是（）o單選題*A. 8B. 9（正確答案）C. 5D. 3二、多選題9.下面屬于構(gòu)造哈希函數(shù)的方法是（）.*A.直接定址法（正確答案）B.數(shù)字分析法（正確答案）C.除留余數(shù)法（正確答案）D.平方取中法（正確答案）10.使用冉哈希法的特點(diǎn)有（）.

4、*A.在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)的地址，直到?jīng)_突不再發(fā)生（正確答案）B.這種方法不易產(chǎn)生 聚集”（正確答案）C.該方法增加了計(jì)算的時(shí)間（正確答案）D.該方法呈線性探測(cè)再散列11.關(guān)于哈希表的裝填因子，以正確的有（）.*A.裝填因子的值越小，發(fā)生沖突的概率越小（正確答案）B.裝填因子越大，表中填入的記錄越多，在填入的時(shí)候發(fā)生沖突的可能性就越大，在進(jìn)行查找時(shí)候，查找的次數(shù)也就越多。（正確答案）C.裝填因子二表中填入的記錄數(shù)/哈希表的總長度（正確答案）D.裝填因子的值越小，就可以避免沖突的發(fā)生12.在哈希表進(jìn)行查找時(shí)，以下不是解決沖突的方法包括（）A.數(shù)字分析法（正確答案）B.除留余數(shù)

5、法（正確答案）C.直接地址法（正確答案）D.線性探測(cè)再散列法13.屬于處理哈希沖突的主要方法是（）.*A.開放定址法（正確答案）B.再哈希法（正確答案）C.除留余數(shù)法D.直接定址法三、判斷題14.哈希表的一個(gè)重要參數(shù)一一裝填因子，它反映哈希表的裝滿程度。（）.單選 題*A.對(duì)（正確答案）B.錯(cuò)15.哈希函數(shù)是根據(jù)關(guān)鍵字確定存儲(chǔ)位置的函數(shù)。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)16.哈希沖突是不同關(guān)鍵字由哈希函數(shù)得到相同存儲(chǔ)位置的現(xiàn)象。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)17.哈希法的查找效率主要取決于哈希表構(gòu)造時(shí)選取的哈希函數(shù)和處理沖突的方法。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)18.哈希

6、表是一種將關(guān)鍵字轉(zhuǎn)換為存儲(chǔ)地址的存儲(chǔ)方法。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)19.選擇好的哈希函數(shù)就可以避免沖突的發(fā)生。（）.單選題*A.對(duì)B.錯(cuò)（正確答案）20.散列存儲(chǔ)法的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)一、單選題1 .下列（）不是利用查找表中數(shù)據(jù)元素的關(guān)系進(jìn)行查找的方法。.單選題*A.平衡二叉樹B.有序表的查找C.散列查找（正確答案）D.二叉排序樹的查找2 .數(shù)據(jù)結(jié)構(gòu)與算法中，假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測(cè)？ （）0單選題*A. k-1 次B. k次C. k+1 次D. k （

7、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í)，（）次比較后查找成功.單選題*A. 2B. 3C. 4（正確答案）D. 54 .二分查找有序表4, 6, 10, 12, 20, 30, 50, 70, 88, 100,若查找表中元素58,則它將依次與表中（）比較大小，查找結(jié)果是失敗.單選題*A. 30, 88, 70, 50B. 20, 70, 30, 50（正確答案）C. 20, 50D. 30, 88, 505 .設(shè)哈希表長m=14,哈希函數(shù)H （key） =ke

8、y% 11。表中已有4個(gè)結(jié)點(diǎn)： addr（15）=4, addr（38）=5, addr（61）=6, addr（84）=7,其余地址為空。如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是（）.單選題*A. 8B. 3C. 5D. 9（正確答案）6.有一個(gè)長度為12的有序表，按折半查找法對(duì)其進(jìn)行查找，在表內(nèi)各元素等概率 情況下查找成功所需的平均比較次數(shù)為（）.單選題*A. 35/12B. 37/12（正確答案）C. 39/12D. 43/127.理想情況下，在散列表中查找一個(gè)元素的時(shí)間復(fù)雜度為：（）.單選題*A. O（n）B. O（n*n）C. O（log2n）D. 0（1）（正確答案）

9、8 .在關(guān)鍵字序列（7, 10, 12, 18, 28, 36, 45, 92）中，用二分查找關(guān)鍵字 92, 要比較（）次才找到.單選題*234（正確答案）5二、多選題9 .裝填因子的計(jì)算方法不是（）.*A. 1-（表中未填入記錄的數(shù)目/哈希表的總長度）B.表中未填入記錄的數(shù)目/哈希表的總長度（正確答案）C.（表中未填入的記錄數(shù)-1）/哈希表的總長度（正確答案）D.表中填入的記錄數(shù)/哈希表的總長10.哈希表的查找效率取決于（）.*A.哈希函數(shù)（正確答案）B.處理沖突的方法（正確答案）C.哈希表的裝填因子（正確答案）D.無正確答案11 .設(shè)散列表（哈希表）中有 m個(gè)存儲(chǔ)單元，散列函數(shù)H（key尸

10、key % p,則p不要 選擇（）.*A.小于等于m的最大奇數(shù)（正確答案）B.小于等于m的最大素?cái)?shù)C.小于等于m的最大偶數(shù)（正確答案）D.小于等于m的最大合數(shù)（正確答案）12 .二叉排序樹的葉子結(jié)點(diǎn)個(gè)數(shù)為8個(gè)，則度為2的結(jié)點(diǎn)的數(shù)目不是（）.*A. 5（正確答案）B. 6（正確答案）C. 7D. 8（正確答案）13.下列選項(xiàng)中說法不正確的是（）.*A.二叉排序樹可以含有0個(gè)結(jié)點(diǎn)，這時(shí)它是一棵空二叉排序樹B.二叉排序樹可以含有0個(gè)結(jié)點(diǎn)，這時(shí)它是一棵滿二叉排序樹（正確答案）C.二叉排序樹可以含有0個(gè)結(jié)點(diǎn)，這時(shí)它是一棵完全二叉排序樹（正確答案）D.無正確答案（正確答案）三、判斷題14.折半查找法要求待

11、查表的關(guān)鍵字值必須有序。（）.單選題*A.對(duì)（正確答案）B.錯(cuò).單選題*15.對(duì)有序表而言采用折半查找總比采用順序查找法速度快。（）A.對(duì)B.錯(cuò)（正確答案）16.二叉排序樹是一種靜態(tài)查找表。（）.單選題*A.對(duì)B.錯(cuò)（正確答案）17.哈希表是按散列存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)18.在哈希函數(shù)H（key尸key % P中，P 一般應(yīng)取偶數(shù)。（）.單選題*A.對(duì)B.錯(cuò)（正確答案）19.對(duì)二叉排序樹進(jìn)行查找的方法是用待查的值與根結(jié)點(diǎn)的鍵值進(jìn)行比較，若比根 結(jié)點(diǎn)小，則繼續(xù)在右子樹中查找。（）.單選題*A.對(duì)B.錯(cuò)（正確答案） 20.對(duì)于長度為n的線性表，若采用折半查找

12、，則時(shí)間復(fù)雜度為： O （log2n）（）.單選題*A.對(duì)（正確答案）B.錯(cuò)一、單選題1.排序算法一般是根據(jù)（）的大小，重新安排各元素的順序.單選題*A.數(shù)組B.關(guān)鍵字（正確答案）C.元素件D.結(jié)點(diǎn)2 .有22個(gè)待排記錄，使用直接插入排序需要（）趟能完成全部排序.單選題*A. 21（正確答案）B. 22C. 20D.都不對(duì)3 .下列選項(xiàng)中關(guān)于穩(wěn)定排序說法正確的是（）.單選題*A.穩(wěn)定排序是指對(duì)于關(guān)鍵字相等的記錄，排序前后相對(duì)位置不變（正確答案）B.穩(wěn)定排序是指對(duì)于關(guān)鍵字相等的記錄，排序前后相對(duì)位置可以變化C.穩(wěn)定排序是指排序是指將記錄變成無序的D.無正確答案4 .希爾排序與直接插入排序相同之處

13、是（）.單選題*A.它們都是穩(wěn)定排序B.它們的時(shí)間復(fù)雜度是一樣的C.它們都是插入排序大類里的（正確答案）D.它們都是縮小增量排序5 .在直接插入排序的算法中，要求被排序的數(shù)據(jù)（）存儲(chǔ).單選題*A.必須鏈表B.必須順序（正確答案）C.順序或鏈表D.可以任意6 .用直接插入排序法對(duì)下面的四個(gè)序列進(jìn)行由小到大的排序，元素比較次數(shù)最少的 是（）.單選題*A. 94,32,40,90,80,46,21,69B. 21,32,46,40,80,69,90,94（正確答案）C. 32,40,21,46,69,94,90,80D. 90,69,80,46,21,32,94,407 .內(nèi)排序是指在排序的整個(gè)過程

14、中，全部數(shù)據(jù)都在計(jì)算機(jī)的（）中完成的排序選題*A.內(nèi)存（正確答案）8 .外存C.內(nèi)存和外存D.寄存器8.數(shù)據(jù)結(jié)構(gòu)與算法里，直接插入排序的穩(wěn)定性（）.單選題*A.是不穩(wěn)定排序8 .是穩(wěn)定排序（正確答案）C.有時(shí)是穩(wěn)定的，有時(shí)不穩(wěn)定D.以上說法都不對(duì)二、多選題9 .希爾排序?qū)儆冢ǎ?*A.穩(wěn)定排序B.不穩(wěn)定排序（正確答案）C.選擇排序D.插入排序（正確答案）10 .排序分為：（）、選擇排序、（）、歸并排序四大類排序（）.*A.交換排序（正確答案）B.堆排序C.希爾排序D.插入排序（正確答案）11 .以下屬于插入排序類的排序有（）.*A.冒泡排序B.直接插入排序（正確答案）C.堆排序D.希爾排序（正

15、確答案）12.算法中，如果按照待排記錄是否全部在內(nèi)存中，排序可分為（）.*A.內(nèi)排序（正確答案）B.外排序（正確答案）C.歸并排序D.交換排序13 .按照排序中具有相同關(guān)鍵字的記錄在排序前后的相對(duì)位置是否發(fā)生改變，排序 分為（）.*A.內(nèi)排序B.外排序C.穩(wěn)定排序（正確答案）D.不穩(wěn)定排序（正確答案）、判斷題.單選題*14 .直接插入排序，在排序里屬于穩(wěn)定排序。（）A.對(duì)（正確答案）B.錯(cuò)15 .在排序算法中，希爾排序算法是不穩(wěn)定排序。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)16.大多數(shù)排序算法都有兩個(gè)基本的操作：比較和移動(dòng)。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)17.排序分類中，只有內(nèi)排序，沒

16、有外排序。（）.單選題*A.對(duì)B.錯(cuò)（正確答案）18.如果某種排序算法不穩(wěn)定，則該排序方法就沒有實(shí)用價(jià)值。（）.單選題*A.對(duì)B.錯(cuò)（正確答案）19.算法中，實(shí)現(xiàn)直接插入排序可以使用循環(huán)語句。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)20.外排序是指在排序過程中，數(shù)據(jù)的主要部分存放在計(jì)算機(jī)的內(nèi)存中。（）.單選題*A.對(duì)B.錯(cuò)（正確答案）、單選題1 .數(shù)據(jù)結(jié)構(gòu)與算法里，編寫快速排序算法可以用（）方式實(shí)現(xiàn).單選題*A.插入B.選擇C.遞歸（正確答案）D.都不對(duì)2 .快速排序在（）情況下，不利于發(fā)揮其長處.單選題*A.完全亂序B.基本有序（正確答案）C.雜亂無章D.都不對(duì)3.快速排序在（）情況下，最易發(fā)

17、揮其長處.單選題*A.待排序的數(shù)據(jù)中含有多個(gè)相同的關(guān)鍵字B.待排序的數(shù)據(jù)已基本有序C.待排序的數(shù)據(jù)完全無序（正確答案）D.待排序的數(shù)據(jù)中最大值與最小值相差懸殊4 . 一趟（）最后要返回中軸所在的位置，然后將小的移動(dòng)到它的左邊，將大的移動(dòng) 到它的右邊.單選題*A.快速排序（正確答案）B.直接插入排序C.冒泡排序D.都不對(duì)5 .從排序的穩(wěn)定性來看，快速排序是（）.單選題*A.穩(wěn)定排序B.不穩(wěn)定排序（正確答案）C.不確定D.都不對(duì)6.快速排序的方法是（）的排序方法.單選題*A.穩(wěn)定B.不穩(wěn)定（正確答案）C.外部D.選擇7.冒泡排序的方法對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，第一趟排序共需要比較（）次.單選題*A. 1

18、B. 2C. n-1（正確答案）D. n8.對(duì)n個(gè)不同的排序碼進(jìn)行冒泡（遞增）排序，在下列（）情況比較的次數(shù)最多（）.單選題*A.從小到大排列好的8 .從大到小排列好的（正確答案）C.元素?zé)o序D.元素基本有序9 . 一個(gè)數(shù)據(jù)序列的關(guān)鍵字為：（46, 79, 56, 38, 40, 84）,采用快速排序，并單選題*以第一個(gè)數(shù)為基準(zhǔn)得到第一次劃分的結(jié)果為：（）(38, 40, 46, 56, 79, 84)（38, 40, 46, 79, 56, 84）（40, 38, 46, 56, 79, 84）（正確答案）（40, 38, 46, 79, 56, 84）10 .快速排序?qū)儆诮粨Q排序，它的時(shí)間

19、復(fù)雜度是（）.單選題A. O （n*n）B. O （nlog2n）（正確答案）C. O （1）D.都不對(duì)二、多選題11 .數(shù)據(jù)結(jié)構(gòu)與算法中，排序可以分為四大類，主要包含（）,A.交換排序（正確答案）B.插入排序（正確答案）C.選擇排序（正確答案）D.歸并排序（正確答案）12 .以下屬于交換排序類的排序有（）.*A.冒泡排序（正確答案）B.直接插入排序C.快速排序（正確答案）D.希爾排序13 .以下算法的平均時(shí)間復(fù)雜度為 O （n*n）的有（）.*A.冒泡排序（正確答案）B.直接插入排序（正確答案）C.快速排序D.希爾排序14 .以下算法屬于不穩(wěn)定排序的有（）.*A.冒泡排序B.直接插入排序C.

20、快速排序（正確答案）D.希爾排序（正確答案）15 .已知數(shù)據(jù)序列17, 18, 60, 40, 7, 32, 73, 65, 85采用冒泡排序法對(duì)該序列 作升序排序時(shí)第一趟的結(jié)果不是（）.*A. 17 18 40 7 32 60 65 73 85B. 17 18 40 7 73 32 60 65 85（正確答案）C. 17 40 18 7 32 60 65 73 85正確答案）D. 17 18 40 7 32 60 65 85 73正確答案）三、判斷題16.以穩(wěn)定性來劃分，冒泡排序是不穩(wěn)定的排序。（）.單選題*A.對(duì)B.錯(cuò)（正確答案）17.對(duì)n個(gè)記錄的進(jìn)行快速排序，所需要的平均時(shí)間是O（nlo

21、g2n）（）.單選題*A.對(duì)（正確答案）B.錯(cuò) 18.當(dāng)待排序的元素個(gè)數(shù)很多時(shí)，為了交換元素的位置要占用較多的時(shí)間，這是影 響時(shí)間復(fù)雜度的主要因素。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)19.快速排序在任何情況下都比其它排序方法速度快。（）.單選題*A.對(duì)B.錯(cuò)（正確答案）20.對(duì)快速排序來說，初始序列為正序或反序都是最壞情況。（）.單選題*A.對(duì)（正確答案）B.錯(cuò)一、單選題1 .對(duì)于200個(gè)記錄，進(jìn)行簡(jiǎn)單選擇排序，每趟最多進(jìn)行（）次交換.單選題*A. 1（正確答案）B. 2C. 200D. 1992 .下述幾種排序方法中，平均時(shí)間復(fù)雜度最小的是（）.單選題*A.希爾排序（正確答案）B.選擇排

22、序C.插入排序D.冒泡排序3 .下列排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是（）.單選題*A.希爾排序B.選擇排序（正確答案）C.插入排序D.冒泡排序4 .排序方法中，從無序序列中選擇關(guān)鍵字最小的記錄，將其與無序區(qū)（初始為空） 的第一個(gè)記錄交換的排序方法，稱為（）.單選題*A.歸并排序B.插入排序C.選擇確定（正確答案）D.希爾排序5 .下述幾種排序方法中，要求內(nèi)存量最大的是：（）.單選題*A.歸并排序（正確答案）B.插入排序C.選擇確定D.快速排序6. 10個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，需要（）趟排序。單選題*A. 9（正確答案）B. 8C. 10D. 117. 一組記錄的排序碼為

23、（25, 48, 16, 35, 79, 82, 23, 40）,其中含有4個(gè)長度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為：（）.單選題*A. 16 25 35 48 23 40 79 84正確答案）B. 16 25 35 48 79 82 23 40C. 16 25 48 35 79 82 23 40D. 16 25 35 48 79 23 82 408 .對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間復(fù)雜度為：（）.單選題*A. O （n）B. O （log2n）C. O （nlog2n）（正確答案）D. O （n*n）二、多選題9 .簡(jiǎn)單選擇排序的平均時(shí)間復(fù)雜度不是（）.*A. O（n）（正確答案）B. O（n*n）C. O（nlog