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

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

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