(山東科技大學(xué))PTA數(shù)據(jù)結(jié)構(gòu)答案與解析-363

PTA數(shù)據(jù)結(jié)構(gòu)部分答案與解析樹和二叉樹作業(yè)二叉樹.判斷題1-1某二叉樹的后序和中序遍歷序列正好一樣，則該二叉樹中的任何結(jié)點一定都無右孩子。 （2分）解析：略，分析同1-6答案：T1-2某二叉樹的后序和中序遍歷序列正好一樣，則該二叉樹中的任何結(jié)點一定都無左孩子。 （2分）解析：略，分析同1-6答案：F1-3存在一棵總共有2016個結(jié)點的二叉樹，其中有16個結(jié)點只有一個孩子。（3分）解析：這里只說了是二叉樹，沒說是什么形狀的，所以錯誤答案：F作者：何欽銘單位：浙江大學(xué)1-4若A和B都是一棵二叉樹的葉子結(jié)點，則存在這樣的二叉樹，其前序遍歷序列為 ...A...B... ,而中序遍歷序列為…B...A... o（2分）解析：答案：F1-51-5若一個結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該樹的前序遍歷序列中的最后一個結(jié)點。 (2分)解析：畫圖分析即可，考慮只有兩個節(jié)點的無右子樹的二叉樹，中序遍歷的最后一個節(jié)點是根節(jié)點，而根節(jié)點在前序遍歷中一定是在開頭的。答案：F1-6某二叉樹的前序和中序遍歷序列正好一樣，則該二叉樹中的任何結(jié)點一定都無左孩子。 (2分)解析：假如存在左孩子，那么前序遍歷的第一個元素肯定不等于中序遍歷的第一個元素。我們分析第一層，假設(shè)根節(jié)點的左子樹不存在，那么總算前序遍歷和中序遍歷結(jié)果相等了，然后我們判斷根節(jié)點的右子樹部分，發(fā)現(xiàn)還是要保證左子樹不存在的。遞歸分析一定沒有左孩子的。答案：T作者：DS課程組單位：浙江大學(xué)1-7已知一棵二叉樹的先序遍歷結(jié)果是 ABC,則CAB不可能是中序遍歷結(jié)果。 (2分)解析：知道中序遍歷和先序遍歷，是可以畫出樹來的。如果不是很會這種方法，反正只有三個節(jié)點，大可以畫圖舉例。可得沒有樹滿足先序是ABC,中序是CAB的。我們這樣去分析：由先序遍歷可得 A是根節(jié)點；由中序遍歷可得C是左孩子，B是右孩子，而先序遍歷中B是左孩子，C是右孩子，矛盾，所以不可能滴答案：F.單選題2-1*如果一棵非空k(k>2)叉樹T中每個非葉子結(jié)點都有 k個孩子，則稱T為正則k叉樹。若T的高度為h(單結(jié)點的樹h=1)，則T的結(jié)點數(shù)最多為：(3分).( )/(k-1).( )/(k-1).(砂l(fā)_)/(k-1).以上課而是1解析：將k=2帶入，套用二叉樹的結(jié)點樹結(jié)論，發(fā)現(xiàn)A為正確形式答案：A2-2*如果一棵非空k(k>2)叉樹T中每個非葉子結(jié)點都有 k個孩子，則稱T為正則k叉樹。若T的高度為h(單結(jié)點的樹h=1)，則T的結(jié)點數(shù)最少為：(3分).( )/(k-1)+1.(砂)/(k-1)-1矽-13.4.kh解析：這道題我不知道怎么正確推導(dǎo)答案，不過這題可以舉一個正確的二叉樹的例子，帶答案用排除法做答案：D2-3要使一棵非空二叉樹的先序序列與中序序列相同，其所有非葉結(jié)點須滿足的條件是： （2分）.只有左子樹.只有右子樹.結(jié)點的度均為1.結(jié)點的度均為2解析：略答案：B2-4同層的結(jié)點是:已知一棵二叉樹的樹形如下圖所示，其后序序列為 {e,a,c,b,d,g,f}。樹中與結(jié)點a同層的結(jié)點是:（3分）cdfg解析：模擬一遍求解即可答案：B單位：浙江大學(xué)2-5在下述結(jié)論中，正確的是： （2分）①只有2個結(jié)點的樹的度為1;②二叉樹的度為2;③二叉樹的左右子樹可任意交換；④在最大堆（大頂堆）中，從根到任意其它結(jié)點的路徑上的鍵值一定是按非遞增有序排列的.①④.②④.①②③.②③④解析：二叉樹度數(shù)不一定為 2,比如空二叉樹答案：A單位：浙江大學(xué)2-6若一棵二叉樹的后序遍歷序列是 ｛1,3,2,6,5,7,4｝，中序遍歷序列是｛1,2,3,4,5,6,7｝，則下列哪句是錯的？ (3分).這是一棵完全二叉樹.2是1和3的父結(jié)點.這是一棵二叉搜索樹.7是5的父結(jié)點解析：根據(jù)后序遍歷與中序遍歷建樹判斷即可答案：A單位：浙江大學(xué)2-7如果一棵非空k(k>2)叉樹T中每個非葉子結(jié)點都有k個孩子，則稱T為正則k叉樹。若T有m個非葉子結(jié)點，則T的葉子結(jié)點個數(shù)為：(3分)mkm(k-1)m(k-1)+1m(k-1)-1解析：n=B+1=mk+1n=n()+rifeB代表分支數(shù)，n代表結(jié)點數(shù)，聯(lián)立上邊二式可得正確答案，故選C答案：C單位：浙江大學(xué)2-8有一個四叉樹，度2的結(jié)點數(shù)為2,度3的結(jié)點數(shù)為3,度4的結(jié)點數(shù)為4。問該樹的葉結(jié)點個數(shù)是多少？ (2分)1.10122021解析：根據(jù)題意隨便畫一種符合題意的圖即可判斷，也可以通過公式推導(dǎo)。n= +nj-Fns+ng+nB+1= +2儂B代表分支數(shù)，n代表總結(jié)點數(shù)，將上邊式子聯(lián)立，然后帶入題目中數(shù)據(jù)，可得

