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

1、學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考2012年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案、選擇題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)存中的表示是指AoA.數(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ī)無(wú)關(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ù)元素的類(lèi)型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法5 .在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不

2、考慮A。A.各結(jié)點(diǎn)的值如何B.結(jié)點(diǎn)個(gè)數(shù)的多少C.對(duì)數(shù)據(jù)有哪些運(yùn)算D.所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6 .以下說(shuō)法正確的是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)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)C.分析算法的易讀性和文檔性(2) A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡(jiǎn)明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8 .下面程序段的時(shí)間復(fù)雜度是O(n2)。s=0;for(I=0;

3、i<n；i+)for(j=0;j<n；j+)s+=Bij；學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考sum=s；9 .下面程序段的時(shí)間復(fù)雜度是O(n*m)。for(i=0;i<n；i+)for(j=0;j<m；j+)Aij=0；10 .下面程序段的時(shí)間復(fù)雜度是O(log3n)。i=0；while(i<=n)i=i*3；11 .在以下的敘述中，正確的是BoA.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出D.隊(duì)列的操作方式是先進(jìn)后出12 .通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B(niǎo)。A.數(shù)據(jù)元素具

4、有同一特點(diǎn)B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類(lèi)型要一致C.每個(gè)數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等13 .鏈表不具備白特點(diǎn)是A。A.可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.插入刪除不需要移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與其長(zhǎng)度成正比14 .不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A。next=NULLC.head>next=headDhead!=NULL15 .帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是B。next=NULLC.head>next=headDhead!=NULL16 .若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后

5、一個(gè)結(jié)點(diǎn)，則采用D存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.給出表頭指針的單循環(huán)鏈表C.雙鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表學(xué)習(xí)資料17 .需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是B。A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲(chǔ)結(jié)構(gòu)18 .非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足C。A.p>next=NULLB.p=NULLC.p>next=headD.p=head19 .在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是D。A.p>prior>priorB.p一prior>priorC.s>prior>next=sD.s&

6、gt;prior>prior=s20 .如果最常用白操作是取第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ù)雜度是BA.O(1)B.O(n)C.O(n2)D.O(nlog2n)22 .在一個(gè)長(zhǎng)度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行B操作與鏈表的長(zhǎng)度有關(guān)。A.刪除單鏈表中的第一個(gè)元素B.刪除單鏈表中的最后一個(gè)元素C.在單鏈表第一個(gè)元素前插入一個(gè)新元素D.在單鏈表最后一個(gè)元素后插入一個(gè)新元素23.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是D。A.插入、刪除操作更簡(jiǎn)

7、單B.可以進(jìn)行隨機(jī)訪問(wèn)C.可以省略表頭指針或表尾指針學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考D.順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活24 .如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用BoA.只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表B.只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表C.非循環(huán)雙鏈表D.循環(huán)雙鏈表25 .在長(zhǎng)度為n的順序表的第i個(gè)位置上插入一個(gè)元素(1&i<n+1),元素的移動(dòng)次數(shù)為:A0A.n-i+1B.n-iC.iD.i-126 .對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為CoA.順序表B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示

8、的循環(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線性表采用鏈?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.表元素30 .在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O(1)的操作是AoA.訪問(wèn)第i(1<=i<=n)個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)

9、的直接前驅(qū)(1<i<=n)31 在第i(1<=i<=n)個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C.刪除第i(1<=i<=n)個(gè)結(jié)點(diǎn)D,以上都不對(duì)31 .若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為CoA.O(0)B.O(1)C.O(n)D.O(n2)學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考32 .對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為CoA.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)33 .線性表(a1,a2,，an)以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜度為CA.O(0)B.O

10、(1)C.O(n)D.O(n2)34 .單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了CoA.使單鏈表至少有一個(gè)結(jié)點(diǎn)B.標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C.方面運(yùn)算的實(shí)現(xiàn)D.說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)35 .在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是BoA.p>next=p>next=p>next=s；C.p>next=s>next=s>next；p>next=s36 .線性表的順序存儲(chǔ)結(jié)構(gòu)是一種AoA.隨機(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。A.先進(jìn)先出B.先進(jìn)后出

11、38 .棧和隊(duì)列的共同點(diǎn)是C。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)39 .一個(gè)棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是C。A.edcbaB.decbaC.dceabD.abcde40 .設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、DE。下列C是不可能的出棧序列。A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.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,其輸出序列為p

