數據結構試題及答案一、單項選擇題(1)一個算法應該是（）。A)程序B)問題求解步驟的描述C)要滿足五個基本屬性D)A和C(2)算法指的是（）。A)計算機程序B)解決問題的計算方法C)排序算法D)解決問題的有限運算序列。(3)與數據元素本身的形式、內容、相對位置、個數無關的是數據的（）。A)存儲結構B)邏輯結構C)算法D)操作(4)從邏輯上可以把數據結構分為（）兩大類。A)動態結構、靜態結構B)順序結構、鏈式結構C)線性結構、非線性結構D)初等結構、構造型結構(5)下列敘述中正確的是()。）一個邏輯數據結構只能有一種存儲結構B）數據的邏輯結構屬于線性結構，存儲結構屬于非線性結構C）一個邏輯數據結構可以有多種存儲結構，且各種存儲結構不影響數據處理的效率D）一個邏輯數據結構可以有多種存儲結構，且各種存儲結構影響數據處理的效率(6)數據的基本單位是（）A)數據項B)數據類型C)數據元素D)數據變量(7)下列程序的時間復雜度為（）i=0；s=0；while（s<n）{i++；s=s+i；}A)O（n）B)O（2n）C)O（n）D)O（n2）(8)下列程序段的漸進時間復雜度為（）。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)D）(m+n)程序段如下：sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++；其中n為正整數，則最后一行的語句頻度在最壞情況下是（）。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(logn2)(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為正整數，則最后一行的語句頻度在最壞情況下是（）。A)O(n）B)O(nlogn)C)O(n3)D)O(n2)設有一個遞歸算法如下：intfact(intn){/*大于等于0*/if(n<=0)return1;elsereturnn*fact(n-1);}則計算fact(n)需要調用該函數的次數為（）。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)若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則最節省運算時間的存儲方式是（）。A)單鏈表B)僅有頭指針的單循環鏈表C)雙鏈表D)僅有尾指針的單循環鏈表(1)求循環鏈表中當前結點的后繼和前驅的時間復雜度分別是（）。A)O(n)和O(1)B)O(1)和O(1)C)O(1)和O(n)D)O(n)和O(n)(15) 求單鏈表中當前結點的后繼和前驅的時間復雜度分別是（ ）。A)O（n）和O（1） B)O（1）和O（1）C)O（1）和O（n） D)O(n)和O（n）(16) 非空的單循環鏈表的頭指針為 head,尾指針為 rear，則下列條件成立的是（ ）。A)rear->next==head B)rear->next->next==headC)head->next==rear D)head->next->next==rear從一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動的元素的個數是（）。A)n-i B)n-i+1 C)n-i-1 D)i已知一個有序表為（13，18，24，35，47，50，62，83，90，115，134），當二分檢索值為90的元素時，檢索成功需比較的次數是（）。A)1B)2C)3D)4假設以行優先順序存儲三維數組R[6][9][6]，其中元素R[0][0][0]的地址為2100，且每個元素占4個存儲單元，則存儲地址為2836的元素是（）。A)R[3][3][3]B)R[3][3][4]C)R[4][3][5]D)R[4][3][4](20)設有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，a00為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a45的地址為（）。A)13B)35C)17D)36(21)線性表采用鏈式存儲時，節點的存儲的地址（）。A)必須是不連續的B)連續與否均可C)必須是連續的D)和頭節點的存儲地址相連續(22)用鏈表表示線性表的優點是（）。A)便于隨機存取B)花費的存儲空間比順序表少C)數據元素的物理順序與邏輯順序相同D)便于插入與刪除(23)鏈表不具有的特點是（）。A)插入、刪除不需要移動元素B)可隨機訪問任一元素C)不必事先估計存儲空間D)所需空間與線性長度成正比(24)在長度為n的順序表中刪除第i個元素(1≤i≤時n)，元素移動的次數為()。A)n-i+1B)iC)i+1D)n-i(25)采用順序搜索方法查找長度為n的順序表示，搜索成功的平均搜索長度為（）。A)nB)n/2C)(n-1)/2D)(n+1)/2(26)將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）。A)O(1)B)O(n)C)O(m)D)O(m+n)(27)若不帶頭結點的單鏈表的頭指針為head，則該鏈表為空的判定條件是()。A)head==NULL B)head->next==NULL C)head!=NULL D)head->next==head某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節省運算時間。A)單鏈表B)僅有頭指針的單循環鏈表C)雙鏈表D)僅有尾指針的單循環鏈表(29)若允許表達式內多種括號混合嵌套，則為檢查表達式中括號是否正確配對的算法，通常選用的輔助結構是（）。A)棧B)線性表C)隊列D)二叉排序樹(30)順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數組，則元素e進棧操作的主要語句為（）。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；循環隊列sq中，用數組elem［0··25］存放數據元素，sq.front指示隊頭元素的前一個位置，sq.rear指示隊尾元素的當前位置，

