數(shù)據(jù)結(jié)構(gòu)C描述介紹資料

1、數(shù)據(jù)結(jié)構(gòu)(sh j ji u) C語(yǔ)言描述 特色解析清華大學(xué)(qn hu d xu)計(jì)算機(jī)系 殷人昆教材介紹共一百二十七頁(yè)講座(jingzu)內(nèi)容教材(jioci)編寫(xiě)背景教材編寫(xiě)的考慮學(xué)習(xí)的綱領(lǐng)各章知識(shí)點(diǎn)、特色與疑難問(wèn)題2共一百二十七頁(yè)新書(shū)(xnsh) 數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言描述 分析3共一百二十七頁(yè)教材編寫(xiě)(binxi)背景目前市場(chǎng)上用 C 描述的數(shù)據(jù)結(jié)構(gòu)教材太多了，為什么華章約我寫(xiě)這樣一本書(shū)？我想，主要是看重我教學(xué)經(jīng)驗(yàn)。到底我在數(shù)據(jù)結(jié)構(gòu)方面有什么經(jīng)驗(yàn)？我自己也有些困惑，不過(guò)，在清華BBS網(wǎng)站“水木清華”上學(xué)生對(duì)我的評(píng)價(jià)相當(dāng)正面?；仡櫼酝?，我第一次學(xué)習(xí)(xux)數(shù)據(jù)結(jié)構(gòu)，是1978年，起步與赫赫

2、有名的大師嚴(yán)蔚敏、許卓群、楊冬青等應(yīng)是同一年代，何況嚴(yán)蔚敏的第一本教材還借走了我的筆記呢。4共一百二十七頁(yè)不過(guò)，有一段時(shí)間我參與了 VLSI CAD 數(shù)據(jù)庫(kù)的研發(fā)，1985年去了日本，做了兩年客座研究員，方向是“軟件質(zhì)量管理”，轉(zhuǎn)向了軟件工程方向，回國(guó)后成了鄭人杰老師本科生“軟件工程”課程的B角。1990年鄭人杰老師調(diào)動(dòng)工作到了清華同方，我就成了該課程的A角，直到2006年把課程交給留美歸國(guó)的白曉穎老師。在1985年前，曾確定我擔(dān)任嚴(yán)蔚敏老師“數(shù)據(jù)結(jié)構(gòu)”的B角，為此我還做了些準(zhǔn)備。出國(guó)后換了人，前系主任唐澤圣、周立柱都曾擔(dān)任過(guò)B角，但因?yàn)?yn wi)某些原因，先后離開(kāi)了。5共一百二十七頁(yè)19

3、91年重新讓我擔(dān)任該課程的B角，為爭(zhēng)取學(xué)校的一類課建立梯隊(duì)。此前我已經(jīng)擔(dān)負(fù) 3 年全校非計(jì)算機(jī)專業(yè)二學(xué)位數(shù)據(jù)結(jié)構(gòu)教學(xué)，與嚴(yán)蔚敏老師的配合比較順利，大課一年一輪換，今年上大課來(lái)年上小班輔導(dǎo)課。直到1998年嚴(yán)老師退休，我開(kāi)始擔(dān)任A角。此外，應(yīng)北大老師相邀，從1996年起在京海研修學(xué)院為高教自考學(xué)生上“數(shù)據(jù)結(jié)構(gòu)”課程，為保證通過(guò)率，安排了80個(gè)學(xué)時(shí)講課，教材先后用過(guò) 3 本， 感覺(jué)把數(shù)據(jù)結(jié)構(gòu)的邊邊角角都講到了，通過(guò)率每年都在65%以上(yshng)，年年受獎(jiǎng)。6共一百二十七頁(yè)高教自考指定(zhdng)教材北大許卓群楊冬青(dngqng)等編中科大黃劉生編北大張乃校編7共一百二十七頁(yè)通過(guò)研究高教自考

4、的考試試題，總結(jié)了不少在各個(gè)知識(shí)點(diǎn)學(xué)生容易忽視的細(xì)節(jié)，這對(duì)我的教學(xué)積累幫助不小，后來(lái)雖然不去了，但我與北大孫家潚老師、丁文魁老師、張乃孝老師建立了友誼。1996年，美籍華人學(xué)者冀中田再次來(lái)華講學(xué)(jing xu)，系主任周立柱問(wèn)及在美國(guó)現(xiàn)在以什么語(yǔ)言上數(shù)據(jù)結(jié)構(gòu)課，冀中田推薦了C+。因此，周立柱老師決策上C+的數(shù)據(jù)結(jié)構(gòu)，并啟動(dòng)教材編寫(xiě)，由于我有積極性，決定讓我來(lái)寫(xiě)。當(dāng)時(shí)，我和鄭人杰正在與美國(guó)Grand Valley State University終身教授陶永雷合作編寫(xiě)實(shí)用軟件工 8共一百二十七頁(yè)程（第二版），順理成章開(kāi)始數(shù)據(jù)結(jié)構(gòu) 用面向?qū)ο蠓椒ê虲+描述的合作。我們優(yōu)選的原版英文教材是E.Ho

5、rowitz, S.Sahni & D.Mehta在1995年出版的Fundamentals of data structure in C+，它的特點(diǎn)是章節(jié)編排順序與嚴(yán)蔚敏的教材一致，便于中國(guó)老師接受，作者都是名家，內(nèi)容比較權(quán)威，面向?qū)ο笏惴ㄈ菀组喿x。編寫(xiě)工作(gngzu)十分吃力，還用了 3 位SRT的學(xué)生使用當(dāng)時(shí)流行的Borland C+調(diào)試算法。遺憾的是，許多調(diào)試通過(guò)的算法后來(lái)用Visual C+編譯不過(guò)去（系統(tǒng)兼容問(wèn)題），給學(xué)生造成學(xué)習(xí)困難。 9共一百二十七頁(yè)經(jīng)過(guò)56年的教學(xué)實(shí)踐，我們開(kāi)始改版。這次是清華信息學(xué)院出面，在全院范圍組織了課程教學(xué)組，參加者包括計(jì)算機(jī)、電子、自動(dòng)化、微納電子

6、等系數(shù)據(jù)結(jié)構(gòu)教師(jiosh)，以計(jì)算機(jī)系為主，編寫(xiě)數(shù)據(jù)結(jié)構(gòu) 用面向?qū)ο蠓椒ê虲+描述（第二版）教材。由于有了教學(xué)經(jīng)驗(yàn)和教訓(xùn)，這次編寫(xiě)比較順利，在講解上更加清晰，在技術(shù)細(xì)節(jié)上避開(kāi)了許多語(yǔ)言或編譯上的陷阱，選用了一些新出現(xiàn)的算法。由于多人合作，還會(huì)有些夾纏不清的或出現(xiàn)矛盾的情節(jié)，多謝許多熱心讀者幫助我們解決問(wèn)題。10共一百二十七頁(yè)直到第 4 次印刷后才算松了一口氣，絕大多數(shù)問(wèn)題都解決了。由于以上經(jīng)歷，完成好華章(huzhng)交給的任務(wù)有把握的也是對(duì)我教學(xué)經(jīng)驗(yàn)的一個(gè)總結(jié)。11共一百二十七頁(yè)教材編寫(xiě)(binxi)的考慮數(shù)據(jù)結(jié)構(gòu)到底有什么(shn me)用？它是敲門磚你要進(jìn)電腦公司嗎？業(yè)務(wù)考試必考數(shù)

7、據(jù)結(jié)構(gòu)。你要深造嗎？計(jì)算機(jī)專業(yè)考研、考博必考數(shù)據(jù)結(jié)構(gòu)。你要出國(guó)嗎？進(jìn)外國(guó)大學(xué)計(jì)算機(jī)專業(yè)必考數(shù)據(jù)結(jié)構(gòu)。你要獲得上級(jí)的青睞嗎？聽(tīng)話，出活是必須的，要出活如何少得了數(shù)據(jù)結(jié)構(gòu)。12共一百二十七頁(yè)它是解決問(wèn)題必不可少的世界上很多問(wèn)題的解決都可以歸結(jié)到離散問(wèn)題。解決問(wèn)題的手段是建模（數(shù)學(xué)模型抽象思維），模型求解的根本是算法（計(jì)算思維），算法設(shè)計(jì)的基礎(chǔ)是數(shù)據(jù)結(jié)構(gòu)，算法實(shí)現(xiàn)的基礎(chǔ)是程序設(shè)計(jì)。沃斯說(shuō)：算法+數(shù)據(jù)結(jié)構(gòu)=程序。進(jìn)一步說(shuō)：高效的算法+適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)+程序語(yǔ)言的熟練運(yùn)用=卓越的程序系統(tǒng)(xtng)。系統(tǒng)開(kāi)發(fā)能力就是如此。13共一百二十七頁(yè)學(xué)好數(shù)據(jù)結(jié)構(gòu)要靠什么？責(zé)任感學(xué)習(xí)不能無(wú)目標(biāo)，讓你學(xué)什么就學(xué)(jix

8、u)什么。學(xué)習(xí)涉及的是一種人生觀或價(jià)值觀，涉及你將來(lái)在社會(huì)上扮演什么角色。戰(zhàn)斗精神學(xué)習(xí)像打仗，沒(méi)有免費(fèi)的午餐。不靠拼命如何攻克堡壘，不能三天打漁兩天曬網(wǎng)。實(shí)踐精神學(xué)習(xí)不能光靠讀書(shū)，要多做題。能力是知識(shí)在應(yīng)用中運(yùn)用的體現(xiàn)。14共一百二十七頁(yè)創(chuàng)新精神問(wèn)題的求解需要運(yùn)用已學(xué)到的知識(shí)，問(wèn)題的解決可以舉一反三。特別是算法。嚴(yán)謹(jǐn)精神知識(shí)有系統(tǒng)性。學(xué)習(xí)就是一個(gè)系統(tǒng)工程，每一步(y b)學(xué)習(xí)，都在為后續(xù)的學(xué)習(xí)鋪墊；每一個(gè)知識(shí)點(diǎn)都在后續(xù)的知識(shí)點(diǎn)或其他課程中用到。團(tuán)隊(duì)和奉獻(xiàn)精神一個(gè)合唱隊(duì)，若一個(gè)聲音高亢得超出所有聲音，此合唱必定不和諧。要互相幫助。15共一百二十七頁(yè)這本數(shù)據(jù)結(jié)構(gòu)教材是寫(xiě)給誰(shuí)的？數(shù)據(jù)結(jié)構(gòu)的知識(shí)體系難

