數(shù)據(jù)結(jié)構(gòu)(C語言版)知識點(diǎn)復(fù)習(xí)資料

1、歡迎閱讀數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料一、填空題1 .數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的 關(guān)系 和 運(yùn)算等的學(xué)科。2 .數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R）,其中D是 數(shù)據(jù)元素的有限集合,R是D上的 關(guān)系有限集合。I _ 3 .數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算 這三個方面的內(nèi)容。/J I I4 .數(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é)點(diǎn) 沒有前驅(qū)結(jié)點(diǎn)、其余每個結(jié)點(diǎn)有且只有1個前驅(qū)

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

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

4、指示。19 .在n個結(jié)點(diǎn)的單鏈表中要刪除已知結(jié)點(diǎn)*p,需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時間復(fù)雜度為0 （n）。20 .向量、棧和隊列都是 線性 結(jié)構(gòu)、可以在向量的 任何位置插入和刪除元素:對于棧只能在 棧頂插入和刪除元素:對于隊列只能在.隊星插入和隊首刪除元素。21 .棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂 。不允許插入和刪除運(yùn)算的端稱為棧底 022 . 隊列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算、在表的另一端進(jìn)行刪除運(yùn)算的線性表。 t / i *J一| |23 .不包含任何字符（長度為 0）的串 稱為空串:由一個或多個空格（僅由空格符）組成的串 稱為空白串。24 .子用的定位運(yùn)算

5、稱為用的模式匹配；被匹配的豐串稱為目標(biāo)串, 千串 稱為模式。25 .假設(shè)有二維數(shù)組 A8,每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知 A的起始存 儲位置（基地址）為1000,則數(shù)組A的體積（存儲量）為 288 B ;末尾元素A7的第一個字 節(jié)地址為 1282;若按行存儲時.元素A14的第一個字節(jié)地址為 （8+4） X 6+1000=1072 ;若按列存儲時，元素 A47的第一個字節(jié)地址為 （6 X 7 + 4） X 6+1000） =1276。26 .由3個結(jié)點(diǎn)所構(gòu)成的二叉樹有 5種形態(tài)。27 .一棵深度為6的滿二叉樹有n1+n2=0+ n2= n0-1=31個分支結(jié)點(diǎn)和26-1 =

6、32 個葉子。頁腳內(nèi)容歡迎閱讀注：滿二叉樹沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。28 . 一棵具有2 5 7個結(jié)點(diǎn)的完全二叉樹，它的深度為 9。 注：用 log2(n)+1=8.xx+1=929 .設(shè)一棵完全二叉樹有 700個結(jié)點(diǎn)，則共有350個葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)=n二 35030 .設(shè)一棵完全二叉樹具有1000個結(jié)點(diǎn)，則此完全二叉樹有 500 個葉子結(jié)點(diǎn)，有499 個 度為2的結(jié)點(diǎn)，有1.個結(jié)點(diǎn)只有非空左子樹，有 0 個結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)=n/2 =500 , n2=n0-1=499。另外，最后一結(jié)點(diǎn)為 2i屬于左葉子， 右葉子是空的，所以有1

7、個非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所 以非空右子樹數(shù)=0.31 .在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是順序查找(線性查找)。32 .線性有序表(日，82, a3,a256)是從小到大排列的，對一個給定的值 k,用二分法檢索表中 與k相等的元素，在查找不成功的情況下，最多需要檢索 _8 次。設(shè)有100個結(jié)點(diǎn)，用二分法查 找時，最大比較次數(shù)是 7。33 .假設(shè)在有序線性表a20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1;比較兩次查找成功的結(jié)點(diǎn)數(shù)為 2;比較四次查找成功的結(jié)點(diǎn)數(shù)為 8;平均查找長度為 3.7。解：顯然，平土杳找長度= O (log2n)

8、5次(25)。但具體是多少次，則不應(yīng)當(dāng)按照公式c n 1ASL log2(n 1)n來計算(即(21Xlog221 ) /20 =4.6次并不正確！)。因為這是在假設(shè) n = 2m-1的情況下推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為=(1+2X2 + 4X3+ 8X4+5X5) =74; ASL= 74/20=3.7!34 .折半查找有序表(4,6, 12,20,28, 38, 50,70,88,100),若查找表中元素20,它將依次與表中元素 28 、 6、12、20比較大小。35 .在各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)的查找方法是散列查找。36 .散列法存儲的基本思

9、想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲地址。頁腳內(nèi)容歡迎閱讀二、判斷正誤(在正確的說法后面打勾，反之打叉)(X) 1.鏈表的每個結(jié)點(diǎn)中都恰好包含一個指針。答：錯誤。鏈表中的結(jié)點(diǎn)可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結(jié) 點(diǎn)可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。(X) 2.鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點(diǎn)是無序，而鏈表的示意圖有序。(X) 3.鏈表的刪除算法很簡單，因為當(dāng)刪除鏈中某個結(jié)點(diǎn)后，計算機(jī)會自動地將后續(xù)的各個單 元向前移動。 I錯，鏈表的結(jié)點(diǎn)不會移動，只是指針內(nèi)容改變。(X) 4.線性表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個

