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

1、下載可編輯.專業(yè).整理.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ù)的基本單位下載可編輯.專業(yè).整理.B. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位C. 數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合下載可編輯.專業(yè).整理.D 一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7.算法分析的目的是C ，算法分析的兩個主要方面是A(1) A .找出數(shù)據(jù)結(jié)構(gòu)的合理性 系C.分析算法的效率以求改進(2) A.空間復雜度和時間復雜度 C.可讀性和文檔性8. 下面程序段的時間復雜度是s = 0 ；for(I=0；ivn；i+ + )for(j=0;jvn；

3、j+ + )s += Bij；sum = s ;9. 下面程序段的時間復雜度是for(i=0；ivn；i+ + )for(j=0；jvm；j+ + )Aij二 0 ；10.下面程序段的時間復雜度是i = 0 ；while(iv =n)下載可編輯.專業(yè).整理.i = i * 3 ；11.在以下的敘述中，正確的是B. 研究算法中的輸入和輸出的關(guān)C. 分析算法的易讀性和文檔性B.正確性和簡明性D .數(shù)據(jù)復雜性和程序復雜性O(shè) (n2)。O (n*m )O (Iog3n )下載可編輯.專業(yè).整理.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)是 BoA.單鏈表 B.靜態(tài)鏈表 C.線性鏈表D.順序存儲結(jié)構(gòu)18. 非空的循環(huán)單鏈表 head 的尾結(jié)點（由 p所指向）滿足 C 。A.

5、p next = NULLC. p next = = head下載可編輯.專業(yè).整理.B. p NULLD.p = head19.在循環(huán)雙鏈表的 p 所指的結(jié)點之前插入 s 所指結(jié)點的操作是DoA.p prior priorB.p prior priorC. s prior n ext = sD.s20. 如果最常用的操作是取第 i 個結(jié)點及其前驅(qū)， 則采用 D 存儲方式最 節(jié)省時間。A.單鏈表B.雙鏈表 C.單循環(huán)鏈表 D.順序表21. 在一個具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是BoA.O (1) B. O (n)C. O (n2) D. O (nlog2

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

7、C. 非循環(huán)雙鏈表D. 循環(huán)雙鏈表25.在長度為n 的順序表的第 i 個位置上插入一個元素（1 n ext = p n ext = p n ext = s；C. p n ext = snext = s next ； p next = s36. 線性表的順序存儲結(jié)構(gòu)是一種A.隨機存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)37.棧的特點是B ,隊列的特點是 AoA.先進先出B.先進后出38.棧和隊列的共同點是CoAoB.順序存取的存儲結(jié)構(gòu)D. Hash 存取的存儲結(jié)構(gòu)下載可編輯.專業(yè).整理.A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素39.一個棧的進棧序列是 a, b , c, d

8、, e ,貝 U 棧的不可能的輸出序列是C 。A.edcbaB. decba C. dceab40 .設(shè)有一個棧，元素依次進棧的順序為A、B、C、D、E。下列 C是不可能的出棧序列。A . A， B， C， D， E B. B， C， D， E， A C . E， A， B， C， DD.E， D， C， B， A41.以下 B 不是隊列的基本運算？A.從隊尾插入一個新元素B.從隊列中刪除第 i 個元素C.判斷一個隊列是否為空D .讀取隊頭元素的值42.若已知一個棧的進棧序列是1，2，3，n，其輸出序列為 pl，p2， p3，pn，若 pl = n，則 pi 為 C 。A. i B. n iC

9、. n i+ 1 D.不確定43.判定一個順序棧 st （最多元素為 MaxSize）為空的條件是B 。A.st top !top = 1C. st top !top = MaxSizeD.沒有共同點D. abcde下載可編輯.專業(yè).整理.44. 判定一個順序棧 st （最多元素為 MaxSize）為滿的條件是 DA.st top !top = 1C. st top !下載可編輯.專業(yè).整理.A.qu rear -qu rear -qu front 1 = = MaxSizeC. qu front 147. 在循環(huán)隊列中,若 front 與 rear 分別表示對頭元素和隊尾元素的位置，則判斷循

