2023年數(shù)據(jù)結(jié)構(gòu)考試試卷(含五卷)

2023年數(shù)據(jù)結(jié)構(gòu)考試試卷(一)

一、單項(xiàng)選擇題(共50題，每小題2分，共100分)

1、若從無(wú)向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪問(wèn)圖中所有的

頂點(diǎn)，則該圖一定是(：)圖

A、非連通

B、連通

C、強(qiáng)連通

D、有向

2、設(shè)有序表為{9,12,21,32,41,45,52},當(dāng)二分查找值為52的結(jié)點(diǎn)時(shí)，元素

之間的比較次數(shù)是(C)。

A、1

13、2

C、3

D、4

3、關(guān)于順序表的說(shuō)法不正確的是？

A、邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰

B、可以隨機(jī)存取表中任一元素，方便快捷

C、在線性表中插入某一元素時(shí)，往往需要移動(dòng)大量元素

D、在線性表中刪除某一元素時(shí)，無(wú)需移動(dòng)大量元素

4、下列程序的空間復(fù)雜度是()。

For(i=l;i〈=n;++i){for(j=l;j<=m;++j){}}

A、0(m*n)

0(m+n)

C^O(m-n)

O(m/n)

5、樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加()。

A、0

B、1

C^-1

D、2

6、以下排序方法中，()不需要進(jìn)行關(guān)鍵字的比較。

A、快速排序

B、歸并排序

C、基數(shù)排序

D、堆排序

7、順序查找法適合于存儲(chǔ)結(jié)構(gòu)為()的線性表

A、散列存儲(chǔ)

B、順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)

c、壓縮存儲(chǔ),

D、索引存儲(chǔ)

8、如果按關(guān)鍵碼值遞增的順序依次將99個(gè)關(guān)鍵碼值插入到二叉排序樹(shù)中，則對(duì)

這樣的二又排序樹(shù)檢索時(shí),在等概率情況下:查找成功時(shí)的平均查找長(zhǎng)度ASL為

A、50

B、48

C、45

D、47I"；""：""；"；"；"

9、下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)

A、可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示

B、插入運(yùn)算方便

C、刪除運(yùn)算方便

D、存儲(chǔ)密度大

10、設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn),則在二叉排序樹(shù)上查找結(jié)點(diǎn)的最多的時(shí)間復(fù)雜

度()

A、0(n)

B、O(n^2)

C^O(nlog2n)

D、O(log2n)

1k已知一個(gè)有序表為(11,22,33,44,55,66,77,88,99),則折半查

找55需要比較()次。(1分)

A、1

B、2

C、3

D、4

12、使用二叉線索樹(shù)的目的是便于(D)。

A、二叉樹(shù)中結(jié)點(diǎn)的插入與刪除

B、在二叉樹(shù)中查找雙親

c、確定二叉樹(shù)的高度二;;??；

D、查找-一個(gè)結(jié)點(diǎn)的前趨和后繼

13、(4分)從一個(gè)棧頂指針為HS的鏈棧中刪除一人結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的

值,則執(zhí)行(D)。

A、x=HS;HS=HS->next;

B、x=HS->data;

C>HS=HS->next;x=HS->data;

D、x=HS->data;HS=HS->next;

14、一維數(shù)組與線性表的區(qū)別是()

A、前者長(zhǎng)度固定，后者長(zhǎng)度可變

B、兩者長(zhǎng)度均固定

C、后者長(zhǎng)度固定，前者長(zhǎng)度可變

D、兩者長(zhǎng)度均可變

15、(3分)在具有n個(gè)頂點(diǎn)的無(wú)向完全圖G中邊的總數(shù)為(B)。

A^ii+l

B、n(-l)/2

C、n(n+l)

D、n-1

16、(4分)設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head,指針變量P指向尾結(jié)點(diǎn)的

條件是⑻。

A、p->next->next=-head

B、p->next-head

C^p->next->next-NULL

D、p->next==NULL

17、下列關(guān)于線性鏈表的敘述中，正確的是()。

A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須

一致

B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須

連續(xù)B/Q

C、進(jìn)行插入與刪除時(shí)?，不需要移動(dòng)表中的元素

D、以上說(shuō)法均不正確

18、算法分析的兩個(gè)主要方面是("(5.0分)

A、正確性和簡(jiǎn)明性

B、可讀性和正確性,ll；；；

C、穩(wěn)定性和健壯性

D、時(shí)間復(fù)雜度和空間復(fù)雜度

19、在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)

A、左子結(jié)點(diǎn)

B、右子結(jié)點(diǎn)

C、左子結(jié)點(diǎn)和右子結(jié)點(diǎn)

D、左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)

20、對(duì)表長(zhǎng)為n的有序順序表進(jìn)行折半查找,其判定樹(shù)的高度為()

A、log2(n+1)

B、lug2(u+D-1

C^log2n

D、log2(n-l)

21、若采用鄰接矩陣A存儲(chǔ)有向圖G,則結(jié)點(diǎn)k的入度等于A中。

A、結(jié)點(diǎn)k對(duì)應(yīng)行元素之和

B、：結(jié)點(diǎn)k對(duì)應(yīng)列元素之和

C、結(jié)點(diǎn)k對(duì)應(yīng)行和列元素之和

D、非零元素之和

22、有一個(gè)關(guān)鍵字序列,采用依次插入方法建立一棵二叉排序樹(shù),該二叉排序樹(shù)

的形狀取決于0

A、該序列的存儲(chǔ)結(jié)構(gòu)

B、序列中的關(guān)鍵字的取值范圍

C、關(guān)鍵字的輸入次序

D、使用的計(jì)算機(jī)的軟、硬件條件

23、根據(jù)初始關(guān)鍵字序列（19,22,01,38,10）建立的二叉排序樹(shù)的高度為（）。

A、2"工：

B、3

C、4

D、5

24、在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修

改指針的操作是（）。

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

B、p->ncxt=q;p->next->prior=q;q->prior=p;q->next=p->ncxt;

C、q->prior=p;q->ncxt=p->noxt;p->noxt->prior=q;p->noxt=q;

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

25、對(duì)有n個(gè)數(shù)的數(shù)列進(jìn)行冒泡排序,至少應(yīng)該交換（）次？

A、0

B、n/2

C、n

D、2u

26、給定排序碼值序列為｛F,B,J,C,E,A,I,D,C,H],對(duì)其按字母的字

