數(shù)據(jù)結(jié)構(gòu)試題庫答案

數(shù)據(jù)結(jié)構(gòu)試題及答案一、單項(xiàng)選擇題(1)一個(gè)算法應(yīng)該是（）。A)程序B)問題求解步驟的描述C)要滿足五個(gè)基本屬性D)A和C(2)算法指的是（）。A)計(jì)算機(jī)程序B)解決問題的計(jì)算方法C)排序算法D)解決問題的有限運(yùn)算序列。(3)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（）。A)存儲結(jié)構(gòu)B)邏輯結(jié)構(gòu)C)算法D)操作(4)從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A)動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B)順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C)線性結(jié)構(gòu)、非線性結(jié)構(gòu)D)初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)(5)下列敘述中正確的是()。）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)C）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率(6) 數(shù)據(jù)的基本單位是（ ）A)數(shù)據(jù)項(xiàng)B)數(shù)據(jù)類型C)數(shù)據(jù)元素(7)下列程序的時(shí)間復(fù)雜度為（）i=0；s=0；while（s<n）{i++；s=s+i；}A)O（n）B)O（2n）C)O（n）(8)下列程序段的漸進(jìn)時(shí)間復(fù)雜度為（）。for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)A[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n)程序段如下：sum=0；for(i=1;i<=n;i++)

數(shù)據(jù)變量D)O（n2）D）(m+n)for(j=1;j<=n;j++)sum++；其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）。A）O(n）B)O(nlogn)C)O(n3)D)O(n2)(10)在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;i>=n;i++)for(j=1;j>=n;j++)x:=x+1;A)O(2n)B)O(n)C)O(n2)D)O(log2n)(11)程序段for(i:=n-1;i<=1;i--）for(j:=1;j>=i;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）。A)O(n）B)O(nlogn)C)O(n3)D)O(n2)設(shè)有一個(gè)遞歸算法如下：intfact(intn){/*大于等于0*/if(n<=0)return1;elsereturnn*fact(n-1);}則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。A)nB)n+1C)n+2D)n-1(13)下述程序段中語句①的頻度是（）。s=0;for(i=1;i<m;i++)for(j=0;j<=i;j++)s+=j;A)(m1)(m1)B)m(m1)C)(m2)(m1)D)m(m1)2222(14)若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則最節(jié)省運(yùn)算時(shí)間的存儲方式是（）。A)單鏈表B)僅有頭指針的單循環(huán)鏈表C)雙鏈表D)僅有尾指針的單循環(huán)鏈表(1)求循環(huán)鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時(shí)間復(fù)雜度分別是（）。A)O(n)和O(1)B)O(1)和O(1)C)O(1)和O(n)D)O(n)和O(n)(15)求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時(shí)間復(fù)雜度分別是（）。A)O（n）和O（1）B)O（1）和O（1）C)O（1）和O（n）D)O(n)和O（n）(16)非空的單循環(huán)鏈表的頭指針為head,尾指針為rear，則下列條件成立的是（）。A)rear->next==headB)rear->next->next==headC)head->next==rearD)head->next->next==rear(17)從一個(gè)長度為n的順序表中刪除第i個(gè)元素（1≤i≤n）時(shí)，需向前移動(dòng)的元素的個(gè)數(shù)是（）。A)n-i B)n-i+1 C)n-i-1 D)i已知一個(gè)有序表為（13，18，24，35，47，50，62，83，90，115，134），當(dāng)二分檢索值為90的元素時(shí)，檢索成功需比較的次數(shù)是（ ）。A)1B)2C)3D)4(19)假設(shè)以行優(yōu)先順序存儲三維數(shù)組R[6][9][6]，其中元素R[0][0][0]的地址為2100，且每個(gè)元素占4個(gè)存儲單元，則存儲地址為2836的元素是（）。A)R[3][3][3]B)R[3][3][4]C)R[4][3][5]D)R[4][3][4](20)設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式以行序?yàn)橹餍虼鎯?，a00為第一個(gè)元素，其存儲地址為0，每個(gè)元素占有1個(gè)存儲地址空間，則a45的地址為（）。A)13B)35C)17D)36(21)線性表采用鏈?zhǔn)酱鎯r(shí)，節(jié)點(diǎn)的存儲的地址（）。A)必須是不連續(xù)的B)連續(xù)與否均可C)必須是連續(xù)的D)和頭節(jié)點(diǎn)的存儲地址相連續(xù)(22)用鏈表表示線性表的優(yōu)點(diǎn)是（）。A)便于隨機(jī)存取B)花費(fèi)的存儲空間比順序表少C)數(shù)據(jù)元素的物理順序與邏輯順序相同D)便于插入與刪除(23)鏈表不具有的特點(diǎn)是（）。A)插入、刪除不需要移動(dòng)元素B)可隨機(jī)訪問任一元素C)不必事先估計(jì)存儲空間D)所需空間與線性長度成正比(24)在長度為n的順序表中刪除第i個(gè)元素(1≤i≤時(shí)n)，元素移動(dòng)的次數(shù)為()。A)n-i+1B)iC)i+1D)n-i(25)采用順序搜索方法查找長度為n的順序表示，搜索成功的平均搜索長度為（）。A)nB)n/2C)(n-1)/2D)(n+1)/2(26)將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）。A)O(1)B)O(n)C)O(m)D)O(m+n)(27)若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則該鏈表為空的判定條件是()。A)head==NULL B)head->next==NULL C)head!=NULL D)head->next==head某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲方式最節(jié)省運(yùn)算時(shí)間。A)單鏈表B)僅有頭指針的單循環(huán)鏈表C)雙鏈表D)僅有尾指針的單循環(huán)鏈表(29)若允許表達(dá)式內(nèi)多種括號混合嵌套，則為檢查表達(dá)式中括號是否正確配對的算法，通常選用的輔助結(jié)構(gòu)是（）。A)棧B)線性表C)隊(duì)列D)二叉排序樹(30)順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語句為（）。A)s.elem［top］=e；s.top=s.top+1；B)s.elem［top+1］=e；s.top=s.top+1；C)s.top=s.top+1；s.elem［top+1］=e；D)s.top=s.top+1；s.elem［top］=e；循環(huán)隊(duì)列sq中，用數(shù)組elem［0··25］存放數(shù)據(jù)元素，sq.front指示隊(duì)頭元素的前一個(gè)位置，sq.rear指示隊(duì)尾元素的當(dāng)前位置， 設(shè)當(dāng)前 sq.front 為20，sq.rear為12，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。A)8B)16C)17D)18(32)鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是（）。A)插入操作更加方便B)通常不會(huì)出現(xiàn)棧滿的情況C)不會(huì)出現(xiàn)?？盏那闆rD)刪除操作更加方便(33)一個(gè)遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運(yùn)行時(shí)間來看，通常遞歸過程比非遞歸過程（）。A)較快B)較慢C)相同D)不定p1,p2,p3,??，pn若(34)若已知一個(gè)棧的入棧序列是1,2,3,4??n，其輸出序列為p1==n,則pi為（）。A)iB)n==iC)n-i+1D)不確定(35)一個(gè)棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是()。A)edcbaB)decbaC)dceabD)abcde若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列是()。A)2，4，3，1，5，6B)3，2，4，1，6，5C)4，3，2，1，5，6D)2，3，5，1，6，4(37)對于棧操作數(shù)據(jù)的原則是（）。A)先進(jìn)先出B)后進(jìn)先出C)后進(jìn)后出D)不分順序(38)棧和隊(duì)列的共同點(diǎn)是（）。A)都是先進(jìn)先出B)都是先進(jìn)后出C)只允許在端點(diǎn)處插入和刪除元素D)沒有共同點(diǎn)(39)一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是（）。A)4,3,2,1B)1,2,3,4C)1,4,3,2D)3,2,4,1設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出對操作后其頭指針front值為（）。A) front=front+1C) front=(front-1)%m

