《數(shù)據(jù)結(jié)構(gòu)》填空作業(yè)題(答案)

1、數(shù)據(jù)結(jié)構(gòu)填空作業(yè)題答案第 1 章緒論 （已校對無誤）1 ? 數(shù)據(jù)結(jié)構(gòu)包括 數(shù)據(jù)的邏輯結(jié)構(gòu)、 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 和 數(shù)據(jù)的運(yùn)算 三方面的內(nèi)容。2 ? 程序包括兩個(gè)內(nèi)容： 數(shù)據(jù)結(jié)構(gòu) 和 算法 。3. 數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組： Data Structure = （D, S）。4. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。5. 數(shù)據(jù)的邏輯結(jié)構(gòu)可以分類為 線性 結(jié)構(gòu)和 非線性 結(jié)構(gòu)兩大類。6. 在圖狀結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以有多個(gè)。7. 在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在一對多的關(guān)系。8. 數(shù)據(jù)的物理結(jié)構(gòu)，指數(shù)據(jù)元素在 計(jì)算機(jī) 中的標(biāo)識(shí)（映象），也即

2、存儲(chǔ)結(jié)構(gòu)。9. 數(shù)據(jù)的邏輯結(jié)構(gòu)包括 線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu) 3 種類型，樹型結(jié)構(gòu)和有向 圖結(jié)構(gòu)合稱為 非線性結(jié)構(gòu) 。10. 順序存儲(chǔ)結(jié)構(gòu)是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上連續(xù)的存儲(chǔ)單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元位置的鄰接關(guān)系來體現(xiàn)。11. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上任意 的存儲(chǔ)單元里，節(jié)點(diǎn)之間的邏輯關(guān)系由附加的指針域來體現(xiàn)。12. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用 4 種基本的存儲(chǔ)方法表示，它們分別是 順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引 存儲(chǔ)和散 列存儲(chǔ)。13. 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對一 的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 對多或多對多 。14. 數(shù)據(jù)結(jié)構(gòu)在物理上可分為 順

3、序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。15. 我們把每種數(shù)據(jù)結(jié)構(gòu)均視為抽象類型，它不但定義了數(shù)據(jù)的 表示 方式，還給出了處理數(shù) 據(jù)的實(shí)現(xiàn) 方法 。16. 數(shù)據(jù)元素可由若干個(gè) 數(shù)據(jù)項(xiàng) 組成。17. 算法分析的兩個(gè)主要方面是 時(shí)間 復(fù)雜度和 空間 復(fù)雜度。18. 一個(gè)算法的時(shí)間復(fù)雜度是用該算法 所消耗的時(shí)間 的多少來度量的，一個(gè)算法的空間復(fù)雜 度是用該算法在運(yùn)行過程中所占用的 存儲(chǔ)空間的大小來度量的。19. 算法具有如下特點(diǎn)： 有窮性、確定性、 可行性 、輸入、輸出。20. 對于某一類特 定的問題，算法給出了解決問題的一系列操作，每一操作都有它的 確切 的定義，并在有窮時(shí)間內(nèi)計(jì)算出結(jié)果。21. 下面程序段的時(shí)

4、間復(fù)雜度為 3L。i=1 ；while(i<=n)i= i * 3；第 2 章線性表 ( 已校對無誤 )1. 一線性表表示如下： (ai, a2, ， ai-i, a , a+1,，an), 其中每個(gè) ai代表一個(gè)數(shù)據(jù)元素 (或 結(jié)點(diǎn))。ai稱為 起始 結(jié)點(diǎn),an稱為 終端 結(jié)點(diǎn), i 稱為 a 在線性表中的 位置( 或序號(hào) ) 。 對任意一對相鄰結(jié)點(diǎn) ai,ai+i, (1 <i<n), a 稱為 ai+i的直接 前驅(qū)， a+i稱為 a 的直接 后繼。2. 對一個(gè)長度為 n 的線性表，要?jiǎng)h除第 i 個(gè)元素，則在順序表示的情況下，計(jì)算復(fù)雜性為 0(n), 在鏈?zhǔn)奖硎镜那闆r下，

