數(shù)據(jù)結(jié)構(gòu)第一章1/176一、填空題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算程序設(shè)計(jì)問題中計(jì)算機(jī)操作對(duì)象以及它們之間關(guān)系和運(yùn)算等學(xué)科。2/1762.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是數(shù)據(jù)元素有限集合，R是D上關(guān)系有限集合。3.數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存放結(jié)構(gòu)、和數(shù)據(jù)運(yùn)算這三個(gè)方面內(nèi)容。3/1764.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。5.線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。4/1766．在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最終一個(gè)結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。5/1767.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)數(shù)能夠任意多個(gè)。6/1768.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)能夠任意多個(gè)。9．?dāng)?shù)據(jù)存放結(jié)構(gòu)可用四種基本存放方法表示，它們分別是次序、鏈?zhǔn)?、索引和散列?/17610.數(shù)據(jù)運(yùn)算最慣用有5種，它們分別是插入、刪除、修改、查找、排序。11.一個(gè)算法效率可分為時(shí)間效率和空間效率。8/176二、單項(xiàng)選擇題（B）1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一個(gè)：A）一對(duì)多關(guān)系B）多對(duì)多關(guān)系C）多對(duì)一關(guān)系D）一對(duì)一關(guān)系（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用計(jì)算機(jī)無關(guān)是數(shù)據(jù)

結(jié)構(gòu)；A)存放B)物理C)邏輯D)物理和存放9/176（C）3.算法分析目標(biāo)是：A)找出數(shù)據(jù)結(jié)構(gòu)合理性B)研究算法中輸入和輸出關(guān)系C)分析算法效率以求改進(jìn)D)分析算法易懂性和文檔性10/176（A）4.算法分析兩個(gè)主要方面是：A)空間復(fù)雜性和時(shí)間復(fù)雜性B)正確性和簡明性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性11/176（C）5.計(jì)算機(jī)算法指是：A)計(jì)算方法B)排序方法C)處理問題有限運(yùn)算序列D)調(diào)度方法12/176（B）6.計(jì)算機(jī)算法必須具備輸入、輸出和

等5個(gè)特征。A)可行性、可移植性和可擴(kuò)充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性13/176三、簡答題1.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)分嗎？答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按一些關(guān)系結(jié)合在一起數(shù)組元素。數(shù)據(jù)類型不但定義了一組帶結(jié)構(gòu)數(shù)據(jù)元素，而且還在其上定義了一組操作。14/1762.簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)不一樣點(diǎn)。答：線性結(jié)構(gòu)反應(yīng)結(jié)點(diǎn)間邏輯關(guān)系是一對(duì)一，非線性結(jié)構(gòu)反應(yīng)結(jié)點(diǎn)間邏輯關(guān)系是多對(duì)多。15/1763.算法定義和特征。算法是處理特定問題有限指令序列。特征：有限性、確定性、可行性、有0個(gè)或多個(gè)輸入數(shù)據(jù)、有1個(gè)或多個(gè)輸出結(jié)果。16/176

4.數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)有哪四類？集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)線性結(jié)構(gòu)前驅(qū)與后繼之間為一對(duì)一關(guān)系，非線性結(jié)構(gòu)前驅(qū)與后繼之間通常為一對(duì)多或多對(duì)多關(guān)系。17/176第二章線性表習(xí)題1次序表中邏輯上相鄰元素物理位置

相鄰。單鏈表中邏輯上相鄰元素物理位置

