2024年吉林開放大學《數(shù)據(jù)結(jié)構(gòu)》形成性考核參考試題庫（含答案）

2024年吉林開放大學《數(shù)據(jù)結(jié)構(gòu)》形成性考核參考試題庫(含

答案)

一、單選題

1.對圖從頂點a出發(fā)進行廣度優(yōu)先遍歷,則()是不可能得到的遍歷序列。

Axbcdefg

B、acdbfge

C\abdcegf

D、adcbgef

答案：D

2.棧和隊列的共同點是0。

A、都是先進先出

B、都是先進后出

C、只允許在端點處插入和刪除元素

D、沒有共同點

答案：C

3.在A0E網(wǎng)中()關鍵路徑。

Av一定只有一條

B、可能只有一條

C、不可能只有一條

D、以上答案都不對

答案：B

4.一棵樹的廣義表表示為a(b(c),de(g(h)),f,k)),則該樹的葉子結(jié)點個數(shù)為()o

A、2

B、3

C、4

D、5

答案：C

5.n個頂點的無向圖的接表最多有()個結(jié)點。

A、n2

B、n(n-1)

C\n(n+1)

D、n(n-1)/2

答案：B

6.在一棵深度為k的完全二叉樹中，所含結(jié)點個數(shù)至少()。

A、2K(2的K次方)

B、2k+1(2的K次方+1)

C、2k-1(不選C)

D、2k-1(2的K次方7)

答案：D

7.順序隊列的初始化時,需要將front和rear分別設置為()。

A、都是0

B、0和7

G都是-1

D、-1和0

答案：A

8.在C語言中,有一種適用于不同數(shù)據(jù)類型構(gòu)成的數(shù)據(jù)的結(jié)構(gòu)稱為()。

A、結(jié)構(gòu)體

B、數(shù)組

G變量

D、常量

答案：A

9.用鏈式存儲的棧,在進行出棧和入棧運算時()。

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

D、頭、尾指針可能都要修改

答案：A

10.設無向圖G中有五個頂點,各頂點的度分別為2、4、3、1、2,則G中邊數(shù)為()o

A、4

B、5

C、6

D、無法確定

答案：C

11.表示一個有100個頂點,1000條邊的非帶權(quán)有向圖的鄰接矩陣有0個大于零

矩陣元素

A、100

B、1000

C、100x100-1000

D、1000x2

答案：B

12.雙向鏈表中有兩個指針域，Iink和rink分別指向前趨及后，設p指向鏈表中

的一個結(jié)點,現(xiàn)要求刪去P所指結(jié)點,則正確的刪除是0(鏈中結(jié)點數(shù)大于2,p不

是第一個結(jié)點)O

A、p->IIink->rIink=p->IIink;p->rIink->IIink=p->rIink;free(p);

B、free(p);p->IIink->rIink=p->IIink;p->rIink->IIink=p->rlink;

C、p->lIink->rIink=p->IIink;free(p);p->rIink->IIink=p->rlink;

D、以上A,B,C都不對

答案：D

13.兩類存儲結(jié)構(gòu)為0。

A、線性結(jié)構(gòu)和非線性結(jié)構(gòu)

B、邏輯結(jié)構(gòu)和非邏輯結(jié)構(gòu)

C、順序結(jié)構(gòu)和鏈式結(jié)構(gòu)

D、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

答案：C

14.有一個結(jié)構(gòu)體及其變量定義如下:structdate{intyear;intmonth:intday;)b

irthday;此時要調(diào)用變量中的year,正確的書寫格式是()。

Axyear

B、irthday.year

C、date.year

D、struct.year

答案：B

15.循環(huán)單鏈表的主要優(yōu)點是：)o

A、不再需要頭指針了

B、已知某個結(jié)點的位置后,能夠容易找到他的直接前趨

C、在進行插入、刪除運算時，能更好的保證鏈表不斷開

D、從表中的任意結(jié)點出發(fā)都能掃描到整個鏈表

答案：D

16.圖的深度優(yōu)先遍歷類似于二叉樹的0遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是()。

A、前序，棧

B、后序,棧

C、前序,隊列

D、后序,隊列

答案：A

17.在一棵樹中，每個結(jié)點最多有()個前驅(qū)結(jié)點。

A、0

B、1

C、2

D、任意多個

答案：B

18.為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的

內(nèi)存空間時,只有當()時,才產(chǎn)生上溢

A、兩個棧的棧頂同時到達?？臻g的中心點

B、其中一個棧的棧頂?shù)竭_?？臻g的中心點