設當前

sq.front

為

20，sq.rear為

12，則當前隊列中的元素個數為（

）。A)8

B)16

C)17

D)18(32) 鏈式棧與順序棧相比，一個比較明顯的優點是（

）。A) 插入操作更加方便C)不會出現棧空的情況

B)通常不會出現棧滿的情況D)刪除操作更加方便一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運行時間來看，通常遞歸過程比非遞歸過程（）。A)較快B)較慢C)相同D)不定(34)若已知一個棧的入棧序列是1,2,3,4??n，其輸出序列為p1,p2,p3,??，pn若p1==n,則pi為（）。A)iB)n==iC)n-i+1D)不確定(35)一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是()。A)edcbaB)decbaC)dceabD)abcde若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現的出棧序列是()。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)對于棧操作數據的原則是（）。A)先進先出B)后進先出C)后進后出D)不分順序(38)棧和隊列的共同點是（）。A) 都是先進先出

B)都是先進后出C)只允許在端點處插入和刪除元素

D)沒有共同點(39) 一個隊列的入隊序列是

1，2，3，4，則隊列的輸出序列是（

）。A)4,3,2,1

B)1,2,3,4

C)1,4,3,2

D)3,2,4,1設數組data[m]作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執行出對操作后其頭指針front值為（）。A)front=front+1B)front=(front+1)%(m-1)C)front=(front-1)%mD)front=(front+1)%m(41)引起循環隊列隊頭位置發生變化的操作是()。A)出隊B)入隊C)取隊頭元素D)取隊尾元素(2)設以數組A[m]存放循環隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數為（）。A）(rear-front+m)%mB）rear-front+1C）(front-rear+m)%mD）(rear-front)%m(42)二維數組A[12][18]采用列優先的存儲方法，若每個元素各占3個存儲單元，且A[0][0]地址為150，則元素A[9][7]的地址為()。A)429B)432C)435D)438設有一個10階的對稱矩陣A[10][10]，采用壓縮方式按行將矩陣中下三角部分的元素存入一維數組B[]中，A[0][0]存入B[0]中，則A[8][5]在B[]中（）位置。A)32B)33C)41D)65(44)若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數組B［1..(n(n+1))/2］中，則在B中確定aij（i<j）的位置k的關系為()。A)i*(i-1)/2+jB)j*(j-1)/2+iC)i*(i+1)/2+jD)j*(j+1)/2+i(45)對稀疏矩陣進行壓縮存儲目的是（）。A)便于進行矩陣運算B)便于輸入和輸出C)節省存儲空間D)降低運算的時間復雜度對廣義表L=((a,b),(c,d),(e,f))執行操作tail(tail(L))的結果是()。A)(e,f)B)((e,f))C)(f)D)()(47)設廣義表L=（（a,b,c）），則L的長度和深度分別為（）。A)1和1B)1和3C)1和2D)2和3(48)樹中所有結點的度之和等于所有結點數加（）。A)0B)1C)-1D)2(49)在一棵具有n個結點的二叉鏈表中，所有結點的空域個數等于（）。A)nB)n-1C)n+1D)2*n(50)某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A)空或只有一個結點B)高度等于其節點數C)任一結點無左孩子D)任一結點無右孩子(51)含有10個結點的二叉樹中，度為0的結點數為4，則度為2的結點數為（）A)3B)4C)5D)6(52)除第一層外，滿二叉樹中每一層結點個數是上一層結點個數的（）A)1/2倍B)1倍C)2倍D)3倍(53)對一棵有100個結點的完全二叉樹按層編號，則編號為49的結點，它的父結點的編號為（）A)24B)25C)98D)99(54)可以惟一地轉化成一棵一般樹的二叉樹的特點是（）A)根結點無左孩子B)根結點無右孩子C)根結點有兩個孩子D)根結點沒有孩子設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為（）。A)2hB)2h-1C)2h+1D)h+1(56)在一棵度為3的樹中，度為3的節點個數為2，度為2的節點個數為1，則度為0的節點個數為（）。A)4B)5C)6D)7(57)設森林F對應的二叉樹為B，它有m個結點，B的根為p，p的右子樹結點個數為n,森林F中第一棵子樹的結點個數是（）。A)m-nB)m-n-1C)n+1D)條件不足，無法確定(58)將一株有100個節點的完全二叉樹從上到下，從左到右依次進行編號，根節點的編號為1，則編號為49的節點的左孩子編號為（）。A)98B)89C)50D)沒有孩子(59)下列圖示的順序存儲結構表示的二叉樹是(A)(60)樹最適合用來表示（）。A)有序數據元素B)無序數據元素C)元素之間具有分支層次關系的數據D)元素之間無聯系的數據(61)在一個非空二叉樹的中序遍歷序列中，根結點的右邊（）。A)只有右子樹上的所有結點B)只有右子樹上的部分結點C)只有左子樹的上的部分結點D)只有左子樹上的所有結點(62)任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中相對次序（）。A)不發生改變B)發生改變C)不能確定D)以上都不對(63)在有n個葉子結點的哈夫曼樹中，其結點總數為（）。A)不確定B)2nC)2n+1D)2n-1(64)權值為{1,2,6,8}的四個結點構成的哈夫曼樹的帶權路徑長度是（）。A)18B)28C)19D)29(65)對一個滿二叉樹，m個樹葉，k個分枝結點，n個結點，則（）。A)n=m+1B)m+1=2nC)m=k-1D)n=2k+1(66)在含有n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數為（）。A)eB)2eC)n2-eD)n2-2e(67)若采用鄰接矩陣翻存儲一個n個頂點的無向圖，則該鄰接矩陣是一個（）。A)上三角矩陣B)稀疏矩陣C)對角矩陣D)對稱矩陣(68)在一個圖中，所有頂點的度數之和等于所有邊數的（）倍。A)1/2B)1C)2D)4(69)在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A)1/2B)1C)2D)4(70)對于含n個頂點和e條邊的圖，采用鄰接矩陣表示的空間復雜度為（）。A)O（n）B)O(e)C)O(n+e)D)O(n2)(71)如果求一個連通圖中以某個頂點為根的高度最小的生成樹，應采用（）。A)深度優先搜索算法B)廣度優先搜索算法C)求最小生成樹的prim算法D)拓撲排序算法(72)n個頂點的連通圖至少中含有()。A)n-1B)nC)n+1D)0(73)n個頂點的完全有向圖中含有()。A)n-1條有向邊B)n條有向邊C)n(n-1)/2條有向邊D)n(n-1)條有向邊(74)假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除預某個頂點vi相關的所有弧的時間復雜度是（）。A)O(n)B)O(e)C)O(n+e)D)O(n*e)(75)在無向圖中定義頂點Vi域Vj之間的路徑為從Vi到達Vj的一個（）。A)頂點序列B)邊序列C)權值總和D)邊的條數(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)}，對該圖進行深度優先遍歷，得到的頂點序列正確的是（）。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(77)下面哪一方法可以判斷出一個有向圖是否有環（回路）。A)求節點的度B)拓撲排序C)求最短路徑D)求關鍵路徑(78)圖的廣度優先搜索類似于樹的（）次序遍歷。A)先根B)中根C)后根D)層次(79)在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為()。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的拓撲序列是（）。A)V,V,V,V,V,V,V7B)V1,V,V,V,V,V,V713462532645C)V1,V3,V4,V5,V2,V6,V7D)V1,V2,V5,V3,V4,V6,V7(81)關鍵路徑是事件結點網絡中（）。A)從源點到匯點的最長路徑B)從源點到匯點的最短路徑C)最長回路D)最短回路(82)有n個結點的有向完全圖的弧數是（）。A)n2B)2nC)n(n-1)D)2n(n+1)(83)設圖的鄰接鏈表如題12圖所示，則該圖的邊的數目是（）。83題圖A)4B)5C)10D)20(84)在一個圖中，所有頂點的度數之和等于圖的邊數的（）倍。A)1/2B)1C)2D)4(85)在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A)1/2B)1C)2D)4(86)有8個結點的無向圖最多有（）條邊。A)14B)28C)56D)112(87)有8個結點的無向連通圖最少有（）條邊。A)5B)6C)7D)8(88)有8個結點的有向完全圖有（）條邊。A)14B)28C)56D)112(89)用鄰接表表示圖進行廣度優先遍歷時，通常是采用（）來實現算法的。A)棧B)隊列C)樹D)圖(90)用鄰接表表示圖進行深度優先遍歷時，通常是采用（）來實現算法的。A)棧B)隊列C)樹D)圖(91)已知圖的鄰接矩陣，根據算法思想，則從頂點0出發按深度優先遍歷的結點序列是（）。0111101100100110001001100110101101000011011100010A)0243156 B)0136542 C) 0423165 D)0361542建議：0134256(92) 已知圖的鄰接矩陣同上題 8，根據算法，則從頂點 0出發，按深度優先遍歷的結點序列是（）。A)0243156B)0135642C)0423165D)0134256(93)已知圖的鄰接矩陣同上題8，根據算法，則從頂點0出發，按廣度優先遍歷的結點序列是（）。A)0243651B)0136425C)0423156D)0134256（建議：0123456）(94) 已知圖的鄰接矩陣同上題 8，根據算法，則從頂點 0出發，按廣度優先遍歷的結點序列是（ ）。A)0243165