答案：D2-9門）=劭1+2n3+1以一］若一棵二叉樹的前序遍歷序列是 ｛4,2,1,3,6,5,7｝，中序遍歷序列是｛1,2,3,4,5,6,7｝，則下列哪句是錯的？ （3分）.這是一棵完全二叉樹.所有的奇數(shù)都在葉子結(jié)點上.這是一棵二叉搜索樹.2是5的父結(jié)點解析：根據(jù)前序，中序遍歷可以建出圖來，然后根據(jù)圖來判斷即可答案：D2-10按照二叉樹的定義，具有3個結(jié)點的二叉樹有幾種？ （2分）1.3456解析：畫圖枚舉即可，這里問二叉樹種類不考慮二叉樹節(jié)點值的不同。答案：C2-11任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序 （2分）.發(fā)生改變.不發(fā)生改變.不能確定.以上都不對解析：他們都是左-右，因為問的是相對次序，根節(jié)點插在哪里無所謂的答案：B2-12二叉樹中第5層（根的層號為1）上的結(jié)點個數(shù)最多為：（2分）.8151632解析：答案：C2-13友=2-13友=25T=16TOC\o"1-5"\h\z先序遍歷圖示二叉樹的結(jié)果為 （2分）A, B, C,D, H,E,I, F, GA, B, D,H, I, E, C, F, GH , D, I, B, E, A, F, C, GH , I, D, B, E, F, G, A, C解析：先序遍歷先遍歷根節(jié)點，再遍歷左子樹，最后遍歷右子樹，遞歸進行答案：B2-14三叉樹中，度為1的結(jié)點有5個，度為2的結(jié)點3個，度為3的結(jié)點2個，問該樹含有幾個葉結(jié)點？ （3分）8101213解析：思路與2-8類似，在此不再闡述答案：A單位：浙江大學(xué)2-15某二叉樹的中序序列和后序序列正攵?相反，則該二叉樹一定是 （2分）.空或只有一個結(jié)點.高度等于其結(jié)點數(shù).任一結(jié)點無左孩子.任一結(jié)點無右孩子解析：中序遍歷是左斗^右，后序遍歷是左-右-根，可知如果左子樹不存在的話，就是恰好滿足條件的答案：C單位：浙江大學(xué)2-16某二叉樹的前序和后序遍歷序列正攵?相反，則該二叉樹一定是 （2分）.空或只有一個結(jié)點.高度等于其結(jié)點數(shù)

.任一結(jié)點無左孩子.任一結(jié)點無右孩子解析：思路同2-15,在此不再闡述答案：D2-17設(shè)n、m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時， n在m前的條件是（3分）n在m左方n在m右方n是m祖先n是m子孫解析：由顯然易得，選A答案：A2-18給定二叉樹如下圖所示。設(shè) N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3、1、7、5、6、2、4,則其遍歷方式是：（2分）NRLRNLLRNRLN解析：由顯然易得，選B答案：B2-19設(shè)高為h的二叉樹（規(guī)定葉子結(jié)點的高度為 1）只有度為0和2的結(jié)點，則此類二叉樹的最少結(jié)點數(shù)和最多結(jié)點數(shù)分別為：（3分）解析：由打工飾愈寰桂質(zhì)！解析：由打工飾愈寰桂質(zhì)！易得 B答案正確，容易誤選D,當(dāng)除根節(jié)點之外，每層有兩個節(jié)點的時候，結(jié)點數(shù)是最少的（不方便畫圖就不畫了，自行理解）答案：B2-20在下述結(jié)論中，正確的是：(2分)①只有一個結(jié)點的二叉樹的度為 0；②二叉樹的度為2;③二叉樹的左右子樹可任意交換；④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。.①④.②④.①②③.②③④解析：考察二叉樹的定義以及性質(zhì)，可以參考課本 P113頁答案：A.函數(shù)題.編程題線性表應(yīng)用.單選題2-1采用多項式的非零項鏈式存儲表示法，如果兩個多項式的非零項分別為 N1和N2個，最高項指數(shù)分別為M1則實現(xiàn)兩個多項式相乘的時間復(fù)雜度是： (2分)O(N1XN2)O(M1義M2)O(N1+N2)O(M1+M2)解析：略答案：A.編程題.判斷題1-1通過對堆棧S操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)。輸出的序列為：123。(2分)解析：水題，略答案：F作者：DS課程組1-2若一個棧的輸入序列為 1,2,3,…,N,輸出序列的第一個元素是 i,則第j個輸出元素是j-i-1o(2分)解析：第j個輸出的元素應(yīng)該是不確定的，可以帶i=2,j=3的特指驗證答案：F作者：DS課程組1-3若一個棧的輸入序列為｛1,2,3,4,5｝,則不可能得到｛3,4,1,2,5｝這樣的出棧序列。(2分)解析：2一定先與1出棧的答案：T.單選題2-1給定一個堆棧的入棧序列為｛1,2,?,n｝,出棧序列為｛p1,p2,?,pn｝。如果p2=n，則存在多少種不同的出棧序列？(2分)12n-1n解析：首先p1之前有n-1中選法，然后p2后邊的序列一定是唯一的，因為不會再有元素進棧導(dǎo)致出棧序列變化了答案：C2-2設(shè)一個堆棧的入棧順序是 1、2、3、4、5。若第一個出棧的元素是 4,則最后一個出棧的元素必定是： (2分)1351或者5

解析：要不1-4全出棧再進5,要不進5之后全答案：D2-3從棧頂指針為ST的鏈棧中刪除一個結(jié)點且用 X保存被刪結(jié)點的彳I,則執(zhí)行： （2分）X=ST->data;X=ST;ST=ST->next;X=ST->data;ST=ST->next;ST=ST->next;X=ST->data;解析：考察對鏈棧的掌握，在鏈棧中， ST代表棧頂元素，其data存儲的元素的值答案：C2-4Q,設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a、b、c、d、e、f、g依次進入棧S。若每個元素出棧后立即進入隊列且7個元素出隊的順序是b、d、c、f、e、a、g,則棧S的容量至少是：（2分）Q,1.1234解析：模擬即可答案：C2-5假設(shè)有5個整數(shù)以1、2、3、4、5的順序被壓入堆棧，且出棧順序為 3、5、4、2、1,那么為了獲得這樣的輸出,堆棧大小至少為：（2分）2345解析：模擬一遍即可答案：C2-6若元素a、b、c、d、e、f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧工作，則不可能得到的出棧序列是？ （2分）bcaefdcbdaefdcebfaafedcb解析：D中的dcd很明顯是連續(xù)三次退棧了答案：D2-7設(shè)一個棧的輸入序列是 1、2、3、4、5,則下列序列中，是棧的合法輸出序列的是？（2分）32154512344513243125解析：如果某個子序列在某個數(shù)的左邊，那么在輸出的時候，這個子序列的輸出一定是確定的。例如1,2,3在4的左邊，那么我棧輸出的時候，一定是先輸出 3,在輸出2,最后輸出1,中間可以穿插其他的元素?？梢岳眠@個性質(zhì)去判斷選項是否合法答案：A2-8有六個元素以6、5、4、3、2、1的順序進棧，問哪個不是合法的出棧序列？ （2分）234156346521543612453126解析：針對每個選項進行驗證即可答案：B2-9若一個棧的入棧序列為 1、2、3、飛N,輸出序列的第一個元素是 i,則第j個輸出元素是：（2分）i-j-1i-jj-i-1不確定解析：當(dāng)i不等于N的時候，第j個輸出是不確定的，因為隨時有可能有新的元素插入進來并在任意位置輸出改變原有的輸出順序；當(dāng)i=N,輸出序列才是確定的答案：D2-10若一個棧的入棧序列為 1、2、3、N,其輸出序列為p1、p2、p3、pN。若p1=N,則pi為：（2分）in-in-i+1不確定解析：當(dāng)p1等于N,p2-pn是唯一的一個序列，pi=n-i+1答案：C2-11將5個字母ooops按此順序入棧，則有多少種不同的出棧順序可以仍然得到 ooops?（2分）1.1356解析：五種方案，三個0的順序可以是321,123,213,132,231答案：C2-12棧的插入和刪除操作在（）進行。（2分）.棧頂.棧底.任意位置.指定位置解析：略答案：A3.編程題棧及其應(yīng)用.單選題2-1線性表、堆棧、隊列的主要區(qū)別是什么？ （1分）.線性表用指針，堆棧和隊列用數(shù)組.堆棧和隊列都是插入、刪除受到約束的線性表.線性表和隊列都可以用循環(huán)鏈表實現(xiàn)，但堆棧不能.堆棧和隊列都不是線性結(jié)構(gòu)，而線性表是解析：首先題意我自己感覺很迷。。。A選項，他們都可以用指針或者數(shù)組 ，C選項，線性表不能用循環(huán)鏈表實現(xiàn),選項，他們都是線性結(jié)構(gòu)答案：B.函數(shù)題.編程題解析：略解析：略隊列1.單選題2-1為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是？ （1分）.堆棧.隊列.樹.圖解析：略答案：B2-2若已知一隊列用單向鏈表表示，該單向鏈表的當(dāng)前狀態(tài)（含3個對象）是：1->2->3,其中x->y表示x的下一節(jié)點是yo此時，如果將對象 4入隊，然后隊列頭的對象出隊，則單向鏈表的狀態(tài)是： （1分）1->2->32->3->44->1->2答案不唯一解析：略答案：B2-3在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結(jié)點 s的操作為（）。（2分）front=front->nexts->next=rear;rear=srear->next=s;rear=s;s->next=front;front=s;解析：略答案：C2-4依次在初始為空的隊列中插入元素 a,b,c,d以后，緊接著做了兩次刪除操作，此時的隊頭元素是（ ）。（2分）abcd答案：C2-5在一個不帶頭結(jié)點的非空鏈式隊列中 ，假設(shè)f和r分別為隊頭和隊尾指針，則插入s所指的結(jié)點運算是（）。（2分）f->next=s;f=s;r->next=s;r=s;s->next=s;r=s;s->next=f;f=s;解析：略答案：B2.編程題循環(huán)隊列及線性結(jié)構(gòu)綜合.判斷題1-1所謂循環(huán)隊列”是指用單向循環(huán)鏈表或者循環(huán)數(shù)組表示的隊列。 （1分）解析：略答案：F1-2在用數(shù)組表示的循環(huán)隊列中， front值一定小于等于rear值。（1分）解析：略答案：F1-3不論是入隊列操作還是入棧操作 ，在順序存儲結(jié)構(gòu)上都需要考慮 "溢出"情況。（2分）解析：略答案：T.單選題2-1 若用大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為0和4。當(dāng)從隊列中刪除兩個元素，再加入兩個元素后，front和rear的值分別為多少？ （2分）1.2和02和22和4