9、嗎？不難。每一個(gè)知識(shí)點(diǎn)看起來(lái)如此簡(jiǎn)單，像一個(gè)個(gè)音符(ynf)一樣；然而匯集起來(lái)，以最佳方案解決問(wèn)題就不那么簡(jiǎn)單了。想把這些知識(shí)點(diǎn)用好，就像把音符(ynf)恰到好處地安排到適當(dāng)?shù)奈恢?，奏出最悅耳的音?lè)，這就是我們的目的。這本教材想把最基本的知識(shí)體系介紹給讀者且讓讀者能夠切實(shí)理解它，掌握它。據(jù) 3 年來(lái)批閱計(jì)算機(jī)考研聯(lián)考試卷的體會(huì)，不少考試基本功訓(xùn)練不足，亟待有人引路。16共一百二十七頁(yè)本教材完全遵照全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考考試大綱安排，并參照教育部計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)高等學(xué)校計(jì)算機(jī)專業(yè)人才專業(yè)能力構(gòu)成與培養(yǎng)的要求，以專業(yè)基礎(chǔ)能力培養(yǎng)為目標(biāo)，承續(xù)程序設(shè)計(jì)基礎(chǔ)課程

10、，培養(yǎng)基本計(jì)算思維能力，提高算法設(shè)計(jì)和程序?qū)崿F(xiàn)能力，并為提高系統(tǒng)開(kāi)發(fā)能力打下良好的基礎(chǔ)?；境霭l(fā)點(diǎn)：采用“工科”思維，啟發(fā)學(xué)生(xu sheng)掌握“化復(fù)雜為簡(jiǎn)單”的方式，從問(wèn)題入手，通過(guò)“問(wèn)題/子問(wèn)題”分解，尋找解決方案； 17共一百二十七頁(yè)對(duì)基本知識(shí)點(diǎn)講深講透，通過(guò)多種應(yīng)用舉例，讓學(xué)生了解不同問(wèn)題需要采取什么方法來(lái)應(yīng)對(duì)；通過(guò)大量習(xí)題，從不同視點(diǎn)不同層面訓(xùn)練學(xué)生，見(jiàn)多才能識(shí)廣，才能培養(yǎng)出聯(lián)想能力，提高分析問(wèn)題、解決問(wèn)題的能力；配合輔助教材數(shù)據(jù)結(jié)構(gòu)(sh j ji u)習(xí)題精析與考研輔導(dǎo)，提供了多達(dá)600多題的參考答案和解析，并就關(guān)鍵點(diǎn)進(jìn)行點(diǎn)撥；另外，提供了多套模擬題。 18共一百二十七頁(yè)本

11、教材采用C語(yǔ)言作為數(shù)據(jù)結(jié)構(gòu)及算法的描述工具，適當(dāng)采用C+的少量語(yǔ)句以簡(jiǎn)化程序。算法描述力求結(jié)構(gòu)化，注重編程風(fēng)格，每個(gè)算法基本保持在100行之內(nèi)，可讀性強(qiáng)。本教材是從作者多年在清華大學(xué)計(jì)算機(jī)系講授的“數(shù)據(jù)結(jié)構(gòu)”課程的教材和課件中取材，并經(jīng)過(guò)一定改編而成，因此在敘述上適合學(xué)生的特點(diǎn)，在內(nèi)容上淺顯易懂，在選材上舍棄了很多超出規(guī)范和大綱的內(nèi)容，增加了許多在老教材中忽略了的內(nèi)容，應(yīng)該不會(huì)辜負(fù)讀者的期望。 由于2012年考研大綱增加了“外排序”的內(nèi)容，相應(yīng)(xingyng)補(bǔ)充內(nèi)容可從華章網(wǎng)站下載。19共一百二十七頁(yè)參考(cnko)教材（國(guó)外）20共一百二十七頁(yè)參考(cnko)教材（國(guó)內(nèi)）21共一百二十七

12、頁(yè)學(xué)習(xí)(xux)的綱領(lǐng)數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課程，為業(yè)界做系統(tǒng)開(kāi)發(fā)提供了不可或缺的技術(shù)和知識(shí)，是計(jì)算機(jī)專業(yè)考研的重頭科目。數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)有幾點(diǎn)重要的經(jīng)驗(yàn)提供給大家參考(cnko)。注重概念抓住特點(diǎn)學(xué)會(huì)算法拓展應(yīng)用22共一百二十七頁(yè)注重概念從考研情況分析(fnx)，試題涉及的內(nèi)容都很基本，沒(méi)有很深很難的內(nèi)容，所以要重視概念的學(xué)習(xí)：牢記定義。結(jié)構(gòu)定義有規(guī)范寫(xiě)出的，有言外隱藏的和引伸的概念。注意傳承。某些結(jié)構(gòu)與其他結(jié)構(gòu)間有傳承關(guān)系，有變種關(guān)系。區(qū)分層次。分清邏輯的和物理的結(jié)構(gòu)，以及它們之間的關(guān)系。挖掘細(xì)節(jié)。細(xì)節(jié)可提供更多解題的知識(shí)。23共一百二十七頁(yè)抓住特點(diǎn)每種結(jié)構(gòu)有它的特點(diǎn)和用途，這

13、對(duì)于在解題中應(yīng)使用哪種結(jié)構(gòu) (who)，在何時(shí) (when)，何種場(chǎng)合(where)使用，以及如何 (how) 使用有重要作用(zuyng)。理解結(jié)構(gòu)的行為特征。明確每種結(jié)構(gòu)的行為特征，例如棧是先進(jìn)后出，隊(duì)列是先進(jìn)先出的，可幫助在解題時(shí)作出選擇。理解結(jié)構(gòu)的應(yīng)用背景。知道每種結(jié)構(gòu)常在什么場(chǎng)合做什么用，可適時(shí)作出適當(dāng)選擇。理解結(jié)構(gòu)的聲明方式。在適當(dāng)時(shí)機(jī)合理地定義它們，可減少算法邏輯的混亂。24共一百二十七頁(yè)學(xué)會(huì)(xuhu)算法包括結(jié)構(gòu)的必要操作（初始化、建立、銷毀、遍歷、插入、刪除）的實(shí)現(xiàn)和常用算法（查找、排序）、算法設(shè)計(jì)（迭代、遞歸、分治、回溯）的設(shè)計(jì)與分析?；緮?shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方式。主要是數(shù)據(jù)結(jié)

14、構(gòu)的存儲(chǔ)方式定義和相應(yīng)操作的程序?qū)崿F(xiàn)。常用算法的設(shè)計(jì)。包括設(shè)計(jì)的三階段（基本思想、算法框架、程序?qū)崿F(xiàn)）。算法的簡(jiǎn)單分析。掌握時(shí)間復(fù)雜性的分析技能和附加存儲(chǔ)空間的計(jì)算。25共一百二十七頁(yè)拓展(tu zhn)應(yīng)用每種結(jié)構(gòu)都有許多應(yīng)用場(chǎng)合，有不同應(yīng)用目的和應(yīng)用方式。每種算法也可變通以適用于不同的問(wèn)題求解。明確問(wèn)題求解的步驟。掌握問(wèn)題求解的三階段：分析(弄懂題意)、設(shè)計(jì)(考慮解決方案)、實(shí)現(xiàn)(算法設(shè)計(jì)與分析)。堅(jiān)持算法設(shè)計(jì)與分析的步驟。算法設(shè)計(jì)三階段（基本思想、算法框架、程序?qū)崿F(xiàn)）。結(jié)構(gòu)和算法的不同應(yīng)用。這是最繁雜、范圍最廣的部分。通過(guò)多練習(xí)達(dá)到熟練應(yīng)用。26共一百二十七頁(yè)為在有限的時(shí)間內(nèi)學(xué)習(xí)好這門課

15、程，應(yīng)當(dāng)注意以下幾點(diǎn):注意學(xué)習(xí)用 C / C+ / Java 語(yǔ)言編寫(xiě)小程序時(shí)的語(yǔ)法規(guī)則和方法，為算法分析和算法設(shè)計(jì)題的求解打下基礎(chǔ)。函數(shù)定義和參數(shù)使用。算法一般(ybn)以函數(shù)形式給出，函數(shù)編寫(xiě)需要注意的問(wèn)題包括函數(shù)類型，函數(shù)參數(shù)傳遞，函數(shù)返回值類型等，以及傳值參數(shù)和引用參數(shù)在使用上的區(qū)別。函數(shù)中局部變量的作用域。特別注意在函數(shù)中對(duì)局部變量的任何改變，在函數(shù)外不能使用。27共一百二十七頁(yè)算法設(shè)計(jì)所用數(shù)據(jù)結(jié)構(gòu)的自定義。算法設(shè)計(jì)時(shí)不能忽視所用數(shù)據(jù)結(jié)構(gòu)的聲明。CC+ 中的動(dòng)態(tài)存儲(chǔ)分配和回收方式。涉及鏈表結(jié)構(gòu)的地方都可能有動(dòng)態(tài)存儲(chǔ)分配和回收操作。要掌握正確使用相關(guān)語(yǔ)句的方法。在CC+ 中輸入輸出文件

