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

1、 數(shù)據(jù)結(jié)構(gòu)(c語言版)復(fù)習(xí)資料 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 操作對(duì)象 以及它們之間的 關(guān)系 和運(yù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ù)的 存儲(chǔ)結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。5. 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。6 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)

2、前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。7. 在樹形結(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è) 。8. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 。9數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序 、 鏈?zhǔn)?、 索引 和 散列 。10. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。11. 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率。12. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 表中一半元素，具體移動(dòng)的

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

4、9 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O（n）。20.棧只能在 棧頂 插入和刪除元素；對(duì)于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)首 刪除元素。21. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為 棧底 。22. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。23. 不包含任何字符（長(zhǎng)度為0）的串 稱為空串； 由一個(gè)或多個(gè)空格（僅由空格符）組成的串 稱為空白串。24. 子串的定位運(yùn)算稱為串的模式匹配； 被匹配的主串 稱為目標(biāo)串， 子串 稱為模式。25. 假設(shè)有二維數(shù)組A6×

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

6、8 一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 9 。（ 注：用ë log2(n) û+1= ë 8.xx û+1=929設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有 350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)n/2350 30 設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有 500 個(gè)葉子結(jié)點(diǎn)，有 499 個(gè)度為2的結(jié)點(diǎn)，有 1 個(gè)結(jié)點(diǎn)只有非空左子樹，有 0 個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)n/2500 ，n2=n0-1=499。 另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況

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

8、×log221）/204.6次并不正確！）。因?yàn)檫@是在假設(shè)n2m-1的情況下推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為（12×24×38×45×5）74； ASL74/20=3.7 ！34折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。35. 在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是 散列查找 。36. 散列法存儲(chǔ)的基本思想是由 關(guān)鍵字的值 決定數(shù)據(jù)的存儲(chǔ)地址。二、判斷正誤（在正確的說法后面打勾，反之打叉）（ 

9、15; ）1. 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。 答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。（ × ）2. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò)，鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無序，而鏈表的示意圖有序。（ × ）3. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。錯(cuò)，鏈表的結(jié)點(diǎn)不會(huì)移動(dòng)，只是指針內(nèi)容改變。（ × ）4. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表

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

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

12、存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無關(guān)。（ × ）12. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。 錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。（ ）13. 棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（ ）14. 對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。 正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。（ × ）15. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。（ × ）16. 棧和隊(duì)列是一

13、種非線性數(shù)據(jù)結(jié)構(gòu)。 錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。（ ）17. 棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。 （ ）18. 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。 （ × ）19. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。 錯(cuò)，后半句不對(duì)。（ × ）20. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。 錯(cuò)，有可能。（ ）21. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n1個(gè)非空指針

14、域。（ × ）22.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。 （ ）23.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。 （ × ）24.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。 （ × ）25.二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （應(yīng)當(dāng)是二叉排序樹的特點(diǎn)）（ × ）26.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。（應(yīng)2i-1） （ × ）27.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。 （ × ）28.對(duì)于一棵非

15、空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i1個(gè)結(jié)點(diǎn)。（應(yīng)2i-1）（ ）29.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（ ）30.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。 (× )31.在哈夫曼樹中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。（× ）32.一個(gè)廣義表的表頭總是一個(gè)廣義表。（ ）33廣義表( a ), b), c ) 的表頭是( a ), b)，表尾是( c )。（ × ）34順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（ B ）1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對(duì)多關(guān)系 B）

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

17、備輸入、輸出和 等5個(gè)特性。A) 可行性、可移植性和可擴(kuò)充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性（ C ）7數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲(chǔ)結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲(chǔ)結(jié)構(gòu) （D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（ B ）8.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是 （A）110 （B）108 （C）100 （D）120（ A ）9. 在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是：（A） 訪問第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） （B）

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

19、（ D ）13. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:（A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以（ B ）14 線性表在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。（）需經(jīng)常修改中的結(jié)點(diǎn)值 （）需不斷對(duì)進(jìn)行刪除插入 （）中含有大量的結(jié)點(diǎn) （）中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（ B ）15.棧中元素的進(jìn)出原則是 先進(jìn)先出 后進(jìn)先出 棧空則進(jìn) 棧滿則出（ C ）16. 若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為i n=i n-i+1 不確定（ B ）17. 判定一個(gè)棧ST（最多元素為m0）為空的條件是S

20、T->top<>0 ST->top=0 ST->top<>m0 ST->top=m0（ C ）18. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。A1/2 B. 1 C. 2 D. 4 （ B ）19. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。A1/2 B. 1 C. 2 D. 4 （ B ）20. 有8個(gè)結(jié)點(diǎn)的無向圖最多有 條邊。 A14 B. 28 C. 56 D. 112 （ C ）21. 有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。 A14 B. 28 C. 56 D. 11對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了 D 。A方便運(yùn)算 B