12、1,p2,p3,，pn,若p1=n,學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考則pi為C。A.iB.n-iC.ni+1D.不確定43 .判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是B。A.st>top!top=1C.st>top!top=MaxSize44 .判定一個(gè)順序棧st（最多元素為MaxSize）為滿的條件是D。A.st>top!top=11 .st>top!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（最多元素

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

14、op,push,popB.push,push,push,pop,pop,pop學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考C.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop50 .若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1m,top1、top2分別代表第1和第2個(gè)棧的棧頂，棧1的底在V1,棧2的底在Vm,則棧滿的條件是B。A.|top2top1|=0B.top1+1=top2C.top1+top2=mD.top1=top251 .設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用D數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列 C.線

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

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

17、符的個(gè)數(shù)C.用中所含不同字符的個(gè)數(shù)D.用中所含非空格字符的個(gè)數(shù)61 .用是一種特殊的線性表，其特殊性體現(xiàn)在B。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符62 .設(shè)有兩個(gè)用p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱為B。A.連接B.模式匹配C.求子用D.求用長(zhǎng)63 .數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1至IJ10,從首地址SA開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A85的起始地址為CoA.SA+141B.SA+144C,SA+222D,SA22563 .數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1至IJ

18、10,從首地址SA開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為CoA.SA+141B.SA+180C,SA+222D,SA22564 .若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下：froataverage口=newfloat30;假設(shè)該數(shù)組的內(nèi)存起始位置為200,average15的內(nèi)存地址是C。A.214B,215C,260D.25665 .設(shè)二名t數(shù)組A1m,1n按行存儲(chǔ)在數(shù)組B中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為A。A.n*(i-1)+jB,n*(i-1)+j-1C.i*(j-1)D.j*m+i-166 .有一個(gè)100X90的稀疏矩陣，非0元素有10,設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，

19、則用三元組表示該矩陣時(shí)，所需白字節(jié)數(shù)是BoA.20B.66C.18000D.3367 .數(shù)組A04,1一3,5刀中含有的元素個(gè)數(shù)是A。A.55B.45C.36D.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ǔ)，a1,1為第一個(gè)元素，其存儲(chǔ)地址為1,每個(gè)元素占1個(gè)地址空間，則a8,5的地址為BoA.13B.33C.18D.4070 .稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即C。A,二維數(shù)組和三維數(shù)組B,三元組和散列學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考C.三元組和十字鏈表71 .樹(shù)最適

20、合用來(lái)表示CA.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)72 .深度為5的二叉樹(shù)至多有CA.16B.32C.31C.D .散列和十字鏈表B.無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù) 個(gè)結(jié)點(diǎn)。1073 .對(duì)一個(gè)滿二叉樹(shù)，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h,則D。A.n=h+mBh+m=2nCm=h1Dn=2h1A.不發(fā)生改變B .發(fā)生改變C.不能確定D,以上都不對(duì)74 .任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序A75 .在線索化樹(shù)中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹(shù)結(jié)構(gòu)信息，還是線索化信息，若0標(biāo)識(shí)樹(shù)結(jié)構(gòu)信息,1標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為_(kāi)D_

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

22、.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。A.1/2B1C2D481 .在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍。A.1/2B1C2D482 .某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFGt序序列為BDCAFG則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：CA. 3B. 2C. 4D. 583 .已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考D0A.-A+B*C/DEB.-A+B*CD/EC-+*ABC/DED.-+A*BC/DE84 .已知一個(gè)圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的

23、一種頂點(diǎn)序列為D;按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為AA. a, b, e, c, d, fB. a, c, f, e, b, dC. a, e, b, c, f, d, A. a, b, c, e, d, fD. a, e, b, c, f, d,E. a,e,d,f,c,b8. a, b, c, e, f, dD. a,c,f,d,e,b85 .采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的A0A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷86 .采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的DoA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷87 .具有n個(gè)結(jié)點(diǎn)的

