計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(排序)歷年真題試卷匯編7_第1頁
計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(排序)歷年真題試卷匯編7_第2頁
計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(排序)歷年真題試卷匯編7_第3頁
計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(排序)歷年真題試卷匯編7_第4頁
計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(排序)歷年真題試卷匯編7_第5頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、 計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(排序)歷年真題試卷匯編 7(總分:66.00,做題時間:90分鐘)一、 單項選擇題(總題數(shù):15,分數(shù):30.00)1.下述幾種排序方法中,要求內(nèi)存量最大的是( )?!局心洗髮W(xué) 2005一、6(2分)】(分數(shù):2.00)a.歸并排序 b.快速排序c.插入排序d.選擇排序解析:2.快速排序方法在( )情況下最不利于發(fā)揮其長處?!救A南理工大學(xué) 2007】(分數(shù):2.00)a.要排序的數(shù)據(jù)量太大b.要排序的數(shù)據(jù)中含有多個相同值c.要排序的數(shù)據(jù)個數(shù)為奇數(shù)d.要排序的數(shù)據(jù)已基本有序 解析:3.當待排序列基本有序時,下列排序方法中( )最好。【北京郵電大學(xué) 2005一、10

2、(2分)】(分數(shù):2.00)a.直接插入排序 b.快速排序c.堆排序d.歸并排序解析:4.設(shè)被排序的結(jié)點序列共有 n個結(jié)點,在該序列中的結(jié)點已十分接近排序的情況下,用直接插入法、歸并法和一般的快速排序法對其排序,這些算法的時間復(fù)雜性應(yīng)為( )?!旧虾=煌ù髮W(xué) 2005四、5(2分)】(分數(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é)果?!竞戏使I(yè)大學(xué) 1999一、3(2分)】(分數(shù):2.00)a.選擇排序b.冒泡排序c.插入排序 d.堆排序解析:解析:對于 a、b和 d三種排序方法兩趟排序后,序列的首部或尾部的兩個元素應(yīng)是有序的兩個極值,而給定的序列并不滿足。6.一個排序算法的時間復(fù)雜度與( )有關(guān)?!救A中科技大學(xué) 2004一、8(1分)】(分數(shù):2.00)a.排序算法的穩(wěn)定性b.所需比較關(guān)鍵字的次數(shù) c.所采用的存儲結(jié)構(gòu)d.所需輔助存儲空間的大小 解析:7.對一組數(shù)據(jù)(84,47,25,15,21)排序,數(shù)據(jù)的排列次序在排序的過程中的變化為(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分)】(分數(shù):2.00)a.選擇 b.冒泡c.快速d.插入解析:8.對序列15,9,7,8,20,一 1,4)進行排序,進行一趟后數(shù)據(jù)的排列變?yōu)?,9,一1,8,20,7,15),則采用的是( )排序。 【南京理工大學(xué) 1998一、8(2分)】(分數(shù):2.00)a.選擇b.快速c.希爾 d.冒泡解析:解析:本題為步長為 3的一趟希爾排序。9.若上題的數(shù)據(jù)經(jīng)一趟排序后的排列為9,15,7,8,20,一 1,4,則采用的是( )排序?!灸暇├砉ご髮W(xué) 1998一、9(2分)】(分數(shù)

5、:2.00)a.選擇b.堆c.直接插入 d.冒泡解析:10.( )占用的額外空間的空間復(fù)雜性為 o(1)?!旧虾=煌ù髮W(xué) 2005四、4(2分)】(分數(shù):2.00)a.堆排序算法 b.歸并排序算法c.快速排序算法d.以上答案都不對解析:11.有些排序算法在每趟排序過程中,都會有一個元素被放置在其最終的位置上,下列算法不會出現(xiàn)此情況的是( )?!颈本┙煌ù髮W(xué) 2005一、7(2分)】(分數(shù):2.00)a.shell排序 b.堆排序c.冒泡排序d.快速排序解析:解析:每趟排序都會有一個元素被放置到最終位置上的排序方法有:冒泡排序,快速排序,直接選擇排序,堆排序。12.下列排序算法中,()排序在一趟

