本文格式為Word版，下載可任意編輯——清華大學出版社數(shù)據(jù)結構（C版）（第2版）課后習題答案最全整理第1章緒論課后習題講解

1.填空

⑴（）是數(shù)據(jù)的基本單位，在計算機程序中尋常作為一個整體進行考慮和處理。

數(shù)據(jù)元素

⑵（）是數(shù)據(jù)的最小單位，（）是探討數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位。數(shù)據(jù)項，數(shù)據(jù)元素

數(shù)據(jù)結構指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關系。

⑶從規(guī)律關系上講，數(shù)據(jù)結構主要分為（）、（）、（）和（）。集合，線性結構，樹結構，圖結構

⑷數(shù)據(jù)的存儲結構主要有（）和（）兩種基本方法，不管哪種存儲結構，都要存儲兩方面的內容：（）和（）。

順序存儲結構，鏈接存儲結構，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關系

⑸算法具有五個特性，分別是（）、（）、（）、（）、（）。有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性

⑹算法的描述方法尋常有（）、（）、（）和（）四種，其中，（）被稱為算法語言。

自然語言，程序設計語言，流程圖，偽代碼，偽代碼

⑺在一般狀況下，一個算法的時間繁雜度是（）的函數(shù)。問題規(guī)模

⑻設待處理問題的規(guī)模為n，若一個算法的時間繁雜度為一個常數(shù)，則表示成數(shù)量級的形式為（），若為n*log25n，則表示成數(shù)量級的形式為（）。Ο(1)，Ο(nlog2n)

用大O記號表示算法的時間繁雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。

2.選擇題

⑴順序存儲結構中數(shù)據(jù)元素之間的規(guī)律關系是由（）表示的，鏈接存儲結構中的數(shù)據(jù)元素之間的規(guī)律關系是由（）表示的。A線性結構B非線性結構C存儲位置D指針C，D

順序存儲結構就是用一維數(shù)組存儲數(shù)據(jù)結構中的數(shù)據(jù)元素，其規(guī)律關系由存儲位置（即元素在數(shù)組中的下標）表示；鏈接存儲結構中一個數(shù)據(jù)元素對應鏈表中的一個結點，元素之間的規(guī)律關系由結點中的指針表示。

⑵假設有如下遺產繼承規(guī)則：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產；子女間不能相互繼承。則表示該遺產繼承關系的最適合的

數(shù)據(jù)結構應當是（）。A樹B圖C線性表D集合B

將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出規(guī)律結構圖。

⑶算法指的是（）。

A對特定問題求解步驟的一種描述，是指令的有限序列。B計算機程序C解決問題的計算方法D數(shù)據(jù)處理A

計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有A是算法的確鑿定義。

⑷下面（）不是算法所必需具備的特性。A有窮性B確鑿性C高效性D可行性C

高效性是好算法應具備的特性。

⑸算法分析的目的是（），算法分析的兩個主要方面是（）。A找出數(shù)據(jù)結構的合理性B研究算法中輸入和輸出的關系C分析算法的效率以求改進D分析算法的易讀性和文檔性E空間性能和時間性能F正確性和簡明性

G可讀性和文檔性H數(shù)據(jù)繁雜性和程序繁雜性C，E

3.判斷題

⑴算法的時間繁雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。錯。時間繁雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。

⑵每種數(shù)據(jù)結構都具備三個基本操作：插入、刪除和查找。錯。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結構。

⑶所謂數(shù)據(jù)的規(guī)律結構指的是數(shù)據(jù)之間的規(guī)律關系。錯。是數(shù)據(jù)之間的規(guī)律關系的整體。

⑷規(guī)律結構與數(shù)據(jù)元素本身的內容和形式無關。對。因此規(guī)律結構是數(shù)據(jù)組織的主要方面。

⑸基于某種規(guī)律結構之上的基本操作，其實現(xiàn)是唯一的。

錯。基本操作的實現(xiàn)是基于某種存儲結構設計的，因而不是唯一的。

4.分析以下各程序段，并用大O記號表示其執(zhí)行時間。

⑴基本語句是k=k+10*i，共執(zhí)行了n-2次，所以T(n)=O(n)。⑵基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。

⑶分析條件語句，每循環(huán)一次，i+j整體加1，共循環(huán)n次，所以T(n)=O(n)。⑷設循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最終T(n)=y，即：(T(n)+1)2≤n，所以T(n)=O(n1/2)。⑸x++是基本語句，所以

5．設有數(shù)據(jù)結構（D，R），其中D={1,2,3,4,5,6}，

R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫出其規(guī)律結構圖并指出屬于何種結構。

其規(guī)律結構圖如圖1-3所示，它是一種圖結構。

6.為整數(shù)定義一個抽象數(shù)據(jù)類型，包含整數(shù)的常見運算，每個運算對應一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。整數(shù)的抽象數(shù)據(jù)類型定義如下：ADTintegerData

整數(shù)a：可以是正整數(shù)(1,2,3,