了得網研究生_程序基本算法習題解析

編輯推薦

本書程序基本算法解析全面、經典實用、綜合性強，題目來自ACM ICPC，著重提高編程應用開發能力。本書與《程序基本算法教程哲、劉偉、鄧萬宇編著）相配套，分為兩部分。第1部分為主教材各章重點和課後習題答案，主要針對主教材各章（程序與算法、程序設計語言、數據結構、查找與排序、窮舉法、遞歸法、分治法、動態規劃法、貪心法、回溯法）的內容，介紹每章要求和知識重點，給出課後習題答案。第2部分為各類算法的習題解析，內容包括查找、窮舉法、分治、動態規劃、貪心法、回溯法和深度優先與廣度優先，題目來自ACM ICPC。附錄給出ACM算法競賽簡介、相關技術簡介和3個軟件算法競賽簡介。本書適合作為高等院校計算機軟件專業的教材或教學參考書，也可以供從事計算機應用開發的各類技術人員應用參考，或作為全國計算機等級考試、軟件技術資格與水平考試和各類軟件算法競賽的培訓資料。

內容簡介

本書與《程序基本算法教程哲、劉偉、鄧萬宇編著)相配套,分為兩部分。第1部分為主教材各章重點和課後習題答案,主要針對主教材各章(程序與算法、程序設計語言、數據結構、查找與排序、窮舉法、遞歸法、分治法、動態規劃法、貪心法、回溯法)的內容,介紹每章要求和知識重點,給出課後習題答案。第2部分為各類算法的習題解析,內容包括查找、窮舉法、分治、動態規劃、貪心法、回溯法和深度優先與廣度優先,題目來自ACMICPC。附錄給出ACM算法競賽簡介、相關技術簡介和3個軟件算法競賽簡介。
本書適合作為高等院校計算機軟件及相關專業的教材或教學參考書,也可以供從事計算機應用開發的各類技術人員應用參考,或作為全國計算機等級考試、軟件技術資格與水平考試和各類軟件算法競賽的培訓資料。

目錄
第1部分各章重點和課後習題答案
第1章程序與算法/3
1.1本章要求/3
1.2本章知識重點/3
1.2.1程序/3
1.2.2算法/3
1.2.3算法的“2、3、5”/4
1.2.4算法復雜度/5
1.2.5算法學習步驟/6
1.3課後習題答案/6第2章程序設計語言/12
2.1本章要求/12
2.2本章知識重點/12
2.2.1結構化程序設計/12

第1部分各章重點和課後習題答案

第1章程序與算法/3

1.1本章要求/3

1.2本章知識重點/3

1.2.1程序/3

1.2.2算法/3

1.2.3算法的“2、3、5”/4

1.2.4算法復雜度/5

1.2.5算法學習步驟/6

1.3課後習題答案/6第2章程序設計語言/12

2.1本章要求/12

2.2本章知識重點/12

2.2.1結構化程序設計/12

2.2.2程序執行流程/12

2.2.33種基本結構/12

2.2.43種調試工具/15

2.3課後習題答案/15第3章數據結構/17

3.1本章要求/17

3.2本章知識重點/17

3.2.1概述/17

3.2.2數據結構研究對像/17

3.2.3線性表/18

3.2.4棧和隊列/18

3.2.5二叉樹/19

3.2.6圖的遍歷/21

3.2.7短路徑/23

3.3課後習題答案/26第4章查找與排序/30

4.1本章要求/30

4.2本章知識重點/30

4.2.1查找/30

4.2.2排序/32

4.2.3排序法總結/33

4.3課後習題答案/34第5章窮舉法/40

5.1本章要求/40

5.2本章知識重點/40

5.2.1概述/40

5.2.2窮舉法分類/40

5.3課後習題答案/40第6章遞歸法/46

6.1本章要求/46

6.2本章知識重點/46

6.2.1遞歸概念/46

6.2.2棧和堆/46

6.2.3基本遞歸/47

6.2.4尾遞歸/47

6.2.5相似術語解析/48

6.3課後習題答案/48第7章分治法/52

7.1本章要求/52

7.2本章知識重點/52

7.2.1分治法概念/52

7.2.2分治法適用的情況/52

7.2.3分治法的基本步驟/53

7.3課後習題答案/53第8章動態規劃法/62

8.1本章要求/62

8.2本章知識重點/62

8.2.1動態規劃特性/62

8.2.2動態規劃分類/62

8.2.3動態規劃求解步驟/63

8.3課後習題答案/64第9章貪心法/70

9.1本章要求/70

9.2本章知識重點/70

9.2.1貪心算法概念/70

9.2.2貪心算法的兩個性質/70

9.2.3貪心算法解題步驟/71

