數(shù)據(jù)結(jié)構(gòu)習題解答綜述

1、第 1 章習題解答1.1 什么是數(shù)據(jù)結(jié)構(gòu)？一個數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)的二元組定義形式是什么樣的？舉例解釋其 含義。解答概括地說， 數(shù)據(jù)結(jié)構(gòu)是互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 也就是說， 數(shù)據(jù)結(jié)構(gòu)是由某個數(shù) 據(jù)元素的集合和該集合中的數(shù)據(jù)元素之間的關(guān)系組成的， 因此數(shù)據(jù)結(jié)構(gòu)可以用一個二元組來 表示。例如， B=( D， R)，其中 D是某一數(shù)據(jù)元素的集合， R是 D上的關(guān)系的有限集。 R 所 表示的是集合 D 的數(shù)據(jù)元素之間的邏輯關(guān)系，它表示的可能是數(shù)據(jù)元素之間客觀存在的某 種聯(lián)系， 也可能是為了處理問題的需要而人為組織的數(shù)據(jù)元素之間的某種關(guān)系，因此， 稱之為數(shù)據(jù)的邏輯結(jié)構(gòu)。 例如，一個農(nóng)歷節(jié)氣表， 就構(gòu)成了一

2、個數(shù)據(jù)結(jié)構(gòu)， 其數(shù)據(jù)元素是一年的 農(nóng)歷二十四節(jié)氣， 數(shù)據(jù)元素之間的關(guān)系是節(jié)氣的時間先后關(guān)系。 又如， 一個某年級學生的成 績排序表， 也是一個數(shù)據(jù)結(jié)構(gòu)， 其數(shù)據(jù)元素是包含成績項的該年級的學生記錄， 數(shù)據(jù)元素之 間的關(guān)系是學生之間的成績高低關(guān)系。 為了在計算機中進行數(shù)據(jù)處理， 必須把從實際問題中 抽象出來的數(shù)據(jù)的邏輯結(jié)構(gòu)映象到計算機的存儲器中，即要把抽象出來的數(shù)據(jù)元素集合 D 和數(shù)據(jù)元素之間的關(guān)系存儲到計算機的存儲器中， 稱之為數(shù)據(jù)的物理結(jié)構(gòu)或存儲結(jié)構(gòu)， 它是 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示。1.2 假設 R 是集合 M 上的一個關(guān)系， R 的定義是什么？對實際問題而言，其含義是 什么？ 解答

3、如果 R是對集合 M 自身的笛卡爾積所取的一個子集， 那么我們就說 “R是集合 M 上的 一個關(guān)系”。對實際問題而言，它表示的是集合 M 中元素的某種相關(guān)性。例如，對于參加一 個羽毛球比賽的運動員集合， 可以用一個二元關(guān)系表示出各場比賽的勝負關(guān)系。 對于一組課 程的集合，可以用一個二元關(guān)系表示出各門課程之間的先修和后續(xù)關(guān)系等等。1.3 設有集合 M=d1,d 2,d 3,d 4,d 5 上的一個關(guān)R=(d 1,d 2),(d 2,d 4),(d 4,d 5),(d 2,d 5),(d 1,d 4),(d 1,d 5),(d 3,d 5),(d 1,d 3) ，試說明關(guān)系 R具有什么樣的性質(zhì)。

4、解答 從二元關(guān)系的基本性質(zhì)容易驗證，該關(guān)系 R是反自反的、反對稱的、傳遞的關(guān)系。 因為關(guān)系 R中沒有 (di,d i )這樣的元素，所以它是反自反的。因為關(guān)系 R中沒有 (元素 di ,d j )和(d j,d i )同時存在的情況，所以它是反對稱的。 關(guān)系 R 的傳遞性表現(xiàn)在：有元素 (d 1,d 2),(d 2,d 4) ，同時有元素 (d 1,d 4), 有元素 (d 1,d 2),(d 2,d 5) ，同時有元素 (d 1,d 5),有元素 (d 1,d 3),(d3,d 5) ，同時有元素(d1,d 5)，有元素 (d 1,d 4),(d4,d 5) ，同時有元素(d1,d 5)，有

