2015年數據結構期末考試題與答案

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

2012年數據結構期末考試題及答案

一、選擇題

oC

1.在數據結構中，從邏輯上可以把數據結構分為

B.緊湊結構和非緊湊結構A.動態(tài)結構和靜態(tài)結構

.內部結構和外部結構DC.線性結構和非線性結構

A

.數據結構在計算機內存中的表示是指。2

.數據的邏輯結構C.數據結構BDA.數據的存儲結構.數

據

元素之間的關系

結構。A

3.在數據結構中，與所使用的計算機無關的是數據的

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

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

還要存儲4

Co

.數據的處理方法AB.數據元素的類型

.數據的存儲方法.數據元素之間的關系CD

oA

.在決定選取何種存儲結構時，一般不考慮5

.結點個數的多少B.各結點的值如何A

.所用的編程語言實現這種結構是否方便。D.對數據有哪

些運算C

oD

.以下說法正確的是6

A.數據項是數據的基本單位

B.數據元素是數據的最小單位

.數據結構是帶結構的數據項的集合C

.一些表面上很不相同的數據可以有相同的邏輯結構D

A

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

o.算法分析的目的是7

B.研究算法中的輸入和輸出的關A1O.找出數據結構

的合理性

系

C.分析算法的效率以求改進C.分析算法的易讀性和文檔

性

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

.可讀性和文檔性CD.數據復雜性和程序復雜性

8)n2(0.下面程序段的時間復雜度是?？尚薷?專業(yè)資料.

―word格式一范文—范例一

；s=0

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

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

B[i][j]；s+=

；sum=s

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

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

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

0=;A[i][j]

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

0；i=

V=n)iwhile(

；i=i*3

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

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

B.二維數組是其數據元素為線性表的線性表

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

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

.通常要求同一邏輯結構中的所有數據元素具有相同的特

性，這意味著12

Bo

A.數據元素具有同一特點

B.不僅數據元素所包含的數據項的個數要相同，而且對應

的數據項的類型

要一致

C.每個數據元素都一樣

D.數據元素所包含的數據項的個數要相等

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

表不具備的特點是A

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

.插入刪除不需要移動元素B.可隨機訪問任一結點A

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

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

-word格式一范文—范例一

A14.不帶頭結點的單鏈表head為空的判定條件是。

Ahead二二NULLBhead->next==NULL

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

15.帶頭結點的單鏈表head為空的判定條件是B。

Ahead二二NULLBhead->next==NULL

C.head—>next==head

Dhead!=NULL

16.若某表最常用的操作是在最后一個結點之后插入一個結

點或刪除最后一

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

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

鏈表

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

插入和刪除不需要移動元素的線性表，其存儲結構17.需

要分配較大空間，

是B

0

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

（需

要移動元素）

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

要分配很大的空間，

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

所指向）滿足pC

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

NULL

NULLpB.next.Ap—>head

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

s19.在循環(huá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個結點及其前驅，則采用D

存儲方式最

節(jié)省時間。

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

個結點的有序單鏈表中插入一個新結點并仍然保持有序

的.在一個具有n21

oB時間復雜度是

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

B

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

一個長度為22n

操作與鏈表的長度有關。

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

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

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

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

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

23

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

B.可以進行隨機訪問

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

D.順序訪問相鄰結點更靈活

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

在最后一個元素的

oB

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

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

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

―word格式一范文—范例一

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

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

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

痹—同加減了,譽湖事理@O（D

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

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

所以出黃骸礙好

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

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

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

上插入一個元素（ii

素的移動次數為：。A

1

一.Bn.Di

C1

inA.--H

.-i

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

宜采用的存儲結構為

C

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

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

?.下述哪一條是順序存儲結構的優(yōu)點27o

B可方便地用于各種邏輯結構的存儲表示插入運算方便A

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

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

9

0

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

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

C線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元

D線性表采用鏈式存儲，便于進行插入和刪除操作。

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

D.表元素.數據項C.字符AB.數據元素

0

30.在n個結點的線性表的數組（順序表）實現中，算

法的時間復雜度是

1)的操作是。A

n〈=i<1個結點的直接前驅(i)個結點和求第n

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

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

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

-word格式一范文—范例一

C.刪除第i(1<=i<=n)個結點

D.以上都不對

i個位置插入一個新元的線性表采用順序存儲結構，在其

第31.若長度為n

Co素的算法的時間復雜度為

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

32.對于順序存儲的線性表，訪問結點和增加、刪除結點

的時間復雜度為

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)以鏈式方式存儲，訪問第，a2,al33.線