2和6解析：front=00+2)%6=2,rear=(4+2)%6=0答案：A2-2size代替一般循環(huán)隊列中的 front（2分）1.m-12.3.4.m+1不能確定解析：注意看清楚題目給定的規(guī)則，這樣就不需要空一個位置來判斷是否為滿了答案：B2-3如果循環(huán)隊列用大小為 m的數(shù)組表示，隊頭位置為 size代替一般循環(huán)隊列中的 front（2分）1.m-12.3.4.m+1不能確定解析：注意看清楚題目給定的規(guī)則，這樣就不需要空一個位置來判斷是否為滿了答案：B2-3如果循環(huán)隊列用大小為 m的數(shù)組表示，隊頭位置為 front、隊列元素個數(shù)為為：（2分）size,那么隊尾元素位置 rear1.front+sizefront+size-1（front+size）%m（front+size-1）%m解析：讀題，rear這次代表隊尾元素啦，然后自然就選 D了答案：D3.編程題最短路徑.判斷題1-1在一個有權(quán)無向圖中，若b到a的最短路徑距離是12,且c到b之間存在一條權(quán)為2的邊，則c到a的最短路徑距離一定不小于10。（3分）解析：根據(jù)題意畫出圖來，因為a,b最短路徑是12,所以c-b-a應(yīng)大于等于12,所以c-a最短距離大于等于10答案：T.單選題2-1我們用一個有向圖來表示航空公司所有航班的航線。下列哪種算法最適合解決找給定兩城市間最經(jīng)濟的飛行路線問題？（1分）.Dijkstra算法.Kruskal算法.深度優(yōu)先搜索.拓撲排序算法解析：A選項解決單源最短路問題，自然可以解決兩點之間最短路， B選項解決最小生成數(shù)問題， D選項解決AOE關(guān)鍵路徑問題，C選項。。就是遍歷圖用的，可以生成深度優(yōu)先生成樹答案：A2-2數(shù)據(jù)結(jié)構(gòu)中Dijkstra算法用來解決哪個問題？ （1分）.關(guān)鍵路徑.最短路徑.拓撲排序.字符串匹配解析：考察課本基礎(chǔ)知識答案：B2-3若要求在找到從 S到其他頂點最短路的同時，還給出不同的最短路的條數(shù)，我們可以將Dijkstra算法略作修改，增加一個count[]數(shù)組：count[V] 記錄S到頂點V的最短路徑有多少條。則 count[V] 應(yīng)該被初始化為：（3分）.count[S]=1;對于其他頂點V則令count[V]=0.count[S]=0;對于其他頂點V則令count[V]=1.對所有頂點都有count[V]=1.對所有頂點都有count[V]=0解析：計算S到V最短路徑的遞推式是： count[V]=count[V]+count[S]?？傻肁答案比較合適答案：A2-4使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點 1到其他各頂點的最短路徑，依次得到的各最短路徑的目標(biāo)頂點是：（2分）解析：考察課本基礎(chǔ)知識解析：考察課本基礎(chǔ)知識5,2,3,4,65,2,3,6,45,2,4,3,65,2,6,3,4解析：模擬Dijstra算法求解即可答案：B2-5在一個有權(quán)無向圖中，如果頂點b到頂點a的最短路徑長度是10,頂點c與頂點b之間存在一條長度為3的邊。那么下TOC\o"1-5"\h\z列說法中有幾句是正確的？ （3分）c與a的最短路徑長度就是 13c與a的最短路徑長度就是 7c與a的最短路徑長度不超過 13c與a的最短路徑不小于71.1句2句3句4句解析：根據(jù)題意建出圖來，顯然，3,4句話是正確的答案：B.程序填空題.編程題拓撲排序與關(guān)鍵路徑.單選題2-1在AOE網(wǎng)中，什么是關(guān)鍵路徑？ （1分）.最短回路.最長回路.從第一個事件到最后一個事件的最短路徑.從第一個事件到最后一個事件的最長路徑