相鄰。18/176一定不一定19/1762在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)存放位置由其直接前驅(qū)結(jié)點(diǎn)鏈域值指示。20/1763.線性表中結(jié)點(diǎn)間關(guān)系是一對(duì)一。21/176判斷題（）1.鏈表每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。答：錯(cuò)誤。鏈表中結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。比如，雙向鏈表中結(jié)點(diǎn)能夠含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)指針。22/176（）2.鏈表刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)各個(gè)單元向前移動(dòng)。錯(cuò)，鏈表結(jié)點(diǎn)不會(huì)移動(dòng)，只是指針內(nèi)容改變。23/176（）3.線性表每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表每個(gè)結(jié)點(diǎn)能夠是一個(gè)復(fù)雜類型。錯(cuò)，混同了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是次序表，也能存放統(tǒng)計(jì)型數(shù)據(jù)。24/176（）4.次序表結(jié)構(gòu)適宜于進(jìn)行次序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。錯(cuò)，恰好說反了。次序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”25/176（）5.次序存放方式優(yōu)點(diǎn)是存放密度大，且插入、刪除運(yùn)算效率高。錯(cuò)，前二分之一正確，但后二分之一說法錯(cuò)誤，那是鏈?zhǔn)酱娣艃?yōu)點(diǎn)。次序存放方式插入、刪除運(yùn)算效率較低，在表長為n次序表中，插入和刪除一個(gè)數(shù)據(jù)元素，平均需移動(dòng)表長二分之一個(gè)數(shù)數(shù)據(jù)元素。26/176（）8.線性表在次序存放時(shí)，邏輯上相鄰元素未必在存放物理位置次序上相鄰。錯(cuò)誤。線性表有兩種存放方式，在次序存放時(shí)，邏輯上相鄰元素在存放物理位置次序上也相鄰。27/176單項(xiàng)選擇題（）1．?dāng)?shù)據(jù)在計(jì)算機(jī)存放器內(nèi)表示時(shí)，物理地址與邏輯地址相同而且是連續(xù)，稱之為：（A）存放結(jié)構(gòu)（B）邏輯結(jié)構(gòu)（C）次序存放結(jié)構(gòu)（D）鏈?zhǔn)酱娣沤Y(jié)構(gòu)28/176C29/176（）2.一個(gè)向量第一個(gè)元素存放地址是100，每個(gè)元素長度為2，則第5個(gè)元素地址是

（A）110（B）108（C）100（D）12030/176B31/176（）5.鏈接存放存放結(jié)構(gòu)所占存放空間：A分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系指針B只有一部分，存放結(jié)點(diǎn)值C只有一部分，存放表示結(jié)點(diǎn)間關(guān)系指針D分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)

32/176A33/176（）6.鏈表是一個(gè)采取

存放結(jié)構(gòu)存放線性表；（A）次序（B）鏈?zhǔn)剑–）星式（D）網(wǎng)狀34/176B35/176（）7.線性表若采取鏈?zhǔn)酱娣沤Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存放單元地址:（A）必須是連續(xù)（B）部分地址必須是連續(xù)（C）一定是不連續(xù)（D）連續(xù)或不連續(xù)都能夠36/176D37/176（）8．線性表在

情況下適合用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。（Ａ）需經(jīng)常修改線性表中結(jié)點(diǎn)值（Ｂ）需不停對(duì)線性表進(jìn)行刪除插入（Ｃ）線性表中含有大量結(jié)點(diǎn)（Ｄ）線性表中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜38/176B39/176（）10．設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則以下鏈?zhǔn)酱娣沤Y(jié)構(gòu)稱為（Ａ）循環(huán)鏈表（Ｂ）單鏈表（Ｃ）雙向循環(huán)鏈表（Ｄ）雙向鏈表40/176B41/176簡答題1.【嚴(yán)題集2.3②】試比較次序存放結(jié)構(gòu)和鏈?zhǔn)酱娣沤Y(jié)構(gòu)優(yōu)缺點(diǎn)。在什么情況下用次序表比鏈表好？42/176答：①次序存放時(shí)，相鄰數(shù)據(jù)元素存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存放單元地址必須是連續(xù)。優(yōu)點(diǎn)：存放空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。43/176②鏈?zhǔn)酱娣艜r(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存放空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存放空間利用率低。44/176次序表適宜于做查找這么靜態(tài)操作；鏈表宜于做插入、刪除這么動(dòng)態(tài)操作。若線性表長度改變不大，且其主要操作是查找，則采取次序表；若線性表長度改變較大，且其主要操作是插入、刪除操作，則采取鏈表。45/176第三章46/1761.向量(線性表)、棧和隊(duì)列都是

結(jié)構(gòu)，能夠在向量

位置插入和刪除元素；對(duì)于棧只能在

插入和刪除元素；對(duì)于隊(duì)列只能在

插入和

刪除元素。47/1761、向量、棧和隊(duì)列都是線性結(jié)構(gòu)，能夠在向量任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。48/1762.棧是一個(gè)特殊線性表，允許插入和刪除運(yùn)算一端稱為

。不允許插入和刪除運(yùn)算一端稱為

。49/1762.棧是一個(gè)特殊線性表，允許插入和刪除運(yùn)算一端稱為

棧頂

。不允許插入和刪除運(yùn)算一端稱為

棧底

。50/1763.

是被限定為只能在表一端進(jìn)行插入運(yùn)算，在表另一端進(jìn)行刪除運(yùn)算線性表。51/1763.

隊(duì)列

是被限定為只能在表一端進(jìn)行插入運(yùn)算，在表另一端進(jìn)行刪除運(yùn)算線性表。52/176二、判斷正誤（判斷以下概念正確性，并作出簡明說明。）（）1.線性表每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表每個(gè)結(jié)點(diǎn)能夠是一個(gè)復(fù)雜類型。

53/176二、判斷正誤（判斷以下概念正確性，并作出簡明說明。）（×）1.線性表每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表每個(gè)結(jié)點(diǎn)能夠是一個(gè)復(fù)雜類型。錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，能夠次序存放或鏈?zhǔn)酱娣牛c元素?cái)?shù)據(jù)類型無關(guān)。54/176（）2.在表結(jié)構(gòu)中最慣用是線性表，棧和隊(duì)列不太慣用。

