題庫-數(shù)據(jù)結(jié)構(gòu)14

題庫-數(shù)據(jù)結(jié)構(gòu)14

您的姓名：［填空題］*

1.線性結(jié)構(gòu)是一對一的結(jié)構(gòu)，圖形結(jié)構(gòu)是多對多的結(jié)構(gòu)。［判斷題］*

對

錯

2.算法的效率用空間復(fù)雜度來衡量。［判斷題］*

對

錯（正確答案）

3.n個元素的順序表插入、刪除的時間復(fù)雜度是0（1）（）。［單選題］*

A對

B錯（正確答案）

4.鏈表是線性結(jié)構(gòu)，棧也是線性結(jié)構(gòu)。［判斷題］*

對

錯

5.先進(jìn)先出的英文是FirstInFirstOuto［判斷題］*

對

錯

6.數(shù)據(jù)結(jié)構(gòu)里，線性表若是采用順序存儲結(jié)構(gòu)則稱為順序表。［判斷題］*

對（正確答案）

錯

7.數(shù)據(jù)結(jié)構(gòu)里，線性結(jié)構(gòu)有：順序表、鏈表、棧、隊列。［判斷題］*

對

錯

8.數(shù)據(jù)結(jié)構(gòu)里，鏈表的每個結(jié)點由數(shù)據(jù)域和指針域，指針域只有一個的鏈表稱為單

鏈表。［判斷題］*

對（正確答案）

錯

9.數(shù)據(jù)結(jié)構(gòu)里，隊列的特性是先進(jìn)先出，其英文是FirstInFirstOut。［判斷題］*

對

錯

10.數(shù)據(jù)結(jié)構(gòu)里，棧的特性是后進(jìn)先出，隊列的特性是先進(jìn)先出，都是線性結(jié)構(gòu)。

［判斷題］*

對（正確答案）

錯

1L字符串的處理函數(shù)strcpy是系統(tǒng)定義的，作用是進(jìn)行字符串拷貝，兩個參數(shù)，

返回值為char*。［判斷題］*

對

錯

12.字符串的處理函數(shù)strcmp是系統(tǒng)定義的，作用是進(jìn)行字符串比較大小，返回值

為int型。［判斷題］*

對（正確答案）

錯

13.字符串的處理函數(shù)strlen是系統(tǒng)定義的，作用是進(jìn)行計算字符串的長度包括字

符串結(jié)束'\0'在內(nèi)，返回值為int型。［判斷題］*

對

錯（正確答案）

14.串是一種特殊的線性結(jié)構(gòu)，串的操作可以有（）。*

A截取字串（正確答案）

B串判空（正確答案）

C連接字符串

D定位子串在主串中的位置：答邇）

15.以下是C語言中的字符串處理函數(shù)的，且?guī)в袃蓚€參數(shù)的是（）。*

Astrcat

Bstrcpy（正確答案）

Cstrlen

Dstrcmp（正確答案）

16.線性結(jié)構(gòu)是1對1的結(jié)構(gòu)，以下結(jié)構(gòu)屬于線性結(jié)構(gòu)的是（）。*

A棧（正確答案）

B隊列

C串（正確答案）

D鏈表

17.隊列的性質(zhì)是先進(jìn)先出，常應(yīng)用于（）。*

A離散事件的模擬

B操作系統(tǒng)的作業(yè)調(diào)度

C消息的緩存

D迷宮問題

18.棧的特性是后進(jìn)先出，應(yīng)用范圍廣，以下屬于棧的應(yīng)用的是（）o*

A荷蘭國旗問題（正確答案）

B八皇后問題（正確答案）

C迷宮問題（正確答案）

D漢諾塔問題

19.數(shù)據(jù)結(jié)構(gòu)里，以下是線性結(jié)構(gòu)的是（）o*

A棧（正確答案）

B隊列（正確答案）

C鏈表

D順序表（正確答案）

20.棧是很多算法完成的必備數(shù)據(jù)結(jié)構(gòu)，其中哪些算法（）都是要使用棧來幫助算

法完成的。*

A括號匹配（正確答案）

B進(jìn)制轉(zhuǎn)換

C表達(dá)式求值

D八皇后問題（正確答案）

21.棧是一種應(yīng)用廣泛的線性結(jié)構(gòu)，棧的應(yīng)用包括（）o*

A八皇后問題

B迷宮問題

C括號匹配（正確答案）

D表達(dá)式求值

22.棧和隊列的共同點是（）。*

A都是樹形結(jié)構(gòu)

B都是限制存取點的線性結(jié)構(gòu)

C都是線性結(jié)構(gòu)

D都不對

23.入棧的先后順序為a,b,c,d,e,（入棧和出?？梢蚤g隔進(jìn)行）則出棧順序可能是（）。

*

Aa,b,c,d,e（正確答案）

Be,d,c,b,a

Cc,b,a,d,e（正確答案）

Dd,b,c,a,e

24.線性結(jié)構(gòu)之隊列的應(yīng)用包括哪些（）。*

A消息的緩存

B操作系統(tǒng)的作業(yè)調(diào)度

C離散事件的模擬（正確答案）

D進(jìn)制轉(zhuǎn)換

25.數(shù)據(jù)結(jié)構(gòu)里，由于隊列是先進(jìn)先出的特性，入隊的順序是A、B、C則出隊的

順序不可能是（）。*

AA、C、B

BA、B、C

CC、A、B確答案）

DC、B、A

26.數(shù)據(jù)結(jié)構(gòu)里，下列選項中關(guān)于棧的刪除操作描述正確的是（）o*