B) front=(front+1)%(m-1)D) front=(front+1)%m(41) 引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是

(

)。A) 出隊(duì)

B)入隊(duì)

C) 取隊(duì)頭元素

D)取隊(duì)尾元素(2)

設(shè)以數(shù)組

A[m]

存放循環(huán)隊(duì)列的元素，其頭尾指針分別為

front

和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（

）。A）

(rear-front+m)%m

B）

rear-front+1

C）(front-rear+m)%m

D）(rear-front)%m(42) 二維數(shù)組

A[12][18]

采用列優(yōu)先的存儲方法，若每個(gè)元素各占

3個(gè)存儲單元，且

A[0][0]

地址為150，則元素

A[9][7]

的地址為

(

)。A)429

B)432

C)435

D)438設(shè)有一個(gè)10階的對稱矩陣A[10][10]，采用壓縮方式按行將矩陣中下三角部分的元素存入一維數(shù)組B[]中，A[0][0]存入B[0]中，則A[8][5]在B[]中（）位置。A)32B)33C)41D)65(44)若對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對角線上所有元素)依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中確定aij（i<j）的位置k的關(guān)系為()。A)i*(i-1)/2+jB)j*(j-1)/2+iC)i*(i+1)/2+jD)j*(j+1)/2+i(45)對稀疏矩陣進(jìn)行壓縮存儲目的是（）。A)便于進(jìn)行矩陣運(yùn)算B)便于輸入和輸出C)節(jié)省存儲空間D)降低運(yùn)算的時(shí)間復(fù)雜度(46)對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是()。A)(e,f)B)((e,f))C)(f)D)()(47)設(shè)廣義表L=（（a,b,c）），則L的長度和深度分別為（）。A)1和1B)1和3C)1和2D)2和3(48)樹中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)加（）。A)0B)1C)-1D)2(49)在一棵具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，所有結(jié)點(diǎn)的空域個(gè)數(shù)等于（）。A)nB)n-1C)n+1D)2*n(50)某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A)空或只有一個(gè)結(jié)點(diǎn)B)高度等于其節(jié)點(diǎn)數(shù)C)任一結(jié)點(diǎn)無左孩子D)任一結(jié)點(diǎn)無右孩子(51)含有10個(gè)結(jié)點(diǎn)的二叉樹中，度為0的結(jié)點(diǎn)數(shù)為4，則度為2的結(jié)點(diǎn)數(shù)為（）A)3B)4C)5D)6(52)除第一層外，滿二叉樹中每一層結(jié)點(diǎn)個(gè)數(shù)是上一層結(jié)點(diǎn)個(gè)數(shù)的（）A)1/2倍B)1倍C)2倍D)3倍(53)對一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號，則編號為49的結(jié)點(diǎn)，它的父結(jié)點(diǎn)的編號為（）A)24B)25C)98D)99(54)可以惟一地轉(zhuǎn)化成一棵一般樹的二叉樹的特點(diǎn)是（）A)根結(jié)點(diǎn)無左孩子B)根結(jié)點(diǎn)無右孩子C)根結(jié)點(diǎn)有兩個(gè)孩子D)根結(jié)點(diǎn)沒有孩子設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）。A)2hB)2h-1C)2h+1D)h+1(56)在一棵度為3的樹中，度為3的節(jié)點(diǎn)個(gè)數(shù)為2，度為2的節(jié)點(diǎn)個(gè)數(shù)為1，則度為0的節(jié)點(diǎn)個(gè)數(shù)為（）。A)4B)5C)6D)7(57)設(shè)森林F對應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵子樹的結(jié)點(diǎn)個(gè)數(shù)是（）。A)m-nB)m-n-1C)n+1D)條件不足，無法確定(58)將一株有100個(gè)節(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次進(jìn)行編號，根節(jié)點(diǎn)的編號為1，則編號為49的節(jié)點(diǎn)的左孩子編號為（）。A)98B)89C)50D)沒有孩子(59)下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是(A)(60)樹最適合用來表示（）。A)有序數(shù)據(jù)元素B)無序數(shù)據(jù)元素C)元素之間具有分支層次關(guān)系的數(shù)據(jù)D)元素之間無聯(lián)系的數(shù)據(jù)(61)在一個(gè)非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）。A)只有右子樹上的所有結(jié)點(diǎn)B)只有右子樹上的部分結(jié)點(diǎn)C)只有左子樹的上的部分結(jié)點(diǎn)D)只有左子樹上的所有結(jié)點(diǎn)(62)任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中相對次序（）。A)不發(fā)生改變B)發(fā)生改變C)不能確定D)以上都不對(63)在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（）。A)不確定B)2nC)2n+1D)2n-1(64)權(quán)值為{1,2,6,8}的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（）。A)18B)28C)19D)29(65)對一個(gè)滿二叉樹，m個(gè)樹葉，k個(gè)分枝結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，則（）。A)n=m+1B)m+1=2nC)m=k-1D)n=2k+1(66)在含有n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）。A)eB)2eC)n2-eD)n2-2e(67)若采用鄰接矩陣翻存儲一個(gè)n個(gè)頂點(diǎn)的無向圖，則該鄰接矩陣是一個(gè)（）。A)上三角矩陣B)稀疏矩陣C)對角矩陣D)對稱矩陣(68)在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。A)1/2B)1C)2D)4(69)在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。A)1/2B)1C)2D)4(70)對于含n個(gè)頂點(diǎn)和e條邊的圖，采用鄰接矩陣表示的空間復(fù)雜度為（）。A)O（n）B)O(e)C)O(n+e)D)O(n2)(71)如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用（）。A)深度優(yōu)先搜索算法B)廣度優(yōu)先搜索算法C)求最小生成樹的prim算法D)拓?fù)渑判蛩惴?72)n個(gè)頂點(diǎn)的連通圖至少中含有()。A)n-1B)nC)n+1D)0(73)n個(gè)頂點(diǎn)的完全有向圖中含有()。A)n-1條有向邊B)n條有向邊C)n(n-1)/2條有向邊D)n(n-1)條有向邊(74) 假設(shè)一個(gè)有 n個(gè)頂點(diǎn)和 e條弧的有向圖用鄰接表表示，則刪除預(yù)某個(gè)頂點(diǎn) vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（ ）。A)O(n)B)O(e)C)O(n+e)D)O(n*e)(75)在無向圖中定義頂點(diǎn)Vi域Vj之間的路徑為從Vi到達(dá)Vj的一個(gè)（）。A)頂點(diǎn)序列B)邊序列C)權(quán)值總和D)邊的條數(shù)(76)無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。A)a,b,e,c,d,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,e,d,f,c,b下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）。A)求節(jié)點(diǎn)的度B)拓?fù)渑判駽)求最短路徑D)求關(guān)鍵路徑(78)圖的廣度優(yōu)先搜索類似于樹的（）次序遍歷。A)先根B)中根C)后根D)層次(79)在圖采用鄰接表存儲時(shí)，求最小生成樹的Prim算法的時(shí)間復(fù)雜度為()。A)O(n)B)O(n+e)C)O(n2)D)O(n3)(80)已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓?fù)湫蛄惺牵ǎ?。A)V1,V3,V4,V6,V2,V5,V7B)V1,V3,V2,V6,V4,V5,V7C)V1,V3,V4,V5,V2,V6,V7D)V1,V2,V5,V3,V4,V6,V7(81)關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）。A)從源點(diǎn)到匯點(diǎn)的最長路徑B)從源點(diǎn)到匯點(diǎn)的最短路徑C)最長回路D)最短回路(82)有n個(gè)結(jié)點(diǎn)的有向完全圖的弧數(shù)是（）。A)n2B)2nC)n(n-1)D)2n(n+1)(83)設(shè)圖的鄰接鏈表如題12圖所示，則該圖的邊的數(shù)目是（）。題圖A)4B)5C)10D)20(84)在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（）倍。A)1/2B)1C)2D)4(85)在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。A)1/2B)1C)2D)4(86)有8個(gè)結(jié)點(diǎn)的無向圖最多有（）條邊。A)14B)28C)56D)112(87)有8個(gè)結(jié)點(diǎn)的無向連通圖最少有（）條邊。A)5B)6C)7D)8(88)有8個(gè)結(jié)點(diǎn)的有向完全圖有（）條邊。A)14B)28C)56D)112(89)用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用（）來實(shí)現(xiàn)算法的。A)棧B)隊(duì)列C)樹D)圖(90)用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用（）來實(shí)現(xiàn)算法的。A)棧B)隊(duì)列C)樹D)圖(91)已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。0 1 1 1 1 011 0 0 1 0 011 0 0 0 1 001 1 0 0 1 101 0 1 1 0 100 0 0 1 1 011 1 0 0 0 10A)0243156 B)0136542 C) 0423165 D)0361542建議：0134256(92) 已知圖的鄰接矩陣同上題 8，根據(jù)算法，則從頂點(diǎn) 0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。A)0243156B)0135642C)0423165D)0134256(93)已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。A)0243651B)0136425C)0423156D)0134256（建議：0123456）(94)已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。A)0243165B)0135642C)0123465D)0123456(95)已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。A)132B)0231C)0321D)0123(96)已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。A)0321 B) 0123 C) 0132 D) 0312(97)深度優(yōu)先遍歷類似于二叉樹的（）。A)先序遍歷B)中序遍歷C)后序遍歷D)層次遍歷(98)廣度優(yōu)先遍歷類似于二叉樹的（）。A)先序遍歷B)中序遍歷C)后序遍歷D)層次遍歷(99)任何一個(gè)無向連通圖的最小生成樹（）。A)只有一棵B)一棵或多棵C)一定有多棵D)可能不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最小的情況唯一）(100)在分析折半查找的性能時(shí)常常加入失敗節(jié)點(diǎn)，即外節(jié)點(diǎn)，從而形成擴(kuò)充的二叉樹。若設(shè)失敗節(jié)點(diǎn)i所在層次為Li，那么查找失敗到達(dá)失敗點(diǎn)時(shí)所做的數(shù)據(jù)比較次數(shù)是（）。A)Li+1B)Li+2C)Li-1D)Li(101)向一個(gè)有127個(gè)元素原順序表中插入一個(gè)新元素并保存原來順序不變，平均要移動(dòng)（）個(gè)元素。A)8B)63.5C)63D)7(102)由同一組關(guān)鍵字集合構(gòu)造的各棵二叉排序樹()。其形態(tài)不一定相同，但平均查找長度相同其形態(tài)不一定相同，平均查找長度也不一定相同其形態(tài)均相同，但平均查找長度不一定相同其形態(tài)均相同，平均查找長度也都相同(103)衡量查找算法效率的主要標(biāo)準(zhǔn)是（）。A)元素的個(gè)數(shù)B)所需的存儲量C)平均查找長度D)算法難易程度(104)適合對動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）。A) 有序表 B)分塊有序表 C)二叉排序樹 D)快速排序(3) 能進(jìn)行二分查找的線性表 ,必須以（ ）。順序方式存儲，且元素按關(guān)鍵字有序鏈?zhǔn)椒绞酱鎯?，且元素按關(guān)鍵字有序順序方式存儲，且元素按關(guān)鍵字分塊有序鏈?zhǔn)椒绞酱鎯?，且元素按關(guān)鍵字分塊有序(105)為使平均查找長度達(dá)到最小 ,當(dāng)由關(guān)鍵字集合 {05,11,21,25,37,40,41,62,84} 構(gòu)建二叉排序樹時(shí) ,第一個(gè)插入的關(guān)鍵字應(yīng)為（ ）A)5B)37C)41D)62(106)對關(guān)鍵字序列(56,23,78,92,88,67,19,34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為()。A)(19,23,56,34,78,67,88,92)B)23,56,78,66,88,92,19,34)C)(19,23,34,56,67,78,88,92)D)(19,23,67,56,34,78,92,88)(107) 用某種排序方法對關(guān)鍵字序列 {35,84,21,47,15,27,68,25,20} 進(jìn)行排序時(shí)，序列的變化情況如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則采用的方法是（ ）。A)直接選擇排序B)希爾排序C)堆排序D)快速排序(108)一組記錄的排序碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的第一次劃分結(jié)果為（）。A)38,40,46,56,79,84B)40,38,46,79,56,84C)40,38,46,56,79,84D)40,38,46,84,56,79(109)快速排序在最壞情況下的時(shí)間復(fù)雜度是（）22A)O(nlog2n)B)O(n)C)O(nlog2n)D)O(log2n)(110)下列排序算法中不穩(wěn)定的是（）。A)直接選擇排序B)折半插入排序C)冒泡排序D)快速排序(111)對待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對兩個(gè)子序列進(jìn)行同樣的排序操作，直到子序列為空或只剩下一個(gè)元素為止。這樣的排序方法是（）。A)直接選擇排序B)直接插入排序C)快速排序D)冒泡排序(112)將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較（）次。A)8B)9C)10D)25(113)排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（）。A)選擇排序B)快速排序C)冒泡排序D)插入排序(114)排序算法中，不穩(wěn)定的排序是（）。A)直接插入排序B)冒泡排序C)堆排序D)選擇排序(115)排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（）.A)希爾排序B)冒泡排序C)插入排序D)選擇排序(116)從未排序序列中挑選元素，并將其依次插入已排序序列（初始時(shí)為空）的一端的方法，稱為（）。A)希爾排序B)歸并排序C)插入排序D)選擇排序(117)對ｎ個(gè)不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（）A)從小到大排列好的B)從大到小排列好的C)元素?zé)o序D)元素基本有序(118)對ｎ個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為（）。A)n+1B)nC)n-1D)n(n-1)/2(119)快速排序在下列哪種情況下最易發(fā)揮其長處。（）被排序的數(shù)據(jù)中含有多個(gè)相同排序碼被排序的數(shù)據(jù)已基本有序被排序的數(shù)據(jù)完全無序被排序的數(shù)據(jù)中的最大值和最小值相差懸殊(120)對有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（）。A)O(n)B)O(n2)C)O(nlog2n)D)O(n3)(121)若一組記錄的排序碼為（46,79,56,38,40,84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A)38,40,46,56,79,84B)40,38,46,79,56,84C)40,38，46,56,79,84D)40,38,46,84,56,79下列關(guān)鍵字序列中，（）是堆。A)16,72,31,23,94,53B)94,23,31,72,16,53C)16,53,23,94，31,72D)16,23,53,31,94,72(123)堆是一種（）排序。A)插入B)選擇C)交換D)歸并(124)堆的形狀是一棵（）。A)二叉排序樹B)滿二叉樹C)完全二叉樹D)平衡二叉樹(125)若一組記錄的排序碼為（46,79,56,38,40,84），則利用堆排序的方法建立的初始堆為（）。A)79,46,56,38,40,84B)84,79,56,38,40,46C)84,79,56,46,40,38D)84,56,79,40,46,38(126)下述幾種排序方法中，要求內(nèi)存最大的是（）。A)插入排序B)快速排序C)歸并排序D)選擇排序(127)有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4），用堆排序的篩選方法建立的初始堆為（）。A)-1，4，8，9，20，7，15，7B)-1，7，15，7，4，8，20，9C)-1，4，7，8，20，15，7，9D)A，B，C均不對。51．下列四個(gè)序列中，哪一個(gè)是堆（）。A)75,65,30,15,25,45,20,10B)75,65,45,10,30,25,20,15C)75,45,65,30,15,25,20,10D)75,45,65,10,25,30,20,15(129)以下序列不是堆的是()。A)(100,85,98,77,80,60,82,40,20,10,66)B)(100,98,85,82,80,77,66,60,40,20,10)C)(10,20,40,60,66,77,80,82,85,98,100)D)(100,85,40,77,80,60,66,98,82,10,20)(130)快速排序方法在（）情況下最不利于發(fā)揮其長處。A)要排序的數(shù)據(jù)量太大B)要排序的數(shù)據(jù)中含有多個(gè)相同值C)要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D)要排序的數(shù)據(jù)已基本有序(131)對關(guān)鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結(jié)果為（）。A)(2,5,12,16)26(60,32,72)B)(5,16,2,12)28(60,32,72)C)(2,16,12,5)28(60,32,72)D)(5,16,2,12)28(32,60,72)(132)對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是（）。A){21,25,5,17,9,23,30}B){25,23,30,17,21,5,9}C){21,9,17,30,25,23,5}D){5,9,17,21,23,25,30}二、填空題(133)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 操作對象 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。(134)數(shù)據(jù)結(jié)構(gòu)被形式地定義為（ D,R），其中 D是 數(shù)據(jù)元素 的有限集合， R是D上的 關(guān)系 有限集合。(135)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容。(136)數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。(138)在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)后續(xù)結(jié)點(diǎn)。(139)在樹形結(jié)構(gòu)中， 樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) 。(140)在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 。(141)數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序、鏈?zhǔn)?、索引和散列?142)數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。(143)一個(gè)算法的效率可分為時(shí)間效率和空間效率。(144)對于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合，線性表，樹，圖四種。(145)順序映象的特點(diǎn)是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映象的特點(diǎn)是借助是指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。任何一個(gè)算法的設(shè)計(jì)取決于選定邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲結(jié)構(gòu)。數(shù)據(jù)類型是一組___________性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。數(shù)據(jù)對象是___________性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如果操作不改變原邏輯結(jié)構(gòu)的“值”，而只是從中提取某些信息作為運(yùn)算結(jié)果，則稱該類運(yùn)算為 型運(yùn)算。引用(149)算法的 健壯特性是指做為一個(gè)好的算法， 當(dāng)輸入的數(shù)據(jù)非法時(shí)， 也能適當(dāng)?shù)刈龀稣_反應(yīng)或進(jìn)行相應(yīng)的處理，而不會(huì)產(chǎn)生一些莫名其妙的輸出結(jié)果。算法分析不是針對實(shí)際執(zhí)行時(shí)間的精確的算出算法執(zhí)行具體時(shí)間的分析，而是針對算法中語句的

