數(shù)據(jù)結(jié)構(gòu)試題庫答案

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

一、單項選擇題

⑴一個算法應(yīng)該就是()。

A)程序B)問題求解步驟得描述

C)要滿足五個基本屬性”D)A與C

⑵算法指得就是()。

A)計算機(jī)程序B)解決問題得計算方法

C)排序算法。。D)解決問題得有限運(yùn)算序列。

⑶與數(shù)據(jù)元素本身得形式、內(nèi)容、相對位置、個數(shù)無關(guān)得就是數(shù)據(jù)得()。

A)存儲結(jié)構(gòu)B)邏輯結(jié)構(gòu)C)算法D)操作

(4)從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類。

A)動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)-B)順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C)線性結(jié)構(gòu)、非線性結(jié)構(gòu)”，D)初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

(5)下列敘述中正確得就是(

A)一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)

B)數(shù)據(jù)得邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)

C)一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理得效率

D)一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理得效率

(6)數(shù)據(jù)得基本單位就是()

?A)數(shù)據(jù)項。。B)數(shù)據(jù)類型C)數(shù)據(jù)元素?D)數(shù)據(jù)變量

(7)下列程序得時間復(fù)雜度為()

i=0；s=0;

while(s<n)

{i++;s=s+i;}

A)O()?B)O()?C)O(n)??D)0(n2)

(8)下列程序段得漸進(jìn)時間復(fù)雜度為()。

for(inti=l；i〈=n;i++)

for(intj=l；j〈=m;j++)

A[i][j]=i*j；

A)0(m2)B)0(n2)?C)0(m*n)?D)(m+n)

(9)程序段如下：

sum=0;

for(i=l;i<=n;i++)

for(j=1；j〈=n;j++)

sum++；

其中n為正整數(shù)，則最后一行得語句頻度在最壞情況下就是()o

A)O(n)。oB)O(nlogn)。C)O(n)D)0(n~)

(10)在下面得程序段中，對x得賦值語句得頻度為()o

for(i=l；i>=n；i++)

for(j=1；j>=n;j++)

x:=x+1;

2n

A)0(2n)?B)0(n)?C)0(n)oD)O(log2)

(11)程序段for(i:=n—1;i<=l；i--)

for(j：=1；j>=i;j++)

if(a[j]>a[j+1])

{t=a[j];a[j]=a[j+1]；a[j+l]=t;}

其中n為正整數(shù)，則最后一行得語句頻度在最壞情況下就是()。

A)0(n)?B)0(n1ogn)C)0(n3)??D)0(n2)

(12)設(shè)有一個遞歸算法如下：

intfact(intn)

{/*大于等于0*/

if(n<=0)return1

elsereturnn*fact(n—1)

)

則計算fact(n)需要調(diào)用該函數(shù)得次數(shù)為()。

A)nB)n+loC)n+2D)n-1

(13)下述程序段中語句①得頻度就是()。

s=0；

for(i=1;i〈m；i++)

for(j=O;j<=i;j++)

s+=j;

A)?B)?C)6D)

(14)若某線性表中最常用得操作就是在最后一個元素之后插入一個元素與刪除第一個元素，則最

節(jié)省運(yùn)算時間得存儲方式就是()。

A)單鏈表。。B)僅有頭指針得單循環(huán)鏈表

C)雙鏈表。。D)僅有尾指針得單循環(huán)鏈表

(1)求循環(huán)鏈表中當(dāng)前結(jié)點得后繼與前驅(qū)得時間復(fù)雜度分別就是()。

A)0(n)與O(l)gB)0⑴與0(1)C)0⑴與O(n)D)0(n)與0(n)

(15)求單鏈表中當(dāng)前結(jié)點得后繼與前驅(qū)得時間復(fù)雜度分別就是().

?A)O(n)與0(1)。B)0(1)與0(1)

?C)0⑴與0(n)°°D)0(n)與O(n)

