2021年《數(shù)據(jù)結(jié)構(gòu)》填空作業(yè)題培訓(xùn)資料

1、資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除數(shù)據(jù)結(jié)構(gòu)填空作業(yè)題答案第 1 章緒論（已校對無誤） |精.|品.|可.|編.|輯.|學(xué).|習(xí).|資.|料. * | * | * | * | |歡.|迎.|下.|載. 1數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的規(guī)律結(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ù)的規(guī)律結(jié)構(gòu)在運算機儲備器內(nèi)的表示，稱為數(shù)據(jù)的儲備結(jié)構(gòu)；5. 數(shù)據(jù)的規(guī)律結(jié)構(gòu)可以分類為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類；6. 在圖狀結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)可以有多個；7.

2、 在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在一對多的關(guān)系；8. 數(shù)據(jù)的物理結(jié)構(gòu)，指數(shù)據(jù)元素在運算機中的標(biāo)識（映象），也即儲備結(jié)構(gòu)；9. 數(shù)據(jù)的規(guī)律結(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)是把規(guī)律上相鄰的結(jié)點儲備在物理上連續(xù)的儲備單元里，結(jié)點之間的規(guī)律關(guān)系由儲備單元位置的鄰接關(guān)系來表達；11. 鏈?zhǔn)絻浣Y(jié)構(gòu)是把規(guī)律上相鄰的結(jié)點儲備在物理上任意的儲備單元里，節(jié)點之間的規(guī)律關(guān)系由附加的指針域來表達；12. 數(shù)據(jù)的儲備結(jié)構(gòu)可用4 種基本的儲備方法表示，它們分別是次序儲備、 鏈?zhǔn)絻洹?索引儲備 和 散列儲備；13. 線性結(jié)構(gòu)反映結(jié)點間的規(guī)律關(guān)系是一

3、對一的，非線性結(jié)構(gòu)反映結(jié)點間的規(guī)律關(guān)系是一對多或多對多；14. 數(shù)據(jù)結(jié)構(gòu)在物理上可分為次序儲備結(jié)構(gòu)和鏈?zhǔn)絻浣Y(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. 對于某一類特定的問題，算法給出明白決問題的一系列操作，每一操作都有它的準(zhǔn)確的定義，并

4、在有窮時間內(nèi)運算出結(jié)果；word 可編輯第 1 頁，共 8 頁資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除21. 下面程序段的時間復(fù)雜度為 3n；i=1 ； whilei<=ni= i 3；第 2 章線性表 （已校對無誤）1. 一線性表表示如下： （a ，a ，a，a ，a，a ），其中每個 a 代表一個數(shù)據(jù)元素（或12i-1ii+1ni |精.|品.|可.|編.|輯.|學(xué).|習(xí).|資.|料. * | * | * | * | |歡.|迎.|下.|載. 結(jié)點）；a1 稱為起始結(jié)點， an 稱為終端結(jié)點， i 稱為 ai 在線性表中的位置（或序號）；對任意一對相鄰結(jié)點ai，ai+1 ，（1i n）

5、，ai 稱為 ai+1 的直接前驅(qū)，ai+1 稱為 ai 的直接后繼；2. 對一個長度為 n 的線性表，要刪除第 i 個元素，就在次序表示的情形下， 運算復(fù)雜性為On，在鏈?zhǔn)奖硎镜那樾蜗?，運算復(fù)雜性為O1；3. 在一個長度為 n 的次序表中， 向第 i 個元素（ 1 in）之前插入一個新元素時， 需向后移動ni 1個元素；4. 次序表中規(guī)律上相鄰的元素在物理位置上肯定相連；5. 在 n 個結(jié)點的次序表中插入一個結(jié)點需平均移動n/2個結(jié)點，詳細的移動次數(shù)取決于表長 n 和插入位置 i；6. 在次序表中拜訪任意一個結(jié)點的時間復(fù)雜度均為O1，因此，次序表也稱為隨機拜訪的數(shù)據(jù)結(jié)構(gòu)；7. 次序表相對于鏈

6、表的優(yōu)點有隨機拜訪和空間利用率高；8. 在長度為 n 的次序表中插入一個元素的時間復(fù)雜度為On；9. 在帶有頭結(jié)點的單鏈表L 中，如要刪除第一個結(jié)點， 就須執(zhí)行以下三條語句：U L->next；L->next=U->next ；free（U）；10. 鏈表相對于次序表的優(yōu)點有插入和刪除操作便利；11. 在單鏈表中除首結(jié)點外，任意結(jié)點的儲備位置都由直接前驅(qū)結(jié)點中的指針指示；12. 在 n 個結(jié)點的單鏈表中要刪除已知結(jié)點*p ，需找到它的直接前驅(qū)結(jié)點的地址，其時間復(fù)雜度為On；13單鏈表中設(shè)置頭結(jié)點的作用是簡化操作，削減邊界條件的判定；14在帶表頭結(jié)點的單鏈表中，當(dāng)刪除某一指定結(jié)

