資料結構習題集

《資料結構》練習冊

陝西理工學院計算機系

資料結構精品課建設小組編

電腦科學與技術系

前言《資料結構》練習冊按照《資料結構》課程的教學大綱編著，分為九章，主要題型包括：選擇題、判斷題、填空題和程式題，每章都從基礎出發，有少部分難度較大題型。編寫的目的是為了給學生提供乙個練習和提高的平台。

可作為我校電腦科學與技術、資訊系統與資訊管理與網路工程本科專業學生的輔助教材使用。由於編寫時間較倉促，有錯誤在所難免，敬請教師和學生提出寶貴意見。

電腦科學與技術系《資料結構》課程組

2023年8月

第一章緒論

一、選擇題

1.組成資料的基本單位是（）

a．資料項 b．資料型別 c．資料元素 d．資料變數

2.資料結構是研究資料的（）以及它們之間的相互關係。

a．理想結構，物理結構 b．理想結構，抽象結構

c．物理結構，邏輯結構 d．抽象結構，邏輯結構

3.在資料結構中，從邏輯上可以把資料結構分成（）。

a．動態結構和靜態結構 b．緊湊結構和非緊湊結構

c．線性結構和非線性結構 d．內部結構和外部結構

4.資料結構是一門研究非數值計算的程式設計問題中計算機的（①）以及它們之間的（②）和運算等的學科。

①a．資料元素 b．計算方法 c．邏輯儲存 d．資料映像

②a．結構 b．關係 c．運算 d．演算法

5.演算法分析的兩個主要方面是（）。

a．資料複雜性和程式複雜性 b．正確性和簡明性

c．可讀性和簡明性 d．空間複雜性和時間複雜性

6.演算法分析的目的是（）。

a．找出資料結構的合理性 b．研究演算法中的輸入和輸出的關係

c．分析演算法的效率以求改進 d．分析演算法的易懂性和文件性

7.計算機演算法指的是（①）,它必須具備輸入、輸出和（②）等5個特性。

①a．計算方法 b．排序方法

c．解決問題的有限運算序列 d．排程方法

②a．可執行性，可移植性和可擴充性 b．可行性，確定性和有窮性

c．確定性、有窮性和穩定性 d．易讀性、穩定性和安全性

二、判斷題

1.資料的機內表示稱為資料的儲存結構。（）

2.演算法就是程式。（）

3.資料元素是資料的最小單位。（）

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

5.演算法的時間複雜度取決於問題的規模和待處理資料的初態。（）

三、填空題

1.資料邏輯結構包括和________四種型別,其中樹形結構和圖形結構合稱為________。

2.**性結構中,第乙個結點________前驅結點,其餘每個結點有且只有________個前驅結點；最後乙個結點________後續結點,其餘每個結點有且只有________個後續結點。

3.在樹形結構中,樹根結點沒有________結點,其餘每個結點有且只有________個前驅結點；葉子結點沒有________結點,其餘每個結點的後續結點可以

4.在圖形結構中,每個結點的前驅結點數和後續結點數可以

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

6.演算法的五個重要特性是

7.資料結構的三要素是指和________。

8.鏈式儲存結構與順序儲存結構相比較,主要優點是

9.設有一批資料元素,為了最快的儲存某元素,資料結構宜用________結構,為了方便插入乙個元素,資料結構宜用________結構。

四、演算法分析題

1.求下列演算法段的語句頻度及時間複雜度

for(i=1; i<=n; i++)

for(j =1; j <=i ; j++)

x=x+1;

分析：該演算法為乙個二重迴圈，執行次數為內、外迴圈次數相乘，但內迴圈次數不固定，與外迴圈有關，因些，時間頻度t(n)=1+2+3+…+n=n*(n+1)/2

有 1/4≤t(n)/n2≤1，故它的時間複雜度為ｏ(n2), 即ｔ(n)與n2 數量級相同。

2.分析下列演算法段的時間頻度及時間複雜度

for （i=1;i<=n;i++）

for (j=1;j<=i;j++)

for ( k=1;k<=j;k++)

x=i+j-k;

分析演算法規律可知時間頻度t(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)

由於有1/6 ≤ t（n）/ n3 ≤1，故時間複雜度為ｏ(n3)

一、選擇題