5、元素 (d 2,d 4),(d4,d 5) ，同時有元素(d 2,d 5) 。1.4 什么是線性結(jié)構(gòu)？什么是非線性結(jié)構(gòu)？舉例說明。 解答線性結(jié)構(gòu)與非線性結(jié)構(gòu)是針對數(shù)據(jù)的邏輯結(jié)構(gòu)而言的。 它們的主要區(qū)別是： 線性結(jié)構(gòu)表 示的是數(shù)據(jù)元素之間一對一的關(guān)系， 而非線性結(jié)構(gòu)表示的是數(shù)據(jù)元素之間一對多或多對多的 關(guān)系。線性結(jié)構(gòu)具有以下特點： 存在唯一的沒有前驅(qū)、只有一個直接后繼的“頭”元素； 存在唯一的沒有后繼、只有一個直接前驅(qū)的“尾”元素； 除了“頭”元素和“尾”元素之外，集合中的每個元素有且只有一個直接前驅(qū)、 有且只有一個直接后繼。由以上特點可以看出，線性結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系，結(jié)構(gòu)中的

6、數(shù)據(jù) 元素依照它們的邏輯關(guān)系可以排成一個有“頭” 、有“尾”的序列。例如，前面所說的農(nóng)歷 節(jié)氣表，就是一個線性結(jié)構(gòu)，它是一個從“春分”開始，然后是“雨水”， ，最后是“大寒”。這樣一個序列。除線性結(jié)構(gòu)以外的結(jié)構(gòu)稱為非線性結(jié)構(gòu)。在非線性結(jié)構(gòu)中，各數(shù)據(jù)元素的關(guān)系不一定 保持一個線性序列， 每個數(shù)據(jù)元素可能與零個或多個數(shù)據(jù)元素有聯(lián)系。 也就是說， 非線性結(jié) 構(gòu)中的數(shù)據(jù)元素之間存在一對多或者是多對多的關(guān)系。例如， 一個學校的教學組織關(guān)系可以構(gòu)成一個有明顯層次的數(shù)據(jù)結(jié)構(gòu)：學校下屬有若干學院， 每個學院下設若干個系， 每個系有多個研究所和教研組，有若干的學生班， 這個一對 多的關(guān)系的抽象就是非線性結(jié)構(gòu)。又

7、如， 對一個銷售系統(tǒng)的各個連鎖店及相互之間的聯(lián)系的抽象是一個非線性結(jié)構(gòu)，這個數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素是各連鎖店， 數(shù)據(jù)元素之間的關(guān)系是各連鎖店之間的聯(lián)系， 因為各連 鎖店之間都可以有聯(lián)系， 顯然各連鎖店之間的聯(lián)系是多對多的聯(lián)系。 也就是說， 每一個連鎖 店都可以與其余多個連鎖店發(fā)生聯(lián)系。這個結(jié)構(gòu)也是非線性結(jié)構(gòu)。1.5 數(shù)據(jù)的存儲結(jié)構(gòu)有哪幾種？其中最常用的有哪幾種？說明它們的特點。 解答 數(shù)據(jù)存儲結(jié)構(gòu)也稱物理結(jié)構(gòu)， 它是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示。 數(shù)據(jù)的存儲結(jié)構(gòu) 有順序存儲、鏈式存儲、 索引存儲、 散列存儲四種方式。 其中最常用的存儲結(jié)構(gòu)有順序存儲 和鏈式存儲兩種。在順序存儲方式中， 要開辟一