C、兩個棧的棧頂在?？臻g的某一位置相遇

D、兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底

答案：C

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

A、隨機存取

B、順序存取

C、索引存取

D、Hash存取

答案：A

20.已知單鏈表的每個結(jié)點包括一個指針域next,它指向該結(jié)點的后繼結(jié)點。在

一個單鏈表中，已知q指結(jié)點是P所指結(jié)點的直接前驅(qū)結(jié)點,若在q和P之間插入

s結(jié)點,則執(zhí)行0。

A、s->next=p->next;p->next=s;

B、p->next=s->next;s->next=p:

C、q->next=s;s->next=p;

D、p->next=s;s->next=q;

答案：C

21.無向圖G=(V.E),其中:V=[a,b,c,d,e,f)E={(a,b),(a,e),(a,c),b,e),(c,千),

(f,d)(e,d)},對該圖進行深度優(yōu)先遍歷,得到的頂點序列正確的是()。

A、,b,e,c,d,f

B、A,c,f,e,b,d

CvA,e,b,c,f,d

D、A.e,d,f,c,b

答案：D

22.對于順序存儲的棧和隊歹IJ,進行插入和刪除的算法的時間復雜度為()。

A、0⑴

B、0(n)

C、0(n2)

D、無法確定

答案：A

23.對有n個頂點、e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷,其算法

的時間復雜度是0。

A、0(n)

B、0(e)

C、0(n+e)

D、O(nXe)

答案：C

24.下圖中的樹轉(zhuǎn)換成二又樹后,B結(jié)點的孩子結(jié)點有()o

A、僅有E

B、C和D

C、E和C

D、E和F

答案：C

25.下面關于線性表的敘述中,錯誤的是()。

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

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

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

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

答案：B

26.設aI,a2,a3為三個結(jié)點;p,10,20代表地址,則如下的鏈表存儲結(jié)構(gòu)稱為()。

A、單鏈表

B、循環(huán)單鏈表

C、雙向鏈表

D、循環(huán)雙向鏈

答案：A

27.遞歸函數(shù)調(diào)用時,處理參數(shù)及返回地址,要用一種稱為()的數(shù)據(jù)結(jié)構(gòu)

A、隊列

B、多維數(shù)組

C、棧

D、線性表

答案：C

28.某順序棧sqStack,其成員包含兩部分:data[10]和top,分別代表數(shù)據(jù)和棧頂,

則表示棧中第三個數(shù)據(jù)元素的是()。

A、sqStack.data[2]

B、sqStack.data[3]

C、sqStack.data[4]

D、無法表示

答案：A

29.設深度為k的二叉樹上只有度為0和度為2的結(jié)點,則這棵樹所含的結(jié)點數(shù)至

少為()。

A、k+1

B、2k-1

C、2k

D、2k+1

答案：B

30.在下圖中，樹的深度為0

(A)

>~?、

8：(C)

④⑦QT)

(G)(H)MJCi)

A、1

B、2

C、3

D、4

答案：D

31.已知單鏈表的每個結(jié)點包括一個指針域next,它指向該結(jié)點的后繼結(jié)點。帶

頭結(jié)點的單鏈表L為空的條件是()

A、L!二NULL

B、L==NULL

C、L->next==NULL

D、L->next==L

答案：C

32.棧中元素的進出原則是()。

A、先進先出

B、后進先出

C、?？談t進

D、棧滿則出

答案：B

33.對下面的有向圖進行深度優(yōu)先遍歷得到的遍歷序列是0o

A、bcfdeg

B、abcgfde

C、abcdefg

D、abcfgde

答案：A

34.用鏈式存儲的棧,在進棧操作之前,需要()。

A、判斷棧是否滿了

B、判斷棧是否空了

C、不需判斷

D、以上答案都不對

答案：C

35.下面關于工程計劃的AOE網(wǎng)的敘述中，不正確的是()。

A、關鍵活動不按期完成就會影響整個工程的完成時間

B、任何一個關鍵活動提前完成那么整個工程將會提前完成

C、所有的關鍵活動都提前完成那么整個工程將會提前完成

D、某些關鍵活動若提前完成，那么整個工程將會提前完

答案：B

36.在一棵具有35個結(jié)點的完全二叉樹中,該樹的深度為0。

A、5

B、6

C、7

D、8

答案：B

37.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前,則下列情形不可能出現(xiàn)

的是()。

A、G中有弧

B、G中有一條從Vi到Vj的路徑

C、G中沒有弧

D、G中有一條從Vj到Vi的路徑

答案：D