性表(an,

o時間復雜度為C

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

34.單鏈表中，增加一個頭結點的目的是為了。C

B.使單鏈表至少有一個結點A.標識表結點中首結點的位

置

.方便運算的實現CD.說明單鏈表是線性表的鏈式存儲

.在單鏈表指針為35的結點之后插入指針為ps的結點，

正確的操作是

Bo

S->next=p->next;

P-〉next二s;

A.—>p

=nextp—>

nextp=—>

；=nexts

p.C—>

=nexts—>

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

.線性表的順序存儲結構是一種36A

0

A.順序存取的存儲結構B.隨機存取的存儲結構可修改一專業(yè)資

料.

一word格式一范文—范例一

C.索引存取的存儲結構D.Hash存取的存儲結構

,隊列的特點是A

o37.棧的特點是B

B.先進后出A.先進先出

38.棧和隊列的共同點是C

A.都是先進后出B.都是先進先出

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

a,b.一個棧的進棧序列是39,cC

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

abcde.edcba

A.Bdecba

D.C.dceab

40.設有一個棧，元素依次進棧的順序為C

是EDBA、、C、、。下列

不可能的出棧序列。

CBECBAA.,,,D,AE,,DEA

C.D

DE,,.BBC

A

C,,B,D

41.以下?不是隊列的基本運算B

（隊列只能隊列尾插入，隊列頭刪

除）

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

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

42.若已知一個棧的進棧序列是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.一個隊列的入隊序列是1,2,3,4,則隊列的輸出序

列是B

4

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

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

4,

quC

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

環(huán)隊列

qu—>.qu->rear-A

MaxSize

1—>front—==qurear-

front==qu—〉rear

C.qu—>

1

—front

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

和隊尾元素的位置，

C

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

rear

C==A.frontrear+1

1

+==rear.Bfront==front.

0

D.front==

的帶頭結點的鏈棧中插入指針h.向一個棧頂指針為48應

s所指的結點時，

執(zhí)行操作。D

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

->hA.

next=h；

—>sC.

—>=hnext

snext=；

時，經過的棧操作為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.若棧采用順序存儲方式存儲，現兩棧共享空間、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.設計一個判別表達式中左、右括號是否配對出現的算

法，采用D

數

據結構最佳。.線性表的鏈式存儲結構A.線性表的順

序存儲結構.隊列CB

.棧D52.允許對隊列進行的操作有Do.取出最近進

隊的元素BA.對隊列中的元素排序

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

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

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

front==rear+l

循環(huán)隊列滿的標志：

front^^rear

對列空的標志：

front的數值來實現循環(huán)隊列，且當前546.若用一個

大小為rear和的值分

fronrear0和再加入兩個元素后，3,當從隊列中刪除一

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

rear-front+n)%n別為當前隊列中元素個數公式：(

1

和4c.4

525和2B1.A和.和D..隊列的55“先

進先出”特性是指D

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

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

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

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

A

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

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

情況

CD.插入操作更容易實現.刪除操作更容易實現

57其頭指針指向隊頭結點，.用不帶頭結點的單鏈表存儲

隊列，尾指針指向

C

o隊尾結點，則在進行出隊操作時

B.僅修改隊尾指針A.僅修改隊頭指針

.隊頭、隊尾指針都可能要修改CD.隊頭、隊尾指針都要

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

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

71.樹最適合用來表示Co

B.無序數據元素A.有序數據元素

.元素之間無聯系的數據.元素之間具有分支層次關系的

數據DC

個結點。C72.深度為5的二叉樹至多有

1031

32.CC..16A.B

73.對一個滿二叉樹，m個葉子，n個結點，深度為h,

則oD

1

m

nA.=h+1

—hCm2n

=+Bhm=D

2h=n—

74.任何一棵二叉樹的葉子結點在前序、中序和后序遍

歷序列中的相對次序

oA

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

對

右鏈指向的是樹結構.在線索化樹中，75每個結點必須設

置一個標志來說明它的左、標識線索，對應葉結點的左右鏈

域，應標標識樹結構信息，1信息，還是線索化信息，若0

識為—D—。

11

.BD10

.01

.A00

C.

D

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

;③二叉樹的左右子樹可任意交①只有一個結點的二叉樹的

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

④深度為的順序二叉樹的結點個數小于或等于深度相同的

滿二叉樹。K

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

77.設森林F對應的二叉樹為B,它有m個結點，B的

根為P，P的右子樹

中第一棵樹的結點的個數是FA

o,森林的結點個數為n

1

—n---.Amn

m.BD1

+nC..不能確定

0

.若一棵二叉樹具有78101個度為5的結點，2個度

為的結點，則度為

B的結點的個數是。

15

.9

.C11

.BD.不能確定A

個葉子結點的二叉樹中有10.具有79B

的結點。2個度為

11

.A.C9

.B8

.D10

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

-word格式一范文—范例一

80.在一個無向圖中，所有頂點的度數之和等于所有邊數的

C

倍。

D4

1/2BIC2

A.

同一條邊被兩端頂點計算了兩次

B

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

的出度之和的

倍。

D4

1/2B1C2

A.

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

BDCAFGE,則其，后序序列為ABCDEFG82.某二叉樹結點

的中序序列為

C

左子樹中結點數目為：

5

2

4

CA.3

.D.B

D/EB*CA83.已知一算術表達式的中綴形式為+-，后

綴形式為ABC*+

DE/其前綴形式為D

O

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

B*CD/E

A.-B+C*ABC/DE

A*BC/DE

+

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

如圖所示，若從頂點84a

;;按廣度搜索法進行遍歷，則可能得到的一種頂點序列為

—AD——種頂點序列為

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ōu)先遍歷算法先訪問所在結點，再訪

