點擊查看：2015年計算機二級公共基礎(chǔ)知識考點測試題匯總

　　排序技術(shù)

　　1[單選題]對長度n的線性表排序，在最壞情況下，比較次數(shù)不是n(n一1)/2的排序方法是(　　)。

　　參考答案：D

　　參考解析：排序技術(shù)有：①交換類排序法(冒泡排序法、快速排序法);②插入類排序法(簡單插入排序、希爾排序);③選擇類排序法(簡單選擇排序法、堆排序法)。在最壞情況下，希爾排序需要的比較次數(shù)是O(nl.5)、堆排序需要的比較次數(shù)是O(nlog2n)、其它排序方法需要的比較次數(shù)都是n(n.1)/2。因此本題的正確答案是D。

　　2[單選題]冒泡排序在最壞情況下的比較次數(shù)是(　　)。

　　參考答案：C

　　參考解析：對于長度為n的線性表，在最壞情況下，冒泡排序需要進行的比較次數(shù)是n(n一1)/2。因此本題的正確答案是C。

　　3[單選題]通過相鄰數(shù)據(jù)元素的交換逐步：搿線性表變成有序的排序方法是(　　)

　　A.冒泡排序法B.簡單選擇排序法C.簡單插入排序法D.希爾排序法

　　參考答案：A

　　4[單選題]冒泡排序在最壞情況下的比較次數(shù)是(　　)

　　A.n(n+1)/2B.nlog2nC.n(n-1)/2D.n/2

　　參考答案：C

　　參考解析：對于長度為n的線性表，在最壞情況下，冒泡排序需要進行的比較次數(shù)是n(n-1)/2。因此本題的正確答案是C。

　　5[單選題]快速排序法屬于(　　)

　　A.選擇類排序法B.交換類排序法C.插入類排序法D.歸并類排序法

　　參考答案：B

　　6[單選題]對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是(　　)。

　　參考答案：D

　　參考解析：對于長度為n的線性表，在最壞情況下，冒泡排序需要進行的比較次數(shù)是n(n—1)/2，快速排序需要進行的比較次數(shù)是n(n-1)/2，簡單插入排序需要進行的比較次數(shù)是n(n—1)/2，希爾排序需要進行的比較次數(shù)是0(n1 5)，簡單選擇排序需要進行的比較次數(shù)是n(n-1)/2，堆排序需要進行的比較次數(shù)是0(nl092n)。因此選項D正確。

　　7[單選題]下列排序方法中，最壞情況下比較次數(shù)最少的是(　　)

　　A.冒泡排序B.簡單選擇排序C.直接插入排序D.堆排序

　　參考答案：D

　　參考解析：冒泡排序、簡單選擇排序和直接插入排序法在最壞情況下的比較次數(shù)為n(n-1)/2，而堆排序法在最壞情況下的比較次數(shù)為O(nl092n)。

　　8[單選題]長度為l0的順序表的首地址是從l023開始的，順序表中每個元素的長度為2，在第4個元素前面插入一個元素和刪除第7個元素后，順序表的總長度還是不變。問在執(zhí)行插入和刪除操作前，順序表中第5個元素在執(zhí)行插入和刪除操作后在順序表中的存儲地址是(　　)

　　A.1028B.1029C.1031D.1033

　　參考答案：D

　　參考解析：由于問的是原來順序表中的第5個元素，它在插入操作后變成了第6個元素(因為插入的元素在它前面)。由于刪除的第7個元素在它后面，不會影響它在順序表中的排位。因此在執(zhí)行插入和刪除操作后原先順序表中的第5個元素變成了新的順序表中的第6個元素。再按照線性表的隨機存取地址的計算公式ADD(ai)=ADD(a1)+(i-l)×k計算ADD(a6)=ADD(a1)+(6—1)×2=1023+5×2=1033，因此選項D正確。

　　9[填空題]________是-組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。

　　參考解析：算法

　　10[填空題]請寫出用二分查找法在有序順序表(1，2，3，4，6，8，9，11)中查找3的比較序列________。

