數(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)在計(jì)算機(jī)內(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)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的A 結(jié)構(gòu)。A .邏輯B .存儲C.邏輯和存儲D .物理4 .在存儲數(shù)據(jù)時(shí)，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲C A .數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲方法5. 在決定選取何種存儲結(jié)構(gòu)時(shí)，一般不考

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

3、n2)for ( I = 0； i v n； i + + )for (j = 0; j vn； j + + )s += Bij；sum = s ；9 下面程序段的時(shí)間復(fù)雜度是 O (n*m)。for ( i = 0； i v n； i + + )for (j = 0； j vm； j + + )Aij二 0；10. 下面程序段的時(shí)間復(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. 棧的操作方式是先進(jìn)先出D. 隊(duì)列的操作方式是先進(jìn)

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

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

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

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

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

9、的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)D. Hash存取的存儲結(jié)構(gòu)37棧的特點(diǎn)是B，隊(duì)列的特點(diǎn)是 A 。A .先進(jìn)先出B.先進(jìn)后出38. 棧和隊(duì)列的共同點(diǎn)是C 。A .都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D .沒有共同點(diǎn)39. 一個(gè)棧的進(jìn)棧序列是a, b, c, d, e,則棧的不可能的輸出序列是CA. edcbaB . decbaC. dceabD. abcde40.設(shè)有一個(gè)棧,元素依次進(jìn)棧的順序?yàn)锳、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不是隊(duì)列的基本運(yùn)算？A. 從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D .讀取隊(duì)頭元素的值42. 若已知一個(gè)棧的進(jìn)棧序列是1,2, 3, n,其輸出序列為p1, p2, p3, pn,若 p1 = n,則 pi 為 C 。A. i B. n i C. n i + 1D.不確定43. 判定一個(gè)順序棧st （最多元素為MaxSize）為空的條件是B 。A. st top !top = 1C. st top !top = MaxSize44. 判定一個(gè)順序棧st （最多元素為MaxSize）為滿的條件是D 。A. st top !top = 1C. st t

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

12、front = = rearD. front = = 048. 向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針 s所指的結(jié)點(diǎn)時(shí)，應(yīng) 執(zhí)行D操作。A. hnext= h ；C. s n ext= hnext= s ;49. 輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(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個(gè)棧的棧頂，棧1的底在V1，棧2的底在Vm，則棧滿 的條件是 B 。A . |top2 top1| = 0 B . top1 + 1= top2 C . top1 + top2 = m D . top1 = top251 .設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用 D 數(shù)據(jù)結(jié)構(gòu)最佳。B 隊(duì)列C 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D 。B.取出最近進(jìn)隊(duì)的元素D 刪除隊(duì)頭元素B.無法判斷隊(duì)列是否為滿A 線性表的順序存儲結(jié)構(gòu)D棧52 允許對隊(duì)列進(jìn)行的操作有A 對隊(duì)列中的元素排序C 在隊(duì)頭元素之前插入元素53. 對于循環(huán)隊(duì)列DA 無法判斷隊(duì)列是否為

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

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

16、字符61. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為B 。A .連接 B.模式匹配C.求子串 D .求串長62. 數(shù)組A中，每個(gè)元素的長度為3個(gè)字節(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中，每個(gè)元素的長度為3個(gè)字節(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. 若聲明一個(gè)浮點(diǎn)數(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. 有一個(gè)10090的稀疏矩陣，非0元素有10,設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是B 。A. 20

18、 B.66C. 18 000 D. 3367. 數(shù)組A04, 1 -3，5 7中含有的元素個(gè)數(shù)是A 。A. 55 B.45C. 36D. 1668 .對矩陣進(jìn)行壓縮存儲是為了D 。A.方便運(yùn)算 B .方便存儲C.提高運(yùn)算速度 D .減少存儲空間69 .設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，al, 1為第一個(gè)元素，其存儲地址為1,每個(gè)元素占1個(gè)地址空間，則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ù)個(gè)結(jié)點(diǎn)。A. 16 B. 32C.31 C.1073. 對一個(gè)滿二叉樹，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h,則 D 。A. n = h+ m B h+ m = 2n C m = h 1D n = 2h 174. 任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序A 。A .不發(fā)生改變 B .發(fā)生改變C.不能確定D .以上都不75. 在線索化樹中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若 0標(biāo)識樹結(jié)構(gòu)信息，1標(biāo)識線索，對

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

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

22、 .- + A*BC/DE84 .已知一個(gè)圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為 D_;按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為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個(gè)結(jié)點(diǎn)的連通圖至少有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 .對線性表進(jìn)行折半查找時(shí)，要求線性表必須B 。A以順序方式存儲B以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯以鏈?zhǔn)椒绞酱鎯Γ医Y(jié)點(diǎn)按關(guān)鍵

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

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

26、元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為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 是一個(gè)堆。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、表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A .順序查找B.折半查找C.分塊查找D.插入103. 直接選擇排序的時(shí)間復(fù)雜度為D o (n為元素個(gè)數(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)中，第一個(gè)結(jié)點(diǎn) 沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)后 續(xù)結(jié)點(diǎn)。4. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)

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

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

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

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

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

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