16、的定義和使用。特別注意正確使用文件的打開(kāi)、關(guān)閉、讀入、寫(xiě)出操作的使用。在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，要注意知識(shí)體系。數(shù)據(jù)結(jié)構(gòu)課程中的知識(shí)本身具有良好的結(jié)構(gòu)性，有些結(jié)構(gòu)面向應(yīng)用(yngyng)，有些結(jié)構(gòu)面向?qū)崿F(xiàn)。學(xué)習(xí)時(shí)28共一百二十七頁(yè)要注意這兩個(gè)層次以及它們之間的聯(lián)系。注意循序漸進(jìn)在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，首先(shuxin)需要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的定義和特點(diǎn)，數(shù)據(jù)結(jié)構(gòu)的使用范圍，再學(xué)習(xí)各種操作的實(shí)現(xiàn)。在閱讀算法之前，要先弄清其基本設(shè)計(jì)思想、基本步驟，并通過(guò)事例學(xué)習(xí)了解每個(gè)算法的處理流程以加深理解，最后再閱讀程序代碼。注意比較在復(fù)習(xí)中應(yīng)當(dāng)注意從“橫向”和“縱向”進(jìn)行對(duì)比以加深理解。29共一百二十七頁(yè)縱向?qū)Ρ葘⒁环N結(jié)構(gòu)與

17、它的各種不同的實(shí)現(xiàn)(shxin)加以比較，理解不同實(shí)現(xiàn)方式的優(yōu)點(diǎn)和問(wèn)題。如二叉樹(shù)的順序和鏈表實(shí)現(xiàn)。橫向?qū)Ρ仁菍?duì)屬于同一類邏輯結(jié)構(gòu)的不同數(shù)據(jù)結(jié)構(gòu)（如線性表、棧、隊(duì)列）加以比較，對(duì)具有相同功能的不同算法進(jìn)行比較等，了解數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)間的關(guān)系。注意練習(xí)只看書(shū)不做題，不能真正學(xué)會(huì)有關(guān)知識(shí)，不能達(dá)到技能培養(yǎng)的目的。做題是自我檢查的重要手段。30共一百二十七頁(yè)在做算法設(shè)計(jì)類型的習(xí)題時(shí)，應(yīng)考慮數(shù)據(jù)結(jié)構(gòu)的定義。提高算法設(shè)計(jì)的能力。編寫(xiě)算法的題可能是學(xué)生比較棘手的問(wèn)題，特別是在考試這樣一個(gè)氛圍，時(shí)間又短促，想編出一個(gè)好算法不太容易。一個(gè)建議是首先仔細(xì)閱讀試題題目，了解(lioji)它到底要你干什么。然后用一

18、個(gè)簡(jiǎn)單的例子走一下，總結(jié)每一步向下走可用什么語(yǔ)句實(shí)現(xiàn)。31共一百二十七頁(yè)再做歸納，整理出處理流程。按照結(jié)構(gòu)化程序設(shè)計(jì)的方法，搭建框架(kun ji)，再根據(jù)例子填入細(xì)節(jié)。在設(shè)計(jì)一個(gè)算法時(shí)，要考慮問(wèn)題解決方案的多樣性、算法的適用性、問(wèn)題對(duì)算法選擇的限制。選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)有效的算法。下面我們將與嚴(yán)蔚敏老師的教材做一對(duì)比，說(shuō)明我們的教材在何處補(bǔ)充了嚴(yán)蔚敏老師的教材。順帶給出一些問(wèn)題的點(diǎn)撥。32共一百二十七頁(yè)各章知識(shí)點(diǎn)、特色(ts)與疑難問(wèn)題第一章 數(shù)據(jù)結(jié)構(gòu)概論第二章 線性表第三章 棧、隊(duì)列與數(shù)組第四章 樹(shù)與二叉樹(shù)第五章 圖第六章 查找(ch zho)第七章 排序33共一百二十七頁(yè)本章“緒論”

19、的知識(shí)點(diǎn)有 4 個(gè)：數(shù)據(jù)結(jié)構(gòu)的概念使用C/C+語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu)和算法的方法算法的定義及算法的特性算法的性能分析(fnx)與嚴(yán)版教材的差別抽象數(shù)據(jù)類型的表述有差異增加線性結(jié)構(gòu)按存取方式的分類增加算法設(shè)計(jì)步驟和算法設(shè)計(jì)基本方法算法空間復(fù)雜度度量表述有差異第一章 知識(shí)點(diǎn)解析(ji x)34共一百二十七頁(yè)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的概念問(wèn)題1. 平時(shí)所說(shuō)的信息和數(shù)據(jù)有何區(qū)別(qbi)？問(wèn)題2. 數(shù)值性數(shù)據(jù)和非數(shù)值性數(shù)據(jù)有何區(qū)別？問(wèn)題3. 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)有何關(guān)系？問(wèn)題4. 數(shù)據(jù)對(duì)象與數(shù)據(jù)結(jié)構(gòu)有何關(guān)系？問(wèn)題5. 抽象數(shù)據(jù)類型中的抽象和信息隱藏是何含義？問(wèn)題6. 如何區(qū)分?jǐn)?shù)據(jù)的 4 種邏輯結(jié)構(gòu)類型？

20、問(wèn)題7. 如何區(qū)分?jǐn)?shù)據(jù)的 4 種存儲(chǔ)結(jié)構(gòu)類型？問(wèn)題8. 線性結(jié)構(gòu)按照數(shù)據(jù)的存取方式又可分為幾種類型？35共一百二十七頁(yè)使用C/C+語(yǔ)言描述(mio sh)數(shù)據(jù)結(jié)構(gòu)和算法問(wèn)題1. 定義一個(gè)struct時(shí)，前面加typedef，與不加typrdef有什么不同(b tn)？問(wèn)題2. 用struct和union定義的結(jié)構(gòu)體有何不同？問(wèn)題3. 在循環(huán)結(jié)構(gòu)中while循環(huán)和do循環(huán)中條件表達(dá)式取值對(duì)循環(huán)執(zhí)行有何影響？問(wèn)題4. 函數(shù)調(diào)用時(shí)，參數(shù)采取引用型和傳值型有何區(qū)別？問(wèn)題5. 動(dòng)態(tài)存儲(chǔ)分配和回收操作，C與C+各自如何處理，各有何特點(diǎn)？問(wèn)題6. 輸入和輸出操作，C和C+各自如何處理？36共一百二十七頁(yè)算法

21、(sun f)的定義及算法(sun f)的特性問(wèn)題1. 算法應(yīng)有輸入，則0個(gè)輸入是否有輸入？問(wèn)題2. 如果(rgu)一個(gè)求解方程根的牛頓算法不收斂，它是否違反“有窮性”的要求？問(wèn)題3. 如果一個(gè)算法多層嵌套地調(diào)用了其他算法，它是否違反“可行性”的要求？問(wèn)題4. 如果一個(gè)算法內(nèi)部有一個(gè)隨系統(tǒng)狀態(tài)會(huì)轉(zhuǎn)移到不同指令地址的開(kāi)關(guān)，它是否違反“確定性”的要求？問(wèn)題5. 用結(jié)構(gòu)化方法設(shè)計(jì)算法有哪 4 個(gè)階段？問(wèn)題6. 窮舉法與迭代法有何關(guān)系？37共一百二十七頁(yè)問(wèn)題7. 遞推與遞歸又有何關(guān)系？問(wèn)題8. 窮舉法與遞推有何關(guān)系？問(wèn)題1. 如何用斷言方式判斷算法的正確性？問(wèn)題2. 如何實(shí)現(xiàn)算法的健壯性？問(wèn)題3. 如

22、何判斷算法的簡(jiǎn)單性？為何要求一個(gè)算法具有簡(jiǎn)單性？問(wèn)題4. 如何判斷算法的可讀性？為何要求一個(gè)算法具有可讀性？問(wèn)題5. 算法的執(zhí)行(zhxng)頻度如何計(jì)算？算法(sun f)的性能分析38共一百二十七頁(yè)問(wèn)題6. 問(wèn)題規(guī)模是什么？問(wèn)題7. 算法的復(fù)雜度與問(wèn)題規(guī)模有何關(guān)系？問(wèn)題8. 算法復(fù)雜性度量是事前估計(jì)（分析）還是事后(shhu)測(cè)量？問(wèn)題9. 空間復(fù)雜度度量應(yīng)統(tǒng)計(jì)哪些占用的空間？問(wèn)題10. 算法的大O表示是T(n) = O(f(n)，如果一個(gè)算法的執(zhí)行頻度是2n3+3n2+2n+1，則該算法的漸進(jìn)時(shí)間復(fù)雜度為T(n) = O(n3)，為什么？39共一百二十七頁(yè)本章“線性表”的知識(shí)點(diǎn)有 5 個(gè)

23、：線性表的定義和特點(diǎn)線性表的基本操作線性表的存儲(chǔ)(cn ch)表示：順序存儲(chǔ)、鏈表存儲(chǔ)循環(huán)鏈表和雙向鏈表線性表的應(yīng)用與嚴(yán)版教材的差別順序表中元素的序號(hào)從 1 開(kāi)始，但存儲(chǔ)數(shù)組中的下標(biāo)從 0 開(kāi)始，嚴(yán)版的存儲(chǔ)數(shù)組下標(biāo)均從 1開(kāi)始，因?yàn)樗菑膒ascal版對(duì)譯過(guò)來(lái)的。第二章 知識(shí)點(diǎn)解析(ji x)40共一百二十七頁(yè)給出了順序表的兩種聲明(shngmng)，并指出它們之間的差別，嚴(yán)版只有一種。順序表的操作實(shí)現(xiàn)中盡量采用引用型參數(shù)傳遞表本身，函數(shù)體中的語(yǔ)句簡(jiǎn)單，容易理解；嚴(yán)版不是，導(dǎo)致實(shí)現(xiàn)操作的函數(shù)體內(nèi)語(yǔ)句出現(xiàn)諸多指針運(yùn)算和引用，可讀性差。增加了單鏈表的遞歸性討論，嚴(yán)版沒(méi)有提及。在單鏈表應(yīng)用中引入有序