9.2.4貪心算法和動態規劃的關繫/71

9.3課後習題答案/72第10章回溯法/79

10.1本章要求/79

10.2本章知識重點/79

10.2.1回溯概念/79

10.2.2回溯求解步驟/79

10.3課後習題答案/85

第2部分各類算法習題解析第11章查找/95

11.1尋找字符串/95

11.2小的因子對差/96

11.3能否獲勝/97

11.4能解決多少任務/99

11.5等級/100

11.6執行任務/102

11.7變化字符串的數目/104

11.8兩個人的比賽/106

11.9選擇購物券/109

11.10分蛋糕/111

11.11求先序排列/113

11.12字符串匹配/114第12章窮舉/116

12.1證明錯誤假設/116

12.2平行四邊形第4個頂點/117

12.3能否組成n/118

12.4更改時間/119

12.5捉住小偷/122

12.6Jam的計數法/124

12.7線段/126

12.8求合數和/127

12.9數字挑戰/128

12.10子字符串/130第13章分治/133

13.1排列/133

13.2組合/135

13.3線性時間選擇/137

13.4一維接近點對問題/140

13.5循環賽日程表/145第14章動態規劃/148

14.1線段覆蓋/148

14.2過河卒/149

14.3裝箱問題/151

14.4乘積/153

14.5數的劃分/154

14.6統計單詞個數/156

14.7給樹上色/159

14.8寫作業/161

14.9炸彈/164

14.10攔截導彈/166

14.11入學考試/168第15章貪心法/170

15.1均分紙牌/170

15.2胸有成竹/171

15.3今年暑假不AC/173

15.4手機控/175

15.5握手/176

15.6萬聖節/178

15.7逆序對數/179

15.8操作字符串/181

15.9喫貨/183

15.10二進制/184

15.11奶牛飛車/185

15.12多處服務/187

15.13刪除問題/189

15.14小船過河問題/190第16章回溯法/193

16.1八數碼/193

16.2素數環/194

16.3素數環的排列/196

16.4符號三角形問題/198

16.5迷宮問題/200第17章深度優先與廣度優先/204

17.1油田計數/204

17.2偽二進制/206

17.3越過山丘/207

17.4翻轉道路/210

17.5單詞接龍/212

17.6少步數/214

17.7相鄰數之和為素數/216附錄AACM算法競賽簡介/221

A.1在線判題繫統/221

A.1.1OJ介紹/221

A.1.2VJ介紹/221

A.2ACM訓練環境/221

A.2.1注冊身份/221

A.2.2訓練過程/222

A.2.3評測狀態詳解/224

A.3ACM的算法知識點/225

A.3.1初級/225

A.3.2中級/227

A.3.3高級/228附錄B相關技術簡介/231

B.1STL/231

B.1.1簡介/231

B.1.2容器/231

B.1.3算法/232

B.2頭文件/232附錄C3個軟件算法競賽簡介/233

C.1競考網/233

C.2團體程序設計天梯賽/234

C.2.1歷史背景/234

C.2.2參賽隊組成/234

C.2.3競賽規則/235

C.2.4命題與競賽評分/235

C.2.5競賽環境和競賽語言/237

C.2.6獲獎比例/237

C.2.7報名方法/238

C.3中國軟件杯/239參考文獻/240

前言

前言
本書與《程序基本算法教程哲、劉偉、鄧萬宇編著)相配套,分為兩部分,第1部分共10章，為主教材各重點和課後習題答案。第2部分共7章，給出了查找、窮舉法、分治、動態規劃、貪心法、回溯法和深度優先與廣度優先算法的習題解析,題目來自ACMICPC(ACM International Collegiate Programming Contest,ACM國際大學生程序設計競賽),讀者可注冊網站https://cn.vjudge.net/進行訓練。附錄給出ACM算法競賽、相關技術和3個軟件算法競賽的簡介。
西安郵電大學計算機學院劉偉、鄧萬宇編寫相關章節的課後習題答案。西安郵電大學計算機學院計科14級的張浩然、袁子涵、干財進在第40屆ACM國際大學生程序設計大賽東亞洲大陸子賽區總決賽ECFinal中獲得銅獎,他們編寫了第2部分。其餘章哲編寫,全哲負責大綱擬定與統稿工作。
學習程序基本算法的好方法是實踐,對於已經成型多年的經典算法,以習題為主,將抽像的理論知識應用於編碼實踐,纔能扎實地掌握,深刻地理解這些算法。本書所有程序都在Visual C 6.0下調試運行通過,建議讀者上機編寫、運行和調試本書所給的例程。

前言