55/176（×）2.在表結(jié)構(gòu)中最慣用是線性表，棧和隊(duì)列不太慣用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)慣用，CPU中也用隊(duì)列。56/176（）3.棧是一個(gè)對(duì)全部插入、刪除操作限于在表一端進(jìn)行線性表，是一個(gè)后進(jìn)先出型結(jié)構(gòu)。57/176（√）3.棧是一個(gè)對(duì)全部插入、刪除操作限于在表一端進(jìn)行線性表，是一個(gè)后進(jìn)先出型結(jié)構(gòu)。58/176（）6.棧和隊(duì)列是一個(gè)非線性數(shù)據(jù)結(jié)構(gòu)。

59/176（×）6.棧和隊(duì)列是一個(gè)非線性數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊線性表，對(duì)運(yùn)算定義略有不一樣而已。60/176（）7.棧和隊(duì)列存放方式既可是次序方式，也可是鏈接方式。

61/176（√）7.棧和隊(duì)列存放方式既可是次序方式，也可是鏈接方式。62/176（）8.隊(duì)是一個(gè)插入與刪除操作分別在表兩端進(jìn)行線性表，是一個(gè)先進(jìn)后出型結(jié)構(gòu)。63/176（×）8.隊(duì)是一個(gè)插入與刪除操作分別在表兩端進(jìn)行線性表，是一個(gè)先進(jìn)后出型結(jié)構(gòu)。 錯(cuò)，后半句不對(duì)。64/176（）9.一個(gè)棧輸入序列是12345，則棧輸出序列不可能是12345。

65/176（×）9.一個(gè)棧輸入序列是12345，則棧輸出序列不可能是12345。錯(cuò)，有可能。66/176三、單項(xiàng)選擇題（）1.棧中元素進(jìn)出標(biāo)準(zhǔn)是Ａ．先進(jìn)先出Ｂ．后進(jìn)先出Ｃ．棧空則進(jìn)Ｄ．棧滿則出

67/176三、單項(xiàng)選擇題（B）1.棧中元素進(jìn)出標(biāo)準(zhǔn)是Ａ．先進(jìn)先出Ｂ．后進(jìn)先出Ｃ．棧空則進(jìn)Ｄ．棧滿則出68/1766.【初程P71】從供選擇答案中，選出應(yīng)填入下面敘述

內(nèi)最確切解答，把對(duì)應(yīng)編號(hào)寫在答卷對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和a4，對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)棧或進(jìn)隊(duì)操作時(shí)，按a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)初始狀態(tài)都是空。69/176現(xiàn)要進(jìn)行棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到元素是A，第二次出棧得到元素是B是；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到元素是C，第二次出隊(duì)得到元素是D。經(jīng)操作后，最終在棧中或隊(duì)中元素還有E個(gè)。供選擇答案：A～D：①a1②a2③a3④a4E：①1②2③3④070/176答：ABCDE＝2,4,1,2,271/176第五章1.假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰6個(gè)字節(jié)存放，存放器按字節(jié)編址。已知A起始存放位置（基地址）為1000，則數(shù)組A體積（存放量）為