　　參考解析：4，2，3

　　【分析】可采用擦去法做這類二分法查找序列的題：每次從序列中找出中間元素，剛開始時是4，由于3比4小，只能存在在4之前的序列中，于是把4以后的序列擦去，只剩下序列(1，2，3)，在重復(fù)以上過程直到查找元素或是序列為空.

　　11[填空題]在最壞情況下，冒泡排序的時間復(fù)雜度為________，簡單插入排序的時間復(fù)雜度為________，希爾排序的時間復(fù)雜度為________，簡單選擇排序的時間復(fù)雜度為________，堆排序的時間復(fù)雜度為________。

　　參考解析：O(n(n-1)/2) O(n(n—1)/2) O(n1.5) O(n(n—1)/2) O(nlog2n)

　　12[單選題]通過相鄰數(shù)據(jù)元素的交換逐步：搿線性表變成有序的排序方法是(　　)。

　　參考答案：A

　　13[單選題]快速排序法屬于(　　)。

　　參考答案：B

　　14[填空題]請寫出用冒泡排序法對序列(5，1，7，3，1，6，9，3，2，7，6)進行第-遍掃描后的中間結(jié)果是________。

　　參考解析：

　　(1，1，5，3，2，6，7，3，6，7，9)【分析】冒泡排序法的基本過程：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小，若前面的元素大于后面的元素，則將他們交換，這樣最大者交換到了表的最后面;然后，從后往前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小若后面的元素小于前面的元素，則將他們交換，這樣最小者交換到了表的最前面;從前往后和從后往前掃描一個來回稱為-遍：對剩下的線性表重復(fù)上述過程，直到剩下的線性表變?yōu)榭諡橹?這樣線性表就變?yōu)橛行蛄恕?/P>

　　現(xiàn)在我們來看看對線性表(5，1，7，3，l，6，9，3，2，7，6)從前往后進行掃描的過程：

　　5>15和l交換位置得到(1，5，7，3，l，6，9，3，2，7，6)

　　5<7不管，繼續(xù)往后掃描，掃描到7

　　7>37和3交換位置得到(1，5，3，7，1，6，9，3，2，7，6)

　　7>17和1交換位置得到(1，5，3，l，7，6，9，3，2，7，6)

　　7>67和6交換位置得到(1，5，3，1，6，7，9，3，2，7，6)

　　7<9不管，繼續(xù)往后掃描，掃描到9

　　9>39和3交挾位置得到(1，5，3，l，6，7，3，9，2，7，6)

　　9>29和2交換位置得到fl，5，3，1，6，7，3，2，9.7，6)

　　9>79和7交換位置得到(1，5，3，1，6，7，3，2，7，9，6)

　　9>69和6交換位置得到(1，5，3，l，6，7，3，2，7，6，9)

　　從前往后掃描結(jié)束，9交換到了線性表的最后。

　　現(xiàn)在我們來看看對剩下的線性表(1，5，3，1，6，7，3，2，7，6)從后往前進行掃描的過程：

　　6<76和7交換位置得到(1，5，3，l，6，7，3，2，6，7)

　　6>2不管，繼續(xù)往前掃描，掃描到2