典序列的次序進(jìn)行排列，冒泡排序（大數(shù)下沉）的第一趟排序結(jié)果應(yīng)為

A、｛B,F,C,J,A,E,D,I,C,H｝

B、｛C,B,D,A,E,F,T,C,J,H｝

C、｛B,F,C,E,A,I,D,C,H,J｝

D、{A,B,D,C,E,F,I,J,C,H}

27、算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱(chēng)為算法的（）。

A、正確性

B、易讀性

C、健壯性

D、高效性

28、下列敘述中正確的是（）。

A、在循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長(zhǎng)度

B、在循環(huán)隊(duì)列中，隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長(zhǎng)度

C、在帶鏈的隊(duì)列中，隊(duì)頭指針與隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長(zhǎng)度

D、在帶鏈的棧中，棧頂指針的動(dòng)態(tài)變化決定棧中元素的個(gè)數(shù)

29、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素。2,P4.P5和依

次通過(guò)棧S,一個(gè)元素出棧后即進(jìn)隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是e2,

e4,e3,e6,e5,el則棧S的容量至少應(yīng)該是（）

A、6

C、3I"；"；［"；"；"；：】

D、2

30、已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語(yǔ)句是

A^p=p->next

B、p二null

C、p->next=null

D^p->next=p->next->next

31、（3分）線性表適合丁順序查找的存儲(chǔ)結(jié)構(gòu)是（C）。

A、索引存儲(chǔ)

B、壓縮存儲(chǔ)

C、順序存儲(chǔ)

D、散列存儲(chǔ)

32、在下列存儲(chǔ)形式中，（）不是樹(shù)的存儲(chǔ)形式?

A^雙親表示法

B、孩子鏈表表示法

C、孩子兄弟表示法

D、順序存儲(chǔ)表示法

33、順序棧是空棧的條件是（）。

A、top==0

B、top==l

C、top--1

D、top-m

34、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。（5.0分）

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

R、線性結(jié)構(gòu)和樹(shù)形結(jié)構(gòu)

C、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu),

35、在一棵二叉樹(shù)上第5層的結(jié)點(diǎn)數(shù)最多為（）

A、8

B、15

C、16

D、32

36、用鄰接表存儲(chǔ)圖所用的空間大?。ǎ?/p>

A、與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)

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

C、只與圖的頂點(diǎn)數(shù)有關(guān)

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

37、深度為h的滿m叉樹(shù)的第k層有（）個(gè)結(jié)點(diǎn)。（IWkWH）

A、mk-1

B、mk-1

C、mh-l

D、mh-l

38、一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=5,尾指針rear=9,則

該循環(huán)隊(duì)列中共有（）個(gè)元素。

A、5

B、9

C、4

D、14

39、設(shè)某散列表的長(zhǎng)度為100,散列函數(shù)H（k）=k%P,則P通常情況下最好選

擇（）。

A、99V/.

B、97:"二

91.:???<?<-

I）、93

40、在以下的敘述中，正確的是（）。

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

B、線性表的順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況

C、線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況

D、線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)

41、一個(gè)棧的入棧序列是A,B,C,D,E,則棧的不可能的輸出序列是（）

A、EDCBA

B、DECBA

C、DCEAB

D、ABCDE

42、已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。

現(xiàn)要將指針M指向的新結(jié)點(diǎn)插入到指針P指向的結(jié)點(diǎn)之后，下面的操作序列

中正確的是（）

A、q=p->next;

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

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

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

43、一個(gè)隊(duì)列的入隊(duì)序列是a,b,c,d,則隊(duì)列輸已序列是

A、d,c,b,a

B、a,b,c,d

Ca,d,c,b

D、c,b,cl,a

44、一棵深度為6的滿二叉樹(shù)一共有個(gè)()結(jié)點(diǎn)

A、31

B、32

C、63V/.

D、64

45、數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)科是針對(duì)什么問(wèn)題而產(chǎn)生的？

A、針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題

B、針對(duì)數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題

C、數(shù)值計(jì)算與非數(shù)值計(jì)算的問(wèn)題都針對(duì)

D、兩者都不針對(duì)

46、設(shè)一組權(quán)值集合收⑵3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫夏樹(shù)中帶權(quán)路

徑長(zhǎng)度之和為()。

A、20

B、30

C、40

D、45

47、(4分)在一個(gè)單鏈表中，若刪除p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn),則執(zhí)行的操作為

(A)o

A、q=p->ncxl;p->iicxl=p->iiuxl->iicxI;free(q)

B>p=p->next;q=p->next;p=q->next;fe(e)

C、q=p->next->next;p=p->next;free(q)

Dsp=p->next->next;q=p->next;feeq)

48、算法的計(jì)算量大小稱(chēng)為算法的()。

A、現(xiàn)實(shí)性

B、難度

C、時(shí)間復(fù)雜性

D、效率

49、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖,在其對(duì)應(yīng)的鄰接表中,

所含邊結(jié)點(diǎn)分別()個(gè)。

