數據結構復習資料

1、數據結構復習資料一、填空題數據結構是一門研究非數值計算的程序設計問題中計算機的_操作對象以及它們之間的_關系和運算等的學科。1. 數據結構被形式地定義為(D,R)，其中D是數據元素的有限集合,R是D上的關系有限集合。2. 數據結構包括數據的_邏輯結構_、數據的_存儲結構_和數據的_運算_這三個方面的內容。3. 數據結構按邏輯結構可分為兩大類，它們分別是_線性結構_和_非線性結構。4. 線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。5. 在線性結構中，第一個結點沒有前驅結點，其余每個結點有且只有1個前驅結點；最后一個結點沒有后續(xù)結點，其余每

2、個結點有且只有1個后續(xù)結點。6. 在樹形結構中，樹根結點沒有前驅_結點，其余每個結點有且只有_1個前驅結點；葉子結點沒有_后續(xù)結點，其余每個結點的后續(xù)結點數可以任意多個。7. 在圖形結構中，每個結點的前驅結點數和后續(xù)結點數可以_任意多個。8. 數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序_、_鏈式_、索引_和_散列_。9. 數據的運算最常用的有5種，它們分別是插入_、_刪除、修改、查找、排序。10. 一個算法的效率可分為時間效率和_空間_效率。11. 在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置_有關。12. 線性表中結點的集

3、合是有限的，結點間的關系是_一對一的。13. 向一個長度為n的向量的第i個元素(1<i<n+1)之前插入一個元素時，需向后移動_n-i+1_個元素。14. 向一個長度為n的向量中刪除第i個元素(1<i<n)時，需向前移動n-i_個元素。15. 在順序表中訪問任意一結點的時間復雜度均為0(1),因此，順序表也稱為隨機存取的數據結構。16. 順序表中邏輯上相鄰的元素的物理位置一必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置_不一定_相鄰。17. 在單鏈表中，除了首元結點外，任一結點的存儲位置由_其直接前驅結點的鏈域的值指示。18. 在n個結點的單鏈表中要刪除已知結點*p，需找

4、到它的前驅結點的地址，其時間復雜度為0(n)。19. 向量、棧和隊列都是線性結構，可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂_插入和刪除元素；對于隊列只能在_隊尾插入和二隊首_刪除元素。20. -棧是一種特殊的線性表，允許插入和刪除運算的一端稱為二棧頂二。不允許插入和刪除運算的一端稱為棧底。21. 二隊列二是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。22. _不包含任何字符（長度為_0）的串_稱為空串；由一個或多個空格_（僅由空格符）組成的串稱為空白串。23. 子串的定位運算稱為串的模式匹配；_被匹配的主串稱為目標串，_子串稱為模式。24. 假設有二維數組

5、A6X8,每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000,則數組A的體積（存儲量）為_288B;末尾元素A57的第一個字節(jié)地址為_1282;若按行存儲時，元素Ai4的第一個字節(jié)地址為二（8+4）二X6+1000=1072;若按列存儲時，元素A47的第一個字節(jié)地址為_（6_X7+4）X6+1000）=1276。25. 由3個結點所構成的二叉樹有_5種形態(tài)。26. 一棵深度為6的滿二叉樹有n1+n2=0+屮2=_n。-仁31_個分支結點和_26-1_=32_個葉子。注：滿二叉樹沒有度為1的結點，所以分支結點數就是二度結點數。27. 一棵具有257個結點的完

6、全二叉樹，它的深度為（注：用ILlog2（n）+1=IL8.xx+仁9設一棵完全二叉樹有700個結點，則共有_350_個葉子結點。答：最快方法：用葉子數=n/2=35028. 設一棵完全二叉樹具有1000個結點，則此完全二叉樹有_500_個葉子結點，有_499個度為2的結點，有_1個結點只有非空左子樹，有_0個結點只有非空右子樹。答：最快方法：用葉子數=n/2=500,n2=nc-1=499。另外，最后一結點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數=0.順序查找（線性查找）31在數據的存放無規(guī)律而言的線性表中進行檢索的

7、最佳方法是線性有序表（a1,a2,a3，a256）是從小到大排列的，對一個給定的值k,用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索_8次。設有100個結點，用二分法查找時，最大比較次數是_7。32. 假設在有序線性表a20上進行折半查找，則比較一次查找成功的結點數為1;比較兩次查找成功的結點數為_2;比較四次查找成功的結點數為_8;平均查找長度為_3.7。解：顯然，平均查找長度=O（log2n）<5次（25）。但具體是多少次，則不應當按照公式ASL=3og2（n+1）來計算（即（21Xlog221）/20=4.6次并不正確?。Ｒ驗檫@是在假設n=21的情況下n推導出

8、來的公式。應當用窮舉法羅列：全部元素的查找次數為=（1+2X2+4X3+8X4+5X5）=74;ASL=74/20=3.7!33. 折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它將依次與表中元素一28_,6,12,20比較大小。34. 在各種查找方法中，平均查找長度與結點個數n無關的查找方法是_散列查找。35. 散列法存儲的基本思想是由關鍵字的值決定數據的存儲地址。二、判斷正誤(在正確的說法后面打勾，反之打叉)(x)1.鏈表的每個結點中都恰好包含一個指針。答：錯誤。鏈表中的結點可含多個指針域，分另U存放多個指針。例如，雙向鏈表中的結點可以含有

9、兩個指針域，分別存放指向其直接前趨和直接后繼結點的指針。(X)2.鏈表的物理存儲結構具有同鏈表一樣的順序。錯，鏈表的存儲結構特點是無序，而鏈表的示意圖有序。(X)3.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。錯，鏈表的結點不會移動，只是指針內容改變。(X)4.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，混淆了邏輯結構與物理結構，鏈表也是線性表！且即使是順序表，也能存放記錄型數據。(X)5順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”(X)6順序存