8、塊連續(xù)的存儲空間來存放數(shù)據(jù)結(jié)構(gòu)； 對每個數(shù)據(jù)元素給以 等長的數(shù)據(jù)單元，結(jié)構(gòu)中的數(shù)據(jù)元素按照它們之間的邏輯順序依次存放于連續(xù)的內(nèi)存單元 中。順序存儲方式的特點是除了存儲數(shù)據(jù)元素以外， 不必耗費另外的空間， 數(shù)據(jù)元素之間的 關(guān)系是由數(shù)據(jù)元素在存儲器中的鄰接關(guān)系來表示的。 由于數(shù)據(jù)元素在存儲器中的物理順序和 它們之間的邏輯順序一致，因此這種存儲方式是非常直觀的一種存儲方式。在鏈式存儲方式中， 數(shù)據(jù)元素可以存放在不連續(xù)的內(nèi)存單元中， 數(shù)據(jù)元素在存儲器中的 物理存放順序可以和邏輯順序不一致， 數(shù)據(jù)元素之間的邏輯關(guān)系是通過指示數(shù)據(jù)元素存儲地 址的指針來表示的。因此，每個數(shù)據(jù)元素除了存儲自身以外，同時還要存

9、儲指示其后件（ 或前件 ）的存儲地址的指針，它們構(gòu)成一個結(jié)點。也就是說，在鏈式存儲方式中每個數(shù)據(jù)元素 的存儲映象是一個結(jié)點， 它包括存儲數(shù)據(jù)元素的數(shù)據(jù)域 （ 也稱作值域 ）和存儲指針的指針域兩 部分，通過各結(jié)點的指針把各數(shù)據(jù)元素按照它們的邏輯關(guān)系鏈成一條“鏈” ，從而清晰的表 示了數(shù)據(jù)元素之間的邏輯關(guān)系。 鏈式存儲的明顯優(yōu)點是存儲空間的利用比較靈活， 數(shù)據(jù)元素 的增減操作比較方便。除了上述兩種常用的存儲方式以外，還有索引存儲和散列存儲方式。在索引存儲方式中， 按照某種性質(zhì)把一個大表的元素劃分成若干個子表， 使每個子表中 的元素具有相同的性質(zhì)。 存儲時以子表為單位存放， 同時建立一個索引表， 索

10、引表中的每個 索引項對應一個子表， 指出該子表的起始地址、 長度和子表的性質(zhì)， 這樣能夠給查找等操作帶來很大的方便。 顯然， 在該存儲方式下數(shù)據(jù)元素之間的邏輯關(guān)系是通過數(shù)據(jù)元素在索引表 中的位置得以反映的。在散列存儲方式中， 通過數(shù)據(jù)元素的關(guān)鍵字值來確定數(shù)據(jù)元素的存儲位置， 因而可以直 接通過計算查找到相應的數(shù)據(jù)元素。使得它比通過“比較”查找有更高的效率。1.6 設數(shù)據(jù)元素的集合為 D=a1,a2,a3,a4,a5,a6 ，請分別畫出與以下各關(guān)系 R 對應 的數(shù)據(jù)結(jié)構(gòu) B=(D,R) 的結(jié)構(gòu)示意圖，并指出它屬于哪類結(jié)構(gòu)。(1)R=(a 3,a 4),(a 4,a 5),(a 1,a 2),(a

11、2,a 3),(a5,a 6)(2)R=(a 3,a 2),(a 2,a 4),(a 3,a 1),(a2,a 5),(a2,a 6)(3)R=(a i+1 ,a i ) i=5,4,3,2,1(4)R=(a i ,aj)ij(5)R= 解答(1) 為線性結(jié)構(gòu)，其圖形表示如圖 1-1 (a) 所示。(2) 為非線性結(jié)構(gòu)，其圖形表示如圖 1-1 (b) 所示。(3) 為線性結(jié)構(gòu)，其圖形表示如圖 1-1(c) 所示。(4) 非線性結(jié)構(gòu)，其圖形表示如圖 1-1(d) 所示。(5) 集合結(jié)構(gòu)，除了同屬一個集合外，數(shù)據(jù)元素間無其他關(guān)系。(a) (c)(b)(d)圖 1-11.7 什么是抽象數(shù)據(jù)類型？ 抽

