1、1數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題。1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C。A.動(dòng)態(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ù)的存儲(chǔ)結(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.存儲(chǔ)C.邏輯和存儲(chǔ)D.物理4.在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)C。A.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法5.在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮M。A.各結(jié)點(diǎn)的值如何B.結(jié)點(diǎn)個(gè)數(shù)的多少C

2、.對(duì)數(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.算法分析的目的是 匚，算法分析的兩個(gè)主要方面是A。(1 ) A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)C.分析算法的易讀性和文檔性2(2 ) A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性38.下面程序段的時(shí)間復(fù)雜度是O(n2。s =0;for( I =0; in; i+)for(j=0;jn;

3、j+)s +=Bij; sum = s ;9.下面程序段的時(shí)間復(fù)雜度是O(n*m)。for( i =0; in; i+) for(j=0;jm;j+)Aij = 0;10.下面程序段的時(shí)間復(fù)雜度是O(log3n)。i = 0;while (inext =NULL415.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A . head = NULL B head-next =NULLC. head-next =head D head!=NULL16.若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用D存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.給出表頭指針的單循環(huán)鏈表C.雙鏈表D.帶

4、頭結(jié)點(diǎn)的雙循環(huán)鏈表17.需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是BA.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲(chǔ)結(jié)構(gòu)18.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足C。A . p-next = NULL B . p = NULLC. p-next =head D . p = head19.在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是DOA . p-prior = s ;s-next = p ; p-prior-next = s ;s-prior = p-priorB.p-prior = s ; p-prior-next = s ;s-next = p ;

5、s-prior = p-priorC.s-next = p ;s-prior = p-prior; p-prior = s ;p-prior-next = sD.s-next = p ;s-prior = p-prior; p-prior-next = s ; p-prior = s 20 .如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用_D_存儲(chǔ)方式最節(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 (n

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

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

8、表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。29.線性表是具有n個(gè)B的有限序列。A.字符B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.表元素630.在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O (1)的操作是A。A .訪問第i (1=i=n )個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(1i=n)B.在第i (1=i=n )個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C.刪除第i (1=inext=s; s-next=p-next B . s-next=p-next ; p-next=s; C . p-next=s;p-next=s-next D . p-next=s-next ; p-next

9、=s36.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)C.索引存取的存儲(chǔ)結(jié)構(gòu)D . Hash存取的存儲(chǔ)結(jié)構(gòu)37.棧的特點(diǎn)是B，隊(duì)列的特點(diǎn)是 工。A.先進(jìn)先出B .先進(jìn)后出738.棧和隊(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,貝U棧的不可能的輸出序列是CA. edcbaB. decbaC.dceab D. abcde40.設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列C是不可能的出棧序列。A. A,B,C,D,E B . B,C,D,E,A C . E,A

10、,B,C,D D . E,D,C,B,A41.以下B不是隊(duì)列的基本運(yùn)算?A.從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值42.若已知一個(gè)棧的進(jìn)棧序列是1, 2, 3, n,其輸出序列為pl, p2, p3, , , pn,若pl =n,則pi為C_ o A . i B . n i C. n i + 1 D ,不確定43.判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是B。A . st-top != -1 B . st-top = -1C. st-top != MaxSize D . st-top = MaxSize44.判定一個(gè)順序棧st

11、（最多元素為MaxSize）為滿的條件是D。A . st-top != -1 B . st-top = -1C. st-top != MaxSize D . st-top = MaxSize45.一個(gè)隊(duì)列的入隊(duì)序列是1, 2, 3, 4,則隊(duì)列的輸出序列是BOA.4, 3, 2, 1B. 1 , 2,3, 4C.1, 4, 3, 2D. 3, 2,4, 146.判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是_。A . qu-rear - qu-front =MaxSizeB . qu-rear - qu-front -1=MaxSize8C. qu-rear =qu-frontD

12、 . qu-rear =qu-front -147.在循環(huán)隊(duì)列中，若front與rear分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是C。A.front=rear+1 B . rear=front+1 C . front=rear D . front=048.向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行D操作。A . h-next=s ; B . s-next=h ;C. s-next=h ;h =s ; D . s-next=h-next ;h-next=s ;49.輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為B。A.push, pop, push,p

13、op, push,popB. push,push, push, pop, pop,popC.push, push, pop,pop, push,popD. push, pop, push, push, pop,pop50.若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間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á)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用_D_數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲(chǔ)結(jié)構(gòu)

14、B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧52.允許對(duì)隊(duì)列進(jìn)行的操作有DOA.對(duì)隊(duì)列中的元素排序B.取出最近進(jìn)隊(duì)的元素C.在隊(duì)頭元素之前插入元素D.刪除隊(duì)頭元素53.對(duì)于循環(huán)隊(duì)列D。A.無法判斷隊(duì)列是否為空B .無法判斷隊(duì)列是否為滿C.隊(duì)列不可能滿D.以上說法都不對(duì)54.若用一個(gè)大小為6的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3,當(dāng)從隊(duì)列中刪除一 個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為_B_。9A . 1和5 B . 2和4 C. 4和2 D . 5和155.隊(duì)列的“先進(jìn)先出”特性是指D。A.最早插入隊(duì)列中的元素總是最后被刪除B.當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，

15、總是插入操作優(yōu)先C.每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D.每次從隊(duì)列中刪除的總是最早插入的元素56.和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是A。A .通常不會(huì)出現(xiàn)棧滿的情況B .通常不會(huì)出現(xiàn)?？盏那闆rC.插入操作更容易實(shí)現(xiàn)D.刪除操作更容易實(shí)現(xiàn)57.用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作 時(shí)C。A.僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都可能要修改D.隊(duì)頭、隊(duì)尾指針都要修改58.若串S= software，其子串的數(shù)目是B。A .8 B. 37 C. 36 D. 959.串的長度是指B oA.串中所含不同字母的個(gè)數(shù)B.串中所含

16、字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)60.串是一種特殊的線性表，其特殊性體現(xiàn)在B。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符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ù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A85的起始地址為C oA . SA + 141 B . SA + 144 C . SA + 222 D . SA + 2251063.數(shù)組A中，每個(gè)元素的長度為3個(gè)

17、字節(jié)， 行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為C。A .SA+ 141 B . SA +180 C . SA+ 222D . SA+ 22564.若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下：froat average=new float30;假設(shè)該數(shù)組的內(nèi)存起始位置為200, average15 的內(nèi)存地址是C。A. 214 B. 215 C. 260 D . 25665.設(shè)二維數(shù)組A1 , m,1, n按行存儲(chǔ)在數(shù)組B中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為A。A. n*(i-1)+j B . n*(i-1)+j-1 C . i

18、*(j-1) D . j*m+i-166.有一個(gè)100X90的稀疏矩陣，非0元素有10,設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí), 所需的字節(jié)數(shù)是B。A. 20 B. 66 C. 18 000 D. 3367.數(shù)組A0 , 4, -1,-3, 5 , 7中含有的元素個(gè)數(shù)是A. 55 B. 45 C. 36 D. 1668.對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了D。A.方便運(yùn)算B.方便存儲(chǔ)C.提高運(yùn)算速度D.減少存儲(chǔ)空間69.設(shè)有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a，1為第一個(gè)元素，其存儲(chǔ)地址為1,每個(gè)元素占1個(gè)地址空間，貝U a8,5的地址為B。A. 13 B. 33 C. 1

19、8 D. 40C_。A.二維數(shù)組和三維數(shù)組71.樹最適合用來表示C。70.稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即B.三元組和散列C.三元組和十字鏈表11A.有序數(shù)據(jù)元素B .無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)72.深度為5的二叉樹至多有C個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 C.1073.對(duì)一個(gè)滿二叉樹，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h,則D。A . n = h+m B h+m = 2n C m = h-1 D n = 2h-174.任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序A。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)75.在