24、連通圖至少有A條邊。A.n-1B.nC.n(n-1)/2D.2n88 .廣義表(a),a)的表頭是C,表尾是C。A.aB()C(a)D(a)89 .廣義表(a)的表頭是C,表尾是B。A.aB()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。A以順序方式存儲(chǔ)B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯?chǔ)D以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列92 .采用折半查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為D。AO(n2)BO(nlog2n)CO(n)DO(log2n

25、)93 .有一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，C次比較后查找成功。A.11B5C4D894 .二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考A正確B錯(cuò)誤95 .下面關(guān)于B樹(shù)和B+樹(shù)的敘述中，不正確的結(jié)論是A。AB樹(shù)和B+樹(shù)都能有效的支持順序查找BB樹(shù)和B+樹(shù)都能有效的支持隨機(jī)查找CB樹(shù)和B+樹(shù)都是平衡的多叉樹(shù)DB樹(shù)和B+樹(shù)都可用于文件索引結(jié)構(gòu)96 .以下說(shuō)法錯(cuò)誤的是B。A.散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址B.散列表的結(jié)

26、點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。C.負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度。D.散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法。97 .查找效率最高的二叉排序樹(shù)是C。A.所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)。B.所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)。C.平衡二叉樹(shù)。D.沒(méi)有左子樹(shù)的二叉排序樹(shù)。98 .排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為C。A.希爾排序Bo冒泡排序C插入排序Do選擇排序99 .在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是DoA.希爾排序B.

27、冒泡排序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在鏈表中進(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)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)

28、三種類(lèi)型，樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考2 .數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。3 .在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。4 .線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。5 .在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有后續(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è)算法的

29、優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與空間復(fù)雜度。8 .評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。9 .算法的5個(gè)重要特性是有窮性、確定性、可行性、輸入和輸出。10 .在一個(gè)長(zhǎng)度為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è)結(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)行插入和刪除操作，但要求以最快的速度存取線

30、性表的元素是，應(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)是通過(guò)下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)指針表示元素之間的關(guān)系的。17 .帶頭結(jié)點(diǎn)白循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是L>next>next=L。18 .棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循后進(jìn)先出的原則。19 .空用是零個(gè)字符的用,其長(zhǎng)度等于零?？瞻子檬怯梢粋€(gè)或多個(gè)空格字符組成的申，其長(zhǎng)度等于其包含的空格個(gè)數(shù)。20 .組成用的數(shù)據(jù)元素只能是單個(gè)字符。21 .一個(gè)字符串中任意個(gè)連續(xù)字符構(gòu)成的部分稱為該用的子用。

31、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é)。學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考24 .稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組表和十字鏈表。25 .廣義表（a）,（b）,c）,（d）的長(zhǎng)度是3,深度是4。26 .在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則有n0=n2+1。27 .在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_(kāi)n+1_028 .一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼

32、樹(shù)共有_2n-1_個(gè)結(jié)點(diǎn)。29 .深度為5的二叉樹(shù)至多有31個(gè)結(jié)點(diǎn)。30 .若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為69。31 .某二叉樹(shù)的前序遍歷序列是abdgcefh,中序序列是dgbaechf,其后序序列為gdbehfca。32 .線索二叉樹(shù)的左線索指向其遍歷序列中的前驅(qū)，右線索指向其遍歷序列中的后繼。33 .在各種查找方法中，平土§查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是散列查找法。34 .在分塊索引查找方法中，首先查找索引表，然后查找相應(yīng)的塊表。35 .一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行

33、排序的過(guò)程。36 .具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)45_。37 .已知圖G的鄰接表如圖所示，其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為_(kāi)v1v2v3v6v5v4_,其從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索序列為_(kāi)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è)最小生成樹(shù)每一步選擇都要滿足邊的總數(shù)不超過(guò)n-1,當(dāng)前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹(shù)中不產(chǎn)生回路三項(xiàng)原則。40 .在一棵m階B樹(shù)中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有m棵子樹(shù)，最少有m