問它的鄰接點。與二叉樹的先序遍歷先訪問子樹的根結點,

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

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

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

-word格式一范文—范例一

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

的—Do

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

A

個結點的連通圖至少有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.順序查找法適合于存儲結構為的線性表。CAD

索散列存儲B順序存儲或鏈式存儲壓縮存儲

引存儲B

91.對線性表進行折半查找時，要求線性表必須。

A以順序方式存儲B以順序方式存儲，且結點按關鍵字有

序排列

以鏈式方式存儲，C以鏈式方式存儲且結點按關鍵字有D

序排列

折半查找必須是順序存儲，而且關鍵字必須是有序的

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

當折半查找值為的結點時，

C

4

.AB11

5

D

8

94.二叉樹為二叉排序樹的充分必要條件是其任一結點的值

均大于其左孩子

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

正確錯誤B

A

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

-word格式一范文—范例一

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

的根結點的值；

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

等于它的根結點的值；

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

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

A

95.下面關于B樹和B+樹的敘述中，不正確的結論是。

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

找樹和

效的支持隨機查找

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

于文件索引結構

B

96.以下說法錯誤的是。

A.散列法存儲的思想是由關鍵字值決定數據的存儲地址

B.散列表的結點中只包含數據元素自身的信息，不包含指

針。

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

飽滿程度。

D.散列表的查找效率主要取決于散列表構造時選取的散列

函數和處理沖突

的方法。

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

A.所有結點的左子樹都為空的二叉排序樹。

B.所有結點的右子樹都為空的二叉排序樹。

.平衡二叉樹。C

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

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

序列中的元素進行

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

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

99關鍵字比較的次數與記錄的初始排列次序無關的.在所

有的排序方法中，

oD

是

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

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

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

100.堆是一種有用的數據結構。下列關鍵碼序列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

.在鏈表中進行操作比在順序表中進行操作效率高。

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

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

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

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

二、填空題。

1.數據邏輯結構包括三種類圖狀結構線性結構、樹形

結構和

型，樹形結構和圖狀結構合稱。非線性結構

2.數據的邏輯結構分為、線性結構集合和圖樹形結構、