38.某無向圖的鄰接矩陣如圖所示,可以看出該圖共有()個頂點。

010

1101

b0104

A、1

B、3

C、6

D、9

答案：B

39.以下說法錯誤的是()。

A、存在這樣的二叉樹,對它采用任何次序遍歷其結(jié)點訪問序列均相同

B、普通二叉樹只能用鏈式存儲結(jié)構(gòu)存儲

C、由樹轉(zhuǎn)換成二叉樹,其根結(jié)點的右子樹總是空的

D、二叉樹只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹

答案：B

40.棧通常采用的兩種存儲結(jié)構(gòu)是()。

A、順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)

B、散列方式和索引方式

C、鏈式存儲結(jié)構(gòu)和數(shù)組

D、線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)

答案：A

41.在一棵二叉樹的二叉鏈表中，空指針域等于所有非空指針域相加()。

Av-1

B、0

C、1

D、2

答案：D

42.用鄰接表存儲圖所用的空間大小()。

A、與圖的頂點數(shù)和邊數(shù)都有關

B、只與圖的邊數(shù)有關

C、只與圖的頂點數(shù)有關

D、與邊數(shù)的平方有關

答案：A

43.后綴表達式“45*32+-”的值為()。

A、21

B、17

C、15

D、5

答案：C

44.在長度為n的順序表中第i(1WiWn)個位置上插入一個元素時,為留出插入

位置所需移動元素的次數(shù)為()。

A、n-i

B、i

C\n-i+1

D、n-i-1

答案：C

45.表示一個有100個頂點,1000條邊的無向圖的鄰接矩陣有()個非零矩陣元素。

A、100

B、1000

C、9000

D、1000x2

答案：D

46.某圖的鄰接矩陣如圖所示,若G為無向圖,則G中共有()條邊。

010

1101

b0104

A、1

B、2

C、3

D、4

答案：B

47.最大容量為maxsize的循環(huán)隊列，隊尾指針是rear,隊頭是front,初始時均為

0且采用損失一個空間的原則,則隊滿條件為()。

A、(rear+1)%maxsize==(front+1)%maxsize

B、(front+1)%maxsize-rear

C\(rear+1)%maxsize-front

D、rear==front

答案：C

48.設有13個值,用它們組成一棵赫夫曼樹,則該赫夫曼樹共有0個結(jié)點。

A、12

B、13

C、25

D、26

答案：C

49.用鏈式存儲的棧,在出棧操作之前,需要()o

A、判斷棧是否滿了

B、判斷棧是否空了

C、不需判斷

D、以上答案都不對

答案：B

50.用鏈表表示線性表的優(yōu)點是()。

A、便于隨機存取

B、占用的存儲空間較順序表少

C、便于進行插入和刪除操作

D、元素的物理順序與邏輯順序相同

答案：C

51.對于順序循環(huán)隊列，以下說法正確的是()。

A、無法判斷隊列是否為空

B、無法判斷隊列是否為滿

C、隊列不可能滿

D、以上說法都不對

答案：D

52.分析以下程序段,其時間復雜度為T()二()。

1=1；

While(i<=n)

l="3*i;<">

A、0(n)

B、0(n2)

C、0(n3)

Dx0(log3n)

答案：D

53.靜態(tài)鏈表與動態(tài)鏈表相比，其缺點是()。

A、插入刪除時需要移動較多數(shù)據(jù)

B、有可能浪費較多空間

C、不能隨機存取

D、以上都不對

答案：B

54.如下圖說是的二叉樹按中序線索化,則結(jié)點X的右指針和Y的左指針分別指向

()結(jié)點。

C、D,A

D、C,A

答案：C

55.若已知一個棧的進棧序列是1,2,3....n,其輸出序列為p1,p2,p3,,pn,若p1

=3,則p2為0。

A、一定是2

B\可能是2

C、可能是1

D、一定是1

答案：B

56.數(shù)據(jù)元素之間存在一對多的關系,這種數(shù)據(jù)間的結(jié)構(gòu)屬于0。

A、集合

B、線性結(jié)構(gòu)

C、樹型結(jié)構(gòu)

D、圖型結(jié)構(gòu)

答案：C

57.在實現(xiàn)某個系統(tǒng)中成員之間的隸屬關系時,可以采用()存儲結(jié)構(gòu)

A、線性表

B、棧

C、隊列

D、樹

答案：D

58.一個容量為15的循環(huán)隊列中，隊尾指針是rear,隊頭是front,初始時均為0.

且采用損失一個空間的原則。若頭指front=5,尾指針rear=9,則該循環(huán)隊列中共

