2022年《數(shù)據(jù)結構》填空作業(yè)題培訓資料

1、資料收集于網(wǎng)絡,如有侵權請聯(lián)系網(wǎng)站刪除數(shù)據(jù)結構填空作業(yè)題答案第 1 章緒論 （已校對無誤）、數(shù)據(jù)的儲備結構和數(shù)據(jù)的運算三方面的內(nèi)容；1數(shù)據(jù)結構包括數(shù)據(jù)的規(guī)律結構2程序包括兩個內(nèi)容：數(shù)據(jù)結構和算法；3. 數(shù)據(jù)結構的形式定義為：數(shù)據(jù)結構是一個二元組：Data Structure =（D,S） ；4. 數(shù)據(jù)的規(guī)律結構在運算機儲備器內(nèi)的表示,稱為數(shù)據(jù)的 儲備結構；5. 數(shù)據(jù)的規(guī)律結構可以分類為 線性 結構和 非線性 結構兩大類；6. 在圖狀結構中,每個結點的前驅結點數(shù)和后繼結點數(shù)可以 有多個；7. 在樹形結構中,數(shù)據(jù)元素之間存在 一對多 的關系；8. 數(shù)據(jù)的物理結構,指數(shù)據(jù)元素在 運算機 中的標識（映

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

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

4、 可編輯資料收集于網(wǎng)絡,如有侵權請聯(lián)系網(wǎng)站刪除21. 下面程序段的時間復雜度為 3n ；i=1；whileinext ；8. 在長度為 n 的次序表中插入一個元素的時間復雜度為On ；9. 在帶有頭結點的單鏈表L 中,如要刪除第一個結點, 就須執(zhí)行以下三條語句：L-next=U-next ；free（U）；10. 鏈表相對于次序表的優(yōu)點有 插入 和 刪除 操作便利；11. 在單鏈表中除首結點外,任意結點的儲備位置都由 直接前驅 結點中的指針指示；12. 在 n 個結點的單鏈表中要刪除已知結點 *p,需找到 它的直接前驅結點的地址,其時間復雜度為 On ；13單鏈表中設置頭結點的作用是 簡化操作

5、,削減邊界條件的判定；14在帶表頭結點的單鏈表中,當刪除某一指定結點時,必需找到該結點的 前驅 結點；15. 在雙鏈表中,每個結點有兩個指針域,一個指向 前驅結點,另一個指向 后續(xù)結點；16. 帶頭結點的單鏈表 L 為空的判定條件是 L-next=NULL ,不帶頭結點的單鏈表 L 為空的判定條件是 L=NULL ；word 可編輯資料收集于網(wǎng)絡,如有侵權請聯(lián)系網(wǎng)站刪除17. 在單鏈表中,指針 p 所指結點為最終一個結點的條件是 p-next=NULL ；18. 循環(huán)鏈表的最大優(yōu)點是 從表中任意結點動身都可拜訪到表中每一個元素（或從表中任意結點動身都可遍歷整個鏈表）；19. 設 rear 是指

6、向非空、帶頭結點的循環(huán)單鏈表的尾指針,就該鏈表首結點的儲備位置是rear-next-next ；20. 帶頭結點的雙向循環(huán)表L 為空表的條件是L- prior= L -next ；頭指針才能遍21. 在循環(huán)鏈表中,可依據(jù)任一結點的地址遍歷整個鏈表,而單鏈表中需知道歷整個鏈表；22. 將兩個各有 n 個元素的有序表歸并成一個有序表,其最少的比較次數(shù)是 1 ；第 3 章 棧和隊列（已校對無誤）1. 棧又稱為 后進先出 表,隊列又稱為 先進先出 表；2. 向一個次序棧插入一個元素時,第一使 棧頂指針 后移一個位置, 然后把待插入元素 寫入（或插入）到這個位置上；3. 從一個棧刪除元素時,需要前移一位

7、 棧頂指針；4. 在一個次序棧中,如棧頂指針等于1 ,就為空棧；如棧頂指針等于 maxSize1 ,就為滿棧；5. 在一個鏈式棧中,如棧頂指針等于 NULL ,就為 空棧；在一個鏈式隊列中,如隊頭指針與隊尾指針的值相同,就表示該隊列為 空 或該隊列 只含有一個結點；6. 向一個鏈式棧插入一個新結點時,第一把棧頂指針的值賦給 新結點的指針域,然后把新結點的儲備位置賦給 棧頂指針；7在求表達式值的算符優(yōu)先算法中使用的主要數(shù)據(jù)結構是 棧；8設有一個次序棧 S,元素 s1,s2,s3,s4,s5,s6依次進棧,假如 6 個元素的出棧次序為 s2,s3,s4,s6,s5,s1,就次序棧的容量至少為 3

