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

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

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

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

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

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

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

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

8、來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為=（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. 在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是_散列查找。35. 散列法存儲(chǔ)的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。二、判斷正誤(在正確的說法后面打勾，反之打叉)(x)1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分另U存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有

9、兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。(X)2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò)，鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無序，而鏈表的示意圖有序。(X)3.鏈表的刪除算法很簡單，因?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)容改變。(X)4.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。(X)5順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。錯(cuò)，正好說反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”(X)6順序存

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

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

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

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

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

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

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

17、所占存儲(chǔ)空間：分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針只有一部分，存放結(jié)點(diǎn)值只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)(A)(B)(C)(D)12.鏈表是一種采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表;(A)順序(B)鏈?zhǔn)?C)星式(D)網(wǎng)狀13.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單兀的地址(A)必須是連續(xù)的(C)一定是不連續(xù)的(B)部分地址必須是連續(xù)的(D)連續(xù)或不連續(xù)都可以(則pi14.線性表L在(A)需經(jīng)常修改L中的結(jié)點(diǎn)值(C)L中含有大量的結(jié)點(diǎn)情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。需不斷對(duì)L進(jìn)行刪除插入L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜15.棧中元素

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