12、象數(shù)據(jù)類型和面向?qū)ο蟮某绦蛟O計方法有什么關(guān)系？ 解答 抽象數(shù)據(jù)類型是指用以表示應用問題的一個數(shù)據(jù)模型以及定義在該模型上的一組操作。它與一般的數(shù)據(jù)類型的概念在本質(zhì)上是一致的， 都是對數(shù)據(jù)類型的數(shù)學特性的抽象， 其目的 是可以使程序設計者， 在程序設計中更專注于數(shù)據(jù)的邏輯特性， 而不必關(guān)心抽象數(shù)據(jù)類型實 現(xiàn)的具體細節(jié)。 但抽象數(shù)據(jù)類型比一般數(shù)據(jù)類型的抽象層次更高、 范疇更廣， 它不局限于計 算機系統(tǒng)中已定義和實現(xiàn)的數(shù)據(jù)類型， 通常它是由用戶根據(jù)實際問題的需要而定義， 且通過 計算機系統(tǒng)中已經(jīng)定義的數(shù)據(jù)類型來表示和實現(xiàn)。 因此，它是基于一般數(shù)據(jù)類型的更高層次 上的一種數(shù)據(jù)抽象。抽象數(shù)據(jù)類型的概念是由

13、于程序設計方法和技術(shù)的發(fā)展而提出來的。 為了更好的提高軟 件模塊的可復用性和可擴充性， 現(xiàn)代程序設計方法強調(diào)以數(shù)據(jù)為基礎(chǔ)來構(gòu)建軟件系統(tǒng)， 更加強調(diào)“封裝”和“信息隱蔽” 策略。面向?qū)ο蟮某绦蛟O計方法正是符合這種要求的方法。 “類” 是面向?qū)ο蟮某绦蛟O計方法中的核心概念， 它是數(shù)據(jù)抽象的結(jié)果， 類不但體現(xiàn)了封裝和信息 隱蔽的原則， 而且具有繼承性， 因而為模塊的復用提供了很好的條件。 抽象數(shù)據(jù)類型具有封 裝和信息隱蔽的特點， 可以做到使用與實現(xiàn)分離。 由此可見， 抽象數(shù)據(jù)類型與面向?qū)ο蟮姆?法的思想是一致的， 從抽象數(shù)據(jù)類型出發(fā)來進行面向?qū)ο蟮某绦蛟O計， 會使程序設計更加順 理成章。1.8 完成

14、以下問題：(1) 設計二次多項式 ax2+bx+c 的一種抽象數(shù)據(jù)類型，其數(shù)據(jù)部分為多項式的三個系數(shù) 項 a、 b、c；操作部分包括：初始化數(shù)據(jù)成員 a、 b、c，實現(xiàn)兩個多項式相加，給定 x 求多 項式的值，求方程 ax2+bx+c=0 的兩個實根，按照 ax*2+bx+c 的格式輸出二次多項式。(2) 假定數(shù)據(jù)成員 a、b、 c 定義如下：typedef struct float a,b,c ; Quadratic ;請寫出上述各操作的具體實現(xiàn)。 解答 (1) 對題中的二次多項式抽象數(shù)據(jù)類型可以作以下定義：ADT Quadratic 數(shù)據(jù)： 一元二次多項式的二次項系數(shù) a，一次項系數(shù) b，

15、常數(shù)項 c；其結(jié)構(gòu)類型為： Quadratic 操作：/ 初始化一元二次多項式Quadratic *InitQuadratic (flaot aa, float bb, float cc)/ 兩個多項式相加/ 計算一元二次多項式的值/ 求一元二次方程的兩個實根/ 按指定格式輸出多項式Quadratic *Add (Quadratic *f1, Quadratic *f2 ) ； float Value (Quadratic *f, float x) ； int Root (quadratic *f, float& r1, float& r2)；void print (Quadratic *f)