10、環(huán)隊列空的條件是C 。D. front = = 048.向一個棧頂指針為 h的帶頭結(jié)點的鏈棧中插入指針s 所指的結(jié)點時，應(yīng)執(zhí)行 D 操作。A. h n ext = s ;topMaxSize45. 個隊列的入隊序列是4,則隊列的輸出序列是B 。A. 4, 3, 2, 11, 2, 3,C. 1, 4, 3, 23, 2, 4,46.判定一個循環(huán)隊列 qu（最多元素為 MaxSize）為空的條件是 C 。A. front = rear + 1B. rear = = front + 1C. front = rear下載可編輯.專業(yè).整理.49.輸入序列為ABC,可以變?yōu)?CBA 時，經(jīng)過的棧操作為

11、B 。A. push , pop , push , pop , push , pop B. push , push , push ,下載可編輯.專業(yè).整理.pop , pop , popC. push , push , pop , pop , push , pop D. push , pop , push , push , pop ,pop50 .若棧采用順序存儲方式存儲,現(xiàn)兩棧共享空間V1 m , top1、top2分別代表第 1 和第 2 個棧的棧頂，棧 1的底在 V1，棧 2 的底在 Vm，top1 + 1 = top2 C. top1 + top2、右括號是否配對出現(xiàn)的算法，采用 DB

12、. 隊列 C.線性表的鏈式存儲結(jié)構(gòu)D 。B. 取出最近進隊的元素D. 刪除隊頭元素B.無法判斷隊列是否為滿D .以上說法都不對54.若用一個大小為 6 的數(shù)值來實現(xiàn)循環(huán)隊列，且當前 rear 和 front 的值分 別為0 和 3,當從隊列中刪除一個元素,再加入兩個元素后，rear 和 front 的值 分別為 B 。A. 1 和 5 B. 2 和 4 C. 4 和 2D . 5 和 1則棧滿的條件是B 。A. |top2 top1| = 0 B.=m D . top1 = top251 .設(shè)計一個判別表達式中左 數(shù)據(jù)結(jié)構(gòu)最佳。A .線性表的順序存儲結(jié)構(gòu)D.棧52.允許對隊列進行的操作有A.對

13、隊列中的元素排序C.在隊頭元素之前插入元素53.對于循環(huán)隊列 D。A.無法判斷隊列是否為空C.隊列不可能滿下載可編輯.專業(yè).整理.55.隊列的 先進先出”特性是指D 。A.最早插入隊列中的元素總是最后被刪除B.當同時進行插入、刪除操作時，總是插入操作優(yōu)先C.每當有刪除操作時，總是要先做一次插入操作D.每次從隊列中刪除的總是最早插入的元素56.和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是AA.通常不會出現(xiàn)棧滿的情況B.通常不會出現(xiàn)?？盏那闆rC.插入操作更容易實現(xiàn)D .刪除操作更容易實現(xiàn)57.用不帶頭結(jié)點的單鏈表存儲隊列，其頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，則在進行出隊操作時C。A.僅修改隊頭指

14、針B.僅修改隊尾指針C.隊頭、隊尾指針都可能要修改D隊頭、隊尾指針都要修改58.若串 S= software 其子串的數(shù)目是B 。A. 8B. 37C. 36D. 959.串的長度是指 BA.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D .串中所含非空格字符的個數(shù)60.串是一種特殊的線性表，其特殊性體現(xiàn)在B 。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈式存儲 D .數(shù)據(jù)元素可以是多個字符61. 設(shè)有兩個串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運算稱為 B下載可編輯.專業(yè).整理.A.連接B.模式匹配C.求子串D.求串長下載可編輯.專業(yè).整理.62. 數(shù)

15、組 A 中，每個元素的長度為 3 個字節(jié)，行下標 i 從 1 到 8,列下標 j 從 1 到10，從首地址 SA 開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素 A85的起始地址為 C。A. SA+141 B. SA+144 C. SA+ 222D. SA+ 22563. 數(shù)組 A 中，每個元素的長度為 3 個字節(jié)，行下標 i 從 1 到 8,列下標 j從 1 到 10，從首地址 SA 開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為C 。64. 若聲明一個浮點數(shù)數(shù)組如下：froat average = new float30;假設(shè)該數(shù)組的內(nèi)存起始位置為 200， average1

16、5的內(nèi)存地址是C66.有一個 100X9 的稀疏矩陣，非0 元素有 10，設(shè)每個整型數(shù)占 2 個字A.20B.66C.18 000D.3367.數(shù)組 A04 ,1 3,57 中含有的元素個數(shù)是A.55B.45C.36D.1668.對矩陣進行壓縮存儲是為了D。C.AA.方便運算B.方便存儲A. SA+141 B. SA+180C. SA+ 222D. SA+ 225Ai，A. 214B. 215C. 260D. 25665.設(shè)二維數(shù)組 A1m,j在一維數(shù)組 B 中的下標為A. n* (i 1) + j B. n*1n按行存儲在數(shù)組(i 1)+ j 1 C.B 中，則二維數(shù)組元素i* (j 1)