B) 0135642

C) 0123465

D) 0123456(95) 已知圖的鄰接表如下所示，

根據算法，則從頂點

0出發按深度優先遍歷的結點序列是

（

）。A) 132

B) 0231

C) 0321

D) 0123(96) 已知圖的鄰接表如下所示，

根據算法，則從頂點

0出發按廣度優先遍歷的結點序列是

（

）。A)0321 B) 0123 C) 0132 D) 0312(97)深度優先遍歷類似于二叉樹的（）。A)先序遍歷B)中序遍歷C)后序遍歷D)層次遍歷(98)廣度優先遍歷類似于二叉樹的（）。A)先序遍歷B)中序遍歷C)后序遍歷D)層次遍歷(99)任何一個無向連通圖的最小生成樹（）。A)只有一棵B)一棵或多棵C)一定有多棵D)可能不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權之和或樹權最小的情況唯一）(100)在分析折半查找的性能時常常加入失敗節點，即外節點，從而形成擴充的二叉樹。若設失敗節點i所在層次為Li，那么查找失敗到達失敗點時所做的數據比較次數是（）。A)Li+1B)Li+2C)Li-1D)Li(101)向一個有127個元素原順序表中插入一個新元素并保存原來順序不變，平均要移動（）個元素。A)8B)63.5C)63D)7(102)由同一組關鍵字集合構造的各棵二叉排序樹 ( )。其形態不一定相同，但平均查找長度相同其形態不一定相同，平均查找長度也不一定相同其形態均相同，但平均查找長度不一定相同其形態均相同，平均查找長度也都相同(103)衡量查找算法效率的主要標準是（）。A)元素的個數B)所需的存儲量C)平均查找長度D)算法難易程度(104)適合對動態查找表進行高效率查找的組織結構是（）。A) 有序表 B)分塊有序表 C)二叉排序樹 D)快速排序(3) 能進行二分查找的線性表 ,必須以（ ）。順序方式存儲，且元素按關鍵字有序鏈式方式存儲，且元素按關鍵字有序順序方式存儲，且元素按關鍵字分塊有序鏈式方式存儲，且元素按關鍵字分塊有序(105)為使平均查找長度達到最小,當由關鍵字集合{05,11,21,25,37,40,41,62,84}構建二叉排序樹時,第一個插入的關鍵字應為（）A)5B)37C)41D)62(106)對關鍵字序列(56,23,78,92,88,67,19,34)進行增量為3的一趟希爾排序的結果為()。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)用某種排序方法對關鍵字序列{35,84,21,47,15,27,68,25,20}進行排序時，序列的變化情況如下：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)快速排序一組記錄的排序碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個記錄為基準得到的第一次劃分結果為（）。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)快速排序在最壞情況下的時間復雜度是（）2logn)2C)O(nlogn)D)O(logn)222(110)下列排序算法中不穩定的是（）。A)直接選擇排序B)折半插入排序C)冒泡排序D)快速排序對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列進行同樣的排序操作，直到子序列為空或只剩下一個元素為止。這樣的排序方法是（ ）。A)直接選擇排序B)直接插入排序C)快速排序D)冒泡排序(112)將5個不同的數據進行排序，至多需要比較（）次。A)8B)9C)10D)25(113)排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（）。A)選擇排序B)快速排序C)冒泡排序D)插入排序(114)排序算法中，不穩定的排序是（）。A)直接插入排序B)冒泡排序C)堆排序D)選擇排序(115)排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（）.A)希爾排序B)冒泡排序C)插入排序D)選擇排序(116)從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為（）。A)希爾排序B)歸并排序C)插入排序D)選擇排序(117)對ｎ個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數最多。（）A)從小到大排列好的B)從大到小排列好的C)元素無序D)元素基本有序(118)對ｎ個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數為（）。A)n+1B)nC)n-1D)n(n-1)/2(119)快速排序在下列哪種情況下最易發揮其長處。（）被排序的數據中含有多個相同排序碼被排序的數據已基本有序被排序的數據完全無序被排序的數據中的最大值和最小值相差懸殊(120)對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是（）。A)O(n)B)O(n2)C)O(nlog2n)D)O(n3)(121)若一組記錄的排序碼為（46,79,56,38,40,84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（）。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下列關鍵字序列中，（）是堆。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)下述幾種排序方法中，要求內存最大的是（）。A) 插入排序