答案：D2-2在拓撲排序算法中用堆棧和用隊列產(chǎn)生的結(jié)果會不同嗎？ (1分).是的肯定不同.肯定是相同的.有可能會不同.以上全不對解析：引入棧的目的僅僅是為了避免重復(fù)掃描數(shù)組，因此引入隊列也可以，結(jié)果是有可能相同的，比如只有一個元素答案：C2-3下圖為一個AOV網(wǎng)，其可能的拓撲有序序列為： (2分)ABCDFEGADFCEBGACDFBEGABDCEFG解析：排除法做，首先第一個元素肯定是 A,第二個肯定不是C,假設(shè)第二個是B,那么第三個肯定是D,選D沒毛病答案：D2-4（1分）若將n個頂點（1分）O(n)O(n+e)O(n2)O(nxe)解析：先需要O(e)求入度，然后需要O(n)求序列答案：B2-5（2分）（2分）已知有向圖G=（V,E）,其中V={v1,v2,v3,v4,v5,v6},E={<v1,v2>,已知有向圖G=（V,E）,其中V={v1,v2,v3,v4,v5,v6},E={<v1,v2>,<v1,v4>, <v2,v6>, <v3,v1>,<v3,v4>,<v4,v5>, <v5,v2>, <v5,v6>}G的拓撲序列是：（2分）1.4321解析：一個一個數(shù)，選C答案：C2-6v3,v1,v4,v5,v2,v6TOC\o"1-5"\h\zv3, v4, v1, v5, v2, v6v1, v3, v4, v5, v2, v6v1, v4, v3, v5, v2, v6解析：建圖模擬即可，畫清楚圖答案：A查找-順序查找、二分查找1.單選題2-1已知一個長度為16的順序表L,其元素按關(guān)鍵字有序排列。若采用二分查找法查找一個 L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多是： （2分）A.4B.5C.6D.7解：二分查找的最多比較次數(shù)為 ，故答案是B:52-2用二分查找從100個有序整數(shù)中查找某數(shù)，最壞情況下需要比較的次數(shù)是： （2分）A.7B.10C.50D.99解：解法同上故答案是A:72-3在有n（n>1000）個元素的升序數(shù)組A中查找關(guān)鍵字x。查找算法的偽代碼如下所示:k=0;while （k<n且A[k]<x）k=k+3;if（ k<n且A[k]==x）查找成功；else if（k-1<n且A[k-1]==x）查找成功；elseif（k2<n且A[k2]==x）查找成功；else查找失敗；本算法與二分查找（折半查找）算法相比，有可能具有更少比較次數(shù)的情形是： （2分）A.當(dāng)x不在數(shù)組中 B.當(dāng)x接近數(shù)組開頭處 C.當(dāng)x接近數(shù)組結(jié)尾處 D.當(dāng)x位于數(shù)組中間位置解：顯然可得，選B,這樣第一個while循環(huán)可以少執(zhí)行2-4下列二叉樹中，可能成為折半查找判定樹（不含外部結(jié)點）的是： （4分）時，葉子節(jié)點偏向相反，應(yīng)該是從最左邊開始，偏向左邊的。我們可以自行畫圖驗證。綜上所,，的也即）B有兩種偏向并存）!飛[郴卿扁并存，并且沒有從最左，左右開始）， D錯誤（中間有2.編程題7-1兩個有序序列的中位數(shù)（25分）已知有兩個等長的非降序序列 ，，設(shè)計函數(shù)求 與并集的中位數(shù)。有序序列，，？，的中位數(shù)指的值,即第？（N+1）/2?個數(shù)$Q為第1個數(shù)）七c 河M 占102 AqAi月w—i輸入格式：輸入分三行。第一行給出序列的公共長度 N（0<NC100000）,隨后每行輸入一個序列的信息，即N個非降序排列的整數(shù)。數(shù)字用空格間隔。輸出格式：在一行中輸出兩個輸入序列的并集序列的中位數(shù)。輸入樣例1:213579輸出樣例1：輸入樣例2:100-101111-5002345輸出樣例2:解題思路利用歸并排序中的兩路歸并思想，將兩個區(qū)間歸并成一個區(qū)間，然后求中位數(shù)即可代碼實現(xiàn)1#include<cstdio>usingnamespacestd;structNode{intv;};constintmaxn=2*100000+10;789101112131415161718192021intintintinthead[maxn];nexts[maxn];vec1[maxn],vec2[maxn],vec[maxn];main(){intn;scanf("%d",&n);for(inti=0;i<n;i++){scanf("%d",&vec1[i]);}for(inti=0;i<n;i++){scanf("%d",&vec2[i]);}int i=0,j=0;int cnt=0;while(i<n&&j<n){22if(vec1[i]<vec2[j]){2324232425262728293031323334353637383940414243 }vec[cnt++]=vecl[i];i++；}elseif(vecl[i]>vec2[j]){vec[cnt++]=vec2[j];j++;}else{vec[cnt++]=vec2[j];i++;}}while(i<n){vec[cnt++]=vec1[i++];}while(j<n){vec[cnt++]=vec2[j++];}printf("%d\n",vec[(cnt-1)/2]);return0;查找-二叉排序樹new1.單選題2-1若二叉搜索樹是有N個結(jié)點的完全二叉樹，則不正確的說法是： （1分）A.所有結(jié)點的平均查找效率是 O（logN）B.最小值一定在葉結(jié)點上 C.最大值一定在葉結(jié)點上 D.中位值結(jié)點在根結(jié)點或根的左子樹上解析：A答案顯然正確；因為是完全二叉樹，考慮只有兩個節(jié)點的完全二叉樹，可得 B答案正確，C選項錯誤，D選項錯誤（兩個節(jié)點的中位值好像不存在?。┐鸢福篊2-2若一棵二叉樹的后序遍歷序列是 {1,3,2,6,5,7,4），中序遍歷序列是{1,2,3,4,5,6,7），則下列哪句是錯的？ （3分）A.這是一棵完全二叉樹B.2是1和3的父結(jié)點C.這是一棵二叉搜索樹D.7是5的父結(jié)點解析：根據(jù)后序遍歷和中序遍歷建樹去判斷即可答案：A

2-3將｛32,2,15,65,28,10｝依次插入初始為空的二叉搜索樹。則該樹的前序遍歷結(jié)果是： （3分）2,10,15,28,32,6532,2,10,15,28,6510,28,15,2,65,3232,2,15,10,28,65解析：建出二叉搜索樹，然后去判斷即可答案：A2-4下列二叉樹中，可能成為折半查找判定樹（不含外部結(jié)點）的是： （4分）2-52-5若一棵二叉樹的前序遍歷序列是 ｛4,2,1,3,6,5,7｝，中序遍歷序列是｛1,2,3,4,5,6,7｝，則下列哪句是錯的？ （3分）A.這是一棵完全二叉樹 B.所有的奇數(shù)都在葉子結(jié)點上 C.這是一棵二叉搜索樹 D.2是5的父結(jié)點解析：建出二叉搜索樹，然后去判斷即可答案：D2-6將｛5,11,13,1,3,6｝依次插入初始為空的二叉搜索樹。則該樹的后序遍歷結(jié)果是： （3分）A.3,1,5,6,13,11B.3,1,6,13,11,5C.1,3,11,6,13,5D.1,3,5,6,13,11解析：建出二叉搜索樹，然后去判斷即可答案：B2-7（1分）（1分）A.前序遍歷B.后序遍歷C.中序遍歷D.層次遍歷解析：根據(jù)二叉搜索樹的定理可得，左子樹小于根節(jié)點，右子樹大于根節(jié)點，所以應(yīng)當(dāng)才有中序遍歷，先左，后中，再右答案：C2-8TOC\o"1-5"\h\z若二叉搜索樹是有N個結(jié)點的完全二叉樹，則不正確的說法是： （1分）A.平均查找效率是O（logN）B.最大值一定在最后一層C.最小值一定在葉結(jié)點上D.中位值結(jié)點在根結(jié)點或根的左子樹上解析：B選項，還是考慮只有兩個元素的完全二叉樹，最大值在第一層，故選 B答案：B2-9已知8個數(shù)據(jù)元素為（34,76,45,18,26,54,92,65）,按照依次插入結(jié)點的方法生成一棵二叉搜索樹后，最后兩層上的結(jié)點總數(shù)為： （2分）A.1B.2C.3D.4解析：建樹判斷即可答案：D2-10下列敘述正確的是（）。 （2分）A.在任意一棵非空二叉搜索樹，刪除某結(jié)點后又將其插入，則所得二叉搜索樹與刪除前原二叉搜索樹相同。 B.二叉樹中除葉結(jié)點外，任一結(jié)點X,其左子樹根結(jié)點的值小于該結(jié)點（X）的值；其右子樹根結(jié)點的值2該結(jié)點（X）的值，則此二叉樹一定是二叉搜索樹。 C.雖然給出關(guān)鍵字序列的順序不一樣，但依次生成的二叉搜索樹卻是一樣的。D.在二叉搜索樹中插入一個新結(jié)點，總是插入到最下層，作為新的葉子結(jié)點。解析：因為對于同樣的元素集合，插入的順序不同，二叉樹的形狀也不同，所以 A,C錯誤，B選項中大于等于表述不正確，根據(jù)二叉搜索樹定義可知應(yīng)該是大于 ，故選D答案：D2.編程題7-1是否同一棵二叉搜索樹（25分）給定一個插入序列就可以唯一確定一棵二叉搜索樹。然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。例如分別按照序列｛2,1,3｝和｛2,3,1｝插入初始為空的二叉搜索樹，都得到一樣的結(jié)果。于是對于輸入的各種插入序列，你需要判斷它們是否能生成一樣的二叉搜索樹。輸入格式：輸入包含若干組測試數(shù)據(jù)。每組數(shù)據(jù)的第 1行給出兩個正整數(shù)N（＜10犯L,分別是每個序列插入元素的個數(shù)和需要檢查的序列個數(shù)。第2行給出N個以空格分隔的正整數(shù)，作為初始插入序列。最后L行，每行給出N個插入的元素,屬于L個需要檢查的序列。簡單起見，我們保證每個插入序列都是 1到N的一個排列。當(dāng)讀到N為0時，標(biāo)志輸入結(jié)束，這組數(shù)據(jù)不要處理。

輸出格式：對每一組需要檢查的序列，如果其生成的二叉搜索樹跟對應(yīng)的初始序列生成的一樣，輸出 “Yes；否則輸出“NO：輸入樣例：TOC\o"1-5"\h\z4 231423 4 1 23 2 4 12 12 11 20輸出樣例：YesNoNo鳴謝青島大學(xué)周強老師補充測試數(shù)據(jù)！解題思路：兩棵二叉搜索樹相等應(yīng)該滿足這樣的條件：左子樹相等右子樹相等根節(jié)點相等根據(jù)這個條件，遞歸去解即可，注意邊界以及空子樹的特殊處理，具體可見代碼實現(xiàn)參考代碼：#include <cstdio>TOC\o"1-5"\h\zusing namespace std;struct Node{intv;Node * lchild ;Node * rchild ;};typedefNode *BSTree;voidInsertBST (BSTree& T,intv){if(T ==NULL) {T=new Node();T>lchild =NULL;T-:rchild =NULL;T-：v=v;}elseif(v<T-y){InsertBST(T-^lchild ,v);

171819202122171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061}}boolCompareBST(BSTree&T1,BSTree&T2){if(T1==NULL&&T2==NULL){returntrue;}if(!T1|| !T2){returnfalse;}if(T1-r!=T2f){returnfalse;}if(!CompareBST(T1-4child,T2-4child )|| !CompareBST(T1-:rchildreturnfalse;}returntrue;}voidCreateBST(BSTree&T,intn){T=NULLfor(inti=0;i<n;i++){intd;scanf("%d",&d);InsertBST(T,d);}}intmain(){intNL;while(~scanf("%d",&N)&&N){scanf("%d",&L);BSTreeT1;BSTreeT2;CreateBST(T1,N);for(inti=0;i<L;i++){CreateBST(T2,N);if(CompareBST(T1,T2)){printf("Yes'n");}else{printf("No\n");}}}return0;}T2-:rchild )){7-2是否完全二叉搜索樹（T2-:rchild )){將一系列給定數(shù)字順序插入一個初始為空的二叉搜索樹（定義為左子樹鍵值大，右子樹鍵值?。?，你需要判斷最后的樹是否一棵完全二叉樹，并且給出其層序遍歷的結(jié)果。輸入格式：輸入第一行給出一個不超過20的正整數(shù)N；第二行給出N個互不相同的正整數(shù)，其間以空格分隔。

輸出格式：將輸入的N個正整數(shù)順序插入一個初始為空的二叉搜索樹。在第一行中輸出結(jié)果樹的層序遍歷結(jié)果，數(shù)字間以空格分隔，行的首尾不得有多余空格。第二行輸出YES,如果該樹是完全二叉樹；否則輸出NO。輸入樣例1:1 92 3845422458306712513輸出樣例1:1 384524584230126751YES輸入樣例2:83824124558674251輸出樣例2:3845245842126751NO解題思路：根據(jù)完全二叉樹的性質(zhì)，最后一層可以不滿，但是葉子必須從左到右順排著，不允許中間有空節(jié)點，因此我們可以在層次遍歷的過程中，通過設(shè)置標(biāo)志變量的方式判斷輸入的樹是否滿足葉子節(jié)點之間有空節(jié)點上邊右圖G節(jié)點與F節(jié)點中間為空，因此不是完全二叉樹。要實現(xiàn)判斷,口需要虛擬一個空節(jié)點便于處理。題實現(xiàn)并不簡單，可以參考下邊的代碼參考代碼：注意：代碼中用了部分STL的庫，這些庫的使用不是必要的，容易自己去實現(xiàn)，這里就不再替換了1#include<cstdio>2#include<queue>

#include<vector>usingnamespacestdstructNode{intv;Node*lchildNode*rchild};typedefNode*BSTree;BSTreeNULLTree;voidInsertBST(BSTree&T,intv){if(T==NULLTree){T=newNode();T-Mild =NULLTree;T-:rchild =NULLTree;T-v=v;}else if (v >T -：v) {InsertBST(T-^lchild,v);}else if (v <T -：v) {InsertBST(T-:rchild,v);}}voidCreateBST(BSTree&T,intn){T=NULLTree;for(inti=0;i<n;i++){intd;scanf("%d",&d);InsertBST(T,d);}}boolLevelBST(BSTree&T,vector<int>&vec){queue<BSTree>q;q.push(T);boolis_ok=true;intflag=0;while(!q.empty()) {BSTreet=q.front();q.pop();if(t!=NULLTree){if(flag>0){flag=-1;}vec.push_back(t-r);if(t-：l€hild ){q.push(t-4child);}else{q.push(NULLTree);}if(t-:rchild){q.push(t-=rchild);}else{345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455q.push(NULLTree);2-62-6答案：答案：C5656575859606162636465 }66int6768697071727374757677787980818283848586878889 }}}else{if(flag>=0){

flag++;}}}returnflag==-1;main(){intNL;NULLTree=newNode();NULLTree-Schild =NULLNULLTree—child =NULLNULLTree-v=-1;while(~scanf("%d",&NI)&&N){BSTreeT;CreateBST(T,N);vector<int>vec;boolflag=LevelBST(T,vec);printf("%d",vec[0]);i++){for(inti=1;i<vec.size();

printf("%d",vec[i]);i++){}printf("\n");if(!flag){printf("YES'n");}else{printf("NO\n");}}return0;查找-哈希查找.單選題2-1散列沖突可以被描述為： （1分）.兩個元素除了有不同鍵值，其它都相同.兩個有不同數(shù)據(jù)的元素具有相同的鍵值.兩個有不同鍵值的元素具有相同的散列地址.兩個有相同鍵值的元素具有不同的散列地址解析：由散列沖突的定義，選

2-2將10個元素散列到100000個單元的哈希表中，是否一定產(chǎn)生沖突？ （1分）.一定會.可能會.一定不會.有萬分之一的可能會解析：是否沖突與散列函數(shù)有關(guān)，比如對于散列函數(shù) H（key）= %100000,1與-99999是沖突的答案：B 山中口。0；2-3設(shè)散列表的地址區(qū)間為[0,16],散列函數(shù)為H（Key尸Key%17。采用線性探測法處理沖突，并將關(guān)鍵字序列 ｛26,25,72,38,8,18,59｝依次存儲到散列表中。元素 59存放在散列表中的地址是： （2分）1.891011解析：模擬線性探測法過程，遇到?jīng)_突元素，順著往后找可以放置這個元素的位置答案：D2-4采用線性探測法解決沖突時所產(chǎn)生的一系列后繼散列地址： （1分）.必須大于等于原散列地址.必須小于等于原散列地址.可以大于或小于但不等于原散列地址.對地址在何處沒有限制解析：線性探測法是將原散列表想象成一個循環(huán)表，發(fā)生沖突時，從沖突地址的下一個位置順序?qū)ふ铱諉卧?，可以折返到表頭繼續(xù)找，找不到就說明散列表已滿故選 C答案：C2-5將元素序列｛18,23,11,20,2,7,27,33,42,15｝按順序插入一個初始為空的、大小為11的散列表中。散列函數(shù)為：H（Key尸Key%11,采用線性探測法處理沖突。問：當(dāng)?shù)谝淮伟l(fā)現(xiàn)有沖突時，散列表的裝填因子大約是多少？（3分）1.0.270.450.640.73解析：根據(jù)裝填因子計算公式 表中填入的記錄數(shù)模擬計算即可散列表的長度,答案：B "一2-2-N個關(guān)鍵詞所用的比較次數(shù)為： (2若N個關(guān)鍵詞所用的比較次數(shù)為： (2分)N(N+1)/2N(N-1)/2N+1N解析：1+2+??+N=N(N+1)/2答案：A2-11給定散列表大小為17,散列函數(shù)為H(Key尸Key%17。采用平方探測法處理沖突： hi(k)=(H(k)±)%17將關(guān)鍵字序列{6,22,7,26,9,23}依次插入到散列表中。那么元素 23存放在散列表中的位置是：(3分)i21.02615解析：模擬平方探測法的過程，當(dāng)插入23的時候，發(fā)現(xiàn)i=+1,-1,+2時，位置均被占用，此時選擇i=-2,位置是23%17-4=2答案：B2-12給定散列表大小為17,散列函數(shù)為H(Key尸Key%17。采用平方探測法處理沖突： hi(k)=(H(k)±)%17將關(guān)鍵字序列{23,22,7,26,9,6}依次插入到散列表中。那么元素 6存放在散列表中的位置是：(3分) 飛名1541062解析：同上答案：D2-13將元素序列{18,23,4,26,31,33,17,39}按順序插入一個初始為空的、大小為13的散列表中。散列函數(shù)為：H(Key)=Key%13,采用線性探測法處理沖突。問：當(dāng)?shù)谝淮伟l(fā)現(xiàn)有沖突時，散列表的裝填因子大約是多少？ (3分)1.0.540.630.310.62解析：模擬計算即可，第一次發(fā)現(xiàn)沖突時，此時表中共有4個元素，4/13=0.31,選C答案：C給定散列表大小為11,散列函數(shù)為H(Key尸Key%11。按照線性探測沖突解決策略連續(xù)插入散列值相同的 5個元素問：此時該散列表的平均不成功查找次數(shù)是多少？ (2分)1.26/115/111不確定解析： ，r為散列函數(shù)取值的個數(shù)， 為函數(shù)取值為i時查找失敗的比較次數(shù);比較次數(shù)就是從查找的位置開始到遇到空的位置的比較次數(shù)。帶入公式解即得答案答案：A2.函數(shù)題6-1線性探測法的查找函數(shù)(20分)試實現(xiàn)線性探測法的查找函數(shù)。函數(shù)接口定義：PositionFind(HashTableH,ElementTypeKey);其中HashTable是開放地址散列表，定義如下：#define MAXTABLESIZE100000 /* 允許開辟的最大散列表長度 */typedef intElementType; /* 關(guān)鍵詞類型用整型*/typedef intIndex; /* 散列地址類型*/typedefIndexPosition; /*數(shù)據(jù)所在位置與散列地址是同一類型 *//*散列單元狀態(tài)類型，分別對應(yīng)：有合法元素、空單元、有已刪除元素*/typedef enum {Legitimate,Empty, Deleted}EntryType;typedef structHashEntry Cell;/* 散列表單元類型*/structHashEntry{10ElementTypeData;/*存放元素*/111213EntryType};Info;/*單元狀態(tài)*/14typedefstructTblNode*HashTable;/*散列表類型*/1516struct TblNode{ /*int TableSize; /*散列表結(jié)點定義*/表的最大長度*/171819Cell*Cells;};/*存放散列單元數(shù)據(jù)的數(shù)組*/函數(shù)Find應(yīng)根據(jù)裁判定義的散列函數(shù) Hash(Key,H->TableSize)從散列表H中查到Key的位置并返回。如果Key不存在，則返回線性探測法找到的第一個空單元的位置；若沒有空單元，則返回 ERROR。裁判測試程序樣例：#include<stdio.h>

