數(shù)據(jù)結(jié)構(gòu)書面作業(yè)練習(xí)題69(參考版)
2025-03-28 03:01本頁(yè)面
【正文】 （1）(100,86,48,73,35,39,42,57,66,21)。 綜合題1. 以關(guān)鍵字序列（503,087,512,061,908,170,897,275,653,426），為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時(shí)的關(guān)鍵字狀態(tài)：（1） 直接插入排序；（2） 希爾排序（增量d[1]=5）；（3） 快速排序；（4） 堆排序；（5） 歸并排序；2. 判別以下序列是否為堆（小頂堆或大頂堆）。3. 在堆排序和快速排序中，若原始記錄接近正序或反序，則選用_堆排序___，若原始記錄無(wú)序，則最好選用__快速__。A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個(gè)相同值C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) 填空題 （將正確的答案填在相應(yīng)的空中）1. 在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較__3次__。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序11. 下述幾種排序方法中，要求內(nèi)存量最大的是___D_。A. 希爾排序 B. 歸并排序 C. 插入排序 D. 選擇排序9. 用某種排序方法對(duì)線性表（ 25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，元素序列的變化情況如下：⑴ 25，84，21，47，15，27，68，35，20⑵ 20，15，21，25，47，27，68，35，84⑶ 15，20，21，25，35，27，47，68，84⑷ 15，20，21，25，27，35，47，68，84則所采用的排序方法是__D_。A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，35，48，79，23，36，40，72，827. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為__C__。A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84，C. 84，79，56，46，40，38 D. 84，56，79，40，46，385. 一組記錄的關(guān)鍵字為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為___C_。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是___A_。用開放定址法處理沖突，di=i（i=1，2，3，…）.試在010的散列地址空間中對(duì)關(guān)鍵字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。5. 對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為_ O（n）___；若采用二分法查找，則時(shí)間復(fù)雜度為__ O（log2n）__； 6. 在散列存儲(chǔ)中，裝填因子a的值越大，則__存取元素時(shí)發(fā)生沖突的可能性越大__；的值越小，則____。3. 在散列函數(shù)H(key)=key%p中，p應(yīng)取__小于表長(zhǎng)的最大素?cái)?shù)__。A. 35/12 B. 37/12 C. 39/12 D. 43/12 填空題（將正確的答案填在相應(yīng)的空中）1. 順序查找法的平均查找長(zhǎng)度為_ ___；二分查找法的平均查找長(zhǎng)度為__ __；分塊查找法（以二分查找確定塊）的平均查找長(zhǎng)度為____；哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長(zhǎng)度為____。 H (84)=7如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是__D__。 H (38)=5。A. 1 B. 2 C. 4 D. 86. 設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=key%11。A. 以順序方式存儲(chǔ) B. 以鏈接方式存儲(chǔ)C. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序3. 采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_C___.A. n B. n/2 C. (n+1)/2 D. (n1)/24. 采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為__D__。V1V2V3V4V5V6V7V8V9V1∝645∝∝∝∝∝V2∝∝∝∝1∝∝∝∝V3∝∝∝∝1∝∝∝∝V4∝∝∝∝∝2∝∝∝V5∝∝∝∝∝∝97∝V6∝∝∝∝∝∝∝4∝V7∝∝
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1