【正文】 5,7*} B.{1,7,15,7*,4,8,20,9}C.{1,4,7,8,20,15,7*,9} 練習3：已知序列{503，87，512，61，908，170，897，275，653，462}，寫出采用堆排序對該序列作非遞減排列時的排序過程。排序好的序列為：61，87，170，275，462，503，512，653，897，908 交換排序交換排序的基本思想是：利用交換數(shù)據元素的位置進行排序的方法。交換排序的主要算法有： 1) 冒泡排序 2) 快速排序 冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點：每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結束排序。例：關鍵字序列 T=(21，25，49，25*，16，08），請按從小到大的順序，寫出冒泡排序的具體實現(xiàn)過程。初態(tài)：21，25，49， 25*，16， 08第1趟21，25，25*，16， 08 ， 49第2趟21，25， 16， 08 ，25*，49第3趟21，16， 08 ，25， 25*，49第4趟16，08 ，21， 25， 25*，49第5趟08，16， 21， 25， 25*，49冒泡排序算法public static void bubbleSort(int[] a){ int i, j, flag=1。 int temp。 int n = 。 for(i = 1。 i n amp。amp。 flag == 1。 i++){ flag = 0。 for(j = 0。 j ni。 j++){ if(a[j] a[j+1]){ flag = 1。 temp = a[j]。 a[j] = a[j+1]。 a[j+1] = temp。 } } }}冒泡排序的算法分析時間效率：O（n2) —因為要考慮最壞情況（數(shù)據元素全部逆序），當然最好情況是數(shù)據元素已全部排好序，此時循環(huán)n1次，時間復雜度為O（n) 空間效率：O（1） —只在交換時用到一個緩沖單元 穩(wěn) 定 性： 穩(wěn)定 —25和25*在排序前后的次序未改變練習：關鍵字序列 T=(31，15，9，25，16，28），請按從小到大的順序，寫出冒泡排序的具體實現(xiàn)過程。初態(tài)：31，15，9， 25，16， 28第1趟15，9，25，16， 28， 31第2趟9，15， 16， 25，28，31第3趟9，15， 16，25， 28，31基本思想：設數(shù)組a中存放了n個數(shù)據元素，low為數(shù)組的低端下標，high為數(shù)組的高端下標，從數(shù)組a中任取一個元素（通常取a[low]）做為標準元素，以該標準元素調整數(shù)組a中其他各個元素的位置，使排在標準元素前面的元素均小于標準元素，排在標準元素后面的均大于或等于標準元素。這樣一次排序過程結束后，一方面將標準元素放在了未來排好序的數(shù)組中該標準元素應位于的位置上，另一方面將數(shù)組中的元素以標準元素為中心分成了兩個子數(shù)組，位于標準元素左邊子數(shù)組中的元素均小于標準元素，位于標準元素右邊子數(shù)組中的元素均大于等于或標準元素。對這兩個子數(shù)組中的元素分別再進行方法類同的遞歸快速排序。算法的遞歸出口條件是low≥high。 例、關鍵字序列 T=(60，55，48，37，10，90，84，36），請按從小到大的順序，寫出快速排序的具體實現(xiàn)過程。 快速排序算法各次快速排序過程 快速排序算法public static void quickSort(int[] a, int low, int high){ int i, j。 int temp。 i = low。 j = high。 temp = a[low]。 //取第一個元素為標準數(shù)據元素 while(i j){ //在數(shù)組的右端掃描 while(i j amp。amp。 temp = a[j]) j。 if(i j){ a[i] = a[j]。 i++。 } //在數(shù)組的左端掃描 while(i j amp。amp。 a[i] temp) i++。 if(i j){ a[j] = a[i]。 j。 } } a[i] = temp。 if(low i) quickSort(a, low, i1)。 //對左端子集合遞歸 if(i high) quickSort(a, j+1, high)。 //對右端子集合遞歸}快速排序算法分析：時間效率：一般情況下時間復雜度為O(nlog2n)，最壞情況是數(shù)據元素已全部正序或反序有序，此時每次標準元素都把當前數(shù)組分成一個大小比當前數(shù)組小1的子數(shù)組，此時時間復雜度為O(n2) 空間效率：O（log2n）—因為遞歸要用棧 穩(wěn) 定 性： 不 穩(wěn) 定 —因為有跳躍式交換。練習：已知序列{503,87,512,61,908,170,897,275,653,462}，給出采用快速排序對該序列作非遞減排序時每趟的結果。第一趟：【462 87 275 61 170】 503 【 897 908 653 512】第二趟：【170 87 275 61 】 462 503 【512 653】 897 【908】第三趟：【61 87】 170 【275】 462 503 512 【653】 897 908第四趟：61 【 87】 170 275 462 503 512 653 897 908最后排序結果：61 87 170 275 462 503 512 653 897 908，選擇排序是不穩(wěn)定的。，所需時間確定于初始記錄的排列情況，在初始記錄無序的情況下最好。（ A ） (n) (nlog2n) C. O(log2n) (n2) {8,9,10,4,5,6,20,1,2}只能是（ C ）算法的兩趟排序后的結果。 ，元素比較次數(shù)最少的是（C ） ,32,40,90,80,46,21,69 ,40,21,46,69,94,90,80 ,32,46,40,80,69,90,94 ,69,80,46,21,32,94,40 7. .以下排序算法中，（B ）不能保證每趟排序至少能將一個元素放到其最終位置上。 A. 快速排序 {28,16,32,12,60,2,5,72}序列進行快速排序，第一趟從小到大一次劃分結果為（B ） A.(2,5,12,16)26(60,32,72) B.(5,16,2,12)28(60,32,72) C.(2,16,12,5)28(60,32,72) D.(5,16,2,12)28(32,60,72) {18，16，14，12，10，8}進行從小到大的排序，所需進行的關鍵字比較總次數(shù)是（ B ）。 10. 一組記錄的關鍵字為{45，80，55，40，42，85}，則利用堆排序的方法建立的初始堆為（ B ）。A.{85，80，45，40，42，55} B.{85，80，55，40，42，45} C.{85，80，55，45，42，40} D.{85，55，80，42，45，40}第十章 文件　　文件是性質相同的記錄的集合。記錄是文件中存取的基本單位，數(shù)據項是文件可使用的最小單位，數(shù)據項有時稱字段或者屬性。　　文件　邏輯結構是一種線性結構?！　〔僮饔校簷z索和維護。并有實時和批量處理兩種處理方式?！　∥募〈鎯Y構是指文件在外存上的組織方式。　　基本的組織方式有：順序組織、索引組織、散列組織和鏈組織?！　〕Ｓ玫奈募M織方式：順序文件、索引文件、散列文件和多關鍵字文件?！　≡u價一個文件組織的效率，是執(zhí)行文件操作所花費的時間和文件組織所需的存儲空間。　　檢索功能的多寡和速度的快慢，是衡量文件操作質量的重要標志?！　№樞蛭募侵赴从涗涍M入文件的先后順序存放、其邏輯順序和物理順序一致的文件。主關鍵字有序稱順序有序文件，否則稱順序無序文件?！　∫磺写鎯υ陧樞虼鎯ζ鳎ㄈ绱艓В┥系奈募贾荒茼樞蛭募荒馨错樞虿檎曳ù嫒?。　　順序文件的插入、刪除和修改只能通過復制整個文件實現(xiàn)?！　∷饕募慕M織方式：通常是在主文件之外建立一張索引表指明邏輯記錄和物理記錄之間一一對應的關系，它和主文件一起構成索引文件。　　索引非順序文件中的索引表為稠密索引。索引順序文件中的索引表為稀疏索引?！　∪粲涗浐艽笫沟盟饕硪埠艽髸r，可對索引表再建立索引，稱為查找表。是一種靜態(tài)索引?！　∷饕樞蛭募Ｓ玫挠袃煞N：　　ISAM索引順序存取方法：是專為磁盤存取文件設計的，采用靜態(tài)索引結構。 　　VSAM虛擬存儲存取方法：采用B+樹作為動態(tài)索引結構，由索引集、順序集、數(shù)據集組成?！　∩⒘形募抢蒙⒘写鎯Ψ绞浇M織的文件，亦稱為直接存取文件?！　∩⒘形募　?yōu)點是：文件隨機存放，記錄不需要排序；插入刪除方便；存取速度快；不需要索引區(qū)，節(jié)省存儲空間?！∪秉c是：不能進行順序存取，只能按關鍵字隨機存取，且詢問方式限地簡單詢問，需要重新組織文件。　　多重表文件：對需要查詢的次關鍵字建立相應的索引，對相同次關鍵字的記錄建一個鏈表并將鏈表頭指針、長度、次關鍵字作為索引表的索引項?！　〉古疟恚捍侮P鍵字索引表稱倒排表，主文件和倒排表構成倒排文件。