#defineMAXTABLESIZE100000 /*允許開辟的最大散列表長度 */typedefintElementType;/*關(guān)鍵詞類型用整型 */typedefintIndex;/*散列地址類型*/typedefIndexPosition;/*數(shù)據(jù)所在位置與散列地址是同一類型*//*散列單元狀態(tài)類型，分別對應(yīng):有合法元素、空單元、有已刪除元素 */typedefenum{Legitimate,Empty,Deleted}EntryType;3456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051*/*/typedefstructHashEntrystructHashEntry{ElementTypeData;/*EntryTypeInfo;/*};Cell;/*散列表單元類型存放元素*/單元狀態(tài)*/typedefstructTblNode*HashTable;/*散列表類型*/structTblNode{ /*散列表結(jié)點定義*/intTableSize;/* 表的最大長度*/Cell};*Cells;/*存放散列單元數(shù)據(jù)的數(shù)組 */HashTableBuildTable();/*裁判實現(xiàn)，細節(jié)不表*/PositionHash(ElementTypeKey,intTableSize){return(Key%TableSize);}#defineERROR-1PositionFind(HashTableH,ElementTypeKey);intmain()HashTableH;ElementTypeKey;PositionP;H=BuildTable();scanf("%d",&Key);P=Find(H,Key);if(P==ERROR)printf("ERROR: %diselseif(H-printf("%delse>Cells[P].Infonotfoundandthe