1.乙個線性表第乙個元素的儲存位址是100,每個元素的長度為2,則第5個元素的位址是( )。

a．110 b．108 c．100 d．120

2.向乙個有127個元素的順序表中插入乙個新元素並保持原來順序不變，平均要移動（）個元素。

a．64 b．63 c．63.5 d．7

3.線性表採用鏈式儲存結構時，其位址（）。

a．必須是連續的 b．部分位址必須是連續的

c．一定是不連續的 d．連續與否均可以

4.在乙個單鏈表中，若p所指結點不是最後結點，在p之後插入s所指結點，則執行（）。

a．s->next=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所指結點的後續結點，則執行（）。

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．資料元素 d．資料項

二、判斷題

1.線性表的鏈結儲存，表中元素的邏輯順序與物理順序一定相同。（）

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

3.線性結構的特點是只有乙個結點沒有前驅，只有乙個結點沒有後繼，其餘的結點只有乙個前驅和後繼。（）

4.語句p=p->next完成了指標負值並使p指標得到了p指標所指後繼結點的資料域值。（）

5.要想刪除p指標的後繼結點，我們應該執行q=p->next ； p->next=q->next； free(q)。（）

三、填空題

1.已知p為單鏈表中的非首尾結點，在p結點後插入s結點的語句為

2.順序表中邏輯上相鄰的元素物理位置( )相鄰，單鏈表中邏輯上相鄰的元素物理位置________相鄰。

3.線性表l＝（a1，a2，...，an）採用順序儲存，假定在不同的n＋1個位置上插入的概率相同，則插入乙個新元素平均需要移動的元素個數是________。

4.在非空雙向迴圈鍊錶中，在結點q的前面插入結點p的過程如下：

p->prior=q->prior;

q->prior->next=p;

p->next=q;

________;

5.已知l是無表頭結點的單鏈表，是從下列提供的答案中選擇合適的語句序列，實現：

表尾插入s結點的語句序列是________。

a．p->next=s; b．p=l;

c．l=s; d．p->next=s->next;

e．s->next=p->next; f．s->next=l;

g．s->next=null; h．while(p->next!=0) p=p->next;

i．while(p->next!=null) p=p->next;

四、演算法設計題

1.試編寫乙個求已知單鏈表的資料域的平均值的函式（資料域資料型別為整型）。

2.已知帶有頭結點的迴圈鍊錶中頭指標為head,試寫出刪除並釋放資料域值為x的所有結點的c函式。

3.某百貨公司倉庫中有一批電視機，按其**從低到高的次序構成乙個迴圈鍊錶，每個結點有**、數量和鏈指標三個域。現出庫（銷售）m臺**為h的電視機，試編寫演算法修改原鍊錶。

4.某百貨公司倉庫中有一批電視機，按其**從低到高的次序構成乙個迴圈鍊錶，每個結點有**、數量和鏈指標三個域。現新到m臺**為h的電視機，試編寫演算法修改原鍊錶。

5.線性表中的元素值按遞增有序排列，針對順序表和迴圈鍊錶兩種不同的儲存方式，分別編寫c函式刪除線性表中值介於a與b（a≤b）之間的元素。

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

若n=m，且 ai= bi （0≤i若n若存在乙個j， jb。

試編寫乙個比較a和b的c函式，該函式返回 -1或 0或 1，分別表示 ab。

7.試編寫演算法,刪除雙向迴圈鍊錶中第k個結點。

8.線性表由前後兩部分性質不同的元素組成(a0,a1,...,an-1,b0,b1,...

,bm-1),m和n為兩部分元素的個數,若線性表分別採用陣列和鍊錶兩種方式儲存,編寫演算法將兩部分元素換位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析兩種儲存方式下演算法的時間和空間複雜度。

9.用迴圈鍊錶作線性表(a0,a1,...,an-1)和（b0,b1,...

,bm-1）的儲存結構,頭指標分別為ah和bh，設計c函式，把兩個線性表合併成形如（a0,b0,a1,b1,…）的線性表，要求不開闢新的動態空間,利用原來迴圈鍊錶的結點完成合併操作,結構仍為迴圈鍊錶,頭指標為head,並分析演算法的時間複雜度。

資料結構習題集

資料結構習題集

資料結構習題集

《資料結構》習題集粹

相關推薦