(16)非空得單循環(huán)鏈表得頭指針為head,尾指針為rear,則下列條件成立得就是()。

?A)rear->next==head?B)rear—〉next->next==head

?C)head—>next==rearD)head—〉next-〉next==rear

(17)從一個長度為n得順序表中刪除第i個元素(1WiWn)時，需向前移動得元素得個數(shù)就是

()。

A)n—i8OB)n-i+1C)n-i—1。??D)i

(18)已知一個有序表為(13,18,24,35,47,50,62,83,90,115,134),當(dāng)二分檢索值為90得元素

時，檢索成功需比較得次數(shù)就是()o

A)1??B)2。。?C)3。D)4

(19)假設(shè)以行優(yōu)先順序存儲三維數(shù)組R[6][9][6],其中元素R[0][0]⑼得地址為2100,且每

個元素占4個存儲單元，則存儲地址為2836得元素就是()。

A)R[3][3][3]?B)R[3][3][4]?C)R[4][3][5]D)

R[4][3][4]

(20)設(shè)有一個10階得對稱矩陣A,采用壓縮存儲方式以行序為主序存儲,aOO為第一個元素，其存

儲地址為0,每個元素占有1個存儲地址空間，則a45得地址為()o

A)13B)35?of>f>C)36

(21)線性表采用鏈?zhǔn)酱鎯r，節(jié)點得存儲得地址()。

A)必須就是不連續(xù)得?B)連續(xù)與否均可

C)必須就是連續(xù)得。2)與頭節(jié)點得存儲地址相連續(xù)

(22)用鏈表表示線性表得優(yōu)點就是()。

A)便于隨機(jī)存取B)花費(fèi)得存儲空間比順序表少

C)數(shù)據(jù)元素得物理順序與邏輯順序相同D)便于插入與刪除

(23)鏈表不具有得特點就是()。

A)插入、刪除不需要移動元素“B)可隨機(jī)訪問任一元素

C)不必事先估計存儲空間，D)所需空間與線性長度成正比

(24)在長度為n得順序表中刪除第i個元素(iWiWn)時，元素移動得次數(shù)為()。

A)n—i+1oB)i?C)i+1?D)n-i

(25)采用順序搜索方法查找長度為n得順序表示，搜索成功得平均搜索長度為().

A)n，B)n/2?C)(n—1)/2?D)(n+1)/2

(26)將長度為n得單鏈表鏈接在長度為m得單鏈表之后得算法得時間復(fù)雜度為()。

A)O(1)B)O(n)sC)O(m)°D)O(m+n)

(27)若不帶頭結(jié)點得單鏈表得頭指針為head,則該鏈表為空得判定條件就是()。

A)head==NULL=B)head-)next==NULL?C)head!=NULL?D)head->

next==head

(28)某線性表中最常用得操作就是在最后一個元素之后插入一個元素與刪除第一個元素，則采用

()存儲方式最節(jié)省運(yùn)算時間。

A)單鏈表。。。B)僅有頭指針得單循環(huán)鏈表

C)雙鏈表。。。D)僅有尾指針得單循環(huán)鏈表

(29)若允許表達(dá)式內(nèi)多種括號混合嵌套，則為檢查表達(dá)式中括號就是否正確配對得算法，通常選用

得輔助結(jié)構(gòu)就是()。

??A)棧。B)線性表<)隊列。。oD)二叉排序樹

(30)順序棧S中top為棧頂指針，指向棧頂元素所在得位置，elem為存放棧得數(shù)組,則元素e進(jìn)

棧操作得主要語句為()。

A)s、elem[topj=e：s、top=s、top+1;B)s、elemEtop+1J=e；s、top=s、to

P+1;

C)s、top=s、top+1；s、e1em[top+1]=e;。必s、top=s、top+1;s、elem[top]

=e；