　　2<32和3交換位置得到(1，5，3，1，6，7，2，3，6，71

　　2<72和7交換位置得到(1，5，3，1，6，2，7，3，6，7)

　　2<62和6交換位置得到(1，5，3，1，2，6，7，3，6，7)

　　2>1不管，繼續(xù)往前掃描，掃描到l

　　l<31和3交換位置得到(1，5，1，3，2，6，7，3，6

　　15[填空題]以下排序技術(shù)中屬于交換類排序法的有________，屬于插入類排序法的有________，屬于選擇類排序法的有________。

　�、�.簡單插入排序

　�、�.冒泡排序

　　Ⅲ.希爾排序

　�、�.堆排序

　　Ⅴ.快速排序

　�、�.簡單選擇排序

　　參考解析：

　�、� Ⅴ

　�、�

　�、� Ⅵ

　　16[填空題]請寫出用冒泡排序法對序列(5，1，7，3，1，6，9，3，2，7，6)進行第一遍掃描后的中間結(jié)果是(　　)。

　　參考解析：

　　(1，1，5，3，2，6，7，3，6，7，9)

　　17[填空題]請寫出用希爾排序法對序列(5，1，7，3，1，6，9，3，2，7，6)進行第一遍掃描后的中間結(jié)果是(　　)。

　　參考解析：

　　(5，l，3，2，1，6，9，7，3，7，6)

　　【分析】希爾排序法的基本思想：將整個無序序列分割成若干小的子序列分別進行插入排序(插入排序：開始線性表中只有第l個元素，然后從線性表的第2個元素開始直到最后一個元素，逐次將其中的每一個元素插入到前面已經(jīng)有序的子表中)。

　　子序列的分割方法：將相隔某個增量h(ht=n/2k(k=1，2，3，…，[10g2n]n為待排序的線性表的長度))的元素構(gòu)成一個子序列。在排序過程中，逐次減小這個增量，最后當(dāng)h減到l時進行一次插入排序，排序完成。

　　按以上分析，第1次分割子序列h=n/2=11/2=5，構(gòu)成的子序列有：5—6、1—9、7—3、3—2、l一7、6(最后一個元素6成單)，每一個序列進行插入排序，結(jié)果為：5—6、l一9、3—7、2—3、l一7、6(最后一個元素6成單)，所以第一遍掃描后的中間結(jié)果是(5，l，3，2，1，6，9，7，3，7，6)。

　　18[填空題]請寫出用簡單選擇排序法對序列(5，l，7，3，l，6，9，3，2，7，6)進行第一遍掃描后的中間結(jié)果是(　　)。

　　參考解析：

　　(1，5，7，3，l，6，9，3，2，7，6)

　　【分析】掃描整個線性表，從中選擇最小的元素，將他交換到袁的最前面;然后對剩下的子表采用同樣的方法，直到子表為空。我們對線性表(5，1，7，3，1，6，9，3，2， 7，6)進行第1遍掃描，可以看出元素1最小，將l和第一個位置上的元素5交換，就得到第1遍掃描的結(jié)果：(1，5，7，3，l，6，9，3，2，7，6)。

　　19[填空題](　　)是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。

　　參考解析：算法

　　20[填空題]算法中各操作之間的執(zhí)行順序稱為(　　)。描述算法的工具通常有(　　)、(　　)、(　　)等。

　　參考解析：算法的控制結(jié)構(gòu)、傳統(tǒng)流程圖、N—S結(jié)構(gòu)化流程圖、算法描述語言

　　21[填空題]在最壞情況下，冒泡排序的時間復(fù)雜度為(　　) ，簡單插入排序的時間復(fù)雜度為(　　)，希爾排序的時間復(fù)雜度為(　　) ，簡單選擇排序的時間復(fù)雜度為(　　) ，堆排序的時間復(fù)雜度為(　　) 。

　　參考解析：O(n(n-1)/2) 、O(n(n—1)/2)、O(n1.5) 、 O(n(n—1)/2)、O(nlog2n)

　　22[填空題]以下排序技術(shù)中屬于交換類排序法的有(　　) ，屬于插入類排序法的有(　　)，屬于選擇類排序法的有(　　)。

　�、�.簡單插入排序

　�、�.冒泡排序

　�、�.希爾排序

　�、�.堆排序

　�、�.快速排序

　　Ⅵ.簡單選擇排序

　　參考解析：Ⅱ Ⅴ 、Ⅰ Ⅲ 、Ⅳ Ⅵ

　　相關(guān)推薦：

　　2015年9月計算機等級考試成績查詢時間通知

　　2015計算機二級公共基礎(chǔ)知識考前沖刺練試題匯總

　　2015計算機二級《公共基礎(chǔ)知識》精選選擇題90道

　　2015計算機等級考試通關(guān)必看:一至四級備考經(jīng)驗