24、鏈表，并用它實(shí)現(xiàn)集合結(jié)構(gòu)；嚴(yán)版沒(méi)有提及。把關(guān)于字符串的討論移到線性表的應(yīng)用部分，刪去了KMP算法。嚴(yán)版單列了一章。41共一百二十七頁(yè)一元多項(xiàng)式討論中增加了多項(xiàng)式輸出和多項(xiàng)式乘法的討論。嚴(yán)版只有多項(xiàng)式建立和加法的討論。最后，增加了本章小結(jié)，嚴(yán)版沒(méi)有。問(wèn)題1. 如果一個(gè)元素(yun s)集合中每個(gè)元素(yun s)都有 1 個(gè)且僅有 1 個(gè)直接前驅(qū)和 1 個(gè)直接后繼，它是線性表嗎？問(wèn)題2. 循環(huán)鏈表是線性表嗎？線性表的定義(dngy)和特點(diǎn)42共一百二十七頁(yè)問(wèn)題3. 如果一個(gè)元素集合有一個(gè)元素僅有 1 個(gè)直接后繼而沒(méi)有直接前驅(qū)，另一個(gè)元素僅有 1 個(gè)直接前驅(qū)而沒(méi)有直接后繼，其他每個(gè)元素都僅有 1

25、個(gè)直接前驅(qū)和 1 個(gè)直接后繼，但其中各個(gè)元素可能數(shù)據(jù)類型不同，該元素集合是線性表嗎？問(wèn)題4. 如果一個(gè)有 n（n0）個(gè)表元素的序列構(gòu)成一個(gè)表，且表元素既有不可再分的數(shù)據(jù)元素，又有可以(ky)再分的子表，它是線性表嗎？如果不是，它又是什么表？什么條件下才成為線性表？ 43共一百二十七頁(yè)問(wèn)題1. 如果一個(gè)一維數(shù)組有 n 個(gè)數(shù)組元素(yun s)，它是線性表嗎？二維數(shù)組可視為數(shù)組元素(yun s)為一維數(shù)組的一維數(shù)組，那么二維數(shù)組是線性表嗎？為什么？問(wèn)題2. 順序表每插入一個(gè)新元素，或刪除一個(gè)已有元素，需要移動(dòng)多少元素？平均移動(dòng)多少元素？問(wèn)題3. 如果不想移動(dòng)多個(gè)元素實(shí)現(xiàn)順序表的插入與刪除，應(yīng)如何做

26、？ 線性表的基本操作44共一百二十七頁(yè)線性表的存儲(chǔ)(cn ch)表示問(wèn)題1. 線性表的順序存儲(chǔ)表示是一維數(shù)組嗎？問(wèn)題2. 想要以O(shè)(1)的時(shí)間代價(jià)存取第 i 個(gè)表元素，線性表應(yīng)采用順序表還是單鏈表？問(wèn)題3. 順序表可以擴(kuò)充嗎？如果想要擴(kuò)充，應(yīng)采用何種結(jié)構(gòu)？問(wèn)題4. 為了統(tǒng)一空鏈表和非空鏈表的操作，簡(jiǎn)化鏈表的插入刪除操作，需要給鏈表增加點(diǎn)什么？問(wèn)題5. 如果想使得順序表適合多種數(shù)據(jù)類型，順序表應(yīng)如何構(gòu)建？假設(shè)順序表的每個(gè)元素不是原子(yunz)類型，其元素成分由使用者自行決定。45共一百二十七頁(yè)問(wèn)題6. 在何種場(chǎng)合選用順序表？鏈表呢？問(wèn)題1. 想要以O(shè)(1)的時(shí)間代價(jià)把兩個(gè)鏈表連接起來(lái)可采用(c

27、iyng)何種鏈表結(jié)構(gòu)？問(wèn)題2. 想要判斷一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈表 L 是否為空，應(yīng)采用何種語(yǔ)句？ 問(wèn)題3. 想要以O(shè)(1)的時(shí)間代價(jià)訪問(wèn)第 i 個(gè)表元素的直接前驅(qū)和或直接后繼，應(yīng)采用何種鏈表結(jié)構(gòu)？ 循環(huán)(xnhun)鏈表和雙向鏈表46共一百二十七頁(yè)第三章 知識(shí)點(diǎn)解析(ji x)本章“棧、隊(duì)列與數(shù)組”的知識(shí)點(diǎn)有 8 個(gè)：棧和隊(duì)列的定義及其特點(diǎn)棧的存儲(chǔ)表示及其基本運(yùn)算(yn sun)的實(shí)現(xiàn)隊(duì)列的存儲(chǔ)表示及其基本運(yùn)算的實(shí)現(xiàn)棧的應(yīng)用隊(duì)列的應(yīng)用多維數(shù)組特殊矩陣稀疏矩陣47共一百二十七頁(yè)與嚴(yán)版教材的差別順序棧的棧頂指針設(shè)定為整數(shù)（即游標(biāo)），它指示的是當(dāng)前棧頂?shù)南聵?biāo)位置。嚴(yán)版的棧頂指針設(shè)定為指針型，它指示的

28、是當(dāng)前棧頂?shù)膬?nèi)存地址，棧操作的實(shí)現(xiàn)(shxin)上復(fù)雜一些。為降低復(fù)雜性，提高可讀性，盡量避免使用指針。鏈?zhǔn)綏Ｔ黾恿祟^結(jié)點(diǎn)。嚴(yán)版僅給出鏈?zhǔn)綏５氖疽鈭D，未討論操作的實(shí)現(xiàn)。增加了棧的混洗（即可能出棧序列）的討論。嚴(yán)版未提及。增加了棧操作實(shí)現(xiàn)算法性能分析。嚴(yán)版沒(méi)有。48共一百二十七頁(yè)增加了隊(duì)列操作實(shí)現(xiàn)算法性能分析。嚴(yán)版沒(méi)有。通過(guò)階乘問(wèn)題的討論，介紹(jisho)了遞歸實(shí)現(xiàn)的過(guò)程和遞歸工作棧。嚴(yán)版通過(guò)漢諾塔問(wèn)題的討論，介紹(jisho)了遞歸實(shí)現(xiàn)的過(guò)程和遞歸工作棧。通過(guò)漢諾塔問(wèn)題的討論，引入了分治法。嚴(yán)版沒(méi)有提及。通過(guò)迷宮問(wèn)題的討論，引入了回溯法。嚴(yán)版沒(méi)有此例。通過(guò)求組合問(wèn)題，引入了動(dòng)態(tài)規(guī)劃法。嚴(yán)版沒(méi)

29、有提及。詳細(xì)定義了雙端隊(duì)列及其實(shí)現(xiàn)。嚴(yán)版沒(méi)有提。49共一百二十七頁(yè)增加了數(shù)組的應(yīng)用舉例，給出用數(shù)組存儲(chǔ)長(zhǎng)整數(shù)和實(shí)現(xiàn)階乘運(yùn)算的例子。嚴(yán)版沒(méi)有。針對(duì)特殊矩陣的壓縮存儲(chǔ)，通過(guò)下標(biāo)轉(zhuǎn)換，實(shí)現(xiàn)映射。嚴(yán)版從矩陣到壓縮存儲(chǔ)數(shù)組有，但想從壓縮數(shù)組到特殊矩陣的轉(zhuǎn)換沒(méi)有提及。放寬對(duì)稀疏矩陣的要求，并說(shuō)明三對(duì)角矩陣是稀疏矩陣，不應(yīng)把稀疏矩陣與特殊矩陣對(duì)立起來(lái)。嚴(yán)版僅認(rèn)定一種(y zhn)判斷稀疏矩陣的規(guī)則。增加了帶行指針數(shù)組的二元組表示。嚴(yán)版沒(méi)有。本章有小結(jié)，嚴(yán)版沒(méi)有。50共一百二十七頁(yè)問(wèn)題1. 棧是一種先進(jìn)后出的順序存取結(jié)構(gòu)，它是順序存儲(chǔ)結(jié)構(gòu)嗎？問(wèn)題2. 一個(gè)較早進(jìn)棧的元素能否先于在它之后進(jìn)棧的元素從棧中取出？

30、問(wèn)題3. 一般來(lái)講，只允許棧頂元素從棧中退出，在什么情況下元素可以從棧底泄出？問(wèn)題4. 元素以1, 2, , n的順序進(jìn)棧，如何判斷可能(knng)的出棧序列？可能(knng)的出棧序列有多少種？問(wèn)題5. 隊(duì)列具有先進(jìn)先出的特性，可不可以加塞，在隊(duì)列其他位置進(jìn)出隊(duì)列？棧和隊(duì)列(duli)的定義及其特點(diǎn)51共一百二十七頁(yè)問(wèn)題6. 以1, 2, , n進(jìn)隊(duì)，可能的出隊(duì)序列有多少？ 問(wèn)題7. 棧、隊(duì)列和向量（一維數(shù)組）有什么不同？問(wèn)題8. 可否(k fu)用兩個(gè)棧模擬一個(gè)隊(duì)列？反過(guò)來(lái)呢？問(wèn)題9. 棧、隊(duì)列和向量（一維數(shù)組）有什么不同？問(wèn)題10. 雙端隊(duì)列有何特點(diǎn)？ 問(wèn)題11. 優(yōu)先級(jí)隊(duì)列有何特點(diǎn)？