B)快速排序

C) 歸并排序

D) 選擇排序(127)有一組數據（

15，9，7，8，20，-1，7，4），用堆排序的篩選方法建立的初始堆為（

）。A)-1，4，8，9，20，7，15，7C)-1，4，7，8，20，15，7，9

B)-1，7，15，7，4，8，20，9D)A，B，C均不對。51．下列四個序列中，哪一個是堆（）。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)快速排序方法在（）情況下最不利于發揮其長處。A)要排序的數據量太大B)要排序的數據中含有多個相同值C)要排序的數據個數為奇數D)要排序的數據已基本有序(131)對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（）。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)對下列關鍵字序列用快速排序法進行排序時，速度最快的情形是（）。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)數據結構是一門研究非數值計算的程序設計問題中計算機的 操作對象 以及它們之間的 關系 和運算等的學科。(134)數據結構被形式地定義為（ D,R），其中 D是 數據元素 的有限集合，R是D上的 關系 有限集合。(135)數據結構包括數據的 邏輯結構 、數據的 存儲結構 和數據的 運算 這三個方面的內容。(136)數據結構按邏輯結構可分為兩大類，它們分別是 線性結構 和 非線性結構 。線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。(138)在線性結構中，第一個結點沒有前驅結點，其余每個結點有且只有1個前驅結點；最后一個結點沒有后續結點，其余每個結點有且只有1個后續結點。(139)在樹形結構中，樹根結點沒有前驅結點，其余每個結點有且只有1個前驅結點；葉子結點沒有后續結點，其余每個結點的后續結點數可以任意多個。(140)在圖形結構中，每個結點的前驅結點數和后續結點數可以任意多個。(141)數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序、鏈式、索引和散列。(142)數據的運算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。(143)一個算法的效率可分為時間效率和空間效率。(144)對于給定的n個元素,可以構造出的邏輯結構有集合，線性表，樹，圖四種。(145)順序映象的特點是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。非順序映象的特點是借助是指示元素存儲地址的指針表示數據元素之間的邏輯關系。任何一個算法的設計取決于選定邏輯結構，而算法的實現依賴于采用的存儲結構。數據類型是一組___________性質相同的值集合以及定義在這個值集合上的一組操作的總稱。數據對象是___________性質相同的數據元素的集合，是數據的一個子集。如果操作不改變原邏輯結構的“值”，而只是從中提取某些信息作為運算結果，則稱該類運算為 型運算。引用(149)算法的 健壯特性是指做為一個好的算法， 當輸入的數據非法時， 也能適當地做出正確反應或進行相應的處理，而不會產生一些莫名其妙的輸出結果。算法分析不是針對實際執行時間的精確的算出算法執行具體時間的分析，而是針對算法中語句的

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

