點(diǎn)擊查看：2015年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考點(diǎn)測(cè)試題匯總
排序技術(shù)
1[單選題]對(duì)長(zhǎng)度n的線性表排序，在最壞情況下，比較次數(shù)不是n(n一1)/2的排序方法是( )。
參考答案：D
參考解析：排序技術(shù)有：①交換類排序法(冒泡排序法、快速排序法);②插入類排序法(簡(jiǎn)單插入排序、希爾排序);③選擇類排序法(簡(jiǎn)單選擇排序法、堆排序法)。在最壞情況下，希爾排序需要的比較次數(shù)是O(nl.5)、堆排序需要的比較次數(shù)是O(nlog2n)、其它排序方法需要的比較次數(shù)都是n(n.1)/2。因此本題的正確答案是D。
2[單選題]冒泡排序在最壞情況下的比較次數(shù)是( )。
參考答案：C
參考解析：對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，冒泡排序需要進(jìn)行的比較次數(shù)是n(n一1)/2。因此本題的正確答案是C。
3[單選題]通過相鄰數(shù)據(jù)元素的交換逐步：搿線性表變成有序的排序方法是( )
A.冒泡排序法B.簡(jiǎn)單選擇排序法C.簡(jiǎn)單插入排序法D.希爾排序法
參考答案：A
4[單選題]冒泡排序在最壞情況下的比較次數(shù)是( )
A.n(n+1)/2B.nlog2nC.n(n-1)/2D.n/2
參考答案：C
參考解析：對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，冒泡排序需要進(jìn)行的比較次數(shù)是n(n-1)/2。因此本題的正確答案是C。
5[單選題]快速排序法屬于( )
A.選擇類排序法B.交換類排序法C.插入類排序法D.歸并類排序法
參考答案：B
6[單選題]對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是( )。
參考答案：D
參考解析：對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，冒泡排序需要進(jìn)行的比較次數(shù)是n(n—1)/2，快速排序需要進(jìn)行的比較次數(shù)是n(n-1)/2，簡(jiǎn)單插入排序需要進(jìn)行的比較次數(shù)是n(n—1)/2，希爾排序需要進(jìn)行的比較次數(shù)是0(n1 5)，簡(jiǎn)單選擇排序需要進(jìn)行的比較次數(shù)是n(n-1)/2，堆排序需要進(jìn)行的比較次數(shù)是0(nl092n)。因此選項(xiàng)D正確。
7[單選題]下列排序方法中，最壞情況下比較次數(shù)最少的是( )
A.冒泡排序B.簡(jiǎn)單選擇排序C.直接插入排序D.堆排序
參考答案：D
參考解析：冒泡排序、簡(jiǎn)單選擇排序和直接插入排序法在最壞情況下的比較次數(shù)為n(n-1)/2，而堆排序法在最壞情況下的比較次數(shù)為O(nl092n)。
8[單選題]長(zhǎng)度為l0的順序表的首地址是從l023開始的，順序表中每個(gè)元素的長(zhǎng)度為2，在第4個(gè)元素前面插入一個(gè)元素和刪除第7個(gè)元素后，順序表的總長(zhǎng)度還是不變。問在執(zhí)行插入和刪除操作前，順序表中第5個(gè)元素在執(zhí)行插入和刪除操作后在順序表中的存儲(chǔ)地址是( )
A.1028B.1029C.1031D.1033
參考答案：D
參考解析：由于問的是原來順序表中的第5個(gè)元素，它在插入操作后變成了第6個(gè)元素(因?yàn)椴迦氲脑卦谒懊?。由于刪除的第7個(gè)元素在它后面，不會(huì)影響它在順序表中的排位。因此在執(zhí)行插入和刪除操作后原先順序表中的第5個(gè)元素變成了新的順序表中的第6個(gè)元素。再按照線性表的隨機(jī)存取地址的計(jì)算公式ADD(ai)=ADD(a1)+(i-l)×k計(jì)算ADD(a6)=ADD(a1)+(6—1)×2=1023+5×2=1033，因此選項(xiàng)D正確。
9[填空題]________是-組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。
參考解析：算法
10[填空題]請(qǐng)寫出用二分查找法在有序順序表(1，2，3，4，6，8，9，11)中查找3的比較序列________。
參考解析：4，2，3
【分析】可采用擦去法做這類二分法查找序列的題：每次從序列中找出中間元素，剛開始時(shí)是4，由于3比4小，只能存在在4之前的序列中，于是把4以后的序列擦去，只剩下序列(1，2，3)，在重復(fù)以上過程直到查找元素或是序列為空.
11[填空題]在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為________，簡(jiǎn)單插入排序的時(shí)間復(fù)雜度為________，希爾排序的時(shí)間復(fù)雜度為________，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為________，堆排序的時(shí)間復(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[填空題]請(qǐng)寫出用冒泡排序法對(duì)序列(5，1，7，3，1，6，9，3，2，7，6)進(jìn)行第-遍掃描后的中間結(jié)果是________。
參考解析：
(1，1，5，3，2，6，7，3，6，7，9)【分析】冒泡排序法的基本過程：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小，若前面的元素大于后面的元素，則將他們交換，這樣最大者交換到了表的最后面;然后，從后往前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個(gè)元素的大小若后面的元素小于前面的元素，則將他們交換，這樣最小者交換到了表的最前面;從前往后和從后往前掃描一個(gè)來回稱為-遍：對(duì)剩下的線性表重復(fù)上述過程，直到剩下的線性表變?yōu)榭諡橹?這樣線性表就變?yōu)橛行蛄恕?/P>
現(xiàn)在我們來看看對(duì)線性表(5，1，7，3，l，6，9，3，2，7，6)從前往后進(jìn)行掃描的過程：
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)在我們來看看對(duì)剩下的線性表(1，5，3，1，6，7，3，2，7，6)從后往前進(jìn)行掃描的過程：
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ù)中屬于交換類排序法的有________，屬于插入類排序法的有________，屬于選擇類排序法的有________。
Ⅰ.簡(jiǎn)單插入排序
�、�.冒泡排序
�、�.希爾排序
�、�.堆排序
�、�.快速排序
Ⅵ.簡(jiǎn)單選擇排序
參考解析：
�、� Ⅴ
�、�
�、� Ⅵ
16[填空題]請(qǐng)寫出用冒泡排序法對(duì)序列(5，1，7，3，1，6，9，3，2，7，6)進(jìn)行第一遍掃描后的中間結(jié)果是( )。
參考解析：
(1，1，5，3，2，6，7，3，6，7，9)
17[填空題]請(qǐng)寫出用希爾排序法對(duì)序列(5，1，7，3，1，6，9，3，2，7，6)進(jìn)行第一遍掃描后的中間結(jié)果是( )。
參考解析：
(5，l，3，2，1，6，9，7，3，7，6)
【分析】希爾排序法的基本思想：將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序(插入排序：開始線性表中只有第l個(gè)元素，然后從線性表的第2個(gè)元素開始直到最后一個(gè)元素，逐次將其中的每一個(gè)元素插入到前面已經(jīng)有序的子表中)。
子序列的分割方法：將相隔某個(gè)增量h(ht=n/2k(k=1，2，3，…，[10g2n]n為待排序的線性表的長(zhǎng)度))的元素構(gòu)成一個(gè)子序列。在排序過程中，逐次減小這個(gè)增量，最后當(dāng)h減到l時(shí)進(jìn)行一次插入排序，排序完成。
按以上分析，第1次分割子序列h=n/2=11/2=5，構(gòu)成的子序列有：5—6、1—9、7—3、3—2、l一7、6(最后一個(gè)元素6成單)，每一個(gè)序列進(jìn)行插入排序，結(jié)果為：5—6、l一9、3—7、2—3、l一7、6(最后一個(gè)元素6成單)，所以第一遍掃描后的中間結(jié)果是(5，l，3，2，1，6，9，7，3，7，6)。
18[填空題]請(qǐng)寫出用簡(jiǎn)單選擇排序法對(duì)序列(5，l，7，3，l，6，9，3，2，7，6)進(jìn)行第一遍掃描后的中間結(jié)果是( )。
參考解析：
(1，5，7，3，l，6，9，3，2，7，6)
【分析】掃描整個(gè)線性表，從中選擇最小的元素，將他交換到袁的最前面;然后對(duì)剩下的子表采用同樣的方法，直到子表為空。我們對(duì)線性表(5，1，7，3，1，6，9，3，2， 7，6)進(jìn)行第1遍掃描，可以看出元素1最小，將l和第一個(gè)位置上的元素5交換，就得到第1遍掃描的結(jié)果：(1，5，7，3，l，6，9，3，2，7，6)。
19[填空題]( )是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。
參考解析：算法
20[填空題]算法中各操作之間的執(zhí)行順序稱為( )。描述算法的工具通常有( )、( )、( )等。
參考解析：算法的控制結(jié)構(gòu)、傳統(tǒng)流程圖、N—S結(jié)構(gòu)化流程圖、算法描述語言
21[填空題]在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為( ) ，簡(jiǎn)單插入排序的時(shí)間復(fù)雜度為( )，希爾排序的時(shí)間復(fù)雜度為( ) ，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為( ) ，堆排序的時(shí)間復(fù)雜度為( ) 。
參考解析：O(n(n-1)/2) 、O(n(n—1)/2)、O(n1.5) 、 O(n(n—1)/2)、O(nlog2n)
22[填空題]以下排序技術(shù)中屬于交換類排序法的有( ) ，屬于插入類排序法的有( )，屬于選擇類排序法的有( )。
Ⅰ.簡(jiǎn)單插入排序
�、�.冒泡排序
�、�.希爾排序
�、�.堆排序
�、�.快速排序
�、�.簡(jiǎn)單選擇排序
參考解析：Ⅱ Ⅴ 、Ⅰ Ⅲ 、Ⅳ Ⅵ
相關(guān)推薦：
2015年9月計(jì)算機(jī)等級(jí)考試成績(jī)查詢時(shí)間通知
2015計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考前沖刺練試題匯總
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |
