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

一word格式--范文--范例一

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

一、選擇題

oC

1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為

B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)DC.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

A

.數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是指。2

.數(shù)據(jù)的邏輯結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)BDA.數(shù)據(jù)的存儲結(jié)構(gòu).數(shù)

據(jù)

元素之間的關(guān)系

結(jié)構(gòu)。A

3.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的

.存儲BA.邏輯.物理.邏輯和存儲CD

.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且

還要存儲4

Co

.數(shù)據(jù)的處理方法AB.數(shù)據(jù)元素的類型

.數(shù)據(jù)的存儲方法.數(shù)據(jù)元素之間的關(guān)系CD

oA

.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮5

.結(jié)點(diǎn)個數(shù)的多少B.各結(jié)點(diǎn)的值如何A

.所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。D.對數(shù)據(jù)有哪

些運(yùn)算C

oD

.以下說法正確的是6

A.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位

B.數(shù)據(jù)元素是數(shù)據(jù)的最小單位

.數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合C

.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)D

A

,算法分析的兩個主要方面是C

o.算法分析的目的是7

B.研究算法中的輸入和輸出的關(guān)A1O.找出數(shù)據(jù)結(jié)構(gòu)

的合理性

系

C.分析算法的效率以求改進(jìn)C.分析算法的易讀性和文檔

性

.空間復(fù)雜度和時間復(fù)雜度A2()B.正確性和簡明性

.可讀性和文檔性CD.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

8)n2(0.下面程序段的時間復(fù)雜度是。可修改-專業(yè)資料.

―word格式一范文—范例一

；s=0

i<n；i++)for(1=0；

++)n；jfor(j=0；j<

B[i][j]；s+=

；sum=s

9.下面程序段的時間復(fù)雜度是0(n*mo)

i++)；i<n；Ofor(i=

m；j++)<for(j=0；j

0=;A[i][j]

Iog3nl0.下面程序段的時間復(fù)雜度是0()

0；i=

V=n)iwhile(

；i=i*3

11.在以下的敘述中，正確的是B

A.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)

B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表

C.棧的操作方式是先進(jìn)先出(先進(jìn)后出)

(先進(jìn)先出，尾進(jìn)首出).隊(duì)列的操作方式是先進(jìn)后出D

.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特

性，這意味著12

Bo

A.數(shù)據(jù)元素具有同一特點(diǎn)

B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相同，而且對應(yīng)

的數(shù)據(jù)項(xiàng)的類型

要一致

C.每個數(shù)據(jù)元素都一樣

D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相等

。（順序表是隨機(jī)訪問的，只要知道首元素的地址,就可13.鏈

表不具備的特點(diǎn)是A

i以知道任意的第個元素的地址）

.插入刪除不需要移動元素B.可隨機(jī)訪問任一結(jié)點(diǎn)A

D.不必事先估計存儲空間C.所需空間與其長度成正比可

修改一專業(yè)資料.

-word格式一范文—范例一

A14.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。

Ahead二二NULLBhead->next==NULL

C.head—>next———headDhead!——NULL

15.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是B。

Ahead二二NULLBhead->next==NULL

C.head—>next==head

Dhead!=NULL

16.若某表最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)

點(diǎn)或刪除最后一

個結(jié)點(diǎn)，則采用D存儲方式最節(jié)省運(yùn)算時間。

D.帶頭結(jié)CB.給出表頭指針的單循環(huán)鏈表.雙鏈表A.單

鏈表

點(diǎn)的雙循環(huán)鏈表

插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)17.需

要分配較大空間，

是B

0

.單鏈表A.線性鏈表CDB.靜態(tài)鏈表.順序存儲結(jié)構(gòu)

（需

要移動元素）

靜態(tài)鏈可以申請空間，如果空間不足夠，動態(tài)鏈表不需

要分配很大的空間，

表只能使用初始化時候的空間，不能夠追加空間

所指向）滿足pC

的尾結(jié)點(diǎn)（由head.非空的循環(huán)單鏈表18。

NULL

NULLpB.next.Ap—>head

headC—>next==p.p.D==

s19.在循環(huán)雙鏈表的所指結(jié)點(diǎn)的操作是所指的結(jié)點(diǎn)之前

插入pDo

P->prior->next=s;

S-prior=p->prior;

S—>next=p;

P->prior=s;

A.p—>

prior—>

prior

可修改一專業(yè)資料.

-word格式一范文—范例一

B.p—>

prior—>

prior

C.s—>

prior—>next=s

D.s—>

prior—>

prior=s

20.如果最常用的操作是取第i個結(jié)點(diǎn)及其前驅(qū)，則采用D

存儲方式最

節(jié)省時間。

D.單循環(huán)鏈表B.單鏈表A.雙鏈表C.順序表

個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然保持有序

的.在一個具有n21

oB時間復(fù)雜度是

Dn2(0C(A.01))(0.Bn.))nlog2n(.0

B

>n1）的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（.在

一個長度為22n

操作與鏈表的長度有關(guān)。

A.刪除單鏈表中的第一個元素

.刪除單鏈表中的最后一個元素B

.在單鏈表第一個元素前插入一個新元素C

.在單鏈表最后一個元素后插入一個新元素D

.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是。D

23

A.插入、刪除操作更簡單

B.可以進(jìn)行隨機(jī)訪問

C.可以省略表頭指針或表尾指針

D.順序訪問相鄰結(jié)點(diǎn)更靈活

.如果對線性表的操作只有兩種，24即刪除第一個元素,

在最后一個元素的

oB

后面插入新元素，則最好使用

A.只有表頭指針沒有表尾指針的循環(huán)單鏈表

B.只有表尾指針沒有表頭指針的循環(huán)單鏈表可修改一專業(yè)資料.

―word格式一范文—范例一

德球期現(xiàn)*9后6克的螃輜卻日映節(jié)點(diǎn).繆么曬喇睡第一個元素,呼后通包要

尾腳也?圖二個節(jié)點(diǎn).御加后節(jié)尊蛔摘陶第二個七點(diǎn)，這麗翻LT元瑜醮了，雨

在?后卷囊學(xué),對空0映.然后格際《腳痢針曲悶裹頭，就切

痹—同加減了,譽(yù)湖事理@O（D

融調(diào)W—Rt,磁箱―FN踉沙雄愧墟F震.鶴泰漸元蕾的播入，也耐I

初卻用卿曄崎*0時，由*:廢

所以出黃骸礙好

C.非循環(huán)雙鏈表

D.循環(huán)雙鏈表

WlWn+1）,元.在長度為25n的順序表的第個位置

上插入一個元素（ii

素的移動次數(shù)為：。A

1

一.Bn.Di

C1

inA.--H

.-i

.對于只在表的首、26尾兩端進(jìn)行插入操作的線性表，

宜采用的存儲結(jié)構(gòu)為

C

A.順序表用頭指針表示的循環(huán)單鏈表.B

C.用尾指針表示的循環(huán)單鏈表D.單鏈表C

?.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)27o

B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示插入運(yùn)算方便A

（需要移動元素）存儲密度大C刪除運(yùn)算方便D

.下面關(guān)于線性表的敘述中，錯誤的是哪一個28B

9

0

A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元

B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。

C線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元

D線性表采用鏈?zhǔn)酱鎯?，便于進(jìn)行插入和刪除操作。

B的有限序列。.線性表是具有29n個

D.表元素.數(shù)據(jù)項(xiàng)C.字符AB.數(shù)據(jù)元素

0

30.在n個結(jié)點(diǎn)的線性表的數(shù)組（順序表）實(shí)現(xiàn)中，算

法的時間復(fù)雜度是

1)的操作是。A

n〈=i<1個結(jié)點(diǎn)的直接前驅(qū)(i)個結(jié)點(diǎn)和求第n

<=i<=(i.訪問第Al)

V=1(i.在第B)個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)nV=i可

修改一專業(yè)資料.

-word格式一范文—范例一

C.刪除第i(1<=i<=n)個結(jié)點(diǎn)

D.以上都不對

i個位置插入一個新元的線性表采用順序存儲結(jié)構(gòu)，在其

第31.若長度為n

Co素的算法的時間復(fù)雜度為

B).nC.0()DO(n2.0(1))00A.(

32.對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)

的時間復(fù)雜度為

