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

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

2、個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點其余每個結(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)可用四種基本的存儲方法表示它們分別是順序 、 鏈式 、 索引 和 散列 10. 數(shù)據(jù)的運算最常用的有5種它們分別是插入 、 刪除、修改、 查找 、排序11. 一個算法的效率可分為 時間 效率和 空間 效率12. 在順序表中插入或刪除一個元素需要平均移動 表中一半元素具體移動的元素個數(shù)與 表長和該元素在表

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

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

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

6、樹它的深度為 9 （ 注：用? log2(n) ?+1= ? 8.xx ?+1=929設(shè)一棵完全二叉樹有700個結(jié)點則共有 350 個葉子結(jié)點答：最快方法：用葉子數(shù)n/2350 30 設(shè)一棵完全二叉樹具有1000個結(jié)點則此完全二叉樹有 500 個葉子結(jié)點有 499 個度為2的結(jié)點有 1 個結(jié)點只有非空左子樹有 0 個結(jié)點只有非空右子樹答：最快方法：用葉子數(shù)n/2500 n2=n0-1=499 另外最后一結(jié)點為2i屬于左葉子右葉子是空的所以有1個非空左子樹完全二叉樹的特點決定不可能有左空右不空的情況所以非空右子樹數(shù)0.31在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是 順序查找（線性查找）

7、 32. 線性有序表（a1a2a3.a256)是從小到大排列的對一個給定的值k用二分法檢索表中與k相等的元素在查找不成功的情況下最多需要檢索 8 次設(shè)有100個結(jié)點用二分法查找時最大比較次數(shù)是 7 33. 假設(shè)在有序線性表a20上進行折半查找則比較一次查找成功的結(jié)點數(shù)為1；比較兩次查找成功的結(jié)點數(shù)為 2 ；比較四次查找成功的結(jié)點數(shù)為 8 ；平均查找長度為 3.7 解：顯然平均查找長度O（log2n）<5次（25）但具體是多少次則不應(yīng)當(dāng)按照公式來計算（即（21×log221）/204.6次并不正確?。┮驗檫@是在假設(shè)n2m-1的情況下推導(dǎo)出來的公式應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次

8、數(shù)為（12×24×38×45×5）74； ASL74/20=3.7 ！34折半查找有序表（4612202838507088100）若查找表中元素20它將依次與表中元素 2861220 比較大小35. 在各種查找方法中平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 散列查找 36. 散列法存儲的基本思想是由 關(guān)鍵字的值 決定數(shù)據(jù)的存儲地址二、判斷正誤（在正確的說法后面打勾反之打叉）（ × ）1. 鏈表的每個結(jié)點中都恰好包含一個指針 答：錯誤鏈表中的結(jié)點可含多個指針域分別存放多個指針例如雙向鏈表中的結(jié)點可以含有兩個指針域分別存放指向其直接前趨和直接后繼結(jié)

9、點的指針（ × ）2. 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序錯鏈表的存儲結(jié)構(gòu)特點是無序而鏈表的示意圖有序（ × ）3. 鏈表的刪除算法很簡單因為當(dāng)刪除鏈中某個結(jié)點后計算機會自動地將后續(xù)的各個單元向前移動錯鏈表的結(jié)點不會移動只是指針內(nèi)容改變（ × ）4. 線性表的每個結(jié)點只能是一個簡單類型而鏈表的每個結(jié)點可以是一個復(fù)雜類型錯混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)鏈表也是線性表！且即使是順序表也能存放記錄型數(shù)據(jù)（ × ）5. 順序表結(jié)構(gòu)適宜于進行順序存取而鏈表適宜于進行隨機存取 錯正好說反了順序表才適合隨機存取鏈表恰恰適于"順藤摸瓜"（ ×

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

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

12、表結(jié)構(gòu)既可以是棧也可以是隊列也可以是線性表 正確都是線性邏輯結(jié)構(gòu)棧和隊列其實是特殊的線性表對運算的定義略有不同而已（ × ）15. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu) 錯棧是邏輯結(jié)構(gòu)的概念是特殊殊線性表而鏈表是存儲結(jié)構(gòu)概念二者不是同類項（ × ）16. 棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu) 錯他們都是線性邏輯結(jié)構(gòu)棧和隊列其實是特殊的線性表對運算的定義略有不同而已（ ）17. 棧和隊列的存儲方式既可是順序方式也可是鏈接方式 （ ）18. 兩個棧共享一片連續(xù)內(nèi)存空間時為提高內(nèi)存利用率減少溢出機會應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端 （ × ）19. 隊是一種插入與刪除操作分別