20、線索化樹中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信 息，若0標(biāo)識(shí)樹結(jié)構(gòu)信息，1標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為D。A . 00 B. 01 C. 10 D. 1176.在下述論述中，正確的是D。只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;二叉樹的度為2;二叉樹的左右子樹可任意交換；深度為K的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A. B. C. D.77.設(shè)森林F對(duì)應(yīng)的二叉樹為B,它有m個(gè)結(jié)點(diǎn)，B的根為p, p的右子樹的結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第 棵樹的結(jié)點(diǎn)的個(gè)數(shù)是A。A . m-n B . m-n-1 C . n+1 D .不能確定78.若一棵二叉樹具

21、有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是B。A. 9 B. 11 C. 15 D.不能確定79.具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中有B個(gè)度為2的結(jié)點(diǎn)。A. 8 B. 9 C . 10 D . 111285.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的AA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷86.采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的,DA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷87.具有n個(gè)結(jié)點(diǎn)的連通圖至少有A條邊。A. n-1 B. n C. n(n-1)/2 D . 2n88.廣義表(a), a)的表頭是_C_,表尾是_C_。A. a B

22、() C (a)D (a)80.在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。81.在一個(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 . 3 B . 2 C. 4 D . 583.已知一算術(shù)表達(dá)式的中綴形式為A + B *C Q/E,后綴形式為ABC *+DE/-,其前綴形式為D。A. %+B*C/DE B . A+B*CD/E C f*ABC/DED . -A*BC/DE84.已知一個(gè)圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法能得到

23、的一種頂點(diǎn)序列為.D;按廣度搜索法進(jìn)行遍歷,種頂點(diǎn)序列為A1A . a,b, e, c, d,fC. a, e, b, c, f, d,2A . a,b, c, e, d,fC. a, e, b, c, f, d,B.a,c,f, e, b, dD.a,e, d, f, c, bB.a,b,c, e, f, dD.a,c, f, d, e, b進(jìn)行遍歷，則可則可能得到的一1389.廣義表(a)的表頭是C，表尾是B。A. a B () C (a)D (a)90.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為B的線性表。A散列存儲(chǔ)B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C壓縮存儲(chǔ)D索引存儲(chǔ)91.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須B。

24、A以順序方式存儲(chǔ)B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯?chǔ)D以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列92.采用折半查找法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為DQA O(n2)B O(nlog2n) C O(n) D O(log2n)93.有一個(gè)有序表為1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當(dāng)折半查找值為82的結(jié) 點(diǎn)時(shí)，C次比較后查找成功。A.11 B 5 C 4 D 894.二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這 種說法B。A正確B錯(cuò)誤95.下面關(guān)于B樹和B+樹