5、計(jì)算復(fù)雜性為 0(i) 。3. 在一個(gè)長度為 n 的順序表中，向第 i 個(gè)元素 (K i< n)之前插入一個(gè)新元素時(shí)，需向后移動(dòng)n i + i 個(gè)元素。4. 順序表中邏輯上相鄰的元素在物理位置上 一定相連。5. 在 n 個(gè)結(jié)點(diǎn)的順序表中插入一個(gè)結(jié)點(diǎn)需平均移動(dòng)n/2 個(gè)結(jié)點(diǎn)，具體的移動(dòng)次數(shù)取決于 _表長 n 和插入位置 i 。6. 在順序表中訪問任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為0(i), 因此，順序表也稱為隨機(jī)訪問的數(shù)據(jù)結(jié)構(gòu)。7. 順序表相對于鏈表的優(yōu)點(diǎn)有 隨機(jī)訪問和空間利用率高 。8. 在長度為 n 的順序表中插入一個(gè)元素的時(shí)間復(fù)雜度為0(n)。9. 在帶有頭結(jié)點(diǎn)的單鏈表 L 中，若要?jiǎng)h除第

6、一個(gè)結(jié)點(diǎn)，則須執(zhí)行下列三條語句： U = L->next ; L->next=U->next ； free (U ) 。10. 鏈表相對于順序表的優(yōu)點(diǎn)有 插入和刪除操作方便。11. 在單鏈表中除首結(jié)點(diǎn)外，任意結(jié)點(diǎn)的存儲(chǔ)位置都由 直接前驅(qū) 結(jié)點(diǎn)中的指針指示。12. 在 n 個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn) *p, 需找到它的直接前驅(qū)結(jié)點(diǎn)的地址 ，其時(shí)間復(fù) .雜度為 O(n) 。13. 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 簡化操作，減少邊界條件的 判斷 。14. 在帶表頭結(jié)點(diǎn)的單 鏈表中，當(dāng)刪除某一指定結(jié)點(diǎn)時(shí)，必須找到該結(jié)點(diǎn)的 前驅(qū) 結(jié)點(diǎn)。15. 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向

7、 前驅(qū)結(jié)點(diǎn) ，另一個(gè)指向 后續(xù)結(jié)點(diǎn) 。16. 帶頭結(jié)點(diǎn)的單鏈表 L 為空的判定條件是 L->next=NULL ，不帶頭結(jié)點(diǎn)的單鏈表 L 為空的判 定條件 是 L=NULL 。17. 在單鏈表中，指針 p 所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是 p-> next=NULL18. 循環(huán)鏈表的最大優(yōu)點(diǎn)是 從表中任意結(jié)點(diǎn)出發(fā)都可訪問到表中每一個(gè)元素（或從表中任意結(jié) 點(diǎn)出發(fā)都可遍歷整個(gè)鏈表） 。19. 設(shè) rear 是指向非空、帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，則該鏈表首結(jié)點(diǎn)的存儲(chǔ)位置是 rear->n ext- >n ext 。20. 帶頭結(jié)點(diǎn)的雙向循環(huán)表 L 為空表的條件是 L->

8、; prior= L-> next 。21. 在循環(huán)鏈表中，可根據(jù)任一結(jié)點(diǎn)的地址遍歷整個(gè)鏈表，而單鏈表中需知道 頭指針 才能遍 歷整個(gè)鏈表。22. 將兩個(gè)各有 n 個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是 1 。第 3 章 棧和隊(duì)列 （已校對無誤）1. 棧又稱為 后進(jìn)先出 表，隊(duì)列又稱為 先進(jìn)先出 表。2. 向一個(gè)順序棧插入一個(gè)元素時(shí)，首先使 棧頂指針 后移一個(gè)位置 , 然后把待插入元素 寫入 （或插入） 到這個(gè)位置上。3. 從一個(gè)棧刪除元素時(shí)，需要前移一位 棧頂指針4. 在一個(gè)順序棧中，若棧頂指針等于1 ，則為空棧；若棧頂指針等于 maxSize 1 ，則為滿棧。5. 在一個(gè)

9、鏈?zhǔn)綏Ｖ校魲ｍ斨羔樀扔?NULL ，則為 空棧：在一個(gè)鏈?zhǔn)疥?duì)列中，若隊(duì)頭指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為空或該隊(duì)列只含有一個(gè)結(jié)點(diǎn)6. 向一個(gè)鏈?zhǔn)綏２迦胍粋€(gè)新結(jié)點(diǎn)時(shí)， 首先把棧頂指針的值賦給 新結(jié)點(diǎn)的指針域 ，然后把新結(jié) 點(diǎn)的存儲(chǔ)位置賦給棧頂指針 。7?在求表達(dá)式值的算符優(yōu)先算法中使用的主要數(shù)據(jù)結(jié)構(gòu)是棧。8. 設(shè)有一個(gè)順序棧 S，元素 s1， s2，s3， s4，s5, s6 依次 進(jìn)棧，如果 6 個(gè)元素的出棧順序?yàn)?s2, s3，s4，s6, s5, s1, 則順序棧的容量至少為 3 。9. 設(shè)有一個(gè)空棧，現(xiàn)輸入序列為 1, 2, 3, 4, 5。經(jīng)過 push, push, pop