7、點時，必需找到該結(jié)點的前驅(qū)結(jié)點；15. 在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點，另一個指向后續(xù)結(jié)點；16. 帶頭結(jié)點的單鏈表L 為空的判定條件是L -> next=NULL，不帶頭結(jié)點的單鏈表L 為空的判定條件是L=NULL；word 可編輯第 2 頁，共 8 頁資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除17. 在單鏈表中，指針p 所指結(jié)點為最終一個結(jié)點的條件是p-> next=NULL；18. 循環(huán)鏈表的最大優(yōu)點是從表中任意結(jié)點動身都可拜訪到表中每一個元素（或從表中任意結(jié)點動身都可遍歷整個鏈表）； |精.|品.|可.|編.|輯.|學(xué).|習(xí).|資.|料. * | * | *

8、 | * | |歡.|迎.|下.|載. 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. 將兩個各有 n 個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是1；第 3 章棧和隊列 （已校對無誤）1. 棧又稱為后進先出表，隊列又稱為先進先出表；2. 向一個次序棧插入一個元素時，第一使棧頂指針后移一個位置，

9、然后把待插入元素寫入（或插入）到這個位置上；3. 從一個棧刪除元素時，需要前移一位棧頂指針；4. 在一個次序棧中，如棧頂指針等于 1，就為空棧；如棧頂指針等于maxSize1，就為滿棧；5. 在一個鏈?zhǔn)綏Ｖ?，如棧頂指針等于NULL ，就為空棧；在一個鏈?zhǔn)疥犃兄校珀狀^指針與隊尾指針的值相同，就表示該隊列為空或該隊列只含有一個結(jié)點；6. 向一個鏈?zhǔn)綏２迦胍粋€新結(jié)點時，第一把棧頂指針的值賦給新結(jié)點的指針域，然后把新結(jié)點的儲備位置賦給棧頂指針；7在求表達式值的算符優(yōu)先算法中使用的主要數(shù)據(jù)結(jié)構(gòu)是棧；8設(shè)有一個次序棧S，元素 s1， s2，s3， s4，s5， s6 依次進棧，假如6 個元素的出棧次序為

10、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 定義中，除初始化操作外，其他基本操作的初始條件都要求棧存在；12. 僅答應(yīng)在同一端進行插入和刪除的線性表稱為棧；13. 在次序棧 s 中，棧為空的條件是s.top=s.base ，棧為滿的條件是s.top s.base=s.stacksize ；14. 設(shè)有算術(shù)

11、表達式x a*（ yb） c/d，該表達式的前綴表示為 x*a yb/cd ；后綴表示為xayb* cd/；15. 用 S 表示入棧操作， X 表示出棧操作，如元素入棧次序為1234，為了得到 1342 出棧次序，word 可編輯第 3 頁，共 8 頁 |精.|品.|可.|編.|輯.|學(xué).|習(xí).|資.|料. * | * | * | * | |歡.|迎.|下.|載. 資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除相應(yīng)的 S、X 操作串為SXSSXSXX；16. 向一個棧頂指針為top 的鏈?zhǔn)綏Ｖ胁迦胍粋€新結(jié)點*p 時，應(yīng)執(zhí)行p->link top和topp操作；17. 從一個棧頂指針為top 的非

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

13、操作在隊尾進行，刪除操作在隊頭進行；21. 在一個循環(huán)隊列Q 中，判定隊空的條件為Q.front=Q.rear，判定隊滿的條件為Q.rear1maxSize=Q.front；22. 向一個循環(huán)隊列中插入元素時，需要第一移動隊尾指針，然后再向所指位置寫入（或插入）新插入的元素；23. 當(dāng)用長度為n 的數(shù)組次序儲備一個棧時，如用top=n表示?？?，就表示棧滿的條件為top=0；24. 循環(huán)隊列的引入，目的是為了克服假溢出時大量移動數(shù)據(jù)元素；第 4 章串（已校對無誤）1. 兩個串相等的充分必要條件是兩個串的長度相等且對應(yīng)位置的字符相同；2. 空格串是由一個或多個空格字符組成的串，其長度等于其包含的空