(31)循環(huán)隊列sq中，用數(shù)組elem[0??25]存放數(shù)據(jù)元素，sq、fr。nt指示隊頭元素得前一

個位置，sq、rear指示隊尾元素得當(dāng)前位置，設(shè)當(dāng)前sq、front20,sq^rear為12,則

當(dāng)前隊列中得元素個數(shù)為()。

A)8。B)16。C)17。。。D)18

(32)鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯得優(yōu)點就是()。

A)插入操作更加方便?B)通常不會出現(xiàn)棧滿得情況

C)不會出現(xiàn)?？盏们闆r。。。?？?刪除操作更加方便

(33)一個遞歸得定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運(yùn)行時間來瞧，通常

遞歸過程比非遞歸過程()。

A)較快B)較慢。0相同oD)不定

(34)若已知一個棧得入棧序列就是1,2,3,4……n,其輸出序列為pl,p2,p3,……pn,若p1==n,

則P^()。

?A)i。B)n==i?C)n—i+1。D)不確定

(35)一個棧得入棧序列就是a,b,c,d,e,則棧得不可能得輸出序列就是()。

A)edebaB)decba?C)deeab?D)abcde

(36)若進(jìn)棧序列為123,4,5,6,且進(jìn)棧與出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)得出棧序列就是

()。

A)2,4,3,1,5,6?B)3,2,4,1,6,5

C)4,3,2,1,5,6。~D)2,3,5」，6,4

(37)對于棧操作數(shù)據(jù)得原則就是().

A)先進(jìn)先出。B)后進(jìn)先出。。)后進(jìn)后出D)不分順序

(38)棧與隊列得共同點就是().

A)都就是先進(jìn)先出B)都就是先進(jìn)后出

C)只允許在端點處插入與刪除元素D)沒有共同點

(39)一個隊列得入隊序列就是1,2,3,4,則隊列得輸出序列就是(

A)4,3,2,1。B)1,2,3,4C)1,4,3,2D)

3,2,4,1

(40)設(shè)數(shù)組data[m]作為循環(huán)隊列SQ得存儲空間,fr。nt為隊頭指針，rear為隊尾指針，

則執(zhí)行出對操作后其頭指針fr。nt值為()。

A)front=front+1B)front=(front+1)%(m—1)

C)front=(front-1)%m????D)fronl=(front+1)%m

(41)引起循環(huán)隊列隊頭位置發(fā)生變化得操作就是().

A)出隊。。。B)入隊。@取隊頭元素D)取隊尾元素

(2)設(shè)以數(shù)組A[m]存放循環(huán)隊列得元素，其頭尾指針分別為fr。nt與rear，則當(dāng)前隊列中得元

素個數(shù)為()。

A)(rear-front+m)%mB)rear-front+1?C)(front—rear+m)%mD)(rear-fro

nt)%m

(42)二維數(shù)組A[12][18]采用列優(yōu)先得存儲方法，若每個元素各占3個存儲單元，且A[0][0]

地址為150,則元素A[9][7]得地址為().

A)429?B)432。()435?D)438

(43)設(shè)有一個10階得對稱矩陣A[10][10],采用壓縮方式按行將矩陣中下三角部分得元素

存入一維數(shù)組B口中,A[0][0]存入B[0]中，則A[8][5]在B口中()位置。

A)32。。也)33。C)41。必65

(44)若對n階對稱矩陣A以行序為主序方式將其下三角形得元素(包括主對角線上所有元素)依

次存放于一維數(shù)組B[l、、(n(n+l))/2]中，則在B中確定aij(i〈j)得位置k得關(guān)系為().

A)i*(i—1)/2+j。B)/2+i?C)i*(i+1)/2+j。D)j*(j+l)/2+i

(45)對稀疏矩陣進(jìn)行壓縮存儲目得就是().

A)便于進(jìn)行矩陣運(yùn)算。。B)便于輸入與輸出

C)節(jié)省存儲空間。D)降低運(yùn)算得時間復(fù)雜度