，它表示隨問題規模

n的增大算法的執行時間的增長率和

f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱時間復雜度。若算法執行時所需要的輔助空間相對于輸入數據量而言是個常數，則稱這個算法為原地工作，輔助空間為O(1)。(153)在帶有頭結點的單鏈表中L中，第一個元素結點的指針是。L->next(154)在一個帶頭節點的單循環鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針head可用p表示為head=。p->next->next(155)設單鏈表的結點結構為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結點，指針py指向data為y的新結點,若將結點y插入結點x之后，則需要執行以下語句:py->next=px->next;px->next=py。(156)對于棧操作數據的原則是。后進先出(157)設以數組A[m]存放循環隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數為。(rear-front+m)%m(158)若已知一個棧的入棧序列是1,2,3,4??n，其輸出序列為p1,p2,p3,??，pn若p1==n,則pi為。n-i+1(159) 隊列是被限定為只能在表的一端進行插入運算， 在表的另一端進行刪除運算的線性表。(160)通常程序在調用另一個程序時， 都需要使用一個 棧來保存被調用程序內分配的局部變量。形式參數的存儲空間以及返回地址。棧下溢是指在___棧空_____時進行出棧操作。(162)用P表示入棧操作，D表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的P和D的操作串為_______。PDPPDPDD(163)在具有n個單元的循環隊列中，隊滿共有n-1個元素。(164)隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。循環隊列的引入，目的是為了克服_______假溢出。所謂稀疏矩陣指的是_______非零元很少(t<<m*n)且分布沒有規律。(167)在稀疏矩陣表示所對應的三元組線性表中，每個三元組元素按 行為主序，列號為輔序的次序排列。二位數組Am×n按行優先順序存儲在內存中，元素a00地址為loc(a00),每個元素在內存中占d個字節，元素a的地址計算公式為loc(a)=loc(a)＋(i*n+j)*d。ijij00(169)去除廣義表LS=(a1,a2,a3,??，an)中第1個元素，由其余元素構成的廣義表稱為LS的____表尾_____。(170)樹內個結點的度最大值稱為樹的度。(171)一個二叉樹第5層節點最多有16個。(172)已知完全二叉樹T的第5層只有7個結點，則該樹共有____11____個葉子結點。(173)在一棵二叉樹中，度為零的結點的個數為N0,度為2的結點的個數為N2,則有N0=______N2+1。假設用于通信的電文由8個字母組成，其頻率分別為7,19,2,6,32,3,27,10。設計哈夫曼編碼，其中字母的編碼長度最大是5位。(175)一棵具有257個結點的完全二叉樹，它的深度為。9(176)圖的深度優先遍歷序列不是惟一的。(177)在圖中，任何兩個結點之間都可能存在關系，因此圖的數據元素之間時一種多對多的關系。(178)在有向圖中，以頂點v為終點的邊的數目稱為v的___入度_____。(179)一個無向圖有n個頂點，e條邊，則所以頂點的度數之和為2e。(180)圖有鄰接矩陣、鄰接表等存儲結構，遍歷圖有深度優先遍歷、廣度優先遍歷等方法。(181)(182)有向圖G用鄰接表矩陣存儲，其第i行的所有非零元素之和等于頂點i的。出度(183)如果n個頂點的圖是一個環，則它有棵生成樹。n（以任意一頂點為起點，得到n-1條邊）(184)n個頂點e條邊的圖，若采用鄰接矩陣存儲，則空間復雜度為。O(n2)(185)n個頂點e條邊的圖，若采用鄰接表存儲，則空間復雜度為。O(n+e)(186)設有一稀疏圖G，則G采用鄰接表存儲較省空間。(187)設有一稠密圖G，則G采用鄰接矩陣存儲較省空間。(188)圖的逆鄰接表存儲結構只適用于有向圖。(189)已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點出發的方法是將鄰接矩陣的第i行全部置0。(190)圖的深度優先遍歷序列不是惟一的。n個頂點e條邊的圖采用鄰接矩陣存儲，深度優先遍歷算法的時間復雜度為O(n2)；若采用鄰接表存儲時，該算法的時間復雜度為O(n+e)。(192)n個頂點e條邊的圖采用鄰接矩陣存儲，廣度優先遍歷算法的時間復雜度為O(n2)；若采用鄰接表存儲，該算法的時間復雜度為O(n+e)。(193)圖的BFS生成樹的樹高比DFS生成樹的樹高小或相等。(194)用普里姆(Prim)算法求具有n個頂點e條邊的圖的最小生成樹的時間復雜度為O(n2)；用克魯斯卡爾(Kruskal)算法的時間復雜度是O(elog2e)。(195)若要求一個稀疏圖G的最小生成樹，最好用克魯斯卡爾(Kruskal)算法來求解。(196)若要求一個稠密圖G的最小生成樹，最好用普里姆(Prim)算法來求解。用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度遞增的次序來得到最短路徑的。(198)拓撲排序算法是通過重復選擇具有0個前驅頂點的過程來完成的。(199)在各種查找方法中，平均查找長度與結點個數n無關的查找方法是散列查找。(200)散列法存儲的基本思想是由關鍵字的值決定數據的存儲地址。(201)大多數排序算法都有兩個基本的操作：。比較和移動(202)由于查找算法的基本運算是關鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能。(203)查找有靜態查找和動態查找，當查找不成功時動態查找會將查找關鍵字插入在表中。(204)順序查找法中設置監視哨，可以起到防止越界的作用。(205)假設列表長度為 n，那么查找第 i個數據元素時需進行 n-i+1次比較。假設查找每個數據元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：ASL=(n+1)/2。折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關鍵字大小有序排列的順序表。(208)假定將長度為n的表分成b塊，且每塊含s個元素，則b=n/s。又假定表中每個元素的查找概率相等，(209)在有序表(12,24,36,48,60,72,84)中二分查找關鍵字72時所需進行的關鍵字比較次數為2。(210)折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它將依次與表中元素28，6，12，20比較大小。(211)在各種查找方法中，平均查找長度與結點個數n無關的查找方法是散列查找。(212)散列法存儲的基本思想是由關鍵字的值決定數據的存儲地址。(213)當關鍵字集合很大時，關鍵字值不同的元素可能會映象到哈希表的同一地址上，即k1≠k2，但H（k1）=H（k2），這種現象稱為沖突.(214)產生沖突現象的兩個關鍵字稱為該散列函數的____同義詞________。(215)在散列函數H(key)=keyMODp中，p應取素數。(216)設哈希表長m=14,哈希函數H(key)=keyMOD11.表中已有4個結點；addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址為空。如用二次探測再散列處理沖突，關鍵字為49的結點的地址是。9(217)希爾排序是屬于插入排序的改進方法。(218)給出一組關鍵字T＝（20,4,34,5,16,33,18,29,2,40,7），要求從下到大進行排序，試給出快速排序（選一個記錄為樞紐）第一趟排序結果。7,4,2,85,16,18,20,,29,33,40,34大多數排序算法都有兩個基本的操作：比較和移動。(220)在對一組記錄（