6、結(jié)束后不一定能選出一個元素放在其最終位置上?!灸暇├砉ご髮W(xué) 2005一、10(1分)】(分數(shù):2.00)a.希爾 b.冒泡c.選擇d.直接插入 解析:13.下列排序算法中( )排序在一趟結(jié)束后不一定能選出一個元素放在其最終位置上?!灸暇├砉ご髮W(xué) 2001一、7(15分)】【哈爾濱工業(yè)大學(xué) 2001二、4(2分)】(分數(shù):2.00)a.選擇b.冒泡c.歸并 d.堆解析:14.下列排序算法中,某一趟結(jié)束后未必能選出一個元素放在其最終位置上的是( )?!倦娮涌萍即髮W(xué) 2005一、2(1分)】(分數(shù):2.00)a.堆排序b.起泡排序c.快速排序d.直接插入排序 解析:15.(多選)在下列排序方法中,(

7、)等方法在某趟結(jié)束后,選出一個元素到最終的位置?!救A中科技大學(xué) 2007二、18(2分)】(分數(shù):2.00)a.選擇排序 b.歸并排序c.冒泡排序 d.堆排序 解析:二、 填空題(總題數(shù):5,分數(shù):10.00)16.快速排序在_的情況下最易發(fā)揮其長處。(分數(shù):2.00)_正確答案:(正確答案:最好每次劃分能得到兩個長度相等的子文件。設(shè)文件長度 n=2 1,第一遍劃分k得到兩個長度為 ln2j的子文件,第二遍劃分得到 4個長度為n4的子文件,以此類推,總共進行 k=log(n+1)遍劃分。在最后一趟劃分時,各子文件長度均為 1,排序結(jié)束。)2解析:17.若一組記錄的排序碼為(46,79,56,3

8、8,40,84),利用堆排序建立的初始堆是_。 (注:堆頂元素取最大值。)【東南大學(xué) 2005數(shù)據(jù)結(jié)構(gòu)部分二、9(1分)】(分數(shù):2.00)_正確答案:(正確答案:84,79,56,38,40,46)解析:18.高度為五的堆中,最多有_個元素,最少有_個元素?!竟枮I工業(yè)大學(xué) 2005一、4(1分)】(分數(shù):2.00)_正確答案:(正確答案:2 一 1, 2 )h-1h解析:19.堆排序的算法時間復(fù)雜度為_?!竞戏使I(yè)大學(xué) 1999三、10(2分)】(分數(shù):2.00)_正確答案:(正確答案:o(nlog n)2 解析:20.在堆排序中,首先需要進行的操作是_?!颈本├砉ご髮W(xué) 2006十、5(1

9、分)】(分數(shù):2.00)_正確答案:(正確答案:建堆)解析:三、 判斷題(總題數(shù):10,分數(shù):20.00)21.當待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時,快速排序的執(zhí)行時間最省。 ( )【上海交通大學(xué) 1998一、16(1分)】(分數(shù):2.00)a.正確b.錯誤 解析:22.快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。()【北京郵電大學(xué) 1998一、7(2分)】【吉林大學(xué) 2007一、8(1分)2006一、9(1分)】【中國海洋大學(xué) 2005二、1(1分)】(分數(shù):2.00)a.正確b.錯誤 解析:23.內(nèi)排序的快速排序方法,在任何情況下均可得到最快的排序效果。(

10、)【中國海洋大學(xué) 2007二、14(1分)】(分數(shù):2.00)a.正確b.錯誤 解析:24.堆肯定是一棵平衡二叉樹。( )【南京航空航天大學(xué) 1997一、6(1分)】(分數(shù):2.00)a.正確b.錯誤 解析:解析:堆是 n個元素的序列,可以看作是完全二叉樹,但并無(根)結(jié)點大于左子樹而小于右子樹的要求,故其既不是二叉排序樹,更不會是平衡二叉樹。25.堆是滿二叉樹。 ( )【南京航空航天大學(xué) 1996六、6(1分)】(分數(shù):2.00)a.正確b.錯誤 解析:26.給定序列(100,86,48,73,35,39,42,57,66,21】,按堆結(jié)構(gòu)的定義,它一定是堆。 ( )【吉林大學(xué) 2006一、

11、3(1分)】(分數(shù):2.00)a.正確 b.錯誤解析:27.(101,88,46,70,34,39,45,58,66,10)是堆。( )【北京郵電大學(xué) 1999二、1(2分)】【上海海事大學(xué) 2005一、8(2分)】(分數(shù):2.00)a.正確 b.錯誤解析: 28.在用堆排序算法排序時,如果要進行增序排序,則需要采用“大根堆”。( )【合肥工業(yè)大學(xué) 2000 二、10(1分)】(分數(shù):2.00)a.正確 b.錯誤解析:29.堆排序是穩(wěn)定的排序方法。 ( ) 【上海交通大學(xué) 1998一、19(1分)】(分數(shù):2.00)a.正確b.錯誤 解析:30.有一大根堆,堆中任意結(jié)點的關(guān)鍵字均大于它的左右孩

12、子關(guān)鍵字,則其具有最小值的結(jié)點一定是一個葉結(jié)點并可能在堆的最后兩層中。 ( )【吉林大學(xué) 2006一、10(1分)】(分數(shù):2.00)a.正確 b.錯誤解析:四、 綜合題(總題數(shù):3,分數(shù):6.00)31.簡述直接插入排序、簡單選擇排序、2路歸并排序的基本思想以及在時間復(fù)雜度和排序穩(wěn)定性上的差別。【西北工業(yè)大學(xué) 1999二(8分)】(分數(shù):2.00)_正確答案:(正確答案:直接插入排序的基本思想是基于插入,開始假定第一個記錄有序,然后從第二個記錄開始,依次插入前面有序的子文件中。即將記錄 ri(2in)插入有序子序列 r1i1中,使記的有序序列從 r1i-1變?yōu)?r1i,最終使整個文件有序。共

13、進行n一 1趟插入。最壞時間復(fù)雜度是 o(n ),平均時間復(fù)雜度是 o(n ),空間復(fù)雜度是 o(1),是穩(wěn)定排序。簡單選擇排序的基本思想是基22于選擇,開始有序序列長度為零,第 i(1i 2),平均時間復(fù)雜度是 o(n ),空間復(fù)雜度是 o(1),是不穩(wěn)定2排序。二路歸并排序的基本思想是基于歸并,開始將具有 n個待排序記錄的序列看成是 n個長度為 1的有序序列,然后進行兩兩歸并,得到n2個長度為 2的有序序列,再進行兩兩歸并,得到n4個長度為4的有序序列。如此重復(fù),經(jīng)過log n趟歸并,最終得到一個長度為 n的有序序列。最壞時間復(fù)雜度和平2均時間復(fù)雜度都是 o(nlog n),空間復(fù)雜度是 o(n),是穩(wěn)定排序。)2解析:32.對下列數(shù)據(jù)表,寫出采用希爾排序算法的每一趟排序結(jié)果。 (100,12,20,31,1,5,44,66,61,200,30,80,150,4,8)設(shè)增量序列為:d=-5,3,1)【中國海洋大學(xué) 2007一、4(8分)】(分數(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. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論