數據結構(C語言版第2版_李云清)習題答案2012-12.doc

第 1 章 緒論

1.1 什么是數據結構？

【答】：數據結構是指按一定的邏輯結構組成的一批數據，使用某種存儲結構將這批數據存儲 于計算機中，并在這些數據上定義了一個運算集合。

1.2 數據結構涉及哪幾個方面？

【答】：數據結構涉及三個方面的內容，即數據的邏輯結構、數據的存儲結構和數據的運算集 合。

1.3 兩個數據結構的邏輯結構和存儲結構都相同，但是它們的運算集合中有一個運算的定義不 一樣，它們是否可以認作是同一個數據結構？為什么？

【答】：不能，運算集合是數據結構的重要組成部分，不同的運算集合所確定的數據結構是不 一樣的，例如，棧與隊列它們的邏輯結構與存儲結構可以相同，但由于它們的運算集合不一樣， 所以它們是兩種不同的數據結構。

1.4 線性結構的特點是什么？非線性結構的特點是什么？

【答】：線性結構元素之間的關系是一對一的，在線性結構中只有一個開始結點和一個終端結 點，其他的每一個結點有且僅有一個前驅和一個后繼結點。而非線性結構則沒有這個特點，元 素之間的關系可以是一對多的或多對多的。

1.5 數據結構的存儲方式有哪幾種？

【答】：數據結構的存儲方式有順序存儲、鏈式存儲、散列存儲和索引存儲等四種方式。

1.6 算法有哪些特點？它和程序的主要區別是什么？

【答】：算法具有(1)有窮性(2)確定性(3)0 個或多個輸入(4)1 個或多個輸出(5)可 行性等特征。程序是算法的一種描述方式，通過程序可以在計算機上實現算法。

1.7 抽象數據類型的是什么？它有什么特點？

【答】：抽象數據類型是數據類型的進一步抽象，是大家熟知的基本數據類型的延伸和發展。 抽象數據類型是與表示無關的數據類型，是一個數據模型及定義在該模型上的一組運算。對一 個抽象數據類型進行定義時，必須給出它的名字及各運算的運算符名，即函數名，并且規定這 些函數的參數性質。一旦定義了一個抽象數據類型及具體實現，程序設計中就可以像使用基本 數據類型那樣，十分方便地使用抽象數據類型。抽象數據類型的設計者根據這些描述給出操作 的具體實現，抽象數據類型的使用者依據這些描述使用抽象數據類型。

1.8 算法的時間復雜度指的是什么？如何表示？

【答】：算法執行時間的度量不是采用算法執行的絕對時間來計算的，因為一個算法在不同的 機器上執行所花的時間不一樣，在不同時刻也會由于計算機資源占用情況的不同，使得算法在 同一臺計算機上執行的時間也不一樣，另外，算法執行的時間還與輸入數據的狀態有關，所以 對于算法的時間復雜性，采用算法執行過程中其基本操作的執行次數，稱為計算量來度量。算 法中基本操作的執行次數一般是與問題規模有關的，對于結點個數為 n 的數據處理問題，用 T(n)表示算法基本操作的執行次數。為了評價算法的執行效率，通常采用大寫 O 符號表示算法 的時間復雜度，大寫 O 符號給出了函數 f 的一個上限。其它義如下：

定義：f (n)=O (g (n)) 當且僅當存在正的常數 c 和 n0，使得對于所有的 n≥n0，有 f (n) ≤c g(n)。

2

上述定義表明，函數 f 頂多是函數 g 的 c 倍，除非 n 小于 n0。因此對于足夠大的 n (如 n≥n0)， g 是 f 的一個上限(不考慮常數因子 c)。在為函數 f 提供一個上限函數 g 時，通常使用比較 簡單的函數形式。比較典型的形式是含有 n 的單個項(帶一個常數系數)。表 1-1 列出了一些 常用的 g 函數及其名稱。對于表 1-1 中的對數函數 logn，沒有給出對數基，原因是對于任何大 于 1 的常數 a 和 b 都有 logan =logbn/logba,所以 logan 和 logbn 都有一個相對的乘法系數 1/logba， 其中 a 是一個常量。

表 1-1 常用的漸進函數

函數名稱

1常數

logn對數

n線性

nlognn 個 logn

n2平方

n3立方

2n指數

n!階乘

1.9 算法的空間復雜度指的是什么？如何表示？

【答】：算法的空間復雜度是指算法在執行過程中占用的額外的輔助空間的個數。可以將它表 示為問題規模的函數，并通過大寫O符號表示空間復雜度。

1.10 對于下面的程序段，分析帶下劃線的語句的執行次數，并給出它們的時間復雜度 T(n)。 (1) i++;

(2) for(i=0;i

if (a[i]

(3)for(i=0;i

for(j=0;j

printf(“%d”,i+j);

(4)for (i=1;i<=n-1;i++) { k=i;

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

if(a[j]>a[j

總結

以上是生活随笔為你收集整理的23V3有这种C语言表达式吗,数据结构(C语言版第2版_李云清)习题答案2012-12.doc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。