54,38,96,23,15,72,60,45,83）進行直接插入排序時，當把第

7個記錄

60插入到有序表時，為尋找插入位置至少需比較

次。6。(221)在插入和選擇排序中，若初始數據基本正序，則選用

插入

；若初始數據基本反序，則選用

選擇

。(222)初始記錄基本無序，則最好選用

快速排序

。(223)對于

n個記錄的集合進行冒泡排序，

在最壞的情況下所需要的時間是

O(n2)

。若對其進行快速排序，在最壞的情況下所需要的時間是

O(n2)(234) 對于n個記錄的集合進行歸并排序， 所需要的平均時間是 O(nlog2n) ，所需要的附加空間是 O(n) 。7．對于n個記錄的表進行 2路歸并排序，整個歸并排序需進行 ┌log2n┐ 趟（遍）。設要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結果是 HCQPAMSRDFXY ；初始步長為 4的希爾（shell）排序一趟的結果是 PACSQHFXRDMY ；二路歸并排序一趟掃描的結果是 HQCYAPMSDRFX；快速排序一趟掃描的結果是 FHCDPAMQRSYX ；堆排序初始建堆的結果是 ADCRFQMSYPHX 。在堆排序、快速排序和歸并排序中，若只從存儲空間考慮， 則應首先選取 方法，其次選取 快速排序方法，最后選取歸并排序方法；若只從排序結果的穩定性考慮，則應 選取 歸并排序 方法；若只從平均情況下最快考慮，則應選取 堆排序、快速排序和歸并排序 方法；若只從最壞情況下最快并且要節省內存考慮，則應選取 堆排序 方法。三、程序填空題以下程序的功能是實現帶附加頭結點的單鏈表數據結點逆序連接，請填空完善之。voidreverse(pointerh)/*h為附加頭結點指針； */{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

∥將當前結點作為頭結點后的第一元素結點插入(236)下面是用

c語言編寫的對不帶頭結點的單鏈表進行就地逆置的算法，該算法用

L返回逆置后的鏈表的頭指針，試在空缺處填入適當的語句。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; ∥待逆置結點(3)L=p; ∥頭指針仍為 L以下算法的功能是用頭插法建立單鏈表的算法，請填空完善之。Linklist CreateFromHead( ){ LinkList L;Node *s;char

c;L=(Linklist)malloc(sizeof(Node));

/*為頭結點分配存儲空間

*/L->next=NULL

;While((

c=getchar())

!=

’*’

){

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

/*為讀入的字符分配存儲空間

*/s->data=c;s->next=L->next

;L->next=s

;}returnL;}以下算法的功能是尾插法創建鏈表，請填空完善之。typedefstructNode /*結點類型定義 */{chardata;structNode *next;}

Node,*LinkList;

/*LinkList

為結構指針類型

*/Linklist{

CreateFromTail( ) /*將新增的字符追加到鏈表的末尾LinkListL;Node*r,*s;char c;L=(Node*)malloc(sizeof(Node)); /*為頭結點分配存儲空間L->next=NULL;r=L; /*r指針指向鏈表的當前表尾，以便于做尾插入，其初值指向頭結點while( ( c=getchar())!=’$’)

*/*/*//*當輸入‘$時’，建表結束*/{

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

s->data=c;；r->next=s;

r=s;}；

r->next=NULL

/*將最后一個結點的

next鏈域置為空，表示鏈表的結束*/returnL;}/*CreateFromTail*/(239)下列算法在順序表 L中依次存放著線性表中的元素，在表中查找與 e相等的元素，若L.elem[i]=e,則找到該元素，并返回 i+1，若找不到，則返回“ -1” ，請填空完善之。int Locate(SeqListL，inte){ i=0; /*i為掃描計數器，初值為 0，即從第一個元素開始比較while((i<=L.last)&&(L.elem[i]!=e)) i++;

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

key的元素

,或掃描到表尾而沒找到

*/if (

i<=L.last

)

return(i+1);

/*若找到值為

e的元素，則返回其序號

*/else

return(-1);

/*若沒找到，則返回空序號

*/}(240)下列算法在順序表 L中第i個數據元素之前插入一個元素 e。插入前表長i的合法取值范圍是 1≤i≤L->last+2，請填空完善之。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--) /*為插入元素而移動位置 */

