《第3章排序答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《第3章排序答案.doc（10頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第3章 排序 自測(cè)卷 答案 姓名 班級(jí) 題號(hào) 一 二 三 四 五 總分 題分 24 18 36 8 14 100 得分 一、填空題（每空1分，共24分） 1. 大多數(shù)排序算法都有兩個(gè)基本的操作： 比較（兩個(gè)關(guān)鍵字的大?。? 和 移動(dòng)（記錄或改變指向記錄的指針） 。 2. 在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置至少需比較 3 次。(可約定為，從后向前比較) 3. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 插入排序（到尾部） ；若初始數(shù)據(jù)基本反序，則選用 選擇排序 。 4. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用 堆排序 ；若初始記錄基本無(wú)序，則最好選用 快速排序 。 5. 對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞的情況下所需要的時(shí)間是 O(n2) 。若對(duì)其進(jìn)行快速排序，在最壞的情況下所需要的時(shí)間是 O(n2) 。 6. 對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是 O(nlog2n) ，所需要的附加空間是 O(n) 。 7．【計(jì)研題2000】對(duì)于n個(gè)記錄的表進(jìn)行2路歸并排序，整個(gè)歸并排序需進(jìn)行 log2n 趟（遍），共計(jì)移 動(dòng) n log2n 次記錄。 (即移動(dòng)到新表中的總次數(shù)！共log2n趟，每趟都要移動(dòng)n個(gè)元素) 8.設(shè)要將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按字母序的升序重新排列，則： 冒泡排序一趟掃描的結(jié)果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ； 初始步長(zhǎng)為4的希爾（shell）排序一趟的結(jié)果是 P, A, C, S, Q, D, F, X , R, H,M, Y ； 二路歸并排序一趟掃描的結(jié)果是 H, Q, C, Y，A, P, M, S, D, R, F, X ； 快速排序一趟掃描的結(jié)果是 F, H, C, D, P, A, M, Q, R, S, Y，X ； 堆排序初始建堆的結(jié)果是 A, D, C, R, F, Q, M, S, Y，P, H, X 。 9. 在堆排序、快速排序和歸并排序中， 若只從存儲(chǔ)空間考慮，則應(yīng)首先選取 堆排序 方法，其次選取 快速排序 方法，最后選取 歸并排序 方法； 若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng) 選取歸并排序方法； 若只從平均情況下最快考慮，則應(yīng)選取快速排序方法； 若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取堆排序方法。 二、單項(xiàng)選擇題（每小題1分，共18分） （ C ）1．將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較 次。 Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25 （ C ）2． 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為 Ａ. 希爾排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 選擇排序 （ D ）3． 排序方法中，從未排序序列中挑選元素，并將其依次插入已排序序列（初始時(shí)為空）的一端的方法，稱(chēng)為 Ａ. 希爾排序 Ｂ. 歸并排序 Ｃ. 插入排序 Ｄ. 選擇排序 （ C ）4．對(duì)ｎ個(gè)不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多。 Ａ. 從小到大排列好的 Ｂ. 從大到小排列好的 Ｃ. 元素?zé)o序 Ｄ. 元素基本有序 （ D ）5．對(duì)ｎ個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為 Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2 (前3個(gè)答案都太小了) （ C ）6．快速排序在下列哪種情況下最易發(fā)揮其長(zhǎng)處。 Ａ. 被排序的數(shù)據(jù)中含有多個(gè)相同排序碼 Ｂ. 被排序的數(shù)據(jù)已基本有序 Ｃ. 被排序的數(shù)據(jù)完全無(wú)序 Ｄ. 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊 （ B ）7． 【計(jì)研題2001】對(duì)有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是 A．O(n) B．O(n2) C．O(nlog2n) D．O(n3) （ C ）8．若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為 Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40,38, 46 , 79, 56, 84 Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38,46, 84, 56, 79 （ A&D ）9．【計(jì)研題2001】在最好情況下，下列排序算法中 排序算法所需比較關(guān)鍵字次數(shù)最少。 A．冒泡 B．歸并 C．快速 D．直接插入 (僅n—1次！) （ C ）10． 【計(jì)研題2001】置換選擇排序的功能是 。 （置換選擇排序＝簡(jiǎn)單選擇排序？） A．選出最大的元素 B．產(chǎn)生初始?xì)w并段 C．產(chǎn)生有序文件 D．置換某個(gè)記錄 （ A ）11．將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至少需要比較 次。 Ａ. 4 Ｂ. 5 Ｃ. 6 Ｄ. 7 （ D ）12．下列關(guān)鍵字序列中， 是堆。 Ａ. 16,72,31,23,94,53 Ｂ. 94,23, 31, 72, 16, 53 Ｃ. 16, 53, 23,94,31, 72 Ｄ. 16, 23, 53,31, 94, 72 （ B ）13．堆是一種 排序。 Ａ. 插入 Ｂ.選擇 Ｃ. 交換 Ｄ. 歸并 （ C ）14．堆的形狀是一棵 Ａ. 二叉排序樹(shù) Ｂ.滿二叉樹(shù) Ｃ. 完全二叉樹(shù) Ｄ. 平衡二叉樹(shù) （ B ）15．若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為 Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46 Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 84, 56, 79, 40, 46, 38 （ B ）16． 下述幾種排序方法中，平均查找長(zhǎng)度（ASL）最小的是 Ａ. 插入排序 Ｂ.快速排序 Ｃ. 歸并排序 Ｄ. 選擇排序 （ C ）17． 下述幾種排序方法中，要求內(nèi)存最大的是 Ａ. 插入排序 Ｂ.快速排序 Ｃ. 歸并排序 Ｄ. 選擇排序 （ B ）18．目前以比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無(wú)關(guān)的是 Ａ. 插入排序 Ｂ. 二分插入排序 Ｃ. 快速排序 Ｄ. 冒泡排序 三、簡(jiǎn)答題（每小題4分，共36分） 1. 【全國(guó)專(zhuān)升本題】已知序列基本有序，問(wèn)對(duì)此序列最快的排序方法是多少，此時(shí)平均復(fù)雜度是多少？ 答：插入排序和冒泡應(yīng)該是最快的。因?yàn)橹挥斜容^動(dòng)作，無(wú)需移動(dòng)元素。此時(shí)平均時(shí)間復(fù)雜度為O(n) 2. 設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好采用哪種排序方法？ 答：用堆排序或錦標(biāo)賽排序最合適，因?yàn)椴槐氐热吭嘏磐昃湍艿玫剿杞Y(jié)果，時(shí)間效率為O(nlog2n) ；若用冒泡排序則需時(shí)n!/(n-10)! 3. 用某種排序方法對(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， 問(wèn)采用的是什么排序方法？ 答：用的是快速排序方法。注意每一趟要振蕩完全部元素才算一個(gè)中間結(jié)果。 4. 對(duì)于整數(shù)序列100，99，98，…3，2，1，如果將它完全倒過(guò)來(lái)，分別用冒泡排序和快速排序法，它們的比較次數(shù)和交換次數(shù)各是多少？ 答：冒泡排序的比較和交換次數(shù)將最大，都是1+2+…+n-1=n(n-1)/2＝5099=4545次 快速排序則看按什么數(shù)據(jù)來(lái)分子表。 如果按100來(lái)分，則很慘，也會(huì)是n(n-1)/2！ 若按中間數(shù)據(jù)50或51來(lái)分表，則： 第1輪能確定1個(gè)元素，即在1個(gè)子表中比較和交換了n－1個(gè)元素；n－（21-1） 第2輪能再確定2個(gè)元素，即在2個(gè)子表中比較和交換了n－3個(gè)元素；n－（22-1） 第3輪能再確定4個(gè)元素，即在4個(gè)子表中比較和交換了n－7個(gè)元素；n－（23-1） 第4輪能再確定8個(gè)元素，即在8個(gè)子表中比較和交換了n－15個(gè)元素；n－（24-1） …… 第6輪能再確定32個(gè)元素，即在32個(gè)子表中比較和交換了n－65個(gè)元素；n－（26-1） 第7輪則能全部確定，（因?yàn)?7=128）， 在100個(gè)子表中比較和交換了n－（100－1）個(gè)元素； 比較和交換總次數(shù)為：7n－(21－1＋22－1＋23－1……＋26－1＋100－1) ＝7n+7－(1＋2＋4＋……＋64+100)=7n－(8+16+32+164)=700-220=480次 若從中間選擇初始元素，則ASL=（n+1）log2n－(21＋22＋23+……＋2m)= nlog2n+log2n－(21＋22＋23+……＋n)≈O（nlog2n） 5.【全國(guó)專(zhuān)升本試題】【嚴(yán)題集10.15④】設(shè)有n個(gè)值不同的元素存于順序結(jié)構(gòu)中，試問(wèn)能否用比2n-3少的比較次數(shù)選出這n個(gè)元素中的最大值和最小值？若能請(qǐng)說(shuō)明如何實(shí)現(xiàn)（不需寫(xiě)算法）。在最壞情況下至少需進(jìn)行多少次比較。（或問(wèn)：對(duì)含有n個(gè)互不相同元素的集合，同時(shí)找最大元和最小元至少需進(jìn)行多少次比較?） 答：若用冒泡排序法，求最大值需n-1次比較；第二趟改為從n-1開(kāi)始求最小值，需n-2次比較，合計(jì)2n-3次。 顯然本題意圖是放棄冒泡排序，尋找其他方法。 法1 ：一個(gè)簡(jiǎn)單的辦法是，在一趟比較時(shí)，將頭兩個(gè)元素分別作為最大和最小值的暫存內(nèi)容，將其余n-2個(gè)元素與其相比，具體可設(shè)計(jì)為： 第1步：a1a2? YES則直接替換a2，NO則再比較a1， 1～2次； 第3步：a4>a2? YES則直接替換a2，NO則再比較a1， 1～2次； …… 第n-1步：an>a2? YES則直接替換a2，NO則再比較a1， 1～2次； 合計(jì)：（n-2）（1～2）＋1=(n-1)~(2n-3 )≤2n-3 最好情況至少需要n-1次比較，最壞情況需2n-3次。 法2 ：借用快速排序第一趟思想：以a1為支點(diǎn)，將序列分成兩個(gè)子表。這一趟需要n-1次比較； 然后，在左邊的子表中求最小值，冒泡一趟需要y-1次； 在右邊的子表中求最大值，冒泡一趟需要z-1次； 合計(jì)需要(n-1)+( y-1)+( z-1)=n+y+z-3 因?yàn)閥+z+1=n, 所以總次數(shù)＝2n－4≤2n－3!!!!!!!!!!! 但最壞情況下仍為為2n-3次，即一趟完畢后仍為單子表的情況。怎么辦？有無(wú)更好的辦法？ 法3 ：能否用錦標(biāo)賽排序思路？求最大值等于求冠軍，需要n—1次比較；但接著求最小值，等于在n/2個(gè)葉子中比較即可。 編程也不復(fù)雜：可設(shè)計(jì)為， 第一趟：n個(gè)數(shù)據(jù)兩兩比較（共n/2次），小者放偶數(shù)位，大者放奇數(shù)位； 第二趟：對(duì)奇數(shù)位元素繼續(xù)兩兩比較（n/4次）；對(duì)偶數(shù)位元素也兩兩比較（n/4次）；合計(jì)n/2次； 第三趟：對(duì)奇數(shù)位元素繼續(xù)兩兩比較（n/23次）；對(duì)偶數(shù)位元素也兩兩比較（n/23次）；合計(jì)n/22次； 第四趟：對(duì)奇數(shù)位元素繼續(xù)兩兩比較（n/24次）；對(duì)偶數(shù)位元素也兩兩比較（n/24次）；合計(jì)n/23次； …… 第log2n趟：對(duì)奇數(shù)位元素繼續(xù)兩兩比較（n/2log2n次＝1）；對(duì)偶數(shù)位元素也兩兩比較（1次）；合計(jì)2次； 全部比較次數(shù)為：2+4+8+……＋n/2次≤2n-3 （n>1） 用二進(jìn)制性質(zhì)即可證明？ 因?yàn)?20+21+…2k-2+2k-1<2k ，即21+…2k-2+2k-1<2k —1 < 2k —1 +2k —2 (n=2k, 當(dāng)k＝1，即n=2時(shí)為極端情況，1＝1; n=3時(shí)，1.5<3 k=2時(shí)，即n=4時(shí)，2<5 6. 【成教考題】將兩個(gè)長(zhǎng)度為n的有序表歸并為一個(gè)長(zhǎng)度為2n的有序表，最小需要比較n次，最多需要比較2n-1次，請(qǐng)說(shuō)明這兩種情況發(fā)生時(shí)，兩個(gè)被歸并的表有何特征? 答：最少的比較次數(shù)是這樣一種情況：若A表所有元素都小于（或大于）B表元素，則A1比較完B1～Bn之后，直接拼接即可。 最多比較次數(shù)的情況應(yīng)該是A、B兩表互相交錯(cuò)，此時(shí)需要穿插重排。則A表的每個(gè)元素都要與B表元素相比，A1與B1相比，能確定其中一個(gè)元素的位置；剩下一個(gè)還要與另一表中下一元素再比較一次， 即：在表A或表B的n個(gè)元素中，除了最后一個(gè)元素外，每個(gè)元素都要比較2次！最壞情況總共為2n—1次。 7. 【嚴(yán)題集10.11②】試問(wèn)：按錦標(biāo)賽排序的思想，決出8名運(yùn)動(dòng)員之間的名次排列，至少需編排多少場(chǎng)次的比賽（應(yīng)考慮最壞的情況）？ 劉答：不能簡(jiǎn)單地用(n-1)+(n-2)log2n來(lái)計(jì)算比賽場(chǎng)次。要特別注意，隨著n/2的葉子結(jié)點(diǎn)被調(diào)整完畢之后，樹(shù)的深度會(huì)逐層減少！ 分別n=8和n=7的情況推導(dǎo)并歸納，得到如下計(jì)算公式： 比賽場(chǎng)次＝（n-1）+n/2(k-1)+ (n/22)(k-2)+…+ n/2(k-1) ，其中k=log2n 當(dāng)n＝8時(shí)，k=3, 比賽場(chǎng)次＝7＋8/2(2)＋8/4= 17場(chǎng)(這是最壞情況，即每次都先從葉子調(diào)整起) 8. 【嚴(yán)題集10.19④】假設(shè)某大旅店共有5000個(gè)床位，每天需要根據(jù)住宿旅客的文件制造一份花名冊(cè)，該名冊(cè)要求按?。ㄊ校┑拇涡蚺帕?，每一?。ㄊ校┌纯h（區(qū)）排列，又同一縣（區(qū)）的旅客按姓氏排列。請(qǐng)你為旅店的管理人員設(shè)計(jì)一個(gè)制作這份花名冊(cè)的方法。 （提示）這是一個(gè)多關(guān)鍵字的排序問(wèn)題。請(qǐng)思考對(duì)這個(gè)文件進(jìn)行排序用哪一種方法更合適，是MSD法還是LSD法？ 答：采用哪種排序方法，關(guān)鍵要看記錄的結(jié)構(gòu)是如何定義的，如果旅客填表如下： ?。ㄊ校? 縣（區(qū)） 姓名 床位號(hào) 則按題意要求，應(yīng)當(dāng)采用MSD法，否則無(wú)法滿足。 但若“姓名”項(xiàng)在前，則必須用LSD才符合題意要求。 9. 【全國(guó)專(zhuān)升本題】【嚴(yán)題集10.6④】奇偶交換排序如下所述：第一趟對(duì)所有奇數(shù)i，將a[i]和a[i+1]進(jìn)行比較；第二趟對(duì)所有的偶數(shù)i,將a[i]和a[i+1]進(jìn)行比較，若a[i]>a[i+1]，則兩者交換；第三趟對(duì)奇數(shù)i,第四趟對(duì)偶數(shù)i；……依次類(lèi)推直至整個(gè)序列有序?yàn)橹埂? （1）試問(wèn)這種排序方法的結(jié)束條件是什么？是否為穩(wěn)定排序？ （2）分析當(dāng)初始序列為正序或逆序兩種情況下，奇偶交換排序過(guò)程中所需進(jìn)行的關(guān)鍵字比較的次數(shù)。 （3）分析此種排序方法的平均復(fù)雜度及最壞復(fù)雜度。 答：（1） 這種算法其實(shí)是兩兩比較，第一趟很像錦標(biāo)賽的“初賽”，將勝者（大數(shù)）置于偶數(shù)單元； 第二趟對(duì)偶數(shù)單元操作，即第一組大者與第二組小者戰(zhàn)，大者后移。結(jié)果相當(dāng)于冒泡排序的一趟； 所以結(jié)束條件應(yīng)為偶數(shù)趟無(wú)交換。 結(jié)束條件是：若n為偶數(shù)時(shí)，奇數(shù)循環(huán)時(shí)i>n-1 ，偶數(shù)循環(huán)時(shí)i>n ， 若n為奇數(shù)時(shí)，奇數(shù)循環(huán)時(shí)i>n 偶數(shù)循環(huán)時(shí)i>n+1 似乎不穩(wěn)定？因?yàn)榻粨Q沒(méi)有依次進(jìn)行。 四、【全國(guó)專(zhuān)升本類(lèi)似題】【類(lèi)嚴(yán)題集10.1①】以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫(xiě)出執(zhí)行以下算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)，并說(shuō)明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？ ① 直接插入排序 ② 希爾排序 ③冒泡排序 ④快速排序 ⑤直接選擇排序 ⑥ 堆排序 ⑦ 歸并排序 ⑧ 基數(shù)排序 （8分） 解：先回答第2問(wèn)： ① ⑤ ⑦ ⑧皆易于在鏈表上實(shí)現(xiàn)。 ① 直接插入排序的中間過(guò)程如下： ② 希爾排序的中間過(guò)程如下： ③ 冒泡排序的中間過(guò)程如下： ④快速排序的中間過(guò)程如下： ⑤ 直接選擇排序的中間過(guò)程如下： ⑥堆排序（大根堆）的中間過(guò)程如下： ⑦ 歸并排序排序的中間過(guò)程如下： ⑧ 基數(shù)排序的中間過(guò)程如下： 五、算法設(shè)計(jì)題（4選2， 每題7分，共14分） 1. 【嚴(yán)題集10.25③】試編寫(xiě)教科書(shū)10.2.2節(jié)中所述鏈表插入排序的算法。 10.25 void SLInsert_Sort(SLList &L)//靜態(tài)鏈表的插入排序算法 { L.r[0].key=0;L.r[0].next=1; L.r[1].next=0; //建初始循環(huán)鏈表 for(i=2;i<=L.length;i++) //逐個(gè)插入 { p=0;x=L.r[i].key; while(L.r[L.r[p].next].keyL.r[i]; L.r[i].next=p; } p=q; }//for }//SLInsert_Sort 2. 【嚴(yán)題集10.30④】按下述原則編寫(xiě)快排的非遞歸算法： （1） 一趟排序之后，先對(duì)長(zhǎng)度較短的子序列進(jìn)行排序，且將另一子序列的上、下界入棧保存； （2） 若待排記錄數(shù)≤3,則不再進(jìn)行分割，而是直接進(jìn)行比較排序。 10.30 typedef struct { int low; int high; } boundary; //子序列的上下界類(lèi)型 void QSort_NotRecurve(int SQList &L)//快速排序的非遞歸算法 { low=1;high=L.length; InitStack(S); //S的元素為boundary類(lèi)型 while(low2) //如果當(dāng)前子序列長(zhǎng)度大于3且尚未排好序 { pivot=Partition(L,low,high); //進(jìn)行一趟劃分 if(high-pivot>pivot-low) { Push(S,{pivot+1,high}); //把長(zhǎng)的子序列邊界入棧 high=pivot-1; //短的子序列留待下次排序 } else { Push(S,{low,pivot-1}); low=pivot+1; } }//if else if(low=pivotkey) high--; L.r[low]=L.r[high]; while(lowL.r[high].key) L.r[low]<->L.r[high]; else //子序列含有三個(gè)元素 { if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1]; if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high]; if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1]; } }//Easy_Sort 3. 【嚴(yán)題集10.41④】假設(shè)有1000個(gè)關(guān)鍵字為小于10000的整數(shù)的記錄序列，請(qǐng)?jiān)O(shè)計(jì)一種排序方法，要求以盡可能少的比較次數(shù)和移動(dòng)次數(shù)實(shí)現(xiàn)排序，并按你的設(shè)計(jì)編出算法。 解：可以用基數(shù)排序來(lái)實(shí)現(xiàn)，關(guān)鍵字位數(shù)d=4，數(shù)基radix=10（從0～9） 則基數(shù)排序的算法如下； void Hash_Sort(int a[ ])//對(duì)1000個(gè)關(guān)鍵字為四位整數(shù)的記錄進(jìn)行排序 { int b[10000]; for(i=0;i<1000;i++) //直接按關(guān)鍵字散列 （即分配） { for(j=a[i];b[j];j=(j+1)%10000); b[j]=a[i]; } for(i=0,j=0;i<1000;j++) //將散列收回a中 if(b[j]) { for(x=b[j],k=j;b[k];k=(k+1)%10000) if(b[k]==x) { a[i++]=x; b[k]=0; } }//if }//Hash_Sort 4. 【嚴(yán)題集10.42④】序列的“中值記錄”指的是：如果將此序列排序后，它是第[n/2]個(gè)記錄。試寫(xiě)一個(gè)求中值記錄的算法。 10.42 typedef struct { int gt; //大于該記錄的個(gè)數(shù) int lt; //小于該記錄的個(gè)數(shù) } place; //整個(gè)序列中比某個(gè)關(guān)鍵字大或小的記錄個(gè)數(shù) int Get_Mid(int a[ ],int n) //求一個(gè)序列的中值記錄的位置 { place b[MAXSIZE]; for(i=0;ia[i]) b[i].gt++; else if(a[j]