31、問(wèn)題1. 當(dāng)?？諘r(shí)順序棧的棧頂指針 top = -1，當(dāng)棧非空時(shí) top 是否指示最后元素加入的位置？棧的存儲(chǔ)(cn ch)表示及其基本運(yùn)算的實(shí)現(xiàn)52共一百二十七頁(yè)問(wèn)題2. 順序棧的進(jìn)棧、出棧的先決條件是什么？問(wèn)題3. 當(dāng)一個(gè)順序棧已滿，如何才能擴(kuò)充棧長(zhǎng)度，使得程序能夠繼續(xù)使用這個(gè)棧？ 問(wèn)題4. 當(dāng)兩個(gè)棧共享同一個(gè)存儲(chǔ)空間 Vm 時(shí)，可設(shè)棧頂指針數(shù)組 t2 和棧底指針數(shù)組 b2。如果進(jìn)棧采用兩個(gè)棧相向前行的方式，則任一棧的棧滿條件是什么？問(wèn)題5. 若進(jìn)棧序列為1, 2, 3, 4, 5, 6，出棧序列為2, 4, 3, 6, 5, 1，問(wèn)棧容量至少(zhsho)多大？問(wèn)題6. 順序棧的優(yōu)點(diǎn)是什

32、么？缺點(diǎn)是什么？問(wèn)題7. 鏈?zhǔn)綏５臈ｍ斨羔樖侵冈阪滎^還是鏈尾？53共一百二十七頁(yè)問(wèn)題8. 如果鏈?zhǔn)綏](méi)有頭結(jié)點(diǎn)，鏈?zhǔn)綏５臈ｍ斣阪湵淼氖裁次恢?？棧底在鏈表的什么位置？棧指針如何設(shè)置？?？諚l件是什么？棧滿條件是什么？問(wèn)題9. 鏈?zhǔn)綏Ｖ荒茼樞虼嫒?，而順序棧不但能順序存取，還能直接存取，這話對(duì)嗎？問(wèn)題10. 理論上鏈?zhǔn)綏](méi)有棧滿問(wèn)題，但在進(jìn)棧操作實(shí)現(xiàn)時(shí)，還要判斷一個(gè)后置條件，是何條件？問(wèn)題10. 常用的一種鏈?zhǔn)綏Ｊ腔陟o態(tài)鏈表的。用一個(gè)整數(shù)(zhngsh)數(shù)組 Sn 存放鏈接指針（游標(biāo)），設(shè)初始時(shí) top = -1，表示棧空，則其進(jìn)棧、出棧、判?？盏炔僮魅绾螌?shí)現(xiàn)？54共一百二十七頁(yè)問(wèn)題11. 鏈?zhǔn)綏５?/p>

33、優(yōu)點(diǎn)是什么？缺點(diǎn)是什么？ 問(wèn)題1. 隊(duì)列操作deQueue (Q, x)與getFront (Q, x)有什么區(qū)別(qbi)？問(wèn)題2. 當(dāng)用犧牲一個(gè)單元的方式組織循環(huán)隊(duì)列時(shí)，隊(duì)空和隊(duì)滿條件是什么？進(jìn)隊(duì)、出隊(duì)如何進(jìn)行？問(wèn)題3. 當(dāng)一個(gè)循環(huán)隊(duì)列已滿，如何才能擴(kuò)充隊(duì)列長(zhǎng)度，使得客戶程序能夠繼續(xù)使用這個(gè)隊(duì)列？問(wèn)題4. 在循環(huán)隊(duì)列中進(jìn)行插入和刪除時(shí)，是否需要移動(dòng)隊(duì)列元素的位置？ 隊(duì)列(duli)的存儲(chǔ)表示及其基本運(yùn)算的實(shí)現(xiàn)55共一百二十七頁(yè)問(wèn)題5. 在循環(huán)隊(duì)列中將 elem 數(shù)組的尾端 elemmax Size-1 與前端 elem0 銜接起來(lái)，此時(shí)隊(duì)尾指針rear和隊(duì)頭指針front是如何移動(dòng)的？ 問(wèn)

34、題6. 當(dāng)用隊(duì)頭指針 front 和長(zhǎng)度 length 組織循環(huán) 隊(duì)列時(shí)，隊(duì)空和隊(duì)滿的條件是什么？進(jìn)隊(duì)和出隊(duì)的策略是什么？（設(shè)表長(zhǎng)度為m）問(wèn)題7. 鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾在鏈表的什么地方？問(wèn)題8. 如果鏈?zhǔn)疥?duì)列沒(méi)有頭結(jié)點(diǎn)，鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾在鏈表的什么地方？隊(duì)空條件是什么？問(wèn)題9. 同時(shí)使用多個(gè)(du )隊(duì)列時(shí)需采用何種隊(duì)列結(jié)構(gòu)？如何組織？56共一百二十七頁(yè)問(wèn)題10. 鏈?zhǔn)疥?duì)列的每個(gè)結(jié)點(diǎn)是否還可是隊(duì)列？問(wèn)題11. 隊(duì)列還有哪些(nxi)變型？ 問(wèn)題1. 在后綴表達(dá)式求值過(guò)程中用棧存放什么？在中綴表達(dá)式求值過(guò)程中又用棧存放什么？問(wèn)題2. 為判斷表達(dá)式中的括號(hào)是否配對(duì)，可采用何種結(jié)構(gòu)輔助進(jìn)行判斷？

35、 問(wèn)題3. 在遞歸算法中采用何種結(jié)構(gòu)來(lái)存放遞歸過(guò)程每層的局部變量、返回地址和實(shí)參副本？棧的應(yīng)用(yngyng)57共一百二十七頁(yè)問(wèn)題4. 遞歸深度與遞歸工作棧的層次有何關(guān)系？問(wèn)題5. 在回溯法中采用何種結(jié)構(gòu)來(lái)記錄回退路徑(ljng)？問(wèn)題6. 在分治法中采用棧做什么？舉例說(shuō)明。問(wèn)題7. 在減治法中采用棧做什么？舉例說(shuō)明。問(wèn)題1. 在逐層處理一個(gè)分層結(jié)構(gòu)的數(shù)據(jù)時(shí)，需采用何種輔助結(jié)構(gòu)來(lái)組織數(shù)據(jù)？問(wèn)題2. 為實(shí)現(xiàn)輸入-處理-輸出并行操作需建立多個(gè)輸入緩沖區(qū)隊(duì)列，這些隊(duì)列是按數(shù)組方式組織的還是按鏈表方式組織的？隊(duì)列(duli)的應(yīng)用58共一百二十七頁(yè)問(wèn)題3. 在操作系統(tǒng)中一種進(jìn)程調(diào)度策略是先來(lái)先服務(wù)，

36、為此使用了何種輔助結(jié)構(gòu)？問(wèn)題4. 在對(duì)一個(gè)無(wú)序單鏈表進(jìn)行排序時(shí)，可先把鏈表截出一段段有序的子鏈表，再對(duì)它們做兩路歸并排序。為此定義隊(duì)列來(lái)輔助排序，此隊(duì)列的元素的數(shù)據(jù)類型是什么？問(wèn)題5. 雙端隊(duì)列的作用是什么？有幾種(j zhn)雙端隊(duì)列？問(wèn)題6. 在用動(dòng)態(tài)規(guī)劃法進(jìn)行問(wèn)題求解時(shí)可否利用隊(duì)列？為什么？問(wèn)題7. 在一個(gè)網(wǎng)格中求兩點(diǎn)間最短路徑時(shí)可否利用隊(duì)列？為什么？59共一百二十七頁(yè)多維數(shù)組問(wèn)題1. 一維數(shù)組是線性結(jié)構(gòu)碼？它是邏輯結(jié)構(gòu)還是存儲(chǔ)結(jié)構(gòu)？問(wèn)題2. 對(duì)于(duy)一維數(shù)組只能直接存取嗎？問(wèn)題3. 一維數(shù)組一旦放滿可以擴(kuò)充嗎？問(wèn)題4. 二維數(shù)組可以視為數(shù)組元素為一維數(shù)組的一維數(shù)組，因此二維數(shù)組是

37、線性結(jié)構(gòu)嗎？問(wèn)題5. 二維數(shù)組每個(gè)元素的存取時(shí)間都相同嗎？問(wèn)題6. 二維數(shù)組是按一維數(shù)組存儲(chǔ)的嗎？如何計(jì)算二維數(shù)組中元素的存儲(chǔ)地址？ 問(wèn)題7. 數(shù)組是邏輯結(jié)構(gòu)還是物理結(jié)構(gòu)？60共一百二十七頁(yè)問(wèn)題8. 動(dòng)態(tài)數(shù)組用指針來(lái)定義。假定數(shù)組指針為 a，可否用*a 取出數(shù)組元素的值？可否用 a+ 進(jìn)到下一數(shù)組元素？問(wèn)題9. 鏈表也是動(dòng)態(tài)結(jié)構(gòu)。假定鏈表指針為*a，可否用*a 取出鏈表結(jié)點(diǎn)的值？可否用 a+ 進(jìn)到下一鏈表結(jié)點(diǎn)？問(wèn)題1. 如果用下三角壓縮存儲(chǔ)(cn ch)對(duì)稱矩陣，B0存放A00，如何存取Aij？特殊(tsh)矩陣61共一百二十七頁(yè)問(wèn)題2. 計(jì)算對(duì)稱矩陣在壓縮數(shù)組中的存放位置時(shí)要注意什么問(wèn)題？問(wèn)

