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

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

您的姓名：［填空題］*

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

對(duì)

錯(cuò)

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

對(duì)

錯(cuò)（正確答案）

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

A對(duì)

B錯(cuò)（正確答案）

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

對(duì)

錯(cuò)

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

對(duì)

錯(cuò)

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

對(duì)（正確答案）

錯(cuò)

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

對(duì)

錯(cuò)

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

鏈表。［判斷題］*

對(duì)（正確答案）

錯(cuò)

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

對(duì)

錯(cuò)

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

［判斷題］*

對(duì)（正確答案）

錯(cuò)

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

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

對(duì)

錯(cuò)

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

為int型。［判斷題］*

對(duì)（正確答案）

錯(cuò)

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

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

對(duì)

錯(cuò)（正確答案）

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

A截取字串（正確答案）

B串判空（正確答案）

C連接字符串

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

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

Astrcat

Bstrcpy（正確答案）

Cstrlen

Dstrcmp（正確答案）

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

A棧（正確答案）

B隊(duì)列

C串（正確答案）

D鏈表

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

A離散事件的模擬

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

C消息的緩存

D迷宮問(wèn)題

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

A荷蘭國(guó)旗問(wèn)題（正確答案）

B八皇后問(wèn)題（正確答案）

C迷宮問(wèn)題（正確答案）

D漢諾塔問(wèn)題

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

A棧（正確答案）

B隊(duì)列（正確答案）

C鏈表

D順序表（正確答案）

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

法完成的。*

A括號(hào)匹配（正確答案）

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

C表達(dá)式求值

D八皇后問(wèn)題（正確答案）

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

A八皇后問(wèn)題

B迷宮問(wèn)題

C括號(hào)匹配（正確答案）

D表達(dá)式求值

22.棧和隊(duì)列的共同點(diǎn)是（）。*

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

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

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

D都不對(duì)

23.入棧的先后順序?yàn)閍,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)之隊(duì)列的應(yīng)用包括哪些（）。*

A消息的緩存

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

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

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

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

順序不可能是（）。*

AA、C、B

BA、B、C

CC、A、B確答案）

DC、B、A

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

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

B棧的刪除操作叫做彈棧

C棧的刪除操作叫做壓棧

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

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

ALastInFirstOut

BFirstInFirstOut

C不確定

D都不對(duì)

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

的是0o［單選題］*

Ap->next=p->next;

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

Cp->next=p;

Dp=p->next;

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

素。［單選題］*

An-i+1正確答案）

Bn-2

Cn-1

Dn

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

A0（1）

B0（n）（正確答案）

CO(n*n)

D都不對(duì)

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

*

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

Bn/2

Cn-1

Dn-2

32.在單鏈表中，在s指針指向的結(jié)點(diǎn)后插入p指針指向的結(jié)點(diǎn)，指針域?yàn)閚ext,

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

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個(gè)元素采用順序表存儲(chǔ)，在第i個(gè)位置刪除需要移動(dòng)一個(gè)元素，其時(shí)間復(fù)

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

An-i+1O(n)

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

Cn-i0(1)

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

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

［單選題］*

Amalloc(p);

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

Crelloc(p);

Dempty(p);

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

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

B回收指針變量的空間

C為普通變量分配空間

D釋放普通變量的空間

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

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

A順序表

B鏈表

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

D指針

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

為浪費(fèi)一個(gè)單元的形式，則隊(duì)滿的條件是()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)隊(duì)列最大容量是MAX,隊(duì)頭是front,隊(duì)尾是rear,采用人

為浪費(fèi)一個(gè)單元的形式，則隊(duì)的長(zhǎng)度是0o［單選題］*

A(rear—front)%MAX

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

Crear—front+MAX

D都不對(duì)

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

AMNP（正確答案）

BPNM

CNPM

DNMP

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

［單選題］*

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

（正確答案）

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

行模式匹配

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

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

41.線性結(jié)構(gòu)中，線性表采用鏈?zhǔn)酱鎯?chǔ)的好處是（）。［單選題］*

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

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

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

D插入刪除需要移動(dòng)大量元素

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

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

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

C鏈表等價(jià)于線性表

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

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

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

A1（正確答案）

B0.9

C0.75

D0.25

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

0o［單選題］*

AO,P,Q正確答案）

BO,Q,P

CQ,P,O

DO,Q,P

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

（）o［單選題］*

Ax,y,z

Bz,y,x

Cy,z,x

Dz,x,y正確答案）

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

A只