下載提示(請(qǐng)認(rèn)真閱讀)

• 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
• 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
• 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。

同意并開(kāi)始全文預(yù)覽

文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！

文檔加載中……請(qǐng)稍候！
如果長(zhǎng)時(shí)間未打開(kāi)，您也可以點(diǎn)擊刷新試試。

下載文檔到電腦，查找使用更方便

5 積分

下載

還剩頁(yè)未讀，繼續(xù)閱讀

舉報(bào)
版權(quán)申訴 word格式文檔無(wú)特別注明外均可編輯修改；預(yù)覽文檔經(jīng)過(guò)壓縮，下載后原文更清晰！ 立即下載

配套講稿：

如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。

特殊限制：

部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。

關(guān) 鍵  詞：

排序 答案

溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

  裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書(shū)面授權(quán)，請(qǐng)勿作他用。

關(guān)于本文

本文標(biāo)題：第3章排序答案.doc
鏈接地址：http://www.820124.com/p-12786901.html

最新文檔

• 2020高考化學(xué)熱門(mén)專(zhuān)題：原理綜合透題型析課件
• 現(xiàn)代中國(guó)的教育說(shuō)課稿課件
• 蒸餾和熔點(diǎn)沸點(diǎn)的測(cè)定和溫度計(jì)的校正
• 臨時(shí)起搏器的護(hù)理
• 恒成實(shí)業(yè)網(wǎng)絡(luò)推廣方案
• 勿為小惡優(yōu)秀課件-粵教版
• 人教版初中地理七年級(jí)上冊(cè)人口與人種課件7
• 誡子書(shū)課件文檔
• 軟件測(cè)試計(jì)劃書(shū)與測(cè)試用例編寫(xiě)課件
• 人教版五年級(jí)數(shù)學(xué)上冊(cè)課件3小數(shù)除法第2課時(shí)除數(shù)是整數(shù)的小數(shù)除法課件
• 太白酒2002年全國(guó)推廣營(yíng)銷(xiāo)企劃案
• 滬教版小學(xué)語(yǔ)文三年級(jí)上冊(cè)《小狗杜克》課件1
• 我們的情感世界課件7-人教版
• 擔(dān)保產(chǎn)品案例講解及其風(fēng)險(xiǎn)控制設(shè)計(jì)(含法律相關(guān)規(guī)范)
• 【部編版】四年級(jí)語(yǔ)文上冊(cè)《2.走月亮》ppt課件