執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。(151)T(n)=O(f(n))

，它表示隨問題規(guī)模

n的增大算法的執(zhí)行時(shí)間的增長率和

f(n)

的增長率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。若算法執(zhí)行時(shí)所需要的輔助空間相對于輸入數(shù)據(jù)量而言是個(gè)常數(shù)，則稱這個(gè)算法為原地工作，輔助空間為O(1)。(153)在帶有頭結(jié)點(diǎn)的單鏈表中L中，第一個(gè)元素結(jié)點(diǎn)的指針是。L->next(154)在一個(gè)帶頭節(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head=。p->next->next(155)設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn),若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語句:py->next=px->next;px->next=py。(156)對于棧操作數(shù)據(jù)的原則是。后進(jìn)先出(157)設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為。(rear-front+m)%m(158)若已知一個(gè)棧的入棧序列是1,2,3,4??n，其輸出序列為p1,p2,p3,??，pn若p1==n,則pi為。n-i+1(159) 隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算， 在表的另一端進(jìn)行刪除運(yùn)算的線性表。(160)通常程序在調(diào)用另一個(gè)程序時(shí)， 都需要使用一個(gè) 棧來保存被調(diào)用程序內(nèi)分配的局部變量。形式參數(shù)的存儲空間以及返回地址。棧下溢是指在___?？誣____時(shí)進(jìn)行出棧操作。(162)用P表示入棧操作，D表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的P和D的操作串為_______。PDPPDPDD(163)在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿共有n-1個(gè)元素。(164)隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。循環(huán)隊(duì)列的引入，目的是為了克服_______假溢出。(166)所謂稀疏矩陣指的是_______非零元很少(t<<m*n)且分布沒有規(guī)律。(167)在稀疏矩陣表示所對應(yīng)的三元組線性表中，每個(gè)三元組元素按行為主序，列號為輔序的次序排列。(168)二位數(shù)組Am×n按行優(yōu)先順序存儲在內(nèi)存中，元素a00地址為loc(a00),每個(gè)元素在內(nèi)存中占d個(gè)字節(jié)，元素aij的地址計(jì)算公式為loc(aij)=loc(a00)＋(i*n+j)*d。(169)去除廣義表LS=(a1,a2,a3,??，an)中第1個(gè)元素，由其余元素構(gòu)成的廣義表稱為LS的____表尾_____。(170)樹內(nèi)個(gè)結(jié)點(diǎn)的度最大值稱為樹的度。(171)一個(gè)二叉樹第5層節(jié)點(diǎn)最多有16個(gè)。(172)已知完全二叉樹T的第5層只有7個(gè)結(jié)點(diǎn)，則該樹共有____11____個(gè)葉子結(jié)點(diǎn)。(173)在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為N2,則有N0=______N2+1。(174)假設(shè)用于通信的電文由8個(gè)字母組成，其頻率分別為7,19,2,6,32,3,27,10。設(shè)計(jì)哈夫曼編碼，其中字母的編碼長度最大是5位。(175)一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為。9(176)圖的深度優(yōu)先遍歷序列不是惟一的。(177)在圖中，任何兩個(gè)結(jié)點(diǎn)之間都可能存在關(guān)系，因此圖的數(shù)據(jù)元素之間時(shí)一種多對多的關(guān)系。(178)在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的___入度_____。(179)一個(gè)無向圖有n個(gè)頂點(diǎn)，e條邊，則所以頂點(diǎn)的度數(shù)之和為2e。(180)圖有鄰接矩陣、鄰接表等存儲結(jié)構(gòu)，遍歷圖有深度優(yōu)先遍歷、廣度優(yōu)先遍歷等方法。(181)(182)有向圖G用鄰接表矩陣存儲， 其第i行的所有非零元素之和等于頂點(diǎn) i的 。出度(183)如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有 棵生成樹。 n （以任意一頂點(diǎn)為起點(diǎn)，得到 n-1條邊）(184)n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲，則空間復(fù)雜度為。O(n2)(185)n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接表存儲，則空間復(fù)雜度為。O(n+e)(186)設(shè)有一稀疏圖G，則G采用鄰接表存儲較省空間。(187)設(shè)有一稠密圖G，則G采用鄰接矩陣存儲較省空間。(188)圖的逆鄰接表存儲結(jié)構(gòu)只適用于有向圖。(189)已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是將鄰接矩陣的第i行全部置0。(190)圖的深度優(yōu)先遍歷序列不是惟一的。n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為O(n2)