16、 ；(2) 數(shù)據(jù)成員定義和指定的操作的實現(xiàn)如下： 數(shù)據(jù)成員定義：typedef struct float a, b, c ； Quadratic ；數(shù)據(jù)成員初始化：Quadratic *InitQuadratic (flaot aa, float bb, float cc ) Quadratic *f ；f-a=aa； f-b=bb ； f-c=cc ； return f ；兩個二次多項式相加：Quadratic *Add ( Quadratic *f1, Quadratic *f2 ) Quadratic *f ；f-a=f1-a + f2-a ；f-b=f1-b + f2-b ；f-c=f

17、1-c + f2-c ；return f ；由給定的 x ，求二次多項式的值：float Value (Quadratic *f, float x ) return (f-a*x*x+f-b*x+f-c )；求一元二次方程的實根：int Root (quadratic f, float *r1, float *r2 )float d ;if (f-a=0) return 1 ；d=f-b*f-b-4*f-a*f-c ；if (d=0) r1=(-f-b+sqrt(d)/(2*f-a) ； r2=(-f-b-sqrt(d)/(2*f-a) ； return 1 ；else return 0 ；

18、按照要求的形式輸出二次多項式： void print (Quadratic *f ) if (f.a) printf ( %f x*2 , f.a ) ；if (f.b ) if (f.b0 ) printf ( +%f x , f.b ) ；else printf ( %f x , f.b ) ；if (f.c ) if (f.c0 ) printf ( +%f , f.c ) ；else printf ( %f , f.c ) ；printf ( n ) ；1.9 算法的基本特征是什么？算法分析主要針對哪些方面？ 解答 算法是解決問題方案的準確而完整的描述。 它是為解決某一特定問題而確定的

19、一個指令 序列。算法具有以下的特性：(1) 有窮性。 一個算法必須在執(zhí)行有窮步之后結(jié)束， 而且每一步都應該能夠在有限時間 內(nèi)完成。(2) 確定性。算法中的每一步含義都必須是確切的、 無歧義的。 并且在任何情況下算法 只有一條唯一的執(zhí)行路徑。(3) 可執(zhí)行性。算法中描述的運算都應該能夠準確的執(zhí)行。(4) 有輸入。一個算法應該有 0 個或多個取自于特定對象的集合的輸入。(5) 有輸出。一個算法應該有 0 個或多個經(jīng)算法計算得到輸出。對同一個問題可以設計出不同的算法， 各個算法特點不同， 性能也會不一樣， 因而對一 個算法需要進行性能的分析。對算法的性能分析包括算法的正確性、可讀性、健壯性、 執(zhí)行

20、效率等方面， 但通常對算法的分析主要是針對算法的執(zhí)行效率進行分析， 即對算法執(zhí)行時的 時間和空間代價進行分析比較，也就是分析算法的時間復雜度和空間復雜度。1.10 分治法與減治法的思路有什么相同之處？又有什么不同？ 解答 分治法和減治法的共同之處是，它們都是在“分而治之” 思想的指導下發(fā)展起來的， 基本思路就是把一個規(guī)模較大的問題劃分為若干個規(guī)模較小的子問題，通過對子問題的求 解，得到原問題的解。但分治法和減治法又各自適用于不同的情況， 因此它們的求解過程有所不同。 用分治法 求解的問題，所劃分的子問題是互相獨立的，且原問題的解需要由各子問題的解合并而成。 因此， 需要對各子問題分別求解，并合

21、并子問題的解，才能得到原問題的解?？梢杂脺p治法 求解的問題，雖然也要對原問題進行劃分，但因為原問題的或者解只在其中一個子問題中， 或者是只與其中的一個子問題的解之間有著某種對應關(guān)系， 因此只要對相關(guān)的一個子問題進 行求解，就可以得到原問題的解。當然它也就不存在合并解的過程?？梢哉f，減治法是一種 退化了的分治法。1.11 簡述回溯法的基本思想，采用這種算法的關(guān)鍵是什么？ 解答 回溯法是一種有組織的系統(tǒng)化搜索問題解的技術(shù)，它是對窮舉搜索的改進，其采用的 是“向前走， 碰壁回頭” 思想。 具體的說， 首先要對問題進行分析， 確定問題的所有可能解， 即確定問題的解空間， 然后沿著所確定的路線搜索向前搜

22、索。 在搜索過程中， 對每一步得到 的部分解進行判斷， 如果該部分解有可能構(gòu)成一個完整解， 說明這一步走得通， 則繼續(xù)向前 走，也就是進一步構(gòu)造問題解。否則，說明“此路不同” ，則需要回退，找另一條路線再搜 索，也就是回溯，從新的路線上繼續(xù)構(gòu)造問題的解。由回溯法的求解過程可以看出， 采用回溯法的關(guān)鍵是確定正確的解空間， 即確定解的搜 索范圍，并確定搜索的路線，只有做到這兩步，才可能有效地對問題解進行搜索。例如，“給定一個正整數(shù)集合 X= x 1, x2, , xn 和一個正整數(shù) y，求集合 X 的一個子集Y ，使得 Y 中的元素之和等于 y?！保@個問題可以采用回溯法來求解。其求解思路是：從

23、X 集合中依次選取各元素并將其與 Y 中的元素相加，考察相加結(jié)果。具體做法是：初始子集 Y 為空，其元素和等于 0；選取 x1 ，將其與子集 Y 的元素和相加，檢查結(jié)果 :若相加結(jié)果大于 y，則放棄當前所選 xi ：若 X 中還有后續(xù)元素，繼續(xù)選取 xi+1 再試；否則，回溯：放棄 xi 之前一個選中的元素，繼續(xù)向后選??；若相加結(jié)果小于 y，做 Y=Y+xi ，繼續(xù)向后選取 xi+1 再試； 若相加結(jié)果等于 y，輸出 Y 中的元素。由于這個問題的解空間比較明確(求 X 的子集)，因此，實現(xiàn)這個回溯算法的關(guān)鍵，是 確定求滿足條件的子集的思路確定對當前項xi 取或舍的準則。 即，確定對 x1, x

24、2, , xn 求和的順序以及判斷當前和是否滿足條件的準則。 確定了這兩個條件， 這個回溯算法的搜索路線 也就確定了。算法思路也就明確了。1.12 簡述貪心法和動態(tài)規(guī)劃法思路的異同。 解答 貪心法和動態(tài)規(guī)劃法都是用于解決多階段決策的最優(yōu)化問題?；镜那蠼馑悸?，都是 把一個復雜的問題分解為若干子問題， 通過對子問題求解的一系列的決策或選擇， 最后得到 原問題的解。但是， 兩者的決策方法不相同。 貪心法總是把原問題分解為一系列較為簡單的局部最優(yōu) 選擇， 每一步選擇都是在當前狀態(tài)下做出的最優(yōu)選擇， 同時擴展了當前的部分解， 直到求得 問題的完整解。 這個貪心選擇過程是以自頂向下的方式進行的， 即從原

25、問題出發(fā)， 每做一步 貪心選擇都把問題簡化為規(guī)模更小的子問題， 直到對規(guī)模最小的子問題做出貪心選擇。 動態(tài) 規(guī)劃法中， 分解成的子問題具有兩個特點。其一， 子問題之間往往不是互相獨立的，而是有 重疊的部分，這種重疊關(guān)系通過動態(tài)規(guī)劃函數(shù)表現(xiàn)出來，為了避免對重疊部分的重復計算， 以表格形式保存每一步對子問題的求解結(jié)果， 當需要再次求解已經(jīng)解決的子問題時， 只要做 簡單的查表操作即可。 其二， 每個子問題對應決策過程的一個階段， 每步所做的決策往往依 賴于相關(guān)子問題的解，因此，只有在解決了相關(guān)的子問題之后，才能做出決策或選擇。 正因 為此，其求解子問題時， 通常以自底向上的方式進行， 即從求解最后分

26、解得到的子問題開始， 逐層向前，最后求得原問題的解。1.13 什么是算法的漸近時間復雜度？如何分析一個算法的漸近時間復雜度？ 解答 算法的漸近時間復雜度是對算法的時間效率的度量。 也就是對一個算法執(zhí)行所需要的時 間進行分析。 一個算法執(zhí)行所需要的具體時間與所使用的計算機系統(tǒng)的軟、 硬件性能及問題 的規(guī)模等因素有關(guān)。 為了比較算法本身的時間性能， 應該采用能夠反映算法本身的時間性能 的度量。實際上，通常算法運行所需要的時間 T是問題規(guī)模 n的函數(shù)，可記為 T(n) 。所謂 算法的漸近時間復雜度， 是當問題規(guī)模充分大時， 算法運行時間的增長趨勢的度量。 因為增 長率的上限對算法的比較更具意義， 所

27、以經(jīng)常分析的是算法運行時間的增長率的上限， 這就 是算法的時間復雜度的大 O 表示，也常簡稱為算法的時間復雜度。為了分析一個算法的時間復雜度， 一般情況下需要考察算法中基本語句的執(zhí)行次數(shù)， 找 出其與問題規(guī)模 n 的函數(shù)關(guān)系 f(n) ，從而得到算法的漸近時間復雜度。所謂基本語句是執(zhí) 行次數(shù)與算法的執(zhí)行次數(shù)成正比的語句， 它是算法中的關(guān)鍵操作。 算法的基本語句大多包含 在循環(huán)和遞歸結(jié)構(gòu)中， 對于單循環(huán)結(jié)構(gòu)， 循環(huán)體中的簡單語句就是基本語句， 其執(zhí)行次數(shù)的大 O 表示就是該算法段的漸近時間復雜度；對于并列的循環(huán)結(jié)構(gòu)，要先分析各個循環(huán) 結(jié)構(gòu)的漸近時間復雜度， 然后利用大 O表示法的加法規(guī)則求出算法

28、的時間復雜度； 對于多層 嵌套的循環(huán)結(jié)構(gòu)， 最內(nèi)層循環(huán)中的簡單語句就是算法的基本語句， 要自外向內(nèi)逐層分析各層 循環(huán)的漸近時間復雜度， 再利用大 O表示法的乘法規(guī)則來求出算法的漸近時間復雜度。對于遞歸結(jié)構(gòu)， 則可以根據(jù)遞歸過程遞推出基本語句的執(zhí)行次數(shù)， 進而得到它的大 O表示。總之， 只要分析求出算法中關(guān)鍵操作的執(zhí)行次數(shù)與問題規(guī)模的函數(shù)關(guān)系， 也就得到了該次數(shù)的大 O 表示，從而也就求出了算法的漸近時間復雜度。1.14 什么是算法的漸近空間復雜度？如何分析一個算法的漸近空間復雜度？ 解答 算法的漸近空間復雜度是對算法的空間效率的度量。 也就是對一個算法執(zhí)行所需要的存 儲空間進行分析。 一個算法

29、執(zhí)行時所需要的空間包括幾個方面， 如存儲程序指令所需要的空 間，存儲輸入數(shù)據(jù)的空間等。 與分析算法的時間復雜度類似， 為了能夠反映一個算法的空間 性能，要排除與算法性能無關(guān)的存儲空間需求，僅考慮算法執(zhí)行時所需要的輔助存儲空間 , 因為它直接與算法的空間性能有關(guān)。 一個算法執(zhí)行時所需要的輔助存儲空間量也可以表示為 問題規(guī)模 n 的函數(shù)，其大 O 表示稱之為算法的漸近時間復雜度。 也簡稱為算法的空間復雜度。根據(jù)上述概念， 分析算法的漸近空間復雜度就是要考察和分析算法執(zhí)行時所需要的臨時 工作單元、 動態(tài)使用的空間、 遞歸工作棧所占空間等輔助空間的需求量， 然后將其表示為問 題規(guī)模的函數(shù)，也就是用大

30、O 表示法表示它，即可得到算法的漸近空間復雜度。1.15 給以下程序加上必要的注釋，指出其功能，并分析時間復雜度和空間復雜度。解答(1) int sum (int n ) int i, j, p, s=0 ；/ s 存放 n! 的累加和for (i=1 ；i=n ；i+) p=1 ；for ( j=1 ； j=i ； j+) p* = j ； / p 存放 n!s+=p；return s ；功能：求 n! 的累加和。算法的時間復雜度： 該算法中反映其執(zhí)行時間的操作是內(nèi)循環(huán)中的求階乘語句， 其執(zhí)行 次數(shù)為： 1+2+ +n =n(n+1)/2 ，算法的時間復雜度為： O(n2) 。算法的空間復雜

31、度：原地工作，即 O(1) 。(2) int fac ( int n ) int i, p=1, s= 0 ；for ( i=1 ；i=n； i+) p*= i ；/ 求 n!s+= p ； / s 存放 n! 的累加和return s ；功能： n! 的累加和 算法的時間復雜度：循環(huán)中的求階乘及其累加和語句的執(zhí)行次數(shù)為n，算法的時間復雜度為 O(n) 。算法的空間復雜度：原地工作，即O(1) 。(3) void writ ( int n ) if (n!= 0 ) writ (n-1) ； / n 層遞歸，從 1 開始執(zhí)行 n 次輸出 printf (%d n , n ) ；return ；

32、功能：采用遞歸，依次輸出自然數(shù) 1到 n 算法的時間復雜度： n 層遞歸執(zhí)行 n 次輸出，算法的時間復雜度為 O(n)。 算法的空間復雜度：由遞歸棧的深度決定，遞歸棧深度為n，所以算法的空間復雜度為O(n) 。(4) void Order ( float a, int k, int m ) int i ;flaot temp ;/ 選出 a中 k 到 m的最小元素，放于 k 位置/ k 指向下一個位置/ 執(zhí)行遞歸，對剩余元素選出最小的放于 k 位置if ( km ) for ( i=k ； i=m ； i+ )if ( ai0 ) j =flag-1; flag= 0 ；/ fiag 標 志

33、本 趟 掃 描 是 否 有 交 換 發(fā) 生 ， / 并記錄最后一次發(fā)生的位置/ 有交換發(fā)生，繼續(xù)做for ( i=0; i ai+1) temp= ai ；ai= ai+1 ；/ 使相鄰元素正序ai+1= temp ；flag= i ；功能：對數(shù)組 a中的元素 a0到 an-1 做冒泡排序。 算法的時間復雜度：最好情況下，數(shù)組 a 中的元素全部為正序，只需一趟掃描，做 n-1 次比較， 沒有交換 發(fā)生。其時間復雜度為 O(n) ；最壞情況下，數(shù)組 a 中的元素全部為逆序，需要 n-1 趟掃描，共經(jīng)過(n-1)+(n-2)+ +2+1 次比較交換操作，其時間復雜度為O(n2)；平均情況下，比較交

34、換操作的次數(shù)約為最壞情況的一半，其時間復雜度為O(n2)。算法的空間復雜度：原地工作，即 O(1) 。上機練習思路提示1.1 采用兩種不同的算法，找出數(shù)組 an(n=2 , k 1) 中的最大元素，說明兩種算法 所采用的設計方法及其特點。參考算法 ：本題可以采用多種方法來解決，以下給出幾種不同的求解算法。 采用一趟選擇 , 選出最大元素 :ElemType Select_max1 (ElemType a, int n ) int i, max= 0 ； / max 記錄最大元素所在的下標，初始取第 1 個元素位置 for ( i=1 ； in ； i+ )/ 將 amax 與數(shù)組中元素比較并記大者的位置到 maxif ( amax ai ) max= i ；return ( amax ) ；/ 返回最大元素值該算法對全部數(shù)組元素進行一遍掃描， 比較 n-1 次，只需做一次交換， 數(shù)據(jù)移動次數(shù)少。 采用一趟冒泡 , 得到最大元素 : ElemType Select_max2 (E