34、/2棵子樹(shù)。三、判斷題。1 .在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)的值如何。（，）2 .抽象數(shù)據(jù)類(lèi)型（ADT包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個(gè)ADT的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。（，）3 .抽象數(shù)據(jù)類(lèi)型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(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）學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考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ū)別在于是

35、否按關(guān)鍵字排序。（x）9 .線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。（x）10 .線性表就是順序存儲(chǔ)的表。（x）11 .取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。（x）12 .循環(huán)鏈表不是線性表。（x）13 .鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序表中效率高（V）14 .雙向鏈表可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)。（X）15 .在單鏈表中，給定任一結(jié)點(diǎn)的地址p,則可用下述語(yǔ)句將新結(jié)點(diǎn)s插入2點(diǎn)p的后面：）next；(x)是一種先進(jìn)后出的結(jié)構(gòu)。（x（X ）16 .隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表,17 .用是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲(chǔ)。

36、18 .長(zhǎng)度為1的用等價(jià)于一個(gè)字符型常量。（X）19 .空用和空白用是相同的。（X）20 .數(shù)組元素的下標(biāo)值越大，存取時(shí)間越長(zhǎng)。（X）21 .用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。（，）22 .一個(gè)廣義表的表頭總是一個(gè)廣義表。（X）23 .一個(gè)廣義表的表尾總是一個(gè)廣義表。（V）24 .廣義表（a）,b）,c）的表頭是（a）,b）,表尾是（c）。（M）25 .二叉樹(shù)的后序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的后面。（V）26 .度為2的有序樹(shù)是二叉樹(shù)。（X）27 .二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的

37、前面。（V）28 .用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。（X）29 .若已知一棵二叉樹(shù)的前序遍歷序列和后序遍歷序列，則可以恢復(fù)該二叉樹(shù)。（X）30 .在哈夫曼樹(shù)中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。（X）31 .強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。（V）32 .對(duì)于任意一個(gè)圖，從它的某個(gè)結(jié)點(diǎn)進(jìn)行一次深度或廣度優(yōu)先遍歷可以訪問(wèn)到該圖的每個(gè)頂點(diǎn)學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考（X）33 .在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序仍然保持不變，稱這種排序?yàn)榉€(wěn)定排序。（V）34 .在平衡二叉樹(shù)中，任意結(jié)點(diǎn)左右子樹(shù)的高度差（絕對(duì)值）不超過(guò)1。（，）35 .拓?fù)渑?/p>

38、序是按AOEW中每個(gè)結(jié)點(diǎn)事件的最早發(fā)生時(shí)間對(duì)結(jié)點(diǎn)進(jìn)行排序。（X）36 .冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)。（X）37 .對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列。（X）38 .散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址。（，）39 .二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。（x）40 .具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)有多種，其中樹(shù)高最小的二叉排序樹(shù)是最佳的。（V）41 .直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為O（n）。（X）數(shù)據(jù)結(jié)構(gòu)試卷（一）一、單選題（每題2分，共20分）1 .棧和隊(duì)列的共

39、同特點(diǎn)是（）。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)2 .用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)（）.A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改3 .以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（）A.隊(duì)列B.棧C.線性表D.二叉樹(shù)4 .設(shè)有一個(gè)二維數(shù)組Amn,假設(shè)A00存放位置在644（10）,A22存放位置在676（10）,每個(gè)元素占一個(gè)空間，問(wèn)A33（10）存放在什么位置？腳注（10）表示用10進(jìn)制表示。A. 688B. 678C. 692D. 6965 .樹(shù)最適合用來(lái)表示（B.無(wú)序數(shù)據(jù)元素A.有序數(shù)據(jù)元素C.元素之間具

40、有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)6.二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為（ 學(xué)習(xí)資料).學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考kk-1A.2-1B.2K+1C.2K-1D.27 .若有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為()A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,38 .對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為A.O(1)B.O(n)C.O(1og2n)D.O(n2)9.對(duì)于線性表(7,34,55,25,64,46,20,10)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%9作為散列函數(shù)，則散列地址