；若采用鄰接表存儲時(shí)，該算法的時(shí)間復(fù)雜度為

O(n+e)

。(192)n個(gè)頂點(diǎn)

e條邊的圖采用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為

O(n2)

；若采用鄰接表存儲，該算法的時(shí)間復(fù)雜度為

O(n+e)

。(193)圖的

BFS

生成樹的樹高比

DFS

生成樹的樹高

小或相等

。(194)用普里姆

(Prim)

算法求具有

n個(gè)頂點(diǎn)

e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為

O(n2)

；用克魯斯卡爾

(Kruskal)

算法的時(shí)間復(fù)雜度是

O(elog2e)

。(195)若要求一個(gè)稀疏圖

G的最小生成樹，

最好用

克魯斯卡爾

(Kruskal)

算法來求解。(196)若要求一個(gè)稠密圖 G的最小生成樹， 最好用 普里姆(Prim) 算法來求解。用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長度遞增的次序來得到最短路徑的。(198)拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有0個(gè)前驅(qū)頂點(diǎn)的過程來完成的。(199)在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是散列查找。(200)散列法存儲的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲地址。(201)大多數(shù)排序算法都有兩個(gè)基本的操作：。比較和移動(dòng)(202)由于查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能。(203)查找有靜態(tài)查找和動(dòng)態(tài)查找， 當(dāng)查找不成功時(shí)動(dòng)態(tài)查找會(huì) 將查找關(guān)鍵字插入在表中。(204)順序查找法中設(shè)置監(jiān)視哨，可以起到 防止越界 的作用。(205)假設(shè)列表長度為 n，那么查找第 i個(gè)數(shù)據(jù)元素時(shí)需進(jìn)行 n-i+1次比較。假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：ASL=(n+1)/2。折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。(208) 假定將長度為 n的表分成 b塊，且每塊含 s個(gè)元素，則 b=n/s。又假定表中每個(gè)元素的查找概率相等，(209) 在有序表(12,24,36,48,60,72,84) 中二分查找關(guān)鍵字 72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為2。(210)折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它將依次與表中元素28，6，12，20比較大小。(211)在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是散列查找。(212)散列法存儲的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲地址。(213)當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映象到哈希表的同一地址上，即k1≠k2，但H（k1）=H（k2），這種現(xiàn)象稱為沖突.(214)產(chǎn)生沖突現(xiàn)象的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的____同義詞________。(215)在散列函數(shù)H(key)=keyMODp中，p應(yīng)取素?cái)?shù)。(216)設(shè)哈希表長m=14,哈希函數(shù)H(key)=keyMOD11.表中已有4個(gè)結(jié)點(diǎn)；addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址為空。如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是。9(217)希爾排序是屬于插入排序的改進(jìn)方法。(218)給出一組關(guān)鍵字T＝（20,4,34,5,16,33,18,29,2,40,7），要求從下到大進(jìn)行排序，試給出快速排序（選一個(gè)記錄為樞紐）第一趟排序結(jié)果。7,4,2,85,16,18,20,,29,33,40,34(219)大多數(shù)排序算法都有兩個(gè)基本的操作：比較和移動(dòng)。(220)在對一組記錄（54,38,96,23,15,72,60,45,83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置至少需比較次。6。(221)在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入；若初始數(shù)據(jù)基本反序，則選用選擇。(222)初始記錄基本無序，則最好選用 快速排序 。(223)對于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞的情況下所需要的時(shí)間是O(n2)。若對其進(jìn)行快速排序，在最壞的情況下所需要的時(shí)間是 O(n2)(234) 對于 n個(gè)記錄的集合進(jìn)行歸并排序， 所需要的平均時(shí)間是 O(nlog2n) ，所需要的附加空間是 O(n) 。7．對于n個(gè)記錄的表進(jìn)行 2路歸并排序，整個(gè)歸并排序需進(jìn)行 ┌l(fā)og2n ┐ 趟（遍）。8.設(shè)要將序列（ Q,H,C,Y,P,A,M,S,R,D,F,X ）中的關(guān)鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是 HCQPAMSRDFXY ；初始步長為 4的希爾（shell）排序一趟的結(jié)果是 PACSQHFXRDMY ；二路歸并排序一趟掃描的結(jié)果是 HQCYAPMSDRFX ；快速排序一趟掃描的結(jié)果是 FHCDPAMQRSYX ；堆排序初始建堆的結(jié)果是 ADCRFQMSYPHX 。在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則應(yīng)首先選取方法，其次選取快速排序方法，最后選取歸并排序方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取歸并排序方法；若只從平均情況下最快考慮，則應(yīng)選取堆排序、快速排序和歸并排序方法；若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取堆排序方法。三、程序填空題以下程序的功能是實(shí)現(xiàn)帶附加頭結(jié)點(diǎn)的單鏈表數(shù)據(jù)結(jié)點(diǎn)逆序連接，請?zhí)羁胀晟浦?。voidreverse(pointerh)/*h為附加頭結(jié)點(diǎn)指針； */{pointerp,q;p=h->next; h->next=NULL;while((1)________){q=p;p=p->next;q->next=h->next;h->next=(2)________;

}}(1)p!=null

