計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)(排序)歷年真題試卷匯編7

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