數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)

窗體頂端數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)第9章：數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)試題1(2017年下半年試題57)設(shè)S是一個長度為n的非空字符串，其中的字符各不相同，則其互異的非平凡子串(非空且不同于S本身)個數(shù)為()。A.2n-1B.n2C.n(n+1)/2D.(n+2)(n-1)/2試題分析比如S字串為"abcdefg”,長度為7.則S中的包含的互不相同的字串有如下一些：.長度為6的個數(shù)為2："abcdef"和"bcdefg".長度為5的個數(shù)為3："abcde","bcdef","cdefg"..長度為1的個數(shù)為7："a","b","c","d","e","f","g"個數(shù)總和就是2+3+4+5+6+7=(1+2+3+..+7)-1=7x(7+1)/2-1.其中：1+2+3+...+n=(1+n)+(2+(n-1))+(3+(n-2))+...(首尾兩項相加的和都是門+1,共n/2個)=n(n+1)/2這個公式是初中數(shù)學里面的吧.試題答案C試題2(2017年下半年試題58)假設(shè)某消息中只包含7個字符{a,b,c,d,e,f,g},這7個字符在消息中出現(xiàn)的次數(shù)為{5,24,8,17,34,4,13},利用哈夫曼樹(最優(yōu)二叉樹)為該消息中的字符構(gòu)造符合前綴編碼要求的不等長編碼。各字符的編碼長度分別為()。A.a:4,b:2,c:3,d:3,e:2,f:4,g:3B.a:6,b:2,c:5,d:3,e:1,f:6,g:4C.a:3,b:3,c:3,d:3,e:3,f:2,g:3D.a:2,b:6,c:3,d:5,e:6,f:1,g:4試題分析哈夫曼樹試題答案A試題3(2017年下半年試題59)設(shè)某二叉樹采用二叉鏈表表示(即結(jié)點的兩個指針分別指示左、右孩子)。當該二叉樹包含k個結(jié)點時，其二叉鏈表結(jié)點中必有()個空的孩子指針。(59)A.k-1B.kC.k+1D.2k試題分析二叉樹的的二叉鏈表存儲結(jié)構(gòu)中每個結(jié)點有2個指針。每個結(jié)點有0個、1個或者2個空指針對應有2個、1個、0個非空指針。二叉樹中邊的個數(shù)等于非空指針的個數(shù)。假設(shè)二叉樹中節(jié)點的總個數(shù)為N,假設(shè)二叉樹中邊的個數(shù)為M假設(shè)二叉樹中度為0的結(jié)點的個數(shù)為n0,假設(shè)二叉樹中度為1的結(jié)點的個數(shù)為n1,假設(shè)二叉樹中度為2的結(jié)點的個數(shù)為n2.TOC\o"1-5"\h\z所以有n0+n1+n2=N (1)二叉樹中除了根結(jié)點之外，其他的結(jié)點都有一條便進入該結(jié)點，所以二叉樹中邊的總個數(shù)為M=N-1; (2)又M=n1+2*n2; (3)所以由(1)(2)(3)可得n0=n2+1; (4)設(shè)空節(jié)點的個數(shù)為K，則K=2*n0+n1 (5)結(jié)合(1)(4)(5)可以得到K=N+1.(空指針的的個數(shù)比結(jié)點總個數(shù)多1)由(2)可以知道邊數(shù)M=N-1;(二叉樹的邊數(shù)為結(jié)點個數(shù)減1)由(4)可以知道度為0的結(jié)點的個數(shù)(葉子結(jié)點個數(shù))=度為2的結(jié)點個數(shù)+1(n0=n2+1;)。試題答案C試題4(2017年下半年試題60)以下關(guān)于無向連通圖G的敘述中，不正確的是()。(60)A.G中任意兩個頂點之間均有邊存在B.G中任意兩個頂點之間存在路徑C.從G中任意頂點出發(fā)可遍歷圖中所有頂點D.G的鄰接矩陣是對稱矩陣試題分析無向連通圖不一定有邊，但兩個頂點之間有路徑。P460。試題答案(60)A試題5(2017年下半年試題61)兩個遞增序列A和B的長度分別為m和n(m<n且m與n接近)，將二者歸并為一個長度為m+n的遞增序列。當元素關(guān)系為()時，歸并過程中元素的比較次數(shù)最少。A.a1<a2<，yam-1<am<b1<b2<，ybn-1<bnB.b1<b2<-ybn-1<bn<a1<a2<-yam-1<amC.a1<b1<a2Vb2<-yam-1<bm-1<am<bm<bm+1v<bn-1<bnD.b1<b2<-ybm-1<bm<a1<a2<-yam-1<am<bm+1<-ybn-1<bn試題分析若A的最大元素小于B的最小元素，則只需要比較m次，這時歸并過程中元素的比較次數(shù)最少。試題答案(61)A試題6(2017年下半年試題62-63)求解兩個長度為n的序列X和Y的一個最長公共子序列(如序列ABCBDAB和BDCABA的一個最長公共子序列為BCBA)可以采用多種計算方法。如可以采用蠻力法，對X的每一個子序列，判斷其是否也是Y的子序列，最后求出最長的即可，該方法的時間復雜度為()。經(jīng)分析發(fā)現(xiàn)該問題具有最優(yōu)子結(jié)構(gòu)，可以定義序列長度分別為i和j的兩個序列X和Y的最長公共子序列的長度為C[i,j],如下式所示。( 0 Ki=0或j=0|c[ij]=jc[i-lj-1]+1 若i1j=。HXj=Yj(inax(C[f- -1]) 其它A.O(n2)B.O(n2Ign)C.O(n3)D.O(n2n)A.O(n2)B.O(n2Ign)C.O(n3)D.O(n2n)試題分析.X、Y的所有子序列都檢查過后即可求出X、丫的最長公共子序列。X的一個子序列相應于下標序列1,2,…，n的一個子序列。因此，X共有2M個子序列。當然，丫也有2Am個子序列。.動態(tài)規(guī)劃的一個計算最長公共子序列的方法如下，兩個序列X、Y：設(shè)有二維數(shù)組c[i][j]表示X的i位和Y的j位之前的最長公共子序列的長度，則有題干給定的函數(shù)表現(xiàn)形式其中，叫力當X的第i位與Y的第j位完全相同時為“1”，否則為“0”。此時，c[i][j]中最大的數(shù)便是X和Y的最長公共子序列的長度，依據(jù)該數(shù)組回溯，便可找出最長公共子序列。該算法的空間、時間復雜度均為O(nA2)。試題答案(62)D(63)A試題7(2017年下半年試題64-65)現(xiàn)需要對一個基本有序的數(shù)組進行排序。此時最適宜采用的算法為()排序算法，時間復雜度為()。(64)A.插入B.快速C.歸并D.堆(65)A.O(n)B.O(nlgn)C.O(n2)D.O(n2lgn)試題分析.快速排序(Quicksort)是對冒泡排序法的一種改進，它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列；在對一個基本有序的數(shù)組進行排序時適合采用快速排序法。.快速排序的平均運行時間為O(nlogn)。試題答案(64)B(65)B試題8(2017年上半年試題58)已知棧S初始為空，用I表示入棧、O表示出棧，若入棧序列為a1a2a3a4a5,則通過棧S得到出棧序列a2a4a5a3a1的合法操作序列()。(58)A.IIOIIOIOOOB.IOIOIOIOIOC.IOOIIOIOIOD.IIOOIOIOOO試題分析IIOIIOIOOO出棧序列為：a2a4a5a3alIOIOIOIOIO出棧序列為：ala2a3a4a5IOOIIOIOIO無合法出棧序列，因為入棧1個元素，出棧2個元素，會產(chǎn)生錯誤。IIOOIOIOOO無合法出棧序列，操作序列中4次入棧6次出棧也是會產(chǎn)生錯誤的。試題答案（58）A試題9（2017年上半年試題59）某二叉樹的先序遍歷序列為ABCDEF，中序遍歷序列為BADCFE，則該二叉樹的高度（即層數(shù)）為（）。（59）A.3B.4C.5D.6試題分析先序遍歷即先根后左子樹再右子樹，中序遍歷為先左子樹后跟再右子樹。先序遍歷的最開始結(jié)點A即為整棵樹的根，結(jié)合中序遍歷，A結(jié)點左側(cè)B即為根節(jié)點A的左子樹，右側(cè)DCFE則為A的右子樹，同理可以得出C為A的右子樹的根節(jié)點,D為C的左子樹，EF為C的右子B試題10（2017年上半年試題60）對于n個元素的關(guān)鍵宇序列{k1,k2,...kn},當且僅當滿足關(guān)系kWk2i且kWk2i+1{i=1.2...[n/2]}時稱其為小根堆（小頂堆）。以下序列中，（）不是小根堆。A.16,25,40,55,30,50,45B.16,40,25,50,45,30,55C.16,25,39.,41,45,43,50D.16,40,25,53,39,55,45試題分析D答案中第二個關(guān)鍵字小于第五個關(guān)鍵字，不滿足小根堆的條件。試題答案（60）D試題11（2017年上半年試題61）在12個互異元素構(gòu)成的有序數(shù)組a[1..12]中進行二分查找（即折半查找，向下取整），若待查找的元素正好等于a[9]，則在此過程中，依次與數(shù)組中的（）比較后，查找成功結(jié)束。（61）A. a[6]、a[7]、a[8]、a[9]a[6]、a[9]C.a[6]、a[7]、a[9]D.a[6]、a[8]、a[9]試題分析二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x<a[n/2],則只要在數(shù)組a的左半部分繼續(xù)搜索x,如果x>a[n/2],則只要在數(shù)組a的右半部搜索x.故查找順序如下圖所示：123456789101112試題答案B試題12（2017年上半年試題62-65）某汽車加工工廠有兩條裝配線L1和L2,每條裝配線的工位數(shù)均為n（Sij,i=1或2,j=1,2,...,n）,兩條裝配線對應的工位完成同樣的加工工作，但是所需要的時間可能不同（aij,i=1或2,j=1,2,...,n）。汽車底盤開始到進入兩條裝配線的時間（e1,e2）以及裝配后到結(jié)束的時間（X1X2）也可能不相同。從一個工位加工后流到下一個工位需要遷移時間（tij,i=1或2,j=2,...n）?，F(xiàn)在要以最快的時間完成一輛汽車的裝配，求最優(yōu)的裝配路線。分析該問題，發(fā)現(xiàn)問題具有最優(yōu)子結(jié)構(gòu)。以L1為例，除了第一個工位之外，經(jīng)過第j個工位的最短時間包含了經(jīng)過L1的第j-1個工位的最短時間或者經(jīng)過L2的第j-1個工位的最短時間，如式（1）。裝配后到結(jié)束的最短時間包含離開L1的最短時間或者離開L2的最短時間如式（2）。f二:一1，J Lmin｛萬@j-1.、力六二一藥廠若j=1其他（1）