o(增加一個元素需要平均移動n/2C個元素，刪除一

個元素需要平均移動

n-1/2個元素)

A.0(n)0(n)B.0(n)0(1)C.0(1)0(n)

)(0.D1)1(0

?位置元素的i)以鏈?zhǔn)椒绞酱鎯?，訪問第，a2,al33.線

性表(an,

o時間復(fù)雜度為C

(0.C)(0.B)00.A(1(0).D)n2n

34.單鏈表中，增加一個頭結(jié)點(diǎn)的目的是為了。C

B.使單鏈表至少有一個結(jié)點(diǎn)A.標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位

置

.方便運(yùn)算的實(shí)現(xiàn)CD.說明單鏈表是線性表的鏈?zhǔn)酱鎯?/p>

.在單鏈表指針為35的結(jié)點(diǎn)之后插入指針為ps的結(jié)點(diǎn)，

正確的操作是

Bo

S->next=p->next;

P-〉next二s;

A.—>p

=nextp—>

nextp=—>

；=nexts

p.C—>

=nexts—>

sp；next—>s=next=next—>

.線性表的順序存儲結(jié)構(gòu)是一種36A

0

A.順序存取的存儲結(jié)構(gòu)B.隨機(jī)存取的存儲結(jié)構(gòu)可修改一專業(yè)資

料.

一word格式一范文—范例一

C.索引存取的存儲結(jié)構(gòu)D.Hash存取的存儲結(jié)構(gòu)

,隊(duì)列的特點(diǎn)是A

o37.棧的特點(diǎn)是B

B.先進(jìn)后出A.先進(jìn)先出

38.棧和隊(duì)列的共同點(diǎn)是C

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

C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)

a,b.一個棧的進(jìn)棧序列是39,cC

o,d,e,則棧的不可能的輸出序列是

abcde.edcba

A.Bdecba

D.C.dceab

40.設(shè)有一個棧，元素依次進(jìn)棧的順序?yàn)镃

是EDBA、、C、、。下列

不可能的出棧序列。

CBECBAA.,,,D,AE,,DEA

C.D

DE,,.BBC

A

C,,B,D

41.以下?不是隊(duì)列的基本運(yùn)算B

（隊(duì)列只能隊(duì)列尾插入，隊(duì)列頭刪

除）

i.從隊(duì)列中刪除第B.從隊(duì)尾插入一個新元素A個元素

C.判斷一個隊(duì)列是否為空.讀取隊(duì)頭元素的值D

42.若已知一個棧的進(jìn)棧序列是1,2,3,,n,其輸出序列

為pl,p2,p3,?,Copn,若pl=n,則pi為

C.n-i+1DB.i.n-i.不確定A

43.判定一個順序棧st（最多元素為MaxSize）為空的條

件是B

0

top!.Ast—>

1top==—

Ctop!—>.st

MaxSize

top==

44MaxSizest（最多元素為）為滿的條件是D

.判定一個順序棧。

st.Atop—>!

1top==一

top—>st.C!

MaxSize

==top

可修改一專業(yè)資料.

一word格式一范文—范例一

45.一個隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序

列是B

4

3,21.B,A.4,3,2,1

1,3.D2,3C.1,4,,2

4,

quC

）為空的條件是MaxSize（最多元素為。46.判定一個循

環(huán)隊(duì)列

qu—>.qu->rear-A

MaxSize

1—>front—==qurear-

front==qu—〉rear

C.qu—>

1

—front

與front47.在循環(huán)隊(duì)列中，若rear分別表示對頭元素

和隊(duì)尾元素的位置，

C

則判斷循環(huán)隊(duì)列空的條件是。

rear

C==A.frontrear+1

1

+==rear.Bfront==front.

0

D.front==

的帶頭結(jié)點(diǎn)的鏈棧中插入指針h.向一個棧頂指針為48應(yīng)

s所指的結(jié)點(diǎn)時，

執(zhí)行操作。D

（鏈棧的操作和鏈表類似）

->hA.

next=h；

—>sC.

—>=hnext

snext=；

時，經(jīng)過的棧操作為B

oCBAABC49.輸入序列為，可以變?yōu)?/p>

A.push,pushB.poppoppop

pushpoppoppush,,push,,,,push,,,

pop