==Legitimate)tableisfull.\n",Key)；/*printf("%dreturn0;isis你的代碼將被嵌在這里atpositionnotfound.*/%d.\n",Key,Position%d輸入樣例1:（注：-1表示該位置為空。下同。）P)；isreturned.\n",Key,P);1 112 118821 138輸出樣例1 38isatposition9.2輸入樣例2:11118821 1-151676381041輸出樣例2:輸出樣例2:1 41isnotfound.Position3isreturned.輸入樣例3:1111882131451676381041輸出樣例3:輸出樣例3:1ERROR:41isnotfoundandthetableisfull.解題思路：線性探測法的實現(xiàn)，如果第一次散列得到的位置為空，那么元素不存在；如果不為空并且等于要查找的值，則找到，否則繼續(xù)查找下一個位置，并且判斷是否等于要查找的元素，直到遍歷整個哈希表。參考代碼：PositionFind(HashTableHElementTypeKey){TOC\o"1-5"\h\zPosition p;p=Hash(Key,H -:TableSize);inta= p;intflag =0;while(1) {if (H -:Cells[p].Info!= Legitimate)break;if (H -:Cells[p].Info== Legitimate&&H-;Cells [p].Data==Key)break;if (p ==a&&flag==1) returnERROR++p;

P=P%H-:TableSizeTOC\o"1-5"\h\zflag =1;}return p;}排序-插入排序.單選題2-1對一組包含10個元素的非遞減有序序列，采用直接插入排序排成非遞增序列，其可能的比較次數(shù)和移動次數(shù)分別是：（2分）100,100100,5454,6345,44解析：假設(shè)原序列是1,2,3,4,5,6,7,8,9那么比較和移動的次數(shù)經(jīng)過計算都為 =45。選項中沒有合適的，當(dāng)序列中出現(xiàn)重復(fù)的元素時，如1,2,2,3,4,5,這種情況，移動第2個2的時候移動次康g比較次數(shù)少了一次，故選Dn答案：D2-2設(shè)有1000個元素的有序序列，如果用二分插入排序再插入一個元素，則最大比較次數(shù)是： （2分）100099950010解析：根據(jù)最大比較次數(shù)公式 ，計算可得答案為10答案：D 山蛻可?12-3用直接插入排序方法對下面四個序列進行排序（由小到大），元素比較次數(shù)最少的是（）。 （2分）1.94,32,40,90,80,46,21,6921,32,46,40,80,69,90,9490,69,80,46,21,32,94,4032,40,21,46,69,94,90,80解析：元素比較次數(shù)與逆序數(shù)相關(guān)，從第二個元素開始數(shù)每個元素有多少個數(shù)與之是逆序數(shù)，加起來便是答案，因為每個元素之前的所有元素肯定已經(jīng)排好序了，其逆序數(shù)肯定都放在了后邊，因為我們與大于等于當(dāng)前數(shù)的元素比較，大于等于當(dāng)前數(shù)的就是當(dāng)前數(shù)的逆序數(shù)。因此比較次數(shù)等于逆序數(shù)的個數(shù)。A選項逆序數(shù)和為1+1+1+2+3+6+3=17B選項逆序數(shù)和為0+0+1+0+1+0+0=2C,D選項自行計算答案：B2.編程題7-1排序（25分）給定N個（長整型范圍內(nèi)的）整數(shù)，要求輸出從小到大排序后的結(jié)果。本題旨在測試各種不同的排序算法在各種數(shù)據(jù)情況下的表現(xiàn)。各組測試數(shù)據(jù)特點如下：數(shù)據(jù)1:只有1個元素；數(shù)據(jù)2:11個不相同的整數(shù)，測試基本正確性；數(shù)據(jù)3:103個隨機整數(shù)；數(shù)據(jù)4:104個隨機整數(shù)；數(shù)據(jù)5:105個隨機整數(shù)；數(shù)據(jù)6:105個順序整數(shù)；數(shù)據(jù)7:105個逆序整數(shù)；數(shù)據(jù)8:105個基本有序的整數(shù)；數(shù)據(jù)9:105個隨機正整數(shù)，每個數(shù)字不超過1000o輸入格式：輸入第一行給出正整數(shù)N（＜105,隨后一行給出N個（長整型范圍內(nèi)的）整數(shù)，其間以空格分隔。輸出格式：在一行中輸出從小到大排序后的結(jié)果，數(shù)字間以 1個空格分隔，行末不得有多余空格。輸入樣例：11498110-170-202950843-5輸出樣例：1 -20-17-504810294350981解題思路：參考代碼中是用插入排序來實現(xiàn)的，但是代碼會超時，應(yīng)該使用更快的歸并排序或者快速排序或者希爾排序或者堆排序，這里因為是想考察插入排序的內(nèi)容，就用插入排序?qū)懥?，同時使用了二分去減少比較次數(shù) ^參考彳t碼：1#include<cstdio>2usingnamespacestd;3 intA[1000000];

