資料結構各章複習題

2022-08-05 10:50:48 字數 4200 閱讀 7820

第一章概述

一、選擇題

1.以下哪種資料結構中任何兩個結點之間都沒有邏輯關係( )。

a.樹形結構 b.集合 c.圖形結構 d.線性結構

2.要求同一邏輯結構的所有資料元素具有相同的性質,這意味著( )。

a.資料元素具有同一的特點

b.不僅資料元素包含的資料項的個數相同,而且對應資料項的型別要一致

c.每個資料元素都一樣 d.資料元素所包含的資料項的個數要相等

3.以下說法正確的是( )。

a.資料元素是資料的最小單位b.資料項是資料的基本單位

c.資料結構是帶有結構(或稱關係)的資料項的集合 d.資料結構是帶有結構(或稱關係)的資料元素的集合

4.下面的敘述不是演算法的特性的是( )。

a.有窮性 b.輸入性 c.可行性 d.可讀性

5.下面的敘述中( )不是設計一個好的演算法應達到的目標。

a.健壯性 b.可讀性 c.高儲存量 d.正確性

6.下面運算中( )不是資料結構所具備的基本運算。

a.插入 b.排序 c.退出 d.刪除

7.資料結構是一門研究非數值計算的程式設計問題中計算機的( 1 )以及它們之間的( 2 )和運算等的學科。

(1)a.資料元素 b.計算方法  c.邏輯儲存 d.資料映像

(2)a.結構 b.關係   c.運算d.演算法

8.資料結構被形式地定義為(k,r),其中k是( 1 )的有限集,r是k上的( 2 )的有限集。

(1)a.演算法 b.資料元素 c.資料操作 d.邏輯結構

(2)a.操作 b.映像c.儲存d.關係

9.在資料結構中,從邏輯上可以把資料結構分成( )。

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

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

10.資料結構在計算機記憶體中的表示是指( )。

a.資料的儲存結構 b.資料結構 c.資料的邏輯結構 d.資料元素之間的關係

11.在資料結構中,與所使用的計算機無關的是資料的( )結構。

a.邏輯 b.儲存 c.邏輯和儲存 d.物理

12.演算法分析的目的是( 1 ),演算法分析的兩個主要方面是( 2 )。

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

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

(2)a.空間複雜度和時間複雜度 b.正確性和簡明性

c.可讀性和文件性d.資料複雜性和程式複雜性

13.計算機演算法指的是( 1 ),它必須具備輸入、輸出和( 2 )等5個特性。

(1)a.計算方法 b.排序方法 c.解決問題的有限運算序列 d.排程方法

(2)a.可行性、可移植性和可擴充性 b.可行性、確定性和有窮性

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

14.在以下的敘述中,正確的是( )。

a.線性表的線性儲存結構優於鏈式儲存結構 b.二維陣列是其資料元素為線性表的線性表

c.棧的操作方式是先進先出d.佇列的操作方式是先進後出

15.在決定選取何種儲存結構時,一般不考慮( )。

a.各結點的值如何b.結點個數的多少

c.對資料有哪些運算d.所用程式語言實現這種結構是否方便

16.在儲存資料時,通常不僅要儲存各資料元素的值,而且還要儲存( )。

a.資料的處理方法b.資料元素的型別

c.資料元素之間的關係 d.資料的儲存方法

17.下面說法錯誤的是(  )。

(1)演算法原地工作的含義是指不需要任何額外的輔助空間。

(2)在相同的規模n下,複雜度o(n)的演算法在時間上總是優於複雜度o(2n)的演算法。

(3)所謂時間複雜度是指最壞情況下,估計演算法執行的一個上界。

(4)同一個演算法,實現語句的級別越高,執行效率越低。

a.(1) b.(1)(2) c.(1)(4) d.(3)

二、填空題

1.一種資料結構在計算機記憶體中的( )稱為儲存結構。

2.資料的邏輯結構包括和( )三種結構,樹形結構和圖形結構合稱為(非線性結構)。

3.**性結構中,第一個結點( )前驅結點,其餘每個結點有且只有( )個前驅結點;最後一個結點( )後繼結點,其餘每個結點有且只有( )個後繼結點。

4.在樹形結構中,根結點沒有( )結點,其餘每個結點有且只有( )個前驅結點,葉子結點沒有( )結點,其餘每個結點的後繼結點可以( )。

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

6.線性結構中元素之間存在( )關係,樹形結構中元素之間存在( )關係,圖形結構中元素之間存在( )關係。

7.演算法的5個重要特性是輸入和輸出。

8.演算法可以用不同的語言描述,如果用c語言或pascal語言等高階語言來描述,則演算法實現上就是程式了。這種說法是( )的。

9.演算法效率分析可分為分析和分析。

10.資料結構的儲存方式有和4種。

11.資料結構包括三個組成部分。

12.資料物件是性質相同的的集合。

三、判斷題

1.順序儲存方式只能用於儲存線性結構。( )

2.資料元素是資料的最小單位。( )

3.資料結構、資料元素、資料項在計算機中的映像(或表示)分別稱為儲存結構、結點、資料域。( )

4.資料的物理結構是指資料在計算機內實際的儲存形式。( )

5.資料的邏輯結構是對資料元素之間關係的描述,它與資料元素的儲存形式無關。( )

四、問答題

1.指出下列程式段的時間複雜度

(1)i=12) i=n

while(i<=nwhile(i>=0 && a[i]!=k)

i=i*3i--;

(3) for(i=0;i for(j=0;ja[i][j]=i*jreturn (1);

else

return(n*fact(n-1)); }

2.畫出下列二元組表示的資料結構對應的邏輯圖形,並指出分別屬於何種結構。

(1)b=(k,r)

k=r=(2) c=(k,r)

k=r=第二章線性表

一、選擇題

1.連結串列不具備的特點是( )。

a.可隨機訪問任一結點b.插入刪除不需要移動元素

c.不必事先估計儲存空間 d.所需空間與其長度成正比

2.不帶頭結點的單連結串列head為空的判定條件是( )。

a.head==null b.head->next==null c.head->next==head d.head!=null

3.帶頭結點的單連結串列head為空的判定條件是( )。

a.head==null b.head->next==null c.head->next==head d.head!=null

4.帶頭結點的雙迴圈連結串列l為空表的條件是( )。

a.l==null b.l->next==null c.l->prior==null d.l->next==l

5.非空的迴圈單連結串列head的尾結點(由p所指向)滿足( )。

a.p->next==null b.p==null c.p->next==head d.p==head

6. 在迴圈雙連結串列的p所指結點之前插入s所指結點的操作是( )。

a.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;

b.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;

c.s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;

d.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;

7.若某表最常用的操作是在最後一個結點之後插入一個結點或刪除最後一個結點,則採用(  )儲存方式最節省運算時間。