10、儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數據元素，平均需移動表長一半個數的數據元素。(X)7.線性表在物理存儲空間中也一定是連續(xù)的。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續(xù)存放。(X)8.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。(X)9順序存儲方式只能用于存儲線性結構。錯誤。順序存儲方式不僅能用于存儲線性結構，還可以用來存放非

11、線性結構，例如完全二叉樹是屬于非線性結構，但其最佳存儲方式是順序存儲方式。(后一節(jié)介紹)(X)10.線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈式存儲就無需一致。(X)11.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，線性表是邏輯結構概念，可以順序存儲或鏈式存儲，與元素數據類型無關。(X)12.在表結構中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調用子程序或函數常用，CPU中也用隊列。(V)13.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。(V)14.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以

12、是線性表。正確，都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。(X)15.棧和鏈表是兩種不同的數據結構。錯，棧是邏輯結構的概念，是特殊殊線性表，而鏈表是存儲結構概念，二者不是同類項。(X)16.棧和隊列是一種非線性數據結構。錯，他們都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。(V)17.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。V)18.兩個棧共享一片連續(xù)內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。(X)19.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。錯，后半

13、句不對。(x)20.一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯，有可能。(V)21.若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n1個非空指針域。(x)22.二叉樹中每個結點的兩棵子樹的高度差等于1。V)23.二叉樹中每個結點的兩棵子樹是有序的。X)24.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。(X)25.二叉樹中每個結點的關鍵字值大于其左非空子樹(若存在的話)所有結點的關鍵字值，且小于其右非空子樹(若存在的話)所有結點的關鍵字值。(應當是二叉排序樹的特點)k1iX)26.二叉樹中所有結點個數是2-1，其中k是樹的深度。(應2-1)X)27.二叉樹

14、中所有結點，如果不存在非空左子樹，則不存在非空右子樹。X)28.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i1個結點。(應2i-1)(V)29.用二叉鏈表法(link-rlink)存儲包含n個結點的二叉樹，結點的2n個指針區(qū)域中有n+1個為空指針。(V)30.具有12個結點的完全二叉樹有5個度為2的結點。三、單項選擇題(B)1.非線性結構是數據元素之間存在一種：C)多對一關系D)對一關系(C)2.數據結構中，與所使用的計算機無關的是數據的A)存儲B)物理C)邏輯結構;D)物理和存儲(C)3.算法分析的目的是：A) 找出數據結構的合理性C)分析算法的效率以求改進B) 研究

15、算法中的輸入和輸出的關系D)分析算法的易懂性和文檔性A) 對多關系B)多對多關系(A)4.算法分析的兩個主要方面是：正確性和簡明性數據復雜性和程序復雜性A)空間復雜性和時間復雜性B)(C)5.計算機算法指的是：A)計算方法B)(C)5.計算機算法指的是：A)計算方法B)C) 可讀性和文檔性D)等5個特性。B)可行性、確定性和有窮性D)易讀性、穩(wěn)定性和安全性排序方法C)解決冋題的有限運算序列D)調度方法(B)6.計算機算法必須具備輸入、輸出和A)可行性、可移植性和可擴充性C)確定性、有窮性和穩(wěn)定性(C)7數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：A)存儲結構(B)邏

16、輯結構(C)順序存儲結構(D)鏈式存儲結構(B)8.一個向量第一個元素的存儲地址是100，每個元素的長度為2,則第5個元素的地址是(A)110(B)108(C)100(D)120(A)9.在n個結點的順序表中，算法的時間復雜度是0(1)的操作是：A) 訪問第i個結點(Ki<n)和求第i個結點的直接前驅(2<i<n)在第i個結點后插入一個新結點(Ki<n)B) 刪除第i個結點(Kiwn)(D)將n個結點從小到大排序個元)10.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動(A)8(A)8(B)63.5(C)63(D)7)11.鏈接存儲的存儲結構

17、所占存儲空間：分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針只有一部分，存放結點值只有一部分，存儲表示結點間關系的指針分兩部分，一部分存放結點值，另一部分存放結點所占單元數(A)(B)(C)(D)12.鏈表是一種采用存儲結構存儲的線性表;(A)順序(B)鏈式(C)星式(D)網狀13.線性表若采用鏈式存儲結構時，要求內存中可用存儲單兀的地址(A)必須是連續(xù)的(C)一定是不連續(xù)的(B)部分地址必須是連續(xù)的(D)連續(xù)或不連續(xù)都可以(則pi14.線性表L在(A)需經常修改L中的結點值(C)L中含有大量的結點情況下適用于使用鏈式結構實現。需不斷對L進行刪除插入L中結點結構復雜15.棧中元素

18、的進出原則是A.先進先出B.后進先出16.(B)(D)C.?？談t進D.棧滿則出若已知一個棧的入棧序列是1,2,3，,n,其輸出序列為p1,p2,p3,，pn,若p1=n,A.iB.n=iC.n-i+1D.不確定17.17.判定一個棧ST(最多元素為m0)為空的條件是A.ST->top<>0B.ST->top=0C.ST->top<>m0D.ST->top=mO)18.在一個圖中，所有頂點的度數之和等于圖的邊數的A)18.在一個圖中，所有頂點的度數之和等于圖的邊數的A.1/2B.1C.2D.419.20.倍。在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的.1/2B.1C.2D.4倍。有8個結點的無向圖最多有條邊。.14B.28C.56D.11221.21.22.有8個結點的有向完全圖有_.14B.28C.56在表長為n的鏈表中進行線性查找,A.ASL=n;B.C.ASL=.、n+l;D.