；末尾元素A57第一個(gè)字節(jié)地址為

；若按行存放時(shí)，元素A14第一個(gè)字節(jié)地址為

；若按列存放時(shí)，元素A47第一個(gè)字節(jié)地址為

。72/1761.假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰6個(gè)字節(jié)存放，存放器按字節(jié)編址。已知A起始存放位置（基地址）為1000，則數(shù)組A體積（存放量）為288B；末尾元素A57第一個(gè)字節(jié)地址為1282；若按行存放時(shí)，元素A14第一個(gè)字節(jié)地址為(8+4)×6+1000=1072；若按列存放時(shí)，元素A47第一個(gè)字節(jié)地址為(6×7＋4)×6＋1000）＝1276。(注：數(shù)組是從0行0列還是從1行1列計(jì)算起呢？由末單元為A57可知，是從0行0列開始！)73/1762.三元素組表中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素

、

和

。74/1762.三元素組表中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素行下標(biāo)、列下標(biāo)和元素值。75/1765.用三元組表表示以下稀疏矩陣：76/176解：三元素組表中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素行下標(biāo)、列下標(biāo)和元素值。588521325843667570266405-214932554377/1766以下各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們稀疏矩陣。45500113921824632778/1766答：為4×5矩陣，非零元素有5個(gè)1000000090080060070079/176第六章一、下面是相關(guān)二叉樹敘述，請(qǐng)判斷正誤（）1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)二叉樹鏈表中只有n—1個(gè)非空指針域。80/176（√）1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)二叉樹鏈表中只有n—1個(gè)非空指針域。81/176（）2.二叉樹中每個(gè)結(jié)點(diǎn)兩棵子樹高度差等于1。（）3.二叉樹中每個(gè)結(jié)點(diǎn)兩棵子樹是有序。82/176（×）2.二叉樹中每個(gè)結(jié)點(diǎn)兩棵子樹高度差等于1。（√）3.二叉樹中每個(gè)結(jié)點(diǎn)兩棵子樹是有序。83/176（）4.二叉樹中每個(gè)結(jié)點(diǎn)關(guān)鍵字值大于其左非空子樹（若存在話）全部結(jié)點(diǎn)關(guān)鍵字值，且小于其右非空子樹（若存在話）全部結(jié)點(diǎn)關(guān)鍵字值。84/176（×）4.二叉樹中每個(gè)結(jié)點(diǎn)關(guān)鍵字值大于其左非空子樹（若存在話）全部結(jié)點(diǎn)關(guān)鍵字值，且小于其右非空子樹（若存在話）全部結(jié)點(diǎn)關(guān)鍵字值。（沒有這個(gè)要求）85/176（）5.對(duì)于一棵非空二叉樹，它根結(jié)點(diǎn)作為第一層，則它第i層上最多能有個(gè)結(jié)點(diǎn)。86/176（×）5.對(duì)于一棵非空二叉樹，它根結(jié)點(diǎn)作為第一層，則它第i層上最多能有2i—1個(gè)結(jié)點(diǎn)。（應(yīng)）87/176（）6.用二叉鏈表法（link-rlink）存放包含n個(gè)結(jié)點(diǎn)二叉樹，結(jié)點(diǎn)2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。88/176（√）6.用二叉鏈表法（link-rlink）存放包含n個(gè)結(jié)點(diǎn)二叉樹，結(jié)點(diǎn)2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（正確。用二叉鏈表存放包含n個(gè)結(jié)點(diǎn)二叉樹，結(jié)點(diǎn)共有2n個(gè)鏈域。因?yàn)槎鏄渲校Y(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n-1個(gè)結(jié)點(diǎn)鏈域存放指向非空兒女結(jié)點(diǎn)指針，還有n+1個(gè)空指針。）即有后繼鏈接指針僅n-1個(gè)。89/176二、填空1．由３個(gè)結(jié)點(diǎn)所組成二叉樹有

種形態(tài)。2.一棵深度為6滿二叉樹有

個(gè)分支結(jié)點(diǎn)和

個(gè)葉子。

90/1761．由３個(gè)結(jié)點(diǎn)所組成二叉樹有5種形態(tài)。2.【計(jì)算機(jī)研】一棵深度為6滿二叉樹有n1+n2=0+n2=n0-1=31個(gè)分支結(jié)點(diǎn)和26-1=32個(gè)葉子。注：滿二叉樹沒有度為1結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。91/176二叉樹基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹遍歷次序有六種。最慣用是三種：前序法（即按NLR次序），后序法（即按

次序）和中序法（也稱對(duì)稱序法，即按LNR次序）。這三種方法相互之間相關(guān)聯(lián)。

若已知一棵二叉樹前序序列是BEFCGDH，中序序列是FEBGCHD，則它后序序列必是

。

92/1763.二叉樹基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹遍歷次序有六種。最慣用是三種：前序法（即按NLR次序），后序法（即按LRN次序）和中序法（也稱對(duì)稱序法，即按LNR次序）。這三種方法相互之間相關(guān)聯(lián)。若已知一棵二叉樹前序序列是BEFCGDH，中序序列是FEBGCHD，則它后序序列必是FEGHDCB。解：法1：先由已知條件畫圖，再后序遍歷得到結(jié)果；法2：不畫圖也能快速得出后序序列，只要找到根位置特征。由前序先確定root，由中序先確定左子樹。比如，前序遍歷BEFCGDH中，根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最終面。法3：遞歸計(jì)算。如B在前序序列中第一，中序中在中間（可知左右子樹上有哪些元素），則在后序中必為最終。如法對(duì)B左右子樹一樣處理，則問題得解。93/17694/1764.用5個(gè)權(quán)值{3,2,4,5,1}結(jié)構(gòu)哈夫曼（Huffman）樹帶權(quán)路徑長度是

。95/1764.【計(jì)算機(jī)研】用5個(gè)權(quán)值{3,2,4,5,1}結(jié)構(gòu)哈夫曼（Huffman）樹帶權(quán)路徑長度是33。解：先結(jié)構(gòu)哈夫曼樹，得到各葉子路徑長度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=3396/176三、選擇題()1.3個(gè)結(jié)點(diǎn)可組成

個(gè)不一樣形態(tài)二叉樹。A.2B.3C.4D.597/176(D)1.3個(gè)結(jié)點(diǎn)可組成

個(gè)不一樣形態(tài)二叉樹。A.2B.3C.4D.598/176（）2．二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以

。（Ａ）它不能用次序存放結(jié)構(gòu)存放;（Ｂ）它不能用鏈?zhǔn)酱娣沤Y(jié)構(gòu)存放;（Ｃ）次序存放結(jié)構(gòu)和鏈?zhǔn)酱娣沤Y(jié)構(gòu)都能存放;（Ｄ）次序存放結(jié)構(gòu)和鏈?zhǔn)酱娣沤Y(jié)構(gòu)都不能使用