38、題3. 對(duì)稱矩陣是否可能是稀疏矩陣？問(wèn)題4. 兩個(gè)對(duì)稱矩陣相加，結(jié)果矩陣還對(duì)稱嗎？?jī)蓚€(gè)對(duì)稱矩陣相乘，結(jié)果矩陣還對(duì)稱嗎？問(wèn)題5. 通過(guò)矩陣元素的行、列下標(biāo)如何計(jì)算通過(guò)它的正對(duì)角線（從左上到右下的斜線）和反對(duì)角線（從左下到右上的反斜線）的編號(hào)(bin ho)？ 問(wèn)題6. 兩個(gè)三對(duì)角矩陣相加，結(jié)果矩陣還是三對(duì)角矩陣嗎？相乘的情況又如何？62共一百二十七頁(yè)問(wèn)題7. 為什么特殊矩陣極少使用鏈接存儲(chǔ)？問(wèn)題1. 三對(duì)角矩陣是否稀疏矩陣？ 問(wèn)題2. 兩個(gè)稀疏矩陣相加，結(jié)果矩陣還是稀疏矩陣嗎？?jī)蓚€(gè)稀疏矩陣相乘，結(jié)果矩陣又如何？問(wèn)題3. 用三元組表存儲(chǔ)稀疏矩陣的非零元素，是否失去了直接存取的特性(txng)？如何

39、改進(jìn)？問(wèn)題4. 采用帶行指針的二元組表，相對(duì)于三元組表，有什么優(yōu)點(diǎn)？ 稀疏(xsh)矩陣63共一百二十七頁(yè)第四章 知識(shí)點(diǎn)解析(ji x)本章“樹(shù)與二叉樹(shù)”的知識(shí)點(diǎn)有 9 個(gè)：樹(shù)與二叉樹(shù)的定義(dngy)和性質(zhì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷線索二叉樹(shù)樹(shù)與森林二叉排序樹(shù)平衡二叉樹(shù)Huffman樹(shù)堆64共一百二十七頁(yè)與嚴(yán)版教材的差別區(qū)分自由樹(shù)和有根樹(shù)。嚴(yán)版沒(méi)有。區(qū)分結(jié)點(diǎn)的深度、結(jié)點(diǎn)的高度、樹(shù)的深度、樹(shù)的高度、樹(shù)的寬度。嚴(yán)版沒(méi)有。明確定義結(jié)點(diǎn)間路徑及路徑長(zhǎng)度。嚴(yán)版沒(méi)有。二叉樹(shù)深度定義為log2(n+1)，當(dāng)n=0也可用。嚴(yán)版定義為log2n+1。對(duì)于完全二叉樹(shù)，增加了結(jié)點(diǎn)編號(hào)從 0 開(kāi)始的計(jì)算方法，這在

40、討論堆時(shí)需要(xyo)用到。嚴(yán)版僅討論了結(jié)點(diǎn)編號(hào)從 0 開(kāi)始的計(jì)算方法。增加了嚴(yán)格二叉樹(shù)和理想平衡樹(shù)的概念。65共一百二十七頁(yè)增加了前序和后序的使用棧的非遞歸算法。嚴(yán)版僅給出中序的非遞歸算法。增加了按層次序遍歷(bin l)二叉樹(shù)的使用隊(duì)列的實(shí)現(xiàn)算法。嚴(yán)版僅提了一句。增加了遞歸和非遞歸遍歷算法的應(yīng)用舉例。嚴(yán)版幾乎沒(méi)有。增加了樹(shù)的先根、后根、廣度遍歷的實(shí)現(xiàn)算法以及樹(shù)遍歷算法的應(yīng)用舉例。嚴(yán)版沒(méi)有。增加了二叉排序樹(shù)的非遞歸的查找算法。嚴(yán)版僅給出遞歸的查找算法。查找性能分析增加了不等查找概率情形。嚴(yán)版66共一百二十七頁(yè)僅討論了相等查找概率的情形。刪去了平衡二叉樹(shù)的算法。嚴(yán)版詳盡地介紹了實(shí)現(xiàn)算法，使讀者

41、陷入無(wú)盡的煩惱(fnno)，應(yīng)換一個(gè)角度重新考慮的實(shí)現(xiàn)算法更好。增加了平衡二叉樹(shù)的刪除處理及事例。嚴(yán)版沒(méi)有討論。討論了平衡二叉樹(shù)的插入處理及事例。嚴(yán)版沒(méi)有討論。增加了關(guān)于小根堆的全面討論。嚴(yán)版沒(méi)有。導(dǎo)致在討論圖的算法中不能按邊的權(quán)重高效地組織數(shù)據(jù)。67共一百二十七頁(yè)樹(shù)與二叉樹(shù)的定義(dngy)和性質(zhì)問(wèn)題1. 為何(wih)有的教材定義樹(shù)結(jié)點(diǎn)數(shù)不能為0？而N叉樹(shù)的結(jié)點(diǎn)數(shù)可以為0？問(wèn)題2. 二叉樹(shù)是樹(shù)嗎？問(wèn)題3. 樹(shù)的葉結(jié)點(diǎn)無(wú)子女，是否可稱它無(wú)子樹(shù)？問(wèn)題4. 二叉樹(shù)的葉結(jié)點(diǎn)無(wú)子女，它是否無(wú)子樹(shù)？問(wèn)題5. 樹(shù)和二叉樹(shù)的結(jié)點(diǎn)的高度與深度如何理解？樹(shù)的高度與深度又如何理解？問(wèn)題6. 一棵二叉樹(shù)有1024

42、個(gè)結(jié)點(diǎn)，其中465個(gè)是葉結(jié)點(diǎn)，那么樹(shù)中度為2和度為1的結(jié)點(diǎn)各有多少？68共一百二十七頁(yè)問(wèn)題7. 計(jì)算深度的公式 log2(n+1) 是針對(duì)何種二叉樹(shù)的？問(wèn)題8. 二叉樹(shù)求深度的公式log2(n+1) 與log2n +1有何不同？問(wèn)題9. 完全(wnqun)二叉樹(shù)有何用處？問(wèn)題10. n0 = n2+1公式有何用途？問(wèn)題1. 順序存儲(chǔ)適用于何種二叉樹(shù)？問(wèn)題2. 完全二叉樹(shù)的結(jié)點(diǎn)從 1 開(kāi)始編號(hào)和從 0 開(kāi)始編號(hào)有何不同？二叉樹(shù)的存儲(chǔ)(cn ch)69共一百二十七頁(yè)問(wèn)題3. 二叉樹(shù)順序存儲(chǔ)通常適用于哪類二叉樹(shù)？問(wèn)題4. 在二叉樹(shù)順序存儲(chǔ)中，如果根結(jié)點(diǎn)在 0 號(hào)位置，如何判定某結(jié)點(diǎn) i 的父結(jié)點(diǎn)、左

43、子女結(jié)點(diǎn)、右兄弟(xingd)結(jié)點(diǎn)的位置？如何判斷它所處層次？問(wèn)題5. 通常使用二叉鏈表存儲(chǔ)二叉樹(shù)，為何還選用三叉鏈表？問(wèn)題6. 如果不使用三叉鏈表，能否也很容易地找到父結(jié)點(diǎn)？問(wèn)題7. 使用二叉鏈表存儲(chǔ)有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，空的指針域有多少？70共一百二十七頁(yè)二叉樹(shù)的遍歷(bin l)問(wèn)題1. 已知二叉樹(shù)的前序序列abdcef，中序序列dbaecf，其后序序列是什么？問(wèn)題2. 前序序列與中序序列相同的是什么二叉樹(shù)?問(wèn)題3. 前序序列與后序序列相同的是什么二叉樹(shù)?問(wèn)題4. 中序序列與后序序列相同的是什么二叉樹(shù)？問(wèn)題5. 前序序列與層次(cngc)序序列相同的是什么二叉樹(shù)?問(wèn)題6. 后序序列與層

44、次序序列相同的是什么二叉樹(shù)?問(wèn)題7. 前序序列與中序序列正好相反的是什么二叉樹(shù)？71共一百二十七頁(yè)問(wèn)題8. 前序序列與后序序列正好相反的是什么二叉樹(shù)？問(wèn)題9. 一棵二叉樹(shù)的前序序列的最后一個(gè)結(jié)點(diǎn)是否是它中序序列的最后一個(gè)結(jié)點(diǎn)？問(wèn)題10. 一棵二叉樹(shù)的前序序列的最后一個(gè)結(jié)點(diǎn)是否是它層次序序列的最后一個(gè)結(jié)點(diǎn)？問(wèn)題11. 一棵有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)的前序序列固定，可能的不同二叉樹(shù)有多少種？問(wèn)題12. 二叉樹(shù)的前序、中序、后序遍歷所走的路線都相同，只是訪問(wèn)時(shí)機(jī)(shj)不同，這種說(shuō)法對(duì)嗎？72共一百二十七頁(yè)問(wèn)題13. 二叉樹(shù)的層次序遍歷是按二叉樹(shù)層次進(jìn)行逐層訪問(wèn)，其遍歷算法需要使用(shyng)何種輔

45、助結(jié)構(gòu)？問(wèn)題1. 為什么要建立線索二叉樹(shù)？問(wèn)題2. 如何構(gòu)造一棵中序線索二叉樹(shù)？問(wèn)題3. 如何在一棵中序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p為根的子樹(shù)上的中序第一個(gè)結(jié)點(diǎn)？問(wèn)題4. 如何在一棵中序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p為根的子樹(shù)上的中序最后一個(gè)結(jié)點(diǎn)？線索(xin su)二叉樹(shù)73共一百二十七頁(yè)問(wèn)題(wnt)5. 如何在一棵中序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p的中序下的后繼？問(wèn)題6. 如何在一棵中序線索二叉樹(shù)中尋找某結(jié)點(diǎn) p的中序下的前驅(qū)？問(wèn)題7. 如何在一棵中序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p的父結(jié)點(diǎn)？問(wèn)題8. 如何在一棵中序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p的前序下的后繼？問(wèn)題9. 如何在一棵中序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p的前序下

