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

1、數(shù)據(jù)結(jié)構(gòu)復(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è)前驅(qū)結(jié)點(diǎn)； 最后一

2、個(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)的元素個(gè)數(shù)與 表長(zhǎng)和該元素在表中的位置有關(guān)。1

3、3 .線性表中結(jié)點(diǎn)的集合是 有限 的,結(jié)點(diǎn)間的關(guān)系是一對(duì)一 的。14 .向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素（1&i&n+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1 個(gè)元素。15 .向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素（1&i&n）時(shí)，需向前移動(dòng)n-i個(gè)元素。16 .在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為。，因此，順序表也稱為隨機(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ù)組A6X8,每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知 A 的起始存儲(chǔ)位置（基地址）為1000,則數(shù)組A的體積（存儲(chǔ)量）為 288 B ;末尾元 素A57的第一個(gè)字節(jié)地址為1282;若按行存儲(chǔ)時(shí)，元素 Ai4的第一個(gè)字節(jié)地址為（8+4）X6+1000=1072;若按列存儲(chǔ)時(shí)，元素 A47的第一個(gè)字節(jié)地址為（6X 7+4）X6 +1000） =1276。26 .由3個(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è)葉 子。注：滿二叉機(jī)t沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)28

6、. 一棵具有2 5 7個(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/2 =35030 .設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有 500個(gè)葉子結(jié)點(diǎn),有 499仝度為2的結(jié)點(diǎn)，有 1 個(gè)結(jié)點(diǎn)只有非空左子樹，有 0 個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)=n/2 =500 , n2=n0-1=499。另外，最后一結(jié)點(diǎn)為 2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)=0.31 .在數(shù)

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

8、1Xlog221) /20 = 4.6次并不正確！)。因?yàn)檫@是在假設(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, 10。，若查找表中元素20,它 將依次與表中元素 28, 6, 12, 20 比較大小。35 .在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù) n無關(guān)的查找方法是散列查找。36 .散列法存儲(chǔ)的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。二、判斷正誤(在正確的說法后面打勾，反之

9、打叉)(X) 1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表 中的結(jié)點(diǎn)可以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。(X) 2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò)，鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無序，而鏈表的示意圖有序。(X) 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)容改變。(X)4.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放 記

10、錄型數(shù)據(jù)。(X) 5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。錯(cuò)，正好說反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”(X) 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ù)元素。(X) 7.線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。錯(cuò)，線性表有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。后者不要求連續(xù)存放。(X) 8.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。錯(cuò)誤。線性表有兩種存

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

12、，CPU中也用隊(duì)列。(V) 13.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表， 是一種后進(jìn)先出 型結(jié)構(gòu)。(V) 14.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。正確，都是線性邏輯結(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ǔ)方式既可是順序方式，也可是鏈接方式。(，)1

13、8.兩個(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ò)，后半句不對(duì)。(X) 20. 一個(gè)棧的輸入序列是1234a則棧的輸出序列不可能是1234s錯(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)鍵字值

14、大于其左非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵 字值，且小于其右非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值。(應(yīng)當(dāng)是二叉排序樹的特點(diǎn))(X) 26二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是 2-1-1,其中k是樹的深度。(應(yīng)2i-1)(X) 27二叉樹中所有結(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)選擇題1 .非線性結(jié)構(gòu)是

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

16、B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性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)8 .一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是(A) 110(B) 108(C) 100(D) 1209 .在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O (1)的操作是：(A)訪問第i個(gè)結(jié)點(diǎn)(1&i&n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(20i&n)(B)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1&iwn)(C)刪除第i個(gè)結(jié)點(diǎn)(

17、1<i<n)(D)將n個(gè)結(jié)點(diǎn)從小到大排序10 .向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)一個(gè)兀索(A) 8(B) 63.5(C) 63(D) 711 .鏈接存儲(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ù)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ù)的

18、(B)部分地址必須是連續(xù)的(C)一定是不連續(xù)的(D)連續(xù)或不連續(xù)都可以14 .線性表L在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。(A)需經(jīng)常修改L中的結(jié)點(diǎn)值(B)需不斷對(duì)L進(jìn)行刪除插入(C) L中含有大量的結(jié)點(diǎn)(D) L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜15棧中元素的進(jìn)出原則是A.先進(jìn)先出 B.后進(jìn)先出 C.?？談t進(jìn) D.棧滿則出16.若已知一個(gè)棧的入棧序列是 1, 2, 3,，n,其輸出序列為pl, p2, p3,，pn,若 p1=n,則 pi 為A. i B . n=i C. n-i+1 D.不確定17.判定一個(gè)棧ST (最多元素為m0)為空的條件是A. ST->top<>0 B . ST->top=0 C. ST->top<>m0D . ST->top=m018.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。A. 1/2B.1C.2D.419.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。A. 1/2B.1C.2D.420 .有8個(gè)結(jié)點(diǎn)的無向圖最多有 條邊。A. 14B. 28C. 56D. 11221 .有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。A. 14B. 28C. 56D. 11222 .在表長(zhǎng)為n的鏈表中進(jìn)行線性查找，它的平均查