99/176（C）2．二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以

。（Ａ）它不能用次序存放結(jié)構(gòu)存放;（Ｂ）它不能用鏈?zhǔn)酱娣沤Y(jié)構(gòu)存放;（Ｃ）次序存放結(jié)構(gòu)和鏈?zhǔn)酱娣沤Y(jié)構(gòu)都能存放;（Ｄ）次序存放結(jié)構(gòu)和鏈?zhǔn)酱娣沤Y(jié)構(gòu)都不能使用

100/176（）3．把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹形態(tài)是

。（Ａ）唯一（Ｂ）有各種（Ｃ）有各種，但根結(jié)點(diǎn)都沒有左孩子（Ｄ）有各種，但根結(jié)點(diǎn)都沒有右孩子101/176（A）3．把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹形態(tài)是

。（Ａ）唯一（Ｂ）有各種（Ｃ）有各種，但根結(jié)點(diǎn)都沒有左孩子（Ｄ）有各種，但根結(jié)點(diǎn)都沒有右孩子102/176()4.將一棵有50個(gè)結(jié)點(diǎn)完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為30結(jié)點(diǎn)右孩子編號(hào)為

。A.30B.60C.61D.62103/176(C)4.將一棵有50個(gè)結(jié)點(diǎn)完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為30結(jié)點(diǎn)右孩子編號(hào)為