(46)對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tai1(L))得結(jié)果就是()。

A)(e.DB)((e,f))。。0⑴2)()

(47)設(shè)廣義表L=((a,b,c)),則L得長度與深度分別為().

A)1與1B)1與3C)1與2汨)2

與3

(48)樹中所有結(jié)點得度之與等于所有結(jié)點數(shù)加()?

A)0?B)1C)-l。D)2

(49)在一棵具有n個結(jié)點得二叉鏈表中，所有結(jié)點得空域個數(shù)等于().

A)n。B)n-1C)n+1?D)2*n

(50)某二叉樹得先序序列與后序序列正好相反，則該二叉樹一定就是()得二叉樹。

A)空或只有一個結(jié)點?B)高度等于其節(jié)點數(shù)

C)任一結(jié)點無左孩子。?？?任一結(jié)點無右孩子

(51)含有10個結(jié)點得二叉樹中，度為。得結(jié)點數(shù)為4,則度為2得結(jié)點數(shù)為()

A)3。。B)4。8。C)5。o?oD)6

(52)除第一層外，滿二叉樹中每一層結(jié)點個數(shù)就是上一層結(jié)點個數(shù)得()

A)1/2倍。B)1倍?！癈)2倍。?D)3倍

(53)對一棵有100個結(jié)點得完全二叉樹按層編號，則編號為49得結(jié)點，它得父結(jié)點得編號為

()

A)24。0B)25。。。098。D)99

(54)可以惟一地轉(zhuǎn)化成一棵一般樹得二叉樹得特點就是()

A)根結(jié)點無左孩子B)根結(jié)點無右孩子。C)根結(jié)點有兩個孩子。D)根結(jié)點沒有孩子

(55)設(shè)高度為h得二叉樹上只有度為0與度為2得結(jié)點，則此類二叉樹中所包含得結(jié)點數(shù)至少為

()。

A)2h。B)2h—lC)2h+1oD)h+1

(56)在一棵度為3得樹中，度為3得節(jié)點個數(shù)為2,度為2得節(jié)點個數(shù)為1,則度為0得節(jié)點個數(shù)

為()。

?A)4B)5<)6。D)7

(57)設(shè)森林F對應(yīng)得二叉樹為B,它有m個結(jié)點,B得根為p.p得右子樹結(jié)點個數(shù)為n,森林F中第

一棵子樹得結(jié)點個數(shù)就是()?

A)m-n°°°B)m-n—1~C)n+1?>D)條件不足，無法確定

(58)將一株有100個節(jié)點得完全二叉樹從上到下，從左到右依次進(jìn)行編號，根節(jié)點得編號為1,則

編號為49得節(jié)點得左孩子編號為()。

A)98出)89。.C)50??D)沒有孩子

(59)下列圖示得順序存儲結(jié)構(gòu)表示得二叉樹就是(A)

|6|A|B|C||D|E|]||[國(60)樹

oI23456789101112

最

適

合

用

來

表

示

)。

A)

有序數(shù)據(jù)元素B)無序數(shù)據(jù)元素

<)元素之間具有分支層次關(guān)系得數(shù)據(jù)2)元素之間無聯(lián)系得數(shù)據(jù)

(61)在一個非空二叉樹得中序遍歷序列中，根結(jié)點得右邊().

?A)只有右子樹上得所有結(jié)點B)只有右子樹上得部分結(jié)點

C)只有左子樹得上得部分結(jié)點”D)只有左子樹上得所有結(jié)點

(62)任何一棵二叉樹得葉結(jié)點在先序、中序與后序遍歷序列中相對次序()。

?A)不發(fā)生改變心)發(fā)生改變?C)不能確定2)以上都不對

(63)在有n個葉子結(jié)點得哈夫曼樹中,其結(jié)點總數(shù)為().

A)不確定。。B)2ngoC)2n+1?D)2n-l