A、ee+1

B、e2e

C、2e2e+l

D、e2e-l

50、若串S="software”，其子串的數(shù)目是()。

A、8

R、37

C、36

D、9

參考答案

一、單項(xiàng)選擇題

1、B

2、C

3、D

4、A

5、C

6、C

7、B

8、A

9、D

10、A

11、A

12、D

13、D

14、A

15、B

16、B

17、C

18、D

19、C

20、A

21、B

22、C

23、B

24、C

25、A

26、C

27、A

28、A

29、C

30、D

31、C

32、D

【解析】解釋?zhuān)簶?shù)的存儲(chǔ)結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表

示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹(shù)都能通過(guò)孩子兄弟表

示法轉(zhuǎn)換為二叉樹(shù)進(jìn)行存儲(chǔ)。

33、AV/上

34、A.....二

36、A

37、A

38、C

39、B

40、C

41、CI"；""："["；"；"；

42、C

43、B

44、C

45、A

46、D

47、A

48、C

49、B

50、B

2023年數(shù)據(jù)結(jié)構(gòu)考試試卷（二）

一、單項(xiàng)選擇題（共50題，每小題2分，共100分）

1、以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？

A、隊(duì)列

B、棧

C、線性表

D、二叉樹(shù)

2、下面程序段的時(shí)間復(fù)雜度是（）。I=s=0;

while（s<n）{i++;s+=i;}?應(yīng)該是0（根號(hào)n）

A、0（n）

B、0（if2）

C、0（log2n）

D、0（—3）

3、算法的時(shí)間復(fù)雜度是由（）決定的。

A、問(wèn)題的規(guī)模

B、待處理數(shù)據(jù)的初態(tài)

C、A和B

D、變量個(gè)數(shù)

4、設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最大、最小比較次數(shù)分別時(shí)

A、7,1

B、6,1

C、5,1

D、8,1

5、若要求盡可能快地對(duì)序列進(jìn)行穩(wěn)定的排序，則應(yīng)選（B）。

A、快速排序

B、歸并排序

C、冒泡排序

D、選擇排序

6、下面有關(guān)算法說(shuō)法錯(cuò)誤的是（）。

A、算法最終必須曰計(jì)算機(jī)程序?qū)崿F(xiàn)

B、為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的

C、算法的可行性是指指令不能有二義性

D、算法有5大特性

7、數(shù)據(jù)序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的(C)

的兩趟排序后的結(jié)果。

A、選擇排序

B、冒泡排序

C、插入排序X

；D、堆排序：

8、用二分查找法查找具有n個(gè)結(jié)點(diǎn)的順序表時(shí),查找每個(gè)結(jié)點(diǎn)的平均比較次數(shù)

是(I(5.0分)

A、O(n2)

B、O(nlgn)

C、0(n)

D、0(lon)

9、在下面的程序段中,x=x+l;的語(yǔ)句頻度為()。

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

A、0(2n)

B、0(n)

C、0(rf2)

D、0(log2n)

10、設(shè)一組初始記錄關(guān)鍵字序列為列,H,C,Y,P,A,M,S,R,D,F,X),

則按字母升序的笫一趟冒泡排序結(jié)束后的結(jié)果是()。

A、F,H,C,D,P,A,M,Q,R,S,Y,X

B、P,A,C,S,Q,D,F,X,R,II,M,Y

C、A,D,C,R,F,Q,M,S,Y,P,H,X

D、H,C,Q,P,A,M,S,R,D,F,X,Y

11、設(shè)輸入序列1、2、3、…、n經(jīng)過(guò)棧作用后，輸出序列中的第二個(gè)元素是n,

則輸出序列中的第i個(gè)輸出元素是()o

A、n-i

B、n-1-i

C、n+l-i

D、不能確定

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

()

B、4"上：

.一

【)、6

13、插入和刪除只能在一端進(jìn)行的線性表是

A、循環(huán)隊(duì)列

B、棧

C、隊(duì)列

D、循環(huán)棧

14、具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有(B)人度為2的結(jié)點(diǎn)，

A、8

B、9

C、10

D、11

15、高度為K的二叉樹(shù)最大的結(jié)點(diǎn)數(shù)為()

A、2k

B、2k-l

C、2k-1

D、2k-l-l

16、在任何情況下，時(shí)間復(fù)雜度均為0(nlgn)的K穩(wěn)定的排序方法是()。

⑵0分)

A、直接插入

B、快速排序

C、堆排序

D、歸并排序

17、設(shè)樹(shù)T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1則T中

的葉子數(shù)為（D）

A、5

B、6

D、8"工

18、串是（）。飛:

A、少于一個(gè)字母的序列

B、任意個(gè)字母的序列

C、不少于一個(gè)字符的序列

D、有限個(gè)字符的序列

19、在表長(zhǎng)為n的鏈表中進(jìn)行順序查找，它的平均查找長(zhǎng)度為（）。（5.0

分）

A、n/2

B、（n+l）/2

C、Jn+1

D、lg（n+l）-l

20、評(píng)價(jià)一個(gè)算法性能好壞的重要標(biāo)準(zhǔn)是

A、算法的正確性

B、算法易丁調(diào)試

C、算法的時(shí)間和竺間復(fù)雜度

D、算法易于理解

21、設(shè)有1000個(gè)元素，用二分法查找時(shí)，最小比較次數(shù)為（）。（1分）

A、0

B、1

C、10

D、500

22、將一棵有100個(gè)結(jié)點(diǎn)的完全-二叉樹(shù)從根開(kāi)始,每-層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)

行編號(hào)，根結(jié)點(diǎn)的編號(hào)為10,則編9的結(jié)點(diǎn)的左孩子編號(hào)為(B)。