25、的敘述中，不正確的結(jié)論是A。A B樹和B+樹都能有效的支持順序查找B B樹和B+樹都能有效的支持隨機(jī)查找C B樹和B+樹都是平衡的多叉樹D B樹和B+樹都可用于文件索引結(jié)構(gòu)96.以下說法錯(cuò)誤的是 。A.散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址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.平衡二叉樹。14D.沒有左子樹的二叉排序

26、樹。98.排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的 正確位置上的方法，稱為C。A.希爾排序B。冒泡排序C插入排序Do選擇排序99.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是D。A.希爾排序B.冒泡排序C.直接插入排序D.直接選擇排序100.堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個(gè)堆。A. 94,31,53,23,16,72 B . 94,53,31,72,16,23 C. 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_。(n為元素個(gè)數(shù))A. O(n)B.O(log2n) 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)。154.線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系,樹形結(jié)構(gòu)中元素之間存在一對(duì)

28、多關(guān)系，圖形結(jié)構(gòu)中元素之間存 在多對(duì)多關(guān)系。5.在樹形結(jié)構(gòu)中， 樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有二個(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)的基本存儲(chǔ)方法是順序、鏈?zhǔn)?、索引和散列存?chǔ)。7.衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與空間復(fù)雜8.評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。9.算法的5個(gè)重要特性是有窮性、確定性、可行性、輸入和輸出。10.在一個(gè)長度為n的順序表中刪除第i個(gè)元素時(shí)，需向前移動(dòng)n-i-1個(gè)元素。11.在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。12.在雙鏈表中，每個(gè)

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

30、進(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.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組表和十字鏈25.廣義表(a), (b), c), (d)的長度是 里，深度是4。26.在一棵二叉樹中，度為

31、零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則有n0=n2+1。27.在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為 一0+1_。28.一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有_2n-1_個(gè)結(jié)點(diǎn)。29.深度為5的二叉樹至多有31個(gè)結(jié)，彌。30.若某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)個(gè)數(shù)為69。31.某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf,其后序序列為gdbehfca。1732.線索二義樹的左線索指向其遍歷序列中列前驅(qū)，右線索指向其遍歷序列中列后繼。33.在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是散列查找法。34.在分塊索引查

32、找方法中，首先查找索引表，然后查找相應(yīng)的塊表。35.一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列,構(gòu)造樹的過程即為對(duì)無序序列進(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è)索引隸屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng) 組成，索引項(xiàng)的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字對(duì)應(yīng)記錄的地址。39.Prim算法牛成一個(gè)最小牛成樹每一步選擇者K要滿足邊的總數(shù)不超過n-1 ,當(dāng)前選擇的邊的

33、權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項(xiàng)原則。40.在一棵m階B樹中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有m棵子樹,最少有m/2棵子樹。三、判斷題。1.在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)18的值如何。（vO2.抽象數(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)。（/）4.順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。（X）5.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。（X）6.對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（X）7.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（X）8.集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（X）9.線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。（X）10.線性表就