。A.30B.60C.61D.62104/176()5.設(shè)森林F中有三棵樹，第一、第二和第三棵樹結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。與森林F對(duì)應(yīng)二叉樹根結(jié)點(diǎn)右子樹上結(jié)點(diǎn)個(gè)數(shù)是

。A.M1B.M1+M2C.M3D.M2+M3105/176(D)5.設(shè)森林F中有三棵樹，第一、第二和第三棵樹結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。與森林F對(duì)應(yīng)二叉樹根結(jié)點(diǎn)右子樹上結(jié)點(diǎn)個(gè)數(shù)是

。A.M1B.M1+M2C.M3D.M2+M3106/1766.二叉樹A。在完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有B，則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)二叉樹。由樹轉(zhuǎn)換成二叉樹里，一個(gè)結(jié)點(diǎn)N左兒女是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)C，而N右兒女是它在原樹里對(duì)應(yīng)結(jié)點(diǎn)D。供選擇答案A：①是特殊樹②不是樹特殊形式③是兩棵樹總稱④有是只有二個(gè)根結(jié)點(diǎn)樹形結(jié)構(gòu)B:①左子結(jié)點(diǎn)②右子結(jié)點(diǎn)③左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn)④弟兄C～D：①最左子結(jié)點(diǎn)②最右子結(jié)點(diǎn)③最鄰近右弟兄④最鄰近左弟兄⑤最左弟兄⑥最右弟兄答案：A=

B=

C=

D＝

107/1766.二叉樹A。在完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有B，則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)二叉樹。由樹轉(zhuǎn)換成二叉樹里，一個(gè)結(jié)點(diǎn)N左兒女是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)C，而N右兒女是它在原樹里對(duì)應(yīng)結(jié)點(diǎn)D。供選擇答案A：①是特殊樹②不是樹特殊形式③是兩棵樹總稱④有是只有二個(gè)根結(jié)點(diǎn)樹形結(jié)構(gòu)B:①左子結(jié)點(diǎn)②右子結(jié)點(diǎn)③左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn)④弟兄C～D：①最左子結(jié)點(diǎn)②最右子結(jié)點(diǎn)③最鄰近右弟兄④最鄰近左弟兄⑤最左弟兄⑥最右弟兄答案：A=

B=

C=

D＝

答案：ABCDE＝2，1，1，3108/176四、簡答題1一棵度為2樹與一棵二叉樹有何區(qū)分？109/176四、簡答題1一棵度為2樹與一棵二叉樹有何區(qū)分？答：度為2樹從形式上看與二叉樹很相同，但它子樹是無序，而二叉樹是有序。即，在普通樹中若某結(jié)點(diǎn)只有一個(gè)孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個(gè)孩子也有左右之分。110/1762給定二叉樹兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B

111/176112/1764.試寫出如圖所表示二叉樹分別按先序、中序、后序遍歷時(shí)得到結(jié)點(diǎn)序列。113/1764.試寫出如圖所表示二叉樹分別按先序、中序、后序遍歷時(shí)得到結(jié)點(diǎn)序列。

答：DLR：ABDFJGKCEHILM LDR:BFJDGKACHELIM LRD：JFKGDBHLMIECA114/176

6.【嚴(yán)題集6.21②】畫出和以下二叉樹對(duì)應(yīng)森林。115/1766答：注意根右邊子樹必定是森林，而孩子結(jié)點(diǎn)右子樹均為弟兄。116/176第七章117/176一、單項(xiàng)選擇題（）1.在一個(gè)圖中，全部頂點(diǎn)度數(shù)之和等于圖邊數(shù)

倍。A．1/2B.1C.2D.4（）2.在一個(gè)有向圖中，全部頂點(diǎn)入度之和等于全部頂點(diǎn)出度之和

倍。A．1/2B.1C.2D.4

118/176（C）1.在一個(gè)圖中，全部頂點(diǎn)度數(shù)之和等于圖邊數(shù)

倍。A．1/2B.1C.2D.4（B）2.在一個(gè)有向圖中，全部頂點(diǎn)入度之和等于全部頂點(diǎn)出度之和