A、99

B、98

C、50

D、48

23、無(wú)向圖G=(V,E),其

中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(c,d)},對(duì)該

圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是(D)。

A、a,h,p,c,d,f

B、a,c,f,e,b,cl

C、a,e,b,c,f,cl

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

24、設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度

為()。

A、O(n)

B、O(nlog2n)

C、0(1)

D、O(n2)

25、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種()存儲(chǔ)結(jié)構(gòu)

A、隨機(jī)存取

B、順序存取

C、索引存取

D、散列存取

26、判定一個(gè)循環(huán)隊(duì)列隊(duì)(最多元素為m0,m0==Maxsize-l)為滿隊(duì)列的條件

A、((rear-front)+Maxsize)%Maxsize==m0

B、rear-front-l==mO

C、front==rear

D、front==rear+1

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

A、動(dòng)態(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)

28、有向圖采用鄰接矩陣存儲(chǔ)，某行中非零元素的個(gè)數(shù)等于。

A、對(duì)應(yīng)頂點(diǎn)v的度二;

B、對(duì)應(yīng)頂點(diǎn)v的巴度

C、對(duì)應(yīng)頂點(diǎn)v的入度

D、依附于對(duì)應(yīng)頂點(diǎn)v的邊數(shù)

29、下面給出的四種排序法中(D)排序法是不穩(wěn)定性排序法。

A、插入

B、冒泡

C、二路歸并

D、堆積

30、下面給出的四種排序方法中，排序過(guò)程中的比較次數(shù)與排序方法無(wú)關(guān)的是。

(A)

A、選擇排序法

B、插入排序法

C、快速排序法

D、堆積排序法

31、下面關(guān)于稀疏矩陣的快速轉(zhuǎn)秩算法說(shuō)法正確的是()。

A、算法時(shí)間復(fù)雜度要優(yōu)于普通轉(zhuǎn)秩算法

B、算法時(shí)間復(fù)雜度為0(n),n是矩陣的行數(shù)

C、算法空間復(fù)雜度要優(yōu)于普通轉(zhuǎn)秩算法

D、算法適合于行和列數(shù)基本相等的狀況

32、對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為kl,出度為k2,則對(duì)應(yīng)逆鄰接表中該

頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為（）

A、kl

B、k2

C、kl-k2

D、kl+k2

33、排序方法中，從未排序序列中依次取出元素與己排序序列（初始時(shí)為空）

中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為（）

A、希爾排序X/,

B、起泡排序?;匚；

C、插入排序

I）、選擇排序

34、（4分）棧的操作原則是（C）。

A、順序進(jìn)出

B、后進(jìn)后出

C、后進(jìn)先出

D、先進(jìn)先出

35、若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[m],top[i]代表第i個(gè)

棧（i=1,2）棧頂，棧1的底在v[0],棧2的底在V[m-1],則棧滿的條件是

（）

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

top[l]+l=top[2]

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

D、lop[l]=lop[2]

36、下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹(shù)的是。

A、B樹(shù)

B、AVL樹(shù)

C、二叉排序樹(shù)

D、哈夫曼樹(shù)

37、在一個(gè)鏈隊(duì)中，假設(shè)和分別為隊(duì)首和隊(duì)尾指針,則插入s所指結(jié)點(diǎn)的運(yùn)算時(shí)

(B)o

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

r->next=s;r=s;

C、s->next=r;r=s;

Dss->next=ff=s;

38、在平衡二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍為()。

A、-ri

B、o~iV/A

c、-2~2-

.???????

39、最大容量為maxs-ZP的循環(huán)隊(duì)列，隊(duì)尾指針是rear,隊(duì)頭是front,則

隊(duì)滿條件為()

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

B、(front+1)niaxsize==rear

C、(rear+1)maxsize二二front

D^rear==front

40、設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹(shù)，則該哈夫曼樹(shù)共有()個(gè)結(jié)

點(diǎn)。

A、12

B、13

C、25

D、26

41、若對(duì)”階矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所