13、在表的兩端進行的線性表是一種先進后出型結(jié)構(gòu) 錯后半句不對（ × ）20. 一個棧的輸入序列是12345則棧的輸出序列不可能是12345 錯有可能（ ）21. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)則在n個結(jié)點的二叉樹鏈表中只有n-1個非空指針域（ × ）22.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1 （ ）23.二叉樹中每個結(jié)點的兩棵子樹是有序的 （ × ）24.二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹 （ × ）25.二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值且小于其右非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值 （應(yīng)當(dāng)是二叉排序

14、樹的特點）（ × ）26.二叉樹中所有結(jié)點個數(shù)是2k-1-1其中k是樹的深度（應(yīng)2i-1） （ × ）27.二叉樹中所有結(jié)點如果不存在非空左子樹則不存在非空右子樹 （ × ）28.對于一棵非空二叉樹它的根結(jié)點作為第一層則它的第i層上最多能有2i-1個結(jié)點（應(yīng)2i-1）（ ）29.用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹結(jié)點的2n個指針區(qū)域中有n+1個為空指針（ ）30.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點三、單項選擇題（ B ）1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對多關(guān)系 B）多對多關(guān)系 C）多對一關(guān)系 D）一對一關(guān)系（ C

15、）2. 數(shù)據(jù)結(jié)構(gòu)中與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲（ C ）3. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進 D) 分析算法的易懂性和文檔性（ A ）4. 算法分析的兩個主要方面是：A) 空間復(fù)雜性和時間復(fù)雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（ C ）5. 計算機算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的有限運算序列 D) 調(diào)度方法（ B ）6. 計算機算法必須具備輸入、輸出和 等5個特性A) 可行性、可移植性和可

16、擴充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性（ C ）7數(shù)據(jù)在計算機存儲器內(nèi)表示時物理地址與邏輯地址相同并且是連續(xù)的稱之為： （A）存儲結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲結(jié)構(gòu) （D）鏈式存儲結(jié)構(gòu)（ B ）8.一個向量第一個元素的存儲地址是100每個元素的長度為2則第5個元素的地址是 （A）110 （B）108 （C）100 （D）120（ A ）9. 在n個結(jié)點的順序表中算法的時間復(fù)雜度是O（1）的操作是：（A） 訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in） （B） 在第i個結(jié)點后插入一個新結(jié)點（1in）（C） 刪除第i個結(jié)點（

17、1in）（D） 將n個結(jié)點從小到大排序（ B ）10. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變平均要移動 個元素（A）8 （B）63.5 （C）63 （D）7（ A ）11. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間： （A） 分兩部分一部分存放結(jié)點值另一部分存放表示結(jié)點間關(guān)系的指針 （B） 只有一部分存放結(jié)點值 (C） 只有一部分存儲表示結(jié)點間關(guān)系的指針（D） 分兩部分一部分存放結(jié)點值另一部分存放結(jié)點所占單元數(shù)（ B ）12. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表；（A）順序 （B）鏈式 （C）星式 （D）網(wǎng)狀（ D ）13. 線性表若采用鏈式存儲結(jié)構(gòu)時要求內(nèi)存中可用存儲單元的

18、地址: （A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的 （C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以（ B ）14 線性表在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)（）需經(jīng)常修改中的結(jié)點值 （）需不斷對進行刪除插入 （）中含有大量的結(jié)點 （）中結(jié)點結(jié)構(gòu)復(fù)雜（ B ）15.棧中元素的進出原則是 先進先出 后進先出 ?？談t進 棧滿則出（ C ）16. 若已知一個棧的入棧序列是123.n其輸出序列為p1p2p3.pn若p1=n則pi為 i n=i n-i+1 不確定（ B ）17. 判定一個棧ST（最多元素為m0）為空的條件是 ST->top<>0 ST->top=0 ST->top<>m0 ST->top=m0（ C ）18. 在一個圖中所有頂點的度數(shù)之和等于圖的邊數(shù)的 倍 A1/2 B. 1 C. 2 D. 4 （ B ）19. 在一個有向圖中所有頂點的入度之和等于所有頂點的出度之和的 倍 A1/2 B. 1 C. 2 D. 4 （ B ）20. 有8個結(jié)點的無向圖最多有 條邊 A14 B. 28 C. 56 D