∥鏈表未到尾就一直作(2)q

∥將當(dāng)前結(jié)點(diǎn)作為頭結(jié)點(diǎn)后的第一元素結(jié)點(diǎn)插入(236)下面是用 c語言編寫的對不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，該算法用 L返回逆置后的鏈表的頭指針，試在空缺處填入適當(dāng)?shù)恼Z句。void reverse（linklist&L ）{p=null；q=L；while（q！=null）{(1)

;

q->next=p

；

p=q

；(2)___

;}(3)_____;}(1)L=L->next; ∥暫存后繼(2)q=L; ∥待逆置結(jié)點(diǎn)(3)L=p; ∥頭指針仍為 L以下算法的功能是用頭插法建立單鏈表的算法，請?zhí)羁胀晟浦?。Linklist CreateFromHead( ){ LinkList L;Node *s;char c;L=(Linklist)malloc(sizeof(Node)); /*為頭結(jié)點(diǎn)分配存儲空間 */L->next=NULL ;While(( c=getchar()) !=?*? ){ s=(Node*)malloc(sizeof(Node)); /*為讀入的字符分配存儲空間 */s->data=c;s->next=L->next ;L->next=s ;}returnL;}以下算法的功能是尾插法創(chuàng)建鏈表，請?zhí)羁胀晟浦?。typedefstructNode /*結(jié)點(diǎn)類型定義 */{chardata;structNode *next;} Node,*LinkList; /*LinkList 為結(jié)構(gòu)指針類型 */Linklist CreateFromTail( ) /*將新增的字符追加到鏈表的末尾 */{ LinkListL;Node*r,*s;L=(Node*)malloc(sizeof(Node));

/*為頭結(jié)點(diǎn)分配存儲空間

*/L->next=NULL;r=L;

/*r

指針指向鏈表的當(dāng)前表尾，以便于做尾插入，其初值指向頭結(jié)點(diǎn)

*/while(

(

c=getchar())!=?$?

)

/*當(dāng)輸入,$?時(shí)，建表結(jié)束 */{

s=(Node*)malloc(sizeof(Node));

s->data=c;；

r->next=s;

r=s;}；

r->next=NULL

/*

將最后一個(gè)結(jié)點(diǎn)的

next

鏈域置為空，表示鏈表的結(jié)束 */returnL;}/*CreateFromTail*/(239)下列算法在順序表