10、, push, pop, push, pop , push 后，輸出序列是 2 3 4 。10. 在按算符優(yōu)先法求解表達(dá)式 3-1 + 5*2 時(shí)，最先執(zhí)行的運(yùn)算是 丄，最后執(zhí)行的運(yùn)算是 亠。11. 在棧的 ADT 定義中，除初始化操作外，其他基本操作的初始條件都要求 棧存在。12. 僅允許在同一端進(jìn)行插入和刪除的線性表稱為 棧。13. 在順序棧 s 中，棧為空的條件是 s.top=s.base ，棧為滿的條件是 s.top s.base> =s.stacksize 。14. 設(shè)有算術(shù)表達(dá)式 x+ a* （y b） c/d, 該表達(dá)式的前綴表示為 一+ x*a yb/cd 。 后綴表示為

11、 xayb * + cd/ 。1234 ，為了得到 1342 出棧順序，15. 用 S 表示入棧操作， X 表示出棧操作，若元素入棧順序?yàn)?相應(yīng)的 S、X 操作串為 SXSSXSXX 。16. 向一個(gè)棧頂指針為 top 的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)新結(jié)點(diǎn) *p 時(shí)，應(yīng)執(zhí)行 p->link = top 和 top = p 操作。17. 從一個(gè)棧頂指針為 top 的非空鏈?zhǔn)綏Ｖ袆h除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時(shí)， 應(yīng)執(zhí)行 top = top->li nk 操作。18. 設(shè)有一個(gè)空棧，棧頂指針為 1000H （十六進(jìn)制。現(xiàn)有輸入序列為 1, 2, 3, 4, 5, 經(jīng)過 PUSH, PU

12、SH, POP, PUSH , POP, PUSH, PUSH 之后，輸出序列是 2, 3 ，而棧頂指針是 100C H。 設(shè)棧為順 序棧，每個(gè)元素占 4 個(gè)字節(jié)。19. 在作入棧運(yùn)算時(shí)應(yīng)先判別棧是否 滿；在作出棧運(yùn)算時(shí)應(yīng)先判別棧是否 空。10. 用一個(gè)大小為 1000 的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，當(dāng)前 件，還需要繼續(xù)入隊(duì)的元素個(gè)數(shù)是 993 。20. 隊(duì)列的插入操作在 隊(duì)尾 進(jìn)行，刪除操作在21. 在一個(gè)循環(huán)隊(duì)列 Q 中，判斷隊(duì)空的條件為 （Q.rear+ 1 ） % maxSize=Q.fr ont 。22. 向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，需要首先移動(dòng) 插入）新插入的元素。23. 當(dāng)用長度為 n

13、的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，若用rear 和 front 的值分別為 0 和 994, 若要達(dá)到隊(duì) 滿的條 隊(duì)頭 進(jìn)行。Q.front=Q.rear ，判斷隊(duì)滿的條件為隊(duì)尾指針，然后再向所指位置 寫入（或top=n 表示?？?，則表示棧滿的條件為歡迎下載8top=0 。假溢出時(shí)大量移動(dòng)數(shù)據(jù)元素24. 循環(huán)隊(duì)列的引入，目的是為了克服 第 4 章串 （已校對無誤）1. 兩個(gè)串相等的充分必要條件是 兩個(gè)串的長度相等且對應(yīng)位置的字符相同 。2. 空格串是 由一個(gè)或多個(gè)空格字符組成的串 ，其長度等于 其包含的空格個(gè)數(shù) 。3. 模式串' abaabade 的 next 函數(shù)值為 01122341補(bǔ)充：1

14、. 串的兩種最基本的存儲(chǔ)方式是 順序存儲(chǔ)方式和鏈接存儲(chǔ)方式 。2. 空串是 零個(gè)字符的串 ，其長度等于 零 。3. 組成串的數(shù)據(jù)元素只能是 字符。4. 串是一種特殊的線性表，其特殊性表現(xiàn)在 其數(shù)據(jù)元素都是字符。第 5 章數(shù)組 （已校對無誤）1. 將下三角矩陣 A1 . 8, 1. 8的下三角部分逐行地存儲(chǔ)到起始地址為1000 的內(nèi)存單元中，已知每個(gè)元素占 4 個(gè)單元，則元素 A7, 5的地址為 1100 。A0 , 0的2. 二維數(shù)組 A09, 019采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且元素 存儲(chǔ)地址是 200, 則元素 A6 , 12 的地址是 332 。3. 二維數(shù)組 A10