46、的前驅(qū)？問(wèn)題10. 如何構(gòu)造一棵前序線索二叉樹(shù)？74共一百二十七頁(yè)問(wèn)題11. 如何在一棵前序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p為根的子樹(shù)上的前序第一個(gè)結(jié)點(diǎn)？問(wèn)題12. 如何在一棵前序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p的前序最后一個(gè)(y )結(jié)點(diǎn)？問(wèn)題13. 如何在一棵前序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p的前序下的后繼？問(wèn)題14. 如何在一棵前序線索二叉樹(shù)中尋找某結(jié)點(diǎn)p的前序下的前驅(qū)？問(wèn)題15. 在線索二叉樹(shù)上插入或刪除一個(gè)結(jié)點(diǎn)需要做什么？ 75共一百二十七頁(yè)樹(shù)與森林(snln)問(wèn)題1. 在一棵 m 叉樹(shù)，設(shè)根在第1層，并從0開(kāi)始自上向下分層給各個(gè)結(jié)點(diǎn)編號(hào)。問(wèn)(1) 第 i 層最多有多少結(jié)點(diǎn)？(2) 高度為 h 的 m 叉樹(shù)

47、最多有多少結(jié)點(diǎn)？(3) 編號(hào)為 k 的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)是多少？(4) 編號(hào)為 k 的結(jié)點(diǎn)的第1個(gè)子(g zi)結(jié)點(diǎn)編號(hào)是多少？(5) 編號(hào)為 k 的結(jié)點(diǎn)在第幾層？問(wèn)題2. 使用樹(shù)的父指針表示，尋找某結(jié)點(diǎn) i 的父結(jié)點(diǎn)、所有子女、兄弟的時(shí)間復(fù)雜性是多少？76共一百二十七頁(yè)問(wèn)題3. 樹(shù)的先根次序序列的特性是什么(shn me)？問(wèn)題4. 樹(shù)的后根次序序列的特性是什么？問(wèn)題5. n 個(gè)結(jié)點(diǎn)的樹(shù)有多少種？問(wèn)題6. 森林中樹(shù)T1、T2、T3的結(jié)點(diǎn)數(shù)為m1、m2、m3，在該森林的二叉樹(shù)表示中，根的左子樹(shù)和右子樹(shù)各有多少結(jié)點(diǎn)？問(wèn)題7. 在一個(gè)有 n 個(gè)結(jié)點(diǎn)的森林的二叉樹(shù)表示中，左指針為空的結(jié)點(diǎn)有 m 個(gè)，那

48、么右指針為空的結(jié)點(diǎn)有多少個(gè)？77共一百二十七頁(yè)二叉排序(pi x)樹(shù)問(wèn)題1. 一棵有 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)有多少種不同形態(tài)？問(wèn)題2. 若想把二叉排序樹(shù)上所有結(jié)點(diǎn)的數(shù)據(jù)從小到大排列，采用何種遍歷算法？從大到小排列，又采用何種算法？問(wèn)題3. 每次插入一個(gè)新元素到二叉排序樹(shù)中應(yīng)插入到什么地方？樹(shù)的高度最大是多少？問(wèn)題4. 衡量一棵二叉排序樹(shù)的查找性能要計(jì)算其查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度，此時(shí)可借助的輔助(fzh)結(jié)構(gòu)是什么？78共一百二十七頁(yè)問(wèn)題5. 對(duì)下圖所示二叉排序樹(shù)，查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度是多少？問(wèn)題6. 對(duì)一棵二叉排序樹(shù)做中序遍歷，再基于得到的

49、中序序列重新構(gòu)造二叉排序樹(shù)，這兩棵二叉排序樹(shù)是否相同？問(wèn)題7.如果被刪結(jié)點(diǎn)(ji din)是非葉結(jié)點(diǎn)(ji din)，為何不能直接刪除？kicspyf79共一百二十七頁(yè)問(wèn)題8. 在二叉排序樹(shù)中刪除結(jié)點(diǎn)(ji din)時(shí)如何才能保證刪除后二叉排序樹(shù)的高度不增加？問(wèn)題9. 為何在二叉排序樹(shù)的插入和刪除算法中，子樹(shù)的根指針定義為引用型參數(shù)？問(wèn)題10. 在二叉排序樹(shù)中，從根結(jié)點(diǎn)到任一結(jié)點(diǎn)的路徑長(zhǎng)度的平均值是多少？ 問(wèn)題1. 二叉樹(shù)、二叉排序樹(shù)和平衡二叉樹(shù)之間是何關(guān)系？平衡(pnghng)二叉樹(shù)80共一百二十七頁(yè)問(wèn)題2. 有 n 個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)的最小高度和最大高度是多少？問(wèn)題3. 在高度為 h 的平

50、衡二叉樹(shù)中離根最近的葉結(jié)點(diǎn)在第幾層？問(wèn)題4. 平衡化旋轉(zhuǎn)的目的是什么？問(wèn)題5. 平衡二叉樹(shù)插入新結(jié)點(diǎn)后可能失去平衡。如果在從插入新結(jié)點(diǎn)處到根的路徑上有多個(gè)(du )失去平衡的祖先結(jié)點(diǎn)，為何要選擇離插入結(jié)點(diǎn)最近的失去平衡的祖先結(jié)點(diǎn)，對(duì)以它為根的子樹(shù)做平衡化旋轉(zhuǎn)？ 81共一百二十七頁(yè)問(wèn)題1. Huffman 樹(shù)是一棵擴(kuò)充二叉樹(shù)，外結(jié)點(diǎn)（葉結(jié)點(diǎn)）有 n 個(gè)，那么總共有多少結(jié)點(diǎn)？問(wèn)題2. 在構(gòu)造 Huffman 樹(shù)的過(guò)程中，每次從森林中選(zhng xun)根的關(guān)鍵字值最小和次小的兩棵樹(shù)合并。在合并時(shí)是最小的做左子樹(shù)還是次小的做左子樹(shù)？問(wèn)題3. 在構(gòu)造 Huffman 樹(shù)的過(guò)程中，如果新構(gòu)造二叉樹(shù)的根

51、結(jié)點(diǎn)的關(guān)鍵字值與另一棵二叉樹(shù)根結(jié)點(diǎn)的關(guān)鍵字值相同，下一次選擇根的關(guān)鍵字值最小或次小時(shí)該選哪一個(gè)？ Huffman樹(shù)82共一百二十七頁(yè)問(wèn)題4. 用Huffman樹(shù)構(gòu)造最佳判定(pndng)樹(shù)，內(nèi)、外結(jié)點(diǎn)各起什么作用？帶權(quán)路徑長(zhǎng)度表示什么意思？問(wèn)題5. 用Huffman樹(shù)構(gòu)造不等長(zhǎng)的Huffman編碼，一段報(bào)文的總（二進(jìn)制）編碼數(shù)用什么衡量？問(wèn)題1. 堆與二叉排序樹(shù)有何不同？問(wèn)題2. 堆用數(shù)組作為其存儲(chǔ)，那么它是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)？ 問(wèn)題3. 堆作為優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)，插入和刪除在堆得什么位置實(shí)施？堆（heap）83共一百二十七頁(yè)問(wèn)題(wnt)4. 使用 siftDown() 從結(jié)點(diǎn) r 開(kāi)始向

52、下篩選局部形成堆的前提條件是什么？問(wèn)題5. 使用 siftDown() 對(duì)從結(jié)點(diǎn) r 到結(jié)點(diǎn) e 的子樹(shù)進(jìn)行篩選以形成堆，當(dāng) r e，或 r = e 時(shí)篩選結(jié)果如何？ 問(wèn)題6. 若想把數(shù)組中的 100 個(gè)元素調(diào)整為小根堆（或大根堆）需做多少次關(guān)鍵字比較？84共一百二十七頁(yè)第五章 知識(shí)點(diǎn)解析(ji x)本章“圖”的知識(shí)點(diǎn)有 7 個(gè)：圖的基本概念圖的存儲(chǔ)結(jié)構(gòu)(jigu)圖的遍歷最小生成樹(shù)圖的最短路徑圖的活動(dòng)網(wǎng)絡(luò)（拓?fù)渑判颍﹫D的活動(dòng)網(wǎng)絡(luò)（ 關(guān)鍵路徑）與嚴(yán)版教材的差別85共一百二十七頁(yè)界定了本章不予討論的帶自環(huán)的圖和多重邊的圖。嚴(yán)版沒(méi)有說(shuō)明。說(shuō)明了圖中簡(jiǎn)單路徑的長(zhǎng)度。嚴(yán)版沒(méi)有說(shuō)明。帶權(quán)圖的鄰接矩陣對(duì)角

53、線均為0。嚴(yán)版是。給出了鄰接矩陣和鄰接表常用操作的實(shí)現(xiàn)，后面有關(guān)圖的算法都用這些操作參與圖的運(yùn)算，不直接用圖定義中的結(jié)構(gòu)(jigu)分量參加圖的運(yùn)算。嚴(yán)版直接用圖定義中的結(jié)構(gòu)(jigu)分量參加圖的運(yùn)算。刪去嚴(yán)版求重連通圖關(guān)節(jié)點(diǎn)算法的實(shí)現(xiàn)代碼；把重連通圖改為雙連通圖，增加了有關(guān)三連通圖k連通圖的討論。86共一百二十七頁(yè)討論最小生成樹(shù)時(shí)引入了“貪婪法”。嚴(yán)版沒(méi)有說(shuō)明。對(duì)于求解最小生成樹(shù)問(wèn)題的Kruskal算法以及Prim算法，給出了使用小根堆和并查集（臨時(shí)引入）的較新版實(shí)現(xiàn)代碼，節(jié)省了存儲(chǔ)，提高了可讀性。改進(jìn)(gijn)了求單源最短路徑問(wèn)題的Dijkstra算法的實(shí)現(xiàn)代碼，路徑矩陣P改為路徑數(shù)組

