數(shù)據(jù)結(jié)構(gòu)習(xí)題5概覽

1、第 8 章 查找8.1 選擇題1A）順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。散列存儲B）順序存儲或鏈接存儲C）壓縮存儲D）索引存儲2A)下面哪些操作不屬于靜態(tài)查找表（查詢某個特定元素是否在表中）B）檢索某個特定元素的屬性C)插入一個數(shù)據(jù)元素D ）建立一個查找表3下面描述不正確的是（A)B)C)D)順序查找對表中元素存放位置無任何要求，當(dāng) n 較大時，效率低。 靜態(tài)查找表中關(guān)鍵字有序時，可用二分查找。 分塊查找也是一種靜態(tài)查找表。經(jīng)常進行插入和刪除操作時可以采用二分查找。4A)散列查找時，解決沖突的方法有（除留余數(shù)法B）數(shù)字分析法）C ）直接定址法D）鏈地址法5若表中的記錄順序存放在一個一維數(shù)組

2、中，A)O(1)B) O(log 2n)在等概率情況下順序查找的平均查找長度為（2D） O（n2）C) O(n)對長度為 概率為 3/8 ，64 的順序表進行查找，若第一個元素的概率為1/8，第二個元素的概率為1/4 ，第三個元素的第四個元素的概率為 1/4，則查找任一個元素的平均查找長度為（）A)11/8B) 7/4C) 9/4D) 11/47A)C)所包含的數(shù)據(jù)元素的類型不一樣D ）存儲實現(xiàn)不一樣靜態(tài)查找表與動態(tài)查找表二者的根本差別在于（）它們的邏輯結(jié)構(gòu)不一樣B ）施加在其上的操作不同8若查找表中的記錄按關(guān)鍵字的大小順序存放在一個一維數(shù)組中，在等概率情況下二分法查找的平均檢索 長度是（ ）

3、A ) O(n)B ) O(log 2n)C ) O(nlog 2n)2D) O(log 2n)2)9對有 14 個數(shù)據(jù)元素的有序表 定值，此時元素比較順序依次為（R14 （假設(shè)下標(biāo)從 1）。開始）進行二分查找，搜索到 R4 的關(guān)鍵碼等于給A) R1 ，R2 ， R3 ，R4C) R7 ，R3 ，R5，R4B)D)R1 ，R13 ，R2 ， R3R7，R4 ，R2 ，R3）次。10 設(shè)有一個長度為 100 的已排好序的表，用二分查找進行查找，若查找不成功，至少比較（C) 7 D) 6中，用二分法查找關(guān)鍵碼 12 需做（）次關(guān)鍵碼A) 2 B) 3C)4D)512 從具有 n 個結(jié)點的二叉排序樹

4、中查找一個元素時，A )O (n)B） O （1）C ) O (log 2 n)在最壞情況下的時間復(fù)雜度為2D） O （n 2 ）13分塊查找時確定塊的查找可以用順序查找，也可以用（A）靜態(tài)查找，順序查找B ）二分查找，順序查找C）二分查找，二分查找D ）散列查找，順序查找），而在塊中只能是（14采用分塊查找時，若線性表中共有結(jié)點所在的塊時，每塊應(yīng)分（625 個元素，查找每個元素的概率相同，假設(shè)采用順序查找來確定 ）個結(jié)點最佳。A)10B)25C)6D)62515 采用分塊查找法（塊長為s，度為（以二分查找確定塊）查找長度為 n 的線性表時，每個元素的平均查找長A)s+nB)log2ns/2C

5、) log 2 (n/s+1)+s/2D)(n+s)/216 對一棵二叉排序樹根結(jié)點而言，左子樹中所有結(jié)點與右子樹中所有結(jié)點的關(guān)鍵字大小關(guān)系是（等于D）不小于A）小于B）大于C)17若二叉排序樹中關(guān)鍵字互不相同，最小元和最大元一定是葉子 B ）則下面命題中不正確的是（A)C)最小元必?zé)o左孩子D)最大元必?zé)o右孩子新結(jié)點總是作為葉結(jié)點插入二叉排序樹設(shè)二叉排序樹中關(guān)鍵字由 1至1000 的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為 363的結(jié)點，下述關(guān)鍵字序列18不可能是在二叉排序樹上查找到的序列A)2,252,401,398,330, 344,397,363B)924, 220, 911, 244, 898, 2