poppoppushpushC.,,,,D,push,,push,poppop

push,push,

pop

，push（是彈出棧的意思）pop是壓棧的意思，pop

top[2]

m]V[1

50.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間、top[l],

，棧V[l]的底在1,則棧滿V[m]的底在個棧的棧頂，

棧2和第分別代表第12

的條件是。B

m

Ctop[2]

=10

=top[l]|—|top[2].A+top[l].B=top[2]

top[l].+

top[2]

top[l].D=可修改一專業(yè)資料.

--word格式-一范文--范例一一

51.設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算

法，采用D

數(shù)

據(jù)結(jié)構(gòu)最佳。.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)A.線性表的順

序存儲結(jié)構(gòu).隊(duì)列CB

.棧D52.允許對隊(duì)列進(jìn)行的操作有Do.取出最近進(jìn)

隊(duì)的元素BA.對隊(duì)列中的元素排序

D.刪除隊(duì)頭元素C.在隊(duì)頭元素之前插入元素D53.對

于循環(huán)隊(duì)列。A.無法判斷隊(duì)列是否為空B.無法判斷隊(duì)

列是否為滿D.以上說法都不對.隊(duì)列不可能滿C

front==rear+l

循環(huán)隊(duì)列滿的標(biāo)志：

front^^rear

對列空的標(biāo)志：

front的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前546.若用一個

大小為rear和的值分

fronrear0和再加入兩個元素后，3,當(dāng)從隊(duì)列中刪除一

個元素，別為的值分t和Bo

rear-front+n)%n別為當(dāng)前隊(duì)列中元素個數(shù)公式：(

1

和4c.4

525和2B1.A和.和D..隊(duì)列的55“先

進(jìn)先出”特性是指D

.最早插入隊(duì)列中的元素總是最后被刪除A

B.當(dāng)同時進(jìn)行插入、刪除操作時，總是插入操作優(yōu)先

C.每當(dāng)有刪除操作時，總是要先做一次插入操作

D.每次從隊(duì)列中刪除的總是最早插入的元素

A

.和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是56。

.通常不會出現(xiàn)棧滿的情況A.B通常不會出現(xiàn)?？盏?/p>

情況

CD.插入操作更容易實(shí)現(xiàn).刪除操作更容易實(shí)現(xiàn)

57其頭指針指向隊(duì)頭結(jié)點(diǎn)，.用不帶頭結(jié)點(diǎn)的單鏈表存儲

隊(duì)列，尾指針指向

C

o隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時

B.僅修改隊(duì)尾指針A.僅修改隊(duì)頭指針

.隊(duì)頭、隊(duì)尾指針都可能要修改CD.隊(duì)頭、隊(duì)尾指針都要

修改可修改-專業(yè)資料.

-word格式一范文---范例一

71.樹最適合用來表示Co

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

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

數(shù)據(jù)DC

個結(jié)點(diǎn)。C72.深度為5的二叉樹至多有

1031

32.CC..16A.B

73.對一個滿二叉樹，m個葉子，n個結(jié)點(diǎn)，深度為h,

則oD

1

m

nA.=h+1

—hCm2n

=+Bhm=D

2h=n—

74.任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍

歷序列中的相對次序

oA

.不能確定.發(fā)生改變B.不發(fā)生改變ACD.以上都不

對

右鏈指向的是樹結(jié)構(gòu).在線索化樹中，75每個結(jié)點(diǎn)必須設(shè)

置一個標(biāo)志來說明它的左、標(biāo)識線索，對應(yīng)葉結(jié)點(diǎn)的左右鏈

域，應(yīng)標(biāo)標(biāo)識樹結(jié)構(gòu)信息，1信息，還是線索化信息，若0

識為—D—。

11

.BD10

.01

.A00

C.

D

o.在下述論述中，正確的是76

;③二叉樹的左右子樹可任意交①只有一個結(jié)點(diǎn)的二叉樹的

度為20；②二叉樹的度為換；

④深度為的順序二叉樹的結(jié)點(diǎn)個數(shù)小于或等于深度相同的

滿二叉樹。K

.①②③A.②④.②③④BCD.①④

77.設(shè)森林F對應(yīng)的二叉樹為B,它有m個結(jié)點(diǎn)，B的

根為P，P的右子樹

中第一棵樹的結(jié)點(diǎn)的個數(shù)是FA

o,森林的結(jié)點(diǎn)個數(shù)為n

1

—n---.Amn

m.BD1

+nC..不能確定

0

.若一棵二叉樹具有78101個度為5的結(jié)點(diǎn)，2個度

為的結(jié)點(diǎn)，則度為

B的結(jié)點(diǎn)的個數(shù)是。

15

.9

.C11

.BD.不能確定A

個葉子結(jié)點(diǎn)的二叉樹中有10.具有79B

的結(jié)點(diǎn)。2個度為

11

.A.C9

.B8

.D10

可修改一專業(yè)資料.

-word格式一范文—范例一

80.在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的

C

倍。

D4

1/2BIC2

A.

同一條邊被兩端頂點(diǎn)計算了兩次

B

81.在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)

