數(shù)據(jù)結構填空作業(yè)題答案

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

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

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

4、；while(i=n)i= i * 3；第 2 2 章線性表(已校對無誤)1. 一線性表表示如下：(ai，a2，ai-i,a , a+i,，an),其中每個 ai代表一個數(shù)據(jù)元素(或結點)。ai稱為 起始 結點,an稱為 終端 結點,i 稱為 a 在線性表中的 位置(或序號) 。 對任意一對相鄰結點ai, ai+i, (Kin), ai稱為 ai+i的直接 前驅(qū)，a+i稱為 a 的直接 后繼。2. 對一個長度為 n 的線性表，要刪除第 i 個元素，則在順序表示的情況下，計算復雜性為 0(n),在鏈式表示的情況下，計算復雜性為0(i)。3. 在一個長度為 n 的順序表中，向第 i 個元素(K i

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

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

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

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

9、初始化操作外，其他基本操作的初始條件都要求棧存在。12. 僅允許在同一端進行插入和刪除的線性表稱為棧。4/ 713. 在順序棧 s 中，棧為空的條件是 s.top=s.base，棧為滿的條件是 s.top s.base =s.stacksize。14. 設有算術表達式 x+ a* （y b） c/d,該表達式的前綴表示為+ x*a yb/cd。后綴表示為 xayb * + cd/。15.用 S 表示入棧操作，X 表示出棧操作，若元素入棧順序為1234，為了得到 1342 出棧順序， 相應的S、X 操作串為 SXSSXSXX。16. 向一個棧頂指針為 top 的鏈式棧中插入一個新結點*p 時，應

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

11、， 當前 rear 和 front 的值分別為 0 和 994,若要達到隊 滿的條件，還需要繼續(xù)入隊的元素個數(shù)是993 。20. 隊列的插入操作在隊尾 進行，刪除操作在 隊頭 進行。21. 在一個循環(huán)隊列 Q 中，判斷隊空的條件為Q.front=Q.rear ，判斷隊滿的條件為（Q.rear+ 1） % maxSize=Q.fr ont 。22. 向一個循環(huán)隊列中插入元素時，需要首先移動隊尾指針，然后再向所指位置寫入（或插入）新插入的元素。23. 當用長度為 n 的數(shù)組順序存儲一個棧時，若用top=n 表示?？眨瑒t表示棧滿的條件為top=0 。24. 循環(huán)隊列的引入，目的是為了克服假溢出時大量

12、移動數(shù)據(jù)元素。第 4 4 章串（已校對無誤）1. 兩個串相等的充分必要條件是兩個串的長度相等且對應位置的字符相同。2. 空格串是 由一個或多個空格字符組成的串，其長度等于 其包含的空格個數(shù)。3. 模式串a(chǎn)baabade 的 next 函數(shù)值為 01122341補充：1. 串的兩種最基本的存儲方式是順序存儲方式和鏈接存儲方式。2. 空串是 零個字符的串，其長度等干零 。3. 組成串的數(shù)據(jù)元素只能是字符。5/ 74. 串是一種特殊的線性表，其特殊性表現(xiàn)在其數(shù)據(jù)元素都是字符。第 5 5 章數(shù)組（已校對無誤）1. 將下三角矩陣 A1.8, 1.8的下三角部分逐行地存儲到起始地址為1000 的內(nèi)存單元中

13、，已知每個元素占 4 個單元，則元素 A7, 5的地址為1100 。2. 二維數(shù)組 A09,019采用列序為主方式存儲，每個元素占一個存儲單元，并且元素A0 , 0的存儲地址是 200,則元素 A6 , 12的地址是 332。3.二維數(shù)組 A1020, 5-10采用行序為主方式存儲，每個元素占 4 個存儲單元，并且元素 A10 ,5的存儲地址是 1000,則元素 A18，9的地址是 1208。補充：1. 一維數(shù)組的邏輯結構是線性結構，存儲結構是順序存儲結構 。2. 對于二維數(shù)組或多維數(shù)組，分為按以行為主序和按 以列為主序兩種不同的存儲方式存儲。3. 對矩陣壓縮存儲是為了節(jié)省存儲空間 。4. 二

14、維數(shù)組是一種非線性結構，其中的每一個數(shù)組元素最多有二 個直接前驅(qū)（或直接后繼）。第 6 6 章樹（已校對無誤）4. 結點最少的樹為 只有一個結點的樹，結點最少的二叉樹為空的二叉樹。5. 根據(jù)二叉樹的定義，具有三個結點的二叉樹有5 種不同的形態(tài)，它們分別是 _。6. 具有 n 個結點的完全二叉樹的深度為 _。8. 以數(shù)據(jù)集4，5, 6, 7, 10, 12，18為結點權值所構造的哈夫曼樹為需用圖示，其帶權路徑長度為 165 。9. 哈夫曼樹是帶權路徑長度最短 的樹，通常權值較大的結點離根較近。10. 在 先序 遍歷二叉樹的序列中，任何結點的子樹上的所有結點，都是直接跟在該結點之后。第 7 7 章

15、圖（已校對無誤）I.n 個頂點的連通圖至少有 n 1 條邊。2在無權圖 G 的鄰接矩陣 A 中，若（vi, vj）或vi, vj屬于圖 G 的邊集，則對應元素 Aij等于J,否則等于 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。7/ 75. 設 x, y 是圖 G 中的兩頂點，貝U（x,丫）與（y, x）被認為無向，但x,丫與y, x是有 向的兩條弧。6. 已知一

16、個圖的鄰接矩陣表示，刪除所有從 i 個結點出發(fā)的邊的方法是 將矩陣的第 i 行全部置為 0o7. 在有向圖的鄰接矩陣上，由第 i 行可得到第 i 個結點的出度,而由第 j 列可得到第_j_個結點的 入度。8. 在無向圖中，如果從頂點v到頂點 v 有路徑，則稱v和v是 連通。第 8 8 章查找（已校對無誤）1.順序查找法的平均查找長度為 （n+ 1） /2 ;哈希表查找法采用鏈接法處理沖突時的平均查找長度為 1 + ?o2. 在各種查找方法中，平均查找長度與結點個數(shù)n 無關的查找方法是 哈希表查找法 。3. 二分查找的存儲結構僅限于有序的順序存儲結構。4. 長度為 255 的表，采用分塊查找法，

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