6、58, 362, 363C)2, 399, 387, 219, 266, 382, 381, 278, 363D)925, 202, 911, 240, 912, 245, 36319在初始為空的散列表中依次插入關(guān)鍵字序列（MON,TUE,WED,THU,FRI,SAT,SUN）, 散列函數(shù)為MOD 7,其中，i為關(guān)鍵字k的第一個字母在英文字母表中的序號，地址值域為0:6，采用線性再散列法處理沖突。插入后的散列表應(yīng)該如（）所示。A)THUTUEWEDFRISUNSATMONB)TUETHUWEDFRISUNSATMONC)TUETHUWEDFRISATSUNMOND)TUETHU WEDSUN

7、SATFRI MONH(k)=i11請指出在順序表 2,5,7,10,14,15,18,23,35,41,52 比較。20 若根據(jù)查找表建立長度為m的散列表，采用線性探測法處理沖突，假定對一個元素第一次計算的散列地址為d，則下一次的散列地址為()。B)(d+1)%mC)(d+1)/m D)d+16假設(shè)在有序線性表A1.2O上進行二分查找，則比較一次查找成功的結(jié)點數(shù)為個，比21 若根據(jù)查找表建立長度為m的散列表，采用二次探測法處理沖突，假定對一個元素第一次計算的散列地址為d，則第四次計算的散列地址為()。A )(d+1)%mB)(d-1)%mC)(d+4)%mD)(d-4)%m22 下面有關(guān)散列

8、查找的說法中正確的是()直接定址法所得地址集合和關(guān)鍵字集合的大小不一定相同。除留余數(shù)法構(gòu)造的哈希函數(shù)H(key)=key MOD p ，其中構(gòu)造哈希函數(shù)時不需要考慮記錄的查找頻率。P必須選擇素數(shù)。數(shù)字分析法適用于對哈希表中出現(xiàn)的關(guān)鍵字事先知道的情況。23 .下面有關(guān)散列沖突解決的說法中不正確的是(處理沖突即當(dāng)某關(guān)鍵字得到的哈希地址已經(jīng)存在時，為其尋找另一個空地址。使用鏈地址法在鏈表中插入元素的位置隨意，即可以是表頭表尾，也可以在中間。二次探測能夠保證只要哈希表未填滿，總能找到一個不沖突的地址。線性探測能夠保證只要哈希表未填滿，總能找到一個不沖突的地址。24 .設(shè)哈希表長m=14，哈希函數(shù) H(

9、key)=key%11。表中已有 4個結(jié)點：addr(15)=4 ，addr(38)=5 ，addr(61)=6，addr(84)=7其余地址為空，如用二次探測處理沖突，關(guān)鍵字為49的結(jié)點的地址是(A) 8 B) 3 C) 58.2 填空題1 .在散列函數(shù)H(key)=key% p中,P應(yīng)取2 采用分塊查找法(塊長為以順序查找確定塊)查找長度為n的線性表時的平均查找長度為3 .己知一個有序表為(12,18,20,25,29,32,40,62,83,90,95,98)，當(dāng)二分查找值為29和90的元素時，分別需要次和次比較才能查找成功；若采用順序查找時，分別需要.次和.次比較才能查找成功。4從一棵

10、二叉排序樹中查找一個元素時，若元素的值等于根結(jié)點的值，則表明，若元素的值小于根結(jié)點的值，則繼續(xù)向查找，若元素的值大于根結(jié)點的值，則繼續(xù)向查找。5二分查找的存儲結(jié)構(gòu)僅限于，且是較二次查找成功的結(jié)點數(shù)為查找成功的結(jié)點數(shù)為，比較三次查找成功的結(jié)點數(shù)為，比較五次查找成功的結(jié)點數(shù)為_，比較四次，平均查找長度為7 在對有 20個元素的遞增有序表作二分查找時，查找長度為。(設(shè)下標(biāo)從1開始)5的元素的下標(biāo)從小到大依次為8 對于線性表(70,34,55,23,65,41,20,100 )進行散列存儲時，若選用 地址為1的元素有 _ 個，散列地址為 7的元素有_H(K)=K%9作為散列函數(shù)，則散列 個。9 .索引