(64)權(quán)值為｛1,2,6,8)得四個結(jié)點構(gòu)成得哈夫曼樹得帶權(quán)路徑長度就是()。

?A)18ooB)28C)19。D)29

(65)對一個滿二叉樹,m個樹葉，k個分枝結(jié)點,n個結(jié)點，則()。

A)n=m+l?B)m+1=2n?C)m=k-1。D)n=2k+1

(66)在含有n個頂點與e條邊得無向圖得鄰接矩陣中，零元素得個數(shù)為().

A)e°。B)2e?C)n2―e~D)n2-2e

(67)若采用鄰接矩陣翻存儲一個n個頂點得無向圖，則該鄰接矩陣就是一個()。

?A)上三角矩陣小)稀疏矩陣C)對角矩陣oD)對稱矩陣

(68)在一個圖中，所有頂點得度數(shù)之與等于所有邊數(shù)得()倍.

A)1/2??B)1oooC)2??D)4

(69)在一個有向圖中，所有頂點得入度之與等于所有頂點得出度之與得()倍。

?A)1/2??B)1??C)2。。D)4

(70)對于含n個頂點與e條邊得圖，采用鄰接矩陣表示得空間復(fù)雜度為(),>

A)O(n)B)0(e)8。C)0(n+e)?o?D)O(n2)

(71)如果求一個連通圖中以某個頂點為根得高度最小得生成樹，應(yīng)采用()。

A)。深度優(yōu)先搜索算法。。B)。廣度優(yōu)先搜索算法

C)求最小生成樹得prim算法D)拓?fù)渑判蛩惴?/p>

(72)n個頂點得連通圖至少中含有().

?A)n——1?B)n。。C)n+1。D)0

(73)n個頂點得完全有向圖中含有(

A)n—l條有向邊B)n條有向邊C)n(n—1)/2條有向邊D)n(n—l)條

有向邊

(74)假設(shè)一個有n個頂點與e條弧得有向圖用鄰接表表示，則刪除預(yù)某個頂點vi相關(guān)得所有弧得

時間復(fù)雜度就是().

A)0(n)。B)0(e)<)0(n+e)D)O(n*e)

(75)在無向圖中定義頂點Vi域Vj之間得路徑為從Vi到達(dá)Vj得一個()。

A)頂點序列B)邊序列C)權(quán)值總與D)邊得條數(shù)

(76)無向圖G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,

d),(e,d)},對該圖進(jìn)行深度優(yōu)先遍歷，得到得頂點序列正確得就是().

A)a,b,e,c,d,f?B)a,c,f,e,b,dC)a,e,b,c,f,d

D)a,e,d,f,c,b

(77)下面哪一方法可以判斷出一個有向圖就是否有環(huán)(回路)。

A)求節(jié)點得度B)拓?fù)渑判?lt;)求最短路徑D)求關(guān)鍵路徑

(78)圖得廣度優(yōu)先搜索類似于樹得()次序遍歷。

A)先根。出)中根C)后根D)層次

(79)在圖采用鄰接表存儲時，求最小生成樹得Prim算法得時間復(fù)雜度為()。

A)0(n)。?B)O(n+e)C)0(n2)?D)0(n3)

(80)已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7),E={〈VI,V2>,(VI,V3),

(V1,V4>,<V2,V5>,〈V3,V5),<V3,V6>,<V4,V6),(V5,V7>,<V6,V7>},G得拓

撲序列就是().

A)V),V3,V4,V6,V2,V5,V7出)V”V3,V2,V6,V4,V5,V7

C)V,,V3,V4,V5,V2,V6,V7oD)V,,V2,V5,V3,V4,V6,V7

(81)關(guān)鍵路徑就是事件結(jié)點網(wǎng)絡(luò)中()o

A)從源點到匯點得最長路徑。出)從源點到匯點得最短路徑

C)最長回路oD)最短回路