17、D. j*m + i節(jié),提高運算速度D .減少存儲空間下載可編輯.專業(yè).整理.則用三元組表示該矩陣時，所需的字節(jié)數(shù)是B 。下載可編輯.專業(yè).整理.69.設(shè)有一個 10 階的對稱矩陣 A,采用壓縮存儲萬式,以行序為主存儲,al, 1 為第一個元素，其存儲地址為 1,每個元素占 1 個地址空間，則 a8, 5 的 地址為B 。A. 13 B. 33C. 18D. 4070.稀疏矩陣一般的壓縮存儲方式有兩種，即 C 。A. 16 B. 32 C.31C.1073.對一個滿二叉樹，m 個葉子,n 個結(jié)點,深度為 h，貝 U D 。A. n = h + m B h + m = 2n C m = h 1D

18、 n = 2h 174.任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對次 序 A 。A.不發(fā)生改變B.發(fā)生改變C.不能確定D .以上都不對75.在線索化樹中，每個結(jié)點必須設(shè)置一個標志來說明它的左 、右鏈指向 的是樹結(jié)構(gòu)信息，還是線索化信息，若 0 標識樹結(jié)構(gòu)信息，1 標識線索，對應(yīng)葉 結(jié)點的左右鏈域，應(yīng)標識為_ D _。A. 00B. 01C. 10D. 1176.在下述論述中,正確的是D。A.二維數(shù)組和三維數(shù)組B.C.三元組和十字鏈表D .71.樹最適合用來表示C 。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)三元組和散列散列和十字鏈表B.無序數(shù)據(jù)元素D .元素之間無聯(lián)系的

19、數(shù)據(jù)個結(jié)點。下載可編輯.專業(yè).整理.只有一個結(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。A. m n B. m n 1 C. n + 1 D .不能確定78. 若一棵二叉樹具有 10 個度為 2 的結(jié)點,5 個度為 1 的結(jié)點,貝 U 度為 0 的結(jié)點的個數(shù)是 B。A. 9 B. 11 C. 15 D.不能確定79.具有 10 個葉子結(jié)點

20、的二叉樹中有B 個度為 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 *+下載可編輯.專業(yè).整理.DE/ -,其前綴形式為D。A.-A+ B*C/DEB.-A+

21、 B*CD/EC -ABC/DED.-+ A*BC/DE84. 已知一個圖，如圖所示，若從頂點 a 出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為 _ D 一 按廣度搜索法進行遍歷，則可能得到的85 .采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_A_A.先序遍歷B.中序遍歷C.后序遍歷D .按層遍歷86.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的D_A.先序遍歷B.中序遍歷C.后序遍歷D .按層遍歷87具有 n 個結(jié)點的連通圖至少有A 條邊。A. n 1 B. n C. n (n 1) /2 D. 2n88.廣義表(a )，a)的表頭是 C ，表尾是 C 。A. aB()

22、C(a)D(a)89.廣義表(a)的表頭是 C ，表尾是 B 。A. aB()C(a)D(a)90.順序查找法適合于存儲結(jié)構(gòu)為 B 的線一種頂點序列為 A _1 A.a，b，e，c，d，fC.a，e，b，c，f，d，2A.a，b，c，e，d，fB. a，c，f， e， b， dD. a，e，d，f，c，bB. a，b，c，e，f， dD. a，c，f，d，e，b下載可編輯.專業(yè).整理.性表。A 散列存儲B 順序存儲或鏈式存儲C 壓縮存儲D 索引存儲91.對線性表進行折半查找時，要求線性表必須B 。A 以順序方式存儲B 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C 以鏈式方式存儲D 以鏈式方式存儲，

23、且結(jié)點按關(guān)鍵字有序排列92.采用折半查找法查找長度為 n 的線性表時，每個元素的平均查找長度 為 D 。A O (n2)BO (n Iog2n )CO (n)DO(Iog2n )93 .有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95,100，當折半查找值為 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+樹都能有

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