(2(2)由于在求解經(jīng)過L1和L2的第j個工位的最短時間均包含了經(jīng)過L1的第j-1個工位的最短時間或者經(jīng)過L2的第j-1個工位的最短時間，該問題具有重復子問題的性質(zhì)，故采用迭代方法求解。該問題采用的算法設(shè)計策略是（），算法的時間復雜度為（）以下是一個裝配調(diào)度實例，其最短的裝配時間為（），裝配路線為（）（62）A.分治B.動態(tài)規(guī)劃心貪心D.回溯A.O(lgn)O(n)O(n2)O(nlgn)A.21B.23C.20D.26A.S11-S12-S13B.S11-S22-S13C.S21-S12-S23D.S21-S22-S23試題分析本題考查算法基礎(chǔ)。題目看似是非常復雜的，涉及到復雜的公式，以及算法邏輯，但如果我們先從后面兩個空來分析，問題就簡單得多。求最短裝配時間與裝配路線，其實是一個求最短路徑的過程。此時我們可以把從起點到各個結(jié)點的最短路徑逐步求出。經(jīng)過分析得出最短裝配路線為：S11->S22->S13,長度為21。解決了一個實際問題后，再來看所謂的迭代公式，其做法與之前手動求最短路徑一致，算法是用一個數(shù)組將起點到各個結(jié)點的最短路徑逐個求出，用已求出的最短路徑來分析后面的最短路徑，所以這符合動態(tài)規(guī)劃法的特征，算法策略應是動態(tài)規(guī)劃法。而算法的復雜度為O（n），因為用一個單重循環(huán)就可以解決這個問題。試題答案（62）B（63）B（64）A（65）B試題13（2016年下半年試題22）二維數(shù)組a[1..N，1..N]可以按行存儲或按列存儲。對于數(shù)組元素a[i,j]（1<=i,j<=N）,當（）時，在按行和按列兩種存儲方式下，其偏移量相同。（22）A.iWjB.i=jC.i>jD.i<j試題分析i和j相等，那么這時候的行列是一樣多的，則按行按列變得沒有區(qū)別試題答案（22）B試題14（2016年下半年試題57）拓撲序列是有向無環(huán)圖中所有頂點的一個線性序列，若有向圖中存在弧<v,w>或存在從頂點v到w的路徑，則在該有向圖的任一拓撲序列中，v一定在w之前。下面有向圖的拓撲序列是（）。(57)A.41235B.43125C.42135D.41325試題分析拓撲排序通俗一點來講，其實就是依次遍歷沒有前驅(qū)結(jié)點的結(jié)點。而某一時刻沒有前驅(qū)結(jié)點的結(jié)點有可能存在多個，所以一個圖的拓撲排序可能有多個。4號結(jié)點沒有前戲，所以拓撲排序的第一個元素是4。當4訪問完了就可以訪問1,1號訪問完了就可以訪問2,2號訪問完了就可以訪問3或5。所以拓撲排序結(jié)果為：412（35）。試題答案（57）A試題15（2016年下半年試題58-59）設(shè)有一個包含n個元素的有序線性表。在等概率情況下刪除其中的一個元素，若采用順序存儲結(jié)構(gòu)，則平均需要移動（）個元素；若采用單鏈表存儲，則平均需要移動（）個元素。（58）A.1B.(n-1)/2C.lognD.n(59)A.0B.1C.(n-1)/2D.n/2試題分析若用順序表存儲，則最好情況是刪除最后一個元素，此時不用移動任何元素，直接刪除，最差的情況是刪除第一個元素，此時需要移動n-1個元素，所以平均狀態(tài)是移動(n-1)/2。若用鏈表存儲，直接將需要刪除元素的前趨next指針指向后繼元素即可，不需要移動元素，所以移動元素個數(shù)為0。試題答案(58)B(59)A試題16(2016年下半年試題60)具有3個節(jié)點的二叉樹有()種形態(tài)。(60)A.2B.3C.5D.7試題分析N個節(jié)點(N>=2)的二叉樹有_" '試題答案(60)C試題17(2016年下半年試題61)以下關(guān)于二叉排序樹(或二叉查找樹、二叉搜索樹)的敘述中，正確的是()。(61)A.對二叉排序樹進行先序、中序和后序遍歷，都得到結(jié)點關(guān)鍵字的有序序列B.含有n個結(jié)點的二叉排序樹高度為［log2n」+1C.從根到任意一個葉子結(jié)點的路徑上，結(jié)點的關(guān)鍵字呈現(xiàn)有序排列的特點D.從左到右排列同層次的結(jié)點，其關(guān)鍵字呈現(xiàn)有序排列的特點試題分析二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若左子樹不空，則左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值；若右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值；左、右子樹也分別為二叉排序樹那么同層次的節(jié)點，右子樹大于根節(jié)點，根節(jié)點大于左子樹，則右子樹大于左子樹，則同層次有序排列。試題答案)D

試題18(2016年下半年試題62-63)下表為某文件中字符的出現(xiàn)頻率，采用霍夫曼編碼對下列字符編碼，則字符序列“bee”的編碼為()；編碼“110001001101”的對應的字符序列為()。ababcdf頻率憚)131215g5（62）A.10111011101B.10111001100C.001100100D.110011011A.badB.beeC.faceD.bace試題分析110001001101中:f(1100)a(0)c(100)e(1101)。試題答案(62)A(63)C試題19(2016年下半年試題64-65)兩個矩陣Am*n和Bn*p相乘，用基本的方法進行，則需要的乘法次數(shù)為m*n*p。多個矩陣相乘滿足結(jié)合律，不同的乘法順序所需要的乘法次數(shù)不同?？紤]采用動態(tài)規(guī)劃方法確定Mi,M(i+1),…，Mj多個矩陣連乘的最優(yōu)順序，即所需要的乘法次數(shù)最少。最少乘法次數(shù)用m[i,j]表示，其遞歸式定義為：..f 0 3卻”二上映㈤十用此十1/]十幾以月Ji<J其中i、j和k為矩陣下標，矩陣序列中Mi的維度為(pi-1)*pi采用自底向上的方法實現(xiàn)該算法來確定n個矩陣相乘的順序，其時間復雜度為()。若四個矩陣M1、M2、M3、M4相乘的維度序列為2、6、3、10、3,采用上述算法求解，則乘法次數(shù)為()。A.O(n2)(n2lgn)C.O(n3)D.O(n3lgn)(65)A.156B.144C.180D.360試題分析四個矩陣分別為：2*66*33*1010*3先計算：M1*M2及M3*M4,計算次數(shù)分別為:2*6*3=36,3*10*3=90。然后結(jié)果相乘，計算次數(shù)為：2*3*3=18。36+90+18=144。試題答案（64）C（65）B試題20（2016年上半年試題57）若元素以a，b，c，d，e的順序進入一個初始為空的棧中，每個元素進棧、出棧各1次，要求出棧的第一個元素為d，則合法的出棧序列共有（）種。（57）A.4B.5C.6D.24試題分析一共5個元素a,b,c,d,e，而d被要求作為第一個元素出棧。當d出棧后的情況應為：有一個元素e還未入棧，而棧中已有a，b，c。棧中的a，b，c出棧順序是已無可變性，必須是：c，b，a，此時，只是分析e在什么位置出棧即可。c，b，a，三個元素，有四個空位，所以可以產(chǎn)生的序列可能為：（1）d，e，c，b，a（2）d，c，e，b，a（3）d，c，b，e，a（4）d，c，b，a，e試題答案（57）A試題21（2016年上半年試題58）設(shè)有二叉排序樹（或二叉查找樹）如下圖所示，建立該二叉樹的關(guān)鍵碼序列不可能是（）。(58)A.233117191127139061B.231719312790611113C.231727193113119061D.233190612717191113試題分析注意27在31的后面可以得到答案C試題答案C試題22（2016年上半年試題59）若一棵二叉樹的高度（即層數(shù)）為h,則該二叉樹（）。A.有2h個結(jié)點B.有2h-1個結(jié)點C.最少有2h-1個結(jié)點D.最多有2h-1個結(jié)點試題分析一顆高度為h的二叉樹，結(jié)點數(shù)最多時，即為滿二叉樹。而高度為h的滿二叉樹有2h-1個結(jié)點，所以一棵二叉樹的高度（即層數(shù)）為h,則它最多有2h-1個結(jié)點。試題答案（59）D試題23（2016年上半年試題60）在13個元素構(gòu)成的有序表A[1..13]中進行折半查找（或稱為二分查找，向下取整）。那么以下敘述中，錯誤的是（）。A.無論要查找哪個元素，都是先與A[7]進行比較B.若要查找的元素等于A[9],則分別需與A[7]、A[11]、A[9]進行比較C.無論要查找的元素是否在A口中，最多與表中的4個元素比較即可D.若待查找的元素不在A口中，最少需要與表中的3個元素進行比較試題分析B選項錯誤之處在于，要查找a[9]元素，第一次比較的是A[7]（下標計算方法為：[1+13]/2=7）,第2次比較的是A[10]（下標計算方法為：[8+13]/2=10）。注意：題目要求計算下標時，向下取整。試題答案（60）B試題24（2016年上半年試題61）以下關(guān)于圖的遍歷的敘述中，正確的是（）。A.圖的遍歷是從給定的源點出發(fā)對每一個頂點僅訪問一次的過程B.圖的深度優(yōu)先遍歷方法不適用于無向圖C.使用隊列對圖進行廣度優(yōu)先遍歷D.圖中有回路時則無法進行遍歷試題分析隊列的特點是先進先出，廣度優(yōu)先剛好合適試題答案（61）C試題25（2016年上半年試題62-65）考慮一個背包問題，共有n=5個物品，背包容量為W=10,物品的重量和價值分別為：w={2,2,6,5,4},v={6,3,5,4,6},求背包問題的最大裝包價值。若此為0-1背包問題，分析該問題具有最優(yōu)子結(jié)構(gòu)，定義遞歸式為t0 若i=0或j=0\mctx{c(i-1J\c(i-1J- 其它其中c(i,j)表示i個物品、容量為j的0-1背包問題的最大裝包價值，最終要求解c(n,W)。采用自底向上的動態(tài)規(guī)劃方法求解，得到最大裝包價值為()，算法的時間復雜度為()。若此為部分背包問題，首先采用歸并排序算法，根據(jù)物品的單位重量價值從大到小排序，然后依次將物品放入背包直至所有物品放入背包中或者背包再無容量，則得到的最大裝包價值為()，算法的時間復雜度為()。A.11B.14C.15D.16.67A.0(nW)B.0(nlgn)C.0(n2)D.0(nlgnW)A.11B.14C.15D.16.67(65)A.0(nW)B.0(nlgn)C.0(n2)D.0(nlgnW)試題分析這是典型的01背包問題，動態(tài)規(guī)劃算法中，自底向上(遞推)：從小范圍遞推計算到大范圍，可以看到裝第一個和第五個物品價值是最高的，這時候V=12了，然后占了6的重量了，只能裝物品2了，價值15,第二個問題是部分背包，部分背包的時候計算每個物品單位重量價值多少，單位重量v={31.55/60.81.5},可以看到125的單位價值最高，選擇125后背包重量還只有8,還有2個重量可以選擇3得等5/3的價值，就是1.67,所以第三問為16.67再來看復雜度，都沒有進行指數(shù)級別的運算，問題1只需要找n個物品與價值W相乘，問題3計算單位物品價值然后考慮背包大小就可以了試題答案(62)C(63)A(64)D(65)B試題26(2015年下半年試題57)對于一個長度為n(n>1)且元素互異的序列，每其所有元素依次通過一個初始為空的棧后，再通過一個初始為空的隊列。假設(shè)隊列和棧的容量都足夠大，且只要棧非空就可以進行出棧操作，只要隊列非空就可以進行出隊操作，那么以下敘述中，正確的是()。(57)A.出隊序列和出棧序一定互為逆序B.出隊序列和出棧序列一定相同0入棧序列與入隊序列一定相同口.入棧序列與入隊序列一定互為逆序試題分析從題目的描述來看，出棧之后，直接入隊，然后出隊。所以：入隊序列上出棧序列，又因為出隊序列=入隊序列。所以出隊序列和出棧序列一定相同。試題答案(57)B試題27(2015年下半年試題58)設(shè)某n階三對角矩陣Anxn的示意圖如下圖所示。若將該三對角矩陣的非零元素按行存儲在一維數(shù)組B[k](1WkW3*n-2)中，則k與i、j的對應關(guān)系是()。(58)A.k=2i+j-2B.k=2i-j+2C.k=3i+j-1D.K=3i-j+2試題分析該題最簡單的解題思路是代入法。當i=1,j=1時，k=1。選項A：k=2i+j-2=2+1-2=1；選項B：k=2i-j+2=2-1+2=3；選項C：k=3i+j-1=3+1-1=3；選項D：k=3i-j+2=3+1+2=4。此時可以除排B,C,D,直接選A。若用一個例子，不能排除所有錯誤選項，則而舉一個例子來進行代入，排除更多錯誤選項。試題答案(58)A試題28（2015年下半年試題59）對于非空的二叉樹，設(shè)D代表根結(jié)點，L代表根結(jié)點的左子樹R代表根結(jié)點的右子樹。若對下圖所示的二叉樹進行遍歷后的結(jié)點序列為7654321，則遍歷方式是（）。（59）A.LRDB.DRLC.RLDD.RDL試題分析該題突破了常規(guī)的遍歷樹的方式，采用了新的遍歷方式。但是做題進行判斷時還是比較容易的，因為先根（包括根左右與根右左）的遍歷，則根結(jié)點3會是第1個訪問的結(jié)點；后根（左右根與根右左）的遍歷，則根結(jié)點3會是最后1個訪問的結(jié)點。給出的序列中3既不在第1個位置，也不在最后1個位置，所以先根后根都可除排，而A、B、C三個選項中，A與C是后根，B選項是先根，都可排除，只能選D。D是右根左的訪問方式，與結(jié)點序列完全吻合。試題答案D試題29（2015年下半年試題60）在55個互異元素構(gòu)成的有序表A[1..55]中進行折半查找（或二分查找，向下取整）。若需要找的元素等于A[19],則在查找過程中參與比較的元素依次為（）、A[19]。A.A[28]、A[30]、A[15]、A[20]B.A[28]、A[14]、A[21]、A[17]C.A[28]、A[15]、A[22]、A[18]D.A[28]、A[18]、A[22]、A[20]試題分析折半查找時，下標計算過程為（注：key的值與A[19]相同）：1、mid=[（1+55）/2]=28,^A[28]與key的值比較后，縮小查找范圍為：A[1]至A[27]；2、mid=[（1+27）/2]=14,^A[14]與key的值比較后，縮小查找范圍為：A[15]至A[27]；3、mid=[（15+27）/2]=21,^A[21]與key的值比較后，縮小查找范圍為：A[15]至A[20]；4、mid=[（15+20）/2]=17,^A[17]與key的值比較后，縮小查找范圍為：A[18]至A[20]；5、mid=[（18+20）/2]=19，rA[19]與key的值比較后，發(fā)現(xiàn)值相等，找到目標。試題答案（60）B試題30（2015年下半年試題61）設(shè)一個包含n個頂點、e條弧的簡單有向圖采用鄰接矩陣存儲結(jié)構(gòu)（即矩陣元素A[i][j]團等于1或0,分別表示頂點i與頂點j之間有弧或無弧)，則該矩陣購非零元素數(shù)目為()。A.eB.2eC.n-eD.n+e試題分析用鄰接矩陣存儲有向圖，圖中每一條弧對應矩陣一個非零元素，題目中提到一共有e條弧，所以一共e個非零元素。試題答案(61)A試題31(2015年下半年試題62-63)已知算法A的運行時間函數(shù)為T(n)=8T(n/2)+n2,其中n表示問題的規(guī)模，則該算法的時間復雜度為()。另已知算法B的運行時間函數(shù)為T(n)=XT(n/4)+n2,其中n表示問題的規(guī)模。對充分大的n,若要算法B比算法A快，則X的最大值為()。A.0(n)B.0(nlgn)C.0(n2)D.0(n3)A.15B.17C.63D.65試題分析本題需要用到特定形式的遞歸式分析法：設(shè)3蘭1和匕為常數(shù),設(shè)為一函數(shù).TUD百遞歸式=疔(曰)十f加)其中g(shù)指已和即可吸證明.略去上下去整不會對綠果造成影啊，那么可能有如下的漸進界(1)若麻，且是多項式的小于口即弓￡n露嘴f(n)=O(nlo?b-Fy則T(i。=日("嗨)⑵若f(n)=則Ttn)—0fifthslogn)［初若「心>11［電工且是多項式的大于*即3e>Or有Rn)=口(n1口晶且對Vc<1與所有足移大的n,有M.則T(n)=0(f(n))在本題中，a=8,b=2,故符合(1)的情況。時間復雜度為：O(n3)。a=16,b=4試題答案(62)D(63)C試題32(2015年下半年試題64-65)在某應用中，需要先排序一組大規(guī)模的記錄，其關(guān)鍵字為整數(shù)。若這組記錄的關(guān)鍵字基本上有序，則適宜采用()排序算法。若這組記錄的關(guān)鍵字的取值均在0到9之間(含)，則適宜采用()排序算法。(64)A.插入B.歸并C.快速D.計數(shù)(65)A.插入B.歸并C.快速D.計數(shù)試題分析插入排序中的希爾排序的基本思想是:先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。所以當數(shù)列基本有序時，采用插入排序算法是比較合適的。計數(shù)排序是一個非基于比較的排序算法，該算法于1954年由HaroldH.Seward提出。它的優(yōu)勢在于在對一定范圍內(nèi)的整數(shù)排序時，它的復雜度為O(n+k)(其中k是整數(shù)的范圍)，快于任何比較排序算法。試題答案(64)A(65)D試題33(2015年上半年試題57)設(shè)某循環(huán)隊列Q的定義中有front和rear兩個域變量，其中，front指示隊頭元素的位置，rear指示隊尾元素之后的位置，如下圖所示。若該隊列的容量為M,則其長度為()。(57)A.(Q.rear-Q.front+1)B.(Q.rcar-Q.front+M)C.(Q.rear-Q.front+1)%MD.(Q.rear-Q.front+M)%M試題分析本題考查數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識。根據(jù)圖示，可以計算得知(Q.rear-Q.front+M)%M為隊列中的元素個數(shù)(即隊列長度)。試題答案(57)D

試題34（2015年上半年試題58）設(shè)棧S和隊列Q的初始狀態(tài)為空，元素abcdef依次進入棧S。要求每個元素出棧后立即進入隊列Q，若7個元素出隊列的順序為bdfecag，則棧S的容量最小應該是（）。A.5B.4C.3D.2試題分析本題考查數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識。根據(jù)隊列的特點，元素出隊的順序與入隊的順序相同，因此，可知這7個元素的出棧順序為bdfecag。對于入棧序列abcdefg，得出出棧序列bdfecag的操作過程為：push（a入）、push（b入）、pop（b出）、push（c入）、push（d入）、pop（d出）、push（e入）、push（f入）、pop（f出）、pop（e出）、pop（c出）、pop（a出）、push（g入）、pop（g出），如下圖所示，從中可知棧S中元素最多時為4.因此，S的容量最小為4.試題答案B試題35（2015年上半年試題59）某二叉樹的先序遍歷序列為cabfedg，中序遍歷序列為abcdefg，則該二叉樹是（）。A.完全二叉樹B.最優(yōu)二叉樹C.平衡二叉樹D.滿二叉樹試題分析本題考查數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識。根據(jù)題中所給的遍歷序列，可知其對應的二叉樹如下圖所示。

C試題36（2015年上半年試題60）對某有序順序表進行折半查找時，（）不可能構(gòu)成查找過程中關(guān)鍵字的比較序列。A.45,10,30,18,25B.45,30,18,25,10C.10,45,18,30,25D.10,18,25,30,45試題分析本題考查數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識。進行折半查找時，首先與表中間位置上的元素進行比較，若待查找的元素大于中間元素，則接下來在后半?yún)^(qū)（是比中間元素更大者組成的杳序子表）進行折半查找，否則在前半?yún)^(qū)（是比中間元素更小者組成的有序子表）進行折半查找。二分查找過程可用二分查找判定樹來描述，即大于中間元素時走右分支，小于中間元素時走左分支，等于時查找成功結(jié)束。

選項選項A 選項B選項C 選項D顯然，選項B是不可能的查找路徑。試題答案B試題37（2015年上半年試題61）用某排序方法對一元素序列進行非遞減排序時，若該方法可保證在排序前后排序碼相同者的相對位置不變，則稱該排序方法是穩(wěn)定的。簡單選擇排序法排序方法是不穩(wěn)定的，（）可以說明這個性質(zhì)。（61）A.214821*6317B.172121*4863C.63214821*17D.21*17486321試題分析本題考查數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識。對選項A進行簡單選擇排序時，第一趟需交換17和21,導致21與21*的相對位置發(fā)生變化，最后的非遞減序列為1721*214863,說明簡單選擇排序是不穩(wěn)定的排序方法。試題答案（61）A試題38（2015年上半年試題62-63）優(yōu)先隊列通常采用（）數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，向優(yōu)先隊列中插入一個元素的時間復雜度為（）。（62）A.堆B.棧C.隊列D.線性表(63)A.0(n)B.0(1)C.0(Ign)D.0(n2)試題分析普通的隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊列尾追加，而從隊列頭刪除。在優(yōu)先隊列中，元素被賦予優(yōu)先級。當訪問元素時，具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊列具有最高級先出(largest-in,first-out)的行為特征。優(yōu)先隊列一般采用二叉堆數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，由于是二叉堆，所以插入和刪除一個元素的時間復雜度均為O(lgn)。試題答案(62)A(63)C試題39(2015年上半年試題64-65)在n個數(shù)的數(shù)組中確定其第i(1WiWn)小的數(shù)時，可以采用快速排序算法中的劃分思想對n個元素劃分，先確定第k小的數(shù)，根據(jù)i和k的大小關(guān)系,進一步處理，最終得到第i小的數(shù)。劃分過程中，最佳的基準元素選擇的方法是選擇待劃分數(shù)組的()元素。此時，算法在最壞情況下的時間復雜度為(不考慮所有元素均相等的情況)()。(64)A.第一個B.最后一個C.中位數(shù)D.隨機一個5)A.0(n)0(lgn)C.0(nlgn)D.0(n2)試題分析本題考查算法設(shè)計與分析的相關(guān)知識。中位數(shù)的含義：將一組數(shù)據(jù)按照由小到大(或由大到小)的順序排列，如果數(shù)據(jù)的個數(shù)是奇數(shù)，則處于中間位置的數(shù)就是這組數(shù)據(jù)的中位數(shù)；如果數(shù)據(jù)的個數(shù)是偶數(shù)，則中間兩個數(shù)據(jù)的平均數(shù)就是這組數(shù)據(jù)的中位數(shù)。根據(jù)題干的描述，選擇的基準元素將數(shù)組分得越均勻越好，因此中位數(shù)是最佳選擇。對于該問題，若每次都是選擇中位數(shù)作為基準元素，則時間復雜度的遞歸式為：T(n)=T(n/2)+cn求解該遞歸式，得到T(n)=0(n)。試題答案(64)C(65)D試題40(2014年下半年試題57)對于線性表，相對于順序存儲，采用鏈表存儲的缺點是()。A.數(shù)據(jù)元素之間的關(guān)系需要占用存儲空間，導致存儲密度不高B.表中結(jié)點必須占用地址連續(xù)的存儲單元，存儲密度不高0插入新元素時需要遍歷整個鏈表，運算的時間效率不高D.刪除元素時需要遍歷整個鏈表，運算的時間效率不高試題分析鏈表最大的優(yōu)點是沒有大小限制也就是說它是動態(tài)的。。你可以任意添加大小通過結(jié)構(gòu)體你可以將很多相關(guān)的數(shù)據(jù)放到一起。。但是因為鏈表在內(nèi)存里存放是不連續(xù)的。所以你不能快速的查找和修改。鏈表存儲的缺點為數(shù)據(jù)元素之間的關(guān)系需要占用存儲空間，導致存儲密度不高。試題答案（57）A試題41（2014年下半年試題58）若一個棧初始為空，其輸入序列是1，2,3,…，n-1，n，其輸出序列的第一個元素為k（1WkW「n/2」），則輸出序列的最后一個元素是（）。A.值為n的元素B.值為1的元素C.值為n-k的元素D.不確定的試題分析本題考查數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識。以n等于4舉例說明。輸入序列為1234，輸出序列的第一個元素可以為1或2。若為1，則輸出序列可能為1234、1243、1342、1324、1432；若為2，則輸出序列為2134、2143、2314、2341、2431。試題答案（58）D試題42（2014年下半年試題59）某個二叉查找樹（即二叉排序樹）中進行查找時，效率最差的情形是該二叉查找樹是（）。（59）A.完全二叉樹B.平衡二叉樹C.單枝樹D.滿二叉樹試題分析單枝樹時該二叉查找樹效率最低。試題答案C試題43（2014年下半年試題60）在字符串的KMP模式匹配算法中，需先求解模式串的next函數(shù)值，其定義如下式所示，j表示模式串中字符的序號（從1開始）。若模式串p為"abaac"，則其next函數(shù)值為（）。產(chǎn)1='血西｛幻1MM上應必上必_i'='兄』_i憶—41P品JJ 其他情況A.01234B.01122C.01211D.01111試題分析本題考查字符串的模式匹配運算知識。KMP是進行字符串模式匹配運算效率較高的算法。根據(jù)對next函數(shù)的定義，模式串前兩個字符的next值為0、1。對于第3個字符"a"，其在模式串中的前綴為“ab"，從該子串找不出前綴和后綴相同的部分，因此，根據(jù)定義，該位置字符的next值為1。對于第4個字符"a"，其在模式串中的前綴為"aba"，該子串只有長度為1的前綴“a"和后綴"a"相同，根據(jù)定義，該位置字符的next值為2。對于第5個字符"a"，其在模式串中的前綴為“abaa0"，該子串只有長度為1的前綴“a"和后綴"a"相同，根據(jù)定義，該位置字符的next值為2。綜上可得，模式串"abaac"的next函數(shù)值為01122。試題答案(60)B試題44(2014年下半年試題61-62)快速排序算法在排序過程中，在待排序數(shù)組中確定一個元素為基準元素，根據(jù)基準元素把待排序數(shù)組劃分成兩個部分，前面一部分元素值小于等于基準元素，而后面一部分元素值大于基準元素。然后再分別對前后兩個部分進一步進行劃分。根據(jù)上述描述，快速排序算法采用了()算法設(shè)計策略。日知確定基準元素操作的時間復雜度為0(n)，則快速排序算法的最好和最壞情況下的時間復雜度為()。(61)A.分治B.動態(tài)規(guī)劃0貪心D.回溯(62)A.0(n)和0(nlgn)B.0(n)和0(n2)C.0(nlgn)和0(nlgn)D.0(nlgn)和0(n2)試題分析類別排序方法時間堂雜度空間裝雜費穩(wěn)定性平均銀K最壞情況輔助存苗插入排序直接插入0(n)OCn)得定0（；」）0(；)口⑴不稔定施擇排序直重陲0(D-)OCd-)0(1：不穩(wěn)定堆持序OQnlo5nlOQnlosn\0(1)不稻泥交攜排序?冒泡排序0(；)口⑴穩(wěn)定快速蚱樂Ofnlo^n)OS)OQag□).不苕定犯并持序Ofnloed)0叱n〕穩(wěn)定基數(shù)排序□CdWt財OCd(KW)ocdtn)釐定試題答案(61)A(62)D試題45（2014年下半年試題63）對一待排序序列分別進行直接插入排序和簡單選擇排序，若待排序序列中有兩個元素的值相同，則（）保證這兩個元素在排序前后的相對位置不變。（63）A.直接插入排序和簡單選擇排序都可以B.直接插入排序和簡單選擇排序都不能C.只有直接插入排序可以D.只有簡單選擇排序可以試題分析直接插入排序才是穩(wěn)定的排序算法。試題答案（63）C試題46（2014年下半年試題64-65）已知一個文件中出現(xiàn)的各字符及其對應的頻率如下表所示。若采用定長編碼，則該文件中字符的碼長應為（）。若采用Huffman編碼，則字符序列“face”的編碼應為（）。字符1bCd&f頻率（%）45131210gA.2B.3C.4D.5A.110001001101B.001110110011C.101000010100D.010111101011試題分析本題考查Huffman編碼的相關(guān)知識。字符在計算機中是用二進制表示的，每個字符用不同的二進制編碼來表示。碼的長度影響存儲空間和傳輸效率。若是定長編碼方法，用2位碼長，只能表示4個字符，即00、01、10和11；若用3位碼長，則可以表示8個字符，即000、001、010、011、100、101、110、111。對于題中給出的例子，一共有6個字符，因此采用3位碼長的編碼可以表示這些字符。Huffman編碼是一種最優(yōu)的不定長編碼方法，可以有效的壓縮數(shù)據(jù)。要使用Huffman編碼，除了知道文件中出現(xiàn)的字符之外，還需要知道每個字符出現(xiàn)的頻率。下圖（a）是題干中給出對應的編碼樹，可以看到，每個字符及其對應編碼為圖b），因此字符序列"face”的編碼應為110001001101，即65選擇A。（a）100由100由16（b）字符編碼a0b101c100d111e1101f1100試題答案（64）B（65）A試題47（2014年上半年試題57）若對線性表的最常用操作是訪問任意指定序號的元素，并在表尾加入和刪除元素，則適宜采用（）存儲。（57）A.順序表B.單鏈表0雙向鏈表D.哈希表試題分析考查線性表的特性題意：對線性表的最常用操作是訪問任意指定序號的元素，并在表尾加入和刪除元素。要訪問任意指定序號的元素，最快速的訪問方式自然是采用數(shù)組存儲（順序表），但采用數(shù)組存儲時，在數(shù)組中間位置或者頭部插入、刪除元素效率太低，需要移動大量元素，而題意中在表尾加入和刪除元素，則正好消除了這種缺陷。試題答案（57）A試題48（2014年上半年試題58-59）二叉樹如右圖所示，若進行順序存儲（即用一維數(shù)組元素存儲該二叉樹中的結(jié)點且通過下標反映結(jié)點間的關(guān)系，例如，對于下標為i的結(jié)點，其左孩子的下標為2i、右孩子的下標為2i+1）,則該數(shù)組的大小至少為（）；若采用三叉鏈表存儲該二叉樹（各個結(jié)點包括結(jié)點的數(shù)據(jù)、父結(jié)點指針、左孩子指針、右孩子指針），則該鏈表的所有結(jié)點中空指針的數(shù)目為（）。B.10C.12D.15A.6B.8C.12D.14試題分析用一維數(shù)組元素存儲該二叉樹中的結(jié)點且通過下標反映結(jié)點間的關(guān)系，實際上存儲的是這棵二叉樹對應的完全二叉樹，因此需要的存儲空間為2n-1=15（n為二叉樹層數(shù)）。如下圖所示：采用三叉鏈表存儲該二叉樹（各個結(jié)點包括結(jié)點的數(shù)據(jù)、父結(jié)點指針、左孩子指針、右孩子指針）；如下圖所示：左孩子父節(jié)點節(jié)點較痛右孩子左孩子父節(jié)點節(jié)點較痛右孩子空指針數(shù)量為8。試題答案（58）D（59）B試題49（2014年上半年試題60）某雙端隊列如下所示，要求元素進出隊列必須在同一端口，即從A端進入的元素必須從A端出、從B端進入的元素必須從B端出，則對于4個元素的序列el、e2、e3、e4,若要求從前2個元素（el、e2）從A端口按次序全部進入隊列，后兩個元素（03、e4）從B端口按次序全部進入隊列，則可能得到的出隊序列是（）。A 雙端隊列 B（60）A.el、e2、e3、e4B.e2、e3、e4、elC.e3、e4、el、e2D.e4、e3、e2、el試題分析el、e2從A端口進入，e3、e4從B端口進入，如下圖所示:A 雙端隊列 B根據(jù)題意：從A端進入的元素必須從A端出、從B端進入的元素必須從B端出；則出隊順序中e2在el前面，e4在e3前面。只有答案D滿足。試題答案（60）D試題50（20l4年上半年試題6l）實現(xiàn)二分查找（折半查找）時，要求查找表（）。（6l）A.順序存儲，關(guān)鍵碼無序排列B.順序存儲，關(guān)鍵碼有序排列0雙向鏈表存儲，關(guān)鍵碼無序排列口.雙向鏈表存儲，關(guān)鍵碼有序排列試題分析二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。算法要求：①必須采用順序存儲結(jié)構(gòu)②必須按關(guān)鍵字大小有序排列。試題答案(61)B試題51(2014年上半年試題62-63)在某個算法時間復雜度遞歸式T(n)=T(n-1)+n，其中n為問題的規(guī)模，則該算法的漸進時間復雜度為()，若問題的規(guī)模增加了16倍，則運行時間增加()倍。(62)A.0(n)B.0(nlgn)C.0(n2)D.0(n2lgn)(63)A.16B.64C.256D.1024試題分析由于遞歸式為：T(n)=T(n-1)+n。我們可以把一個規(guī)模為n的時間復雜度算出來。分析過程為：T(n)=T(n-1)+n；T(n-1)=T(n-2)+n-1；T(n-2)=T(n-3)+n-2； T(n)=1+2+..+n-1+n。這是一個典型的等差數(shù)列。用數(shù)列求和公式有：((1+n)*n)/2。這樣就求得時間復雜度為：0(n2)。后面一問則有：當問題規(guī)模為n時，時間復雜度0(n2)。當x=16n時，時間復雜度0(x2)=0((16n)2)=0(256n2)。試題答案(62)C(63)C試題52(2014年上半年試題64-65)Prim算法和Kruscal算法都是無向連通網(wǎng)的最小生成樹的算法，Prim算法從一個頂點開始，每次從剩余的頂點加入一個頂點，該頂點與當前生成樹中的頂占的連邊權(quán)重最小，直到得到最小生成樹開始，Kruscal算法從權(quán)重最小的邊開始，每次從不在當前的生成樹頂點之間的邊中選擇權(quán)重最小的邊加入，直到得到一顆最小生成樹，這兩個算法都采用了()設(shè)計策略，且()。(64)A.分治3.貪心C.動態(tài)規(guī)劃D.回溯(65)A.若網(wǎng)較稠密，則Prim算法更好B.兩個算法得到的最小生成樹是一樣的C.Prim算法比Kruscal算法效率更高D.Kruscal算法比Prim算法效率更高試題分析本題考查算法設(shè)計與分析的基礎(chǔ)知識。Prim算法從擴展頂點開始，每次總是“貪心的"選擇與當前頂點集合中距離最短的頂點，而Kruscal算法從擴展邊開始，每次總是“貪心的”選擇剩余的邊中最小權(quán)重的邊，因此兩個算法都是基于貪心策略進行的。Prim算法的時間復雜度為O(n2)，其中n為圖的頂點數(shù)，該算法的計算時間與圖中的邊數(shù)無關(guān)，因此該算法適合于求邊稠密的圖的最小生成樹； Kruscal算法的時間復雜度為O(mlgm)，其中m為圖的邊數(shù)，該算法的計算時間與圖中的頂點數(shù)無關(guān)，因此該算法適合于求邊稀疏的圖的最小生成樹。當圖稠密時，用Prim算法效率更高。但若事先沒有關(guān)于圖的拓撲特征信息時，無法判斷兩者的優(yōu)劣。由于一個圖的最小生成樹可能有多棵，因此不能保證用這兩種算法得到的是同一棵最小生成樹。試題答案(64)B(65)A試題53(2013年下半年試題57)以下關(guān)于線性表存儲結(jié)構(gòu)的敘述，正確的是()。(57)A.線性表采用順序存儲結(jié)構(gòu)時，訪問表中任意一個指定序號元素的時間復雜度為常量級B.線性表采用順序存儲結(jié)構(gòu)時，在表中任意位置插入新元素的運算時間復雜度為常量級C.線性表采用鏈式存儲結(jié)構(gòu)時，訪問表中任意一個指定序號元素的時間復雜度為常量級D.線性表采用鏈式存儲結(jié)構(gòu)時，在表中任意位置插入新元素的運算時間復雜度為常量級試題分析線性表采用順序存儲結(jié)構(gòu)時，訪問表中任意一個指定序號元素的時間復雜度為常量級，因為順序存儲結(jié)構(gòu)訪問元素時，能直接定位元素，這樣，操作的時間復雜度為O(1)。試題答案(57)A試題54(2013年下半年試題58)設(shè)循環(huán)隊列Q的定義中有front和size兩個域變量，其中front表示隊頭元素的指針，size表示隊列的長度，如下圖所示(隊列長度為3,隊頭元素為x,隊尾元素為z)。設(shè)隊列的存儲空間容量為M,則隊尾元素的指針為()。

Q.frcntA.(Q.front+Q.size-1)(Q.front+Q.size-1+M)%M(Q.front-Q.size)(Q.front-Q.size+M)%M試題分析本題考查循環(huán)隊列隊尾指針的計算方法。從圖示可以看出，要得到z的值可進行Q.front+Q.size-1操作，但在此不容忽視的一個問題是，循環(huán)隊列在進行了多次入隊出隊操作之后，Q.front+Q.size-1有可能大于M，如Q.front指向M-1空間時，Q.front+Q.size-1=M+1,這已超出隊列長度，所以需要讓其與M進行求模操作，修正位置號。試題答案(58)B試題55(2013年下半年試題59)在一個有向圖G的拓撲序列中，頂點Vi排列在Vj之前，說明圖G中()。A.一定存在弧<vi,vj>B.一定存在弧<vj,vi>C.可能存在vi到vj的路徑，而不可能存在vj到vi的路徑D.可能存在vj到vi的路徑，而不可能存在vi到vj的路徑試題分析拓撲序列是拓撲排序的產(chǎn)出物。對一個有向無環(huán)圖G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v,若邊(u,v)￡E(G),則u在線性序列中出現(xiàn)在v之前。由此可見，如果Vi排列在Vj之前，說明可能存在vi到vj的路徑，而不可能存在vj到vi的路徑。試題答案(59)C試題56(2013年下半年試題60)以下關(guān)于哈夫曼樹的敘述，正確的是()。A.哈夫曼樹一定是滿二叉樹，其每層結(jié)點數(shù)都達到最大值B.哈夫曼樹一定是平衡二叉樹，其每個結(jié)點左右子樹的高度差為■1、0或1C.哈夫曼樹中左孩子結(jié)點的權(quán)值小于父節(jié)點、右孩子節(jié)點的權(quán)值大于父節(jié)點D.哈夫曼樹中葉子節(jié)點的權(quán)值越小則距離樹根越遠、葉子結(jié)點的權(quán)值越大則距離樹根越近試題分析給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，稱這樣的二

叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。所以D選項的說法正確。試題答案(60)D試題57(2013年下半年試題61)某哈希表(散列表)的長度為n，改散列函數(shù)為H(Key)=Keymodp,采用線性探測法解決沖突。以下關(guān)于P值的敘述中，正確的是()。(61)A.p的值一般為不大于n且最接近n的質(zhì)數(shù)B.p的值一般為大于n的任意整數(shù)C.p的值必須為小于n的合數(shù)D.p的值必須等于n試題分析在采用散列表進行數(shù)據(jù)存儲時，散列函數(shù)中p的取值是非常重要的，因為該取值直接影響沖突發(fā)生率，所以p的值一般會取接近于元素個數(shù)n但是要小于n的質(zhì)數(shù)。例如你n取20,那么P最好是19。試題答案A試題58(2013年下半年試題62-63)對n個基本有序的整數(shù)進行排序，若采用插入排序算法，則時間和空間復雜度分別為()；若采用快速排序算法，則時間和空間復雜度分別為()。A.O(n2)和O(n)B.O(n)和O(n)C.O(n2)和O(1)D.O(n)和O(1)A.O(n2)和O(n)B.O(nlgn)和O(n)C.O(n2)和O(1)D.O(nlgn)和O(1)試題分析本題考查算法分析的基礎(chǔ)知識。排序和查找是基本的計算問題。存在很多相關(guān)的算法，不同的算法適用于不同的場合。不同的數(shù)據(jù)輸入特點相同的算法也有不同的計算時間。若數(shù)據(jù)基本有序，對插入排序算法而言，則可以在近似線性時間內(nèi)完成排序。即O(n)；而對于快速排序而言，則是其最壞情況，需要二次時間才能完成排序，即O(n2)。兩個算法在排序時僅需要一個額外的存儲空間，即空間復雜度為常數(shù)O(1)。試題答案(62)D(63)C試題59(2013年下半年試題64-65)在求解某問題時,經(jīng)過分析發(fā)現(xiàn)該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，求解過程中子問題被重復求解，則采用()算法設(shè)計策略；若定義問題的解空間，以深度優(yōu)先的方式搜索解空間，則采用()算法設(shè)計策略。(64)A.分治B.動態(tài)規(guī)劃0貪心D.回溯(65)A.動態(tài)規(guī)劃3貪心C.回溯D.分支限界試題分析分治法的設(shè)計思想是將一個難以直接解決的大問題分解成一些規(guī)模較少的相同問題以便各個擊破，分而治之。動態(tài)規(guī)劃法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是獨立的。若用分治法來解這類問題，則相同的子問題會被求解多次，以至于最后解決原問題需要耗費指數(shù)級時間。貪心法經(jīng)常用于解決最優(yōu)化問題，但他的最優(yōu)往往是從局部最優(yōu)來考慮的，每一步都選最優(yōu)的方案，但這種方案不一定能得到整體上的最優(yōu)解。回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根節(jié)點出發(fā)搜索解空間樹。題目描述中提到，需要解決的問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，且求解過程中子問題被重復求解，這種情況下如果采用分治法，效率會很低，所以應采用動態(tài)規(guī)劃法。而'以深度優(yōu)先的方式搜索解空間”則明顯是在采用回溯法。試題答案(64)B(65)C試題60(2013年上半年試題51)采用順序表和單鏈表存儲長度為n的線性序列，根據(jù)序號查找元素，其時間復雜度分別為()。(51)A.0(1)0(1)B.0(1)0(N)C.O(N)0(1)D.0(N)0(N)試題分析順序表是在計算機內(nèi)存中以數(shù)組的形式保存的線性表，是指用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)。順序存儲結(jié)構(gòu)的主要優(yōu)點是節(jié)省存儲空間，因為分配給數(shù)據(jù)的存儲單元全用存放結(jié)點的數(shù)據(jù)，結(jié)點之間的邏輯關(guān)系沒有占用額外的存儲空間。采用這種方法時，可實現(xiàn)對結(jié)點的隨機存取，即每一個結(jié)點對應一個序號，由該序號可以直接計算出來結(jié)點的存儲地址。鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(鏈表中每一個元素稱為結(jié)點)組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。鏈表（Linkedlist）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針（Pointer）。由于不必按順序存儲，鏈表在插入的時候可以達到O⑴的復雜度，比另一種線性表：順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O（n）的時間，而順序表相應的時間復雜度分別是O（logn）和O⑴。試題答案（51）B試題61（2013年上半年試題52）設(shè)元素序列a，b，c，d，e，f經(jīng)過初始為空的棧S后，得到出棧序列cedfba，則棧S的最小容量為（）。A.3B.4C.5D.6試題分析此題考查棧的用法，根據(jù)題中出棧的順序，當元素c出棧后，棧中有元素a、b，當元素e出棧之前，棧中由元素a、b、d、e，此時棧中的元素達到最多。因此棧S中最小容量為4。試題答案B試題62（2013年上半年試題53）輸出受限的雙端隊列是指元素可以從隊列的兩端輸入，但只能從隊列的一端輸出，如下圖所示，若有e1，e2,e3,e4依次進入輸出受限的雙端隊列，則得不到輸出序列（）。輸出受限的雙揣隊列A.e4，e3，e2，e1B.e4，e2，e1，e3C.e4，e3，e1，e2D.e4，e2，e3，e1試題分析此題考查隊列的用法，題中給出的受限雙端隊列，兩端都可以進，一端出。假設(shè)分A和B端，B端可以進出，由D選項出序列，可以看出e1、e2、e3按順序從A端進入，而e4從B端進入，當e4從B端出來后，無法將后面的e2出隊列。試題答案（53）D試題63（2013年上半年試題60-61）考慮下述背包問題的實例。有5件物品，背包容量為100，每件物品的價值和重量如下表所示，并已經(jīng)按照物品的單位重量價值從大到小排好序，根據(jù)物品單位重量價值大優(yōu)先的策略裝入背包中，則采用了（）設(shè)計策略?？紤]0/1背包問題（每件物品或者全部放入或者全部不裝入背包）和部分背包問題（物品可以部分裝入背包），求解該實例，得到的最大價值3.貪心C.動態(tài)規(guī)劃D.回溯（61）A.605和630B.605和605C.430和630D.630和430試題分析本題考查貪心算法和背包問題的知識點。貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。0/1背包考慮該問題時，只能放入1、2、3號物品，故總價值為430，采用部分背包問題可以將物品拆分，故放1、2、3號物品后還可以放入部分4號物品，故總?cè)萘繛?30。試題答案（60）B（61）C試題64（2013年上半年試題62-63）給定n個整數(shù)構(gòu)成的數(shù)組A={a1,a2,…,an}和整數(shù)x,判斷A中是否存在兩個元素ai和aj，使得ai+aj=x。為了求解該問題，首先用歸并排序算法對數(shù)組A進行從小到大排序；然后判斷是否存在ai+aj=x，具體如下列偽代碼所示，則求解該問題時排序算法應用了（）算法設(shè)計策略，整個算法的時間復雜度為（）i=1;j=nwhilei<jifai+aj=xreturntrueelseifai+aj>xj--;elsei++;returnfalse;（62）A.分治3.貪心C.動態(tài)規(guī)劃D.回溯A.O(n)B.O(nlgn)C.O(n2)D.O(nlg2n)試題分析分治算法的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題，這些子問題相互獨立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。試題答案(62)A(63)B試題65(2013年上半年試題64)一個高度為h的滿二叉樹的結(jié)點總數(shù)為2h-1,從根結(jié)點開始，自上而下、同層次結(jié)點從左至右，對結(jié)點按照順序依次編號，即根結(jié)點編號為1,其左、右孩子結(jié)點編號分別為2和3,再下一層從左到右的編號為4、5、6、7,依此類推。那么，在一棵滿二叉樹中，對于編號為m和n的兩個結(jié)點，若n=2m+1^()。A.m是n的左孩子B.m是n的右孩子C.n是m的左孩子D.n是m的右孩子試題分析由于該二叉樹為滿二叉樹，除最后一層無任何子節(jié)點外，每一層上的所有結(jié)點都有兩個子結(jié)點(最后一層上的無子結(jié)點的結(jié)點為葉子結(jié)點)。滿二叉樹的性質(zhì)可知父結(jié)點m和右孩子之間的關(guān)系式n=2m+1。試題答案(64)D試題66(2013年上半年試題65)以下關(guān)于哈希(Hash,散歹IJ)查找敘述中，正確的是()。A.哈希函數(shù)應盡可能復雜些，以消除沖突B.構(gòu)造哈希函數(shù)時應盡量使關(guān)鍵字的所有組成部分都能起作用C.進行哈希查找時，不再需要與查找表中的元素進行比較D.在哈希表中只能添加元素不能刪除元素試題分析哈希表根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上并以關(guān)鍵字在地址集中的“象”作為相應記錄在表中的存儲位置。所以在構(gòu)造哈希函數(shù)使應盡量使關(guān)鍵字的所有組成部分起作用。試題答案(65)B試題67(2012年下半年試題57)在字符串的模式匹配過程中，如果模式串的每個字符依次和主事中一個連續(xù)的字符序列相等，則稱為匹配成功。如果不能在主串中找到與模式串相同的子串，則稱為匹配失敗。在布魯特―福斯模式匹配算法（樸素的或基本的模式匹配）中，若主串和模式串的長度分別為n和m（且n遠大于m），且恰好在主串末尾的m個字符處匹配成功，則在上述的模式匹配過程中，字符的比較次數(shù)最多為（）。（57）A.n*m（n-m+1）*m（n-m-1）*m（n-m）*n試題分析本題主要考查字符串的匹配。在本題的描述中，告訴我們是在主串末尾的m個字符處匹配成功，那么在這之前，從左到右依次匹配了n-m次，且都失敗了，最壞的情況，就是每次匹配都是匹配到最后一個字符不符合，因此每次匹配的比較次數(shù)就是子串的長度，即m。而匹配成功時，一共也比較了m次。所以字符的比較次數(shù)最多為（n-m+1）*m次。試題答案（57）B試題68（2012年下半年試題58）試題分析本題考查二叉樹的遍歷。二叉樹的主要遍歷方式有：前序遍歷、中序遍歷、后序遍歷、層次遍歷。如果已知中序遍歷，并知道前序遍歷與后序遍歷中的任意一個，便可得到一棵唯一的二叉樹。具體是怎么做的呢？利用的是遍歷的特點。中序遍歷的順序是：左、根、右。而后序遍歷的順序是：左、右、根?；氐筋}目里面來，從“后序遍歷序列為KBFDCAE”，可以得知，二叉樹的根結(jié)點為：E（此時已經(jīng)可以排除選項C與選項D了）。繼續(xù)分析，由“中序遍歷序列為BKEFACD"，可以得知，二叉樹的左子樹包括結(jié)點：BK。右子樹包括結(jié)點：FACD。重復上面的步驟，對左子樹與左子樹看成獨立的兩棵樹進行分析。在后序遍歷中，左子樹的結(jié)點BK的順序為“KB"，所以B是根結(jié)點；右子樹的結(jié)點FACD的順序為“FDCA”，所以右子樹的根結(jié)點為A。當分析到這一步時，已經(jīng)可以得到本題答案為A。試題答案（58）A試題69（2012年下半年試題59）在13個元素構(gòu)成的有序表M[1..13]中進行折半查找（向下取整），若找到的元素為M[4],則被比較的元素依次為（）。（59）A.M[7]、M[3]、M[5]、M[4]B.M[7]、M[5]、M[4]C.M[7]、M[6]、M[4]D.M[7]、M[4]試題分析整個查找的過程為：（1+13）/2=7,因此首先與第7元素比較，由于要查找的元素在其前面，因此用（1+7-1）/2=3,然后與第3個元素比較，由于待查找在其后面，因此用（3+1+6）/2=5,因此接下來與第5個元素進行比較，最后再與第4個元素比較，找到了M[4]。試題答案（59）A試題70（2012年下半年試題60）拓撲排序是將有向圖中所有頂點排成一個線性序列的過程，并且該序列滿足：若在AOV網(wǎng)中從頂點Vi到Vj有一條路徑，則頂點VI必然在頂點Vj之前。對于下面所示的有向圖，（）是其拓撲序列。(60)A.1234576B.1235467C.2135476D.2134567試題分析本題考查數(shù)據(jù)結(jié)構(gòu)中的拓撲排序。拓撲排序通俗一點來講，其實就是依次遍歷沒有前驅(qū)結(jié)點的結(jié)點。而某一時刻沒有前驅(qū)結(jié)點的結(jié)點有可能存在多個，所以一個圖的拓撲排序可能有多個。以本題為例，1號結(jié)點與2號結(jié)點都沒有前驅(qū)結(jié)點，所以拓撲排序的第一個元素可以是1，也可以是2。當1與2都訪問完了，便可訪問3號結(jié)點，3號結(jié)點訪問完了，便可訪問5號結(jié)點，訪問完5號結(jié)點，可訪問4號，或是7號結(jié)點。所以拓撲排序結(jié)果為：(12)35(47)6。括號中有多個數(shù)字，則代表在這多個數(shù)字的順序可以變化。這樣，具體的拓撲排序結(jié)果為：1235476、1235746、2135476、2135746。試題答案(60)C試題71(2012年下半年試題61)下圖所示為一棵M階B-樹，M最有可能的值為()。A.1B.2C.3D.4試題分析本題主要考查B-樹的概念。一棵m階的B-樹，或者為空樹，或為滿足下列特性的m叉樹：(1)樹中每個結(jié)點至多有m棵子樹；(2)若根結(jié)點不是終端結(jié)點，則至少有2棵子樹；(3)除根結(jié)點之外的所有非終端結(jié)點至少有［m/2］棵子樹；(4)所有的非終端結(jié)點中包含信息數(shù)據(jù)(n,P0,K1,P1,K2,P2,...,Kn,Pn),其中：Ki(1WWn)是關(guān)鍵字，并且Ki<ki+1(1WWn-1)；Pi(0WiWn)是指向子樹根結(jié)點的指針，而且指針Pi-1所指子樹中所有結(jié)點的關(guān)鍵字均小于關(guān)鍵字Ki(1WiWn),并且均大于關(guān)鍵字Ki-1(2WiWn)；第一個指針P0所指子樹中所有結(jié)點的關(guān)鍵字均小于K1,最后一個指針Pn所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn；n是結(jié)點中關(guān)鍵字的個數(shù)，有［m/2］-1WnWm-1。(5)所有的葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息。這些結(jié)點實際上并不存在，如果查找進入葉子結(jié)點，則說明查找失敗。從題目給出的圖來看，最多一個節(jié)點有4棵子樹，最少一個節(jié)點有2棵子樹，因此這個B-樹最有可能是一棵4階的B-樹。試題答案D試題72(2012年下半年試題62-63)將數(shù)組｛1,1,2,4,7,5｝從小到大排序，若采用()排序算法，則元素之間需要進行的比較次數(shù)最少，共需要進行()次元素之間的比較。A.直接插入B.歸并C.堆D.快速A.5B.6C.7D.8試題分析本題主要考查排序算法。本題給出的數(shù)組如果采用直接插入排序，那么其排序過程如下：首先1和1比較找到合適的插入位置，然后2和1比較，找到合適的插入位置；然后4和2比較，找到4的合適插入位置，然后7和4比較，找到7的合適插入位置，然后5和7比較，因為5比7小，因此要與4比較，然后就找到了5的合適位置，整個排序過程結(jié)束?？偟谋容^次數(shù)為1+1+1+1+2=6次。歸并排序的算法思想是將兩個相鄰的有序子序列歸并為一個有序序列，然后再將新產(chǎn)生的相鄰序列進行歸并，當只剩下一個有序序列時算法結(jié)束。其過程如下：1和1比較，然后歸并，2和4比較，然后歸并，7和5比較，然后歸并，解析來將再將［1,1］和［2,4］歸并，用2分別與兩個1比較得到［1,1,2,4］,然后再用［1,1,2,4］與［5,7］歸并。這時，用5與［1,1,2,4］中每個元素分別比較一次，最后即可得到整個有序序列?？偟谋容^次數(shù)為：1+1+1+2+4=9次。堆排序的基本思想是先將序列建立堆，然后輸出堆頂元素，再將剩下的序列建立堆，然后再輸出堆頂元素，依此類推，直到所有元素均輸出為止。因此在堆排序過程中，最重要的就是建堆。本題中給出的數(shù)組序列就是一個小頂堆，然后輸出堆頂，將剩下的部分調(diào)整為小頂堆，調(diào)整的過程為，首先將最后一個元素5置換到堆頂，然后用5與左孩子結(jié)點比較，由于大于左孩子，因此與其置換位置，然后值為5的結(jié)點仍然大于其左孩子結(jié)點，再置換位置，這樣就得到了新的小頂堆，這個過程總共比較2次。后面的排序過程是同樣的道理。本題采用堆排序算法總共的比較次數(shù)為7次。快速排序的基本思想是：（1）以某個元素為支點（通常是第一個元素），通過比較關(guān)鍵碼和交換記錄，將待排序的序列分成兩個區(qū)間。其中左區(qū)間中所有元素的關(guān)鍵字均不大于支點元素的關(guān)鍵字，而右區(qū)間中所有元素的關(guān)鍵字均不小于支點元素的關(guān)鍵字。稱此過程為一次劃分；（2）分別對左右區(qū)間的待排序序列，再按照以上方法進行劃分，直到整個序列按關(guān)鍵字有序為止。由于本題給出的例子基本是從小到大有序，不適合采用快速排序發(fā)，其總共需要的比較次數(shù)為15次。試題答案（62）A（63）B試題73（2012年下半年試題64-65）霍夫曼編碼將頻繁出現(xiàn)的字符采用短編碼，出現(xiàn)頻率較低的字符采用長編碼。具體的操作過程為：i）以每個字符的出現(xiàn)頻率作為關(guān)鍵字構(gòu)建最小優(yōu)先級隊列；ii）取出關(guān)鍵字最小的兩個結(jié)點生成子樹，根節(jié)點的關(guān)鍵字為孩子節(jié)點關(guān)鍵字之和，并將根節(jié)點插入到最小優(yōu)先級隊列中，直至得到一顆最優(yōu)編碼樹?；舴蚵幋a方案是基于（）策略的。用該方案對包含a到f六個字符的文件進行編碼，文件包含