10、結(jié)點(diǎn)可以是一個復(fù)雜類型。 if ； 1 z， X A卡y X |錯，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型 數(shù)據(jù)。II(X) 5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。錯，正好說反了。順序表才適合隨機(jī)存取，然表恰恰適于“順藤摸瓜”I I111/J(X) 6.順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。/7 一 錯：前一半正確：伸后一半說法錯誤：那是鈉式存儲的優(yōu)點(diǎn)。順序存儲方式插入、刪除 1 :運(yùn)算效率較低：在表長為n的順序表中：插入和刪除一個數(shù)據(jù)元素： 平均需移動表長一 半個數(shù)的數(shù)據(jù)元素。(X) 7.線性表在物理存儲空間中也一定是

11、連續(xù)的。錯，線性表有兩種存儲方式，順序存儲和鏈?zhǔn)酱鎯?。后者不要求連續(xù)存放。(X) 8.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，涉輯上相鄰的元素在存儲的物理位置次 序上也相鄰。歡迎閱讀(X) 9.順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯誤。順序存儲方式不僅能用于存儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式。(后一節(jié)介紹)(X) 10.線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈?zhǔn)酱鎯蜔o需一致。(X) 11.線性表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)點(diǎn)可以

12、是一個復(fù)雜類型。錯，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲或鏈?zhǔn)酱鎯Γc元素數(shù)據(jù)類型無關(guān)。(X) 12.在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。1 Ir ?弋、：./ ,錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPH也用隊列。()13.棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。(V) 14.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運(yùn)算的定義略有不同而已。(X) 15.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。(X

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

14、鏈表中只有 匚1個非空指針 域。(X) 22.二叉樹中每個結(jié)點(diǎn)的兩棵子樹的高度差等于1。(V) 23.二叉樹中每個結(jié)點(diǎn)的兩棵子樹是有序的。 I / _(X) 24.二叉樹中每個結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。(X) 25.二叉樹中每個結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值， 且小于其右非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值。(應(yīng)當(dāng)是二叉排序樹的特點(diǎn))(X) 26.二叉樹中所有結(jié)點(diǎn)個數(shù)是2k-1-1 ,其中k是樹的深度。(應(yīng)2i-1)(X) 27.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。(X) 28.對于一棵非空二叉樹，它的根2點(diǎn)作為第一層，則它的

15、第 i層上最多能有2i 1個結(jié)點(diǎn), (應(yīng) 2i-1 )(V) 29.用二叉鏈表法(link-rlink )存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個指針區(qū)域中有 n+1個為空指針。(V) 30.具有12個結(jié)點(diǎn)的完全二叉樹有5個度為2的結(jié)點(diǎn)。 I I三、單項選擇題1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A) 一對多關(guān)系B)多對多關(guān)系C )多對一關(guān)系D ) 一對一關(guān)系2 .數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A)存儲 B) 物理C)邏輯 D) 物理和存儲3 .算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)研究算法中的輸入和輸出的關(guān)系歡迎閱讀C)分析算法的效率以求改進(jìn) D)分析算法的易懂性和

16、文檔性4 .算法分析的兩個主要方面是：A)空間復(fù)雜性和時間復(fù)雜性B)正確性和簡明性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性5 .計算機(jī)算法指的是：A)計算方法B)排序方法 C)解決問題的有限運(yùn)算序列D)調(diào)度方法6 .計算機(jī)算法必須具備輸入、輸出和 等5個特性。A)可行性、可移植性和可擴(kuò)充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性 D)易讀性、穩(wěn)定性和安全性7 .數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：(A)存儲結(jié)構(gòu) (B)邏輯結(jié)構(gòu)J：Q順序存儲結(jié)構(gòu)(D)鏈?zhǔn)酱鎯Y(jié)構(gòu)8 .一個向量第一個元素的存儲地址是 100,每個元素的長度為2,則第5個元素的地

17、址是(A) 110(B) 108(Q 100(D) 1209 .在n個結(jié)點(diǎn)的順序表中，算法的時間復(fù)雜度是 O (1)的操作是：(A) 訪問第i個結(jié)點(diǎn)(1&i & n)和求第i個結(jié)點(diǎn)的直接前驅(qū)(20i &n)(B)在第i個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)(1&i & n)(C)刪除第i個結(jié)點(diǎn)(1&i top0 B . ST-top=0 C . ST-topm0 D . ST-top=m018 .在一個圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。A . 1/2 B. 1C. 2D. 4，i I II * I19 .在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。A . 1/2B. 1C. 2 D. 420 .有8個結(jié)點(diǎn)的無向圖最多有 條邊。A . 14B. 28C. 56 D. 11221 .有8個結(jié)點(diǎn)的有向完全圖有 條邊。A . 14 B. 28C. 56D. 11222 .在表長為n的鏈表中進(jìn)行線性查找，它的平均查找長度為歡迎閱讀(n+ 1) /2 ;C . A S L +1；