種。4狀結構

3.在線性結構中，第一個結點沒有前驅結點，其余每個

結點有且只有1個前驅結點；最后一個結點沒有后續(xù)結

點，其余每個結點有且只有1個后續(xù)結點。

4.線性結構中元素之間存在一對一關系，樹形結構中元

素之間存在一對

多對多關系，圖形結構中元素之間存在關系。多

前驅5.在樹形結構中，樹根結點沒有結點，其余每個結

點有且只有1個

結點，其余每個結點的后續(xù)結點可以后續(xù)前驅結點；葉子

結點沒有。任意多個

6.數據結構的基本存儲方法是順序、鏈式、索引和散

列存

儲。

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

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

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

間復雜度

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

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

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

輸入和輸

出。

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

素時，需向前移動一i

元素。

11.在單鏈表中，要刪除某一指定的結點，必須找到該

結點的前驅結點。

后繼結結點，另一個指向12.在雙鏈表中，每個結點有兩

個指針域，一個指向前驅

。點

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

一個數據元素，需要平均移動的個數與位置有關。

但要求以且很少進行插入和刪除操作，14.當線性表的元

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

順序最快的速度存取線性表的元素是，應采用存儲結構。

15將線性鏈表.根據線性表的鏈式存儲結構中每一個結點

包含的指針個數，

單鏈表。和雙鏈表分成

16.順序存儲結構是通過下標表示元素之間的關系的；鏈

式存儲結構是通過指針表示元素之間的關系的。

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

L->next—>

onext=L

18.后其運算遵循棧是限定僅在表尾進行插入或刪除操

作的線性表，

進先出的原則。

零?？瞻状怯梢粋€或多個空格零個字符的串，其長度

等于.空串是19

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

20.組成串的數據元素只能是單個字符。

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

的子串。

5

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

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

到8,列下標M23.二維數組個字至少需要，則存放到的

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

5108

節(jié)。

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

三元組表。

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

深3

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

-word格式一范文—范例一

度是4o

,度為2的結點的個數為n026.在一棵二叉樹中，度為

零的結點的個數為

n2,則有n0=

n2+l

o

l_o+27.在有n個結點的二叉鏈表中，空鏈域的個數

為_n

1_個結點。n個葉子結點的哈夫曼樹共有_2n—28.一棵

有3129.深度為5的二叉樹至多有個結點。

則該二叉樹個結點僅有一個孩子，2030.若某二叉樹有個

葉子結點，有30

的總結點個數為69

O

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

序序列是dgbaechf

gdbehfca列為。

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

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

33.在各種查找方法中，平均查找長度與結點個數n無關

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

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

相應的

塊表。

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

個有序序列，

構造樹的過程即為對無序序列進行排序的過程。

個頂點的無向圖，邊的總數最多為10.具有_45—o36

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

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

列為vl,其從頂點_vlv2V5V4V3V6―。

38.索引是為了加快檢索速度而引進的一種數據結構。

個索引隸屬于某個數據記錄集，它由若干索引項組成，索

引項的結構為關鍵字和關鍵字對應記錄的地址。

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

的總數不超過n

,—1

三選中的邊加入樹中不產生回路，當前選擇的邊的權值是

候選邊中最小的

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

一word格式一范文—范例一

項原則。

40.在一棵m階B樹中，除根結點外，每個結點最多有m

棵子樹，最少

棵子樹。有m/2

三、判斷題。

1.在決定選取何種存儲結構時，一般不考慮各結點的值

如何。（如

2.抽象數據類型（）包括定義和實現兩方面，其中定義是

獨立于實現ADT

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

何在計算機中實現。（

V）3.抽象數據類型與計算機內部表示和實現無關。（

4.順序存儲方式插入和刪除時效率太低，因此它不如鏈式

存儲方式好。

（X）

5.線性表采用鏈式存儲結構時，結點和結點內部的存儲空

間可以是不連續(xù)

義）的。（

.對任何數據結構鏈式存儲結構一定優(yōu)于順序存儲結構。（6

X）

X）.順序存儲方式只能用于存儲線性結構。（7

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

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

后繼。（

X）.線性表就是