8、；9. 設有一個空棧,現(xiàn)輸入序列為 push 后,輸出序列是 2 3 4 ；1,2,3,4,5；經(jīng)過 push,push,pop,push,pop,push,pop,10. 在按算符優(yōu)先法求解表達式 315*2 時,最先執(zhí)行的運算是 * ,最終執(zhí)行的運算是 ；11. 在棧的 ADT 定義中,除初始化操作外,其他基本操作的初始條件都要求 棧存在；12. 僅答應在同一端進行插入和刪除的線性表稱為 棧；13. 在次序棧 s 中,棧為空的條件是 s.top=s.base ,棧為滿的條件是 s.tops.base=s.stacksize ；14. 設有算術表達式 xa*（yb）c/d,該表達式的前綴表示

9、為 x*ayb/cd ；后綴表示為 xayb* cd/；15. 用 S 表示入棧操作, X 表示出棧操作,如元素入棧次序為 word 可編輯1234,為了得到 1342 出棧次序,資料收集于網(wǎng)絡,如有侵權請聯(lián)系網(wǎng)站刪除相應的 S、X 操作串為SXSSXSXX ；*p 時,應執(zhí)行p-link top 和topp 16. 向一個棧頂指針為top 的鏈式棧中插入一個新結點操作；17. 從一個棧頂指針為 top 的非空鏈式棧中刪除結點并不需要返回棧頂結點的值和回收結點時,應執(zhí)行 toptop-link 操作；18. 設有一個空棧,棧頂指針為 1000H（十六進制；現(xiàn)有輸入序列為 1,2,3,4,5,經(jīng)

10、過 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后,輸出序列是 2,3 ,而棧頂指針是 100C H；設棧為次序棧,每個元素占 4 個字節(jié)；19. 在作入棧運算時應先判別棧是否 滿；在作出棧運算時應先判別棧是否 空；10. 用一個大小為 1000 的數(shù)組來實現(xiàn)循環(huán)隊列,當前 滿的條件,仍需要連續(xù)入隊的元素個數(shù)是 993 ；rear 和 front 的值分別為 0 和 994,如要達到隊20. 隊列的插入操作在隊尾進行,刪除操作在隊頭進行；,判定隊滿的條件為Q.rear21. 在一個循環(huán)隊列Q 中,判定隊空的條件為Q.front=Q.rear 1maxSize=Q.fro

11、nt ；22. 向一個循環(huán)隊列中插入元素時,需要第一移動 隊尾指針,然后再向所指位置 寫入（或插入）新插入的元素；23. 當用長度為 n 的數(shù)組次序儲備一個棧時,如用 top=n 表示?？?就表示棧滿的條件為top=0 ；24. 循環(huán)隊列的引入,目的是為了克服 假溢出時大量移動數(shù)據(jù)元素；第 4 章 串（已校對無誤）1. 兩個串相等的充分必要條件是 兩個串的長度相等且對應位置的字符相同；2. 空格串是 由一個或多個空格字符組成的串,其長度等于 其包含的空格個數(shù)；3. 模式串a(chǎn)baabade 的 next 函數(shù)值為 01122341 補充：1. 串的兩種最基本的儲備方式是 次序儲備方式和鏈接儲備方

12、式；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ù)組 A0 9,0 19采納列序為主方式儲備,每個元素占一個儲備單元,并且元素 A0 ,0的word 可編輯資料收集于網(wǎng)絡,如有侵權請聯(lián)系網(wǎng)站刪除儲備地址是 200,就元素 A6 ,12的地址是332 ；4 個儲備單元,并且元素A10 ,3.

13、 二維數(shù)組 A1 0 20,5 10采納行序為主方式儲備,每個元素占5的儲備地址是 1000,就元素 A18 ,9的地址是1208 ；補充：1. 一維數(shù)組的規(guī)律結構是 線性結構,儲備結構是 次序儲備結構；2. 對于二維數(shù)組或多維數(shù)組,分為按 以行為主序 和按 以列為主序 兩種不同的儲備方式儲備；3. 對矩陣壓縮儲備是為了 節(jié)約儲備空間；4. 二維數(shù)組是一種非線性結構,其中的每一個數(shù)組元素最多有 二 個直接前驅（或直接后繼） ；第 6 章 樹（已校對無誤）4. 結點最少的樹為 只有一個結點的樹,結點最少的二叉樹為 空的二叉樹；5. 依據(jù)二叉樹的定義,具有三個結點的二叉樹有 5 種不同的形狀,它們