有元素)依此存放于一維數(shù)組B[L.(n(n+l)/2]中,則在B中確定a[i][j](i<j)

的位置k的關(guān)系為()

A、i*(i-l)/2+j

B、j*(j-l)/2+i

C、i*(i+l)/2+j

D、j*(j+l)/2+i

42、樹(shù)形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種()

A、一對(duì)一關(guān)系

多對(duì)多關(guān)系

C、多對(duì)一關(guān)系

D、一對(duì)多關(guān)系

43、下面程序段執(zhí)行的時(shí)間復(fù)雜度為()opublicstaticvoid

main(String[]args){inti=l,n=100;while(i<=n){i=i*2;

System,out.printin(i);}(5.0分)

A、0(n)號(hào)/二[J]

B、0(log2n)

C、0(n2)

D、0(n3)

44、數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí),物理地址與邏輯地址不相同的,稱(chēng)為()

A、存儲(chǔ)結(jié)構(gòu)

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

C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

D、順序存儲(chǔ)結(jié)構(gòu)

45、深度為4的二叉樹(shù)至多可以有的結(jié)點(diǎn)數(shù)為。

A、17

B、13

C、18

D、15

46、N個(gè)頂點(diǎn)的無(wú)向連通圖，其姓成樹(shù)的邊數(shù)為(A)。

A^n-l

B、n

C、n+1

D、nlogn

47、對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為

(C)。

A、0(n)0(n)

B、0(n)0(1)

C、0(1)0(n)

D、0(1)0(1)

48、圖中有關(guān)路徑的定義是(A)。

A、由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列

B、由不同頂點(diǎn)所形成的序列

C、由不同邊所形成的序列

D、上述定義都不是

49、廣度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的()0

A、先序遍歷

:B、中序遍歷"，

C、后序遍歷

D、層次遍歷

50、(4分)長(zhǎng)度為n的順序表,刪除位置i上的元素(Osisn-1),需要移動(dòng)的元素

個(gè)數(shù)為(B)o

A^n-i

B、n-i-1

C、i

D、i+1

參考答案

一、單項(xiàng)選擇題

1、D

2、A

3、A

4、A

5、B

6、B

7、C

8、D

9、C

10、D

11、D

12、C

13、B

14、B

15、C

16、C

17、D

18、D

19、B

20、C

21、B

22、B

23、D

24、C

25、B

26、A

27、C

28、B

29、D

30、A

31、A

32、C

33、C

34、C

35、B

36、A

37、B

38、A

39、C

40、C

41、A

42、D

43、B

44、C

45、D

46、A

47、C

48、A

49、D

50、B

2023年數(shù)據(jù)結(jié)構(gòu)考試試卷（三）

一、單項(xiàng)選擇題（共50題，每小題2分，共100分）

1、一個(gè)遞歸算法必須包括（）。

A、遞歸部分

B、終止條件

C、終止條件和遞歸部分

D、以上答案都不對(duì)

2、鏈表不具有的特點(diǎn)是（）。

A、可隨機(jī)訪問(wèn)任一元素；，/；「；：二；?「】；

B、插入刪除不需要移動(dòng)元素

C、不必事先估計(jì)存儲(chǔ)空間

D、所需空間與線性表長(zhǎng)度成正比

3、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須

A、以順序方式存儲(chǔ)

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

C、以鏈接方式存儲(chǔ)

D、以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序

4、下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（A

A、存儲(chǔ)密度大

B、插入運(yùn)算方便

C、刪除運(yùn)算方便

D、可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示

5、設(shè)有兩個(gè)串p和q,求p和q首次出現(xiàn)的位置的運(yùn)算稱(chēng)作（）

A、連接

B、模式匹配

C、求子串

D、求串長(zhǎng)

6、設(shè)無(wú)向圖G中有五個(gè)頂點(diǎn)，各頂點(diǎn)的度分別為2、4、3、1、2,則G中邊

數(shù)為（）

A、4

B、5

C、6

D、無(wú)法確定

7、在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）

A、單鏈表定義而已

B、為方便鏈表的操作

C、為雙向鏈表做準(zhǔn)備

D、為循環(huán)鏈表做準(zhǔn)備

8、下列排序方法中,平均時(shí)間性能為O（nlogn）且空間性能最好的是（）。（1

分）???????

A、快速排序

】B、堆排序；：

C、歸并排序

D、基數(shù)排序

9、判定一個(gè)順序棧S（?？臻g大小為n）為空的條件是（）

A^S->top==-l

B、S->top!=0

C^S->top==n

D^S->top!=n

10、下列排序算法中（）排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終

位置上。（2.0分）

A、選擇

B、冒泡

C、歸并

D、堆

11、已知某二叉樹(shù)的后序遍歷序列是DabeC,中序遍歷序列是DebaC,它的前序

遍歷序列是（）

A、aCbeD

DeCaB

C、DeabC

D、CeDba

12、“二叉樹(shù)為空”意味著二叉樹(shù)（）o（3.0分）

A、由一些沒(méi)有賦值的空結(jié)點(diǎn)構(gòu)成

B、根結(jié)點(diǎn)沒(méi)有子樹(shù)

C、不存在

D、沒(méi)有結(jié)點(diǎn)

13、將序列序00,80,90,60,120,110,130,1,2,3）生成二叉排序樹(shù)，則該樹(shù)的高度

R、5

C、6：

D、7

14、設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量s指向插.入的結(jié)點(diǎn)X,則

在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為（）。

A、p->right=s；s->left=p；p->right->left=s；

s->right=p->right；

B、s->left=p；s->right=p->right；p->right=s；p->right->left=s；

C^p->right=s；p->right->left=s；s->left=p；

s->right=p->right；

D^s->left=p；s->right=p->right；p->right->left=s；p->right=s；

15、設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則該無(wú)向圖中所有頂點(diǎn)的入度之和為

（）O

A、n

B、e

C、2n

D、2e

16、i=0;S=0;While(s<n)s+=i++;

A、0(1)

B、0(n71/2))

C、0(n)

D、0(rT2)

17、在一個(gè)含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中,表示邊存在的元素的個(gè)

數(shù)為()o(5.0分)

A、e

B、2e

C、n2-e

D、n2-2e

18、二維數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7,列下標(biāo)j

從0到9.從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)

數(shù)是

A、80

B、100

C、240

D、270I"；""：""；"；"；"

19、一棵完全二叉樹(shù)上有101個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是()

A、50

B、51

C、52

D、53

20、循環(huán)鏈表的主要優(yōu)點(diǎn)是()0

A、不再需要頭指針

B、己知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū)

C、在進(jìn)行插入、刪除運(yùn)算時(shí)能保證鏈表不斷開(kāi)

D、在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表

21、設(shè)一組初始記錄關(guān)鍵字序列⑸2,6,3,8),以第一個(gè)記錄關(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

22、（4分）判定一個(gè)隊(duì)列QU（最多元素為m）為空的條件是（C）。

AsQU->rear-QU->front==m

B、QU->rear-QU->front-l==m

C、QU->front==QU->rear

D、QU->front==QU->rear+l

23、在一個(gè)順序循環(huán)隊(duì)列中，隊(duì)尾指向隊(duì)尾元素的（）位置。

A、前一個(gè)

R、后一個(gè)

C、當(dāng)前

D、最后

24、二維數(shù)組A的每個(gè)元素是由10個(gè)字符組成的串，其行下標(biāo)i=0,1,…,8,列

下標(biāo)j=l,2,…，10。若A按行先存儲(chǔ)，元素A[8,5]的起始地址與當(dāng)A按列先存

儲(chǔ)時(shí)的元素（）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。

A、A[8,5]

B、A[3,10]

C、A[5,8]

D.A[0,9]

25、下列關(guān)于二叉樹(shù)的說(shuō)法正確的是（）

A、一棵二叉樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)大于0