14、格個數(shù)；3. 模式串 abaabade的 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采納列序為主方式儲備，每個元素占一個儲備單元，并且元素A0 ，0的word 可編輯第 4 頁，共 8

15、頁資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除儲備地址是 200，就元素 A6 ，12的地址是332；3. 二維數(shù)組 A1 020，510采納行序為主方式儲備，每個元素占4 個儲備單元，并且元素A10 ， 5 的儲備地址是 1000，就元素 A18 ， 9的地址是1208；補充： |精.|品.|可.|編.|輯.|學(xué).|習(xí).|資.|料. * | * | * | * | |歡.|迎.|下.|載. 1. 一維數(shù)組的規(guī)律結(jié)構(gòu)是線性結(jié)構(gòu)，儲備結(jié)構(gòu)是次序儲備結(jié)構(gòu)；2. 對于二維數(shù)組或多維數(shù)組，分為按以行為主序和按以列為主序兩種不同的儲備方式儲備；3. 對矩陣壓縮儲備是為了節(jié)約儲備空間；4. 二維數(shù)組是一種非線性

16、結(jié)構(gòu)，其中的每一個數(shù)組元素最多有二個直接前驅(qū)（或直接后繼） ；第 6 章樹（已校對無誤）4. 結(jié)點最少的樹為只有一個結(jié)點的樹，結(jié)點最少的二叉樹為空的二叉樹；5. 依據(jù)二叉樹的定義，具有三個結(jié)點的二叉樹有5種不同的形狀，它們分別是；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 條

17、邊；2在無權(quán)圖 G 的鄰接矩陣 A 中，如（ vi ， vj ）或vi ， vj 屬于圖 G 的邊集，就對應(yīng)元素Aij 等于1，否就等于0；3. 在無向圖 G 的鄰接矩陣 A 中，如 Aij等于 1，Aj i等于1；4. 已知圖 G 的鄰接表如下圖所示，其從頂點v1 動身的深度優(yōu)先搜尋序列為v1 v2 v3 v6 v5 v4 ，其從頂點 v1 動身的廣度優(yōu)先搜尋序列為v1 v2 v5 v4 v3 v6；V1v2 v3v4v5 word 可編輯v6V2V5V4v3V5V6V4V6V3第 5 頁，共 8 頁資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除5. 設(shè) x， y 是圖 G 中的兩頂點，就（ x，

18、y）與（ y，x）被認為無向 ，但 x ，y與 y， x是 有向 的兩條?。?|精.|品.|可.|編.|輯.|學(xué).|習(xí).|資.|料. * | * | * | * | |歡.|迎.|下.|載. 6. 已知一個圖的鄰接矩陣表示，刪除全部從i 個結(jié)點動身的邊的方法是將矩陣的第 i 行全部置為 0 ；7. 在有向圖的鄰接矩陣上， 由第 i 行可得到第i個結(jié)點的出度， 而由第 j 列可得到第j個結(jié)點的入度；8. 在無向圖中，假如從頂點v 到頂點 v有路徑，就稱 v 和 v是連通；第 8 章查找（已校對無誤）1. 次序查找法的平均查找長度為（n1） /2；哈希表查找法采納鏈接法處理沖突時的平均查找長度為

19、1？；2. 在各種查找方法中，平均查找長度與結(jié)點個數(shù)n 無關(guān)的查找方法是哈希表查找法；3. 二分查找的儲備結(jié)構(gòu)僅限于有序的次序儲備結(jié)構(gòu)；4. 長度為 255 的表，采納分塊查找法，每塊的正確長度是15；5. N 個記錄的有序次序表中進行折半查找，最大的比較次數(shù)是 2N？；6. 對于長度為 n 的線性表，如進行次序查找，就時間復(fù)雜度為 On ；如采納二分法查找，就時間復(fù)雜度為 O 2n ；如采納分塊查找（假定總塊數(shù)和每塊長度均接近 n ），就時間復(fù)雜度為On ；7. 在散列儲備中，裝填因子 a 的值越大，就 存取元素時發(fā)生沖突的可能性就越大；a 的值越小，就 存取元素時發(fā)生沖突的可能性就越??；8. 對于二叉排序樹的查找，如根結(jié)點元素的鍵值大于被查元素的鍵值，就應(yīng)當(dāng)在二叉樹的左子樹上連續(xù)查找；9. 高度為 8 的平穩(wěn)二叉樹至少有54個結(jié)點；word 可編輯第 6 頁，共 8 頁資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除10. 在散列函數(shù) H（ key）=key % p 中， p 應(yīng)取素數(shù)； |精.|品.|可.|編.|輯.|學(xué).|習(xí).|資.|料. *