的出度之和的

倍。

D4

1/2B1C2

A.

在一個有向圖中，入度之和等于出度之和

BDCAFGE,則其，后序序列為ABCDEFG82.某二叉樹結(jié)點(diǎn)

的中序序列為

C

左子樹中結(jié)點(diǎn)數(shù)目為：

5

2

4

CA.3

.D.B

D/EB*CA83.已知一算術(shù)表達(dá)式的中綴形式為+-，后

綴形式為ABC*+

DE/其前綴形式為D

O

.-D-++A.-AB*C/DE

B*CD/E

A.-B+C*ABC/DE

A*BC/DE

+

出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的.已知一個圖，

如圖所示，若從頂點(diǎn)84a

;;按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為

—AD——種頂點(diǎn)序列為

d

①Aa,be,c,,.Bac,b,,f,d,f

e

b

d,cf,,,,.Cae,bcfd,,,,e,aD.

d,e,,bf

decbaA②.，，，，，，.Bacf,

b

,ca.D,d,,c,,e,.Cabf,,df,,e

85.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹

的—Ao

.按層遍歷D.后序遍歷.中序遍歷B.先序遍歷AC

這是因?yàn)閳D的深度優(yōu)先遍歷算法先訪問所在結(jié)點(diǎn)，再訪

問它的鄰接點(diǎn)。與二叉樹的先序遍歷先訪問子樹的根結(jié)點(diǎn),

再訪問它的孩子結(jié)點(diǎn)（鄰接點(diǎn)）類似。圖的廣度優(yōu)先遍歷算

法類似于二叉樹的按層次遍歷。

可修改一專業(yè)資料.

-word格式一范文—范例一

86.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹

的—Do

.后序遍歷D.按層遍歷B.先序遍歷A.中序遍歷C

A

個結(jié)點(diǎn)的連通圖至少有87.具有n條邊。C.nD.2n

(1

B.n

n-1)/2

A.n-C88.廣義表((a),a)的表頭是C,表尾

是。))D((a()C(a)A.a

B

B

89.廣義表((a))的表頭是C，表尾是。((a))

C(a)DA.a

B()

B

90.順序查找法適合于存儲結(jié)構(gòu)為的線性表。CAD

索散列存儲B順序存儲或鏈?zhǔn)酱鎯嚎s存儲

引存儲B

91.對線性表進(jìn)行折半查找時，要求線性表必須。

A以順序方式存儲B以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有

序排列

以鏈?zhǔn)椒绞酱鎯?，C以鏈?zhǔn)椒绞酱鎯η医Y(jié)點(diǎn)按關(guān)鍵字有D

序排列

折半查找必須是順序存儲，而且關(guān)鍵字必須是有序的

n的線性表時，每個元素的平均查找長度為92.采用折半查

找法查找長度為

oD