(82)有n個結(jié)點得有向完全圖得弧數(shù)就是()。

A)n2eB)2n。On(n一1)goD)2n(n+1)

(83)設(shè)圖得鄰接鏈表如題12圖所示，則該圖得邊得數(shù)目就是()。

A)4?B)5?C)10??D)20

(84)在一個圖中，所有頂點得度數(shù)之與等于圖得邊數(shù)得()倍。

A)1/2B)1?C)22)4

(85)在一個有向圖中,所有頂"I、----------一頂點得出度之與得()倍。

83題圖c)2

A)1/2D)4

(86)有8個結(jié)點得無向圖最多有()條邊.

A)14oB)28C)56D)

112

(87)有8個結(jié)點得無向連通圖最少有()條邊。

A)5?B)6C)7D)8

(88)有8個結(jié)點得有向完全圖有()條邊。

A)14B)28?56D)

112

(89)用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時,通常就是采用()來實現(xiàn)算法得.

A)棧oB)隊列C)樹D)圖

(90)用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常就是采用()來實現(xiàn)算法得。

A)棧?B)隊列oC)樹D)圖

(91)已知圖得鄰接矩陣,根據(jù)算法思想，則從頂點0出發(fā)按深度優(yōu)先遍歷得結(jié)點序列就是()。

oA)0243156B)0136542C)0423165D)03615

42

建議：0134256

(92)已知圖得鄰接矩陣同上題8,根據(jù)算法，則從頂點0出發(fā)，按深度優(yōu)先遍歷得結(jié)點序列就是

()。

A)0243156?B)0135642C)0423165

D)0134256

(93)已知圖得鄰接矩陣同上題8,根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷得結(jié)點序列就是

()。

A)0243651B)0136425C)0423156

D)0134256

(建議：0123456)

(94)已知圖得鄰接矩陣同上題8,根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷得結(jié)點序列就是

)。

A)0243165B)0135642C)0123465

D)0123456

(95)已知圖得鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按深度優(yōu)先遍歷得結(jié)點序列就是

()。

A)132$)0231C)0321?D)

0123

(96)已知圖得鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷得結(jié)點序列就是

()。

A)0321?B)0123C)0132D)03

I2

(97)深度優(yōu)先遍歷類似于二叉樹得()o

A)先序遍歷B)中序遍歷C)后序遍歷?D)層次遍歷

(98)廣度優(yōu)先遍歷類似于二叉樹得()。

A)先序遍歷?B)中序遍歷C)后序遍歷D)層次遍歷

(99)任何一個無向連通圖得最小生成樹()。

A)只有一棵B)一棵或多棵C)一定有多棵D)可能不

存在

(注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之與或樹權(quán)最小得情況唯一)

(100)在分析折半查找得性能時常常加入失敗節(jié)點，即外節(jié)點，從而形成擴(kuò)充得二叉樹。若設(shè)失敗節(jié)

點i所在層次為Li,那么查找失敗到達(dá)失敗點時所做得數(shù)據(jù)比較次數(shù)就是().

A)Li+1?B)Li+2??C)Li—1?D)Li

(101)向一個有127個元素原順序表中插入一個新元素并保存原來順序不變，平均要移動()個元

素。

?A)8。。蟲)63.5。。C)63?D)7

(102)由同一組關(guān)鍵字集合構(gòu)造得各棵二叉排序樹()。

A)其形態(tài)不一定相同,但平均查找長度相同

B)其形態(tài)不一定相同,平均查找長度也不一定相同

C)其形態(tài)均相同，但平均查找長度不一定相同

D)其形態(tài)均相同，平均查找長度也都相同

(103)衡量查找算法效率得主要標(biāo)準(zhǔn)就是().

A)元素得個數(shù)B)所需得存儲量C)平均查找長度D)算法難易程度

(104)適合對動態(tài)查找表進(jìn)行高效率查找得組織結(jié)構(gòu)就是()。