41、為1的元素有()個(gè)，A.1B.2C.3D.410.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有()條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.8二、填空題(每空1分，共26分)1 .通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：?口。2 .一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2,其數(shù)量級(jí)表示為。3 .假定一棵樹(shù)的廣義表表示為A(C,D(E,F,G),H(I,J),則樹(shù)中所含的結(jié)點(diǎn)數(shù)為個(gè)，樹(shù)的深度為,樹(shù)的度為。4 .后綴算式923+-102/-的值為o中綴算式(3+4X0-2Y/3對(duì)應(yīng)的后綴算式為5 .若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)

42、中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有個(gè)指針域，其中有個(gè)指針域是存放了地址，有個(gè)指針是空指針。6 .對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有個(gè)和個(gè)。7 .AOV網(wǎng)是一種的圖。8 .在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊,在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有條邊。9 .假定一個(gè)線性表為(12,23,74,55,63,40),若按Key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為口10 .向一棵BJM插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù)比原樹(shù)的高度學(xué)習(xí)資料11 .在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為

43、,整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為。12 .在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。三、計(jì)算題(每題6分，共24分)1.在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A0.next,試寫(xiě)出該線性表。datanext2.3 .已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。4 .畫(huà)出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí)，每

44、加入一個(gè)數(shù)據(jù)后堆的變化。四、閱讀算法(每題7分，共14分)1. LinkListmynote(LinkListL)/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next)q=L;L=L>next;p=L;51: while(p>next)p=p>next；52: p>next=q；q>next=NULL;returnL；請(qǐng)回答下列問(wèn)題：(1)說(shuō)明語(yǔ)句S1的功能；(2)說(shuō)明語(yǔ)句組S2的功能；(3)設(shè)鏈表表示白線性表為(a1,a2,?,an)，寫(xiě)出算法執(zhí)行后的返回值所表示的線性表。2. voidABC(BTNode*BT)ifBTABC(BT

45、->left);學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考ABC(BT->right);cout<data<<該算法的功能是：五、算法填空(共8分)二叉搜索樹(shù)的查找遞歸算法boolFind(BTreeNode*BST,ElemType&item)if(BST=NULL)returnfalse;/查找失敗elseif(item=BST->data)item=BST->data;/查找成功return;elseif(itemdata)returnFind(,item);elsereturnFind(,item);/if六、編寫(xiě)算法(共8分)統(tǒng)計(jì)出單鏈表H

46、L中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。intCountX(LNode*HL,ElemTypex)數(shù)據(jù)結(jié)構(gòu)試卷(一)參考答案一、選擇題(每題2分，共20分)1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、填空題(每空1分，共26分)1.正確性易讀性強(qiáng)壯性高效率2.O(n)3.9334. -134X*+2Y*3/-5. 2nn-1n+1學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考7 .有向無(wú)回路8 .n(n-1)/2n(n-1)9 .(12,40)()(74)(23,55,63)10 .增加111 .O(log2n)O(nlog2n)12.歸并三、計(jì)算題(每題6分，共24分)1.線性表為：(78,5

47、0,40,60,34,90)?0?1?1?1?02.鄰接矩陣：？1110?0101?1011?0101?1110?鄰接表如圖11所示：圖113 .用克魯斯卡爾算法得到的最小生成樹(shù)為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204 .見(jiàn)圖1226四、讀算法(每題7分，共14分)1.(1)查詢鏈表的尾結(jié)點(diǎn)(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3)返回的線性表為(a2,a3,?,an,a1)2.遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。五、法填空(每空2分，共8分)trueBST->leftBST->right六、編寫(xiě)算法(8分)intCou

48、ntX(LNode*HL,ElemTypex)inti=0;LNode*p=HL;/i為計(jì)數(shù)器while(p!=NULL)if(P->data=x)i+;p=p->next;/while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)return i;學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考/CountX數(shù)據(jù)結(jié)構(gòu)試卷(二)一、選擇題(24分)1 .下面關(guān)于線性表的敘述錯(cuò)誤的是()。(A)線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間(B)線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C)線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D)線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)2 .設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)