C(AOn2)0()nlog2nn)D0(log2n)(B

0

93.有一個有序表為{1,3,9,12,32,41,45,62,75,

77,82,95,100},

次比較后查找成功。82C

當(dāng)折半查找值為的結(jié)點(diǎn)時，

C

4

.AB11

5

D

8

94.二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值

均大于其左孩子

o的值、小于其右孩子的值。這種說法

正確錯誤B

A

二叉樹是二叉排序樹的充要條件：可修改一專業(yè)資料.

-word格式一范文—范例一

(1)若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它

的根結(jié)點(diǎn)的值；

(2)若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或

等于它的根結(jié)點(diǎn)的值；

(3)左、右子樹也分別為二叉排序樹;

(4)沒有鍵值相等的節(jié)點(diǎn)。

A

95.下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是。

B+樹都能有BABB樹和B+樹都能有效的支持順序查

找樹和

效的支持隨機(jī)查找

樹和BCB樹和B+樹都是平衡的多叉樹B+樹都可用D

于文件索引結(jié)構(gòu)

B

96.以下說法錯誤的是。

A.散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址

B.散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指

針。

C.負(fù)載因子是散列表的一個重要參數(shù)，它反映了散列表的

飽滿程度。

D.散列表的查找效率主要取決于散列表構(gòu)造時選取的散列

函數(shù)和處理沖突

的方法。

.查找效率最高的二叉排序樹是97。C

A.所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。

B.所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。

.平衡二叉樹。C

.沒有左子樹的二叉排序樹。D

.排序方法中，98從未排序序列中依次取出元素與已排序

序列中的元素進(jìn)行

C比較，將其放入已排序序列的正確位置上的方法，稱為。

o冒泡排序BA.希爾排序插入排序CDo選擇排序

99關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的.在所

有的排序方法中，

oD

是

.冒泡排序BD.直接插入排序.希爾排序AC.直接選

擇排序可修改一專業(yè)資料.

一word格式一范文--范例一

100.堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D

是一個堆。

23

72,16,31B.23,16,72

94,53,,A.94,31,53,

72,,D16,53,23,94,31,72

.1631,23,94,53C.

.堆排序是一種B

排序。101

.歸并C.選擇.交換A.插入DB

堆排序是一種選擇排序

D

.在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。

102.插入DC.分塊查找.直接選擇A103.順序

查找B.折半查找nDo(為元素個數(shù))。排序的時間

復(fù)雜度為B.n.0()A

n2)(0nlog2n)D.0)(log2nC.(

二、填空題。

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)、

種。4狀結(jié)構(gòu)

3.在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個

結(jié)點(diǎn)有且只有1個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn)沒有后續(xù)結(jié)

點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個后續(xù)結(jié)點(diǎn)。

4.線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元

素之間存在一對

多對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。多

前驅(qū)5.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有結(jié)點(diǎn)，其余每個結(jié)

點(diǎn)有且只有1個

結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以后續(xù)前驅(qū)結(jié)點(diǎn)；葉子

結(jié)點(diǎn)沒有。任意多個

6.數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序、鏈?zhǔn)?、索引和?/p>

列存

儲。

時間復(fù)雜度與空間復(fù)雜.衡量一個算法的優(yōu)劣主要考慮正確

性、7可讀性、健壯性和。度

和時間復(fù)雜度兩個.評估一個算法的優(yōu)劣，通常從8空

間復(fù)雜度

方面考察?？尚薷囊粚I(yè)資料.

-word格式一范文--范例一

9.算法的5個重要特性是有窮性、確定性、可行性、

輸入和輸

出。

-1個10.在一個長度為n的順序表中刪除第ni個元

素時，需向前移動一i

元素。

11.在單鏈表中，要刪除某一指定的結(jié)點(diǎn)，必須找到該

結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

后繼結(jié)結(jié)點(diǎn)，另一個指向12.在雙鏈表中，每個結(jié)點(diǎn)有兩

個指針域，一個指向前驅(qū)

。點(diǎn)

個數(shù)據(jù)元素，移動數(shù)據(jù)元素n13.在順序表中插入或刪除

一個數(shù)據(jù)元素，需要平均移動的個數(shù)與位置有關(guān)。

但要求以且很少進(jìn)行插入和刪除操作，14.當(dāng)線性表的元

素總數(shù)基本穩(wěn)定，

順序最快的速度存取線性表的元素是，應(yīng)采用存儲結(jié)構(gòu)。

15將線性鏈表.根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點(diǎn)

包含的指針個數(shù)，

單鏈表。和雙鏈表分成

16.順序存儲結(jié)構(gòu)是通過下標(biāo)表示元素之間的關(guān)系的；鏈

式存儲結(jié)構(gòu)是通過指針表示元素之間的關(guān)系的。

