數(shù)據(jù)結(jié)構(gòu)期末考試題及答案

1、精品文檔2012年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案一、選擇題1 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C 。A 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C .線性結(jié)構(gòu)和非線性結(jié)構(gòu)D .內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2 數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指A A .數(shù)據(jù)的存儲結(jié)構(gòu)B .數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)D .數(shù)據(jù)元素之間的關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A 結(jié)構(gòu)。A .邏輯B .存儲C.邏輯和存儲D .物理4 .在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲C A .數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲方法5. 在決定選取何種存儲結(jié)構(gòu)時，一般不考

2、慮A A .各結(jié)點的值如何B .結(jié)點個數(shù)的多少C.對數(shù)據(jù)有哪些運算D .所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。6. 以下說法正確的是 D A. 數(shù)據(jù)項是數(shù)據(jù)的基本單位B. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位C. 數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D .一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7. 算法分析的目的是C，算法分析的兩個主要方面是A(1) A .找出數(shù)據(jù)結(jié)構(gòu)的合理性C.分析算法的效率以求改進(2) A.空間復(fù)雜度和時間復(fù)雜度C.可讀性和文檔性B .研究算法中的輸入和輸出的關(guān)系C.分析算法的易讀性和文檔性B .正確性和簡明性D .數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8.下面程序段的時間復(fù)雜度是s = 0；O (

3、n2)for ( I = 0； i v n； i + + )for (j = 0; j vn； j + + )s += Bij；sum = s ；9 下面程序段的時間復(fù)雜度是 O (n*m)。for ( i = 0； i v n； i + + )for (j = 0； j vm； j + + )Aij二 0；10. 下面程序段的時間復(fù)雜度是0 (Iog3n)。i = 0；while (i v = n)i = i * 3 ；11. 在以下的敘述中，正確的是B 。A .線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C. 棧的操作方式是先進先出D. 隊列的操作方式是先進

4、后出12. 通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B。A .數(shù)據(jù)元素具有同一特點B 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項的類型 要一致C. 每個數(shù)據(jù)元素都一樣D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等13鏈表不具備的特點是A 。A 可隨機訪問任一結(jié)點B.插入刪除不需要移動元素C .不必事先估計存儲空間D .所需空間與其長度成正比17. 需要分配較大空間，插入和刪除不需要移動元素的線性表， 其存儲結(jié)構(gòu) 是 B 。A 單鏈表B 靜態(tài)鏈表C 線性鏈表D 順序存儲結(jié)構(gòu)18. 非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足 C 。A. p next 一 NUL

5、LB . p NULLC. pnext = headD. p = head19. 在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是 D 。A. p priorpriorB. ppriorpriorC. s prior next = sD. spriorprior = s20. 如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用 D存儲方式最 節(jié)省時間。A .單鏈表B .雙鏈表 C.單循環(huán)鏈表D .順序表21. 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復(fù)雜度是B。A. O (1)B. O (n)C . O (n2) D . O (nlog2n)22 .在一個長度為n (

6、n1)的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行B操作與鏈表的長度有關(guān)。A. 刪除單鏈表中的第一個元素B. 刪除單鏈表中的最后一個元素C. 在單鏈表第一個元素前插入一個新元素D .在單鏈表最后一個元素后插入一個新元素23. 與單鏈表相比，雙鏈表的優(yōu)點之一是D 。A .插入、刪除操作更簡單B. 可以進行隨機訪問C .可以省略表頭指針或表尾指針D.順序訪問相鄰結(jié)點更靈活24. 如果對線性表的操作只有兩種， 即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用B 。A .只有表頭指針沒有表尾指針的循環(huán)單鏈表B. 只有表尾指針沒有表頭指針的循環(huán)單鏈表C. 非循環(huán)雙鏈表D. 循環(huán)雙鏈表25. 在長度為

7、n的順序表的第i個位置上插入一個元素(K i丟1),元素的移動次數(shù)為：A 。A. n -i + 1B. n -C. iD. i -126. 對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為C 。A .順序表B.用頭指針表示的循環(huán)單鏈表C. 用尾指針表示的循環(huán)單鏈表D .單鏈表27. 下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？ C 。A插入運算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大D刪除運算方便28. 下面關(guān)于線性表的敘述中，錯誤的是哪一個 ？ B 。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?，不必占用一?/p>

