數(shù)據(jù)結構習題及答案-嚴蔚敏

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結構習題及答案——嚴蔚敏第一章緒論

一、挑選題

1.組成數(shù)據(jù)的基本單位是（）

（A）數(shù)據(jù)項（B）數(shù)據(jù)類型（C）數(shù)據(jù)元素（D）數(shù)據(jù)變量

2.數(shù)據(jù)結構是討論數(shù)據(jù)的（）以及它們之間的互相關系。

（A）抱負結構，物理結構（B）抱負結構，抽象結構

（C）物理結構，規(guī)律結構（D）抽象結構，規(guī)律結構

3.在數(shù)據(jù)結構中，從規(guī)律上可以把數(shù)據(jù)結構分成（）

（A）動態(tài)結構和靜態(tài)結構（B）緊湊結構和非緊湊結構

（C）線性結構和非線性結構（D）內(nèi)部結構和外部結構

4.數(shù)據(jù)結構是一門討論非數(shù)值計算的程序設計問題中計算機的（①）以及它們之間的（②）和運算等的學科。

①（A）數(shù)據(jù)元素（B）計算辦法（C）規(guī)律存儲（D）數(shù)據(jù)映像

②（A）結構（B）關系（C）運算（D）算法

5.算法分析的目的是（）。

（A）找出數(shù)據(jù)結構的合理性（B）討論算法中的輸入和輸出的關系

（C）分析算法的效率以求改進（D）分析算法的易懂性和文檔性

6.計算機算法指的是（①）,它必需具備輸入、輸出和（②）等5

個特性。

①（A）計算辦法（B）排序辦法（C）解決問題的有限運算序列（D）調(diào)度辦法

②（A）可執(zhí)行性、可移植性和可擴充性（B）可行性、確定性和有窮性

（C）確定性、有窮性和穩(wěn)定性（D）易讀性、穩(wěn)定性和平安性

二、推斷題

1.數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結構。（）

2.算法就是程序。（）

3.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）

4.算法的五個特性為：有窮性、輸入、輸出、完成性和確定性。（）

5.算法的時光復雜度取決于問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。（）

三、填空題

1.數(shù)據(jù)規(guī)律結構包括________、________、_________和_________四種類型,其中樹形結構和圖形結構合稱為_____。

2.在線性結構中,第一個結點____前驅結點,其余每個結點有且惟獨______個前驅結點；最后一個結點______后續(xù)結點,其余每個結點有且惟獨_______個后續(xù)結點。

3.在樹形結構中,樹根結點沒有_______結點,其余每個結點有且只

有_______個前驅結點；葉子結點沒有________結點,其余每個結點的后續(xù)結點可以_________。

4.在圖形結構中,每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以

_________。

5.線性結構中元素之間存在________關系,樹形結構中元素之間存

在______關系,圖形結構中元素之間存在_______關系。

6.算法的五個重要特性是_______、_______、______、_______、

_______。

7.數(shù)據(jù)結構的三要素是指______、_______和________。

8.鏈式存儲結構與挨次存儲結構相比較,主要優(yōu)點是

________________________________。

9.設有一批數(shù)據(jù)元素,為了最快的存儲某元素,數(shù)據(jù)結構宜用

_________結構,為了便利插入一個元素,數(shù)據(jù)結構宜用

____________結構。

四、算法分析題

1.求下列算法段的語句頻度準時間復雜度

參考答案：

一、挑選題

1.C

2.C

3.C

4.A、B

5.C

6.C、B

二、推斷題:

1、√

2、×

3、×

4、×

5、√

三、填空題

1、線性、樹形、圖形、集合?；非線性（網(wǎng)狀）

2、沒有；1；沒有；1

3、前驅；1；后繼；隨意多個

4、隨意多個

5、一對一；一對多；多對多

6、有窮性；確定性；可行性；輸入；輸出

7、數(shù)據(jù)

元素；規(guī)律結構；存儲結構8、插入、刪除、合并等操作較便利9、挨次存儲；鏈式存儲

四、算法分析題

for(i=1;inext=p;p->next=s;（B）s->next=p->next;p->next=s;（C）s->next=p->next;p=s;（D）p->next=s;s->next=p;

5.在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(zhí)行（）（A）p->next=p->next->next;（B）p=p->next;

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

（C）p->next=p->next;（D）p=p->next->next;

6.下列有關線性表的講述中，正確的是（）

（A）線性表中的元素之間隔是線性關系

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

（C）線性表中任何一個元素有且僅有一個直接前趨

（D）線性表中任何一個元素有且僅有一個直接后繼

7.線性表是具有n個（）的有限序列（n≠0)

（A）表元素（B）字符（C）數(shù)據(jù)元素（D）數(shù)據(jù)項

二、推斷題