49、總數(shù)為m若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有()個(gè)空指針域。(A)2m-1(B)2m(C)2m+1(D)4m3 .設(shè)順序循環(huán)隊(duì)列Q0:M-1的頭指針和尾指針?lè)謩e為F和R,頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為()(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M4 .設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD前序遍歷序列為CABD則后序遍歷該二叉樹(shù)得到序列為()。(A)BADC(B)BCDA(C)CDAB(D)CBDA5 .設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有()條邊。22(A)n(n-1)/2(B

50、)n(n-1)(C)n(D)n-16 .設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為()。(A)9(B)10(C)11(D)127 .設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有()個(gè)表頭結(jié)點(diǎn)。(A)n-1(B)n(C)n+1(D)2n-18 .設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為()o(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8二、填空題(24分)1 .為了能有效地應(yīng)用HASFg找技術(shù)，必須解決的兩個(gè)問(wèn)題是和2 .下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上

51、正確的語(yǔ)句學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考typedefstructints100;inttop;sqstack;voidpush(sqstack&stack,intx)if(stack.top=m-1)printf("overflow");else;3 .中序遍歷二叉排序樹(shù)所得到的序列是序列(填有序或無(wú)序)。4 .快速排序的最壞時(shí)間復(fù)雜度為,平均時(shí)間復(fù)雜度為。5 .設(shè)某棵二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為NO,度數(shù)為1的結(jié)點(diǎn)數(shù)為N1,則該二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)數(shù)為;若采用二叉鏈表作為該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有個(gè)空指針域。46 .設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為

52、n和e,所有頂點(diǎn)的度數(shù)之和為d,則=。7 .設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為8 .已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是BFS遍歷的輸出序列是三、應(yīng)用題(36分)1 .設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。2 .設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn)B,要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink)。3 .設(shè)一組有序的記錄關(guān)鍵字序列

53、為(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。4 .設(shè)一棵樹(shù)T中邊的集合為(A,B),(A,C),(A,D),(B,E),(C,F),(C,G),要求用孩子兄弟表示法(二叉鏈表)表示出該樹(shù)的存儲(chǔ)結(jié)構(gòu)并將該樹(shù)轉(zhuǎn)化成對(duì)應(yīng)的二叉樹(shù)。5 .設(shè)有無(wú)向圖G,要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。6 .設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。四、算法設(shè)計(jì)題(16分)1 .設(shè)有一組初始記錄關(guān)鍵字序列(K1,K2,?,Kn),要求設(shè)計(jì)

54、一個(gè)算法能夠在O(n)的時(shí)間學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考Ki ,右半部分的每個(gè)關(guān)鍵字均復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于大于等于Ki。2 .設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C=A1B的算法，其中集合AB和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷(二)參考答案一、選擇題1 .D2.B3.C4.A5.A6.C7.B8.C二、填空題2 .構(gòu)造一個(gè)好的HASHE數(shù)，確定解決沖突的方法3 .stack.top+,stack.sstack.top=x4 .有序24 .O(n),O(nlog2n)5. N0-1,2N0+N16. d/27. (31,38,54,56,75

55、,80,55,63)8. (1,3,4,5,2),(1,3,2,4,5)三、應(yīng)用題1 .(22,40,45,48,80,78),(40,45,48,80,22,78)2 .q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3 .2,ASL=91*1+2*2+3*4+4*2)=25/94 .樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹(shù)略5 .E=(1,3),(1,2),(3,5),(5,6),(6,4)6 .略四、算法設(shè)計(jì)題1 .設(shè)有一組初始記錄關(guān)鍵字序列(K1,K2,?,Kn),要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于Ki。voidquickpass(intr,ints,intt)inti=s,j=t,x=rs;while(i<j)<p="">學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考while(ix)j=j-1;if(i<j)ri=rj;i=i+1;while(i<j&&ri<x)i=i+1;i