21、 方便存儲(chǔ) C提高運(yùn)算速度 D減少存儲(chǔ)空間設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1，1為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a8，5的地址為 B 。A13 B 33 C18 D40允許對(duì)隊(duì)列進(jìn)行的操作有 D 。A對(duì)隊(duì)列中的元素排序 B取出最近進(jìn)隊(duì)的元素 C在隊(duì)頭元素之前插入元素 D刪除隊(duì)頭元素輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為 B 。Apush，pop，push，pop，push，pop Bpush，push，push，pop， pop， pop Cpush，push，pop， pop，push，pop Dpush，pop，push，

22、push，pop， pop（ B ）22在表長(zhǎng)為的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為. ; . （）; . ; . （）（ A ）23折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中 比較大小，查找結(jié)果是失敗。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（ C ）24對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較 次關(guān)鍵字。A3 B4 C5 D 6（ A ）25. 鏈表適用于 查找A順序 B二分法 C順序，也能二分法 D隨機(jī)四、簡(jiǎn)答題1.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎

23、？答：簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。2. 簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。3、分析下面各程序段的時(shí)間復(fù)雜度(1.) for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;答：O（m*n）1. 項(xiàng)基本原則(2.) x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+;解：因?yàn)閤+共執(zhí)行了n-1+n-2+1= n(n-1)

24、/2，所以執(zhí)行時(shí)間為O（n2）4.設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。 全進(jìn)之后再出情況，只有1種：4，3，2，1 進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4 進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,35.給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I； 中

25、序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并簡(jiǎn)述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。 D A C FE GB H I6. 試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I M

26、LRD：J F K G D B H L M I E C A數(shù)據(jù)結(jié)構(gòu)的概念：數(shù)據(jù)之間的內(nèi)在聯(lián)系。要了解3種數(shù)據(jù)結(jié)構(gòu)的概念：邏輯結(jié)構(gòu)；物理結(jié)構(gòu)；基本操作。例如：棧和隊(duì)的邏輯結(jié)構(gòu)都是線性的，但她們的基本操作不同，就是不同的數(shù)據(jù)結(jié)構(gòu)。常見的數(shù)據(jù)結(jié)構(gòu)的分類：線性關(guān)系；集合關(guān)系；一對(duì)多；多對(duì)多（圖）；什么事物理結(jié)構(gòu)（應(yīng)該有印象）。算法設(shè)計(jì)時(shí)要用類PASCAL,類C，不要用C+.算法分析的常用方法：事前分析；事后統(tǒng)計(jì)。時(shí)間/空間復(fù)雜度的概念?？臻g是算法運(yùn)行時(shí)資源占用情況。 時(shí)間復(fù)雜度：最壞，最好，平均。例如：歸并排序都是O（n*logn），最好，最懷，平均都是一樣的   插入排序：最好為

27、O(n) ,最壞為O（n2）線性表：邏輯關(guān)系，各種基本操作，兩個(gè)有序表的歸并。線性表的順序存儲(chǔ)：線性表的操作在順序表中的實(shí)現(xiàn)。例如：1。插入與刪除和插入的位置與表長(zhǎng)有關(guān)。   2在一個(gè)長(zhǎng)為n的表中插入一個(gè)元素的平均復(fù)雜度，要有插入位置的概率分布表達(dá)式，即給出此表達(dá)式，算平均復(fù)雜度。線性表的鏈?zhǔn)酱鎯?chǔ)：鏈表的基本操作：2個(gè)有序表的歸并。例如：1。把鏈表就地逆置：一個(gè)指針P指向當(dāng)前逆置好的一系列節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)，取P的NEXT插入隊(duì)頭。   2三色問題：節(jié)點(diǎn)紅黃藍(lán)在鏈表上無序排列，把他們按紅黃藍(lán)的順序排好。要求只能從頭到尾搜索一遍。設(shè)當(dāng)前指針P，頭指針S，S

28、.NEXT為Q，S后接紅節(jié)點(diǎn)。若P為紅，插入S后。若P為黃，插入Q后。若P為蘭，不動(dòng)。然后P向后移，求下個(gè)。注：要了解單鏈表的插入，刪除在什么位置操作。靜態(tài)鏈表（數(shù)組表示）：不能象單鏈表那樣不受限增加節(jié)點(diǎn)。循環(huán)鏈表：如果表示隊(duì)列，用它最好。P指向隊(duì)尾。好處：用于優(yōu)先隊(duì)列中。雙向鏈表：?jiǎn)捂湵碇兄挥蠵指向當(dāng)前節(jié)點(diǎn)，不能刪除P。因?yàn)闊o法找到P 的前驅(qū)。而雙向鏈表可以。注意指針變化情況。棧：后進(jìn)先出?；静僮鳎撼鋈霔?，取棧頂。在順序表和鏈表上的實(shí)現(xiàn)；出棧序列是否合理？例如：入棧序列是1，2，n，則出棧序列有幾種？（即n個(gè)節(jié)點(diǎn)的二叉樹的個(gè)數(shù)。因?yàn)闃涞南刃蚴?，2，n）。棧與遞歸：見我給你寄過去的手寫體。