有()個元素。

A、5

B、9

C、4

D、14

答案：C

59.一棵有124個葉結(jié)點的完全二又樹,最多有0個結(jié)點。

A、124

B、247

C、248

D、無法確定

答案：C

60.設森林F對應的二叉樹有m個結(jié)點,二叉樹的根節(jié)點的右子樹上結(jié)點個數(shù)為n.

則森林F中第一個樹的結(jié)點個數(shù)為()。

A、m-n

B、m-n-1

C、m-n+1

D、無法確定

答案：A

61.當定義一個結(jié)構(gòu)體變量時,系統(tǒng)為它分配的內(nèi)存空間是()o

A、結(jié)構(gòu)體中一個成員所需的內(nèi)存容量

B、結(jié)構(gòu)體中第一個成員所需的內(nèi)存容量

C、結(jié)構(gòu)體中占內(nèi)存容量最大者所需的容量

D、結(jié)構(gòu)體中各成員所需內(nèi)存容量之和

答案：D

62.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成()o

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)

答案:C

63,由3個結(jié)點所構(gòu)成的二又樹有()種形態(tài)。

A、1

B、3

C、5

D、7

答案：C

64.分析以下程序段,其時間復雜度為T()二()

X=0;

For(i=1;i<n;i++);

For(j=1;j<n;j++);

For(k=1;k<n;k++);

x++;

A、0(n)

B、0(n2)

Cv0(n3)

D、0(1)

答案：A

65.一個棧的入棧序列是A,B,C,D,E,則棧的不可能的輸出序列是()。

A、EDCBA

B、DECBA

CvDCEAB

D、ABODE

答案：C

66.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[].top口代表第i個棧(i=1.2)

