形考作業(yè)1

一、單項(xiàng)選擇題（每小題3分，共60分）

1.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（ ）。

A.邏輯結(jié)構(gòu) B.物理結(jié)構(gòu) C.算法的具體實(shí)現(xiàn) D.給相關(guān)變量分配存儲(chǔ)單元

答案：B

2.下列說(shuō)法中，不正確的是（ ）。

A.數(shù)據(jù)元素是數(shù)據(jù)的基本單位 B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位 C.數(shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成 D.數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成

答案：D

3.一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（ ）。

A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)元素 C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)類(lèi)型

答案：B

4.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）。

A.存儲(chǔ)結(jié)構(gòu) B.物理結(jié)構(gòu) C.邏輯結(jié)構(gòu) D.物理和存儲(chǔ)結(jié)構(gòu)

答案：C

5.在線性表的順序結(jié)構(gòu)中，以下說(shuō)法正確的是（ ）。

A.邏輯上相鄰的元素在物理位置上不一定相鄰 B.數(shù)據(jù)元素是不能隨機(jī)訪問(wèn)的 C.邏輯上相鄰的元素在物理位置上也相鄰 D.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高

答案：C

6.對(duì)鏈表, 以下敘述中正確的是（ ）。

A.不能隨機(jī)訪問(wèn)任一結(jié)點(diǎn) ?B.結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的 C.插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn) D.可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)

答案：A

7.下列的敘述中，不屬于算法特性的是（ ）。

A.有窮性 B.輸入性 C.可行性 D.可讀性

答案：D

8.算法的時(shí)間復(fù)雜度與（ ）有關(guān)。

A.所使用的計(jì)算機(jī) B.計(jì)算機(jī)的操作系統(tǒng) C.算法本身 D.數(shù)據(jù)結(jié)構(gòu)

答案：C

9.設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新表的第i個(gè)元素），插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（ ）。

A.n-i+1 B.n-i C.n-i-1 D.i

答案：A

10.設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（ ）。

A.n-i+1 B.n-i C.n-i-1 D.i

答案：B

11.在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語(yǔ)句（ ）。

A.p=q->next B.p->next=q C.p->next=q->next D.q->next=NULL

答案：C

12.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ ）。

A.p->next= s; s->next= p->next B.p->next=s->next; C.p=s->next D.s->next=p->next; p->next=s;

答案：D

13.非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（ ）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。

A.p->next==head B.p==NULL C.p->next==NULL D.p== head

答案：A

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

A.可隨機(jī)訪問(wèn)任一元素 B.插入刪除不需要移動(dòng)元素 C.不必事先估計(jì)存儲(chǔ)空間 D.邏輯上相鄰的元素在物理位置上不一定相鄰

答案：A

15.帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（ ）（設(shè)頭指針為head）。

A.head ==NULL B.head->next==NULL C.head->next==head D.head!=NULL

答案：B

16.在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開(kāi)始從后到前依次移動(dòng)了15個(gè)元素。則原順序表的長(zhǎng)度為（ ）。

A.21 B.20 C.19 D.25

答案：B

17.有關(guān)線性表的正確說(shuō)法是（ ）。

A.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B.線性表至少要求一個(gè)元素 C.表中的元素必須按由小到大或由大到下排序 D.除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼

答案：D

18.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并保持原來(lái)的順序不變，平均要移動(dòng)（ ）個(gè)元素。

A.8 B.7 C.63 D.63.5

答案：D

19.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度為2，則第6個(gè)元素的地址是（ ）。

A.98 B.100 C.102 D.106

答案：B

20. 在一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、q分別指向表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，且p、q仍然分別指向新表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)。可用的語(yǔ)句是p=p->next;和（ ）。

A.p=q->next B.p->next=q C.q=p D.q->next=p

答案：D

二、判斷題（ 每小題2分，14題，共28分）

21.數(shù)據(jù)元素可以有一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。

答案：對(duì)

22.數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。

答案：錯(cuò)

23.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為邏輯結(jié)構(gòu)。

答案：錯(cuò)

24.數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲(chǔ)該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。

答案：錯(cuò)

25.數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對(duì)多的關(guān)系稱為樹(shù)狀結(jié)構(gòu)。

答案：錯(cuò)

26.通?？梢园岩槐竞胁煌鹿?jié)的書(shū)的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。

答案：錯(cuò)

27.通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成樹(shù)型結(jié)構(gòu)。

答案：錯(cuò)

28. 設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，指針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn)，可用語(yǔ)句p=p->next;。

答案：對(duì)

29. 設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語(yǔ)句p->next=head 。

答案：對(duì)

30. 設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，指針p指向表中某結(jié)點(diǎn)，若邏輯表達(dá)式p->next==head;的結(jié)果為真，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。

答案：對(duì)

31. 要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行 p->next=s; s->next= p->next；的操作。

答案：錯(cuò)

32. 要在一個(gè)單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行q->next= p->next；

答案：對(duì)

33. 要在一個(gè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個(gè)新的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，若結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，尾指針為p，則可執(zhí)行head=head-> next; p->next=head；。

答案：對(duì)

34. 設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為head，鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)行操作p->next=head；。

答案：對(duì)

三、程序填空題（每小題6分，共12分。請(qǐng)點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）

35.

設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head，以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data,完成程序中空格部分。

#define NULL 0

void main( )

{ NODE *head ,*p ;

p=head; /*p為工作指針*/

do

{printf(“%d\n”, _p->data__;

_p=p->next;

}while__p!=NULL__;

}

36.

設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表，p、q是指向鏈表中結(jié)點(diǎn)類(lèi)型的指針變量，p指向鏈表中結(jié)點(diǎn)a, （設(shè)鏈表中沒(méi)有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同）,寫(xiě)出相關(guān)語(yǔ)句

(1)使該單向鏈表成為單向循環(huán)鏈表

(2)插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)

q=p; x=p->data;

while __q->next!=NULL__）q=q->next;

q->next=head;

q=p; p=p->next;

while(p->data!=x)

{ q=p;

_p=p->next_

}

s->next=p;

__q->next=s__;

?

?

?

?

?