5678567891011121314 }15int161718192021222324252627282930313233343536 }intm=(l+r)/2;if(A[0]<=A[m{

r=m-1;}else{l=m+1;}}returnl;main(){intn;scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d",&A[i]);}for(inti=1;i<=n;i++){A[0]=A[i];intj;intt=search(A,1,i-1);for(j=i;j>t;j->{A[j]=A[j-1];}A[j]=A[0];}printf("%d",A[1]);for(inti=2;i<=n;i++){printf("%d",A[i]);}printf("\n");return0;排序--交換類排序與選擇類排序.判斷題1-1對N個記錄進行堆排序，需要的額外空間為 O(N)o(1分)解析：需要O(1)的額外空間答案：F1-2(1分)對N個記錄進行簡單選擇排序，比較次數(shù)和移動次數(shù)分別為 O()和(1分)解析:

答案：T1-3希爾排序是穩(wěn)定的算法。 （1分）解析：希爾排序過程中因為不是順需插入的，會破壞相等元素的相對位置，（意會吧，我將不出來）答案：F作者：DS課程組1-4對N個不同的數(shù)據(jù)采用冒泡排序進行從大到小的排序，當(dāng)元素基本有序時交換元素次數(shù)肯定最多。 （1分）解析：基本有序時不發(fā)生交換答案：F.單選題2-1*TOC\o"1-5"\h\z在快速排序的一趟劃分過程中，當(dāng)遇到與基準數(shù)相等的元素時，如果左右指針都會停止移動，那么當(dāng)所有元素都相等時，算法的時間復(fù)雜度是多少？ （2分）1.0（ ）2.0（）3.0（ ）4.O（ ）趟排序,解析：考察對快速排序過程的理解。首先我們要記住，當(dāng)對進行完一趟排序之后，如果基準元素在接近于中間的位置，那么它的時間復(fù)雜度自然是極好的，每趟排序我們都要對元素比較 n次，賦值n次，總共進行了趟排序,所以時間復(fù)雜度是 ；但如果我們進行完一趟排序之后，如果基準元素在接近于最左或者最右的位置，那么我們排序的趟數(shù)肯定會增加，極端條件下達到 no 英;fog*ri回到這道題，當(dāng)遇到基準元素的時候左右指針都停止了移動，那么進行完一趟排序的時候，基準元素一定位于接近于中間的位置（想一想為什么），因此時間復(fù)雜度為 0（ ）答案：C MogN2-2*在快速排序的一趟劃分過程中，當(dāng)遇到與基準數(shù)相等的元素時，如果左右指針都不停止移動，那么當(dāng)所有元素都相等時，算法的時間復(fù)雜度是多少？ （2分）1.0( )")0( )0( )N2解析：與上題屬于一個系列的，當(dāng)遇到基準元素的時候左右指針都不停止移動，那么進行完一趟排序的時候，基準TOC\o"1-5"\h\z元素一定位于接近于右邊的位置(想一想為什么)，因此時間復(fù)雜度為 0()答案：D2-3*在快速排序的一趟劃分過程中，當(dāng)遇到與基準數(shù)相等的元素時，如果左指針停止移動，而右指針在同樣情況下卻不停止移動，那么當(dāng)所有元素都相等時，算法的時間復(fù)雜度是多少？ (2分)( )()0(，吟0( )NlogN解析：與上題屬于一個系列的，當(dāng)遇到基準元素的時候右指針都不停止移動，因為我們通常的寫法會先從右往左找一遍元素，在這道題目的條件下就已經(jīng)遍歷到最左邊了，此時基準元素就被安插到了最右邊，，因此時間復(fù)雜度為0()答案：D2-4對N個不同的數(shù)據(jù)采用冒泡算法進行從大到小的排序，下面哪種情況下肯定交換元素次數(shù)最多？ (1分).從小到大排好的.從大到小排好的.元素?zé)o序.元素基本有序解析：由顯然易得，選A,此時每次比較都要交換，太悲催了答案：A2-5對于7個數(shù)進行冒泡排序，需要進行的比較次數(shù)為： (2分)1.7142149解析：(6+5+4+3+2+1)/2=21答案：C2-6有組記錄的排序碼為｛46,79,56,38,40,84｝，則利用堆排序的方法建立的初始堆為： (2分)46,56,38,40,8079,56,46,40,3856,79,40,46,3879,56,38,40,461.79,2.84,3.84,4.84,解析：模擬堆排序建初始堆過程即可求解答案：D2-7采用遞歸方式對順序表進行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是： （2分）.每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù).每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù).遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān).遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)解析：A,B選項顯然很扯，兩部分分區(qū)處理都是3立的，不會減少遞歸次數(shù)， D選項肯定是有關(guān)的，不然也不會存在最壞時間復(fù)雜度答案：C2-8對N個記錄進行快速排序，在最壞的情況下，其時間復(fù)雜度是：（1分）O（N）O（NlogN）0（）0（解析：考察課本基礎(chǔ)知識答案：C2-9有組記錄的排序碼為{46,79,56,38,40,84},采用快速排序（以位于最左位置的對象為基準而）得到的第一次劃分結(jié)果為：（2分）{38,46,79,56,40,84}{38,79,56,46,40,84}{38,46,56,79,40,84}{40,38,46,56,79,84}解析：本題可以模擬快排過程去做，也可以根據(jù)快速排序第一次劃分結(jié)束后，基準元素左邊元素應(yīng)該都小于基準元素，右邊元素應(yīng)該都大于基準元素，故選D答案：D2-10對于序列{49,38,65,97,76,13,27,50},按由小到大進行排序，下面哪一個是初始步長為 4的希爾排序法第一趟的結(jié)果？ （2分）13,27,38,49,50,65,76,9749,13,27,50,76,38,65,9749,76,65,13,27,50,97,3897,76,65,50,49,38,27,13解析：觀察序列中的49,76,他們相距4并且已經(jīng)有序，然后第一趟排序后應(yīng)該位置不變，觀察選項中，只有滿足B選項答案：B2-11給定初始待排序列{15,9,7,8,20,-1,4}。如果希爾排序第一趟結(jié)束后得到序列為 {15,-1,4,8,9,7},則該趟增量為：（2分）1.1234解析：這道題的可以將選項帶進去驗證，比如帶入 D選項，發(fā)現(xiàn)在此增量下，元素都是有序的，故選解析：觀察序列中的49,76,他們相距4并且已經(jīng)有序，然后第一趟排序后應(yīng)該位置不變，觀察選項中，只有滿足B選項答案：B2-11給定初始待排序列{15,9,7,8,20,-1,4}。如果希爾排序第一趟結(jié)束后得到序列為 {15,-1,4,8,9,7},則該趟增量為：（2分）1.1234解析：這道題的可以將選項帶進去驗證，比如帶入 D選項，發(fā)現(xiàn)在此增量下，元素都是有序的，故選D答案：D2-12對N個元素采用簡單選擇排序，比較次數(shù)和移動次數(shù)分別為:(1分)1.0(0(0(0(),O(N)),O( )吸解)解析:考察為喇需知識NlogN答案:2-13對于10個數(shù)的簡單選擇排序，最壞情況下需要交換元素的次數(shù)為:(2分)1.936454.100解析：當(dāng)序列為逆序時，此時需要最大交換次數(shù)，為n-1答案：A2-14對N個記錄進行堆排序，最壞的情況下時間復(fù)雜度是:(1分)O(logN)O(N)O(NlogN)O(N2)解析：考察課本基礎(chǔ)知識答案：C2-15對N個記錄進行堆排序，需要的額外空間為： (1分)1.0(1)O(logN)0(N)O(NlogN)解析：考察課本基礎(chǔ)知識答案：A3.編程題排序-歸并排序與基數(shù)排序.判斷題1-1對N個記錄進行歸并排序，歸并趟數(shù)的數(shù)量級是 0( )。(2分)解析：考察課本基礎(chǔ)知識，并且要認真看題呀答案：F.單選題2-1對N個記錄進行歸并排序，歸并趟數(shù)的數(shù)量級是： (1分)O(logN)0(N)O(NlogN)0(N2)解析：仔細讀題即可答案：A2-2對N個記錄進行歸并排序，空間復(fù)雜度為： (1分)O(logN)0(N)O(NlogN)0(N2)解析：略答案：B2-3給出關(guān)鍵字序列｛431,56,57,46,28,7,331,33,24,63｝,下面哪個選擇是按次位優(yōu)先(LSD)鏈式基數(shù)排序進行了一趟分配和收集的結(jié)果？ (2分)f331—431—33—63—24—56—46—57—7-28f56—28—431—331—33—24—46—57—63—7f431—331—33—63—24—56—46—57—7-28f57—46—28—7-33—24—63—56—431—331解析：考察對基數(shù)排序的掌握，基數(shù)排序的方式可以采用 LSD(Leastsigni?cantdigital)或MSD(Mostsigni?cantdigital),LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。［隱藏］1效率2實現(xiàn)2.1C++2.2CO2.3Python2.4Lua53參考較獻答案：C2-4輸入105個只有一位數(shù)字的整數(shù)，可以用