15、20, 5-10采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占 4 個(gè)存儲(chǔ)單元，并且元素 A10, 5的存 儲(chǔ)地址是 1000, 則元素 A18 ， 9的地址是 1208補(bǔ)充：1. 一維數(shù)組的邏輯結(jié)構(gòu)是 線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)是 順序存儲(chǔ)結(jié)構(gòu) 。2. 對于二維數(shù)組或多維數(shù)組，分為按 以行為主序 和按 以列為主序 兩種不同的存儲(chǔ)方式存儲(chǔ)。3. 對矩陣壓縮存儲(chǔ)是為了 節(jié)省存儲(chǔ)空間 。4. 二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個(gè)數(shù)組元素最多有 二 個(gè)直接前驅(qū)（或直接后繼）。 第 6 章樹 （已校對無誤）4. 結(jié)點(diǎn)最少的樹為 只有一個(gè)結(jié)點(diǎn)的樹，結(jié)點(diǎn)最少的二叉樹為 空的二叉樹。5. 根據(jù)二叉樹的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹

16、有 5 種不同的形態(tài)，它們分別是 。6. 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。8. 以數(shù)據(jù)集 4，5, 6, 7, 10, 12，18為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹為需用圖示 ，其帶權(quán)路徑長度為 165 。9. 哈夫曼樹是帶權(quán)路徑長度 最短 的樹，通常權(quán)值較大的結(jié)點(diǎn)離根 較近。10. 在 先序 遍歷二叉樹的序列中，任何結(jié)點(diǎn)的子樹上的所有結(jié)點(diǎn)，都是直接跟在該結(jié)點(diǎn)之后。第 7 章圖 （已校對無誤）1. n 個(gè)頂點(diǎn)的連通圖至少有 n1 條邊。2?在無權(quán)圖 G 的鄰接矩陣 A 中，若（ vi, vj）或 vi, vj屬于圖 G 的邊集，則對應(yīng)元素 Aij等于L, 否則等于 0 。3. 在無向圖 G 的

17、鄰接矩陣 A 中，若 Aij等于 1, Aj i等于 1。4. 已知圖 G 的鄰接表如下圖所示，其從頂點(diǎn) v1 出發(fā)的深度優(yōu)先搜索序列為 v1 v2 v3 v6 v5 v4 ，其從 頂點(diǎn) v1 出發(fā)的廣度優(yōu)先搜索序列為 v1 v2 v5 v4 v3 v6 。105. 設(shè) x, y 是圖 G 中的兩頂點(diǎn)，貝 U( x, 丫)與(y, x)被認(rèn)為無向，但 x, 丫與y, x是有 向的兩條 弧。6. 已知一個(gè)圖的鄰接矩陣表示，刪除所有從 i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是 將矩陣的第 i行全部置為 0 o7. 在有向圖的鄰接矩陣上，由第 i 行可得到第 i 個(gè)結(jié)點(diǎn)的出度 , 而由第 j 列可得到第 _j_個(gè)結(jié)

18、點(diǎn)的 入度。8. 在無向圖中，如果從頂點(diǎn) v 到頂點(diǎn) v 有路徑，則稱 v 和 v ' 是一連通。1. 處理沖突時(shí)的平均查找長 度為 1 + ?第 8 章查找 ( 已校對無誤 )順序查找法的平均查找長度為 (n+ 1) 12 ; 哈希表查找法采用鏈接法2.在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n 無關(guān)的查找方法是哈希表查找法3.二分查找的存儲(chǔ)結(jié)構(gòu)僅限于 有序的順序存儲(chǔ)結(jié)構(gòu)4.長度為 255 的表，采用分塊查找法，每塊的最佳長度是15 。5.N 個(gè)記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù)是log 2N ? o對于長度為 n 的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為 復(fù)雜度為 0(log 2n) ；若采用分塊查找 (假定總塊數(shù)和每塊長度均接近6.O(n); 若采用二分法查找，則時(shí)間蘇) ，則時(shí)間復(fù)雜度為0(n)。7. 在散列存儲(chǔ)中，裝填因子 a 的值越大，則存取元素時(shí)發(fā)生沖突的可能性就越大 取元素時(shí)發(fā)生沖突的可能性就越?。篴 的值越小，貝8. 對于二叉排序樹的查找，若根結(jié)點(diǎn)元素的鍵值大于被查元素的鍵值，則應(yīng)該在