數(shù)據(jù)結(jié)構(gòu)(c語言版)復(fù)習(xí)資料

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

2、點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。7. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)_結(jié)點，其余每個結(jié)點有且只有 _1_個前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù) _結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個 _。8. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以_任意多個 _。9. 數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序、鏈?zhǔn)健⑺饕?和散列。10. 數(shù)據(jù)的運算最常用的有 5種，它們分別是 插入、刪除、修改、 查找、排序。11. 一個算法的效率可分為 時間效率和空間效率。12. 在順序表中插入或刪除一個元素，需要平均移動_表中一半元素，具體移動的元素個數(shù)與表長和該元素在表中的位置 _有關(guān)。13

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

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

5、A6X 8,每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000,則數(shù)組A的體積（存儲量）為288 B ;末尾元素 A57的第一個字節(jié)地址為1282;若按行存儲時，元素 A14的第一個字節(jié)地址為（8+4） X 6+1000=1072;若按列存儲時，元素A47的第一個字節(jié)地址為（6X 7 + 4） X 6 + 1000）= 1276。26. 由3個結(jié)點所構(gòu)成的二叉樹有_5_種形態(tài)。27. 一棵深度為6的滿二叉樹有_m+n2=0+ n 2= no-1=31 _個分支結(jié)點和_26-1 =32個葉子。注：滿二叉樹沒有度為 1的結(jié)點，所以分支結(jié)點數(shù)就是二度結(jié)點數(shù)。28

6、. 一棵具有2 5 7個結(jié)點的完全二叉樹，它的深度為_9。（注：用 |l_log2（n） +1= |l.8.xx +1=929. 設(shè)一棵完全二叉樹有 700個結(jié)點，則共有_ 350_個葉子結(jié)點。答：最快方法：用葉子數(shù)=n/2 = 35030. 設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有 _500.個葉子結(jié)點，有499 個度為2的結(jié)點，有_1_個結(jié)點只有非空左子樹，有_0個結(jié)點只有非空右子樹。答：最快方法：用葉子數(shù)=n/2 = 500 , n2=no-1=499。另外，最后一結(jié)點為 2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非

7、空右子樹數(shù)=0.31在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是_順序查找（線性查找）_。32. 線性有序表（a1, a2, a?,，a?56）是從小到大排列的，對一個給定的值k,用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索_8 _次。設(shè)有100個結(jié)點，用二分法查找時，最大比較次數(shù)是_7。33. 假設(shè)在有序線性表 a20上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為1;比較兩次查找成功的結(jié)點數(shù)為_ 2_ ;比較四次查找成功的結(jié)點數(shù)為_ 8_;平均查找長度為3.7_。解：顯然，平均查找長度=O （log 2n ） 5次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式ASL=

8、L0|og2（n比）來計算（即（21 Xlog 221 ） /20 = 4.6次并不正確?。Ｒ驗檫@是在假設(shè) n = 2m-1的情 n況下推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為=（1 + 2 X2 + 4 X3 + 8X4 + 5 X5 ）= 74 ; ASL = 74/20=3.7!34. 折半查找有序表（4,6,12, 20,28,38, 50, 70,88,100）,若查找表中元素20,它將依次與表中元素 28, 6, 12, 20比較大小。35.在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是散列查找36.散列法存儲的基本思想是由 _關(guān)鍵字的值決定數(shù)據(jù)的存儲地

9、址。二、判斷正誤(在正確的說法后面打勾，反之打叉)(x ) 1.鏈表的每個結(jié)點中都恰好包含一個指針。答：錯誤。鏈表中的結(jié)點可含多個指針域，分另U存放多個指針。例如，雙向鏈表中的結(jié)點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。(x ) 2鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點是無序，而鏈表的示意圖有序(x ) 3.鏈表的刪除算法很簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向 前移動。錯，鏈表的結(jié)點不會移動，只是指針內(nèi)容改變。(x ) 4.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。 錯，混淆了邏輯結(jié)構(gòu)與物

