資料結構習題

前言資料結構是計算機相關專業教學計畫中的一門核心課程，是有志從事計算機與技術工作的人員的一門重要的專業基礎課程。計算機相關學科各領域都要用到各種資料結構，要從事這些領域的工作，尤其是計算機應用領域的開發研製工作，必須具備良好的資料結構基礎。

資料結構課程的教學要求是學會分析研究計算機加工的資料物件的特徵，以便在實際應用中選擇適當的資料結構、儲存結構和相應的演算法，初步掌握演算法的時間與空間效能分析技巧，得到複雜程式設計的訓練。

我們在認真總結多年教學經驗和體會的基礎上，結合新時期大學生的學習特點和要求，編寫了這本《資料結構習題》，作為資料結構課程學習的配套教材，以希望通過習題的求解，使學生更好地學習和掌握課程內容，理解和掌握演算法設計所需的方法和技術，為整個專業學習打下良好的基礎。

由於時間倉促和編者水平所限，本書一定還存在著許多問題，敬請廣大讀者批評指正。

目錄第一章緒論1

第二章線性表6

第三章棧和佇列12

第四章串19

第五章陣列和廣義表22

第六章樹和二叉樹28

第七章圖33

第九章查詢38

第十章內部排序41

第一章緒論

一、選擇題

1. 演算法的計算量的大小稱為計算的（）。

a．效率b. 複雜性 c. 現實性d. 難度

2. 演算法的時間複雜度取決於（）

a．問題的規模 b. 待處理資料的初態 c. a和b

3.計算機演算法指的是（1），它必須具備（2）這三個特性。

(1) a．計算方法 b. 排序方法

c. 解決問題的步驟序列 d. 排程方法

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

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

4．乙個演算法應該是（）。

a．程式 b．問題求解步驟的描述 c．要滿足五個基本特性 d．a和c.

5. 下面關於演算法說法錯誤的是（）

a．演算法最終必須由電腦程式實現

b.為解決某問題的演算法同為該問題編寫的程式含義是相同的

c. 演算法的可行性是指指令不能有二義性

d. 以上幾個都是錯誤的

6. 下面說法錯誤的是（）

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

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

（3）所謂時間複雜度是指最壞情況下，估算演算法執行時間的乙個上界

（4）同乙個演算法，實現語言的級別越高，執行效率就越低

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

7．從邏輯上可以把資料結構分為（）兩大類。

a．動態結構、靜態結構 b．順序結構、鏈式結構

c．線性結構、非線性結構 d．初等結構、構造型結構

8．以下與資料的儲存結構無關的術語是（）。

a．迴圈佇列 b. 鍊錶 c. 雜湊表d. 棧

9．以下資料結構中，哪乙個是線性結構（）？

a．廣義表 b. 二叉樹 c. 稀疏矩陣 d. 串

10．以下那乙個術語與資料的儲存結構無關？（）

a．棧b. 雜湊表 c. 線索樹d. 雙向鍊錶

11．線性表若採用鏈式儲存結構時，要求記憶體中可用儲存單元的位址（①）。

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

c．一定是不連續的 d．連續或不連續都可以

12．在以下的敘述中，正確的是（①）。

a．線性表的線性儲存結構優於鍊錶儲存結構

b．二維陣列是其資料元素為線性表的線性表

c．棧的操作方式是先進先出

d．佇列的操作方式是先進後出

13．以下哪個資料結構不是多型資料型別（）

a．棧 b．廣義表 c．有向圖 d．字串

14．以下資料結構中，（）是非線性資料結構

a．樹 b．字串 c．隊d．棧

15. 下列資料中，（）是非線性資料結構。

a．棧 b. 佇列 c. 完全二叉樹 d. 堆

16．連續儲存設計時，儲存單元的位址（）。

a．一定連續 b．一定不連續 c．不一定連續 d．部分連續，部分不連續

17．以下屬於邏輯結構的是（）。

a．順序表 b. 雜湊表 c.有序表d. 單鏈表

18.乙個資料物件是（）的集合。

a.相同型別的資料項 b.相同型別的資料元素

c.不同型別的資料項 d.不同型別的資料元素

19. ( )是資料的基本單位。

a.資料項 b.關鍵字 c.資料元素 d.資料型別

20.資料結構在計算機中的表示稱為資料( )。

a.物件 b.的儲存結構 c.型別 d.元素

21.下列程式段的時間複雜度為( )。

)22．資料結構是一門研究非數值計算的程式設計問題中計算機的（①）以及它們之間的（②）和運算等的學科。 ①a．操作物件 b．計算方法 c．邏輯儲存 d．資料映象 ②a．結構 b．關係 c．運算 d．演算法

23．資料結構被形式地定義為（k，r），其中k是（①）的有限集合，r是k上的（②）的有限集合。 ①a．演算法 b．資料元素 c．資料操作 d．邏輯結構 ②a．操作 b．映象 c．儲存 d．關係

24．在資料結構中，從邏輯上可以把資料結構分成（①）。 a．動態結構和靜態結構b．緊湊結構和非緊湊結構 c．線性結構和非線性結構 d．內部結構和外部結構25．線性表的順序儲存結構是一種（①）的儲存結構，線性表的鏈式儲存結構是一種（②）的儲存結構。 a．隨機訪問 b．順序訪問 c．索引訪問 d．雜湊訪問 26．演算法分析的目的是（①），演算法分析的兩個主要方面是（②）。

①a．找出資料結構的合理性 b．研究演算法中的輸入和輸出的關係 c．分析演算法的效率以求改進 d．分析演算法的易懂性和文件性 ②a．空間複雜性和時間複雜性 b．正確性和簡明性 c．可讀性和文件性 d．資料複雜性和程式複雜性 27．計算機演算法指的是（①），它必具備輸入、輸出和（②）等五個特性。

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

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

②a．可行性、可移植性和可擴充性

b．可行性、確定性和有窮性

c．確定性、有窮性和穩定性

d．易讀性、穩定性和安全性

28．線性表的邏輯順序與儲存順序總是一致的，這種說法（①）。

a．正確b．不正確

二、填空題

1．資料的物理結構包括的表示和的表示。

2. 對於給定的n個元素,可以構造出的邏輯結構有（1），（2），（3），__（4）四種。

3．資料的邏輯結構是指

4．乙個資料結構在計算機中稱為儲存結構。

5．抽象資料型別的定義僅取決於它的一組__（1）_，而與_（2）_無關，即不論其內部結構如何變化，只要它的_（3）_不變，都不影響其外部使用。

6．資料結構中評價演算法的兩個重要指標是

7. 資料結構是研討資料的_（1）_和_（2）_，以及它們之間的相互關係，並對與這種結構定義相應的_（3）_，設計出相應的（4）_。

8．乙個演算法具有5個特性: （1）、（2）、（3），有零個或多個輸入、有乙個或多個輸出。

9．下面程式段的時間複雜度為n>1)

sum=1；

for (i=0;sum10．計算機執行下面的語句時，語句s的執行次數為

for(i=l；i for(j=n;j>=i;j--)

s;11.下面程式段中帶下劃線的語句的執行次數的數量級是

i：=1； while i三、基礎知識題

1．資料結構是一門研究什麼內容的學科？

2．資料元素之間的關係在計算機中有幾種表示方法？各有什麼特點？

資料結構習題

資料結構習題

資料結構習題

資料結構習題

相關推薦