《數(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ù)的存儲結(jié)構(gòu) 和 數(shù)據(jù)的運算 三方面的內(nèi)容。2程序包括兩個內(nèi)容： 數(shù)據(jù)結(jié)構(gòu) 和 算法 。3. 數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組： Data Structure =（D，S） 。4. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的 存儲結(jié)構(gòu) 。5. 數(shù)據(jù)的邏輯結(jié)構(gòu)可以分類為 線性 結(jié)構(gòu)和 非線性 結(jié)構(gòu)兩大類。6. 在圖狀結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)可以 有多個 。7. 在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在 一對多 的關(guān)系。8. 數(shù)據(jù)的物理結(jié)構(gòu)，指數(shù)據(jù)元素在 計算機 中的標識（映象），也即 存儲

2、結(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. 順序存儲結(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理上 連續(xù) 的存儲單元里，結(jié)點之間的邏輯關(guān)系由存儲單元位置的鄰接關(guān)系來體現(xiàn)。11. 鏈式存儲結(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理上 任意 的存儲單元里，節(jié)點之間的邏輯關(guān)系由附加的指針域來體現(xiàn)。12. 數(shù)據(jù)的存儲結(jié)構(gòu)可用4種基本的存儲方法表示，它們分別是 順序存儲 、 鏈式存儲 、 索引存儲 和 散列存儲 。13. 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一 的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對多或多對多 。14. 數(shù)據(jù)結(jié)構(gòu)在

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

4、。21. 下面程序段的時間復(fù)雜度為 3n 。i=1；while(i<=n) i= i3；第2章 線性表（已校對無誤）1. 一線性表表示如下：（a1，a2，ai-1，ai，ai+1，an），其中每個ai代表一個 數(shù)據(jù)元素（或結(jié)點） 。a1稱為 起始 結(jié)點，an稱為 終端 結(jié)點，i稱為ai在線性表中的 位置（或序號） 。對任意一對相鄰結(jié)點ai，ai+1，（1in），ai稱為ai+1的直接 前驅(qū) ，ai+1稱為ai的直接 后繼 。2. 對一個長度為n的線性表，要刪除第i個元素，則在順序表示的情況下，計算復(fù)雜性為 O(n) ，在鏈式表示的情況下，計算復(fù)雜性為 O(1) 。3. 在一個長度為n的順

5、序表中，向第i個元素（1in）之前插入一個新元素時，需向后移動 ni1 個元素。4. 順序表中邏輯上相鄰的元素在物理位置上 一定 相連。5. 在n個結(jié)點的順序表中插入一個結(jié)點需平均移動 n/2 個結(jié)點，具體的移動次數(shù)取決于 表長n和插入位置i 。6. 在順序表中訪問任意一個結(jié)點的時間復(fù)雜度均為 O(1) ，因此，順序表也稱為 隨機訪問 的數(shù)據(jù)結(jié)構(gòu)。7. 順序表相對于鏈表的優(yōu)點有 隨機訪問 和 空間利用率高 。8. 在長度為n的順序表中插入一個元素的時間復(fù)雜度為 O(n) 。9. 在帶有頭結(jié)點的單鏈表L中，若要刪除第一個結(jié)點，則須執(zhí)行下列三條語句： UL->next ；L->next

6、=U->next；free（U）。10. 鏈表相對于順序表的優(yōu)點有 插入 和 刪除 操作方便。11. 在單鏈表中除首結(jié)點外，任意結(jié)點的存儲位置都由 直接前驅(qū) 結(jié)點中的指針指示。12. 在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到 它的直接前驅(qū)結(jié)點的地址 ，其時間復(fù)雜度為 O(n) 。13單鏈表中設(shè)置頭結(jié)點的作用是 簡化操作，減少邊界條件的判斷 。14在帶表頭結(jié)點的單鏈表中，當刪除某一指定結(jié)點時，必須找到該結(jié)點的 前驅(qū) 結(jié)點。15. 在雙鏈表中，每個結(jié)點有兩個指針域，一個指向 前驅(qū)結(jié)點 ，另一個指向 后續(xù)結(jié)點 。16. 帶頭結(jié)點的單鏈表L為空的判定條件是 L->next=NULL

7、，不帶頭結(jié)點的單鏈表L為空的判定條件是 L=NULL 。17. 在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是 p->next=NULL 。18. 循環(huán)鏈表的最大優(yōu)點是 從表中任意結(jié)點出發(fā)都可訪問到表中每一個元素（或從表中任意結(jié)點出發(fā)都可遍歷整個鏈表） 。19. 設(shè)rear是指向非空、帶頭結(jié)點的循環(huán)單鏈表的尾指針，則該鏈表首結(jié)點的存儲位置是 rear->next->next 。20. 帶頭結(jié)點的雙向循環(huán)表L為空表的條件是 L->prior= L->next 。21. 在循環(huán)鏈表中，可根據(jù)任一結(jié)點的地址遍歷整個鏈表，而單鏈表中需知道 頭指針 才能遍歷整個鏈表。22

8、. 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是 1 。第3章 棧和隊列（已校對無誤）1. 棧又稱為 后進先出 表，隊列又稱為 先進先出 表。2. 向一個順序棧插入一個元素時，首先使 棧頂指針 后移一個位置，然后把待插入元素 寫入（或插入） 到這個位置上。3. 從一個棧刪除元素時，需要前移一位 棧頂指針 。4. 在一個順序棧中，若棧頂指針等于 1 ，則為空棧；若棧頂指針等于 maxSize1 ，則為滿棧。5. 在一個鏈式棧中，若棧頂指針等于NULL，則為 空棧 ；在一個鏈式隊列中，若隊頭指針與隊尾指針的值相同，則表示該隊列為 空 或該隊列 只含有一個結(jié)點 。6. 向一個鏈式棧

9、插入一個新結(jié)點時，首先把棧頂指針的值賦給 新結(jié)點的指針域 ，然后把新結(jié)點的存儲位置賦給 棧頂指針 。7在求表達式值的算符優(yōu)先算法中使用的主要數(shù)據(jù)結(jié)構(gòu)是 棧 。8設(shè)有一個順序棧S，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的出棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為 3 。9. 設(shè)有一個空棧，現(xiàn)輸入序列為1，2，3，4，5。經(jīng)過push，push，pop，push，pop，push，pop，push后，輸出序列是 2 3 4 。10. 在按算符優(yōu)先法求解表達式315*2時，最先執(zhí)行的運算是 * ，最后執(zhí)行的運算是 。11. 在棧的ADT定義中，除初始化操

10、作外，其他基本操作的初始條件都要求 棧存在 。12. 僅允許在同一端進行插入和刪除的線性表稱為 棧 。13. 在順序棧s中，棧為空的條件是 s.top=s.base ，棧為滿的條件是 s.tops.base=s.stacksize 。14. 設(shè)有算術(shù)表達式xa*（yb）c/d，該表達式的前綴表示為 x*ayb/cd 。后綴表示為 xayb*cd/ 。15. 用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234，為了得到1342出棧順序，相應(yīng)的S、X操作串為 SXSSXSXX 。16. 向一個棧頂指針為top的鏈式棧中插入一個新結(jié)點*p時，應(yīng)執(zhí)行 p->linktop 和 topp

11、操作。17. 從一個棧頂指針為top的非空鏈式棧中刪除結(jié)點并不需要返回棧頂結(jié)點的值和回收結(jié)點時，應(yīng)執(zhí)行 toptop->link 操作。18. 設(shè)有一個空棧，棧頂指針為1000H（十六進制?，F(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，輸出序列是 2，3 ，而棧頂指針是 100C H。設(shè)棧為順序棧，每個元素占4個字節(jié)。19. 在作入棧運算時應(yīng)先判別棧是否 滿 ；在作出棧運算時應(yīng)先判別棧是否 空 。10. 用一個大小為1000的數(shù)組來實現(xiàn)循環(huán)隊列，當前rear和front的值分別為0和994，若要達到隊滿的條件，還需要繼續(xù)入隊的

12、元素個數(shù)是 993 。20. 隊列的插入操作在 隊尾 進行，刪除操作在 隊頭 進行。21. 在一個循環(huán)隊列Q中，判斷隊空的條件為 Q.front=Q.rear ，判斷隊滿的條件為 (Q.rear1)maxSize=Q.front 。22. 向一個循環(huán)隊列中插入元素時，需要首先移動 隊尾指針 ，然后再向所指位置 寫入（或插入） 新插入的元素。23. 當用長度為n的數(shù)組順序存儲一個棧時，若用top=n表示?？?，則表示棧滿的條件為 top=0 。24. 循環(huán)隊列的引入，目的是為了克服 假溢出時大量移動數(shù)據(jù)元素 。第4章 串（已校對無誤）1. 兩個串相等的充分必要條件是 兩個串的長度相等且對應(yīng)位置的字

13、符相同 。2. 空格串是 由一個或多個空格字符組成的串 ，其長度等于 其包含的空格個數(shù) 。3. 模式串a(chǎn)baabade的next函數(shù)值為 01122341 補充：1. 串的兩種最基本的存儲方式是 順序存儲方式和鏈接存儲方式 。2. 空串是 零個字符的串 ，其長度等于 零 。3. 組成串的數(shù)據(jù)元素只能是 字符 。4. 串是一種特殊的線性表，其特殊性表現(xiàn)在 其數(shù)據(jù)元素都是字符 。第5章 數(shù)組（已校對無誤）1. 將下三角矩陣A1.8，1.8的下三角部分逐行地存儲到起始地址為1000的內(nèi)存單元中，已知每個元素占4個單元，則元素A7，5的地址為 1100 。2. 二維數(shù)組A09，019采用列序為主方式存

14、儲，每個元素占一個存儲單元，并且元素A0，0的存儲地址是200，則元素A6，12的地址是 332 。3. 二維數(shù)組A1020，510采用行序為主方式存儲，每個元素占4個存儲單元，并且元素A10，5的存儲地址是1000，則元素A18，9的地址是 1208 。補充：1. 一維數(shù)組的邏輯結(jié)構(gòu)是 線性結(jié)構(gòu) ，存儲結(jié)構(gòu)是 順序存儲結(jié)構(gòu) 。2. 對于二維數(shù)組或多維數(shù)組，分為按 以行為主序 和按 以列為主序 兩種不同的存儲方式存儲。3. 對矩陣壓縮存儲是為了 節(jié)省存儲空間 。4. 二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個數(shù)組元素最多有 二 個直接前驅(qū)（或直接后繼）。第6章 樹（已校對無誤）4. 結(jié)點最少的樹為

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

16、素Aij等于 1 ，否則等于 0 。3. 在無向圖G的鄰接矩陣A中，若Aij等于1，Aj i等于 1 。4. 已知圖G的鄰接表如下圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為v1 v2 v3 v6 v5 v4，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為v1 v2 v5 v4 v3 v6。V1v2v3v4 v5v6 V2V5V4 v3V5 V4V6V3 V6 5. 設(shè)x，y是圖G中的兩頂點，則（x，y）與（y，x）被認為 無向 ，但x，y與y，x是 有向 的兩條弧。6. 已知一個圖的鄰接矩陣表示，刪除所有從i個結(jié)點出發(fā)的邊的方法是 將矩陣的第i行全部置為0 。7. 在有向圖的鄰接矩陣上，由第i行可得到

17、第 i 個結(jié)點的出度，而由第j列可得到第 j 個結(jié)點的入度。8. 在無向圖中，如果從頂點v到頂點v有路徑，則稱v和v 是 連通 。第8章 查找（已校對無誤）1. 順序查找法的平均查找長度為 （n1）/2 ；哈希表查找法采用鏈接法處理沖突時的平均查找長度為 1？ 。2. 在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 哈希表查找法 。3. 二分查找的存儲結(jié)構(gòu)僅限于 有序的順序存儲結(jié)構(gòu) 。4. 長度為255的表，采用分塊查找法，每塊的最佳長度是 15 。5. N個記錄的有序順序表中進行折半查找，最大的比較次數(shù)是 2N ？ 。6. 對于長度為n的線性表，若進行順序查找，則時間復(fù)雜度為 O

18、(n) ；若采用二分法查找，則時間復(fù)雜度為 O(2n) ；若采用分塊查找（假定總塊數(shù)和每塊長度均接近），則時間復(fù)雜度為 O(n) 。7. 在散列存儲中，裝填因子a的值越大，則 存取元素時發(fā)生沖突的可能性就越大 ；a的值越小，則 存取元素時發(fā)生沖突的可能性就越小 。8. 對于二叉排序樹的查找，若根結(jié)點元素的鍵值大于被查元素的鍵值，則應(yīng)該在二叉樹的 左子樹 上繼續(xù)查找。9. 高度為8的平衡二叉樹至少有 54 個結(jié)點。10. 在散列函數(shù)H（key）=key % p中，p應(yīng)取 素數(shù) 。第9章 排序（已校對無誤）1. 在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第8個記錄45插入到有序表時，為尋找插入位置需比較 5 次。2. 對于關(guān)鍵字序列（12，13，11，18，60，15，7，20，25，100），用篩選法建堆，必須從鍵值為 60的關(guān)鍵字開始。3. 對n個記錄的表r1n進行簡單選擇排序，所需要進行的關(guān)鍵字間的比較次數(shù)為 n(n1)/2 。4. 在插入排序、希爾排序、選擇排序