1.線性表的鏈接存儲，表中元素的規(guī)律挨次與物理挨次一定相同。（）

2.假如沒有提供指針類型的語言，就無法構造鏈式結構。（）

3.線性結構的特點是惟獨一個結點沒有前驅，惟獨一個結點沒有后繼，其余的結點惟獨一個前驅和后繼。（）

4.語句p=p->next完成了指針賦值并使p指針得到了p指針所指后繼結點的數(shù)據(jù)域值。（）

5.要想刪除p指針的后繼結點，我們應當執(zhí)行q=p->next；

p->next=q->next；free(q)。（）

三、填空題

1.已知P為單鏈表中的非首尾結點，在P結點后插入S結點的語句為：_______________________。

2.挨次表中規(guī)律上相鄰的元素物理位置()相鄰，單鏈表中規(guī)律上相鄰的元素物理位置_________相鄰。

3.線性表L＝（a1，a2，...，an）采納挨次存儲，假定在不同的n＋1個位置上插入的概率相同，則插入一個新元素平均需要移動的元素個數(shù)是________________________

4.在非空雙向循環(huán)鏈表中，在結點q的前面插入結點p的過程如下：p->prior=q->prior;

q->prior->next=p;

p->next=q;

______________________;

5.已知L是無表頭結點的單鏈表，是從下列提供的答案中挑選合適的語句序列，分離實現(xiàn)：

（1）表尾插入s結點的語句序列是

_______________________________

(2)表尾插入s結點的語句序列是

_______________________________

1.p->next=s;

2.p=L;

3.L=s;

4.p->next=s->next;

5.s->next=p->next;

6.s->next=L;

7.s->next=null;

8.while(p->next!=Q)?p=p-next;

9.while(p->next!=null)p=p->next;

四、算法設計題

1.試編寫一個求已知單鏈表的數(shù)據(jù)域的平均值的函數(shù)（數(shù)據(jù)域數(shù)據(jù)類型為整型）。

2.已知帶有頭結點的循環(huán)鏈表中頭指針為head,試寫出刪除并釋放數(shù)據(jù)域值為x的全部結點的c函數(shù)。

3.某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成一個循環(huán)鏈表，每個結點有價格、數(shù)量和鏈指針三個域?，F(xiàn)出庫（銷售）m臺價格為h的電視機，試編寫算法修改原鏈表。

4.某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成一個循環(huán)鏈表，每個結點有價格、數(shù)量和鏈指針三個域?，F(xiàn)新到m臺價格為h的電視機，試編寫算法修改原鏈表。

5.線性表中的元素值按遞增有序羅列，針對挨次表和循環(huán)鏈表兩種不同的存儲方式，分離編寫C函數(shù)刪除線性表中值介于a與b（a≤b）之間的元素。

6.設A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是兩個給定的線性表,它們的結點個數(shù)分離是n和m,且結點值均是整數(shù)。

若n=m，且ai=bi（0≤iB。

試編寫一個比較A和B的C函數(shù)，該函數(shù)返回-1或0或1，分離表示AB。

7.試編寫算法,刪除雙向循環(huán)鏈表中第k個結點。

8.線性表由前后兩部分性質不同的元素組成

(a0,a1,...,an-1,b0,b1,...,bm-1),m和n為兩部分元素的個數(shù),若線性表分離采納數(shù)組和鏈表兩種方式存儲,編寫算法將兩部分元素

換位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析兩種存儲方式下算法的時光和空間復雜度。

9.用循環(huán)鏈表作線性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存儲結構,頭指針分離為ah和bh，設計C函數(shù)，把兩個線性表合并成形如（a0,b0,a1,b1,…）的線性表，要求不開拓新的動態(tài)空間,利用本來循環(huán)鏈表的結點完成合并操作,結構仍為循環(huán)鏈表,頭指針為head,并分析算法的時光復雜度。

10.試寫出將一個線性表分解為兩個帶有頭結點的循環(huán)鏈表，并將兩個循環(huán)鏈表的長度放在各自的頭結點的數(shù)據(jù)域中的C函數(shù)。其中,線性表中序號為偶數(shù)的元素分解到第一個循環(huán)鏈表中,序號為奇數(shù)的元素分解到其次個循環(huán)鏈表中。

11.試寫出把線性鏈表改為循環(huán)鏈表的C函數(shù)。

12.己知非空線性鏈表中x結點的直接前驅結點為y,試寫出刪除x結點的C函數(shù)。

參考答案：

一、挑選題

1.B

2.C

3.D

4.B

5.A

6.A7、C

二、推斷題:

參考答案：1、×2、√3、×4、×5、√

三、填空題

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

2、一定；不一定

3、n/2

4、q->prior=p;

5、(1)6)3)

(2)2)9）1)7)

四、算法設計題

1、

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{intdata;

structnode*link;

}NODE;

intaver(NODE