n=L->last+1，L->elem[k+1]=L->elem[k]

;L->elem[i-1]=e ; /*在C語言數組中，第i個元素的下標為 i-1*/L->last++;}(241)下列算法是在順序表 L中刪除第 i個數據元素，并用指針參數 e返回其值。i的合法取值為1≤i≤L.last+1，請填空完善之。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)假設以數組 seqn［m］存放循環隊列的元素，設變量 rear和quelen分別指示循環隊列中隊尾元素的位置和元素的個數。寫出隊滿的條件表達式；寫出隊空的條件表達式；設m=40,rear=13,quelen=19,求隊頭元素的位置；寫出一般情況下隊頭元素位置的表達式。quelen==mquelen==0(13-19+40)%40=34(rear-quelen+m)%m已知一棵二叉樹的中序序列為ABCDEFG，層序序列為BAFEGCD，請畫出該二叉樹。\F\G/C\D已知一棵二叉樹的前序序列為ABCDEFGH，中序序列為CBEDFAGH，請畫出該二叉樹。A\B G/ \ \C D H\EF已知一棵二叉樹如圖所示。請分別寫出按前序、中序、后序和層次遍歷是得到的頂點序列。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的結點個數。該二叉樹的后序序列為： J,G,D,H,E,B,K,L,I,F,C,A 。該二叉樹的形式如圖所示：ABCEDFG HIJK L該二叉樹高度為： 5。度為2的結點的個數為： 3。度為1的結點的個數為： 5。度為0的結點個數為： 4。(247)有一份電文中共使用