A)有序表°B)分塊有序表C)二義排序樹D)快速排序

(3)能進(jìn)行二分查找得線性表，必須以().

A)順序方式存儲，且元素按關(guān)鍵字有序

B)鏈?zhǔn)椒绞酱鎯Γ以匕搓P(guān)鍵字有序

C)順序方式存儲，且元素按關(guān)鍵字分塊有序

D)鏈?zhǔn)椒绞酱鎯Γ以匕搓P(guān)鍵字分塊有序

(105)為使平均查找長度達(dá)到最小，當(dāng)由關(guān)鍵字集合{05,11,21,25,37,40,41,62,84}

構(gòu)建二叉排序樹時，第一個插入得關(guān)鍵字應(yīng)為()

A)5。。出)37。C)41。。D)62

(106)對關(guān)鍵字序列(56,23,78,92,88,67,19,34)進(jìn)行增量為3得一趟希爾排序得結(jié)果為().

A)(19,23,56,34,78,67,88,92)。出)23,56,78,66,88,92,19,

34)

0(19,23,34,56,67,78,88,92)D)(19,23,67,56,34,

78,92,88)

(107)用某種排序方法對關(guān)鍵字序列｛35,84,21,47,15,27,68,25,20｝進(jìn)行排序時，序列得變化

情況如下：

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

則采用得方法就是().

A)直接選擇排序oB)希爾排序。。0堆排序。D)快速排序

(108)一組記錄得排序碼為(46,79,56,38,40,84),則利用快速排序得方法，以第一個記錄為基準(zhǔn)得

到得第一次劃分結(jié)果為()o

?A)38,40,46,56,79,84B)40,38,46,79,56,84C)40,38,46,56,79,842)

40,38,46,84,56,79

(109)快速排序在最壞情況下得時間復(fù)雜度就是()

A)O(n2log2n)。。B)0(n2)?C)O(nlog2n)”D)0(log2n)

(110)下列排序算法中不穩(wěn)定得就是()。

A)直接選擇排序B)折半插入排序?C)冒泡排序-D)快速排序

(111)對待排序得元素序列進(jìn)行劃分,將其分為左、右兩個子序列，再對兩個子序列進(jìn)行同樣得排序

操作，直到子序列為空或只剩下一個元素為止.這樣得排序方法就是()。

A)直接選擇排序B)直接插入排序?C)快速排序D)冒泡排序

(112)將5個不同得數(shù)據(jù)進(jìn)行排序，至多需要比較()次。

A)8B)9?C)10必25

(113)排序算法中，第一趟排序后，任一元素都不能確定其最終位置得算法就是()。

A)選擇排序。也)快速排序C)冒泡排序?！癉)插入排序

(114)排序算法中，不穩(wěn)定得排序就是()。

A)直接插入排序也)冒泡排序。。C)堆排序6。D)選擇排序

(115)排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)中得元素進(jìn)行比較,

將其放入已排序序列得正確位置上得方法，稱為()、

A)希爾排序B)冒泡排序C)插入排序D)選擇

排序

(116)從未排序序列中挑選元素,并將其依次插入已排序序列(初始時為空)得一端得方法，稱為

A)希爾排序B)歸并排序C)插入排序D)選擇排序

(117)對n個不同得排序碼進(jìn)行冒泡排序，在下列哪種情況下比較得次數(shù)最多。()

A)從小到大排列好得B)從大到小排列好得

C)元素?zé)o序。。??D)元素基本有序

(118)對n個不同得排序碼進(jìn)行冒泡排序，在元素?zé)o序得情況下比較得次數(shù)為()o

A)n+1B)n?C)n—1?D)n(n-1)

/2

(119)快速排序在下列哪種情況下最易發(fā)揮其長處。()

A)被排序得數(shù)據(jù)中含有多個相同排序碼

B)被排序得數(shù)據(jù)已基本有序