倍。A．1/2B.1C.2D.4

119/176（）3.有8個(gè)結(jié)點(diǎn)無向圖最多有條邊。

A．14B.28C.56D.112

120/176（B）3.有8個(gè)結(jié)點(diǎn)無向圖最多有

條邊。

A．14B.28C.56D.112

121/176（）4.有8個(gè)結(jié)點(diǎn)有向完全圖有

條邊。

A．14B.28C.56D.112

122/176（C）4.有8個(gè)結(jié)點(diǎn)有向完全圖有

條邊。

A．14B.28C.56D.112

123/176二、填空題1.圖有

、

等存放結(jié)構(gòu)，遍歷圖有

、

等方法。124/1761.圖有鄰接矩陣、鄰接表等存放結(jié)構(gòu)，遍歷圖有深度優(yōu)先遍歷、廣度優(yōu)先遍歷等方法。125/176三、簡答題1.【嚴(yán)題集7.1①】已知如圖所表示有向圖，請(qǐng)給出該圖:(1)每個(gè)頂點(diǎn)入/出度；(2)鄰接矩陣；(3)鄰接表；(4)逆鄰接表。

126/176127/176128/176129/176130/176131/1764.已知一個(gè)圖頂點(diǎn)為A、B、C、D，其鄰接矩陣上三角元素（包含主對(duì)角線元素）全為0，其它元素均為1(以下表所表示)。請(qǐng)問：（1）該圖是有向圖還是無向圖?（2）請(qǐng)畫出該圖形。132/176

該圖是一個(gè)有向圖圖形以下:133/1765已知某網(wǎng)鄰接（出度）表，請(qǐng)畫出該網(wǎng)絡(luò)。節(jié)點(diǎn)結(jié)構(gòu)表示以下:134/176135/176第八章136/176一、填空題1.在數(shù)據(jù)存放無規(guī)律而言線性表中進(jìn)行檢索最正確方法是

。137/176一、填空題1.在數(shù)據(jù)存放無規(guī)律而言線性表中進(jìn)行檢索最正確方法是次序查找（線性查找）。138/1763.假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功結(jié)點(diǎn)數(shù)為1；比較兩次查找成功結(jié)點(diǎn)數(shù)為

；比較四次查找成功結(jié)點(diǎn)數(shù)為

。139/1763.假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功結(jié)點(diǎn)數(shù)為1；比較兩次查找成功結(jié)點(diǎn)數(shù)為2；比較四次查找成功結(jié)點(diǎn)數(shù)為8。140/1765.在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)查找方法是

。6.哈希法存放基本思想是由

決定數(shù)據(jù)存放地址。141/1765.在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)查找方法是哈希查找。6.哈希法存放基本思想是由關(guān)鍵字值決定數(shù)據(jù)存放地址。142/176（）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中

比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50143/176（A）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中

比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50144/176（）4.鏈表適合用于

查找A．次序B．二分法C．次序，也能二分法D．隨機(jī)145/176（A）4.鏈表適合用于

查找A．次序B．二分法C．次序，也能二分法D．隨機(jī)146/1766．要進(jìn)行線性查找，則線性表A；要進(jìn)行二分查找，則線性表B；要進(jìn)行散列查找，則線性表C。供選擇答案：A~C：①必須以次序方式存放②必須以鏈表方式存放③必須以散列方式存放④既能夠以次序方式，也能夠以鏈表方式存放⑤必須以次序方式存放且數(shù)據(jù)元素已按值遞增或遞減次序排好⑥必須以鏈表方式存放且數(shù)據(jù)元素已按值遞增或遞減次序排好答案：A=

B=