本書與《程序基本算法教程哲、劉偉、鄧萬宇編著)相配套,分為兩部分,第1部分共10章，為主教材各重點和課後習題答案。第2部分共7章，給出了查找、窮舉法、分治、動態規劃、貪心法、回溯法和深度優先與廣度優先算法的習題解析,題目來自ACMICPC(ACM International Collegiate Programming Contest,ACM國際大學生程序設計競賽),讀者可注冊網站https:
//cn.vjudge.net/進行訓練。附錄給出ACM算法競賽、相關技術和3個軟件算法競賽的簡介。

西安郵電大學計算機學院劉偉、鄧萬宇編寫相關章節的課後習題答案。西安郵電大學計算機學院計科14級的張浩然、袁子涵、干財進在第40屆ACM國際大學生程序設計大賽東亞洲大陸子賽區總決賽ECFinal中獲得銅獎,他們編寫了第2部分。其餘章哲編寫,全哲負責大綱擬定與統稿工作。

學習程序基本算法的好方法是實踐,對於已經成型多年的經典算法,以習題為主,將抽像的理論知識應用於編碼實踐,纔能扎實地掌握,深刻地理解這些算法。本書所有程序都在Visual C 6.0下調試運行通過,建議讀者上機編寫、運行和調試本書所給的例程。

西安郵電大學計算機學院的李曉戈、孟偉君、陳琳、舒新峰等審閱了某些章節。西安郵電大學ACM集訓隊的楚東方、劉敏、趙偉奇、郝希烜等同學調試了相關代碼。清華大學出版社張民對本教材的寫作大綱、寫作風格等提出了很多寶貴的意見。衷心感謝上述各位的支持和幫助。在本書的寫作過程中參閱了大量中外文的專著、教材、論文、報告及網絡資料,在此向有關作者表示敬意和感謝。

本書可作為高等院校各專業學生學習程序設計和備戰軟件競賽的輔導教材,也可作為程序員和社會讀者的自學輔助用書。

由於作者水平有限,時間緊迫,本書難免有不足之處,我們誠懇期待讀者的批評指正,以使本書日臻完善。

作者

2018年3月

在線試讀