17.帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個元素結(jié)點(diǎn)的條件是

L->next—>

onext=L

18.后其運(yùn)算遵循棧是限定僅在表尾進(jìn)行插入或刪除操

作的線性表，

進(jìn)先出的原則。

零。空白串是由一個或多個空格零個字符的串，其長度

等于.空串是19

字符組成的串，其長度等于其包含的空格個數(shù)。

20.組成串的數(shù)據(jù)元素只能是單個字符。

任意個連續(xù)字符構(gòu)成的部分21.一個字符串中稱為該串

的子串。

5

datastructurestr22.子串“在“主串“中的”位置是。

06的每個元素是個字符組成的串，行下標(biāo)i的范圍從

到8,列下標(biāo)M23.二維數(shù)組個字至少需要，則存放到的

范圍從j110M540行共占列和第8的第個字節(jié)；M

5108

節(jié)。

24.稀疏矩陣一般的壓縮存儲方法有兩種，即十字鏈表和

三元組表。

d),(((c),b),((a25.廣義表(())))的長度是，

深3

可修改一專業(yè)資料.

-word格式一范文—范例一

度是4o

,度為2的結(jié)點(diǎn)的個數(shù)為n026.在一棵二叉樹中，度為

零的結(jié)點(diǎn)的個數(shù)為

n2,則有n0=

n2+l

o

l_o+27.在有n個結(jié)點(diǎn)的二叉鏈表中，空鏈域的個數(shù)

為_n

1_個結(jié)點(diǎn)。n個葉子結(jié)點(diǎn)的哈夫曼樹共有_2n—28.一棵

有3129.深度為5的二叉樹至多有個結(jié)點(diǎn)。

則該二叉樹個結(jié)點(diǎn)僅有一個孩子，2030.若某二叉樹有個

葉子結(jié)點(diǎn)，有30

的總結(jié)點(diǎn)個數(shù)為69

O

，其后序序abdgcefh31.某二叉樹的前序遍歷序列是,中

序序列是dgbaechf

gdbehfca列為。

32.線索二叉樹的左線索指向其遍歷序列中的前驅(qū)，右

線索指向其遍歷序列中的后繼。

33.在各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)

的查找方法是散列查找法。

34.在分塊索引查找方法中，首先查找索引表，然后查找

相應(yīng)的

塊表。

35.一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一

個有序序列，

構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。

個頂點(diǎn)的無向圖，邊的總數(shù)最多為10.具有_45—o36

點(diǎn)搜先度深的出vl發(fā)優(yōu)為列索序頂從其示所圖表接鄰G

圖已.37知的如，_vlv2v3v6v5v4_出發(fā)的廣度優(yōu)先搜索序

列為vl,其從頂點(diǎn)_vlv2V5V4V3V6―。

38.索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。

個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成，索

引項(xiàng)的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字對應(yīng)記錄的地址。

39.Prim算法生成一個最小生成樹每一步選擇都要滿足邊

的總數(shù)不超過n

,—1

三選中的邊加入樹中不產(chǎn)生回路，當(dāng)前選擇的邊的權(quán)值是

候選邊中最小的

可修改一專業(yè)資料.

一word格式一范文—范例一

項(xiàng)原則。

40.在一棵m階B樹中，除根結(jié)點(diǎn)外，每個結(jié)點(diǎn)最多有m

棵子樹，最少

棵子樹。有m/2

三、判斷題。

1.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點(diǎn)的值

如何。（如

2.抽象數(shù)據(jù)類型（）包括定義和實(shí)現(xiàn)兩方面，其中定義是

獨(dú)立于實(shí)現(xiàn)ADT

的，定義僅給出一個ADTV）的邏輯特性，不必考慮如

何在計算機(jī)中實(shí)現(xiàn)。（

V）3.抽象數(shù)據(jù)類型與計算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)。（

4.順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)?/p>

存儲方式好。

（X）

5.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空

間可以是不連續(xù)

義）的。（

.對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（6

X）

X）.順序存儲方式只能用于存儲線性結(jié)構(gòu)。（7

.集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（8X）

9X）.線性表中每個元素都有一個直接前驅(qū)和一個直接

后繼。（

X）.線性表就是