C)被排序得數(shù)據(jù)完全無序

D)被排序得數(shù)據(jù)中得最大值與最小值相差懸殊

(120)對有n個記錄得表作快速排序,在最壞情況下，算法得時間復(fù)雜度就是()。

23

A)0(n)^B)0(n)。C)0(n1og2n)0D)O(n)

(121)若一組記錄得排序碼為(46,79,56,38,40,84),則利用快速排序得方法，以第一個記錄為

基準(zhǔn)得到得一次劃分結(jié)果為()。

A)38,40,46,56,79,84B)40,38,46,7

9,56,84

C)40,38,46,56,79,84D)40,38,46,84,

56,79

(122)下列關(guān)鍵字序列中，()就是堆.

A)16,72,31,23,94,53?B)94,23,31,72,16,53

C)16,53,23,94,31,72。D)16,23,53,31,

94,72

(123)堆就是一種()排序.

A)插入止)選擇“C)交換"D)歸并

(124)堆得形狀就是一棵()。

A)二叉排序樹B)滿二叉樹“C)完全二叉樹D)平衡二叉樹

(125)若一組記錄得排序碼為(46,79,56,38,40,84),則利用堆排序得方法建立得初

始堆為().

A)79,46,56,38,40,84出)84,79,56,38,40,46

C)84,79,56,46,40,38D)84,56,79,40,46,

38

(126)下述幾種排序方法中，要求內(nèi)存最大得就是()。

A)插入排序B)快速排序<)歸并排序D)選擇排序

(127)有一組數(shù)據(jù)(15,9,7,8,20,-1,7,4),用堆排序得篩選方法建立得初始堆為().

A)-1,4,8,9,20,7,15,7“B)-1,7,15,7,4,8,20,9

C)一1,4,7,8,20,15,7,9D)A,B,C均不對。

(128)51.下列四個序列中，哪一個就是堆()。

A)75,65,30,15,25,45,20,10。?B)75,65,45,10,30,25,20,15

C)75,45,65,30,15,25,20,10?D)75,45,65,10,25,30,20,15

(129)以下序列不就是堆得就是()。

A)(100,85,98,77,80,60,82,40,20,10,66)。B)(100,98,85,82,80,77,66,

60,40,20,10)

C)(10,20,40,60,66,77,80,82,85,98,100)。D)(100,85,40,77,80,60,66,98,

82,10,20)

(130)快速排序方法在()情況下最不利于發(fā)揮其長處.

A)要排序得數(shù)據(jù)量太大。不)要排序得數(shù)據(jù)中含有多個相同值

C)要排序得數(shù)據(jù)個數(shù)為奇數(shù)。D)要排序得數(shù)據(jù)已基本有序

(131)對關(guān)鍵碼序列28,16,32,12,60,2,5,72快速排序，從小到大一次劃分結(jié)果為()。

A)(2,5,12,16)26(60,32,72)。。。B)(5,16,2,12)28(60,32,72)

C)(2,16,12,5)28(60,32,72)。。。D)(5,16,2,12)28(32,60,72)

(132)對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時，速度最快得情形就是().

A){21,25,5,17,9,23,30}。。B){25,23,30,17,21,5,9}

C){21,9,17,30,25,23,5}。。D){5,9,17,21,23,25,30)

二、填空題

(133)數(shù)據(jù)結(jié)構(gòu)就是一門研究非數(shù)值計算得程序設(shè)計問題中計算機(jī)得操作對象以及它

們之間得關(guān)系與運(yùn)算等得學(xué)科.

(134)數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R),其中D就是數(shù)據(jù)元素得有限集合,R就是D上

得關(guān)系有限集合。

(135)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)得邏輯結(jié)構(gòu)、數(shù)據(jù)得存儲結(jié)構(gòu)與數(shù)據(jù)得運(yùn)算這三個方

面得內(nèi)容.

(136)數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別就是線性結(jié)構(gòu)與