




下載本文檔
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、 計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(排序)歷年真題試卷匯編 7(總分:66.00,做題時(shí)間:90分鐘)一、 單項(xiàng)選擇題(總題數(shù):15,分?jǐn)?shù):30.00)1.下述幾種排序方法中,要求內(nèi)存量最大的是( )?!局心洗髮W(xué) 2005一、6(2分)】(分?jǐn)?shù):2.00)a.歸并排序 b.快速排序c.插入排序d.選擇排序解析:2.快速排序方法在( )情況下最不利于發(fā)揮其長(zhǎng)處?!救A南理工大學(xué) 2007】(分?jǐn)?shù):2.00)a.要排序的數(shù)據(jù)量太大b.要排序的數(shù)據(jù)中含有多個(gè)相同值c.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)d.要排序的數(shù)據(jù)已基本有序 解析:3.當(dāng)待排序列基本有序時(shí),下列排序方法中( )最好?!颈本┼]電大學(xué) 2005一、10
2、(2分)】(分?jǐn)?shù):2.00)a.直接插入排序 b.快速排序c.堆排序d.歸并排序解析:4.設(shè)被排序的結(jié)點(diǎn)序列共有 n個(gè)結(jié)點(diǎn),在該序列中的結(jié)點(diǎn)已十分接近排序的情況下,用直接插入法、歸并法和一般的快速排序法對(duì)其排序,這些算法的時(shí)間復(fù)雜性應(yīng)為( )?!旧虾=煌ù髮W(xué) 2005四、5(2分)】(分?jǐn)?shù):2.00)a.o(n),o(n),o(n)b.o(n),o(n*log n),o(n*log n)22c.o(n),o(n*log n),o(n ) 22d.o(n ),o(n*log n),o(n )222解析:5.數(shù)據(jù)序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的( )的兩趟排序后
3、的結(jié)果。【合肥工業(yè)大學(xué) 1999一、3(2分)】(分?jǐn)?shù):2.00)a.選擇排序b.冒泡排序c.插入排序 d.堆排序解析:解析:對(duì)于 a、b和 d三種排序方法兩趟排序后,序列的首部或尾部的兩個(gè)元素應(yīng)是有序的兩個(gè)極值,而給定的序列并不滿足。6.一個(gè)排序算法的時(shí)間復(fù)雜度與( )有關(guān)?!救A中科技大學(xué) 2004一、8(1分)】(分?jǐn)?shù):2.00)a.排序算法的穩(wěn)定性b.所需比較關(guān)鍵字的次數(shù) c.所采用的存儲(chǔ)結(jié)構(gòu)d.所需輔助存儲(chǔ)空間的大小 解析:7.對(duì)一組數(shù)據(jù)(84,47,25,15,21)排序,數(shù)據(jù)的排列次序在排序的過(guò)程中的變化為(1)84 47 25 15 21 (2)1547 25 84 21 (3)
4、15 21 25 84 47 (4)15 21 25 47 84則采用的排序是( )。【南京理工大學(xué) 1997一、2(2分)】(分?jǐn)?shù):2.00)a.選擇 b.冒泡c.快速d.插入解析:8.對(duì)序列15,9,7,8,20,一 1,4)進(jìn)行排序,進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)?,9,一1,8,20,7,15),則采用的是( )排序。 【南京理工大學(xué) 1998一、8(2分)】(分?jǐn)?shù):2.00)a.選擇b.快速c.希爾 d.冒泡解析:解析:本題為步長(zhǎng)為 3的一趟希爾排序。9.若上題的數(shù)據(jù)經(jīng)一趟排序后的排列為9,15,7,8,20,一 1,4,則采用的是( )排序?!灸暇├砉ご髮W(xué) 1998一、9(2分)】(分?jǐn)?shù)
5、:2.00)a.選擇b.堆c.直接插入 d.冒泡解析:10.( )占用的額外空間的空間復(fù)雜性為 o(1)。【上海交通大學(xué) 2005四、4(2分)】(分?jǐn)?shù):2.00)a.堆排序算法 b.歸并排序算法c.快速排序算法d.以上答案都不對(duì)解析:11.有些排序算法在每趟排序過(guò)程中,都會(huì)有一個(gè)元素被放置在其最終的位置上,下列算法不會(huì)出現(xiàn)此情況的是( )?!颈本┙煌ù髮W(xué) 2005一、7(2分)】(分?jǐn)?shù):2.00)a.shell排序 b.堆排序c.冒泡排序d.快速排序解析:解析:每趟排序都會(huì)有一個(gè)元素被放置到最終位置上的排序方法有:冒泡排序,快速排序,直接選擇排序,堆排序。12.下列排序算法中,()排序在一趟
6、結(jié)束后不一定能選出一個(gè)元素放在其最終位置上?!灸暇├砉ご髮W(xué) 2005一、10(1分)】(分?jǐn)?shù):2.00)a.希爾 b.冒泡c.選擇d.直接插入 解析:13.下列排序算法中( )排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上?!灸暇├砉ご髮W(xué) 2001一、7(15分)】【哈爾濱工業(yè)大學(xué) 2001二、4(2分)】(分?jǐn)?shù):2.00)a.選擇b.冒泡c.歸并 d.堆解析:14.下列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是( )?!倦娮涌萍即髮W(xué) 2005一、2(1分)】(分?jǐn)?shù):2.00)a.堆排序b.起泡排序c.快速排序d.直接插入排序 解析:15.(多選)在下列排序方法中,(
7、)等方法在某趟結(jié)束后,選出一個(gè)元素到最終的位置。【華中科技大學(xué) 2007二、18(2分)】(分?jǐn)?shù):2.00)a.選擇排序 b.歸并排序c.冒泡排序 d.堆排序 解析:二、 填空題(總題數(shù):5,分?jǐn)?shù):10.00)16.快速排序在_的情況下最易發(fā)揮其長(zhǎng)處。(分?jǐn)?shù):2.00)_正確答案:(正確答案:最好每次劃分能得到兩個(gè)長(zhǎng)度相等的子文件。設(shè)文件長(zhǎng)度 n=2 1,第一遍劃分k得到兩個(gè)長(zhǎng)度為 ln2j的子文件,第二遍劃分得到 4個(gè)長(zhǎng)度為n4的子文件,以此類推,總共進(jìn)行 k=log(n+1)遍劃分。在最后一趟劃分時(shí),各子文件長(zhǎng)度均為 1,排序結(jié)束。)2解析:17.若一組記錄的排序碼為(46,79,56,3
8、8,40,84),利用堆排序建立的初始堆是_。 (注:堆頂元素取最大值。)【東南大學(xué) 2005數(shù)據(jù)結(jié)構(gòu)部分二、9(1分)】(分?jǐn)?shù):2.00)_正確答案:(正確答案:84,79,56,38,40,46)解析:18.高度為五的堆中,最多有_個(gè)元素,最少有_個(gè)元素。【哈爾濱工業(yè)大學(xué) 2005一、4(1分)】(分?jǐn)?shù):2.00)_正確答案:(正確答案:2 一 1, 2 )h-1h解析:19.堆排序的算法時(shí)間復(fù)雜度為_(kāi)?!竞戏使I(yè)大學(xué) 1999三、10(2分)】(分?jǐn)?shù):2.00)_正確答案:(正確答案:o(nlog n)2 解析:20.在堆排序中,首先需要進(jìn)行的操作是_?!颈本├砉ご髮W(xué) 2006十、5(1
9、分)】(分?jǐn)?shù):2.00)_正確答案:(正確答案:建堆)解析:三、 判斷題(總題數(shù):10,分?jǐn)?shù):20.00)21.當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時(shí),快速排序的執(zhí)行時(shí)間最省。 ( )【上海交通大學(xué) 1998一、16(1分)】(分?jǐn)?shù):2.00)a.正確b.錯(cuò)誤 解析:22.快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。()【北京郵電大學(xué) 1998一、7(2分)】【吉林大學(xué) 2007一、8(1分)2006一、9(1分)】【中國(guó)海洋大學(xué) 2005二、1(1分)】(分?jǐn)?shù):2.00)a.正確b.錯(cuò)誤 解析:23.內(nèi)排序的快速排序方法,在任何情況下均可得到最快的排序效果。(
10、)【中國(guó)海洋大學(xué) 2007二、14(1分)】(分?jǐn)?shù):2.00)a.正確b.錯(cuò)誤 解析:24.堆肯定是一棵平衡二叉樹。( )【南京航空航天大學(xué) 1997一、6(1分)】(分?jǐn)?shù):2.00)a.正確b.錯(cuò)誤 解析:解析:堆是 n個(gè)元素的序列,可以看作是完全二叉樹,但并無(wú)(根)結(jié)點(diǎn)大于左子樹而小于右子樹的要求,故其既不是二叉排序樹,更不會(huì)是平衡二叉樹。25.堆是滿二叉樹。 ( )【南京航空航天大學(xué) 1996六、6(1分)】(分?jǐn)?shù):2.00)a.正確b.錯(cuò)誤 解析:26.給定序列(100,86,48,73,35,39,42,57,66,21】,按堆結(jié)構(gòu)的定義,它一定是堆。 ( )【吉林大學(xué) 2006一、
11、3(1分)】(分?jǐn)?shù):2.00)a.正確 b.錯(cuò)誤解析:27.(101,88,46,70,34,39,45,58,66,10)是堆。( )【北京郵電大學(xué) 1999二、1(2分)】【上海海事大學(xué) 2005一、8(2分)】(分?jǐn)?shù):2.00)a.正確 b.錯(cuò)誤解析: 28.在用堆排序算法排序時(shí),如果要進(jìn)行增序排序,則需要采用“大根堆”。( )【合肥工業(yè)大學(xué) 2000 二、10(1分)】(分?jǐn)?shù):2.00)a.正確 b.錯(cuò)誤解析:29.堆排序是穩(wěn)定的排序方法。 ( ) 【上海交通大學(xué) 1998一、19(1分)】(分?jǐn)?shù):2.00)a.正確b.錯(cuò)誤 解析:30.有一大根堆,堆中任意結(jié)點(diǎn)的關(guān)鍵字均大于它的左右孩
12、子關(guān)鍵字,則其具有最小值的結(jié)點(diǎn)一定是一個(gè)葉結(jié)點(diǎn)并可能在堆的最后兩層中。 ( )【吉林大學(xué) 2006一、10(1分)】(分?jǐn)?shù):2.00)a.正確 b.錯(cuò)誤解析:四、 綜合題(總題數(shù):3,分?jǐn)?shù):6.00)31.簡(jiǎn)述直接插入排序、簡(jiǎn)單選擇排序、2路歸并排序的基本思想以及在時(shí)間復(fù)雜度和排序穩(wěn)定性上的差別?!疚鞅惫I(yè)大學(xué) 1999二(8分)】(分?jǐn)?shù):2.00)_正確答案:(正確答案:直接插入排序的基本思想是基于插入,開(kāi)始假定第一個(gè)記錄有序,然后從第二個(gè)記錄開(kāi)始,依次插入前面有序的子文件中。即將記錄 ri(2in)插入有序子序列 r1i1中,使記的有序序列從 r1i-1變?yōu)?r1i,最終使整個(gè)文件有序。共
13、進(jìn)行n一 1趟插入。最壞時(shí)間復(fù)雜度是 o(n ),平均時(shí)間復(fù)雜度是 o(n ),空間復(fù)雜度是 o(1),是穩(wěn)定排序。簡(jiǎn)單選擇排序的基本思想是基22于選擇,開(kāi)始有序序列長(zhǎng)度為零,第 i(1i 2),平均時(shí)間復(fù)雜度是 o(n ),空間復(fù)雜度是 o(1),是不穩(wěn)定2排序。二路歸并排序的基本思想是基于歸并,開(kāi)始將具有 n個(gè)待排序記錄的序列看成是 n個(gè)長(zhǎng)度為 1的有序序列,然后進(jìn)行兩兩歸并,得到n2個(gè)長(zhǎng)度為 2的有序序列,再進(jìn)行兩兩歸并,得到n4個(gè)長(zhǎng)度為4的有序序列。如此重復(fù),經(jīng)過(guò)log n趟歸并,最終得到一個(gè)長(zhǎng)度為 n的有序序列。最壞時(shí)間復(fù)雜度和平2均時(shí)間復(fù)雜度都是 o(nlog n),空間復(fù)雜度是 o(n),是穩(wěn)定排序。)2解析:32.對(duì)下列數(shù)據(jù)表,寫出采用希爾排序算法的每一趟排序結(jié)果。 (100,12,20,31,1,5,44,66,61,200,30,80,150,4,8)設(shè)增量序列為:d=-5,3,1)【中國(guó)海洋大學(xué) 2007一、4(8分)】(分?jǐn)?shù):2.00)_正確答案:(正確答案:數(shù)據(jù)表初態(tài):100,12,20,31,1,5,44,66,61,200,30,80,150,4,8第1趟后:5,12,20,4,1,30,44,66,31,8,100,80,150,61,200 第 2趟后:4,1,20,5,12,30,8,61,31,44,66,80,150
溫馨提示
- 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. 人人文庫(kù)網(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 手屈曲畸形的護(hù)理查房
- 淚小點(diǎn)外翻護(hù)理課件
- 心因性無(wú)食欲個(gè)案護(hù)理
- 距骨骨囊腫個(gè)案護(hù)理
- 漿液性中耳炎個(gè)案護(hù)理
- 腮腺囊腫的護(hù)理查房
- 結(jié)膜黑變病個(gè)案護(hù)理
- 電影敘事學(xué)理論創(chuàng)新-洞察闡釋
- 時(shí)尚媒體與首飾設(shè)計(jì)-洞察及研究
- 2025屆湖南衡陽(yáng)正源學(xué)校高一物理第二學(xué)期期末質(zhì)量跟蹤監(jiān)視模擬試題含解析
- 公司收購(gòu)公司協(xié)議書
- 基于移動(dòng)端的互聯(lián)網(wǎng)金融服務(wù)創(chuàng)新研究
- T∕CACM 024-2017 中醫(yī)臨床實(shí)踐指南 穴位埋線減肥
- GB 45189-2025氰化物安全生產(chǎn)管理規(guī)范
- 小號(hào)獨(dú)奏名曲100首
- 電廠安全知識(shí)培訓(xùn)
- 中國(guó)冠心病康復(fù)循證實(shí)踐指南(2024版)解讀
- 火電工程達(dá)標(biāo)投產(chǎn)考核標(biāo)準(zhǔn)(2024版)
- 停車場(chǎng)數(shù)據(jù)分析與優(yōu)化方案
- 護(hù)理安全管理課件
- 能源中國(guó)學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年
評(píng)論
0/150
提交評(píng)論