29、隊(duì)列：先進(jìn)現(xiàn)出。鏈隊(duì)列，循環(huán)隊(duì)列。例如：1。把從隊(duì)頭開始的第i個(gè)元素刪除：隊(duì)列 只有出隊(duì)入隊(duì)，不能直接刪除。要先將前i-1個(gè)出隊(duì)，入隊(duì)尾；i出隊(duì)；i+1以后的出隊(duì)入隊(duì)尾。   2隊(duì)列逆置（隊(duì)頭與隊(duì)尾交互）：出隊(duì)入棧；后出棧入隊(duì)。注意：這些結(jié)構(gòu)的基本操作有什么，不能混。循環(huán)隊(duì)列：隊(duì)頭指針和隊(duì)尾指針。記住隊(duì)空和滿的標(biāo)志。見手寫版。串：1。KMP算法，求NEXT函數(shù)值等。時(shí)間：O(n+m)。其中，模式匹配為O（n）；預(yù)處理為O（m）,要會(huì)證明她們。簡(jiǎn)略證明見手寫版。      2求兩串的最長(zhǎng)公共子串，時(shí)間為O（n）是不行的，至少要O（n2）

30、。具體證明估計(jì)不會(huì)考。17數(shù)組：存儲(chǔ)位置與下標(biāo)對(duì)應(yīng)。特殊數(shù)組（對(duì)稱，上三角等）。  三元組，稀疏矩陣（求逆）。計(jì)數(shù)技術(shù)，在設(shè)計(jì)算法中的應(yīng)用。   十字鏈表不考。   廣義表：基本概念，存儲(chǔ)結(jié)構(gòu)（二叉鏈表）。應(yīng)用不考。   廣義表遞歸算法了解。二叉樹的性質(zhì)（熟）。   存儲(chǔ)結(jié)構(gòu)：二叉鏈表，三叉鏈表。   遍歷：中，先，后。 按層遍歷：用輔助隊(duì)列。例如求K層有多少節(jié)點(diǎn)。線索二叉樹：中序（先后序不考）。線索中的插入刪除不考。樹與森林的遍歷：樹的先根與后根（分別對(duì)應(yīng)相應(yīng)二叉樹的先序，

31、中序）。森林的先序和后序（分別對(duì)應(yīng)相應(yīng)二叉樹的先序，中序）。樹與二叉樹一一對(duì)應(yīng)。由先序中序可以唯一確定二叉樹。而由先序后序不能。例子見手寫版。二叉樹可以為空，樹不能為空（樹為有根有序樹）。樹與等價(jià)：例如：判斷一個(gè)元素是否屬于一個(gè)特定的集合，可看這個(gè)節(jié)點(diǎn)是否在此樹上?？磧蓚€(gè)節(jié)點(diǎn)是否在一個(gè)強(qiáng)聯(lián)通分量，看他們是否在一棵樹上。求KRUSCAL算法（最小生成樹集合）。哈夫曼：前綴碼。它是加權(quán)外部路徑長(zhǎng)度最小的二叉樹。它是嚴(yán)格二叉樹，無度為1的點(diǎn)。節(jié)點(diǎn)個(gè)數(shù)2×葉節(jié)點(diǎn)1。 構(gòu)造，編碼。擴(kuò)展：用0，1，2三進(jìn)制編碼：元素個(gè)數(shù)為奇。N個(gè)元素K進(jìn)制：K-1整除N-1。否則增加概率為零的元素。注意11。6