L中依次存放著線性表中的元素，在表中查找與

e相等的元素，若L.elem[i]=e,

則找到該元素，并返回

i+1

，若找不到，則返回“

-1”

，請?zhí)羁胀晟浦?。int

Locate(SeqListL

，

inte){

i=0;

/*i

為掃描計(jì)數(shù)器，初值為

0，即從第一個(gè)元素開始比較

*/while((i<=L.last)&&(L.elem[i]!=e))

i++;/*

順序掃描表，直到找到值為

key

的元素

,或掃描到表尾而沒找到

*/if

(

i<=L.last

)

return(i+1);

/*

若找到值為

e的元素，則返回其序號

*/else

return(-1);

/*

若沒找到，則返回空序號

*/}(240)下列算法在順序表 L中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)元素 e。插入前表長 n=L->last+1，i的合法取值范圍是 1≤i≤L->last+2 ，請?zhí)羁胀晟浦?。void InsList(SeqList*L,inti, inte){intk;if((i<1)||(i>L->last+2)) printf( 插“入位置 i值不合法 ”)；if(L->last>=maxsize-1) printf( 表“已滿無法插入 ”)；for(k=L->last;k>=i-1;k--) /*為插入元素而移動(dòng)位置 */L->elem[k+1]=L->elem[k] ;L->elem[i-1]=e ; /*在C語言數(shù)組中，第 i個(gè)元素的下標(biāo)為 i-1*/L->last++;}(241)下列算法是在順序表 L中刪除第 i個(gè)數(shù)據(jù)元素， 并用指針參數(shù) e返回其值。 i的合法取值為1≤i≤L.last+1，請?zhí)羁胀晟浦?。int DelList(SeqList*L,inti,int*e){intk;if((i<1)||(i> L->last+1 )) printf(“刪除位置不合法！ ”)；*e=L->elem[i-1] ; /*將刪除的元素存放到 e所指向的變量中 */for(k=i;i<=L->last;k++)L->elem[k-1]= L->elem[k] ; /*將后面的元素依次前移 */L->last-- ;}四、解答題(242)假設(shè)以數(shù)組 seqn［m］存放循環(huán)隊(duì)列的元素，設(shè)變量 rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和元素的個(gè)數(shù)。寫出隊(duì)滿的條件表達(dá)式；寫出隊(duì)空的條件表達(dá)式；設(shè)m=40,rear=13,quelen=19,求隊(duì)頭元素的位置；寫出一般情況下隊(duì)頭元素位置的表達(dá)式。quelen==mquelen==0(13-19+40)%40=34(rear-quelen+m)%m(243)已知一棵二叉樹的中序序列為 ABCDEFG，層序序列為 BAFEGCD ，請畫出該二叉樹。\F\G/CD已知一棵二叉樹的前序序列為ABCDEFGH，中序序列為CBEDFAGH，請畫出該二叉樹。A\B G/C D H\EF已知一棵二叉樹如圖所示。請分別寫出按前序、中序、后序和層次遍歷是得到的頂點(diǎn)序列。A前序：A,B,D,G,C,E,F,HCB中序：D,G,B,A,E,C,H,FE后序：G,D,B,E,H,F,C,AD層次：A,B,C,D,E,F,G,HFGH已知一棵二叉樹的前序序列為：A,B,D,G,J,E,H,C,F,I,K,L 中序序列： D,J,G,B,E,H,A,C,K,I,L,F 。寫出該二叉樹的后序序列；畫出該二叉樹；(3)求該二叉樹的高度 (假定空樹的高度為－ 1)和度為2、度為 1、及度為 0的結(jié)點(diǎn)個(gè)數(shù)。該二叉樹的后序序列為： J,G,D,H,E,B,K,L,I,F,C,A 。該二叉樹的形式如圖所示：ABCEDFG HIJK L該二叉樹高度為： 5。度為2的結(jié)點(diǎn)的個(gè)數(shù)為：3。度為1的結(jié)點(diǎn)的個(gè)數(shù)為：5。度為0的結(jié)點(diǎn)個(gè)數(shù)為：4。(247)有一份電文中共使用6個(gè)字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹，并求其加權(quán)路徑長度WPL，字符c的編碼。WPL＝80字符c：001（不唯一）(4)下圖是帶權(quán)的有向圖G的鄰接表表示法。從結(jié)點(diǎn)V1出發(fā)，求出：深度遍歷圖G；G的一個(gè)拓?fù)湫蛄?；從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的最短路徑。2題29圖43V38V8V266113812312V1V4V524V715012V6參考答案：v1,v2,v3,v8,v4,v5,v7,v6(2分)v1,v2,v4,v6,v5,v3,v7,v8(2分)V1到結(jié)點(diǎn)V8的最短路徑為：v1,v2,v3,v8(2分)已知如圖所示的有向圖，請給出該圖的：（1）每個(gè)頂點(diǎn)的入度、出度；2）鄰接矩陣；3）鄰接表；(249)對下面的有向圖，從頂點(diǎn) V1開始進(jìn)行遍歷，試畫出遍歷得到的 DFS生成森林和BFS生成森V3林。圖全對給 4分，錯(cuò)一個(gè)頂點(diǎn)扣 1分，扣完為止。遍歷得到的 DFS生成森林和 BFS生成森林如下圖：V1V4 V2V3V3V6 V5V6V7 V8