11、順序表上的查找分兩個階段:10 分塊查找中，要得到最好的平均查找長度，應(yīng)對256個元素的線性查找表分成塊的最佳長度是 。若每塊的長度為8，則等概率下平均查找長度為塊，每11 .是一棵二叉樹，如果不為空，則它必須滿足下面的條件: 若左子樹不空，則左子樹上所有結(jié)點的值均小于根的值。若右子樹不空，則右子樹上所有結(jié)點的值均大于根的值。 其左右子樹均為二叉排序樹。13 假定有 k個關(guān)鍵字互為同義詞，若用線性探測法把這些同義詞存入散列表中，至少要進行 次探測。8.3 應(yīng)用題1 .設(shè)有序表為(a, b, c, d, e, f, g, h, i, j, k, p, q)，請分別畫出對給定值 a, g和n進行折

12、半查找的過程。(1 )假如刪除關(guān)鍵字28，畫出新二叉樹。(2)若查找56，需和哪些關(guān)鍵字比較。3.已知散列表的地址區(qū)間為011,散列函數(shù)為 H（k）=k % 11 ,采用線性探測法處理沖突，將關(guān)鍵字序列20,30,70,15,8,12,18,63,19 依次存儲到散列表中，試構(gòu)造出該散列表，并求出在等概率情況下的平均查找 長度。4設(shè)散列函數(shù)為 H（k）=k % 11 ，采用拉鏈法處理沖突，將上例中關(guān)鍵字序列依次存儲到散列表中，并求出 在等概率情況下的平均查找長度。5假定一個待散列存儲的線性表為 （32,75,29,63,48,94,25,46,18,70） ，散列地址空間為 HT13 ，若采用

13、除 留余數(shù)法構(gòu)造散列函數(shù)和線性探測法處理沖突，試求出每一元素的初始散列地址和最終散列地址，畫出最 后得到的散列表，求出平均查找長度。第 9 章 排序9.1 選擇題1.從末排序的序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在排序序列的合 適位置，該排序方法稱為（）排序法。A）插入B）選擇 C）希爾D ）二路歸并2A）下面各種排序方法中，最好情況下時間復(fù)雜度為0（n）的是（）快速排序 B）直接插入排序C）堆排序 D ）歸并排序3用某種排序方法對線性表（ 25,84,21,47,15,27,68,35,20 ）進行排序時，無序序列的變化情況如下：25 84 21 47 15 2

14、7 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84 則所采用的排序方法是（）A）選擇排序 B）希爾排序C）歸并排序D）快速排序4A)下面給出的四種排序法中， （ 插入B ）冒泡）排序是不穩(wěn)定排序法。C）二路歸并 D ）堆5A)B)快速排序方法在（ ）情況下最不利于發(fā)揮其長處。要排序的數(shù)據(jù)量太大 要排序的數(shù)據(jù)中含有多個相同值C)要排序的數(shù)據(jù)已基本有序D)要排序的數(shù)據(jù)個數(shù)為奇數(shù)6一組記錄的關(guān)鍵碼為（ 46,79,56,38,40,84 ），則利用快速排序的方法，以第一個記錄

15、為基準(zhǔn)得到的一次 劃分結(jié)果為（ ）A) 38,40,46,56,79,84B ) 40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,797對記錄的關(guān)鍵碼 50，26，38，80，70，90， 8，30，40，20進行排序，各趟排序結(jié)束時的結(jié)果為： 50,26,38,80,70,90 ,8,30,40,20 50,8,30,40,20,90,26,38,80,70 26,8,30,40,20,80,50,38,90,70 8,20,26,30,38,40,50,70,80,90其使用的排序方法是( )A）快速排序B）基數(shù)排序C ）希爾排序D

16、）歸并排序8A)在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序方法是（）直接插入排序B）冒泡排序C）簡單選擇排序D ）歸并排序9 置上。在下列算法中， （ ）算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位A）堆排序B ）冒泡排序C）插入排序D ）快速排序10設(shè)有 5000 個無序的元素， 用（ ）方法最好希望用最快速度挑選出其中前 10 個最大的元素，在以下的排序方法中，采A）快速排序B）堆排序C）基數(shù)排序11對給出的一組關(guān)鍵字 14，5，19 ，20 ，11，19。若按關(guān)鍵字非遞減排序，第一趟排序結(jié)果為19，20，11，19 ，問采用的排序算法是（）A）簡單選擇