6個字符

:a,b,c,d,e,f,它們的出現頻率依次為

2,3,4,7,8,9，試構造一棵哈夫曼樹，并求其加權路徑長度

WPL，字符

c的編碼。WPL＝80

字符

c：001（不唯一）(4) 下圖是帶權的有向圖

G的鄰接表表示法。從結點

V1

出發，求出：深度遍歷圖G；G的一個拓撲序列；從結點V1到結點V8的最短路徑。2題29圖43V38V86V26111238V131224V4V5V7150V6 12參考答案：v1,v2,v3,v8,v4,v5,v7,v6(2分)v1,v2,v4,v6,v5,v3,v7,v8(2分)V1到結點V8的最短路徑為：v1,v2,v3,v8(2分)已知如圖所示的有向圖，請給出該圖的：（1）每個頂點的入度、出度；（2）鄰接矩陣；（3）鄰接表；V1(249)對下面的有向圖，從頂點V1開始進行遍V2V4歷，試畫出遍歷得到的DFS生成森林和BFS生成森V3林。V5圖全對給4分，錯一個頂點扣1分，扣完為止。V6V7V8遍歷得到的DFS生成森林和BFS生成森林如下圖：V1V1V4V2V3V4V2V3V6V5V5V8V6V7V7 V8 BFS生成森林DFS生成森林采用哈希函數Ｈ(k)=3*kmod13并用線性探測開放地址法處理沖突，在數列地址空間0..12］中對關鍵字序列22,41,53,46,30,13,1,67,511）構造哈希表（畫示意圖）；2）裝填因子；等概率下3）成功的和（4）不成功的平均查找長度1）散列地址0123456789101112關鍵字13225314167465130比較次數111212111（2）裝填因子=9/13=0.7（3）ASLsucc=11/9（4）ASLunsucc=29/13(251)設有一組關鍵字 {9,01,23,14,55,20,84,27}，采用哈希函數： H（key）=keymod7 ，表長為10，用開放地址法的二次探測再散列方法 Hi=(H(key)+di)mod10(di=12,22,32, ?,)解決沖突。要求：對該關鍵字序列構造哈希表，并計算查找成功的平均查找長度。散列地址0123456789關鍵字140192384275520比較次數11123412平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關鍵字27為例：H（27）=27%7=6（沖突）H1=（6+1）%10=7（沖突）22）%10=0（沖突）H3=（6+33）%10=5所以比較了4次。H=（6+2對于給定的一組記錄的關鍵字{23,13,17,21,30,60,58,28,30,90},試分別寫出冒泡排序、快速排序、堆排序、歸并排序第一趟排序后的結果。冒泡排序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)采用哈希函數Ｈ(k)=2*kmod13并用鏈地址法處理沖突，在數列地址空間［0..12］中對關鍵字序列22,41,53,46,30,13,1,67,51進行下列工作：a）構造哈希表（畫示意圖）；b）等概率下成功的和不成功的平均查找長度。參考答案：鏈地址表全對給 8分。錯一個結點扣 1分，扣完為止。0→13^1→46^2→53→1^3^4→41→67^5→22^^^8 → 30 ^^^→51^^ASLsucc=(7+4)/13=11/9（1分） ASLunsucc=(5+4)/13=9/13（1分）四、算法設計題 (10分)(254)閱讀下列遞歸算法，寫出非遞歸方法實現相同功能的 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分)}試寫出把圖的鄰接矩陣表示轉換為鄰接表表示的算法。設圖的鄰接矩陣為g[n][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=(edgenode*)malloc(sizeof(edgenode));p->adjvex=j;p->next=null;if (gl[i]=null) { gl[i]==p;else ( q->next=p; q=p;

q=p;}

}}}閱讀算法并根據輸入數據畫出鏈表。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);}輸入數據為： 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) pre->next=q;free(pb);}兩個多項式相加閱讀下面的程序，說明程序的具體功能。typedefintelementypetypedefstructnode{elemtypedata;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( “therelse { q->next=p->next; free(p);

}

n”);}該程序的功能是：在帶頭結點的單鏈表中，刪除單鏈表中枝為

z的數據元素。閱讀下面的程序，說明程序的具體功能。voidfunction( ){initstack(s);scanf(

“%”,n);while(n){

push(s,n%8);

n=n/8;

}while(!