計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)部分真題解析講義

《《數(shù)據(jù)結(jié)構(gòu)》４０８及歷年名校真題精考試點(diǎn)考試點(diǎn)（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課電話(huà)：４００６８８５第一 線性線性表是一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，在線性表方面，主要考查線性表的定義和基本操作、線性表的實(shí)現(xiàn)。在線性表實(shí)現(xiàn)方面，要掌握的是線性表的存儲(chǔ)結(jié)構(gòu)，包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，特別是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是考查的重點(diǎn)。另外，還要掌握線性表的基本應(yīng)用。線性表這一章里面的知識(shí)點(diǎn)不多，但要做到深刻理解，能夠應(yīng)用相關(guān)知識(shí)點(diǎn)解決實(shí)際問(wèn)題。鏈表上插入、刪除節(jié)點(diǎn)時(shí)的指針操作是選擇題的一個(gè)?？键c(diǎn)，諸如雙向鏈表等一些相對(duì)復(fù)雜的鏈表上的操作也是可以出現(xiàn)在綜合應(yīng)用題當(dāng)中的。※【大綱解讀通過(guò)對(duì)歷年計(jì)算機(jī)考研中數(shù)據(jù)結(jié)構(gòu)部分考試大綱的分析不難看出，最近幾年計(jì)算機(jī)考研中針對(duì)數(shù)據(jù)結(jié)構(gòu)第一部分線性表的考點(diǎn)、試題類(lèi)型及側(cè)重點(diǎn)幾乎沒(méi)有改變。依然保持的是最初的要求：（一）線性表的定義及基本操（二）線性表的實(shí)現(xiàn)１．順序存儲(chǔ)２．鏈?zhǔn)酱妫常€性表的應(yīng)其中，在２００９年綜合題第４２題中考查了線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的應(yīng)用【考點(diǎn)歸納作為線性結(jié)構(gòu)的開(kāi)篇章節(jié)，線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。在這一章，第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯?chǔ)的概念，鏈?zhǔn)酱鎯?chǔ)概念將是整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重，無(wú)論哪一章都涉及到了這個(gè)概念。總體來(lái)說(shuō)，線性表一章可供考查的重要考點(diǎn)有以下幾個(gè)方面１．線性表的相關(guān)基本概念，如：前驅(qū)、后繼、表長(zhǎng)、空表、首元結(jié)點(diǎn)，頭結(jié)點(diǎn)，頭指針等概念。１２．線性表的結(jié)構(gòu)特點(diǎn)，主要是指：除第一及最后一個(gè)元素外，每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。３．線性表的順序存儲(chǔ)方式及其在具體語(yǔ)言環(huán)境下的兩種不同實(shí)現(xiàn)：表空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處。４．線性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算：?jiǎn)捂湵怼⒀h(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見(jiàn)的考查方式。此外，近年來(lái)在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出（可能是順序也可能是倒序）的問(wèn)題。在鏈表的小題型中，經(jīng)?？嫉揭恍┲T如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請(qǐng)大家注意。５．線性表的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)情況下，其不同的優(yōu)缺點(diǎn)比較，即其各自適用的場(chǎng)合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。※及典型題精講精例題精【例１】（２００９４２綜合應(yīng)用題）已知一個(gè)帶有頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)圖１ 單鏈表結(jié)點(diǎn)結(jié)假設(shè)該鏈表只給出了頭指針ｌｉｓｔ。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第Ｋ個(gè)位置上的結(jié)點(diǎn)（ｋ為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的ｄａｔａ值，并返回１；否則，只返回０。要求：（１）描述算法的基本設(shè)計(jì)思想（２）描述算法的詳細(xì)實(shí)現(xiàn)步驟（３）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言描述算法（使用Ｃ或Ｃ＋＋或ＪＡＶＡ語(yǔ)言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋?？键c(diǎn)還原 對(duì)單鏈表進(jìn)行查找的思路為：對(duì)單鏈表的結(jié)點(diǎn)依次掃描，檢測(cè)其數(shù)據(jù)域是否是我們所要查找的值，若是返回該結(jié)點(diǎn)的指針，否則返回ｎｕｌｌ。因?yàn)樵趩捂湵淼逆溣蛑邪撕罄^結(jié)點(diǎn)的存儲(chǔ)地址，所以當(dāng)我們實(shí)現(xiàn)的時(shí)候，只２知道該單鏈表的頭指針，即可依次對(duì)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行檢測(cè)【例２】（２０１０４２綜合應(yīng)用題）設(shè)將ｎ（ｎ，１）個(gè)整數(shù)存放到一維數(shù)組Ｒ中，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能有效的算法，將Ｒ中保有的序列循環(huán)左移Ｐ（０＜Ｐ＜ｎ）個(gè)位置，即將Ｒ中的數(shù)據(jù)由（Ｘ１，Ｘ２，…，Ｘｎ）變換為（Ｘｐ，Ｘｐ＋１，，Ｘｎ，Ｘ１，…，Ｘｐ１）。要求：（１）給出算法的基本設(shè)計(jì)思想（２）根據(jù)設(shè)計(jì)思想，采用Ｃ或Ｃ＋＋或ＪＡＶＡ語(yǔ)言表述算法，關(guān)鍵之處給出注釋?zhuān)ǎ常┱f(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度【例３ （ ４２綜合應(yīng)用題）一個(gè)長(zhǎng)度為Ｌ（Ｌ ＝１）的升序序列Ｓ，處在「Ｌ／２」個(gè)位置的數(shù)稱(chēng) Ｓ的中位數(shù)例如，若序列Ｓ１＝（１１，１３，１５，１７，１９），則Ｓ１的中位數(shù)是１５。兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若Ｓ２＝（２，４，６，８，２０），則Ｓ１和Ｓ２的中位數(shù)是１１?，F(xiàn)有兩個(gè)等長(zhǎng)升序序列Ａ和Ｂ，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，找出兩個(gè)序列Ａ和Ｂ的中位數(shù)。要求：（１）給出算法的基本設(shè)計(jì)思想（２）根據(jù)設(shè)計(jì)思想，采 Ｃ或Ｃ＋＋或ＪＡＶＡ語(yǔ)言描述算法，關(guān)鍵之處給出注釋?zhuān)ǎ常┱f(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度考點(diǎn)還原 所謂的中位數(shù)是指：將數(shù)據(jù)按大小順序排列起來(lái)，形成一個(gè)數(shù)列，居于數(shù)列中間位置的數(shù)叫中位數(shù)，且要分奇數(shù)與偶數(shù)兩種情況來(lái)分析。１：如果總數(shù)個(gè)數(shù)是奇數(shù)，按從小到大的順序，取中間的那個(gè)２：如果總數(shù)個(gè)數(shù)是偶數(shù)，按從小到大的順序，取中間那兩個(gè)數(shù)的平均數(shù)例：數(shù)列：１、９、１１中位數(shù)：９，而數(shù)列：１、９、１１、３９，則是（９＋１１）／２＝１０思考過(guò)程１：由于中位數(shù)是位于中間位置，所以容易想到的思路就是，設(shè)計(jì)一種以中位數(shù)隔開(kāi)，維護(hù)左右兩邊的數(shù)列，左邊都是小于中位數(shù)的，右邊都是大于中位數(shù)的數(shù)據(jù)結(jié)構(gòu)思考過(guò)程如何建立左右兩邊的數(shù)據(jù)結(jié)構(gòu)，才能易于與中位數(shù)比較，又易于插入刪除顯然，中位數(shù)的計(jì)算方式是，若數(shù)列為偶數(shù)，是左邊的最大值和右邊的最小值除２；若不是，也要維護(hù)這左右的最大值和右邊的最大值，原因是，經(jīng)常插入或刪除，數(shù)據(jù)的總數(shù)，時(shí)常在奇數(shù)和偶數(shù)之間變換。３所以，對(duì)于左邊的數(shù)列，我們?cè)噲D是設(shè)計(jì)出容易找到最小值的數(shù)據(jù)結(jié)構(gòu)，同理，右邊也一樣，所以自然而然，就想到堆。即大頂堆和小頂堆。得出簡(jiǎn)單結(jié)論：可以利用大堆和小堆來(lái)解決這個(gè)問(wèn)題，大致過(guò)程如下：１：用一個(gè)大頂堆存儲(chǔ)數(shù)列中不大于中位數(shù)的元素２：用一個(gè)小頂堆存儲(chǔ)數(shù)列中不小于中位數(shù)的元習(xí)題精—、選擇１．某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間?！灸祥_(kāi)大學(xué)２０００一、３（２分）】Ａ．單鏈 Ｂ．僅有頭指針的單循環(huán)鏈Ｃ．雙鏈表 Ｄ．僅有尾指針的單循環(huán)鏈表２．下面的敘述不正確的是 。【南京理工大學(xué)１９９６一、１０（２分）】Ａ．表性在鏈?zhǔn)酱鎯?chǔ)時(shí)，找第ｉ元素的時(shí)間同ｉ值成正Ｂ．性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，找第ｉ元素的時(shí)間同ｉ值無(wú)關(guān)Ｃ．性表在順序存儲(chǔ)時(shí)，找第ｉ元素的時(shí)間同ｉ值成正Ｄ．性表在順序存儲(chǔ)時(shí)，找第ｉ元素的時(shí)間同ｉ值無(wú)關(guān)３．在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除ｐ所指的結(jié)點(diǎn)時(shí)需修改指針 ?！疚靼搽娮涌萍即髮W(xué)１９９８一、１（２分）】Ａ．（ｐ＾．Ｌｌｉｎｋ）＾．Ｒｌｉｎｋ：＝ｐ＾．Ｒｌｉｎｋ（ｐ＾．Ｒｌｉｎｋ）＾．Ｌｌｉｎｋ：＝ｐ＾．Ｌｌｉｎｋ；Ｂ．ｐ＾．Ｌｌｉｎｋ：＝（ｐ＾．Ｌｌｉｎｋ）＾．Ｌｌｉｎｋ（ｐ＾．Ｌｌｉｎｋ）＾．Ｒｌｉｎｋ：＝ｐ；Ｃ．（ｐ＾．Ｒｌｉｎｋ）＾．Ｌｌｉｎｋ：＝ ｐ＾．Ｒｌｉｎｋ：＝（ｐ＾．Ｒｌｉｎｋ）＾．Ｄ．ｐ＾．Ｒｌｉｎｋ：＝（ｐ＾．Ｌｌｉｎｋ）＾．Ｌｌｉｎｋ ｐ＾．Ｌｌｉｎｋ：＝（ｐ＾．Ｒｌｉｎｋ）＾．Ｒｌｉｎｋ；二、判斷題１．線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。 【北京郵電大學(xué)１９９８一、２（２分）２．順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。（ ）【北京郵電大學(xué)２００２一、２（１分）】３．為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（ 學(xué)院１９９５一、１（１分）】【上海海運(yùn)學(xué)院１９９７一、２（１分）】三、填空１．對(duì)于一個(gè)具有ｎ個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié) ｐ后插入一個(gè)新結(jié)點(diǎn)的時(shí)間４雜度為 ，在給定值為ｘ的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 ?！竟枮I工業(yè)大學(xué)２００１一、１（２分）】２．下面程序段是逆轉(zhuǎn)單向循環(huán)鏈表的方法，ｐ０是原鏈表頭指針，逆轉(zhuǎn)后鏈表頭指針仍為ｐ０。（可以根據(jù)需要增加標(biāo)識(shí)符）ｐ：＝ｐ０；ｑ０：＝ＮＵＬＬ； （ （ （ （ （ ｐ＾．ｎｅｘｔ：＝ｑ０；ｐ０＾．ｎｅｘｔ：＝ｐ；ｐ０：＝ｐ；【中國(guó)人民大學(xué)２０００二、１（４分）３．對(duì)單鏈表中元素按插入方法排序的Ｃ語(yǔ)言描述算法如下，其中Ｌ為鏈表頭結(jié)點(diǎn)指針。請(qǐng)?zhí)畛渌惴ㄖ袠?biāo)出的空白處，完成其功能。ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ｉｎｔｄａｔａ；ｓｔｒｕｃｔｎｏｄｅ｝ｌｉｎｋｎｏｄｅ，ｌｉｎｋ；ｖｏｉｄＩｎｓｅｒｔｓｏｒｔ（ｌｉｎｋＬ）｛ｌｉｎｋｐ，ｑ，ｒ，ｐ＝Ｌ ＞ｎｅｘｔ； （１） （２） ｛ｒ＝Ｌ；ｑ＝ ＞ （３） ＆＆ｑ ＞ｄａｔａ＜＝ｐ ＞ｄａｔａ）｛ｒ＝ｑ；ｑ＝ｑ ＞ｎｅｘｔ；｝ｕ＝ｐ ＞ｎｅｘｔ； （４） （５） ；ｐ＝ｕ；｝｝【北京科技大學(xué)２００１二 四、應(yīng)用題１．試述頭結(jié)點(diǎn)，首元結(jié)點(diǎn)，頭指針這三個(gè)概念的區(qū)別．【武漢交通科技大學(xué)１９９６二、２（３分）】【西安電子科技大學(xué)２００１計(jì)應(yīng)用 二、１（５分）】２．已知有如下定義的靜態(tài)鏈表：ＴＹＰＥｃｏｍｐｏｎｅｎｔ＝ＲＥＣＯＲＤｄａｔａ：ｅｅｔｐｎｅｘｔ：０．．ｍａｘｓｉｚｅＥＮＤ ｓｔａｌｉｓｔ：ＡＲＲＡＹ［０．．ｚｅＯＦｐｎｎｔ５以及三個(gè)指針：ａｖ指向頭結(jié)點(diǎn)，ｐ指向當(dāng)前結(jié)點(diǎn)，ｐｒｅ指向前驅(qū)結(jié)點(diǎn)，現(xiàn)要求修改靜態(tài)鏈表中ｎｅｘｔ域中的內(nèi)容，使得該靜態(tài)鏈表有雙向鏈表的功能，從當(dāng)前結(jié)點(diǎn)ｐ既能往后查找，也能往前查找：（１）定義ｎｅｘｔ域中的內(nèi)容。（用老的ｎｅｘｔ域中的值表示）（２）如何得到當(dāng)前結(jié)點(diǎn)ｐ的前驅(qū)（ｐｒｅ）的前驅(qū)，給出計(jì)算式（３）如何得到ｐ的后繼，給出計(jì)算式；【中科院計(jì)算所２０００四（１０分）３．已知Ｌ是一個(gè)數(shù)據(jù)類(lèi)型ｌｉｎｋｅｄｌｉｓｔ的單循環(huán)鏈表，ｐａ和ｐｂ是指向Ｌ中結(jié)點(diǎn)的指針。簡(jiǎn)述下列程序段的功能。【山東科技大學(xué)２００１一、２（５分）】ＴＹＰＥｌｉｎｋｅｄｌｉｓｔ＝↑ｅｎｏｄｅ＝ｄａｔａ：ｄａｔａｔｙｐｅ；ｎｅｘｔ：ｌｉｎｋｅｄｌｉｓｔ ｐｐａ，ｐｂ：ｌｉｎｋｅｄｌｉｓｔ）； ｓｕｂｐ（ｓ，ｑ：ｌｉｎｋｅｄｌｉｓｔ）ｐ：＝ＷＩＬＥｐｎｅｘｔ＜＞ｑＤＯ ｐ：＝ｐ↑ｎｅｘｔ；ｐ↑ｎｅｘｔ：＝ｓｓｕｂｐ（ｐａ，ｐｂ）；ｓｕｂｐ（ｐｂ，ｐａ）；五、算法設(shè)計(jì)１．假設(shè)有兩個(gè)按元素值遞增次序排列的線性表，均以單鏈表形式存儲(chǔ)。請(qǐng)編寫(xiě)算法將這兩個(gè)單鏈表歸并為一個(gè)按元素值遞減次序排列的單鏈表，并要求利用原來(lái)兩個(gè)單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。【北京大學(xué)１９９８三、１（５分）】類(lèi)似本題的另外敘述有（１）設(shè)有兩個(gè)無(wú)頭結(jié)點(diǎn)的單鏈表，頭指針?lè)謩e為ｈａ，ｈｂ，鏈中有數(shù)據(jù)域ｄａｔａ，鏈域ｎｅｘｔ，兩鏈表的數(shù)據(jù)都按遞增序存放，現(xiàn)要求將ｈｂ表歸到ｈａ表中，且歸并后ｈａ仍遞增序，歸并中ｈａ表中已有的數(shù)據(jù)若ｈｂ中也有，則ｈｂ中的數(shù)據(jù)不歸并到ｈａ中，ｈｂ的鏈表在算法中不允許破壞?！灸暇├砉ご髮W(xué)１９９７四、３（１５分）】 ｅｒｇｅｈａ，ｈｂ）６（２）已知頭指針?lè)謩e為ｌａ和ｌｂ的帶頭結(jié)點(diǎn)的單鏈表中，結(jié)點(diǎn)按元素值非遞減有序排列。寫(xiě)出將ｌａ和ｌｂ兩鏈表歸并成一個(gè)結(jié)點(diǎn)按元素值非遞減有序排列的單鏈表（其頭指針為ｌｃ），并計(jì)算算法的時(shí)間復(fù)雜度?！狙嗌酱髮W(xué)１９９８五（２０分）】２．設(shè)Ｌｉｓｔｈｅａｄ為一單鏈表的頭指針，單鏈表的每個(gè)結(jié)點(diǎn)由一個(gè)整數(shù)域ＤＡＴＡ和指針域ＮＥＸＴ組成，整數(shù)在單鏈表中是無(wú)序的。編一ＰＡＳＣＡＬ過(guò)程，將Ｌｉｓｔｈｅａｄ鏈中結(jié)點(diǎn)分成一個(gè)奇數(shù)鏈和一個(gè)偶數(shù)鏈，分別由Ｐ，Ｑ指向，每個(gè)鏈中的數(shù)據(jù)按由小到大排列。程序中不得使用ＮＥＷ過(guò)程申請(qǐng)空間。【山東大學(xué)１９９３六（１５分）】類(lèi)似本題的另外敘述有（１）設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表Ａ分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表Ｂ、Ｃ，其中Ｂ表的結(jié)點(diǎn)為Ａ表中值小于零的結(jié)點(diǎn)，而Ｃ表的結(jié)點(diǎn)為Ａ表中值大于零的結(jié)點(diǎn)（鏈表Ａ的元素類(lèi)型為整型，要求Ｂ、Ｃ表利用Ａ表的結(jié)點(diǎn)）?！颈本├砉ご髮W(xué)２０００四、２（４分）】（２）設(shè)Ｌ為一單鏈表的頭指針，單鏈表的每個(gè)結(jié)點(diǎn)由一個(gè)整數(shù)域ｄａｔａ和指針域ＮＥＸＴ組成，整數(shù)在單鏈表中是無(wú)序的。設(shè)計(jì)算法，將鏈表中結(jié)點(diǎn)分成一個(gè)奇數(shù)鏈和一個(gè)偶數(shù)鏈，分別由Ｐ，Ｑ指向，每個(gè)鏈中的數(shù)據(jù)按由小到大排列，算法中不得申請(qǐng)新的結(jié)點(diǎn)空間?！厩鄭u海洋大學(xué)１９９９三（１２分）】（３）將一個(gè)帶頭結(jié)點(diǎn)的單鏈表Ａ分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表Ａ和Ｂ，使得Ａ表中含有原表中序號(hào)為奇數(shù)的元素，而Ｂ表中含有原表中序號(hào)為偶數(shù)的元素，且保持其相對(duì)順序不變。１）寫(xiě)出其類(lèi)型定義２）寫(xiě)出算法?！旧綎|大學(xué)１９９８ （９分）】【山東工業(yè)大學(xué)２０００九（９分）３．設(shè)有一頭指針為Ｌ的帶有表頭結(jié)點(diǎn)的非循環(huán)雙向鏈表，其每個(gè)結(jié)點(diǎn)中除有（前驅(qū)指針），ｄａｔａ（數(shù)據(jù)）和（后繼指針）域外，還有一個(gè)訪問(wèn)頻度域ｆｒｅｑ。在鏈表被起用前，其值均初始化為零。每當(dāng)在鏈表中進(jìn)行一次Ｌｏｃａｔｅ（Ｌ，ｘ）運(yùn)算時(shí)，令元素值為ｘ的結(jié)點(diǎn)中ｆｒｅｑ域的值增１，并使此鏈表中結(jié)點(diǎn)保持按訪問(wèn)頻度非增（遞減）的順序排列，同時(shí)最近訪問(wèn)的結(jié)點(diǎn)排在頻度相同的結(jié)點(diǎn)的最后，以便使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試編寫(xiě)符合上述要求的Ｌｏｃａｔｅ（Ｌ，ｘ）運(yùn)算的算法，該運(yùn)算為函數(shù)過(guò)程，返回找到結(jié)點(diǎn)的地址，類(lèi)型為指針型?！厩迦A大學(xué)１９９７二（１０分）】７第二 棧、隊(duì)列和數(shù)棧和隊(duì)列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊(duì)列的基本概念，以及他們之間的區(qū)別。對(duì)于棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)（包括順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）要有較深的理解，對(duì)于棧和隊(duì)列的應(yīng)用，例如，排隊(duì)問(wèn)題、子程序調(diào)用問(wèn)題、表達(dá)式問(wèn)題等，要搞清楚?！S數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲(chǔ)結(jié)構(gòu)，例如按行優(yōu)先、按列優(yōu)先等，某個(gè)元素存在的地址是什么。對(duì)于特殊矩陣（二維數(shù)組）的壓縮存儲(chǔ)原理也要搞清楚。棧、隊(duì)列和數(shù)組可以考查的知識(shí)點(diǎn)相比鏈表來(lái)說(shuō)要多一些。最基本的，是棧與隊(duì)列ＦＩＬＯ和ＦＩＦＯ的特點(diǎn)。比如針對(duì)棧ＦＩＬＯ的特點(diǎn)，進(jìn)棧出棧序列的問(wèn)題常出現(xiàn)在選擇題中。其次，是棧和隊(duì)列的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，這里一個(gè)?？键c(diǎn)是不同存儲(chǔ)結(jié)構(gòu)下棧頂指針、隊(duì)首指針以及隊(duì)尾指針的操作，特別是循環(huán)隊(duì)列判滿(mǎn)和判空的２種判斷方法。再次，是特殊矩陣的壓縮存儲(chǔ)，這個(gè)考點(diǎn)復(fù)習(xí)的重點(diǎn)可以放在二維矩陣與一維數(shù)組相互轉(zhuǎn)換時(shí)，下標(biāo)的計(jì)算方法，比如與對(duì)角線平行的若干行上數(shù)據(jù)非零的矩陣存放在一維數(shù)組后，各個(gè)數(shù)據(jù)點(diǎn)相應(yīng)的下標(biāo)的計(jì)算。這一章可能的大題點(diǎn)，在于利用堆?；蜿?duì)列的特性，將它們作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，支持實(shí)際問(wèn)題求解算法的設(shè)計(jì)，例如用棧解決遞歸問(wèn)題，用隊(duì)列解決圖的遍歷問(wèn)題等等。※【大綱解讀通過(guò)對(duì)歷年計(jì)算機(jī)考研中數(shù)據(jù)結(jié)構(gòu)部分考試大綱的分析不難看出，最近幾年計(jì)算機(jī)考研中針對(duì)數(shù)據(jù)結(jié)構(gòu)第二部分棧、隊(duì)列和數(shù)組的考點(diǎn)、試題類(lèi)型及側(cè)重點(diǎn)幾乎沒(méi)有改變。依然保持的是最初的要求：（一）棧和隊(duì)列的基本概（二）棧和隊(duì)列的順序存儲(chǔ)結(jié)（三）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)（四）棧和隊(duì)列的應(yīng)（五）特殊矩陣的壓縮存８【考點(diǎn)歸納棧與隊(duì)列，是很多學(xué)習(xí)ＤＳ的同學(xué)遇到第一只攔路虎，很多人從這一章開(kāi)始坐暈車(chē)，一直暈到現(xiàn)在。所以，理解棧與隊(duì)列，是走向ＤＳ高手的一條必由之路。學(xué)習(xí)此章前，你可以問(wèn)一下自己是不是已經(jīng)知道了以下幾點(diǎn)：１．棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享?xiàng)＃h(huán)隊(duì)列，鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)（請(qǐng)注意包括：存和取兩部分）的特點(diǎn)。２．遞歸算法。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：ｎ！階乘問(wèn)題，ｆｉｂ數(shù)列問(wèn)題，Ｈａｎｏｉ問(wèn)題，背包問(wèn)題，二叉樹(shù)的遞歸和非遞歸遍歷問(wèn)題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹(shù)與圖的問(wèn)題，多半會(huì)在樹(shù)與圖的相關(guān)章節(jié)中進(jìn)行考查。３．棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號(hào)的配對(duì)等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計(jì)題不多。４．循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿(mǎn)條件，循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌，棧與隊(duì)列一章可以不看書(shū)了。注意，我說(shuō)的是可以不看書(shū)，并不是可以不作題哦?！暗湫皖}精講精例題精【例１】（２００９１）為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是 Ａ． Ｂ．隊(duì) Ｃ． Ｄ．【例２】（２００９２）設(shè)棧Ｓ和隊(duì)列Ｑ的初始狀態(tài)均為空，元素ａｂｃｄｅｆｇ依次進(jìn)入棧Ｓ。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Ｑ，且７個(gè)元素出隊(duì)的順序是ｂｄｃｆｅａｇ，則棧Ｓ的容量至少是 Ａ． Ｂ． Ｃ． Ｄ．【例３】 （２０１０ １）若元素ａ，ｂ，ｃ，ｄ，ｅ，ｆ依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是 Ａ． Ｂ． Ｃ． Ｄ．【例４ （ ２）某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出９操作，則不可能得到的順序 Ａ． Ｂ． Ｃ． Ｄ．【例５】（２０１１２）元素ａ，ｂ，ｃ，ｄ，ｅ依次進(jìn)入初始非空的棧中。若元素進(jìn)棧后可以停留，可以出棧，直到所有元素都出棧，則在所有的可能的出棧序列中，以元素ｄ開(kāi)頭的序列的個(gè)數(shù)為 Ａ． Ｂ． Ｃ． Ｄ．【例６】（２０１１３）一直循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組Ａ［０…ｎ１］中，且隊(duì)列非空時(shí)ｆｒｏｎｔ和ｒｅａｒ分別指向隊(duì)頭和隊(duì)尾。若初始時(shí)隊(duì)列為空，且要求第一個(gè)進(jìn)入隊(duì)列的元素在Ａ［０］處，則初始時(shí)ｆｒｏｎｔ和ｒｅａｒ的值分別為 Ａ．０， Ｂ．０．ｎ Ｃ．ｎ１， Ｄ．ｎ１，ｎ【例７】（２０１２３）已知操作符包括‘＋’，‘’，‘’，‘／’，‘（’和‘）’，將中綴表達(dá)式ａ＋ｂａ×（（ｃ＋ｄ）／ｅｆ）＋ｇ轉(zhuǎn)化為等價(jià)的后綴表達(dá)式ａｂ＋ａｃｄ＋ｅ／ｆ×ｇ＋時(shí)，用棧來(lái)存放暫時(shí)還不能確定的運(yùn)算次序的操作符，若棧初始時(shí)為空，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是 Ａ． Ｂ． Ｃ． Ｄ．習(xí)題精—、選擇１．一個(gè)棧的輸入序列為 １２３４５，則下列序列中不可能是棧的輸出序列的是（ ）。Ａ．２３４１ Ｂ．５４１３ Ｃ．２３１４ Ｄ．１５４３【南開(kāi)大學(xué)２０００一、１】【山東大學(xué)２００１二、４（１分）】【北京理工大學(xué)２０００一、２（分）２．設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 ）數(shù)據(jù)結(jié)最佳Ａ．線性表的順序存儲(chǔ)結(jié) Ｂ．隊(duì)Ｃ．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié) Ｄ．【西安電子科技大學(xué)１９９６一、６（２分）３．用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的 ）位置?！厩迦A大學(xué)１９９８一、１（分）

