《數(shù)據(jù)結構與算法》三

1、數(shù)據(jù)結構與算法三您的姓名：填空題*一、單選題1.散列表的地址區(qū)間為0-17，散列函數(shù)為H（K尸K mod 17。采用線性探測法處理沖 突，并將關鍵字序列43, 42, 89, 55, 25, 35, 76依次存儲到散列表中。則元素 76存放在散列表中的地址是（ ）.單選題*A. 9B. 11（正確答案）C. 10D. 82.將5個元素散列到200000個單元的哈希表中，則（）產(chǎn)生沖突。單選題*A.仍可能會（正確答案）B. 一定不會C. 一定會D.以上答案均不對3. 一組長度為11的整型關鍵字為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 .對包含n個元素的散列表進行查找，時間度雜度為（）.單選題*A. O（n*n）B. O（log2n）C. O（n）D.不直接依賴于n（正確答案）5 .沖突指的是（）.單選題*A.兩個元素具有相同序號B.兩個元素的鍵值不同C.不同鍵值對應相同的存儲地址（正確答案）D.兩個元素的鍵值相同6 .在哈希表里，裝填因子的計算公式為（）.單選題*A.填入記錄數(shù)/哈希表的長度（正確答案）B. 1-（表中填入的記錄數(shù)/哈希表的總長度）C.哈希表未填空白處/哈希表的長度D.以上都不正確7.對于線

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

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

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

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

7、k+1） /2次（正確答案）3. 一個有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100,當二分 查找值為82的結點時，（）次比較后查找成功.單選題*A. 2B. 3C. 4（正確答案）D. 54 .二分查找有序表4, 6, 10, 12, 20, 30, 50, 70, 88, 100,若查找表中元素58,則它將依次與表中（）比較大小，查找結果是失敗.單選題*A. 30, 88, 70, 50B. 20, 70, 30, 50（正確答案）C. 20, 50D. 30, 88, 505 .設哈希表長m=14,哈希函數(shù)H （key） =ke

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

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

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

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

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

13、是（）.單選題*A.它們都是穩(wěn)定排序B.它們的時間復雜度是一樣的C.它們都是插入排序大類里的（正確答案）D.它們都是縮小增量排序5 .在直接插入排序的算法中，要求被排序的數(shù)據(jù)（）存儲.單選題*A.必須鏈表B.必須順序（正確答案）C.順序或鏈表D.可以任意6 .用直接插入排序法對下面的四個序列進行由小到大的排序，元素比較次數(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 .內排序是指在排序的整個過程

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

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

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

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

18、B. 2C. n-1（正確答案）D. n8.對n個不同的排序碼進行冒泡（遞增）排序，在下列（）情況比較的次數(shù)最多（）.單選題*A.從小到大排列好的8 .從大到小排列好的（正確答案）C.元素無序D.元素基本有序9 . 一個數(shù)據(jù)序列的關鍵字為：（46, 79, 56, 38, 40, 84）,采用快速排序，并單選題*以第一個數(shù)為基準得到第一次劃分的結果為：（）(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 .快速排序屬于交換排序，它的時間

19、復雜度是（）.單選題A. O （n*n）B. O （nlog2n）（正確答案）C. O （1）D.都不對二、多選題11 .數(shù)據(jù)結構與算法中，排序可以分為四大類，主要包含（）,A.交換排序（正確答案）B.插入排序（正確答案）C.選擇排序（正確答案）D.歸并排序（正確答案）12 .以下屬于交換排序類的排序有（）.*A.冒泡排序（正確答案）B.直接插入排序C.快速排序（正確答案）D.希爾排序13 .以下算法的平均時間復雜度為 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采用冒泡排序法對該序列 作升序排序時第一趟的結果不是（）.*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.對B.錯（正確答案）17.對n個記錄的進行快速排序，所需要的平均時間是O（nlo

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

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

23、（25, 48, 16, 35, 79, 82, 23, 40）,其中含有4個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為：（）.單選題*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 .對于n個記錄的集合進行歸并排序，所需要的平均時間復雜度為：（）.單選題*A. O （n）B. O （log2n）C. O （nlog2n）（正確答案）D. O （n*n）二、多選題9 .簡單選擇排序的平均時間復雜度不是（）.*A. O（n）（正確答案）B. O（n*n）C. O（nlog