數(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.動態(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ī)內(nèi)存中的表示是指AoA.數(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ī)無關(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)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)C.分析算法的易讀性和文檔性(2) A.空間復(fù)雜度和時間復(fù)雜度B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8 .下面程序段的時間復(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 .下面程序段的時間復(fù)雜度是O(n*m)。for(i=0;i<n；i+)for(j=0;j<m；j+)Aij=0；10 .下面程序段的時間復(fù)雜度是O(log3n)。i=0；while(i<=n)i=i*3；11 .在以下的敘述中，正確的是BoA.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出D.隊列的操作方式是先進(jìn)后出12 .通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B。A.數(shù)據(jù)元素具

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

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

6、gt;prior>prior=s20 .如果最常用白操作是取第i個結(jié)點及其前驅(qū)，則采用D存儲方式最節(jié)省時間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表21 .在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復(fù)雜度是BA.O(1)B.O(n)C.O(n2)D.O(nlog2n)22 .在一個長度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行B操作與鏈表的長度有關(guān)。A.刪除單鏈表中的第一個元素B.刪除單鏈表中的最后一個元素C.在單鏈表第一個元素前插入一個新元素D.在單鏈表最后一個元素后插入一個新元素23.與單鏈表相比，雙鏈表的優(yōu)點之一是D。A.插入、刪除操作更簡

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

8、的循環(huán)單鏈表D.單鏈表27 .下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？C。A插入運算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大D刪除運算方便28 .下面關(guān)于線性表的敘述中，錯誤的是哪一個？B。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯Γ槐卣加靡黄B續(xù)的存儲單元D線性表采用鏈?zhǔn)酱鎯?，便于進(jìn)行插入和刪除操作。29 .線性表是具有n個B的有限序列。A.字符B,數(shù)據(jù)元素C.數(shù)據(jù)項D.表元素30 .在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復(fù)雜度是O(1)的操作是AoA.訪問第i(1<=i<=n)個結(jié)點和求第i個結(jié)點

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

10、(1)C.O(n)D.O(n2)34 .單鏈表中，增加一個頭結(jié)點的目的是為了CoA.使單鏈表至少有一個結(jié)點B.標(biāo)識表結(jié)點中首結(jié)點的位置C.方面運算的實現(xiàn)D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?5 .在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是BoA.p>next=p>next=p>next=s；C.p>next=s>next=s>next；p>next=s36 .線性表的順序存儲結(jié)構(gòu)是一種AoA.隨機(jī)存取的存儲結(jié)構(gòu)B.順序存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)D.Hash存取的存儲結(jié)構(gòu)37 .棧的特點是B,隊列的特點是A。A.先進(jìn)先出B.先進(jìn)后出

11、38 .棧和隊列的共同點是C。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點處插入和刪除元素D.沒有共同點39 .一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是C。A.edcbaB.decbaC.dceabD.abcde40 .設(shè)有一個棧，元素依次進(jìn)棧的順序為A、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不是隊列的基本運算？A.從隊尾插入一個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值42 .若已知一個棧的進(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 .判定一個順序棧st（最多元素為MaxSize）為空的條件是B。A.st>top!top=1C.st>top!top=MaxSize44 .判定一個順序棧st（最多元素為MaxSize）為滿的條件是D。A.st>top!top=11 .st>top!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（最多元素

13、為MaxSize）為空的條件是C。A.qu>rearqu>rearqu>front1=MaxSizeC.qu>front147 .在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是CoA.front=rear+1B.rear=front+1C.front=rearD.front=048 .向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應(yīng)執(zhí)行D操作。A.h>next=h；C.s>next=h>next=s;49.輸入序列為ABC可以變?yōu)镃BAM,經(jīng)過的棧操作為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 .若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1m,top1、top2分別代表第1和第2個棧的棧頂，棧1的底在V1,棧2的底在Vm,則棧滿的條件是B。A.|top2top1|=0B.top1+1=top2C.top1+top2=mD.top1=top251 .設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用D數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲結(jié)構(gòu)B.隊列 C.線

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

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

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

