【正文】 。將其放入已排序序列的正確的位置上，此方法稱為（ ） A. 插入排序 B. 選擇排序 C. 交換排序 D. 歸并排序 ，并將其放入已排序序列的一端，此方法稱為（ ）。 A. 插入排序 B. 交換排序 C. 選擇排序 D. 歸并排序 （ ）。 A. 插入排序 B. 交換排序 C. 選擇排序 D. 歸并排序 ，這種排序方法稱為（ ）。 A. 插入排序 B. 交換排序 C. 選擇排序 D. 歸并排序 、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（ ）。 A. 插入排序 B. 快速排序 C. 堆排序 D. 歸并排序 ，直接插入排序的時(shí)間復(fù)雜度為（ ）。 A. O(log2n) B. O(n) C. O(n log2n) D. O(n2) ，冒泡排序的時(shí)間復(fù)雜度為（ ）。 A. O(log2n) B. O(n) C. O(n log2n) D. O(n2) ，歸并趟數(shù)的數(shù)量級(jí)為（ ）。 A. O(log2n) B. O(n) C. O(n log2n) D. O(n2) ，效率最高的排序方法是（ ）。 A. 插入排序 B. 快速排序 C. 堆排序 D. 歸并排序 ，要求內(nèi)存量最大的是（ ）。A. 插入排序 B. 交換排序 C. 選擇排序 D. 歸并排序 ，關(guān)鍵字比較的次數(shù)與記錄的初始排列秩序無關(guān)的是（ ）。 A. 希爾排序 B. 冒泡排序 C. 插入排序 D. 選擇排序（ ）情況下最不利于發(fā)揮其長(zhǎng)處。 A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個(gè)相同值 C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) ，平均情況下占用內(nèi)存量最大的是（ ）方法。 A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序，在最壞的情況下，其深度不會(huì)超過（ ）。A. n/2 B. n C. (n+1)/2 D. n+1 （49，72，68，13，38，50，97，27）進(jìn)行排序，前三趟排序結(jié)果時(shí)的結(jié)果依次為第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。該排序采用的方法是（ ）。A. 插入排序法 B. 選擇排序法 C. 冒泡排序法 ，排序趟數(shù)為（　?。. n1 B. n C. n+1 D. [log2n] （49，38，65，97，76，13，47，50）采用直接插入排序法進(jìn)行排序，要把第七個(gè)元素47插入到已排序中，為尋找插入的合適位置需要進(jìn)行（　?。┐卧亻g的比較。A. 3 B. 4 C. 5 D. 6，（　?。┦且环N穩(wěn)定性排序方法。 A. 插入排序法 B. 選擇排序法 34．一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ ）。 A．40，38，46，79，56，84 B．40，38，46，84，56，79C．40，38，46，56，79，84 D．38，40，46，56，79，8435．一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用堆排序的方法建立的初始堆為（ ）。 A．79，46，56，38，40，84 B．84，79，56，38，40，46C．84，79，56，46， 40，38， D．84，56，79，40，46，38 36．一組記錄的關(guān)鍵字序列為（25，48，16，35，79，82，23，40，36，72），其中，含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（ ）。 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，72 D．16，25，35，48，79，23，36，40，82，72 37．已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對(duì)該數(shù)列從小到到大排序，經(jīng)過一趟冒泡排序后的序列為（ ）。A．16，28，34，54，73，62，60，26，43，95 B．28，16，34，54，62，73，60，26，43，95C．28，16，34，54，62，60，73，26，43，95D．16，28，34，54，62，60，73，26，43，95 38．用某種排序的方法對(duì)線性表（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，元素序列的變化情況如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 其所采用的排序方法是（ ）。A. 希爾排序 D. 直接選擇排序二、填空題1．在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是 。2．如果對(duì)查找表只進(jìn)行查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中，以及查找某個(gè)特定數(shù)據(jù)元素的各種屬性兩種類型的基本操作，而不進(jìn)行插入和刪除操作數(shù)據(jù)元素的查找表稱為 。3．如果在查找表中進(jìn)行查詢的過程中，同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素，則稱此類查找表為 。4．關(guān)鍵字是記錄某個(gè) ，用它可以識(shí)別、確定一個(gè) 。5．在一個(gè)查找表中，能夠唯一地確定一個(gè)記錄的關(guān)鍵字稱為 。6．平均查找長(zhǎng)度是指為確定記錄在查找表中的位置，需要與給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的 。7． 查找是一種最簡(jiǎn)單的查找方法。8．折半查找又稱為 。使用該查找算法的前提條件是，查找表中記錄相應(yīng)的關(guān)鍵字值必須按 。9．折半查找只適用于 的有序表 。10．分塊查找又稱為 ，它是一種介于 和折半查找之間的查找方法。11．二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的一棵二叉樹： （1）若左子數(shù)不空，則左子樹所有結(jié)點(diǎn)的值 。 （2）若右子數(shù)不空，則右子樹所有結(jié)點(diǎn)的值 。 （3）左右子樹又分別是 。12．哈希表是用來存放查找表中記錄序列的表，每一個(gè)記錄的存儲(chǔ)位置是以該記錄得到關(guān)鍵字為 ，由相應(yīng)哈希函數(shù)計(jì)算所得到的 。 13．在有序表A[1….18]中，采用二分查找算法查找元素值等于A[17]的元素，所比較過的元素的下標(biāo)依次是 。14．根據(jù)排序過程中所用的存儲(chǔ)器不同，可以將排序方法分為 和 。 15．冒泡排序是一種比較簡(jiǎn)單的 方法。16．在對(duì)一組記錄（50，40，95，20，15，70，60，45，80）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需要比較 次。17．在歸并排序中，在第3趟歸并中，是把長(zhǎng)度為 的有序表歸并為長(zhǎng)度為 有序表。18．在堆排序和快速排序中，若原始記錄接近正序和反序，則選用 ，若原始記錄無序，則最好選用 。19．對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按_________排序結(jié)果是唯一的。20．按某關(guān)鍵字對(duì)記錄序列排序， 若在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。21．n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行________趟冒泡，第j趟冒泡要進(jìn)行______次元素間的比較。 22．當(dāng)從一個(gè)小根堆中刪除一個(gè)元素時(shí)，需要把 元素填補(bǔ)到 位置，然后再按條件把它逐層 調(diào)整。三、綜合題1．已知序列（70，83，100，105，10，32，7，9），請(qǐng)寫出對(duì)此序列采用插入排序法進(jìn)行升序排序時(shí)各趟的結(jié)果。2．已知序列（10，18，4，3，6，12，1，9，15，8），請(qǐng)寫出對(duì)此序列采用歸并排序法進(jìn)行升序排序時(shí)各趟的結(jié)果。3．已知序列（17，18，60，40，7，32，73，65，85）請(qǐng)給出采用冒泡排序法對(duì)該序列作升序排列時(shí)的每一趟結(jié)果。4．已知序列（503，87，512，61，908，170，897，275，653，462）請(qǐng)給出采用快速排序法對(duì)該序列作升序排列時(shí)的每一趟結(jié)果。5．設(shè)一組記錄的關(guān)鍵字序列為（51，85，61，43，45，49），采用堆排序算法完成以下操作：（要求小根堆，并畫出中間過程）（1）以二叉樹描述6個(gè)元素的初始堆（2）以二叉樹描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的5個(gè)元素、4個(gè)元素的堆6．設(shè)查找表為(20,19,24,57,68,11) (1)用冒泡對(duì)該表進(jìn)行排序，要求寫出每一趟的排序過程，通常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第j趟要進(jìn)行多少次元素間的比較？ (2)在排序后的有序表的基礎(chǔ)上，畫出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹.(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))(3)求在等概率條件下,對(duì)上述有序表成功查找的平均查找長(zhǎng)度。7． (1) 設(shè)有查找表{8,17,5,9,21,10,7,19,6},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹.（2）說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中序遍歷的結(jié)果.四、程序填空題1．以下直接輸入排序算法對(duì)存放在a[0],a[1],,a[n1]中，長(zhǎng)度為n的記錄序列按關(guān)鍵字key由小到大排序，完成程序中的空格部分。void disort (NODE a[ ], int n) { int I,j。NODE temp。 /*工作單位*/ for (i=1。in。i++){ temp=a[i]。 j=j1。 while (__①____amp。amp。a[j].key){ a[j+1]=__ _②__ ________③______} a[j+1]=____④____。}} 2．以下冒泡法程序?qū)Υ娣旁赼[1]，a[2]，……，a[n]中的序列進(jìn)行冒泡排序完成程序中的空格部分，其中n是元素個(gè)數(shù)，程序按升序排列。Void bsort (NODE a[ ], int) { NODE temp。 int i,j,flag。 for(j=1。 （1） 。j++)。 {flag=0。 for(i=1。 （2） 。i++) if(a[i].keya[i+1].key){flag=1。 temp=a[i]。 （3） 。 （4） 。}if(flag= =0)break。}} 程序中flag的功能是 （5） 五、算法設(shè)計(jì)題1．寫出在二叉樹中刪除一個(gè)結(jié)點(diǎn)的算法，且使刪除后仍為二叉樹，設(shè)刪除的結(jié)點(diǎn)由指針p所指，其雙親結(jié)點(diǎn)由指針f所指，并假設(shè)被刪除結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子。2．編寫順序查找算法。 六、完成：實(shí)驗(yàn)5――查找 實(shí)驗(yàn)6——排序根據(jù)實(shí)驗(yàn)要求（見教材P207－208）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。34 / 3