17、排序B ）快速排序C）希爾排序D）二路歸并排序14，5，12以下序列不是堆的是（A)100,85,98,77,80,60,82,40,20,10,66B)100,98,85,82,80,77,66,60,40,20,10C)10,20,40,60,66,77,80,82,85,98,100D)100,85,40,77,80,60,66,98,82,10,2013下面排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排列無關(guān)的是（A）希爾排序B）冒泡排序C）直接插入排序D ）直接選擇排序14一組記錄的關(guān)鍵字為 45 ，80，55，40，42，85，則利用堆排序的方法建立的初始堆為（A)80,45,50,40

18、,42,85B)85,80,55,40,42, 45C)85,80,55,45,42,40D)85,55,80,42,45,4015一組記錄的關(guān)鍵字為 25 ，50，15，35，80， 表，用歸并排序方法對該序列進行一趟歸并后的結(jié)果為85，20，40，36，70，其中含有 5 個長度為）2 的有序A ) 15,25,35,50,20,40,80,85,36,70B) 15,25,35,50,80,20,85,40,70,36C) 15,25,50,35,80,85,20,36,40,70D) 15,25,35,50,80,20,36,40,70,8516 . n個元素進行冒泡排序的過程中，最好

19、情況下的時間復(fù)雜度為(A) O(1) B) O(log 2n)C) O(n2)D) O(n)17. n個元素進行快速排序的過程中，第一次劃分最多需要移動( 臨時變量的那一次)。)次元素(包括開始將基準(zhǔn)元素移到A) n/2B) n-1 C) n D) n+l18 下述幾種排序方法中，要求內(nèi)存量最大的是(A )插入排序 B)選擇排序 C)快速排序)D)歸并排序19 .下面排序方法中，時間復(fù)雜度不是A)直接插入排序B)二路歸并排序2O(n )的是(C )冒泡排序)D)直接選擇排序20 對下列4個序列用快速排序方法進行排序，以序列的第1個元素為基準(zhǔn)進行劃分。在第1趟劃分過程中，元素移動次數(shù)最多的是序列

20、(70,75,82,90, 23,16,10,6870,75,68,23,10,16,90,8282,75,70,16,10,90,68,2323,10,16,70,82,75,68,909.2填空題1.當(dāng)數(shù)據(jù)量特別大需借助外部存儲器對數(shù)據(jù)進行排序，則這種排序稱為2 在堆排序、快速排序和歸并排序中，若從節(jié)省存儲空間考慮，則應(yīng)首先選取 次選取方法；若只從排序結(jié)果的穩(wěn)定性考慮，情況下排序的速度來考慮，則選擇 方法；慮，則應(yīng)選取方法。方法，其則應(yīng)先擇 方法；若只從平均若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考3 .對n個元素的序列進行冒泡排序，最少的比較次數(shù)是 ，在情況下比較次數(shù)最多,其比較次數(shù)為，此

21、時元素的排列情況為(4)。4.希爾排序是把記錄按下標(biāo)的一定增量分組，對每組記錄進行直接插入排序，隨著增量 所分成的組包含的記錄越來越多，當(dāng)增量的值為 時，整個數(shù)組合為一組。5 .直接插入排序需借助的存儲單元個數(shù)(空間復(fù)雜度)為 算法時間復(fù)雜度為 ，最壞情況下該算法的時間復(fù)雜度為，最好情況下直接插入排序的6.對n個數(shù)據(jù)進行簡單選擇排序，所需進行的關(guān)鍵字間的比較次數(shù)為，時間復(fù)雜度為7.對于關(guān)鍵字序列(12, 13, 11, 18, 60, 15, 7, 20，25, 100)，用篩選法建堆，必須從鍵值為 的關(guān)鍵字開始。8 .對一組記錄(54 , 38 , 96 , 23 , 15 , 72 , 60 , 45 , 83)進行直接插入排序時，當(dāng)把第7個記錄60插入到已排序的有序表時，為尋找其插入位置需比較 次。9 若對順序存儲在 AlA9的記錄(76 , 38 , 62 , 53 , 80 , 74 , 83 , 65 , 85)進行堆排序，已知除第一個元素76夕卜，以其余元素為根的結(jié)點都已是堆，則對第一個元素進行篩