數(shù)據(jù)結(jié)構(gòu)--重修作業(yè)題(1).doc

第一章 緒論一、選擇題 3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ） （A）動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) （B）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) （C）線性結(jié)構(gòu)和非線性結(jié)構(gòu)（D）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 5.算法分析的目的是（）。 （A） 找出數(shù)據(jù)結(jié)構(gòu)的合理性 （B）研究算法中的輸入和輸出的關(guān)系 （C）分析算法的效率以求改進（D）分析算法的易懂性和文檔性 二、判斷題 1.數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。（ ） 2.算法就是程序。（ ） 5.算法的時間復(fù)雜度取決于問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。（ ） 三、填空題 1.數(shù)據(jù)邏輯結(jié)構(gòu)包括_、_、_ 和_四種類型,其中樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_。 2.在線性結(jié)構(gòu)中,第一個結(jié)點_前驅(qū)結(jié)點,其余每個結(jié)點有且只有_個前驅(qū)結(jié)點；最后一個結(jié)點_后續(xù)結(jié)點,其余每個結(jié)點有且只有_個后續(xù)結(jié)點。 3.在樹形結(jié)構(gòu)中,樹根結(jié)點沒有_結(jié)點,其余每個結(jié)點有且只有_個前驅(qū)結(jié)點；葉子結(jié)點沒有_結(jié)點,其余每個結(jié)點的后續(xù)結(jié)點可以_。 4.在圖形結(jié)構(gòu)中,每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以_。 5.線性結(jié)構(gòu)中元素之間存在_關(guān)系,樹形結(jié)構(gòu)中元素之間存在_關(guān)系,圖形結(jié)構(gòu)中元素之間存在_關(guān)系。8.鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比較,主要優(yōu)點是_。 9.設(shè)有一批數(shù)據(jù)元素,為了最快的存儲某元素,數(shù)據(jù)結(jié)構(gòu)宜用_結(jié)構(gòu),為了方便插入一個元素,數(shù)據(jù)結(jié)構(gòu)宜用_結(jié)構(gòu)。 四、算法分析題,求下列算法段的語句頻度及時間復(fù)雜度 for （i=1;i=n;i+） for (j=1;j=i;j+) for ( k=1;ktop=0 （C）ST.top!=m0-1（D）ST.top=m0-15.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是（ ）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,16.循環(huán)隊列用數(shù)組A0,m-1存放其元素值,已知其頭尾指針分別是front和rear則當(dāng)前隊列中的元素個數(shù)是（ ）（A）(rear-front+m)%m （B） rear-front+1 （C）rear-front-1（D）rear-front7.棧和隊列的共同點是（ ）（A） 都是先進后出 （B）都是先進先出（C）只允許在端點處插入和刪除元素（D）沒有共同點9.4個元素a1，a2，a3和a4依次通過一個棧，在a4進棧前，棧的狀態(tài)，則不可能的出棧序是（）(A)a4，a3，a2，a1(B)a3，a2，a4，a1 (C)a3，a1，a4，a2(D)a3，a4，a2，a110.以數(shù)組Q0.m1存放循環(huán)隊列中的元素，變量rear和qulen分別指示循環(huán)隊列中隊尾元素的實際位置和當(dāng)前隊列中元素的個數(shù)，隊列第一個元素的實際位置是（）(A)rearqulen(B)rearqulenm(C)mqulen (D)1（rearmqulen）% m二、填空題1.棧的特點是_,隊列的特點是_。2.線性表、棧和隊列都是_結(jié)構(gòu),可以在線性表的_位置插入和刪除元素，對于棧只能在_插入和刪除元素，對于隊列只能在_插入元素和_刪除元素。3.一個棧的輸入序列是12345,則棧有輸出序列12345是_。(正確/錯誤)4.設(shè)棧S和隊列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過一個棧，一個元素出棧后即進入隊列Q，若6個元素出隊列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該容納_個元素。三、算法設(shè)計題 1.鏈棧的出棧入棧算法。2.順序循環(huán)隊列的出隊入隊算法.第四章 串和數(shù)組 一、選擇題 1.下列關(guān)于串的敘述中，正確的是（ ）(A)一個串的字符個數(shù)即該串的長度 (B)一個串的長度至少是1(C)空串是由一個空格字符組成的串 (D)兩個串S1和S2若長度相同，則這兩個串相等2. 二維數(shù)組M的元素是4個字符(每個字符占一個存儲單元)組成的串,行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行存儲時元素M35的起始地址與M按列存儲時元素( ) 的起始地址相同。（A）M24（B）M34（C）M35（D）M443.數(shù)組A810中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內(nèi),存放該數(shù)組至少需要的單元數(shù)是（ ）。（A）80（B）100（C）240（D）2704.數(shù)組A810中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內(nèi),該數(shù)組按行存放時,元素A74的起始地址為（ ）。（A）SA+141（B）SA+144（C）SA+222（D）SA+2255.數(shù)組A810中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內(nèi),該數(shù)組按列存放時,元素A47的起始地址為（ ）。（A）SA+141（B）SA+180（C）SA+222（D）SA+2256.稀疏矩陣一般的壓縮存儲方法有兩種,即（ ）。（A） 二維數(shù)組和三維數(shù)組（B）三元組和散列（C）三元組和十字鏈表 （D）散列和十字鏈表7.若采用三元組壓縮技術(shù)存儲稀疏矩陣,只要把每個元素的行下標(biāo)和列下標(biāo)互換,就完成了對該矩陣的轉(zhuǎn)置運算,這種觀點（ ）。（A）正確（B）錯誤8.設(shè)矩陣A是一個對稱矩陣,為了節(jié)省存儲,將其下三角部分按行序存放在一維數(shù)組B1,n(n-1)/2中,對下三角部分中任一元素ai,j(i=j),在一組數(shù)組B的下標(biāo)位置k的值是（ ）。（A）i(i-1)/2+j-1（B）i(i-1)/2+j（C）i(i+1)/2+j-1 (D)i(i+1)/2+j4.串是一種特殊的線性表,其特殊性表現(xiàn)在（ ）(A)可以順序存儲 (B)數(shù)據(jù)元素是一個字符(C)可以鏈?zhǔn)酱鎯?(D)數(shù)據(jù)元素可以是多個字符5設(shè)串S1=ABCDEFG,s2=PQRST,函數(shù)CONCAT（X，Y）返回X和Y串的連接串，SUBSTR（S，I，J）返回串S從序號I開始的J個字符組成的字串，LENGTH（S）返回串S的長度，則CONCAT（SUBSTR（S1，2，LENGTH（S2），SUBSTR（S1，LENGTH（S2），2）的結(jié)果串是（ ）（A）BCDEF (B) BCDEFG (C)BCPQRST (D)BCDEFEF 2、 填空題1. 己知二維數(shù)組Amn采用行序為主方式存儲,每個元素占k個存儲單元,并且第一個元素的存儲地址是LOC(A00),則A00的地址是_。2.二維數(shù)組A1020采用列序為主方式存儲,每個元素占一個存儲單元,并且A00的存儲地址是200,則A612的地址是_。3.有一個10階對稱矩陣A,采用壓縮存儲方式(以行序為主,且A00=1),則A85的地址是_。4.設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組S1.n*(n+1)/2中,若按行序為主存儲,則Aij對應(yīng)的S中的存儲位置是_。5.若A是按列序為主序進行存儲的46的二維數(shù)組,其每個元素占用3個存儲單元,并且A00的存儲地址為1000,元素A13的存儲地址為_,該數(shù)組共占用_個存儲單元。三、算法設(shè)計 1.串的模式匹配算法。第五章 樹與二叉樹3.二叉樹的前序遍歷序列中,任意一個結(jié)點均處在其子女結(jié)點的前面,這種說法（ ）(A)正確 (B)錯誤 （C）不同情況下答案不確定4.由于二叉樹中每個結(jié)點的度最大為2,所以二叉樹是一種特殊的樹,這種說法（ ） 2. 正確 （B）錯誤 （C）不同情況下答案不確定5.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點,則此類二叉樹中所包含的結(jié)點數(shù)至少為（ ）。（A）2h （B）2h-1（C）2- 9 -3+1（D）h+16.已知某二叉樹的后序遍歷序列是dabec。中序遍歷序列是debac,它的前序遍歷序列是（ ）。（A）acbed （B）decab（C）deabc （D）cedba7.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹,那么T中結(jié)點的前序就是T2中結(jié)點的（ ）（A）前序（B）中序（C）后序（D）層次序8.某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh,中序遍歷的結(jié)點訪問順序是dgbaechf,則其后序遍歷的結(jié)點訪問順序是（ ）。（A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca9.二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法（ ）（A）正確（B）錯誤（C）不同情況下答案不確定10.按照二叉樹的定義,具有3個結(jié)點的二叉樹有（ ）種。（A）3（B）4（C）5（D）611.在一非空二叉樹的中序遍歷序列中,根結(jié)點的右邊（ ）（A）只有右子樹上的所有結(jié)點（B）只有右子樹上的部分結(jié)點（C）只有左子樹上的部分結(jié)點（D）只有左子樹上的所有結(jié)點12.樹最適合用來表示（ ）。（A）有序數(shù)據(jù)元素（B）無序數(shù)據(jù)元素（C）元素之間具有分支層次關(guān)系的數(shù)據(jù)（D）元素之間無聯(lián)系的數(shù)據(jù)13.任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序（ ）（A）不發(fā)生改變（B）發(fā)生改變（C）不能確定D.以上都不對15.對一個滿二叉樹,m個樹葉,n個結(jié)點,深度為h,則（ ）（A）n=h+m （B）h+m=2n（C）m=h-1（D）n=2h-1 16.如果某二叉樹的前序為stuwv,中序為uwtvs,那么該二叉樹的后序為（ ）（A）uwvts （B）vwuts（C）wuvts （D）wutsv17.具有五層結(jié)點的二叉平衡樹至少有（ ）個結(jié)點。（A）10（B）12（C）15（D）173. 已知一棵樹邊的集合為，,，畫出這棵樹，并回答下列問題： 哪個結(jié)點是根結(jié)點？ 1 哪些結(jié)點是葉子結(jié)點？ 2 哪個結(jié)點是結(jié)點 G 的雙親結(jié)點？ 3 哪些結(jié)點是結(jié)點 G 的祖先結(jié)點？ 4 哪些結(jié)點是結(jié)點 G 的孩子結(jié)點？ 5 哪些結(jié)點是結(jié)點 E 的子孫結(jié)點？ 6 哪些結(jié)點是結(jié)點 E 的兄弟結(jié)點？哪些是結(jié)點 F 的兄弟結(jié)點？ 7 結(jié)點 B 和 N 的層次分別是多少？8 樹的深度是多少？1) 以結(jié)點 C 為根的子樹的深度是多少？4. 已知一棵二叉樹的先序、中序和后序序列如下，其中各有一部分未給出其值，請構(gòu)造出該二叉樹。 先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C_ _BHGJI_ _5. 已知一棵樹的度為4，其中度為4的結(jié)點的數(shù)目為3，度為3的結(jié)點的數(shù)目為4，度為2的結(jié)點的數(shù)目為54.按照下列給定二叉樹的先序遍歷序列、中序遍歷和后序遍歷序列，分別構(gòu)造出二叉樹。 1 先序遍歷序列： EBADCFHGIKJ 中序遍歷系列： ABCDEFGHIJK 2 中序遍歷序列： ACBGEDF 后序遍歷序列： ABCDEFG 3 度為1的結(jié)點的數(shù)目為2，請求出該樹中的葉子結(jié)點的數(shù)目。二、判斷題 1.二叉樹中任何一個結(jié)點的度都是2。（ ）2.由二叉樹結(jié)點的先根序列和后根序列可以唯一地確定一棵二叉樹。（ ）3.一棵哈夫曼樹中不存在度為1的結(jié)點。（ ）4.平衡二叉排序樹上任何一個結(jié)點的左、右子樹的高度之差的絕對值不大于2（ ）6. 三、填空題 3.若結(jié)點A有三個兄弟(包括A本身),并且B是A的雙親結(jié)點,B的度是_4.若一棵具有n個結(jié)點的二叉樹采用標(biāo)準(zhǔn)鏈接存儲結(jié)構(gòu),那么該二叉樹所有結(jié)點共有_個空指針域。5.已知二叉樹的前序序列為ABDEGCFHIJ,中序序列為DBGEAHFIJC,寫出后序序列_。6.已知二叉樹的后序序列為FGDBHECA,中序序列為BFDGAEHC ,并寫出前序序列_。7.找出滿足下列條件的二叉樹1）先序和中序遍歷，得到的結(jié)點訪問順序一樣。_2）后序和中序遍歷，得到的結(jié)點訪問順序一樣。_3）先序和后序遍歷，得到的結(jié)點訪問順序一樣。_9.一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點有_個。10.含有100個結(jié)點的樹有_條邊。四、問答題 4.有七個帶權(quán)結(jié)點,其權(quán)值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~結(jié)點構(gòu)造一棵哈夫曼樹(請按照每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造,并計算出帶權(quán)路徑長度WPL及該樹的結(jié)點總數(shù)。5.有一電文共使用五種字符a,b,c,d,e,其出現(xiàn)頻率依次為4,7,5,2,9。(1)試畫出對應(yīng)的編碼哈夫曼樹(要求左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán))。(2)求出每個字符的晗夫曼編碼。(3)求出傳送電文的總長度。(4)并譯出編碼系列1100011100010101的相應(yīng)電文。第七章 圖 一、判斷題 1.一個無向圖的鄰接矩陣中各非零元素之和與圖中邊的條數(shù)相等。（ ） 2.一個有向圖的鄰接矩陣中各非零元素之和與圖中邊的條數(shù)相等。（ ） 3.一個對稱矩陣一定對應(yīng)著一個無向圖。（ ） 4.一個有向圖的鄰接矩陣一定是一個非對稱矩陣。（ ） 二、選擇題 1.在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的（ ）倍。 （A）1/2（B）1（C）2（D）42.在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。 （A）1/2（B）1（C）2（D）43.一個有n個頂點的無向圖最多有（ ）條邊。 （A）n （B）n(n-1)（C）n(n-1）/2（D）2n4.具有4個頂點的無向完全圖有（ ）條邊。 （A）6（B）12（C）16（D）205.具有6個頂點的無向圖至少應(yīng)有（ ）條邊才能確保是一個連通圖。 （A）5（B）6（C）7（D）86.在一個具有n個頂點的無向圖中,要連通全部頂點至少需要（ ）條邊。 （A）n （B）n+1（C）n-1（D）n/27.對于一個具有n個頂點的無向圖,若采用鄰接矩陣表示,則該矩陣的大小（ ） （A）n （B）(n-1) 2（C）n-1 （D）n28.對于一個具有n個頂點和e條邊的無向圖,若采用鄰接表表示,則表頭向量的大小為（ ），所有鄰接表中的結(jié)點總數(shù)是（ ）。 （A）n （B）n+1（C）n-1（D）n+e（A）e/2（B）e（C）2e （D）n+e9.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）。 （A）先序遍歷（B）中序遍歷（C）后序遍歷（D）按層遍歷 10.采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的（ ）。 （A）先序遍歷（B）中序遍歷（C）后序遍歷（D）按層遍歷 11.判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?還可以利用（ ）.（A）求關(guān)鍵路徑的方法（B）求最短路徑的Dijkstm方法 （C）寬度優(yōu)先遍歷算法（D）深度優(yōu)先遍歷算法 12.用Prim算法求下列連通的帶權(quán)圖的最小代價生成樹，在算法執(zhí)行的某刻，已選取的頂點集合U1，2，5，邊的集合TE（1，2），（2，5），要選取下一條權(quán)值最小的邊，應(yīng)當(dāng)從（ ）組中選取。 (A)（1，4），（3，4），（3，5），（2，5）(B)（5，4），（5，3），（5，6） (C)（1，2），（2，3），（3，5） (D)（3，4），（3，5），（4，5），（1，4） 三、填空題 1.n個頂點的連通圖至少_條邊。 2.在一個無環(huán)有向圖G中，若存在一條從頂點i到頂點j的弧，則在頂點的拓?fù)湫蛄兄?，頂點i與頂點j的先后次序是_。 3.在一個無向圖的鄰接表中，若表結(jié)點的個數(shù)是m，則圖中邊的條數(shù)是_條。 4. 如果從一個頂點出發(fā)又回到該頂點，則此路徑叫做_。 5.如果從一無向圖的任意頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是_。 6.若采用鄰接表的存儲結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類似于二叉樹的_遍歷。 7. 一個連通圖的生成樹是該圖的_連通子圖。若這個連通圖有n個頂點, 則它的生成樹有_條邊。 第八章 查找 一、判斷題 1.用二分查找法對一個順序表進行查找，這個順序表可以是按各鍵值排好序的，也可以是沒有按鍵值排好序的。（ ） 3.哈希表的定義函數(shù)H（key）=key%p(p=m)這種方法是直接定址法。（ ） 2、 填空題 1.順序查找法的平均查找長度為_，二分查找法的平均查找長度為_，分塊查找法(以順序查找確定塊)的平均查找長度為_，分塊查找法(以二分查找確定塊)的平均查找長度為_。 2.在各種查找方法中,平均查找長度與結(jié)點個數(shù)n無關(guān)的查法方法是_3.二分查找的存儲結(jié)構(gòu)僅限于_,且是_。 4.在分塊查找方法中,首先查找_,然后再查找相應(yīng)的_。 5.長度為255的表,采用分塊查找法,每塊的最佳長度是_。 7.假設(shè)在有序線性表A1.20上進行二分查找,則比較一次查找成功的結(jié)點數(shù)為_,則比較二次查找成功的結(jié)點數(shù)為_,則比較三次查找成功的結(jié)點數(shù)為_,則比較四次查找成功的結(jié)點數(shù)為_,則比較五次查找成功的結(jié)點數(shù)為_,平均查找長度為_。 9.己知一個有序表為(12,18,20,25,29,32,40,62,83,90,95,98),當(dāng)二分查找值為29和90的元素時,分別需要_次和_次比較才能查找成功；若采用順序查找時,分別需要_次和_次比較才能查找成功。 三、選擇題 1.順序查找法適合于存儲結(jié)構(gòu)為（ ）的線性表。 （A）散列存儲（B）順序存儲或鏈接存儲（C）壓縮存儲（D）索引存儲 2.對線性表進行二分查找時,要求線性表必須（ ）。 （A）以順序方式存儲（B）以鏈接方式存儲 （C）以順序方式存儲,且結(jié)點按關(guān)鍵字有序排序 （D）以鏈接方式存儲,且結(jié)點按關(guān)鍵字有序排序 3.采用順序查找方法查找長度為n的線性表時,每個元素的平均查找長度為（ ） （A）n （B）n/2（C）(n+1)/2（D）(n-1)/24.采用二分查找方法查找長度為n的線性表時,每個元素的平均查找長度為（ ） （A）O(n2)（B）O(log2n)（C）O(n)（D）O(log2n-1)5.二分查找和二叉排序樹的時間性能（ ）。 （A）相同? （B）不相同? （C）無法比較 6.有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)二分查找值為82的結(jié)點時,（ ）次比較后查找成功。 （A）1（B）2（C）4（D）88.有一個長度為12的有序表,按二分查找法對該表進行查找,在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（? ） （A）35/12（B）37/12（C）39/12（D）43/129.采用分塊查找時,若線性表中共有625個元素,查找每個元素的概率相同,假設(shè)采用順序查找來確定結(jié)點所在的塊時,每塊應(yīng)分（ ）個結(jié)點最佳。 （A）10（B）25（C）6（D）62510.如果要求一個線性表既能較快地查找,又能適應(yīng)動態(tài)變化的要求,可以采用（ ）查找方法。 （A）分塊（B）順序（C）二分（D）散列 第九章 排序 一、選擇題 1.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄得初始排列次序無關(guān)的是（ ） （A）希爾排序 （B）起泡排序 （C）插入排序 （D）選擇排序 2.設(shè)有1000個無序的元素,希望用最快的速度挑選出其中前10個最大的元素,最好（ ）排序法。 （A）起泡排序（B）快速排序（C）堆排序（D）基數(shù)排序 3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 4.一組記錄的排序碼為(46,79,56,38,40,84),則利用堆排序的方法建立的初始推為（ ）。 （A）79,46,56,38,40,80 （B）84,79,56,38,40,46（C）84,79,56,46,40,38 （D）84,56,79,40,46,385.一組記錄的關(guān)鍵碼為(46,79,56,38,40,84),則利用快速排序的方法,以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。 （A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,56,79,84（D）40,38,46,84,56,796.一組記錄的排序碼為(25,48,16,35,79,82,23,40,36,72),其中含有5個長度為2的有序表,按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為（ ）。 （A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72（C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,827.排序方法中,從未排序序列中依次取出元素與己排序序列(初始時為空)中的元素進行比較,將其放入己排序序列的正確位置上的方法,稱為（ ） （A）希爾排序（B）起泡排序（C）插入排序（D）選擇排序 8.排序方法中,從未排序序列中挑選元素并將其依次放入己排序序列(初始為空)的一端的方法,稱為（ ） （A）希爾排序（B）歸并排序（C）插入排序（D）選擇排序 9.用某種排序方法對線性表(25,84,21,47,15,27,68,35,20)進行排序時,元素序列的變化情況如下: (1)25,84,21,47,15,27,68,35,20 ?(2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 ?(4)15,20,21,25,27,35,47,68,845則所采用的排序方法是（ ）。 （A）選擇排序（B）希爾排序（C）歸并排序（D）快速排序 10.下述幾種排序方法中,平均查找長度最小的是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 11.下述幾種排序方法中,要求內(nèi)存量最大的是（ ）。 （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 12.快速排序方法在情況下最不利于發(fā)揮其長處。( )（A）要排序的數(shù)據(jù)量太大? （B）要排序的數(shù)據(jù)中含有多個相同值 （C）要排序的數(shù)據(jù)已基本有序（D）要排序的數(shù)據(jù)個數(shù)為奇數(shù) 13.設(shè)有10000個元素組成的無序序列,希望盡快挑選出其中前10個最大值元素,在不改變已有算法結(jié)構(gòu)的前提下,以下幾種內(nèi)排序算法中(? ?)最合適。 (A)選擇排序法(B)快速排序法(C)堆排序法(D)冒泡排序法。 14.下列四種排序方法中，不穩(wěn)定的方法是（ ） (A)直接插入排序 (B)冒泡排序 (C)歸并排序(D)直接選擇排序 二、判斷題 1.用直接選擇排序方法分別對序列S1（1，2，3，4，5，6，7）和序列S2（7，5，3，2，4，1， 6）進行排序，兩者的比較次數(shù)不相同。（ ） 2.快速排序是所有排序中速度最快的一種。（ ） 3.堆排序是直到最后一趟排序結(jié)束之前所有元素才能在其最終的位置上。（ ） 三、填空題 1.試五種排序方法與對應(yīng)的操作聯(lián)系起來: (A)歸并排序 _(B)選擇排序 _ (C)冒泡排序 _ (D)插入排序 _(E)快速排序_ (1)從待排序序列中依次取出元素與己排序序列中的元素作比較將其放入己排序序列中的正確的位置上。 (2)從待排序序列中挑選元素,并將其放入己排序序列的一端。 (3)依次將相鄰的有序表合并成一個有序表。 (4)每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間,其中左區(qū)間中元素的鍵