32、節(jié)的最佳歸并。樹的計(jì)數(shù)：記結(jié)論。N個(gè)操作符或N個(gè)括號(hào)，為操作符加括號(hào)的情況數(shù)目。N2個(gè)頂點(diǎn)的凸多邊形，他的不同三角剖分的個(gè)數(shù)。a1,a2,an, ai=1/-1,任意前k個(gè)ai之和大于等于0， 動(dòng)態(tài)查找：二叉排序樹：中序遍歷有序，先序無序。給出先（或后）序的次序，寫出此樹（因?yàn)橹行蚴琼樞虻?，已知）。他的插入和刪除（刪除不一定考）。給定樹，求平均查找長(zhǎng)度。查找長(zhǎng)度的量級(jí)。平衡二叉樹：一定是二叉排序樹。樹的所有子樹都是平衡二叉樹。反之不成立。若要執(zhí)行4種旋轉(zhuǎn)，至少7個(gè)節(jié)點(diǎn)。M階B樹：關(guān)鍵字個(gè)數(shù)的上下限。N個(gè)關(guān)鍵字構(gòu)成樹的節(jié)點(diǎn)數(shù)目層數(shù)。B樹的概念。  鍵樹。哈希表：解決沖突的方法

33、。只有鏈地址法可以解決二次聚集。不是同義詞不會(huì)競(jìng)爭(zhēng)同一位置。鏈地址法是順序結(jié)構(gòu)和鏈結(jié)構(gòu)的完美結(jié)合。查找長(zhǎng)度：1。探測(cè)次數(shù)（包括最后一次比較為空的次數(shù)）。       2關(guān)鍵字比較次數(shù)（不包括最后一次為空的）。37內(nèi)部排序：簡(jiǎn)單插入排序（穩(wěn)定）；折半（不穩(wěn)定）；希爾（不穩(wěn)定）；冒泡（穩(wěn)定）；快速（不穩(wěn)定）；選擇（不穩(wěn)定）；堆（不穩(wěn)定）；歸并（穩(wěn)定）。要記住她們的時(shí)間復(fù)雜度（最好，平均，最壞）。  基數(shù)排序：給定N個(gè)數(shù)，范圍在（0，n2-1），以O(shè)(n)時(shí)間排序。記ni=ai*n+bi，按(ai,bi)先以bi為基數(shù)排序，再以ai 排。&

34、#160; 基數(shù)排序利用關(guān)鍵字本身的值，而其他基于比較。找最大和最小值的時(shí)間3/2n-2。見手寫版。兩兩比較，小的方一個(gè)數(shù)組，大的放一個(gè)數(shù)組，再找。找最大和次大值：可以調(diào)整堆，也可以記下比較6數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料12010-01-06 10:43一、名詞解釋：1. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)的組織形式，也可看成是包含數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)表，說明數(shù)據(jù)之間存在著一定的相互關(guān)系或約束。2. 邏輯結(jié)構(gòu)我們把只表現(xiàn)元素之間邏輯關(guān)系，而不涉及它們?cè)谟?jì)算機(jī)中的表示，只是理論的、反映在紙面上的東西，這種抽象的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。3. 物理結(jié)構(gòu)抽象的數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的表示，也就是映射在存儲(chǔ)空間上的、具體的數(shù)據(jù)

35、結(jié)構(gòu)在計(jì)算機(jī)內(nèi)表示，也就是映射在存儲(chǔ)空間上的、具體的數(shù)據(jù)結(jié)構(gòu)。二、問答題：2.       說明對(duì)程序進(jìn)行評(píng)價(jià)時(shí)，“時(shí)間”與“空間”之間的關(guān)系。答：時(shí)間性和空間性是程序的效率問題。時(shí)間效率決定于：源程序轉(zhuǎn)換為目標(biāo)程序的時(shí)間和目標(biāo)程序執(zhí)行的時(shí)間。時(shí)間效率與編譯質(zhì)量有關(guān)，與算法的簡(jiǎn)化程度有關(guān)，還與用戶對(duì)語言的熟練程度有關(guān)，其中，算法的效率起主要作用。空間效率一般指程序花費(fèi)的內(nèi)存空間的問題。對(duì)于同等復(fù)雜程度的程序：一般時(shí)間效率越高的程序，占用的內(nèi)存就越大，空間效率就越低；一般時(shí)間效率越低的程序，占用的內(nèi)存就越小，空間效率就越高。兩者具有一定

36、的矛盾性。但是隨著內(nèi)存容量的不斷增大，往往會(huì)犧牲空間性來提高時(shí)間性。五、將二叉樹的左右孩子交換的算法：algorithm swap( Tree *b )            Tree *t;            if( b = null )              

37、;   return;            else                             t = b->lchild;        

38、;         b->lchild = b->rchild;                 b->rchild = t;                 swap( b->lchild );

39、                 swap( b->rchild );            六、用兩個(gè)棧模擬一個(gè)隊(duì)列：       algorithm 用兩個(gè)棧模擬一個(gè)隊(duì)列       stack s1, s2; / 容量

40、都為n。            void 元素入隊(duì)                             int x;           

41、0;     if( s1->top = n )                          printf( "隊(duì)列上溢" );              &

42、#160;  else                          push( s1, x );                           void 元素出隊(duì)                             int x;