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

1、任何的限度，都是從自己的心坎開(kāi)端的。每一奮發(fā)盡力的背地，必有加倍的彌補(bǔ)。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(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)可分為兩大類(lèi)它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 5. 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系6 在線性結(jié)構(gòu)中第一個(gè)結(jié)點(diǎn) 沒(méi)有 前

2、驅(qū)結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒(méi)有 后續(xù)結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)7. 在樹(shù)形結(jié)構(gòu)中樹(shù)根結(jié)點(diǎn)沒(méi)有 前驅(qū) 結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 后續(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. 在順序表中訪問(wèn)任意一結(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)的鏈域的值 指示19 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h

4、除已知結(jié)點(diǎn)*p需找到它的前驅(qū)結(jié)點(diǎn)的地址其時(shí)間復(fù)雜度為O（n）20. 向量、棧和隊(duì)列都是 線性 結(jié)構(gòu)可以在向量的 任何 位置插入和刪除元素；對(duì)于棧只能在 棧頂 插入和刪除元素；對(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è)有

5、二維數(shù)組A6×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)成的二叉樹(shù)有 5 種形態(tài) 27. 一棵深度為6的滿二叉樹(shù)有 n1+n2=0+ n2= n0-1=31 個(gè)分支結(jié)點(diǎn)和 26-1 =32 個(gè)葉子注：滿二叉樹(shù)沒(méi)有度為1的結(jié)點(diǎn)所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)

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

7、佳方法是 順序查找（線性查找） 32. 線性有序表（a1a2a3.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)按照公式來(lái)計(jì)算（即（21×log221）/204.6次并不正確?。┮?yàn)檫@是在假設(shè)n2m-1的情況下推導(dǎo)出來(lái)的公式應(yīng)當(dāng)

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

9、存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針（ × ）2. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序錯(cuò)鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無(wú)序而鏈表的示意圖有序（ × ）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)單類(lèi)型而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類(lèi)型錯(cuò)混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)鏈表也是線性表！且即使是順序表也能存放記錄型數(shù)據(jù)（ × ）5. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取而鏈表適宜于進(jìn)行隨機(jī)存取 錯(cuò)正好說(shuō)反了順序表才適合隨機(jī)存取鏈表恰恰適于"順藤摸

10、瓜"（ × ）6. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大且插入、刪除運(yùn)算效率高錯(cuò)前一半正確但后一半說(shuō)法錯(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. 線性表在順序存儲(chǔ)時(shí)邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰錯(cuò)誤線性表有兩種存儲(chǔ)方式在順序存儲(chǔ)時(shí)邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也相鄰（ × ）9. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu) 錯(cuò)

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

12、）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)概念二者不是同類(lèi)項(xiàng)（ × ）16. 棧和隊(duì)列是一種非線性數(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

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

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

15、一關(guān)系 D）一對(duì)一關(guān)系（ C ）2. 數(shù)據(jù)結(jié)構(gòu)中與所使用的計(jì)算機(jī)無(wú)關(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) 解決問(wèn)題的有限運(yùn)算序列 D) 調(diào)度方法（ B ）6. 計(jì)算機(jī)算法必須具備輸入、輸出和 等5個(gè)

16、特性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） 訪問(wèn)第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） （B） 在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1

17、in）（C） 刪除第i個(gè)結(jié)點(diǎn)（1in）（D） 將n個(gè)結(jié)點(diǎn)從小到大排序（ B ）10. 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變平均要移動(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)狀（ D ）13. 線性表若采用鏈?zhǔn)酱鎯?chǔ)

18、結(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)先出 ?？談t進(jìn) 棧滿則出（ C ）16. 若已知一個(gè)棧的入棧序列是123.n其輸出序列為p1p2p3.pn若p1=n則pi為 i n=i n-i+1 不確定（ B ）17. 判定一個(gè)棧ST（最多元素為m0）為空的條件是 ST->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)的無(wú)向圖最多有 條邊 A14 B. 28 C. 56