18、10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為CoA.SA+141B.SA+180C,SA+222D,SA22564 .若聲明一個浮點數(shù)數(shù)組如下：froataverage口=newfloat30;假設(shè)該數(shù)組的內(nèi)存起始位置為200,average15的內(nèi)存地址是C。A.214B,215C,260D.25665 .設(shè)二名t數(shù)組A1m,1n按行存儲在數(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 .有一個100X90的稀疏矩陣，非0元素有10,設(shè)每個整型數(shù)占2個字節(jié)，

19、則用三元組表示該矩陣時，所需白字節(jié)數(shù)是BoA.20B.66C.18000D.3367 .數(shù)組A04,1一3,5刀中含有的元素個數(shù)是A。A.55B.45C.36D.1668 .對矩陣進(jìn)行壓縮存儲是為了D。A.方便運算B.方便存儲C.提高運算速度D.減少存儲空間69 .設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，a1,1為第一個元素，其存儲地址為1,每個元素占1個地址空間，則a8,5的地址為BoA.13B.33C.18D.4070 .稀疏矩陣一般的壓縮存儲方式有兩種，即C。A,二維數(shù)組和三維數(shù)組B,三元組和散列學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考C.三元組和十字鏈表71 .樹最適

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

21、0A. 00B. 01C. 10D. 1176 .在下述論述中，正確的是只有一個結(jié)點的二叉樹的度為0;二叉機(jī)t的度為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-nB.m-n1C.n+1D.不能確定78 .若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點的個數(shù)是B。A.9B.11C.15D.不能確定79 .具有10個葉子結(jié)點的二叉樹中有B個度為2的結(jié)點。A.8B.9C.10D.1180

22、.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的C倍。A.1/2B1C2D481 .在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B倍。A.1/2B1C2D482 .某二叉樹結(jié)點的中序序列為ABCDEFGt序序列為BDCAFG則其左子樹中結(jié)點數(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 .已知一個圖，如圖所示，若從頂點a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的

23、一種頂點序列為D;按廣度搜索法進(jì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 .采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的A0A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷86 .采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的DoA.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷87 .具有n個結(jié)點的

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 .順序查找法適合于存儲結(jié)構(gòu)為B的線性表。A散列存儲B順序存儲或鏈?zhǔn)酱鎯壓縮存儲D索引存儲91 .對線性表進(jìn)行折半查找時，要求線性表必須B。A以順序方式存儲B以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯以鏈?zhǔn)椒绞酱鎯?，且結(jié)點按關(guān)鍵字有序排列92 .采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為D。AO(n2)BO(nlog2n)CO(n)DO(log2n

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

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

27、冒泡排序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在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A.順序查找B.折半查找C.分塊查找D.插入103 .直接選擇排序的時間復(fù)雜度為D。(n為元素個數(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)

28、三種類型，樹形結(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)、樹形結(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é)構(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)?、索引和散列存儲? .衡量一個算法的

29、優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復(fù)雜度與空間復(fù)雜度。8 .評估一個算法的優(yōu)劣，通常從時間復(fù)雜度和空間復(fù)雜度兩個方面考察。9 .算法的5個重要特性是有窮性、確定性、可行性、輸入和輸出。10 .在一個長度為n的順序表中刪除第i個元素時，需向前移動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 .當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線

30、性表的元素是，應(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>next>next=L。18 .棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運算遵循后進(jìn)先出的原則。19 .空用是零個字符的用,其長度等于零。空白用是由一個或多個空格字符組成的申，其長度等于其包含的空格個數(shù)。20 .組成用的數(shù)據(jù)元素只能是單個字符。21 .一個字符串中任意個連續(xù)字符構(gòu)成的部分稱為該用的子用。

31、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é)。學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考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_028 .一棵有n個葉子結(jié)點的哈夫曼

32、樹共有_2n-1_個結(jié)點。29 .深度為5的二叉樹至多有31個結(jié)點。30 .若某二叉樹有20個葉子結(jié)點，有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)造樹的過程即為對無序序列進(jìn)行

33、排序的過程。36 .具有10個頂點的無向圖，邊的總數(shù)最多為_45_。37 .已知圖G的鄰接表如圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_,其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為_v1v2v5v4v3v6_。38 .索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字對應(yīng)記錄的地址。39 .Prim算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n-1,當(dāng)前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項原則。40 .在一棵m階B樹中，除根結(jié)點外，每個結(jié)點最多有m棵子樹，最少有m

34、/2棵子樹。三、判斷題。1 .在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（，）2 .抽象數(shù)據(jù)類型（ADT包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機(jī)中實現(xiàn)。（，）3 .抽象數(shù)據(jù)類型與計算機(jī)內(nèi)部表示和實現(xiàn)無關(guān)。（，）4 .順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。（X）5 .線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（X）學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考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ū)別在于是

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

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

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

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

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

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

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

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

43、,整個堆排序過程的時間復(fù)雜度為。12 .在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。三、計算題(每題6分，共24分)1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A0.next,試寫出該線性表。datanext2.3 .已知一個圖的頂點集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;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4 .畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每

44、加入一個數(shù)據(jù)后堆的變化。四、閱讀算法(每題7分，共14分)1. LinkListmynote(LinkListL)/L是不帶頭結(jié)點的單鏈表的頭指針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；請回答下列問題：(1)說明語句S1的功能；(2)說明語句組S2的功能；(3)設(shè)鏈表表示白線性表為(a1,a2,?,an)，寫出算法執(zhí)行后的返回值所表示的線性表。2. voidABC(BTNode*BT)ifBTABC(BT

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

46、L中結(jié)點的值等于給定值X的結(jié)點數(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.正確性易讀性強壯性高效率2.O(n)3.9334. -134X*+2Y*3/-5. 2nn-1n+1學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考7 .有向無回路8 .n(n-1)/2n(n-1)9 .(12,40)()(74)(23,55,63)10 .增加111 .O(log2n)O(nlog2n)12.歸并三、計算題(每題6分，共24分)1.線性表為：(78,5

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

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

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

50、)n(n-1)(C)n(D)n-16 .設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為()。(A)9(B)10(C)11(D)127 .設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有()個表頭結(jié)點。(A)n-1(B)n(C)n+1(D)2n-18 .設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個記錄關(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ù)，必須解決的兩個問題是和2 .下面程序段的功能實現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上

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

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

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

54、一個算法能夠在O(n)的時間學(xué)習(xí)資料學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考Ki ,右半部分的每個關(guān)鍵字均復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于大于等于Ki。2 .設(shè)有兩個集合A和集合B,要求設(shè)計生成集合C=A1B的算法，其中集合AB和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷(二)參考答案一、選擇題1 .D2.B3.C4.A5.A6.C7.B8.C二、填空題2 .構(gòu)造一個好的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 .樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略5 .E=(1,3),(1,2),(3,5),(5,6),(6,4)6 .略四、算法設(shè)計題1 .設(shè)有一組初始記錄關(guān)鍵字序列(K1,K2,?,Kn),要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki,右半部分的每個關(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