棧頂，棧1的底在V[0],棧2的底在V[m~lV則棧滿的條件是()。

A、top[2]-top[1]=0

B、top[1]+1=top[2]

C、top[1]+top[2]=m

D\top[1]=top[2]

答案：B

67.計算機算法指的是解決問題的有限運算序列,它必具備輸入、輸出和()等五個

特性。

A、可行性、可移植性和可擴充性

B、可行性、確定性和有窮性

C、確定性、有窮性和穩(wěn)定性

D、易讀性、穩(wěn)定性和安全性

答案：B

68.已知單鏈表的每個結(jié)點包括一個指針域next,它指向該結(jié)點的后繼結(jié)點。若

已建立如圖所示的單向鏈表,則以下不能將s所指的結(jié)點插入到鏈表尾部,構(gòu)成

新的單向鏈表的語句組是0。

A、s->next=a->next->next;a->next->next=s;

B、a=a->next;a->next=s;s->next=NULL;

C、s->next=NULL;a=a->next;a->next=s

D、a=a->next:s->next=a->next:a->next=s>next:

答案：D

69.設棧S和隊列Q的初始狀態(tài)為空,元素1,e2,e3,e4,e5和e6依次通過棧S.一

個元素出棧后即進隊列Q若6個元素出隊的序列是e2,e4,e3,e6,e5,e1則棧S

的容量至少應該是0。

A、6

B、4

C、3

D、2

答案：C

70.下面關于無向連通圖特性的敘述中，正確的是()。

①所有頂點的度之和為偶數(shù)

②邊數(shù)大于頂點個數(shù)減1

③至少有一個頂點度為1

A、①

B、②

C、①和②

D、①和③

答案：A

71.一顆非空二叉樹其前序遍歷序列與后序遍歷序列正好相反,則該二叉樹一定

滿足()。

A、所有結(jié)點均無左孩了結(jié)點

B、所有結(jié)點均無右孩子結(jié)點

C、只有一個葉結(jié)點

D、是任意一棵二又樹

答案：C

72.若鄰接表中有奇數(shù)個邊結(jié)點,則一定是()。

A、圖中有奇數(shù)個頂點

B、圖中有偶數(shù)個頂點

C、圖為無向圖

D、圖為有向圖

答案：D

73.設計一個判別表達式中左,右括號是否配對出現(xiàn)的算法,采用()數(shù)據(jù)結(jié)構(gòu)最佳。

A、線性表的順序存儲結(jié)構(gòu)

B、隊列

C、線性表的鏈式存儲結(jié)構(gòu)

D、棧

答案：D

74.一個遞歸算法必須包括()。

A、遞歸部分

B、終止條件

C、終止條件和遞歸部分

D、以上答案都不對

答案：C

75.用不帶頭結(jié)點的單鏈表存儲隊列時,其隊頭指針指向隊頭結(jié)點,其隊尾指針指

向隊尾結(jié)點,則在進行插入(入隊)操作時()。

A、僅修改隊頭指針

B、僅修改隊尾指針

C、隊頭、隊尾指針都要修改

D、隊頭和隊尾指針都可能要修改

答案：D

76.最小生成樹指的是()。

A、由連通圖所得到的邊數(shù)最少的生成樹

B、由連通圖所得到的頂點數(shù)相對較少的生成樹

C、連通圖中所有生成樹中權(quán)值之和為最小的生成樹

D、連通圖的極小連通子圖

答案：C

77.n個頂點的強連通圖,若該連通圖含有最少的邊,其形狀是()。

A、無回路

B、有多個回路

C、環(huán)狀

D、無法確定

答案：C

78.設一棵二叉樹中有3個葉子結(jié)點,有8個度為1的結(jié)點,則該二叉樹中總的結(jié)

點數(shù)是0

A、11

B、12

C、13

D、無法確定

答案：C

79.以下說法正確的是()。

A、若一個樹葉是某二叉樹的前序遍歷序列中的最后一個結(jié)點,則它必是該二又樹

的后序遍歷序列中的最后一個結(jié)點。

B、若一個樹葉是某二叉樹的前序遍歷序列中的最后一個結(jié)點,則它必是該二叉樹

的中序遍歷序列中的最后一個結(jié)點。

C、若二叉樹中,有兩個孩子結(jié)點的雙親結(jié)點在中序遍歷序列中，它的后繼結(jié)點中

必然有一個孩子結(jié)點。

D、若二叉樹中,有一個孩子結(jié)點的雙親結(jié)點在中序遍歷序列中，它的后繼結(jié)點中

沒有該孩子結(jié)點。

答案：C

80.已知某二叉樹的前序遍歷序列是ABDEFGC,中序序列是DEBGFAC,則對應的二

叉樹為()。

A、圖A

B、圖B

C、圖C

D、圖D

答案：B

81.判定一個非循環(huán)的順序隊列Q(最多元素為M)為滿隊列的條件是()o

A、Q->rear-Q->front==M

B、Q->rear-Q->front-1==M

C、Q->front==Q->rear

D、Q->rear==M-1

答案：D

82.已知二又樹的后序遍歷序列是dabe

C,中序序列是deba

C,則它的前序遍歷是()。

A、cedba

B、acbed

C、decab

Dxeabc

答案：A

83.以下說法不正確的是0。

A、無向圖中的極大連通子圖稱為連通分量

B、圖的廣度優(yōu)先遍歷中一般要采用隊列來暫存剛訪問過的頂點

C、圖的深度優(yōu)先遍歷中一般要采用棧來暫存剛訪問過的頂點

D、有向圖的遍歷不可采用廣度優(yōu)先遍歷方法

答案：D

84.已知一棵度為3的樹有2個度為1的結(jié)點,3個度為2的結(jié)點,4個度為3的結(jié)

點。則該樹中有()個葉子結(jié)點。

A、8

B、10

C、12

D、14

答案：C

E

85.如圖所示,該二又樹的前序遍歷序列是()

A、EGFACDB

B、EAGCFBD

C、EACBDGF

D、EGACDFB

答案：C

86.在下圖中，F(xiàn)結(jié)點的兄弟結(jié)點是()o

B、D

C、I

D、空

答案：D

87.下列命題正確的是()。

A、一個圖的鄰接矩陣表示是唯一的,鄰接表表示也唯一

B、一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一

C、一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一

D、一個圖的鄰接矩陣表示不唯一的,鄰接表表示也不唯一

答案：B

88.一維數(shù)組與線性表的區(qū)別是()。

A、前者長度固定，后者長度可變

B、兩者長度均固定

C、后者長度固定，前者長度可變

答案：A

解析：D兩者長度均可變

89.設T是赫夫曼樹,具有5個葉結(jié)點,樹T的高度最高可以是()。

A、2

B、3

C、4

D、5

答案：D

90.一棵完全二又樹按層次遍歷的序列為ABCDEFGHI則在前序遍歷中結(jié)點E的直

接前驅(qū)為結(jié)點()。

A、D

B、F

C、H

D、I

答案：D

91.對于任何一棵二又樹,如果其終端結(jié)點數(shù)為no,度為2的結(jié)點數(shù)為n2,則no=

Oo

A、n2-1

B、n2+1

C、n2

D、n2-2

答案：B

92.有結(jié)構(gòu)體定義及結(jié)構(gòu)體類型數(shù)組如下：structworkIist{intno;charname120];

charsex[person[5];需要給結(jié)構(gòu)體數(shù)組中第2個變量的no成員賦值為5,正確

的寫法是0。

A、no=5;

B、person.no=5:

C、person[2].no=5;

Dxperson[1].no=5.

答案：D

93.任何一棵二又樹的葉結(jié)點在前序、中序和后序遍歷序列中的相對次序()。

A、不發(fā)生變化

B、發(fā)生變化

C、某些樹中發(fā)生變化,某些樹中不發(fā)生變化

D、沒有規(guī)律,無法確定

答案：A

94.算法分析的目的是分析算法的效率以求改進,算法分析的兩個主要方面是()o

A、空間復雜性和時間復雜性

B、正確性和簡明性

C、可讀性和文檔性

D、數(shù)據(jù)復雜性和程序復雜性

答案：A

95.在一棵二又樹上第5層的結(jié)點數(shù)最多為()。

A、8

B、15

C、16

D、32

答案：C

96.一個圖中包含k個連通分量,若按深度優(yōu)先遍歷方法訪問多有頂點，則必須調(diào)

用()次深度優(yōu)先遍歷算法。

A、1

B、k-1

C、k

D、k+1

答案：C

97.已知單鏈表的每個結(jié)點包括一個指針域next,它指向該結(jié)點的后繼結(jié)點?，F(xiàn)

要將指針指向的新結(jié)點插入到指針P指向的結(jié)點之后,下面的操作序列中正確的

是()。

A、q=p->next;p->next=q->next:

B、p->next=q->next:q=p->next:

C、q->next=p->next;p->next=q:

D、p->next=q;q->next=p->next;

答案：C

98.在下圖中，J結(jié)點是0o

('—A,)

B：?

/r\\\

乂乂X

'：0>[f)(?)

rY\r

(S(M)(l)Qj

A、葉節(jié)點

B、根結(jié)點但不是分支結(jié)點

C、根結(jié)點也是分支結(jié)點

D、分支結(jié)點但不是根結(jié)點

答案：A

99.線性表是()。

A、一個有限序列，可以為空

B、一個有限序列，不可以為空

C、一個無限序列，可以為空

D、一個無限序列，不可以為空

答案：A

100.若長度為n的線性表采用順序存儲結(jié)構(gòu),訪問其第i個元素的算法時間復雜

度為0

A、0(1)

B、0(n)

C、0(n2)

D、0(log2n)

答案：A

101.在進棧運算時,應先判別棧是否①,在出棧運算時.應先判別棧是否②,①②

處應該是0。

A、空,滿

B、滿，空

C、滿,上溢

D、空，下溢

答案：B

102.下面關于圖的敘述中，正確的是0。

A、強連通有向圖的任何頂點到所有其他頂點都有弧

B、任意圖頂點的入度都等于出度

C、有向完全圖一定是強連通有向圖

D、有向圖邊集的子集和頂點集的子集可構(gòu)成原有向圖的子集

答案：C

103.當順序棧中元素為n個,進棧運算時發(fā)生上溢，則說明該棧的最大容量為()。

A、n-1

B、n

C\n+1

D、n/2

答案：B

104.圖的廣度優(yōu)先遍歷類似于二叉樹的()遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是()。

A、前序，棧

B、層次，棧

C、前序,隊列

D、層次,隊列

答案：D

105.該二叉樹對應的森林有()棵樹。

B、2

C、3

D、4

答案：D

106.一棵完全二又樹按層次遍歷的序列為ABCDEFGHI,后序遍歷中結(jié)點B的直接

后繼是結(jié)點()。

A、D

B、F

C、H

D、I

答案：B

107,若長度為n的線性表采用鏈式存儲結(jié)構(gòu),訪問其第i個元素的算法時間復雜

度為()。

A、0(1)

B、0(n)

C、0(n2)

D、0(log2n)

答案：B

108.G是一個簡單的非連通無向圖,共有28條邊,則該圖至少有()個頂點。

A、6

B、7

C、8

D、9

答案：D

109,雙向鏈表中有兩個指針域.Iink和rink分別指向前趨及后繼,設p指向鏈表

中的一個結(jié)點,在p的結(jié)點前插入一個指針g指向的結(jié)點操作是0O

A、p->IIink=q;q->rIink=p;p->IIink->rIink=q;q->IIink=q;

B、p->IIink=q;p->IIink->rIink=q;q->rIink=p;q->IIink=p->IIink:

C\q->rIink=p;q->IIink=p->IIink;p->IIink->rIink=q;p->IIink=q;

D、q->IIink=p->IIink;q->rIink=p;p->IIink=q;p->IIink->rIink=q;

答案：C

110.若已知一個棧的入棧序列是1,2,3..n,其輸出序列為p1,p2rp3....pn,

若pkn,貝ljpi為0。

A、i

B、n-i

C\n-i+1

D、不確定

答案：C

111.以下鏈表結(jié)構(gòu)中,從當前結(jié)點出發(fā)能夠訪問到任一結(jié)點的是()。

A、單向鏈表和雙向鏈表

B、雙向鏈表和循環(huán)鏈表

C、單向鏈表和循環(huán)鏈表

D、單向鏈表、雙向鏈表和循環(huán)鏈表

答案：B

112.線性表L=(a1,a2,....an),下列說法正確的是()。

A、每個元素都有一個直接前驅(qū)和一個直接后繼

B、線性表中至少有一個元素

C、表中所有元素的排列順序是由小到大或者由大到小

D、除了第一個元素和最后一個元素外,其余每個元素都有一個直接前驅(qū)和一個直

接后繼

答案：D

113.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列,且當前rear和front的值分別為

0和3,當從隊列中刪除一個元素,再加入兩個元素后,rear和front的值分別為

Oo

A、1和5

B、2和4

C、4和2

D、5和1

答案：B

114.設一個鏈表最常用的操作是在末尾插入結(jié)點,則選用()最節(jié)省時間。

A、單鏈表

B、單循環(huán)鏈表

C、帶尾指針的單循環(huán)鏈表

D、帶頭結(jié)點的雙循環(huán)鏈表

答案：C

115.在解決計算機主機與打EU機之間速度不匹配問題時,通常設置個打印機數(shù)據(jù)

緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)打印機則從該緩沖區(qū)中取出數(shù)據(jù)

打印。該緩沖區(qū)應該是一個0結(jié)構(gòu)。

A、棧

B、隊列

C、樹

D、線性表

答案：B

116.含門個頂點的連通圖中的任意一條簡單路徑,其長度不可能超過0。

A、1

B、n/2

C、n-1

D\n

答案：C

117.已知鏈表的每個結(jié)點包括一個指針域next,它指向該結(jié)點的后繼結(jié)點。非空

的循環(huán)單鏈表head的尾結(jié)針p滿足()。

A、p->next=head

B、p->next=NULL

C、p二NULL

D、p=head

答案：A

118.某圖的鄰接矩陣如圖所示,若G為有向圖，則G中共有0條弧。

010

1101

)0104

A、1

B、2

C、3

D、4

答案：D

119.設有一順序棧已含3個元素,如下圖所示,元素a4正等待進棧。那么下列4

個序列中不可能出現(xiàn)的出棧序列是()。

012)auiirl

Ttop

Ax3,a1,a4,a2

B、a3,a2,a4,a1

Cva3,a4,a2,a1

D、a4,a3,a2,a1

答案：A

120.用一維數(shù)組存放的一棵完全二叉樹如下圖所示，則后序遍歷該二叉樹時產(chǎn)生

的結(jié)點序列中結(jié)點B后面的結(jié)點是()。

123456789101112

ABCDEFCHIJKL

A、L

B、F

C、

D、A

答案：A

121.順序棧包含兩部分,數(shù)組data[10]和棧頂top,當top值為()表示棧空。

A、0

B、10

C、9

D、-1

答案：D

122.一棵二又樹前序遍歷序列是ABDGCFK,中序序列是DGBAFCK,則它的后序遍歷

序列是()。

A、CFKDBG

B、GDBFKCA

C、KCFAGDB

D、ABCDFKG

答案：B

123.設無向圖G中頂點數(shù)為n,則圖G至多有()條邊。

A、0

B、n

C、n(n-1)/2

D、n(n-1)

答案：C

124.分析以下程序段,其時間復雜度為T()二()o

For(i=0;i<n;i++)

For(j=0;j<i;j++)

A[i][j]=O;

A、0(n)

B、0(n2)

C、0(n3)

D、0⑴

答案：B

125.最大容量為n的循環(huán)隊列,隊尾指針是rear,隊頭指針是front,初始時均為

0,采用損失一個空間的原則,則隊空的條件是()。

Av(rear+1)%n==front

B、rear==front

C、rear+1==front

D、(rear-1)%n==front

答案：B

126.在下圖中，A結(jié)點是()。

(A)

B、根結(jié)點但不是分支結(jié)點

C、根結(jié)點也是分支結(jié)點

D、分支結(jié)點但不是根結(jié)點

答案：C

127.在n個結(jié)點的線索二叉樹中,可用于線索的指針域數(shù)目為()。

A、n-1

B、n

C\n+1

D、2n

答案：C

128.一棵樹的廣義表表示為a(b(c),d(e(g(h)),f,k)),則該樹的高度為()

A、3

B、4

C、5

D、6

答案：C

129?隊列的“先進先出”特性是指()。

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

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

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

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

答案：D

130.鏈棧與順序棧相比,有一個比較明顯的優(yōu)點()。

A、插入操作更方便

B、刪除操作更方便

C、通常不會出現(xiàn)棧滿的情況

D、不會出現(xiàn)棧空的情況

答案：C

131.若用單鏈表來表示隊列,則應該選用()。

A、帶尾指針的非循環(huán)鏈表

B、帶尾指針的循環(huán)鏈表

C、帶頭指針的非循環(huán)鏈表

D、帶頭指針的循環(huán)鏈表

答案：B

132.一棵深度為6的滿二又樹一共有個()結(jié)點。

A、31

B、32

C、63

D、64

答案：C

133.有一份電文中共使用5個字符:a、b、c、d、e,它們的出現(xiàn)頻率依次為4、7、

5、2、9,對應的赫夫曼樹中字符a的赫夫曼編碼長度為()。

A、1

B、2

C、3

D、4

答案：C

134.已知單鏈表的每個結(jié)點包括一個指針域next,它指向該結(jié)點的后繼結(jié)點。假

定己建立以下動態(tài)鏈表結(jié)構(gòu)，且指針pl和P2已指向如圖所示的結(jié)點:則以下可以

將P2所指結(jié)點從鏈表中刪除并釋放該結(jié)點的語句組是()。

numnext

A、pI->next=:p2->next;free'pI);

B、pl=p2;free(p2);

C、pI->next=p2->next;free:p2);