B、二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)要么是葉子，耍么恰有兩個(gè)子女

C、一棵二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1

D、二又樹(shù)中任何一個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)一定相等

26、棧的插入和刪除操作在（）o

A、棧底

B、棧頂

C、任意位置

D、指定位置

27、數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性

上，鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要

A^低

B、高

C、相同

D、不好說(shuō)

28>一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)，（）形態(tài)達(dá)到最大深度

A、單支樹(shù):二:?

B、二叉樹(shù)

C、二叉樹(shù)

D、n叉樹(shù)

29、以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)

A、樹(shù)

B、字符串

C、隊(duì)列

D、棧

30、對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列,用快速排序方法,在

（）情況下排序碼值總比較次數(shù)最多。

A、按排序碼值從小到大排列

B、基本按排序碼值降序排列

C、隨機(jī)排列（完全無(wú)序）

D、基本按排序碼值升序排列

31、一顆二叉樹(shù)高度為h（根的高度為1）,所有結(jié)點(diǎn)的度為0,或者為2,則這顆二

叉樹(shù)最少（）結(jié)點(diǎn)。（3.0分）

A、2h

B、2h-l

C、2h+l

D、h+1

32、在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可

能出現(xiàn)的是（）

A、G中有弧<Vi,Vj>

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

C、G中沒(méi)有弧

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

33、算法的時(shí)間復(fù)雜度取決于（）o

A、輸入量的多少

B、數(shù)據(jù)初始狀態(tài).二;｝二

C、內(nèi)存的大小

I）、硬盤(pán)的大小

34、關(guān)于二叉樹(shù)的說(shuō)法正確的是（）。

A、所有二叉樹(shù)的度均為2

B、一棵二叉樹(shù)的度可以小于2

C、一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2

D、一棵二叉樹(shù)的根結(jié)點(diǎn)的度必為2

35、用順序存儲(chǔ)的方法將完仝二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組中

R[l..n],結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)

A、R[2i+1]

B、R[2i]

C、R[i/2]

D、R[2i-1]

36、對(duì)丁TOO個(gè)長(zhǎng)度不等的初始?xì)w并段,構(gòu)建5路最住歸并樹(shù)時(shí)，需要增加（）

個(gè)虛段。

A、0

B、1

C、2

D、3

37、用鏈?zhǔn)酱鎯?chǔ)的棧，在進(jìn)棧操作時(shí)，將要進(jìn)棧的結(jié)點(diǎn)放在鏈表的（）

A、頭部

B、尾部

C、中間

D、用戶指定的位置

38、在表長(zhǎng)為n的順序表中，當(dāng)在任何位置刪除一個(gè)元素的概率相同時(shí),刪除一

個(gè)元素所需移動(dòng)的平均個(gè)數(shù)為（）0

A、（n-l）/2

B、n/2

C、（n+l）/2二【

D^n

39、雙向鏈表中有兩個(gè)指針域，11ink和rlink分別指向前趨及后繼，設(shè)p

指向鏈表中的一個(gè)結(jié)點(diǎn)，現(xiàn)要求刪去P所指結(jié)點(diǎn)，則正確的刪除是（）（鏈

中結(jié)點(diǎn)數(shù)大于2,p不是第一個(gè)結(jié)點(diǎn)）。

A、p->l1ink->rlink=p->l1ink;

B、"]]

free（p）;P->llink->rlink=p->rlink;p->l1ink->rlink=p->l1ink;Free（p）;p->

Hink->r1ink=p->rlink;

C^p->l1ink->rlink=p->l1ink;

D、以上A,B,C者R不對(duì)。free（p）;P->11ink->r1ink=p->rlink;

40、在進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否①，在出棧運(yùn)算時(shí).應(yīng)先判別棧是否②，

①②處應(yīng)該是（）

A、空，滿

B、滿，空

C、滿，上溢

D、空，下溢

41、數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到5,列下標(biāo)j

從1到6,從首地址開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)

是（）。

A、90

B、70

C、50

D、30

42、表長(zhǎng)為n的順序存儲(chǔ)的線性表，當(dāng)在任意位置上插入或刪除一個(gè)元素的概

率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為(D、),刪除一個(gè)元素

需要移動(dòng)元素的平均個(gè)數(shù)為()

A、(n-l)/2

B、n

C、(n+l)/2二：：：」1

43、算法分析的兩個(gè)主要方面是().

A、空間復(fù)雜性和時(shí)間復(fù)雜性

B、正確性和簡(jiǎn)明性,ll；；.

C、可讀性和文檔性

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

44、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素。1、。2、。3、。4、°5和c6依次進(jìn)

入棧S,一個(gè)元素出棧后即進(jìn)入Q,若6個(gè)元素出隊(duì)的序列是02、。4、。3、

e6、e5和el,則棧S的容量至少應(yīng)該是()。

A、2

B、3

C、4

D、6

45、某二叉樹(shù)的中序序列為ABCDEFG,后序序列為BDCAFGE,則其左子樹(shù)數(shù)目為

()。(3.0分)

A、3

B、2

C、4

D、5

46、為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問(wèn)題，通常設(shè)一個(gè)打數(shù)據(jù)緩沖

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

出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是()。

A、隊(duì)列