8、連續(xù)的存儲單元D線性表采用鏈?zhǔn)酱鎯?，便于進行插入和刪除操作。29. 線性表是具有n個 B 的有限序列。A .字符B .數(shù)據(jù)元素C.數(shù)據(jù)項D.表元素30. 在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復(fù)雜度是O (1)的操 作是 A 。A 訪問第i (1v= i = n)個結(jié)點和求第i個結(jié)點的直接前驅(qū)(1vi = n)B. 在第i (1= i = n)個結(jié)點后插入一個新結(jié)點C. 刪除第i (1 = i n ext= pn ext= pn ext= s；C. p n ext= snext= s next; p next= s36. 線性表的順序存儲結(jié)構(gòu)是一種A oA .隨機存取的存儲結(jié)構(gòu)B.順序存取

9、的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)D. Hash存取的存儲結(jié)構(gòu)37棧的特點是B，隊列的特點是 A 。A .先進先出B.先進后出38. 棧和隊列的共同點是C 。A .都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D .沒有共同點39. 一個棧的進棧序列是a, b, c, d, e,則棧的不可能的輸出序列是CA. edcbaB . decbaC. dceabD. abcde40.設(shè)有一個棧,元素依次進棧的順序為A、B、C、D、E。下列C 是不可能的出棧序列。A. A , B, C, D, EB. B, C, D, E, AC. E, A , B, C, DD. E,D, C, B, A

10、41 .以下B不是隊列的基本運算？A. 從隊尾插入一個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D .讀取隊頭元素的值42. 若已知一個棧的進棧序列是1,2, 3, n,其輸出序列為p1, p2, p3, pn,若 p1 = n,則 pi 為 C 。A. i B. n i C. n i + 1D.不確定43. 判定一個順序棧st （最多元素為MaxSize）為空的條件是B 。A. st top !top = 1C. st top !top = MaxSize44. 判定一個順序棧st （最多元素為MaxSize）為滿的條件是D 。A. st top !top = 1C. st t

11、op !top = MaxSize45. 個隊列的入隊序列是1, 2, 3, 4,則隊列的輸出序列是 B 。A. 4, 3, 2, 1B. 1, 2, 3, 4C. 1, 4, 3, 2D. 3, 2, 4, 146. 判定一個循環(huán)隊列qu （最多元素為MaxSize）為空的條件是 C 。A. qu rear -qurear -qu front 1 = = MaxSizeC. qufront 147. 在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是C 。A . front = = rear + 1 B . rear= front + 1 C .

12、front = = rearD. front = = 048. 向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針 s所指的結(jié)點時，應(yīng) 執(zhí)行D操作。A. hnext= h ；C. s n ext= hnext= s ;49. 輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為B 。A. push, pop, push, pop, push, pop B. push, push, push, pop, pop, popC. push, push, pop, pop, push, pop D. push, pop, push, push, pop, pop50 .若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間

13、 V1 m , top1、top2 分別代表第1和第2個棧的棧頂，棧1的底在V1，棧2的底在Vm，則棧滿 的條件是 B 。A . |top2 top1| = 0 B . top1 + 1= top2 C . top1 + top2 = m D . top1 = top251 .設(shè)計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用 D 數(shù)據(jù)結(jié)構(gòu)最佳。B 隊列C 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D 。B.取出最近進隊的元素D 刪除隊頭元素B.無法判斷隊列是否為滿A 線性表的順序存儲結(jié)構(gòu)D棧52 允許對隊列進行的操作有A 對隊列中的元素排序C 在隊頭元素之前插入元素53. 對于循環(huán)隊列DA 無法判斷隊列是否為

14、空C.隊列不可能滿D.以上說法都不對54. 若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當(dāng)前 rear和front的值分 別為0和3,當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分 別為 B 。A. 1 和 5 B . 2 和 4 C. 4 和 2D . 5 和 155. 隊列的 先進先出”特性是指D 。A .最早插入隊列中的元素總是最后被刪除B. 當(dāng)同時進行插入、刪除操作時，總是插入操作優(yōu)先C. 每當(dāng)有刪除操作時，總是要先做一次插入操作D. 每次從隊列中刪除的總是最早插入的元素56. 和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是A 。A .通常不會出現(xiàn)棧滿的情況B.通常不會出現(xiàn)