10、理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。(X ) 5.順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”(X ) 6.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈?zhǔn)酱鎯Φ膬?yōu)點。順序存儲方式插入、刪除運算效率較低， 在表長為n的順序表中，插入和刪除一個數(shù)據(jù)元素，平均需移動表長一半個數(shù)的數(shù)據(jù)元素。(X ) 7.線性表在物理存儲空間中也一定是連續(xù)的。錯，線性表有兩種存儲方式，順序存儲和鏈?zhǔn)酱鎯?。后者不要求連續(xù)存放。(x ) 8.線性表在順序存儲時，邏輯上相鄰的元

11、素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。(x ) 9.順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯誤。順序存儲方式不僅能用于存儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但 其最佳存儲方式是順序存儲方式。(后一節(jié)介紹)(x ) 10.線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈?zhǔn)酱鎯蜔o需一致。(x ) 11.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。錯，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲或鏈?zhǔn)酱鎯?，與元素數(shù)據(jù)類型無關(guān)。(x ) 12.在表結(jié)構(gòu)中最常用的是

12、線性表，棧和隊列不太常用。 錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊列。(V ) 13.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構(gòu)。(V ) 14.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。 正確，都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。(x ) 15.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。(x ) 16.棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。(V )

13、 17.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。V ) 18.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。(x ) 19.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。錯，后半句不對。(x ) 20. 一個棧的輸入序列是 12345，則棧的輸出序列不可能是12345。錯，有可能。(V ) 21.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n 1個非空指針域。(x ) 22.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。V ) 23.二叉樹中每個結(jié)點的兩棵子樹是有序的。(X ) 24二叉

14、樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。(X ) 25二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹(若存在的話)所有結(jié)點的關(guān)鍵字值，且小于 其右非空子樹(若存在的話)所有結(jié)點的關(guān)鍵字值。(應(yīng)當(dāng)是二叉排序樹的特點)(X ) 26二叉樹中所有結(jié)點個數(shù)是 2k-1-l，其中k是樹的深度。(應(yīng)2-1)X ) 27二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。X ) 28.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i 1個結(jié)點。(應(yīng) 2i-1(V ) 29用二叉鏈表法(link-rlink )存儲包含n個結(jié)點的二叉樹，結(jié)點的 2n個指針區(qū)域中有 n+1個為空指針。(

15、V ) 30具有12個結(jié)點的完全二叉樹有 5個度為2的結(jié)點。三、單項選擇題(B(C)1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種:A)一對多關(guān)系B)多對多關(guān)系)2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A)存儲 B)物理(C ) 3.算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 C)分析算法的效率以求改進(A ) 4.算法分析的兩個主要方面是：A)空間復(fù)雜性和時間復(fù)雜性 C)可讀性和文檔性(C ) 5.計算機算法指的是：A)計算方法B)排序方法(B ) 6.計算機算法必須具備輸入、輸出和 A)可行性、可移植性和可擴充性 C)確定性、有窮性和穩(wěn)定性C)多對一關(guān)系D) 一對一關(guān)系結(jié)構(gòu)；D)物理和存儲B)

16、研究算法中的輸入和輸出的關(guān)系D)分析算法的易懂性和文檔性C)邏輯B)正確性和簡明性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C)解決問題的有限運算序列D)調(diào)度方法等5個特性。B)可行性、確定性和有窮性D)易讀性、穩(wěn)定性和安全性(C ) 7數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：(A )存儲結(jié)構(gòu)(B )邏輯結(jié)構(gòu)(C)順序存儲結(jié)構(gòu)(D)鏈?zhǔn)酱鎯Y(jié)構(gòu)(B ) 8.個向量第一個元素的存儲地址是100,每個元素的長度為 2,則第5個元素的地址是 (A) 110( B) 108( C) 100( D) 120(A ) 9.在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O (1)的操作是：(A)訪

17、問第i個結(jié)點(1 iw n)和求第i個結(jié)點的直接前驅(qū)(2 itop=m0倍。A. ST-topv0 B. ST-top=0C. ST-topvmO倍。D.)18.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的A. 1/2B. 1C. 2A. 1/2B. 1C.2D. 4(B )20.有8個結(jié)點的無向圖最多有條邊。A. 14B. 28C.56D. 112(C )21.有8個結(jié)點的有向完全圖有條邊。A . 14B. 28C.56D. 112(B )22 .在表長為n的鏈表中進行線性查找，它的平均查找長度為A. ASL=n ;B. ASL=(n +1)/2 ；在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之