54、P，同樣達(dá)到目的。在給出Dijkstra算法的框架時(shí)明確提出各邊權(quán)重非負(fù)。嚴(yán)版沒(méi)提。87共一百二十七頁(yè)在討論求每對(duì)頂點(diǎn)間最短路徑的Floyd算法時(shí)說(shuō)明了算法采用了“動(dòng)態(tài)規(guī)劃法”。嚴(yán)版沒(méi)有說(shuō)明。特別討論了Floyd算法的適用范圍，只要不存在包括帶負(fù)權(quán)重的邊的回路，不論有向圖還是無(wú)向圖，該算法都可以使用。增加了對(duì)不帶權(quán)有向圖最短路徑的討論。嚴(yán)版沒(méi)有。求關(guān)鍵路徑的算法與嚴(yán)版不同。嚴(yán)版是一邊拓?fù)渑判蛞贿吳笫录淖钤玳_(kāi)始時(shí)間和最遲開(kāi)始時(shí)間，本教材是假定各頂點(diǎn)已經(jīng)(y jing)按拓?fù)溆行蚓幪?hào)，再做計(jì)算的。算法簡(jiǎn)單得多。88共一百二十七頁(yè)圖的基本概念問(wèn)題1. 是否有“空?qǐng)D”的概念(ginin)？問(wèn)題2.

55、有 n 個(gè)頂點(diǎn)的無(wú)向圖最多有多少條邊，最少有多少條邊？無(wú)向連通圖的情形呢？問(wèn)題3. 有 n 個(gè)頂點(diǎn)的有向圖最多有多少條邊，最少有多少條邊？強(qiáng)連通圖的情形呢？問(wèn)題4. 在無(wú)向圖中頂點(diǎn)的度與邊有何關(guān)系？在有向圖中頂點(diǎn)的出度、入度與邊有何關(guān)系？問(wèn)題5. 圖中任意兩頂點(diǎn)間的路徑是用頂點(diǎn)序列標(biāo)識(shí)的，還是用邊序列標(biāo)識(shí)的？89共一百二十七頁(yè)問(wèn)題6. 圖中各個(gè)頂點(diǎn)的序號(hào)是規(guī)定的，還是人為可改變的？問(wèn)題7. 自由(zyu)樹(shù)和生成樹(shù)是什么關(guān)系？ 問(wèn)題1. 有 n 個(gè)頂點(diǎn)、e 條邊的無(wú)向圖的鄰接矩陣有多少矩陣元素？其中有多少零元素？有向圖的情形呢？問(wèn)題2. 為什么在有向圖的鄰接矩陣中，統(tǒng)計(jì)某行1的個(gè)數(shù)，得到頂點(diǎn)的

56、出度；統(tǒng)計(jì)某列1的個(gè)數(shù)，得到某頂點(diǎn)的入度？圖的存儲(chǔ)(cn ch)結(jié)構(gòu)90共一百二十七頁(yè)問(wèn)題3. 有一個(gè)存儲(chǔ) n 個(gè)頂點(diǎn)(dngdin) e 條邊的鄰接表，某個(gè)算法要求檢查每個(gè)頂點(diǎn)，并掃描每個(gè)頂點(diǎn)的邊鏈表，那么這樣的算法的時(shí)間復(fù)雜度是O(n*e)，還是O(n+e)?問(wèn)題4. 設(shè)每個(gè)頂點(diǎn)數(shù)據(jù)占 4 個(gè)字節(jié)，頂點(diǎn)號(hào)碼占 2 字節(jié)，每條邊的權(quán)值占 4 個(gè)字節(jié)，每個(gè)指針占 2 個(gè)字節(jié)。若一個(gè)無(wú)向圖有 n 個(gè)頂點(diǎn) e 條邊，請(qǐng)問(wèn)使用鄰接矩陣經(jīng)濟(jì)還是使用鄰接表經(jīng)濟(jì)？問(wèn)題5. 有向圖的鄰接表與逆鄰接表組合起來(lái)形成十字鏈表，它適合于什么場(chǎng)合？91共一百二十七頁(yè)問(wèn)題1. 圖的遍歷針對(duì)頂點(diǎn)，要求按一定順序訪問(wèn)圖中所

57、有頂點(diǎn)，且每個(gè)頂點(diǎn)僅訪問(wèn)一次。可否針對(duì)邊也使用遍歷算法？問(wèn)題2. 圖的深度優(yōu)先搜索類似(li s)于樹(shù)的先根遍歷，可歸屬于哪一類算法？問(wèn)題3. 圖的遍歷對(duì)無(wú)向圖和有向圖都適用嗎？問(wèn)題4. 圖的深度優(yōu)先遍歷如何體現(xiàn)“回溯”？問(wèn)題5. 圖的廣度優(yōu)先遍歷類似于樹(shù)的層次序遍歷，需要使用何種輔助結(jié)構(gòu)？圖的遍歷(bin l)92共一百二十七頁(yè)問(wèn)題6. 圖的廣度優(yōu)先生成樹(shù)是否比深度優(yōu)先生成樹(shù)的深度低？問(wèn)題7. 圖的深度優(yōu)先搜索是個(gè)遞歸的過(guò)程，而廣度優(yōu)先搜索為何是非遞歸的過(guò)程？ 問(wèn)題8. 圖的深度優(yōu)先搜索遍歷一個(gè)連通分量上的所有頂點(diǎn)如何得到生成樹(shù)？ 問(wèn)題9. 對(duì)無(wú)向圖進(jìn)行遍歷，在何條件(tiojin)下可以建

58、立一棵生成樹(shù)？在什么條件(tiojin)下得到一個(gè)生成森林，其中每個(gè)生成樹(shù)對(duì)應(yīng)圖的什么部分？ 問(wèn)題10. 對(duì)有向圖進(jìn)行遍歷，在何條件下可以建立一棵生成樹(shù)？在何條件下得到一個(gè)生成森林？ 93共一百二十七頁(yè)問(wèn)題11. 如何判斷一個(gè)無(wú)向圖中的關(guān)節(jié)點(diǎn)？如何以最少的邊構(gòu)成雙連通圖？問(wèn)題12. 設(shè)連通圖有6個(gè)頂點(diǎn)，雙連通圖、三連通圖、四連通圖、五連通圖如何構(gòu)造？ 問(wèn)題1. 圖的最小生成樹(shù)必須滿足(mnz)什么要求？問(wèn)題2. 構(gòu)造圖的最小生成樹(shù)有多種算法，都遇到在一組邊集合中選出權(quán)值最小的邊的問(wèn)題，用什么結(jié)構(gòu)輔助最好？圖的最小生成(shn chn)樹(shù)94共一百二十七頁(yè)問(wèn)題3. 把所有的邊按照其權(quán)值加入到小根

59、堆中，相應(yīng)算法的時(shí)間復(fù)雜度是多少？問(wèn)題4. Kruskal 算法中為了判斷一條邊的兩個(gè)端點(diǎn)(dun din)是否在同一連通分量上，采用何種輔助結(jié)構(gòu)？問(wèn)題5. Prim算法每次選擇一個(gè)端點(diǎn)在生成樹(shù)頂點(diǎn)集合 U，另一個(gè)端點(diǎn)不在生成樹(shù)頂點(diǎn)集合 V-U 的邊中權(quán)值最小的邊，采用什么輔助結(jié)構(gòu)？問(wèn)題1. 圖的最短路徑問(wèn)題必須滿足什么要求？圖的最短路徑(ljng)95共一百二十七頁(yè)問(wèn)題2. 用Dijkstra算法求最短路徑，為何要求所有邊上的權(quán)值必須大于0？ 問(wèn)題3. Dijkstra算法是求解單源最短路徑問(wèn)題的算法，可否用它解決單目標(biāo)最短路徑問(wèn)題？問(wèn)題4. 用Floyd算法求最短路徑，允許圖中有帶負(fù)權(quán)值的

60、邊，但為何不許有包含帶負(fù)權(quán)值的邊組成的回路(hul)？ 問(wèn)題1. 什么是拓?fù)渑判?？它是針?duì)何種結(jié)構(gòu)的？拓?fù)?tu p)排序96共一百二十七頁(yè)問(wèn)題2. 可以對(duì)一個(gè)有向圖的所有頂點(diǎn)從新編號(hào)，把所有表示邊的非零元素集中到鄰接矩陣的上三角部分。根據(jù)什么順序進(jìn)行頂點(diǎn)的編號(hào)？問(wèn)題3. 拓?fù)渑判虻囊粋€(gè)重要應(yīng)用是判斷(pndun)有向圖中是否有環(huán)。如何判斷(pndun)？問(wèn)題4. 如果調(diào)用深度優(yōu)先搜索算法，在每次遞歸結(jié)束并退出時(shí)輸出頂點(diǎn)，就可得到一個(gè)逆拓?fù)溆行虻男蛄?。此方法有效性的前提是什么？?wèn)題5. 為什么拓?fù)渑判虻慕Y(jié)果不唯一？關(guān)鍵(gunjin)路徑97共一百二十七頁(yè)問(wèn)題1. 關(guān)鍵路徑法的應(yīng)用背景是什么？