15、?？盏那闆rC.插入操作更容易實現(xiàn)D .刪除操作更容易實現(xiàn)57. 用不帶頭結(jié)點的單鏈表存儲隊列，隊尾結(jié)點，則在進行出隊操作時CA .僅修改隊頭指針C.隊頭、隊尾指針都可能要修改58. 若串S= software其子串的數(shù)目是其頭指針指向隊頭結(jié)點，尾指針指向B. 僅修改隊尾指針D .隊頭、隊尾指針都要修改B 。A. 8 B. 37 C. 36D. 959. 串的長度是指BA .串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C串中所含不同字符的個數(shù)D 串中所含非空格字符的個數(shù)60. 串是一種特殊的線性表，其特殊性體現(xiàn)在B 。A 可以順序存儲B.數(shù)據(jù)元素是一個字符C. 可以鏈?zhǔn)酱鎯 數(shù)據(jù)元素可以是多個

16、字符61. 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為B 。A .連接 B.模式匹配C.求子串 D .求串長62. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j 從1到10，從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A85 的起始地址為 C 。A. SA + 141 B. SA + 144 C. SA+ 222 D . SA+ 22563. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j 從1到10，從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A58 的起始地址為 C 。A. SA + 141 B. SA + 180 C.

17、SA+ 222 D . SA+ 22564. 若聲明一個浮點數(shù)數(shù)組如下：froat average= new float30;假設(shè)該數(shù)組的內(nèi)存起始位置為 200， average15的內(nèi)存地址是C 。A. 214B. 215C. 260D. 25665. 設(shè)二維數(shù)組A1m , 1n按行存儲在數(shù)組B中，則二維數(shù)組元素Ai， j在一維數(shù)組B中的下標(biāo)為 A 。A. n* (i-1)+ j B. n* (i-1)+ j 1 C. i* (j 1) D. j*m + i -166. 有一個10090的稀疏矩陣，非0元素有10,設(shè)每個整型數(shù)占2個字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是B 。A. 20

18、 B.66C. 18 000 D. 3367. 數(shù)組A04, 1 -3，5 7中含有的元素個數(shù)是A 。A. 55 B.45C. 36D. 1668 .對矩陣進行壓縮存儲是為了D 。A.方便運算 B .方便存儲C.提高運算速度 D .減少存儲空間69 .設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，al, 1為第一個元素，其存儲地址為1,每個元素占1個地址空間，則a8, 5的 地址為 B 。A. 13 B.33 C. 18 D. 4070稀疏矩陣一般的壓縮存儲方式有兩種，即CA .二維數(shù)組和三維數(shù)組B.C .三元組和十字鏈表D.71. 樹最適合用來表示C 。A .有序數(shù)據(jù)元素C.

19、元素之間具有分支層次關(guān)系的數(shù)據(jù)72. 深度為5的二叉樹至多有C三元組和散列散列和十字鏈表B. 無序數(shù)據(jù)元素D .元素之間無聯(lián)系的數(shù)據(jù)個結(jié)點。A. 16 B. 32C.31 C.1073. 對一個滿二叉樹，m個葉子，n個結(jié)點，深度為h,則 D 。A. n = h+ m B h+ m = 2n C m = h 1D n = 2h 174. 任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對次序A 。A .不發(fā)生改變 B .發(fā)生改變C.不能確定D .以上都不75. 在線索化樹中，每個結(jié)點必須設(shè)置一個標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若 0標(biāo)識樹結(jié)構(gòu)信息，1標(biāo)識線索，對

20、應(yīng)葉結(jié) 點的左右鏈域，應(yīng)標(biāo)識為_ D _。A. 00B. 01C. 10D. 1176. 在下述論述中，正確的是D只有一個結(jié)點的二叉樹的度為0;二叉樹的度為2;二叉樹的左右子樹可任意交換；深度為K的順序二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A .B .C. D .77. 設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹的結(jié)點個數(shù)為n，森林F中第一棵樹的結(jié)點的個數(shù)是A。B. m n 1D .不能確定78. 若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0 的結(jié)點的個數(shù)是B。A. 9 B. 11 C. 15D .不能確定79. 具有10個葉子結(jié)點的二叉樹中有B