D、pI=p2->next;free(p2);

答案：C

135.下面關于圖的敘述中，正確的是()。

A、圖與樹的區(qū)別在于圖的邊數(shù)大于頂點數(shù)

B、假設有圖G二(V,

C、，頂點集V'V,E'E則V'和E'構(gòu)成G的子圖

D、無向圖的連通分量指無向圖中的極大連通子圖

E、圖的遍歷就是從圖中某個頂點出發(fā)訪問圖中的其余頂點。

答案:C

136.某順序棧saStack,其成員包含兩部分:data[10]和top,分別代表數(shù)據(jù)和棧

頂,初始時top值為7,則表示棧頂數(shù)據(jù)元素的是()。

A、sqStack.data[9]

B、sqStack.top

C、sqStack.data[sqStack.top]

D、sqStack.top+1

答案：C

137.數(shù)組Q[n]用來表示一個循環(huán)隊列,為當前隊列頭元素的前一位置,r為隊尾

元素的位置,假定隊列中元素的個數(shù)小于n,計算隊列中元素的公式為()。

A、r-f

B、(n+f-r)%n

C、n+r-f

D、(n+r-f)%n

答案：D

138.已知鏈表的每個結(jié)點包括一個指針域next它指向該結(jié)點的后繼結(jié)點。在頭

指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結(jié)點,若p->nex

t->next=head,則0。

A、p指向頭結(jié)點

B、p指向尾結(jié)點

C、米p的直接后繼是頭結(jié)點

D、米p的直接后繼是尾結(jié)點

答案：D

判斷題

1.已知二叉樹的前序遍歷序列和后序遍歷序列并不能唯一地確定這棵樹,因為不

知道樹的根結(jié)點是哪一個。

Ax正確

B、錯誤

答案：B

2.棧和隊列都是線性表,只是在插入和刪除時受到了一些限制。

A、正確

B、錯誤

答案：A

3.求最小生成樹的Prim算法在邊較少且頂點較多時效率高。

A、正確

B、錯誤

答案：B

4.完全二叉樹的某結(jié)點若無左孩子，則必是葉結(jié)點。

A、正確

B、錯誤

答案：A

5.線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特

性,因此是屬于同一數(shù)據(jù)對象。

A、正確

B、錯誤

答案：A

6.棧和隊列的存儲方式既可是順序,也可是鏈式。

A、正確

B、錯誤

答案：A

7.線性表的邏輯順序與存儲順序總是一致的。

A、正確

B、錯誤

答案：B

8.無向圖的鄰接矩陣一定對稱,有向圖的鄰接矩陣一定不對稱。