14、分別是；6. 具有 n 個結點的完全二叉樹的深度為；8. 以數(shù)據(jù)集 4 ,5,6,7,10,12,18為結點權值所構造的哈夫曼樹為 需用圖示,其帶權路徑長度為 165 ；9. 哈夫曼樹是帶權路徑長度 最短 的樹,通常權值較大的結點離根 較近；10. 在 先序 遍歷二叉樹的序列中,任何結點的子樹上的全部結點,都是直接跟在該結點之后；第 7 章 圖（已校對無誤）1n 個頂點的連通圖至少有 n1 條邊；2在無權圖 G 的鄰接矩陣 A 中,如（ vi,vj）或vi,vj屬于圖 G 的邊集,就對應元素 Aij 等于1 ,否就等于 0 ；3. 在無向圖 G 的鄰接矩陣 A 中,如 Aij 等于 1,Aj

15、i 等于 1 ；4. 已知圖 G 的鄰接表如下圖所示,其從頂點 v1 動身的深度優(yōu)先搜尋序列為 v1 v2 v3 v6 v5 v4 ,其從頂點 v1 動身的廣度優(yōu)先搜尋序列為 v1 v2 v5 v4 v3 v6；V1 V2 V5 V4 v2 v3 V5 v3 V6 v4 v5 V4 V6 V3 word 可編輯v6 資料收集于網(wǎng)絡,如有侵權請聯(lián)系網(wǎng)站刪除5. 設 x,y 是圖 G 中的兩頂點,就（ x,y）與（ y,x）被認為 向 的兩條弧；無向 ,但 x,y與 y,x是 有6. 已知一個圖的鄰接矩陣表示,刪除全部從 i 個結點動身的邊的方法是 將矩陣的第 i 行全部置為 0 ；7. 在有向圖

16、的鄰接矩陣上, 由第 i 行可得到第 i 個結點的出度, 而由第 j 列可得到第 j 個結點的入度；8. 在無向圖中,假如從頂點 v 到頂點 v有路徑,就稱 v 和 v 是 連通；第 8 章 查找 （已校對無誤）1. 次序查找法的平均查找長度為（n1）/2 ；哈希表查找法采納鏈接法處理沖突時的平均查找長度為 1？；哈希表查找法；2. 在各種查找方法中,平均查找長度與結點個數(shù)n 無關的查找方法是3. 二分查找的儲備結構僅限于有序的次序儲備結構；4. 長度為 255 的表,采納分塊查找法,每塊的正確長度是15 ；5. N 個記錄的有序次序表中進行折半查找,最大的比較次數(shù)是 2N ？；6. 對于長度

17、為 n 的線性表,如進行次序查找,就時間復雜度為On ；如采納二分法查找,就時間復雜度為 O2n ；如采納分塊查找（假定總塊數(shù)和每塊長度均接近 n ）,就時間復雜度為On ；7. 在散列儲備中,裝填因子 a 的值越大,就 存取元素時發(fā)生沖突的可能性就越大；a的值越小,就 存取元素時發(fā)生沖突的可能性就越??；8. 對于二叉排序樹的查找,如根結點元素的鍵值大于被查元素的鍵值,就應當在二叉樹的 左子樹上連續(xù)查找；9. 高度為 8 的平穩(wěn)二叉樹至少有 54 個結點；word 可編輯資料收集于網(wǎng)絡,如有侵權請聯(lián)系網(wǎng)站刪除10. 在散列函數(shù) H（key）=key % p 中, p 應取 素數(shù)；第 9 章 排序 （已校對無誤） 1. 在對一組記錄（ 54,38,96,23,15,72,60,45,83）進行直接插入排序時,當把第 8 個記錄 45 插入到有序表時,為查找插入位置需比較 5 次；2. 對于關鍵字序列（ 12,13,11,18,60,15,7,20,25,100）,用挑選法建堆,必需從鍵值為 60的關鍵字開頭；3. 對 n 個記錄的表 r 1 n 進行簡潔挑選排序,所需要進行的關鍵字間的比較次數(shù)為 nn1/2 ；4. 在插入排序、希爾排序、挑選排序、快速排序、堆排序、歸并排序和基數(shù)排序中,排序是不穩(wěn)固的有 希爾排序、挑選