A棧的刪除操作叫做出棧（正確答案）

B棧的刪除操作叫做彈棧

C棧的刪除操作叫做壓棧

D棧的刪除操作叫做進(jìn)棧

27.數(shù)據(jù)結(jié)構(gòu)里，棧是后進(jìn)先出的線性表，后進(jìn)先出英文是（）。［單選題］*

ALastInFirstOut

BFirstInFirstOut

C不確定

D都不對

28.數(shù)據(jù)結(jié)構(gòu)里，單鏈表中刪除p指針指向結(jié)點的后繼（假設(shè)存在）的語句序列正確

的是0o［單選題］*

Ap->next=p->next;

Bp->next=p->next->next;

Cp->next=p;

Dp=p->next;

29.數(shù)據(jù)結(jié)構(gòu)里，在n個元素的順序表的第i個位置插入元素需要移動（）個元

素。［單選題］*

An-i+1正確答案）

Bn-2

Cn-1

Dn

30.數(shù)據(jù)結(jié)構(gòu)里，順序表刪除元素的時間復(fù)雜度是（）。［單選題］*

A0（1）

B0（n）（正確答案）

CO(n*n)

D都不對

31.數(shù)據(jù)結(jié)構(gòu)里，n個元素的順序表，刪除元素平均需要移動()個元素。［單選題］

*

A(n-l)/2(正確答案)

Bn/2

Cn-1

Dn-2

32.在單鏈表中，在s指針指向的結(jié)點后插入p指針指向的結(jié)點，指針域為next,

語句序列是：()。［單選題］*

Ap->next=s->next;s->next=p;

Bs->next=p->next;p->next=s;

Cs->next=s->next->next;free(p);

Ds->next=p;p->next=s->next;

33.線性表n個元素采用順序表存儲，在第i個位置刪除需要移動一個元素，其時間復(fù)

雜度是()o［單選題］*

An-i+1O(n)

Bn-iO(n)(正確答案)

Cn-i0(1)

D(n-1)/2O(1)

34.假設(shè)指針變量為p指向某塊內(nèi)存區(qū)域，則回收這塊區(qū)域所用的語句是()o

［單選題］*

Amalloc(p);

Bfi*ee(p);(正確答案)

Crelloc(p);

Dempty(p);

35.在C語言描述的數(shù)據(jù)結(jié)構(gòu)算法中，函數(shù)malloc的作用是()。［單選題］*

A為指針變量分配空間(正確答案)

B回收指針變量的空間

C為普通變量分配空間

D釋放普通變量的空間

36.線性結(jié)構(gòu)中，無需為表中的元素之間的邏輯關(guān)系而增加額外的存儲空間是()

的優(yōu)點。［單選題］*

A順序表

B鏈表

C結(jié)構(gòu)體

D指針

37.數(shù)據(jù)結(jié)構(gòu)中，循環(huán)隊列最大容量是MAX,隊頭是front,隊尾是rear,采用人

為浪費一個單元的形式，則隊滿的條件是()o［單選題］*

A(rear+1)%MAX==front

Brear%MAX==front

C(rear-l)%MAX==front

D(rear+l)==front

38.數(shù)據(jù)結(jié)構(gòu)中，循環(huán)隊列最大容量是MAX,隊頭是front,隊尾是rear,采用人

為浪費一個單元的形式，則隊的長度是0o［單選題］*

A(rear—front)%MAX

B(rear—front+MAX)%MAX正歹

Crear—front+MAX

D都不對

39.入隊順序是M,N,P;則出隊順序是（）o［單選題］*

AMNP（正確答案）

BPNM

CNPM

DNMP

40.串的KMP算法是由三個科學(xué)家同時發(fā)現(xiàn)的，對原有的算法改進(jìn)點在于（）。

［單選題］*

A指向主串的指針不需要回溯，只模式串滑動盡可能遠(yuǎn)的距離后繼續(xù)進(jìn)行模式匹配

（正確答案）

B主串的指針要回溯到之前的某個位置，同時模式串滑動盡可能遠(yuǎn)的距離后繼續(xù)進(jìn)

行模式匹配

C某個字符匹配失敗時，主串與模式都不需要回溯指針

D時間復(fù)雜度可提高到O（n*m）,n和m表示主串和模式串的長度。

41.線性結(jié)構(gòu)中，線性表采用鏈?zhǔn)酱鎯Φ暮锰幨牵ǎ?。［單選題］*

A可以隨機(jī)訪問任何一個元素

B元素都存在一片連續(xù)的存儲空間

C無需預(yù)估存儲空間的大小

D插入刪除需要移動大量元素

42.鏈表與線性表的關(guān)系是（）。［單選題］*

A鏈表是線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。（正確答案）

B鏈表是線性表采用順序存儲結(jié)構(gòu)。

C鏈表等價于線性表

D鏈表和順序表都不是線性表

43.順序表可以存儲大量密集數(shù)據(jù)，不需要額外的空間存儲線性表元素之間的邏輯

關(guān)系，順序表的存儲密度是0o［單選題］*

A1（正確答案）

B0.9

C0.75

D0.25

44.隊列具有先進(jìn)先出的特性，那么入隊的O,P,Q順序的三個元素，出隊順序是

0o［單選題］*

AO,P,Q正確答案）

BO,Q,P

CQ,P,O

DO,Q,P

45.棧有后進(jìn)先出的特性，那么入棧順序是x,y,z的三個元素，出棧不可能的順序是

（）o［單選題］*

Ax,y,z

Bz,y,x

Cy,z,x

Dz,x,y正確答案）

46.鏈表的指針域可以有（）。［單選題］*

A只