C=147/1766．要進(jìn)行線性查找，則線性表A；要進(jìn)行二分查找，則線性表B；要進(jìn)行散列查找，則線性表C。供選擇答案：A~C：①必須以次序方式存放②必須以鏈表方式存放③必須以散列方式存放④既能夠以次序方式，也能夠以鏈表方式存放⑤必須以次序方式存放且數(shù)據(jù)元素已按值遞增或遞減次序排好⑥必須以鏈表方式存放且數(shù)據(jù)元素已按值遞增或遞減次序排好答案：A=④B=⑤C=③148/1767.數(shù)據(jù)結(jié)構(gòu)反應(yīng)了數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系。鏈表是一個(gè)A，它對(duì)于數(shù)據(jù)元素插入和刪除B。通常查找線性表數(shù)據(jù)元素方法有C和D兩種方法，其中C是一個(gè)只適合于次序存放結(jié)構(gòu)但E方法；而D是一個(gè)對(duì)次序和鏈?zhǔn)酱娣沤Y(jié)構(gòu)均適用方法。A：①次序存放線性表②非次序存放非線性表 ③次序存放非線性表 ④非次序存放線性表B： ①不需要移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針②不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 ③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 ④既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C：①次序查找②循環(huán)查找 ③條件查找④二分法查找D：①次序查找②隨機(jī)查找 ③二分法查找④分塊查找E：①效率較低線性查找②效率較低非線性查找 ③效率較高非線性查找④效率較高線性查找答案：A＝

B＝

C＝

D＝

E＝

149/1767.數(shù)據(jù)結(jié)構(gòu)反應(yīng)了數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系。鏈表是一個(gè)A，它對(duì)于數(shù)據(jù)元素插入和刪除B。通常查找線性表數(shù)據(jù)元素方法有C和D兩種方法，其中C是一個(gè)只適合于次序存放結(jié)構(gòu)但E方法；而D是一個(gè)對(duì)次序和鏈?zhǔn)酱娣沤Y(jié)構(gòu)均適用方法。A：①次序存放線性表②非次序存放非線性表 ③次序存放非線性表 ④非次序存放線性表B： ①不需要移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針②不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 ③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 ④既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C：①次序查找②循環(huán)查找 ③條件查找④二分法查找D：①次序查找②隨機(jī)查找 ③二分法查找④分塊查找E：①效率較低線性查找②效率較低非線性查找 ③效率較高非線性查找④效率較高線性查找答案：A＝④B＝②C＝④

D＝①E＝③

150/176三、簡答題1.對(duì)分（折半）查找適不適合鏈表結(jié)構(gòu)序列，為何？用二分查找查找速度必定比線性查找速度快，這種說法對(duì)嗎？151/1761對(duì)分（折半）查找適不適合鏈表結(jié)構(gòu)序列，為何？用二分查找查找速度必定比線性查找速度快，這種說法對(duì)嗎？答：不適合！即使有序單鏈表結(jié)點(diǎn)是按從小到大（或從大到?。┐涡蚺帕校蚱浯娣沤Y(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開始逐步搜索，故不能進(jìn)行折半查找。二分查找速度在普通情況下是快些，但在特殊情況下未必快。比如所查數(shù)據(jù)位于首位時(shí)，則線性查找快；而二分查找則慢得多。152/1764.使用折半查找兩個(gè)前提條件是什么？（1）采取次序存放結(jié)構(gòu)；（2）按關(guān)鍵字大小有序排列。153/1764.使用折半查找兩個(gè)前提條件是什么？154/1764.設(shè)哈希（Hash）表地址范圍為0～17，哈希函數(shù)為：H（K）＝KMOD16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，試回答以下問題：畫出哈希表示意圖；若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？假定每個(gè)關(guān)鍵字查找概率相等，求查找成功時(shí)平均查找長度。

155/176解：（1）畫表以下：156/176（2）查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次?。?）查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)該有空標(biāo)識(shí)），所以應(yīng)該只比較這一次即可。（4）對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55157/1764.選取散列函數(shù)H（key）=（3*key）%11，用線性探測(cè)法處理沖突，對(duì)以下關(guān)鍵碼序列結(jié)構(gòu)一個(gè)散列地址空間為0～10，表長為11散列表，{22，41，53，08，46，30，01，31，66}。158/176解：由題意知，m=11(剛好為素?cái)?shù))則(22*3)%11=6……0(41*3)%11=11……2(53*3)%11=14……5(08*3)%11=2……2(46*3)%11=12……6(30*3)%11=8……2(01*3)%11=0……3(31*3)%11=8……5(66*3)%11=9……0159/176第9章160/176一、填空題1.大多數(shù)排序算法都有兩個(gè)基本操作：

和

。161/1761.大多數(shù)排序算