B、棧

C、線性表

D、有序表

47、對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣大小是

A、NV'.

B、(N-D2：

......

I)、N*N

48、以下說(shuō)法正確的是()。

A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位

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

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

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

49、設(shè)帶權(quán)連通圖G中含有n(n>l)個(gè)頂點(diǎn)。條邊。下列敘述中，正確的是

A、最小生成樹(shù)中--定含有權(quán)值最小的e條邊

B、最小生成樹(shù)中可能含有權(quán)值最小的n+1條邊

C、最小生成樹(shù)中一定含有權(quán)值最小的n條邊

D、最小生成樹(shù)中可能含有權(quán)值最小的n-I條邊

50、索引順序表的特點(diǎn)是順序表中的數(shù)據(jù)

A、有序

B、無(wú)序

C、塊間有序

D、散列

參考答案

一、單項(xiàng)選擇題

1、C

2、A

3、B

4、A

5、B

6、C

7、B"工

8、B

9、A

10、C

11、D

12、D

13、C

14、D

15、D

16、B

17、B

18、C

19、B

20、D

21、C

22、C

23、B

24、B

【解析】解釋?zhuān)涸O(shè)數(shù)組從內(nèi)存首地址M開(kāi)始順序存放，若數(shù)組按行先存儲(chǔ)，元

素A[8,5]的起始地址為:M+[(8-0)*10+(5-1)]*l=M+84；若數(shù)組按列先存

儲(chǔ)，易計(jì)算出元素A[3,10]的起始地址為：M+[(10-1)*9+(3-0)]*1=M+84O

故選B。

25、C

26、B

27、B

28、A

29、A

30、A

31、BV/4

32、D

33、B

34、B

35、B

36、B

37、A

38、A

39、D

40、B

41、A

42、D

43、A

44、B

【解析】解釋?zhuān)涸爻鲫?duì)的序列是e2、e4、e3、e6、e5和el,可知元素入隊(duì)

的序列是c2、u4>e3、6e5和4,即元素出棧的序列也是e2、“、匕3、

e6、e5和el,而元素el、e2>e3、e4>e5和e6依次進(jìn)入棧，易知棧S中最多

同時(shí)存在3個(gè)元素，故棧S的容量至少為3。

45、C

46、A

【解析】解釋?zhuān)航鉀Q緩沖區(qū)問(wèn)題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一

種先進(jìn)先出的線性表。

47、D

48、D

【解析】解釋?zhuān)簲?shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)

結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。

49、D

2023年數(shù)據(jù)結(jié)構(gòu)考試試卷(四)

一、單項(xiàng)選擇題(共50題，每小題2分，共100分)

1、廣義表(A,(a,b,c))的表頭和表尾是()o

A^A((a,b,c))

aB,c

C>(a,b,c)A

D、(a,b)c

2、不含任何結(jié)點(diǎn)的空樹(shù)

A、是一棵樹(shù)款

B、是一棵二叉樹(shù)

C、是一棵樹(shù)也是一棵二叉樹(shù)

D、既不是樹(shù)也不是二叉樹(shù)

3、對(duì)于順序表的優(yōu)缺點(diǎn)，以下說(shuō)法不正確的是()。(3.0分)

A、無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間

B、可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)

C、插入和刪除運(yùn)算比較方便

D、容易造成一部分空間長(zhǎng)期閑置而得不到充分利用

4、線性表是一個(gè)有限序列，組成線性表的基本單位是(B)。

A、數(shù)據(jù)項(xiàng)

B、數(shù)據(jù)元素

C、數(shù)據(jù)域

D、字符

5、一棵二叉樹(shù)的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是

(B)

A、CABDEFG

B、ABCDEFG

C、DACEFBG

D、ADCFEG

6、下面程序段的時(shí)間復(fù)雜性的量級(jí)為()For(i=l;i<=n;i++)

For(j=l;j<=I;j++)For(k=l;k<=j;k++)x=x+l;

A、0(1)

B、0(n)

C、0(n2)

D、0(n3)

7、在二叉排序樹(shù)的()序列是一個(gè)遞增有序序列。

A、先序遍歷

B、中序遍歷.

C、后序遍歷

D、層次遍歷

8、n個(gè)頂點(diǎn)的生成樹(shù)有()條邊.

A、n-1

B、n

C、n+1

D、2n

9、向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所有結(jié)點(diǎn)時(shí)，則執(zhí)行(不帶空的頭

結(jié)點(diǎn))

A^HS->next=s;

s—>next=HS—>next;HS—>next=s;

C、s—>next=HS;HS=s;

D、s->next=HS;HS=HS一>next;

10、設(shè)有向無(wú)環(huán)圖G中的有向邊集合E={<1,2>,<2,3>,<3,4>,<1,4>},假設(shè)每條

邊長(zhǎng)度為1,則1點(diǎn)到4點(diǎn)的最短距離為()

A、4

B、3

C、2

D、1

11、利用數(shù)組a[N]存儲(chǔ)一個(gè)順序棧時(shí)，用top標(biāo)識(shí)棧頂指針，已知棧未滿，

當(dāng)元素x進(jìn)行進(jìn)棧時(shí)執(zhí)行的操作是()

A、a[—top]=x;

B、a[top-]=x;

C、a[++top]=x;

Dsa[top++]=x;

12、在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)，通常設(shè)置一個(gè)打印機(jī)

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

取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)()結(jié)構(gòu)

；A、棧；

B、隊(duì)列

C、樹(shù)

D、線性表

13、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q和P之

間插入一個(gè)結(jié)點(diǎn)S,則執(zhí)行()。

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

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

C、q->ncxt=s;s->noxt=p;

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