21、個度為2的結(jié)點。A. 8 B. 9 C. 10 D. 1180. 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的C 倍。A. 1/2 B 1 C 2 D 481 .在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B倍。A . 1/2 B 1 C 2 D 482 .某二叉樹結(jié)點的中序序列為 ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點數(shù)目為：CA . 3B . 2C . 4D . 583 .已知一算術(shù)表達式的中綴形式為 A + B *C -D/E，后綴形式為ABC * +DE/ -其前綴形式為D 。A. + B*C/DEB . + B*CD/E C 十 *ABC/DED

22、 .- + A*BC/DE84 .已知一個圖，如圖所示，若從頂點a出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為 D_;按廣度搜索法進行遍歷，則可能得到的一種頂點序列為A ; A .a，b，e，c，d，fB .a,c，f，e，b，dC . a, e, b， c，f， d， D . a，e, d，f，c，b A .a，b，c，e，d，fB .a,b，c，e，f，dC .a, e,b, c, f, d,D . a, c, f, d, e, b85 .采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的 _A_A.先序遍歷B.中序遍歷C.后序遍歷D .按層遍歷86 .采用鄰接表存儲的圖的廣度優(yōu)先

23、遍歷算法類似于二叉樹的 D_A.先序遍歷B.中序遍歷C .后序遍歷D .按層遍歷87. 具有n個結(jié)點的連通圖至少有A 條邊。A. n 1 B. n C. n (n 1) 12 D. 2n88. 廣義表(a), a)的表頭是 C ，表尾是 C 。A.aB()C(a)D(a)89. 廣義表(a)的表頭是 C ，表尾是 B 。A.aB()C(a)D(a)90. 順序查找法適合于存儲結(jié)構(gòu)為B的線性表。A散列存儲B順序存儲或鏈?zhǔn)酱鎯壓縮存儲D索引存儲91 .對線性表進行折半查找時，要求線性表必須B 。A以順序方式存儲B以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯以鏈?zhǔn)椒绞酱鎯?，且結(jié)點按關(guān)鍵

24、字有序排列92. 采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為D 。A O (n2)B O (nIog2n)C O ( n)D O (Iog2n)93. 有一個有序表為1，3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當(dāng)折半查找值為82的結(jié)點時，C次比較后查找成功。A.11B 5C 4D 894. 二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子 的值、小于其右孩子的值。這種說法B 。A 正確B 錯誤95. 下面關(guān)于B樹和B +樹的敘述中，不正確的結(jié)論是A 。A B樹和B +樹都能有效的支持順序查找B B樹和B +樹

25、都能有效的支持隨機查找C B樹和B +樹都是平衡的多叉樹D B樹和B +樹都可用于文件索引結(jié)構(gòu)96. 以下說法錯誤的是B。A 散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址B. 散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。C. 負(fù)載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。D 散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。97. 查找效率最高的二叉排序樹是C 。A 所有結(jié)點的左子樹都為空的二叉排序樹。B. 所有結(jié)點的右子樹都為空的二叉排序樹。C. 平衡二叉樹。D. 沒有左子樹的二叉排序樹。98. 排序方法中，從未排序序列中依次取出元素與已排序序列中的

26、元素進行比較，將其放入已排序序列的正確位置上的方法，稱為C 。A .希爾排序B。冒泡排序C插入排序D。選擇排序99. 在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的 是 D oA .希爾排序B .冒泡排序C.直接插入排序D .直接選擇排序100. 堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D 是一個堆。A. 94， 31， 53， 23， 16， 72B. 94， 53， 31， 72， 16， 23C. 16， 53， 23， 94， 31， 72D. 16， 31， 23， 94， 53， 72101 .堆排序是一種B 排序。A .插入B.選擇C.交換D.歸并102. D 在鏈

27、表中進行操作比在順序表中進行操作效率高。A .順序查找B.折半查找C.分塊查找D.插入103. 直接選擇排序的時間復(fù)雜度為D o (n為元素個數(shù))A. O (n)B. O (Iog2n)C. O (nlog2n)D. O (n2)二、填空題。1.數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類 型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱 非線性結(jié)構(gòu)。2 數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合 、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu) 4種。3 在線性結(jié)構(gòu)中，第一個結(jié)點 沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點，其余每個結(jié)點有且只有 1個后 續(xù)結(jié)點。4. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)