Ａ．鏈 Ｂ．鏈 Ｃ．鏈二、判斷１．消除遞歸不一定需要使用棧，此說(shuō)法 ）。【中科院計(jì)算所１９９８二、２（２分）【中國(guó)科技大學(xué)１９９８二、２（２分）２．棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。 ）【中科院軟件所１９９９六、（５）（分）３．隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。 ）【上海交大學(xué)１９９８一、２】三、填空題１．設(shè)有一個(gè)空棧，棧頂指針為０Ｈ十六進(jìn)制），現(xiàn)有輸入序列為１，２，３，４，５，經(jīng)過(guò)ＨＨＰＯＰ，ＨＰＯＰ，ＨＰＵＳＨ之后，輸出序列是 ，而棧頂指針值 Ｈ。設(shè)棧為順序棧，每個(gè)元素占４個(gè)字節(jié)?！疚靼搽娮涌萍即髮W(xué)１９９８二、１（４分）】２．在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否（１）；在作退棧運(yùn)算時(shí)應(yīng)先判別棧是（２）；當(dāng)棧中元素為ｎ個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為（３）。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的（４）分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)（５）時(shí)才產(chǎn)生溢出?！旧綎|工業(yè)大學(xué)１９９４一、１（５分）】３．算術(shù)表達(dá)式求值的流程，其中ＯＰＴＲ為算術(shù)符棧，ＯＰＮＤ為操作數(shù)棧，ｐｒｅｃｅｄｅ（ｏｐｅｒ１，ｏｐｅｒ２）是比較運(yùn)算符優(yōu)先級(jí)別的函數(shù)，ｏｐｅｒａｔｅ（ｏｐｎｄ１，ｏｐｅｒ，ｏｐｎｄ２）為兩操作數(shù)的運(yùn)算結(jié)果函數(shù)。（＃表示運(yùn)算起始和終止符號(hào)）【西北工業(yè)大學(xué)１９９９六、２（７分）】 ｅｘｐｒｅｄｕｃｅｄ：ｏｐｅｒａｎｄｔｙｐｅ；ＩＮＩＴＳＴＡＣＫ（ＯＰＴＲ）；ＨＯＰＴＲ＂＃＂）；ＷＬ ＮＯＴ（（ｗ＝＇＃’）ＡＮＤ（ＧＥＴＴＯＰ（ＯＰＴＲ）＝＇＃＇））ＤＯＩＦＮＯＴｗｉｎｏｐＴＨＥＮＨＯＰＮＤ，ｗ）；ＥＬＳＥＣＡＳＥｐｒｅｃｅｄｅ（ＧＥＴＴＯＰ（ＯＰＴＲ），ｗ）＇＜＇：［（ ；ｒｅａｄ（ｗ）；＇＝＇：［（ ；ｒｅａｄ（ｗ）；］＇＞＇：［ｔｈｅｔａ：＝ＰＯＰ（ＯＰＴＲ）；ｂ：＝ＰＯＰ（ＯＰＮＤ）；ａ：＝ＰＯＰ（ＯＰＮＤ）（ ；ＲＥＴＵＲＮ（ＧＥＴＴＯＰ（ＯＰＮＤ））；四、應(yīng)用１．假設(shè)以Ｓ和Ｘ分別表示入棧和出棧操作，則對(duì)初態(tài)和終態(tài)均為空的棧操作可由Ｓ和Ｘ組成的序列表示（如ＳＸＳＸ）。（１）試指出判別給定序列是否合法的一般規(guī)則（２）兩個(gè)不同合法序列（對(duì)同一輸入序列）能否得到相同的輸出元素序列？如能得到，請(qǐng)舉列說(shuō)明?！緰|南大學(xué)１９９２二（１０分）】２．試證明：若借助棧由輸入序列１，２，…，ｎ得到輸出序列為Ｐ１，Ｐ２，…，Ｐｎ（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ｉ＜ｊ＜ｋ，使Ｐｊ＜Ｐｋ＜Ｐｉ?！旧虾＝煌ù髮W(xué)１９９８二（１５分）】３．對(duì)下面過(guò)程寫(xiě)出調(diào)用Ｐ（３）的運(yùn)行結(jié)果。ＰＲＯＣＥＤＵＲＥｐ（ｗ：ｉｎｔｅｇｅｒ）；ＩＦｗ＞０ｐ（ １）ｗｒｉｔｅｌｎ（ｗ）；｛輸出Ｗｐ（ｗ ＥＮＤ；【西北大學(xué)２００１三、７４．一個(gè)循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)描述如下：ＴＹＰＥｓｅｑｕｅｕｅｔｐ＝ＲＥＣＯＲＤｅｌｅｍ：ＡＲＲＡＹ［１．．ＭＡＸＳＩＺＥＯＦｌｅｔｐｆｒｏｎｔ，ｒｅａｒ：０．．ＭＡＸＳＥ給出循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿(mǎn)的判斷條件，并且分析一下該條件對(duì)隊(duì)列實(shí)際存儲(chǔ)空間大小的影響，如果為了不損失存儲(chǔ)空間，你如何改進(jìn)循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿(mǎn)的判斷條件【西北工業(yè)大學(xué)１９９９ （８分）５．順序隊(duì)列一般應(yīng)該組織成為環(huán)狀隊(duì)列的形式，而且一般隊(duì)列頭或尾其中之一應(yīng)該特殊處理。例如，隊(duì)列為ｌｉｓｔａｒｒａｙ［０．．ｎ１］，隊(duì)列頭指針 ｆｒｏｎｔ，隊(duì)列尾指針為則ｌｉｓｔａｒｒａｙ［ｒｅａｒ］表示下一個(gè)可以插入隊(duì)列的位置。請(qǐng)解釋其原因。【北京大學(xué)—、３（２０／３分）五、算法設(shè)計(jì)１．設(shè)有兩個(gè)棧Ｓ１，Ｓ２都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)［Ｏ．．ｍａｘｓｉｚｅ１］，為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長(zhǎng)的存儲(chǔ)方式。試設(shè)計(jì)Ｓ１，Ｓ２有關(guān)入棧和出棧的操作算法。【哈爾濱工業(yè)大學(xué)２００１七（１２分）】【北京科技大學(xué)２００１九、１（１０分）】２．請(qǐng)利用兩個(gè)棧Ｓ１和Ｓ２來(lái)模擬一個(gè)隊(duì)列。已知棧的三個(gè)運(yùn)算定義如下：（ＳＴ，ｘ）：元素ｘ入ＳＴ棧；ＰＯＰ（ＳＴ，ｘ）：ＳＴ棧頂元素出棧，賦給變量ｘ；ｐｔｙＳＴ）：判ＳＴ棧是否為空。那么如何利用棧的運(yùn)算來(lái)實(shí)現(xiàn)該隊(duì)列的三個(gè)運(yùn)算：ｅｎｑｕｅｕｅ：插入一個(gè)元素入隊(duì)列；ｄｅｑｕｅｕｅ：刪除一個(gè)元素出隊(duì)列；ｑｕｅｕｅｅｐｔｙ：判隊(duì)列為空。（請(qǐng)寫(xiě)明算法的思想及必要的注釋?zhuān)疚靼搽娮涌萍即髮W(xué)２００１軟件 五（１０分）】【上海交通大學(xué)１９９９二（１２分）】【河海大學(xué)１９９８三（１２分）】類(lèi)似本題的另外敘述有（１）有兩個(gè)長(zhǎng)度相同的棧Ｓ１，Ｓ２，已知以下入棧、出棧、判棧滿(mǎn)和判?？詹僮鳎?ｐｕｓｈ（Ｓｔａｃｋ：Ｓｔａｃｋｔｙｐｅ；ｘ：Ｄａｔａｔｙｐｅ）；ＦＵＮＣＴＩＯＮＰｏｐ（Ｓｔａｃｋ：Ｓｔａｃｋｔｙｐｅ）：Ｄａｔａｔｙｐｅ；ＦＵＮＣＴＩＯＮＦｕｌｌ（Ｓｔａｃｋ：Ｓｔａｃｋｔｙｐｅ）：Ｂｏｏｌｅａｎ；ＦＵＮＣＴＩＯＮＥｐｔｙ（Ｓｔａｃｋ：Ｓｔａｃｋｔｙｐｅ）Ｂｏｏｌｅａｎ；現(xiàn)用此二棧構(gòu)成一個(gè)隊(duì)列，試寫(xiě)出下面入隊(duì)列、出隊(duì)列操作算法： ＥｎＱｕｅｕｅ（ｘ：Ｄａｔａｔｙｐｅ）；ＦＵＮＣＴＩＯＮＤｅＱｕｅｕｅ：【北京郵電大學(xué)２０００六（１０分）３．已知Ｑ是一個(gè)非空隊(duì)列，Ｓ是一個(gè)空棧。僅用隊(duì)列和棧的ＡＤＴ函數(shù)和少量工作變量，使用Ｐａｓｃａｌ或Ｃ語(yǔ)言編寫(xiě)一個(gè)算法，將隊(duì)列Ｑ中的所有元素逆置。棧的ＡＤＴ函數(shù)有：ｋｅＥｐｔｙｓ：ｓｔａｃｋ）；／／置空ｐｕｓｈ（ｓ：ｓｔａｃｋ；ｖａｌｕｅ：ｄａｔａｔｙｐｅ）；／／新元素ｖａｌｕｅ進(jìn)棧ｐｏｐ（ｓ：ｓｔａｃｋ）：ｄａｔａｔｙｐｅ； ／／出棧，返回棧頂值ｉｓＥｐｔｙｓ：ｓｔａｃｋ）：Ｂｏｏｌｅａｎ；／／判?？辗耜?duì)列的ＡＤＴ函數(shù)有ｅｎｑｕｅｕｅ（ｑ：ｑｕｅｕｅ：ｖａｌｕｅ：ｄａｔａｔｙｐｅ）；／／元素ｖａｌｕｅ進(jìn)隊(duì)ｄｅＱｕｅｕｅ（ｑ：ｑｕｅｕｅ）：ｄａｔａｔｙｐｅ；／／出隊(duì)列，返回隊(duì)頭值ｐｙｑ：ｑｕｅｕｅ）：ｂｏｏｌｅａｎ；／／判隊(duì)列空否【清華大學(xué)２０００六（１２分）第三 樹(shù)與二叉二叉樹(shù)和樹(shù)是兩種不同的概念，這一點(diǎn)是必須要搞清楚的。在這個(gè)部分，我們要掌握樹(shù)的定義、二叉樹(shù)的定義及主要特征（特殊的二叉樹(shù)、二叉樹(shù)的性質(zhì)）。在二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)方面，特別是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)楹芏鄳?yīng)用都是建立在鏈?zhǔn)酱鎯?chǔ)基礎(chǔ)上，例如，二叉樹(shù)的遍歷（前序遍歷、中序遍歷、后序遍歷）就是一種典型的應(yīng)用。在特殊的二叉樹(shù)中，完全二叉樹(shù)的概念是必須要搞清楚的，其次，線索二叉樹(shù)的基本概念和構(gòu)造、二叉排序樹(shù)、平衡二叉樹(shù)的基本概念和應(yīng)用，特別是二叉排序樹(shù)的基本性質(zhì)和特點(diǎn)要能很好地理解。多棵獨(dú)立的樹(shù)就組成了森林，樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷、森林的遍歷、樹(shù)和二叉樹(shù)的轉(zhuǎn)換、森林和二叉樹(shù)的轉(zhuǎn)換等知識(shí)，也要有了了解。最后就是樹(shù)的應(yīng)用，通常會(huì)作為綜合應(yīng)用類(lèi)試題出現(xiàn)，包括等價(jià)類(lèi)問(wèn)題、哈夫（ｕｆｆａｎ樹(shù)和哈夫曼編碼等※【大綱解讀通過(guò)對(duì)歷年計(jì)算機(jī)考研中數(shù)據(jù)結(jié)構(gòu)部分考試大綱的分析不難看出，最近幾年計(jì)算機(jī)考研中針對(duì)數(shù)據(jù)結(jié)構(gòu)第一部分線性表的考點(diǎn)、試題類(lèi)型及側(cè)重點(diǎn)幾乎沒(méi)有改變。依然保持的是最初的要求：（一）樹(shù)的概（二）二叉１．二叉樹(shù)的定義及其主要特２．二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)３．二叉樹(shù)的遍歷４．線索二叉樹(shù)的基本概念和構(gòu)造５．二叉排序樹(shù)６．平衡二叉（三）樹(shù)、森１．書(shū)的存儲(chǔ)結(jié)２．森林與二叉樹(shù)的轉(zhuǎn)換３．樹(shù)和森林的遍歷１．等價(jià)類(lèi)問(wèn)２．哈夫曼（ｕｆｆａｎ樹(shù)和哈夫曼編【考點(diǎn)歸納從對(duì)線性結(jié)構(gòu)的研究過(guò)度到對(duì)樹(shù)形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實(shí)際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專(zhuān)業(yè)課總分。所以，樹(shù)這一章的重要性，已經(jīng)不說(shuō)自明了?？傮w來(lái)說(shuō)，樹(shù)一章的知識(shí)點(diǎn)包括二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)遍歷的三種算法（遞歸與非遞歸），在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹(shù)的其它算法，線索二叉樹(shù)的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹(shù)的概念、構(gòu)成和應(yīng)用，樹(shù)的概念和存儲(chǔ)形式，樹(shù)與森林的遍歷算法及其與二叉樹(shù)遍歷算法的聯(lián)系，樹(shù)與森林和二叉樹(shù)的轉(zhuǎn)換。※及典型題精講精例題精【例１】（２００９３）給定二叉樹(shù)如圖所示。設(shè)Ｎ代表二叉樹(shù)的根，Ｌ代表根結(jié)點(diǎn)的左子樹(shù)，Ｒ代表根結(jié)點(diǎn)的右子樹(shù)。若遍歷后的結(jié)點(diǎn)序列為３，１．７，５，６，２，４，則其遍歷方式是?Ａ． Ｂ． Ｃ． Ｄ．【例２】（ ４）下列二叉排序樹(shù)中，滿(mǎn)足平衡二叉樹(shù)定義的 【例３】（２００９ ５）已知一棵完全二叉樹(shù)的第６層（設(shè)根為第ｌ層）有８?jìng)€(gè)葉結(jié)點(diǎn)，則完全結(jié)點(diǎn)個(gè)數(shù)最多是 Ａ． Ｂ． Ｃ． Ｄ．【例４】（２００９６）將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)，若在二叉樹(shù)中，結(jié)點(diǎn)ｕ是結(jié)點(diǎn)ｖ的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來(lái)的森林中，ｕ和ｖ可能具有的關(guān)系是 父子關(guān)兄弟關(guān)的父結(jié)點(diǎn)與ｖ的父結(jié)點(diǎn)是兄弟關(guān)Ａ．只有 Ｂ．Ⅰ和 Ｃ．Ⅰ和 Ｄ．Ⅰ、Ⅱ和【例５】（２０１０ ３）下列線索二叉樹(shù)中（用虛線表示線索），符合后序線索樹(shù)定義的 【例６】（４）在下列所示的平衡二叉樹(shù)中插入關(guān)鍵字４８后得到一棵新平衡二叉樹(shù)，在新平衡二叉樹(shù)中，關(guān)鍵字３７所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是Ａ．１３， Ｂ．２４， Ｃ．２４， Ｄ．２４，【例７】（２０１０５）在一棵度為４的樹(shù)Ｔ中，若有２０個(gè)度為４的結(jié)點(diǎn)，１０個(gè)度為３的結(jié)點(diǎn)，１個(gè)度為２的結(jié)點(diǎn)，１０個(gè)度為１的結(jié)點(diǎn)，則樹(shù)Ｔ的葉結(jié)點(diǎn)個(gè)數(shù)是 Ａ． Ｂ． Ｃ． Ｄ．【例８】（２０１０６）對(duì)ｎ（ｎ大于等于２）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)，關(guān)于該樹(shù)的敘述中，錯(cuò)誤的是 Ａ．該樹(shù)一定是一棵完全二叉樹(shù)Ｂ．樹(shù)種一定沒(méi)有度為１的結(jié)Ｃ．樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)Ｄ．樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)【例９】（ ４）若一棵全完二叉樹(shù)有７６８?jìng)€(gè)結(jié)點(diǎn)，則該二叉樹(shù)葉結(jié)點(diǎn)的個(gè)數(shù)Ａ． Ｂ． Ｃ． Ｄ．【例１０】（２０１１５）若一棵二叉樹(shù)的前序遍歷和后序遍歷分別為１，２，３，４和４，３，２，１，則該二叉樹(shù)的中序遍歷不會(huì)是 Ａ．１，２，３， Ｂ．２，３，４， Ｃ．３，２，４， Ｄ．４，３，２，應(yīng)的二叉樹(shù)中無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)最多是 Ａ． Ｂ． Ｃ． Ｄ．【例１２】（２０１１７）對(duì)于下列關(guān)鍵序列，不能構(gòu)成某二叉樹(shù)排序中的一條查找路徑的序列是 Ａ．９５，２２，９１，２４，９４， Ｂ．９２，２０，９１，３４，８８，Ｃ．２１，８９，７７，２９，３６， Ｄ．１２，２５，７１，６８，３３，習(xí)題精—、選擇１．在一棵三元樹(shù)中度為３的結(jié)點(diǎn)數(shù)為２個(gè)，度為２的結(jié)點(diǎn)數(shù)為１個(gè)，度為１的結(jié)點(diǎn)為２個(gè)，則度為０的結(jié)點(diǎn)數(shù)為（ ）個(gè)?！竟枮I工業(yè)大學(xué)２００１二、２（２分）】Ａ．４ Ｂ．５ Ｃ．６ Ｄ．７２．若度為ｍ的哈夫曼樹(shù)中，其葉結(jié)點(diǎn)個(gè)數(shù)為ｎ，則非葉結(jié)點(diǎn)的個(gè)數(shù)為（ ）。【中科院計(jì)算所１９９９一、２（２分）】Ａ． Ｂ．?ｎ／ｍ Ｃ．?（ｎ １）／（ｍ１）」 Ｄ．?ｎ／（ｍ１）」 Ｅ．?（ｎ＋１）／（ｍ＋１）」１３．下述二叉樹(shù)中，哪一種滿(mǎn)足性質(zhì)：從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序（ ）。Ａ．二叉排序 Ｂ．哈夫曼Ｃ．ＡＶＬ Ｄ．【中國(guó)科技大學(xué)１９９８二、８（２分）】【中科院計(jì)算所１９９８二、８（２分）ｎ４．最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）、最優(yōu)查找樹(shù)均為平均查找路徑長(zhǎng)度∑ｗｈｉ最小的樹(shù)，ｉ＝中對(duì)最優(yōu)二叉樹(shù)，ｎ表示（１），對(duì)最優(yōu)查找樹(shù)，ｎ表示（２），構(gòu)造這兩種樹(shù)均（３）。【中科院計(jì)算所１９９９一、３（６分）】Ａ．結(jié)點(diǎn) Ｂ．葉結(jié)點(diǎn)Ｃ．非葉結(jié)點(diǎn)數(shù) Ｄ．度為２的結(jié)點(diǎn)數(shù)Ｅ．需要一張ｎ個(gè)關(guān)鍵字的有序表Ｆ．需要對(duì)ｎ個(gè)關(guān)鍵字進(jìn)行動(dòng)態(tài)插Ｇ．需要ｎ個(gè)關(guān)鍵字的查找概率表Ｈ．不需要任何前提５．下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是 ）Ａ．｛０，１０，１１０， Ｂ．｛１１，１０，００１，１０１，Ｃ．｛００，０１０，０１１０， Ｄ．｛ｂ，ｃ，ａａ，ａｃ，ａｂａ，ａｂｂ，【西安電子科技大學(xué)２００１應(yīng)用 一、６（２分）】二、判斷題１．二叉樹(shù)以后序遍歷序列與前序遍歷序列反映的同樣的信息（他們反映的信息不獨(dú)立）。【華南理工大學(xué)２００２一、７（１分）】２．完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉?！緰|南大學(xué)２００１一、 （１分）】【中科院軟件所１９９７一、２（１分）】【山東大學(xué)２００１一、４（１分）３．在任意一棵非空二叉排序樹(shù)，刪除某結(jié)點(diǎn)后又將其插入，則所得二叉排序樹(shù)與刪除前原二叉排序樹(shù)相同?！局锌圃很浖保梗梗芬弧ⅲ罚ǎ狈郑咳?、填空１．深度為Ｈ的完全二叉樹(shù)至少有（１）個(gè)結(jié)點(diǎn)；至多有（２）個(gè)結(jié)點(diǎn)；Ｈ和結(jié)點(diǎn)總數(shù)Ｎ之間的關(guān)系是（３）?！局锌圃河?jì)算所１９９８一、３（３分）１９９９二、４（３分）】【中國(guó)科技大學(xué)１９９８一、３（４分）】２．設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)的高度為０，則高度為ｋ的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)，最小結(jié)點(diǎn)數(shù) 。【北京大學(xué)１９９７一、１（４分）３．在一棵存儲(chǔ)結(jié)構(gòu)為三叉鏈表的二叉樹(shù)中，若有一個(gè)結(jié)點(diǎn)是它的雙親的左子女，且它的雙親有右子女，則這個(gè)結(jié)點(diǎn)在后序遍歷中的后繼結(jié)點(diǎn)是 。【中國(guó)人民大學(xué)２００１一、４（２分）】４．若以｛４，５，６，７，８｝作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)度【西安電子科技大學(xué)２００１軟件一、３（２分）】【廈門(mén)大學(xué)２００２六、２（４分）】５．設(shè)一棵二叉樹(shù)的結(jié)點(diǎn)定義為ｓｔｒｕｃｔＥｌｅｍＴｙｐｅｄａｔａ；ＢｉｎＴｒｅｅＮｏｄｅ 現(xiàn)采用輸入廣義表表示建立二叉樹(shù)。具體規(guī)定如下（１）樹(shù)的根結(jié)點(diǎn)作為由子樹(shù)構(gòu)成的表的表名放在表的最前面；（２）每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)用逗號(hào)隔開(kāi)。若僅有右子樹(shù)沒(méi)有左子樹(shù)，逗號(hào)不能省略。（３）在整個(gè)廣義表輸入的結(jié)尾加上一個(gè)特殊的符號(hào)（例如“?！保┍硎据斎虢Y(jié)束。例如，對(duì)于如右圖所示的二叉樹(shù)，其廣義表表示為Ａ（Ｂ（Ｄ，Ｅ（Ｇ）），Ｃ（，Ｆ））。此算法的基本思路是：依次從保存廣義表的字符串ｌｓ中輸入每個(gè)字符。若遇到的是字母（假設(shè)以字母作為結(jié)點(diǎn)的值），則表示是結(jié)點(diǎn)的值，應(yīng)為它建立一個(gè)新的結(jié)點(diǎn)，并把該結(jié)點(diǎn)作為左子女（當(dāng)ｋ＝１）或右子女（當(dāng)ｋ＝２）鏈接到其雙親結(jié)點(diǎn)上。若遇到的是左括號(hào)“（”，則表明子表的開(kāi)始，將ｋ置為１；若遇到的是右括號(hào)“）”，則表明子表結(jié)束。若遇到的是逗號(hào)“，”，則表示以左子女為根的子樹(shù)處理完畢，接著處理以右子女為根的子樹(shù)，將Ｋ置為２。在算法中使用了一個(gè)棧ｓ，在進(jìn)入子表之前，將根結(jié)點(diǎn)指針進(jìn)棧，以便括號(hào)內(nèi)的子女鏈接之用。在子表處理結(jié)束時(shí)退棧。相關(guān)的棧操作如下：ＭａｅＥｐｔｙｓ）置空棧 Ｐｕｓｈ（ｓ，ｐ） 元素ｐ入棧Ｐｏｐ（ｓ）退 Ｔｏｐ（ 存取棧頂元素的函下面給出了建立二叉樹(shù)的算法，其中有５個(gè)語(yǔ)句缺失，請(qǐng)閱讀此算法并把缺失的語(yǔ)句補(bǔ)上。（每空３分）ｖｏｉｄＣｒｅａｔＢｉｎＴｒｅｅ（ ＆ＢＴ，ｃｈａｒｌｓ）Ｓｔａｃｋ＜ＢｉｎＴｒｅｅＮｏｄｅ＞ｓ； ＭａｅＥｐｔｙｓ）；ＢＴ＝ＮＵＬＬ；／／置空二叉樹(shù) ｉｎｔｋ；ｉｓｔｒｅａｍｉｎｓ（ｌｓ）；／／把串ｌｓ定義為輸入字符串流對(duì)象ｉｎｓｃｈａｒｃｈ；ｉｎｓ＞＞ｃｈ；／／從ｉｎｓ順序讀入一個(gè)字符ｗｈｉｌｅ（ｃｈ！ ＝‘?！?／／逐個(gè)字符處理，直到遇到‘?！癁橹梗螅鳎椋簦悖瑁ǎ悖瑁悖幔螅濉ā海ǎ保?；ｋ＝１；ｂｒｅａｋ；ｃａｓｅ‘）’： ｐｏｐ（ｓ）； ｃａｓｅ’，’：（２） ｄｅｆａｕｌｔ：ｐ＝ｎｅｗＢｉｎＴｒｅｅＮｏｄｅ；（ ； ＞ｌｅｆｔＣｈｉｌｄ＝ＮＵＬＬ； ＞ｒｉｇｈｔＣｈｉｌｄ＝ｉｆ（ＢＴ＝＝ＮＵＬＬ）（４） ；ｅｌｓｅｉｆ（ｋ＝＝１）ｔｏｐ（ｓ）＞ｌｅｆｔＣｈｉｌｄ＝ｐ；ｅｌｓｅｔｏｐ（ｓ）＞ｒｉｇｈｔＣｈｉｌｄ＝ｐ；｝（ ｝｝【清華大學(xué)２００１六、（１５分）】四、應(yīng)用題１．一個(gè)深度為Ｌ的滿(mǎn)Ｋ叉樹(shù)有以下性質(zhì)：第Ｌ層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有Ｋ棵非空子樹(shù)，如果按層次順序從１開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào)，求：１）各層的結(jié)點(diǎn)的數(shù)目是多少２）編號(hào)為ｎ的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號(hào)是多少３）編號(hào)為ｎ的結(jié)點(diǎn)的第ｉ個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少４）編號(hào)為ｎ的結(jié)點(diǎn)有右兄弟的條件是什么？如果有，其右兄弟的編號(hào)是多少請(qǐng)給出計(jì)算和推導(dǎo)過(guò)程?！疚鞅惫I(yè)大學(xué)１９９９五（１０分）】【中科院自動(dòng)化所１９９６二、１（１０分）】類(lèi)似本題的另外敘述有（１）一棵高度為ｈ的滿(mǎn)ｋ叉樹(shù)有如下性質(zhì)：根據(jù)結(jié)點(diǎn)所在層次為０；第ｈ層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)；其余各層上每個(gè)結(jié)點(diǎn)都有ｋ棵非空子樹(shù)，如果按層次自頂向下，同一層自左向右，順序從１開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào)，試問(wèn)：１）各層的結(jié)點(diǎn)個(gè)數(shù)是多少？（３分２）編號(hào)為ｉ的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號(hào)是多少？（３分３）編號(hào)為ｉ的結(jié)點(diǎn)的第ｍ個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？（３分４）編號(hào)為ｉ的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟結(jié)點(diǎn)的編號(hào)是多少？（３分【清華大學(xué)１９９９ （１２分）２．已知完全二叉樹(shù)的第七層有１０個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹(shù)的結(jié)點(diǎn)數(shù)最多是多少【西安電子科技大學(xué)２０００計(jì)應(yīng) 一、４（５分）３．在一棵表示有序集Ｓ的二叉搜索樹(shù)（ｂｉｎａｒｙｓｅａｒｃｈｔｒｅｅ）中，任意一條從根到葉結(jié)點(diǎn)的路徑將Ｓ分為３部分：在該路徑左邊結(jié)點(diǎn)中的元素組成的集合Ｓｌ；在該路徑上的結(jié)點(diǎn)中的元素組成的集合Ｓ２；在該路徑右邊結(jié)點(diǎn)中的元素組成的集合Ｓ３。Ｓ＝Ｓ１∪Ｓ２Ｓ３。若對(duì)于任意的ａｌｂ∈Ｓ２ｃ∈是否總有ａｃ為什么？【清華大學(xué)２０００四（１０分）】【武漢大學(xué)２０００三、３４．一棵非空的二叉樹(shù)其先序序列和后序序列正好相反，畫(huà)出這棵二叉樹(shù)的形狀【西安電子科技大學(xué)２０００軟件 一、８（５分）】５．對(duì)如下算法，解答下列問(wèn)題。ＰＲＯＣＥＤＵＲＥｉｎｏｒｄｅｒ（Ｔ：ｂｉｔｒｅｅ）；ＢＥＧＩＮｔｏｐ：＝１；ｓ［ｔｏｐ］：＝Ｔ；Ｌｓ［ｔｏｐ］＜＞ＮＩＬＤＯＢＥＧＩＮｓ［ｔｏｐ＋１］：＝ｓ［ｔｏｐ］＾．ｌｃｈｉｌｄ；ｔｏｐ：＝ｔｏｐ１；ＩＦｔｏｐ＞１ＴＨＥＮＢＥＧＩＮｔｏｐ：＝ｔｏｐ１；ＷＲＩＴ（ｓ［ｔｏｐ］＾．ｄａｔａ）；ｓ［ｔｏｐ］：ｓ［ｔｏｐ］＾．ｒｃｈｉｌｄ；ＵＮＴＩＬｔｏｐ＝０ＥＮ（１）該算法正確嗎？循環(huán)結(jié)束條件ｔｏｐ＝能否滿(mǎn)足（２）若將ＩＦｔｏｐ＞１…改為ＩＦｔｏｐ＞０…是否正確（３）若將結(jié)束條件改為ｔｏｐ＝１，其它不變，是否正確（４）若僅將結(jié)束處條件改為（ｔｏｐ＝１）ＡＮＤ（ｓ［ｔｏｐ］＝ＮＩＬ），是否正確（５）試找出二叉樹(shù)中各結(jié)點(diǎn)在棧中所處層次的規(guī)律【西安電子科技大學(xué)２０００計(jì)應(yīng)用 三（１０分）】五、算法設(shè)計(jì)題１．在二叉樹(shù)中查找值為ｘ的結(jié)點(diǎn)，試編寫(xiě)算法（用Ｃ語(yǔ)言）打印值為ｘ的結(jié)點(diǎn)的所有祖先，假設(shè)值為ｘ的結(jié)點(diǎn)不多于一個(gè)，最后試分析該算法的時(shí)間復(fù)雜度（若不加分析，直接寫(xiě)出結(jié)果，按零分算）。【上海交通大學(xué)１９９８五】類(lèi)似本題的另外敘述有（１）在二叉樹(shù)中查找值為ｘ的結(jié)點(diǎn)，請(qǐng)編寫(xiě)一算法用以打印值為ｘ的結(jié)點(diǎn)的所有祖先，假設(shè)值為ｘ的結(jié)點(diǎn)不多于１個(gè)。注：采用非遞歸算法?！疚靼搽娮涌萍即髮W(xué)１９９６六（１０分）（２）設(shè)二叉樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)域的值互不相同，試設(shè)計(jì)一個(gè)算法將數(shù)據(jù)域值為ｘ的結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的數(shù)據(jù)域打印出來(lái)。【北方交通大學(xué)１９９６八（２０分）】（３）設(shè)二叉樹(shù)根指針為ｔ，且樹(shù)中結(jié)點(diǎn)值各不相同，寫(xiě)出算法ｄｉｓｐｆ（ｔ，ｘ），查找樹(shù)中值為ｔ的結(jié)點(diǎn)，并顯示出其所有祖先結(jié)點(diǎn)的值?！臼锥冀?jīng)貿(mào)大學(xué)１９９８三、４（２０分）】（４）若一棵二叉樹(shù)中沒(méi)有數(shù)據(jù)域值相同的結(jié)點(diǎn)，設(shè)計(jì)算法打印數(shù)據(jù)域值為ｘ的所有祖先結(jié)點(diǎn)的數(shù)據(jù)域。如果根結(jié)點(diǎn)的數(shù)據(jù)域值為ｘ或不存在數(shù)據(jù)域值為ｘ的結(jié)點(diǎn)，則什么也不打印。例如右圖所示的二叉樹(shù)，則打印結(jié)點(diǎn)序列為Ａ、Ｃ、Ｅ。【北京工業(yè)大學(xué) 五、（１６分）】２．寫(xiě)一非遞歸遍歷算法，使下圖樹(shù)遍歷輸出順序?yàn)樽帜疙樞?。【中?guó)人民大學(xué)２０００３．設(shè)兩棵二叉樹(shù)的的根結(jié)點(diǎn)地址分別為ｐ和ｑ，采用二叉鏈表的形式存儲(chǔ)這兩棵樹(shù)上所有的結(jié)點(diǎn)。請(qǐng)編寫(xiě)程序，判斷它們是否相似?！旧虾＝煌ù髮W(xué)２０００十二（８分）】類(lèi)似本題的另外敘述有（１）編寫(xiě)一個(gè)函數(shù)或過(guò)程判定兩棵二叉樹(shù)是否相似，所謂兩棵二叉樹(shù)ｓ和ｔ相似，即是要么它們都為空或都只有一個(gè)結(jié)點(diǎn)，要么它們的左右子樹(shù)都相似。【廈門(mén)大學(xué)２０００四、１（９分）】（２）設(shè)計(jì)判斷兩棵二叉樹(shù)是否相似的算法?！局袊?guó)礦業(yè)大學(xué)２０００四（１０分）４．已知二叉樹(shù)以二叉鏈表存儲(chǔ)，編寫(xiě)算法完成：對(duì)于樹(shù)中每一個(gè)元素值為ｘ的結(jié)點(diǎn)，刪去以它為根的子樹(shù)，并釋放相應(yīng)的空間。【北京輕工業(yè)學(xué)院１９９８二（１４分）】類(lèi)似本題的另外敘述有（１）設(shè)Ｔ是一棵給定的查找樹(shù)，試編寫(xiě)一個(gè)在樹(shù)中刪除根結(jié)點(diǎn)為ａ的子樹(shù)的程序，要求在刪除的過(guò)程中釋放該子樹(shù)所有結(jié)點(diǎn)所占有的存儲(chǔ)空間，這里假設(shè)樹(shù)Ｔ中結(jié)點(diǎn)所占有的存儲(chǔ)空間是通過(guò)動(dòng)態(tài)存儲(chǔ)分配取得的，其結(jié)點(diǎn)的形式為：（ｌｃｈｉｌｄ，ｄａｔａ，ｒｃｈｉｌｄ）【復(fù)旦大學(xué)１９９９七、（１５分）】第四 在數(shù)據(jù)結(jié)構(gòu)中，圖的結(jié)構(gòu)是最復(fù)雜的，這里的概念也是最多的。我們要掌握?qǐng)D的基本概念（有向圖、無(wú)向圖、連通、路徑、子圖、出度、入度、生成樹(shù)、最短路徑、關(guān)鍵路徑等）。圖的存儲(chǔ)及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無(wú)向圖的這２種存儲(chǔ)方法，要清楚圖的連通和存儲(chǔ)方法之間的關(guān)系。例如，一個(gè)頂點(diǎn)的出度和臨界矩陣中１的個(gè)數(shù)有什么關(guān)系，等等。圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這２種遍歷方法的算法實(shí)現(xiàn)。給出一個(gè)具體的圖，要能知道它的遍歷次序。在數(shù)據(jù)結(jié)構(gòu)課程中，圖的基本應(yīng)用是最多的，也是最復(fù)雜的，我們要掌握這些應(yīng)用的復(fù)雜度分析。要掌握的具體應(yīng)用主要包括最小（代價(jià)）生成樹(shù)、最短路徑、拓?fù)渑判?、關(guān)鍵路徑。在給出的一個(gè)具體的圖中，我們要會(huì)利用已知條件，求出上述應(yīng)用的結(jié)果。※【大綱解讀在這一章中需要識(shí)記的是圖以及基于圖的各種定義，存儲(chǔ)方式。要熟練掌握?qǐng)D的深度遍歷和廣度遍歷算法，這是用圖來(lái)解決應(yīng)用問(wèn)題時(shí)常用的算法基礎(chǔ)。需要掌握基于圖的多個(gè)算法，能夠以手工計(jì)算的方式在一個(gè)給定的圖上執(zhí)行特定的算法求解問(wèn)題。常見(jiàn)的應(yīng)用問(wèn)題直接給出或經(jīng)過(guò)抽象，會(huì)成為下列問(wèn)題：最小生成樹(shù)求解（ＰＲＩＭ算法和ＫＲＵＳＫＡＬ算法，兩種方法思想都很簡(jiǎn)單，但要注意不要混淆這兩種方法），拓?fù)渑判騿?wèn)題（這里會(huì)用到數(shù)組實(shí)現(xiàn)的鏈表，可以注意一下），關(guān)鍵路徑問(wèn)