14、執(zhí)行完下列語(yǔ)句段后，i值為：()。intf(intx)

{return((x>0)?x*f(x-l):2);}inti;i=f(f(l)):

(4.0分)

A、2

B、4

C、8

D、無(wú)限遞歸

15、求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前趨的時(shí)間復(fù)雜度分別是()。

A、0(n)和0(1)

B、0⑴和0(1)

C、0(1)和0(n)

D、0(一和08)

16、在一個(gè)鏈隊(duì)中,假設(shè)和分別為隊(duì)首和隊(duì)尾指針,則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí)

(C)o

A、r=f->next;

B、r=r->next;

C、f=f->next;

Dsf=r->next;

17、若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和

刪除運(yùn)算,則利用(A)存儲(chǔ)方式最節(jié)省時(shí)間。

A、順序表

R、雙鏈表

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

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

18、設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最大、最小比較次數(shù)分別時(shí)

()

A、7,1I"；""："["；"；"；

B、6,1

C、5,1

D、8,1第九章排序

19、數(shù)據(jù)的四種存儲(chǔ)結(jié)構(gòu)是()。

A、順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)

B、鏈?zhǔn)酱鍍?chǔ)結(jié)構(gòu)、非線性存儲(chǔ)結(jié)構(gòu)、樹(shù)型存儲(chǔ)結(jié)構(gòu)和圖型存儲(chǔ)結(jié)構(gòu)

C、集合存儲(chǔ)結(jié)構(gòu)一對(duì)-存儲(chǔ)結(jié)構(gòu).一對(duì)多存儲(chǔ)緒構(gòu)和多對(duì)多存儲(chǔ)結(jié)構(gòu)

D、順序存儲(chǔ)結(jié)構(gòu)、樹(shù)型存儲(chǔ)結(jié)構(gòu)、圖型存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)

20、算法的空間復(fù)雜度是指(

A、執(zhí)行算法程序所占的存儲(chǔ)空間

B、算法程序中的指令條數(shù)

C、算法程序的長(zhǎng)度

D、算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間

21、如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu),則退棧操作時(shí)()。

A、必須判別棧是否滿

B、判別棧元素的類(lèi)型

C、必須判別棧是否空

D、不做任何判別

22、(4分)隊(duì)列的特點(diǎn)是(D)。

A、允許在表的任何位置進(jìn)行插入和刪除

B、只允許在表的一端進(jìn)行插入和刪除

C、允許在表的兩端進(jìn)行插入和刪除

D、只允許在表的--端進(jìn)行插入，在另一端進(jìn)行刪除

23、一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的出隊(duì)序列是()0(1分)

A、1,2,3,4

B、4,3,2,1

C、1,4,3,2

D、3,4,1,2

24、某哈希查找表有n條記錄，對(duì)應(yīng)的哈希函數(shù)具有ni個(gè)值，則()

A、n<m

n>m

C、n<=m

D、n>=m

25、若有向圖G中頂點(diǎn)數(shù)為n,則圖G至多有()條邊。

A、0

C、n(n-l)/2

D>n(n-l)

26、若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素

算法的時(shí)間復(fù)雜度()。(1分)

A^0(log2n)

B、0(1)

C、0(n)

D、0(if2)

27、由二叉樹(shù)的前序利后序遍歷序列()惟一確定這棵二叉樹(shù)。

A、能

B、不能

C、如果是滿二叉樹(shù)就能

D、如果是完全二叉樹(shù)就能

28、(3分)下列關(guān)于散列函數(shù)的說(shuō)法正確的是(D)。

A、散列函數(shù)越復(fù)雜越好二;；丁；

B、用除余法構(gòu)造的散列函數(shù)是最好的

C、散列函數(shù)越簡(jiǎn)單越好

D、在沖突盡可能少的情況下,散列函數(shù)越簡(jiǎn)單越好

29、下列結(jié)構(gòu)中屬于非線性結(jié)構(gòu)的是()'

A、循環(huán)隊(duì)列

B、二維數(shù)組

C、二叉鏈表

D、雙向鏈表

30、時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0(nlog2n)的是()。

A、堆排序

B、冒泡排序

C、選擇排序

D、快速排序

31、(4分)在一個(gè)單鏈表中，口知q指向p所指向結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q.p所

指結(jié)點(diǎn)之間插入一個(gè)s所指向的新結(jié)點(diǎn),則執(zhí)行的操作是(A)。

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

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

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

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

32、若對(duì)n階對(duì)稱(chēng)矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線

上所有元素)依次存放于一維數(shù)組B[l..(n(n+l))/2]中，則在B中確定aij

(i<j)的位置k的關(guān)系為()。

A、i*(i-l)/2+j

B、j*(j-l)/2+i

C、i*(i+l)/2+j

D、j*(j+l)/2+i

33、現(xiàn)有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。

表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為()

A、向量k:：】二:：

B、二叉樹(shù)

C、樹(shù)

D、圖

34、設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)邊結(jié)點(diǎn)，則該圖中有(：條

有向邊。

A、n

n-l

C、m

D、m-1

35、數(shù)據(jù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求()

A、每個(gè)結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域

B、所有結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域

C、結(jié)點(diǎn)的最后一人域必須是指針域

D、每個(gè)結(jié)點(diǎn)有多〃后繼結(jié)點(diǎn)，就必須設(shè)多少個(gè)針域

36、一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1,2,3,4,則隊(duì)列的出隊(duì)時(shí)輸出序列是

A、4,3,2,1

B、1,2,3,4

C、1,4,3,2

D、3,2,4,1

37、對(duì)順序表上的插入、刪除算法的時(shí)間復(fù)雜性分析來(lái)說(shuō)，常以()為標(biāo)準(zhǔn)操作。