25、元素與已排序序列中的元素進 行比較，將其放入已排序序列的正確位置上的方法，稱為 CoA.希爾排序 Bo冒泡排序C 插入排序Do選擇排序99. 在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān) 的是 DoA.希爾排序B.冒泡排序C.直接插入排序D .直接選擇排序100.堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D 是一個堆。下載可編輯.專業(yè).整理.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 歸并

26、102 . D在鏈表中進行操作比在順序表中進行操作效率高。A順序查找B.折半查找C.分塊查找D .插入103.直接選擇排序的時間復雜度為D (n 為元素個數(shù))A. O (n)B. O (Iog2n )C. O (nIog2n ) 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)中元素之間存在一對

27、一關(guān)系， 樹形結(jié)構(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)的基本存儲方法是順序、鏈式、 索引和散列 存儲。下載可編輯.專業(yè).整理.7 .衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復雜度與空間復雜度。8. 評估一個算法的優(yōu)劣，通常從 時間復雜度 和 空間復雜度 兩個 方面考察。9.算法的 5 個重要特性是有窮性、確定性、可行性、輸入和 輸出。10.在一個長度為 n 的順序表中刪除第 i 個元素時，需

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

29、的關(guān)系的。17.帶頭結(jié)點的循環(huán)鏈表 L 中只有一個元素結(jié)點的條件是L next 下載可編輯.專業(yè).整理.n ext = L 。18 . 棧 是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循 后進先出的原則。19.空串是 零個字符的串 ，其長度等于 零?？瞻状怯梢粋€或多個空 格字符組成的串，其長度等于其包含的空格個數(shù)。20.組成串的數(shù)據(jù)元素只能是單個字符。21.一個字符串中 任意個連續(xù)字符構(gòu)成的部分稱為該串的子串。22.子串” str 在主串” datastructure 中的位置是 5。23.二維數(shù)組 M 的每個元素是 6 個字符組成的串，行下標 i 的范圍從 0 到 8,列下標 j 的

30、范圍從 1 到 10,貝 U 存放 M 至少需要 540 個字節(jié)；M 的第 8 列和 第 5 行共占108 個字節(jié)。24 .稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表 和十字鏈25 .廣義表(a )，( b )，c )，( d)的長度是 3，深度是 4。26 .在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0,度為 2 的結(jié)點的個數(shù)為 n2，則有 n0 = n2 + 1。27.在有 n 個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為 n+ 1。下載可編輯.專業(yè).整理.28.一棵有 n 個葉子結(jié)點的哈夫曼樹共有 2n1 個結(jié)點。29 .深度為 5 的二叉樹至多有31 個結(jié)點。30.若某二叉樹有 20 個葉子結(jié)點，

31、有 30 個結(jié)點僅有一個孩子，則該二叉 樹的總結(jié)點個數(shù)為 69。31 .某二叉樹的前序遍歷序列是 abdgcefh ，中序序列是 dgbaechf ，其后 序序列為 gdbehfca。32 .線索二叉樹的左線索指向其遍歷序列中的前驅(qū)，右線索指向其遍歷序列中的后繼。33 .在各種查找方法中，平均查找長度與結(jié)點個數(shù)n 無關(guān)的查找方法是散列查找法 。34.在分塊索引查找方法中，首先查找索引表，然后查找相應(yīng)的塊表 。35.個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程。36.具有 10 個頂點的無向圖，邊的總數(shù)最多為_45 丄37.已知圖 G 的鄰接表

32、如圖所示，其從頂點 v1 出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為_v1v2v5v4v3v6_。38 .索引是為了加快檢索速度而引進的一種數(shù)據(jù)結(jié)構(gòu)。一個索引隸屬于某 個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為 關(guān)鍵字和關(guān)鍵字對 應(yīng)記錄的地址。下載可編輯.專業(yè).整理.39 . Prim 算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n-1 ，當前選擇的邊的 權(quán)值是候選邊中最小的，選中的邊加入樹中 不產(chǎn)生回路三項原則。40.在一棵 m 階 B 樹中，除根結(jié)點外，每個結(jié)點最多有 m 棵子樹，最少有 m/2棵子樹。三、判斷題。1.在決定選

33、取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（V）2 .抽象數(shù)據(jù)類型（ADT）包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn) 的，定義僅給出一個 ADT 的邏輯特性，不必考慮如何在計算機中實現(xiàn)。（V）3.抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān) 。（“）4 順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（x ）5. 線性表采用鏈式存儲結(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù) 的。（X）6. 對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(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. 取線性表的第 i 個元素的時間同 i 的大小有關(guān)。（x