第3章數據結構〖*4/5〗3.1本章要求 掌握線性表。 掌握棧。 掌握隊列。 掌握二叉樹。 掌握圖。3.2本章知識重點〖1〗3.2.1概述數據結構是計算機存儲和組織數據的方式,是指相互之間存在著一種或多種關繫素的集合和該集合素之間的關繫，記為Data_Structure=(D,R)其中D素的集合,R是該集合素之間的關繫的有限集合。3.2.2數據結構研究對像數據結構具體指同一素的集素之間的相互關繫,包括3個組成成分: 數據的邏輯結構、數據的物理結構和數據結構的運算。1. 數據的邏輯結構數據的邏輯結構反素之間的前後件關繫,與它們在計算機中的存儲位置無關。數據的邏輯結構有以下幾種:(1) 集合。數據結素之間除了“同屬一個集合” 的相互關繫外,別無其他關繫。(2) 線性結構。數據結素存在一對一的相互關繫。(3) 樹形結構。數據結素存在一對多的相互關繫。(4) 圖結構。數據結素存在多對多的相互關繫。2. 數據的物理結構數據的物理結構是指數據在計算機存儲空間的存放形式,具體實現的方法有順序、鏈接、索引、散列等多種,一種邏輯結構可表示成多種存儲結構。3. 數據結構的運算數據結構有以下幾種常見的運算:(1) 建立(Create): 建立一個數據結構。(2) 消除(Destroy): 消除一個數據結構。(3) 刪除(Delete): 從一個數據結構中刪除一素。(4) 插入(Insert): 把一素插入到一個數據結構中。(5) 訪問(Access): 對一個數據結構進行訪問。(6) 修改(Modify): 對一個數據結構中素進行修改。(7) 排序(Sort): 對一個數據結構中素進行排序。(8) 查找(Search): 對一個數據結構中素進行查找。3.2.3線性表線性表是常用的數據結構之一,它是由n(n≥0)素(結點)組成的滿足如下條件的有限序列(a0,a1,…,an-1),具有如下特點: 當i=1,2,…,n-1時,ai有且僅有一個直接前趨ai-1。 當i=0,1,…,n-2時,有且僅有一個直接後繼ai 1。素a0沒有前趨。 素an-1沒有後繼素的個數稱為線性表長度,長度為0時稱為空表素可以是單一類型的數據,如整數、字符串等,也可以是由若干個數據項組成的結構體,如學生信息(學號、姓名、班級)等。3.2.4棧和隊列〖*4/5〗1. 棧棧是一種要求插入或刪除操作都在同一端進行的線性表,具有先進後出(FILO)的特性,素後被釋放。棧是一種線性存儲結構,它具有如下特點:(1) 棧中素遵守先進後出的原則。(2) 限定隻能在棧頂進行插入和刪除操作。棧具有如下相關概念:(1) 棧頂與棧底:素插入與刪除的一端稱為棧頂,另一端稱為棧底。(2) 進棧: 棧的插入操作,也稱壓棧、入棧。例如,一個存素的棧中依次進棧,表示為{1,2,3},如圖3.1所示。圖素1、2、3依次進棧在進棧的過程中,棧頂的位置一直在向上移動,而棧底固定不變。(3) 出棧: 棧的刪除操作,也叫作彈棧，如圖3.2所示。圖素3、2、1依次出棧出棧的順序為3、2、1,順序與進棧時相反,這就是所謂的“先進後出”。在出棧的過程中,棧頂位置一直在向下移動,而棧底一直保持不變。進棧和出棧這一對操作在某種意義上具有“記憶效應”,或者說是對稱性。一般在如下兩種情況下用到棧: ①需要保存之前的狀態; ②狀態涉及先後順序。典型的例子就是計算器,涉及運算的先後順序以及計算狀態的保存。2. 隊列隊列是隻允許在一端插入,在另一端刪除的線性表,具有先進先出(FIFO)的特性。隊列中需要注意“假溢出”的現像,當進隊和出隊反復進行後,整個隊列出現整體向後移動,隊尾指針已經移到了後,仿佛隊列已滿,而事實上隊列並未真滿,在隊頭前有空位置,如圖3.3所示。圖3.3假溢出為了解決假溢出問題,將隊列的數據區的頭尾銜接,形成頭尾相接的循環結構,此時隊頭前的空位置將可以被使用。但這樣會出現“隊滿”和“隊空”條件混淆的問題。3.2.5二叉樹二叉樹是一素的集合,該集合或者為空，或者由一個稱素及兩個不相交的左子樹和右子樹組成，如圖3.4所示。在樹形結構中素之間有著明顯的層次關繫,每一層上素可能和下一層素(孩子)相關,但卻隻能和上一層中素相關。圖3.4二叉樹1. 先序遍歷基本流程為: 若二叉樹為空,則空操作,否則,①訪問根結點; ②先序遍歷左子樹; ③先序遍歷右子樹。先序遍歷遞歸算法如下:void PreOrderTraverse(BNode p){ if(p != NULL) //若二叉樹為空,則空操作{ printf("%c",p->data); //訪問根結點PreOrderTraverse(p->lchild);//先序遍歷左子樹PreOrderTraverse(p->rchild);//先序遍歷右子樹}}2. 中序遍歷基本流程為: 若二叉樹為空,則空操作,否則,①中序遍歷左子樹; ②訪問根結點; ③中序遍歷右子樹。中序遍歷遞歸算法如下:void InOrderTraverse(BNode p){ if(p != NULL){ InOrderTraverse(p->lchild); //中序遍歷左子樹printf("%c",p->data); //訪問根結點InOrderTraverse(p->rchild); //中序遍歷右子樹}}3. 後序遍歷基本流程為: 若二叉樹為空,則空操作,否則,①後序遍歷左子樹; ②後序遍歷右子樹; ③訪問根結點。後序遍歷遞歸算法如下:void PostOrderTraverse(BNode p){ if(p != NULL){ PostOrderTraverse(p->lchild); //後序遍歷左子樹PostOrderTraverse(p->rchild); //後序遍歷右子樹printf("%c",p->data); //訪問根結點}}3.2.6圖的遍歷在圖結構中,頂點之間的關繫可以是任意的,任意兩素之間都可能相關。從圖中某個頂點出發訪遍圖中其餘頂點且僅訪問一次的過程稱為圖的遍歷。圖的遍歷有兩種方式: 深度優先遍歷和廣度優先遍歷。1. 深度優先遍歷深度優先遍歷是樹的先根遍歷的推廣。如圖3.5所示，從頂點a出發,訪問此頂點,然後依次從a的未被訪問的鄰接點出發深度優先遍歷圖,直至圖中所有和a有路徑相通的頂點都被訪問到;若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點,重復上述過程,直至圖中所有頂點都被訪問到為止。顯然,這是一個遞歸的過程。圖3.5深度優先遍歷深度優先遍歷算法如下:void DFS(Graph G,int v){ //從頂點v出發遞歸地深度優先遍歷圖Gvisited\\[v\\]=TRUE;Visit(v); //訪問頂點vfor(w=FirstAdjVex(G,v);w; w=NextAdjVex(G,v,w))if (!visited\\[w\\]) DFS(G,w); //對v 的尚未訪問的鄰接頂點w 遞歸地深度優先遍歷}2. 廣度優先遍歷廣度優先遍歷類似於樹的按層次遍歷的過程。如圖3.6所示,從圖中頂點a出發,在訪問了a之後依次訪問a的各個未曾訪問過的鄰接點,然後分別從這些鄰接點出發依次訪問它們的鄰接點,並使“先被訪問的頂點的鄰接點”先於“後被訪問的頂點的鄰接點”被訪問,直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點,重復上述過程,直至圖中所有頂點都被訪問到為止。圖3.6廣度優先遍歷廣度優先遍歷算法如下:void BFSTraverse(Graph G, Status(Visit)(int v)){ //按廣度優先遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visitedfor (v=0;v,d(v0,vi)為弧上的權值。 若不存在,d(v0,vi)為∞。步驟2: 從T中選取一個與S中頂點有關聯邊且權值小的頂點w,加入到S中。步驟3: 對T中其餘頂點的距離值進行修改:d(v0,vi)=min(d(v0,vi),d(v0,w) d(w,vi))若加進w作中間頂點,從v0到vi的距離值縮短,則修改此距離值。步驟4: 重復上述步驟2、3,直到S中包含所有頂點,即w=vi為止。算法如下:#include #include #define MAX 1000000using namespace std;int arcs\\[10\\]\\[10\\];//鄰接矩陣int D\\[10\\];//保存短路徑長度int p\\[10\\]\\[10\\];//路徑int final\\[10\\];//若final\\[i\\]= 1則說明頂點vi已在集合S中int n= 0;//頂點個數int v0= 0;//源點int v,w;void ShortestPath_DIJ(){for (v= 0; v< n; v ) //循環初始化{final\\[v\\]= 0; D\\[v\\]= arcs\\[v0\\]\\[v\\];for (w= 0; w< n; w ) p\\[v\\]\\[w\\]= 0;//設空路徑if (D\\[v\\]< MAX) {p\\[v\\]\\[v0\\]=1; p\\[v\\]\\[v\\]= 1;}}D\\[v0\\]= 0; final\\[v0\\]=0; //初始化 v0頂點屬於集合S//開始主循環,每次求得v0到某個頂點v的短路徑,並將v加到集合S中for (int i= 1; i< n; i ){int min= MAX;for (w= 0; w < n; w ){if (!final\\[w\\]) //如果頂點w在v-S中{ //這個過程終選出的點應該是當前v-S中與S有關聯邊且權值小的頂點if (D\\[w\\]< min) {v= w; min= D\\[w\\];}}}final\\[v\\]= 1; //選出該點後加到集合S中for (w= 0; w < n; w )//更新當前短路徑和距離{/在此循環中,v為當前剛選入集合S中的點,則以v為中間點考察d(v0,v) d(v,w)是否小於D\\[w\\],如果是,則更新。例如加進點3,則若要考察D\\[5\\]是否要更新,就判斷d(v0,v3) d(v3,v5)的和是否小於D\\[5\\]/if (!final\\[w\\] && (min arcs\\[v\\]\\[w\\]> n;for (int i= 0; i < n; i ){for (int j= 0; j < n; j ){cin >> arcs\\[i\\]\\[j\\];}}ShortestPath_DIJ();for (int i= 0; i < n; i ) printf("D\\[%d\\]= %d\\\
,i,D\\[i\\]);return 0;}2. 弗洛伊德算法弗洛伊德算法又稱為插點法,是一種利用動態規劃的思想尋找給定的加權圖中多源點之間短路徑的算法。弗洛伊德算法步驟如下。步驟1: 初始化短路徑。兩點之間的距離是邊的權,如果兩點之間沒有邊相連,則權為無窮大。步驟2: 對於每一對頂點 u 和 v,檢查是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是，則更新短路徑。步驟3: 把圖用鄰接矩陣G表示出來。如果從vi到vj有路可達,則G\\[i\\]\\[j\\]=d,d表示該路的長度;否則G\\[i\\]\\[j\\]=無窮大。定義一個矩陣D用來記錄所插入點的信息,D\\[i\\]\\[j\\]表示從vi到vj需要經過的路徑上的點,初始化D\\[i\\]\\[j\\]=j。把各個頂點插入圖中,比較插入頂點後的距離與原來的距離,G\\[i\\]\\[j\\]=min(G\\[i\\]\\[j\\],G\\[i\\]\\[k\\] G\\[k\\]\\[j\\]),如果G\\[i\\]\\[j\\]的值變小,則更新D\\[i\\]\\[j\\]=k。在G中包含兩點之間的短路徑的長度,在D中包含兩點間短路徑經過的點。代碼如下:#include #include #define max 1000000000int d\\[1000\\]\\[1000\\],path\\[1000\\]\\[1000\\];int main(){int i,j,k,m,n;int x,y,z;scanf("%d%d",&n,&m);for(i=1;i<=n;i )for(j=1;j<=n;j ){d\\[i\\]\\[j\\]=max;path\\[i\\]\\[j\\]=j;}for(i=1;i<=m;i ) {scanf("%d%d%d",&x,&y,&z);d\\[x\\]\\[y\\]=z;d\\[y\\]\\[x\\]=z;}for(k=1;k<=n;k )for(i=1;i<=n;i )for(j=1;j<=n;j ){if(d\\[i\\]\\[k\\] d\\[k\\]\\[j\\]%d:%d\\\
,i,j,d\\[i\\]\\[j\\]);int f, en;scanf("%d%d",&f,&en);while (f!=en){printf("%d->",f);f=path\\[f\\]\\[en\\];}printf("%d\\\
,en);return 0;}3.3課後習題答案1. 試分別以不同的存儲結構實現線性表的就地逆置算法,即在原表的存儲空間將線性表(a1,a2,…,an)逆置為(an,an-1,…,a1)。(1) 以一維數組作為存儲結構。(2) 以單鏈表作為存儲結構。【解答】(1) 用一維數組作為存儲結構。void invert(SeqList L, int num)//L為數組,num素個數{int j, tmp;for(j=0;j<=(num-1)/2;j ){tmp=L\\[j\\];L\\[j\\]=L\\[num-j-1\\];L\\[num-j-1\\]=tmp;}}(2) 用單鏈表作為存儲結構。void invert(LinkList L)//LinkList為結構體指針類型名{Node p, q, r;if(L->next==NULL) return;//鏈表為空p=L->next;q=p->next;p->next=NULL;//摘下個結點,生成初始逆置表while(q!=NULL)//從第二個結點起依次插入當前逆置表{r=q->next;q->next=L->next;L->next=q;q=r;}}2. 已知二叉樹的中序和後序遍歷序列如下,試構造該二叉樹。中序: A C B D H G E F後序: A B C D E F G H【解答】該二叉樹如圖3.7所示。圖3.7第2題所求的二叉樹3. 設二叉樹采用二叉鏈表存儲,試編寫一個求二叉樹高度的算法。【解答】int treedepth(BiTree t)//二叉樹采用二叉鏈表存儲{int hl,hr,rel;if(!t) return 0;else{hl=treedepth(t->lchild);hr=treedepth(t->rchild);rel=(hl>hr)?hl 1:hr 1;return(rel);}}4. 判斷循環隊列是否滿有哪些方法?【解答】判斷循環隊列是否滿可以采用如下兩種方法。方法1: 犧牲不用。當Q.front==Q.rear時隊列為空。當(Q.rear 1) % MAXSIZE==Q.front時隊列為滿。方法2: 標志域法。設置一個flag標志域,設flag==0時隊列空,flag==1時隊列滿。5. 設L為有序順序表,編寫一個算法刪除L中素，不能另外開闢數據存儲空間。【解答】#include #include int delduplicate(int a\\[\\],int n){int i,j,k,count;i=0;while (iadjvex\\].in ;p=p->nextarc;}}}第4章查找與排序〖*4/5〗4.1本章要求 了解查找的概念。 熟練掌握各種查找方法的原理。 實現各種查找方法。 了解排序的概念。 熟練掌握各種排序方法的原理。 實現各種排序方法。4.2本章知識重點〖1〗4.2.1查找〖*4/5〗1. 順序查找順序查找是一種簡單的查找方法。1) 算法思想順序表中的記錄都是無序的。從頭到尾或者從尾到頭沿著一個方向依次將掃素值與給定的關鍵字key相比素值與key相等,則查找成功;若掃描完所有節點,仍未找到等於key的節點,則查找失敗。2) 時間復雜度好的情況是次比較就找到,時間復雜度是O(1);而壞的情況是直到後一個記錄纔找到,或者根本沒找到,時間復雜度是O(n)。因此,順序查找平均需要查找(n 1)/2次,時間復雜度是O(n)。3) 優缺點順序表的優點就是直觀簡單。缺點是當n很大時查找的效率比較低。2. 折半查找折半查找的前提是線性表(a0,a1,…,an-1)已經按照從小到大的順序排列。具體如下所示:1) 算法思想設素的關鍵字為key,首先將查找範圍的下限設為low=0,上限為high=n-1,中點為m=(low high)/2素記為am。用key素am比較,若key=a素正為素,查找停止;若key>am,則替換下限low=mid 1,到下半段繼續查找;若keyhigh為止,low>high素未找到。2) 時間復雜度折半查找的總次數就是二叉樹的深度,n個結點的二叉樹深度為log2n 1,時間復雜度為O(log2n)。3) 優缺點折半查找的時間復雜度是O(log2n),好於順序查找的O(n)。但它的缺點就在於每次都是從表的中間開始,如果是一個很大的表,查找表的開始或結束附近的記錄就需要經過很多次查找。3. 分塊查找分塊查找是順序查找和折半查找的結合,性能介於兩者之間,但無須像折半查找那樣要求表中數據必須有序。1) 算法思想數據(a0,a1,…,an-1)均分為B塊,每一塊中的數據無須有序,但要求“分塊有序”,即前一塊中的數據必須小於後一塊中的小數據。為此,構造一個索引表index素index［i］(0≤i≤B-1)中存放第i塊的關鍵字max、該塊的起始位置start及結束位置end。分塊查找如圖4.1所示。圖4.1分塊查找2) 時間復雜度每次先找到要素所在的塊,再查找塊內的數據。設素,平均分成m個塊,每個塊素,平均查找次數就是(m 1)/2 (t 1)/2=(n/t t)/2 1≥log2n 1。所以分塊索引的時間復雜度介於O(n)和O(log2n)之間。3) 優點分塊索引兼顧了有序和無序的需求,平衡了插入、刪除和查找的性能,普遍應用於數據庫查找等方面。4.2.2排序排序是將一組無序的記錄序列調整為有序的記錄序列,排序的過程是一個逐步擴大記錄的有序序列長度的過程,如圖4.2所示。圖4.2排序的過程1. 插入類排序插入類排序將無序序列中的一個或幾個記錄插入有序序列,從而增加記錄的有序序列的長度。插入類排序又可細分為直接插入排序和折半插入排序。2. 交換類排序交換類排序的基本思想是: 通過交換無序序列中的記錄得到其中關鍵字小或的記錄,並將其加入到有序子序列中,終形成有序序列。交換類排序可分為冒泡排序和快速排序等。假設要排序的數組是A［0］,A［1］,…,A［N-1］,快速排序具體步驟如下。步驟1: 設置兩個變量i、j,排序開始的時候,i=0,j=N-1。步驟2: 以素作為關鍵數據,賦值給key,即key=A［0］。步驟3: 從j開始向前搜索,即由後開始向前搜索(j--),找到個小於key的值A［j］,將A［j］和A［i］互換。步驟4: 從i開始向後搜索,即由前開始向後搜索(i ),找到個大於key的值A［i］,將A［i］和A［j］互換。步驟5: 重復步驟3、4,直到i=j(步驟3、4中沒有找到符合條件的值,即步驟3中A［j］不小於key、步驟4中A［i］不大於key的時候,改變j、i的值,使得j=j-1,i=i 1,直至找到為止。找到符合條件的值,進行交換的時候i、j指針位置不變。另外,i==j這一過程一定正好是i 或j--完成的時候,此時令循環結束)。快速排序算法如下:void sort(int a, int left, int right){if(left>= right) {return;}int i= left;int j= right;int key= a\\[left\\];while(i< j) {while(i< j && key<= a\\[j\\]){ j--; } //向前尋找a\\[i\\]= a\\[j\\];while(i< j && key>= a\\[i\\]){ i ; } a\\[j\\]= a\\[i\\];}a\\[i\\]= key;//當在當前組內找完一遍以後就把中間數key回歸sort(a, left, i- 1);//後用同樣的方式對分出來的左邊的組進行同樣的查找sort(a, i 1, right);//用同樣的方式對分出來的右邊的組進行同樣的查找}3. 選擇類排序選擇類排序的基本思想是從記錄的無序序列中選擇關鍵字小或的記錄,並將它加入到有序序列中,終獲得整體有序序列。選擇類排序又可分為簡單選擇排序、樹形選擇排序和堆排序。4. 歸並類排序歸並排序法是將兩個(或兩個以上)有序表合並成一個新的有序表,即把待排序序列分為若干個子序列,每個子序列是有序的,然後再把有序子序列合並為整體有序序列。歸並排序的核心在於先分解再合並。4.2.3排序法總結〖*4/5〗1. 時間性能各種排序法按平均的時間性能分為如下3類:(1) 時間復雜度為O(n log2n)的排序方法有快速排序、堆排序和歸並排序,其中以快速排序的時間性能好。(2) 時間復雜度為O(n2)的排序方法有直接插入排序、冒泡排序和簡單選擇排序,其中以直接插入排序的時間性能好。(3) 時間復雜度為O(n)的排序方法隻有基數排序。2. 空間性能空間性能指的是排序過程中所需的輔助空間大小。(1) 簡單排序方法(直接插入排序、冒泡排序和簡單選擇排序)和堆排序的空間復雜度為O(1)。(2) 快速排序的空間復雜度為O(log2n),為棧所需的輔助空間。(3) 歸並排序所需輔助空間多,其空間復雜度為O(n)。3. 穩定性排序的穩定性是指對於兩個關鍵字相等的記錄,它們在序列中的相對位置在排序前後沒有改變。對於不穩定的排序方法,隻要能舉出一個實例說明即可。例如,排序前的序列為56、34、47、23、66、18、82、47,排序後的序列為18、23、34、47、47、56、66、82,則其采用的排序法是不穩定的。其中,快速排序和堆排序是不穩定的排序方法。各種常用排序算法如表4.1所示。表4.1各種常用排序算法類別排序方法時間復雜度空間復雜度平均情況好情況壞情況輔助存儲穩定性插入排序直接插入O(n2)O(n)O(n2)O(1)穩定Shell排序O(n1.5)O(n)O(n2)O(1)不穩定選擇排序直接選擇O(n2)O(n2)O(n2)O(1)不穩定堆排序O(n log2n)O(n log2n)O(n log2n)O(1)不穩定交換排序冒泡排序O(n2)O(n)O(n2)O(1)穩定快速排序O(n log2n)O(n log2n)O(n2)O(n log2n)不穩定歸並排序O(n log2n)O(n log2n)O(n log2n)O(n)穩定基數排序O(d(r n))O(d(n rd))O(d(r n))O(rd n)穩定注: 基數排序的復雜度中,r代表關鍵字的基數,d代表長度,n代表關鍵字的個數。4.3課後習題答案1. 給出一組關鍵字: 29,18,25,47,58,12,51,10,分別寫出按下列各種排序方法進行排序時的變化過程。(1) 二路歸並排序: 每歸並一次寫出一個次序。(2) 快速排序: 每劃分一次寫出一個次序。(3) 堆排序: 先建成一個堆,然後每從堆頂取素,就將堆調整一次。【解答】(1) 二路歸並排序。趟: 18,29,25,47,12,58,10,51。第二趟: 18,25,29,47,10,12,51,58。第三趟: 10,12,18,25,29,47,51,58。(2) 快速排序。趟: 10,18,25,12,29,58,51,47。第二趟: 10,18,25,12,29,47,51,58。第三趟: 10,12,18,25,29,47,51,58。(3) 堆排序。建大堆: 58,47,51,29,18,12,25,10。① 51,47,25,29,18,12,10,58。② 47,29,25,10,18,12,51,58。③ 29,18,25,10,12,47,51,58。④ 25,18,12,10,29,47,51,58。⑤ 18,10,12,25,29,47,51,58。⑥ 12,10,18,25,29,47,51,58。⑦ 10,12,18,25,29,47,51,58。2. 下面是一段C語言代碼,其中,數組a存儲了N個整數。(1) 請將對數組a進行堆排序的程序補充完整。#include #include void HeapAdjust(int a\\[ \\], int h, int s){ int rc;int j;rc=a\\[h\\];for(j= ①; j<=s; j=2){ if((j0;--i)HeapAdjust(a,i,n);for(i= n; i>1;--i){ t=a\\[1\\];a\\[1\\]=a\\[i\\];a\\[i\\]=t;⑤}}main(){int a\\[\\]={3,2,7,5,4};HeapSort(a,5);}(2) 上面的程序建成的堆是大頂堆還是小頂堆?(3) 素進行初始建堆的過程中,多進行次數據比較。【解答】（1） ① 2*h② a［h］=a［j］;③ a［h］=rc;④ n/2⑤ HeapAdjust(a,1,i-1);(2) 大頂堆。(3) n-1。3. 以單鏈表作為存儲結構實現直接插入排序算法。【解答】#define int KeyType //定義KeyType為int型typedef struct node{ KeyType key; //關鍵字域OtherInfoType info; //其他信息域 struct node  next; //鏈表中的指針域}RecNode; //記錄節點類型typedef RecNode  LinkList; //單鏈表用LinkList表示void InsertSort(LinkList head) //鏈式存儲結構的直接插入排序算法,head是帶頭節點的單鏈表{ RecNode p,q,s; if ((head->next)&&(head->next->next)) //當表中含有節點數大於1{ p=head->next->next; //p指向第二個節點head->next=NULL;q=head; //指向插入位置的前趨節點while(p)&&(q->next)&&(p->keynext->key)q=q->next;if (p){ s=p;p=p->next; //將要插入的節點摘下s->next=q->next; //插入合適位置:q節點後q->next=s;}}}4. 設計一個算法,在盡可能少的時間內重排數組,將所有關鍵字取負值的記錄放在所有關鍵字取非負值的記錄之前。請分析算法的時間復雜度。

書摘插畫

商品搜索

商品分类

【醫學】

【各大出版社】