28、構(gòu)中元素之間存在一對 多關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對多 關(guān)系。5. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個 前驅(qū)結(jié)點；葉子結(jié)點沒有 后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以 任意多 個。6 數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序、鏈?zhǔn)?、索引和散列?儲。7. 衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復(fù)雜度與 空間復(fù)雜度。8. 評估一個算法的優(yōu)劣，通常從 時間復(fù)雜度 和 空間復(fù)雜度兩個 方面考察。9. 算法的5個重要特性是有窮性、確定性、可行性、輸入和輸 出。10. 在一個長度為n的順序表中刪除第i個元素時，需向前移動n i -1個11. 在單鏈表中，要刪除某一指

29、定的結(jié)點，必須找到該結(jié)點的 前驅(qū) 結(jié)點。12. 在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū) 結(jié)點，另一個指 向后繼結(jié)點。13. 在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動n個數(shù)據(jù)元素， 移動數(shù)據(jù)元素的個數(shù)與 位置 有關(guān)。14. 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用順序 存儲結(jié)構(gòu)。15. 根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表 分成單鏈表 和雙鏈表16順序存儲結(jié)構(gòu)是通過 下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過 指針 表示元素之間的關(guān)系的。17. 帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是L n

30、extn ext= L。18. 棧 是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循后進先出的原則。19. 空串是 零個字符的串，其長度等于 零。空白串是由一個或多個空格 字符組成的串，其長度等于其包含的空格個數(shù)。20. 組成串的數(shù)據(jù)元素只能是 單個字符。21. 個字符串中 任意個連續(xù)字符構(gòu)成的部分 稱為該串的子串。22. 子串” str在主串” datastructure中的位置是 5。23. 二維數(shù)組M的每個元素是6個字符組成的串，行下標(biāo)i的范圍從0到8, 列下標(biāo)j的范圍從1到10,則存放M至少需要540個字節(jié)；M的第8列和第5 行共占108個字節(jié)。24. 稀疏矩陣一般的壓縮存儲方法有

31、兩種，即三元組表和十字鏈表。25. 廣義表(a), (b )，c)，( d)的長度是 3 ，深度是 4 。26. 在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0,度為2的結(jié)點的個數(shù)為n2，則有 n0= n2+ 1。27. 在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為 n+ 1。28. 棵有n個葉子結(jié)點的哈夫曼樹共有 2n1 個結(jié)點。29. 深度為5的二叉樹至多有31個結(jié)點。30. 若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉 樹的總結(jié)點個數(shù)為69。31. 某二叉樹的前序遍歷序列是 abdgcefh，中序序列是dgbaechf，其后序 序列為 gdbehfca 。32. 線索二叉樹的左線

32、索指向其遍歷序列中的前驅(qū)，右線索指向其遍歷序列中的后繼。33. 在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是散列查找法34. 在分塊索引查找方法中，首先查找索引表，然后查找相應(yīng)的塊表 。35. 個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列， 構(gòu)造樹的過程即為對無序序列進行排序的過程。36. 具有10個頂點的無向圖，邊的總數(shù)最多為 _45_。37. 已知圖G的鄰接表如圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為 _v1v2v3v6v5v4_，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為 _v1v2v5v4v3v6_。38. 索引是為了加快檢索速度而引進的一種數(shù)據(jù)結(jié)構(gòu)。 一個索引隸

33、屬于某個 數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為 關(guān)鍵字 和 關(guān)鍵字對應(yīng)記 錄的地址。39. Prim算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n1 ，當(dāng)前選擇的邊的 權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項原則。40.在一棵m階B樹中，除根結(jié)點外，每個結(jié)點最多有m 棵子樹，最少有m/2 棵子樹。三、判斷題。1.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各 結(jié)點的值如何。（V2 .抽象數(shù)據(jù)類型（ADT ）包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。（V ）3.抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。（V ）4 .順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。（x ）5. 線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù) 的。（X）6. 對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（X ）7. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。（X ）8. 集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（X ）9. 線性表中每個元素都有一個直接前驅(qū)和一個直接后繼。（x ）10. 線性表就是順序存儲的表。（X ）11. 取線