V1V4 V2V5V6 V7 V8V1V4 V2V5 V8V7BFS生成森林DFS生成森林采用哈希函數(shù)Ｈ(k)=3*kmod13并用線性探測開放地址法處理沖突，在數(shù)列地址空間［0..12］中對關(guān)鍵字序列 22,41,53,46,30,13,1,67,51（1）構(gòu)造哈希表（畫示意圖） ；2）裝填因子；等概率下3）成功的和（4）不成功的平均查找長度1）散列地址0123456789101112關(guān)鍵字13225314167465130比較次數(shù)111212111（2）裝填因子=9/13=0.7（3）ASLsucc=11/9（4）ASLunsucc=29/13(251)設(shè)有一組關(guān)鍵字

{9,01,23,14,55,20,84,27}

，采用哈希函數(shù)：

H（

key）

=keymod7

，表長為10，用開放地址法的二次探測再散列方法 Hi=(H(key)+di)mod10(di=12,22,32,,,)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長度。

解決沖突。要求：對散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)11123412平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關(guān)鍵字27為例：H（27）=27%7=6（沖突）H1=（6+1）%10=7（沖突）H2=（6+22）%10=0（沖突）H3=（6+33）%10=5所以比較了4次。(252)對于給定的一組記錄的關(guān)鍵字{23,13,17,21,30,60,58,28,30,90},試分別寫出冒泡排序、快速排序、堆排序、歸并排序第一趟排序后的結(jié)果。冒泡排序 13,23,17,21,,28,30,60,58,30*,90快速排序： (21,13,17,)13,(30,60,58,28,30*,90)堆排序： 13,21,17,23,30,60,58,28,30*,90,歸并排序按層遍歷：(1323)(1721)(3060)(2858)(30*90)(253)采用哈希函數(shù)Ｈ(k)=2*kmod13并用鏈地址法處理沖突，在數(shù)列地址空間［0..12］中對關(guān)鍵字序列22,41,53,46,30,13,1,67,51進(jìn)行下列工作：a）構(gòu)造哈希表（畫示意圖）；b）等概率下成功的和不成功的平均查找長度。參考答案：鏈地址表全對給 8分。錯(cuò)一個(gè)結(jié)點(diǎn)扣 1分，扣完為止。0→13^1→46^2→53→1^3^4→41→67^5→22^6^7^8→30^9^^→51^^ASLsucc=(7+4)/13=11/9 （1分） ASLunsucc=(5+4)/13=9/13 （1分）四、算法設(shè)計(jì)題 (10分)(254)閱讀下列遞歸算法，寫出非遞歸方法實(shí)現(xiàn)相同功能的 C程序。void test(int &sum){intx；scanf(x)；if(x=0)sum=0else{test(sum);sum+=x;}printf(sum) ；}＃include<stdio.h>(1分)voidmain()(1分){intx,sum=0,top=0,s[];(1分)scanf(“%d”,&x)while(x<>0){s[++top]:=a;scanf( “%d”,&x);(3分})while(top)sum+=s[top--];(3 分)printf(“%d”,sum);(1分)p=(edgenode*)malloc(sizeof(edgenode));}試寫出把圖的鄰接矩陣表示轉(zhuǎn)換為鄰接表表示的算法。設(shè)圖的鄰接矩陣為g[n][n]（針對無向圖），定義鄰接表節(jié)點(diǎn)的類型為structedgenode{intadjvex;edgenodenext;}typedef edgenode *adjlist[n];voidmatritolist(intg[][],adjlistgl,intn){edgenode*p,*q;for(inti=0i<n;i++) gl[i]=null;for(inti=0;i<n;i++)for(intj=0;j<n;j++){ if (g[i][j]!=0)p->adjvex=j;p->next=null;ifelse

(gl[i]=null){(q->next=p;

gl[i]==p;

q=p;

q=p;}

}}}閱讀算法并根據(jù)輸入數(shù)據(jù)畫出鏈表。linklistcreatelistr1( ){charch;linklist head=(listnode*)malloc(sizeof(listnode));listnode

*p

，

*r

；r=head;while((ch=getchar())!= ‵n′){p=(listnode*)malloc(sizeof(listnode));while (p) p=(listnode*)malloc(sizeof(listnode));p–>data=ch; r–>next=p; r=p;}r–>next=NULL;return(head);}輸入數(shù)據(jù)為： textheadt r x t ^閱讀算法并指出下列各段程序完成的功能。void add_poly(Lnode*pa,Lnode*pb){ Lnode*p,*q,*u,*pre; intx;p=pa->next; q=pb->next; pre=pa;while((p!=NULL)&&((q!=NULL)){ if (p->exp<q->exp){ pre=p; p=p->next;else if(p->exp==q->exp)

}{

x=p->coef+q->coef;if

(x!=0){p->coef=x;

pre=p;}else

{pre->next=p->next;

free(p);}p=pre->next; u=q; q=q->next;free(u);}else{u=q->next;q->next=p;pre->next=q;pre=q; q=u;}}if(q!=NULL)free(pb);

pre->next=q;}兩個(gè)多項(xiàng)式相加閱讀下面的程序，說明程序的具體功能。typedefintelementypetypedefstructnode{ elemtype data;strunctnode *next;}linklist;voidfunction(linklist*head,elemtypex){linklist*q,*p;q=head;p=q-next;while(p!=NULL)&&(p->data!=x){

q=p;

p=p->next;

}if

(q==NULL)

printf(

“

thereisnothisnode

”::);else

{

q->next=p->next;

free(p);

}}該程序的功能是：在帶頭結(jié)點(diǎn)的單鏈表中，刪除單鏈表中枝為 z的數(shù)據(jù)元素。閱讀下面的程序，說明程序的具體功能。voidfunction( ){initstack(s);scanf( “%”,n);while(n){ push(s,n%8); n=n/8; }while(!Stackempty(s)){ pop(s,e);