數(shù)據(jù)結(jié)構(gòu)考試題

一、填空題：（1分*10=10分）1）線性結(jié)構(gòu)中元素之間存在1對(duì)1關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在二對(duì)多，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。2）順序表中，邏輯上相鄰的元素物理位置一定相鄰；單鏈表中邏輯上相鄰的元素位置不一定相鄰。3）線性表、棧和隊(duì)列都是線性結(jié)構(gòu)。對(duì)于棧只能在棧頂位置插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾位置插入和在對(duì)頭—位置刪除元素。4）由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有5―種不同的結(jié)構(gòu)。5）具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為10。6）評(píng)價(jià)算法的優(yōu)劣通常主要考慮算法的時(shí)間復(fù)雜度和空間復(fù)雜度這兩方面。7）鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是利用指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。8）線性表常見(jiàn)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。9）棧的特點(diǎn)是，隊(duì)列的特點(diǎn)是先進(jìn)先出。10）對(duì)于二叉樹(shù)來(lái)說(shuō)，第i層上最多有2i-i__個(gè)節(jié)點(diǎn)。11）哈夫曼樹(shù)是指J弋權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。12）構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有—條弧。13）常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)有集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)。14）計(jì)算機(jī)程序中加工處理的基本單位是數(shù)據(jù)元素，數(shù)據(jù)中不可再分割最小單位是數(shù)據(jù)項(xiàng)。15）鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是利用指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。16）棧的特點(diǎn)是，隊(duì)列的特點(diǎn)是先進(jìn)先出。17）一棵深度為k的滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)總數(shù)為2k-i。18）在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)2（n-1）。19）線性結(jié)構(gòu)中元素之間存在1對(duì)1關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在二對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。20）計(jì)算機(jī)程序中加工處理的基本單位是數(shù)據(jù)元素，數(shù)據(jù)中不可再分割最小單位是數(shù)據(jù)項(xiàng)。21）線性表常見(jiàn)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。22）棧的特點(diǎn)是，隊(duì)列的特點(diǎn)是先進(jìn)先出。23）在一顆二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0=n2+1。

24）n個(gè)頂點(diǎn)的連通圖至少要有n-1條邊。二、單選題：（2分*10=20分）1、數(shù)據(jù)結(jié)構(gòu)中圖形結(jié)構(gòu)中元素對(duì)應(yīng)關(guān)系為（C）1對(duì)1B.1對(duì)多C.多對(duì)多D.無(wú)關(guān)系2、數(shù)據(jù)處理的基本單位是（A）數(shù)據(jù)元素C.數(shù)據(jù)類(lèi)型3、用鏈表表示線性表的優(yōu)點(diǎn)是A.便于進(jìn)行插入和刪除操作數(shù)據(jù)項(xiàng)D.數(shù)據(jù)變量（A）便于隨機(jī)存取占用的存儲(chǔ)空間較順序表少D.元素的物理順序與與邏輯順序一致4數(shù)據(jù)元素C.數(shù)據(jù)類(lèi)型3、用鏈表表示線性表的優(yōu)點(diǎn)是A.便于進(jìn)行插入和刪除操作數(shù)據(jù)項(xiàng)D.數(shù)據(jù)變量（A）便于隨機(jī)存取占用的存儲(chǔ)空間較順序表少D.元素的物理順序與與邏輯順序一致前移動(dòng)（C）個(gè)元素。n-i+1B.n-i-1C.n-iD.i5、對(duì)具有n個(gè)結(jié)點(diǎn)的線性表進(jìn)行插入或刪除操作，所需的算法時(shí)間復(fù)雜度為（D）O（n2）B.O（nlog2n）C.O（log2n）D.O（n）6、對(duì)于棧操作數(shù)據(jù)的原則是（B）A.先進(jìn)先出B?后進(jìn)先出C?后進(jìn)后出D-不分順序7、已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（B）A.1B.2C.3D.48、一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（A）A.n-1B.nC.n+1D.nlogn；9、要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（B）條邊。A.n-lB.nC.n+lD.2n10、某二又樹(shù)的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則前序序列遍歷為（D）A.ACBEDB.DECABC.DEABCD.CEDBA11、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類(lèi)。A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)12、數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)中元素對(duì)應(yīng)關(guān)系為（A）A.1對(duì)1B.1對(duì)多C.多對(duì)多D.無(wú)關(guān)系13、數(shù)據(jù)處理的基本單位是（A）。A.數(shù)據(jù)元素B.數(shù)據(jù)項(xiàng)C.數(shù)據(jù)類(lèi)型D.數(shù)據(jù)變量14、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是:（B）。A.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;C.p->next=s;p->next=s->next;D.p->next=s->next;p->next=s;15、在一個(gè)長(zhǎng)度為n的順序表中，若要?jiǎng)h除第i(1W^n)個(gè)元素，則需向

前移動(dòng)（C）個(gè)元素。A.n-i+1B.n-i-1C.n-iD.i16、對(duì)具有n個(gè)結(jié)點(diǎn)的線性表進(jìn)行插入或刪除操作，所需的算法時(shí)間復(fù)雜度為（D）A.O（n2）B.O（nlog2n）C.O（log2n）D.O（n）17、棧和隊(duì)列的共同點(diǎn)是（C）。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)18、某二又樹(shù)的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則前序序列遍歷為（D）A.ACBEDB.DECABC.DEABCD.CEDBA19、一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（A）。A.n-1B.nC.n+1D.nlogn；20、用折半查找表的元素的速度比用順序法（D）A.必然快B.必然慢C.相等D.不能確定21、數(shù)據(jù)結(jié)構(gòu)中樹(shù)型結(jié)構(gòu)中元素對(duì)應(yīng)關(guān)系為（B）A.1對(duì)1B.1對(duì)多C.多對(duì)多D.無(wú)關(guān)系22、算法分析的兩個(gè)主要方面是（D）。A.正確性和簡(jiǎn)單性B.可讀性和文檔性C.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性D.時(shí)間復(fù)雜度和空間復(fù)雜度23、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是:（B）。A.p->next=s;s->next=p->next;B.C.p->next=s;p->next=s->next;D.2A.p->next=s;s->next=p->next;B.C.p->next=s;p->next=s->next;D.24、棧和隊(duì)列的共同點(diǎn)是（CA.都是先進(jìn)先出s->next=p->next;p->next=s;p->next=s->next;p->next=s;）。B.都是先進(jìn)后出D.沒(méi)有共同點(diǎn)C.只允許在端點(diǎn)處插入和刪除元素25、輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為（B）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop26、已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（B）。A.1B.2C.3D.427、在一棵二叉樹(shù)上第3層上的結(jié)點(diǎn)數(shù)最多為（B）。A.2B.4C.6D.88、設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（BA.n-1B.n（n-1）/2C.n（n+1）/229、用折半查找表的元素的速度比用順序法（D）C.相等是穩(wěn)定的。B.快速排序，D.歸并排序，）條邊。D.0A.必然快B.必然慢30、下列排序算法中，其中（DA.堆排序，冒泡排序C.直接選擇排序，歸并排序31、線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)（D）A、必須是連續(xù)的D.不能確定堆排序冒泡排序要求內(nèi)存中可用存儲(chǔ)單元的地址B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)不連續(xù)都可以32、判定一個(gè)循環(huán)隊(duì)列Q（最多元素為MAX）為滿(mǎn)隊(duì)列的條件是（C）A、Q->front==Q->rearB、Q->front!=Q->rearC、Q->front==（Q->rear+1）%MAXD、Q->front!=（Q->rear+1）%MAX33、在一個(gè)單鏈表中，已知結(jié)點(diǎn)P，若在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)，則執(zhí)行（A）A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、p->next=s;s->next=p->next;D、以上均不正確34、按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有幾種（C）A、3B、4C、5D、635、深度為5的二叉樹(shù)至多有多少個(gè)結(jié)點(diǎn)(B)A、16B、31C、32D、4836、圖的深度優(yōu)先搜索算法類(lèi)似于二叉樹(shù)的哪種遍歷(A)A、先序遍歷B、中序遍歷C、后序遍歷D、按層次遍歷37、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的幾倍（C）A、1/2B、1C、2D、438、到目前為止哪種排序是平均速度最大的一種排序方法（B）A、直接插入排序B、快速排序C、冒泡排序D、希爾排序39、首先訪問(wèn)該結(jié)點(diǎn)，然后訪問(wèn)結(jié)點(diǎn)的左子樹(shù)，最后訪問(wèn)結(jié)點(diǎn)的右子樹(shù)，這種遍歷方式稱(chēng)為（A）A、先序遍歷B、后序遍歷C、中序遍歷D、層次遍歷40、一組記錄的關(guān)鍵字為｛46,79,56,38,40，84｝，則利用冒泡排序的方TOC\o"1-5"\h\z法，經(jīng)第一趟排序后的結(jié)果為（B）A、38，40，46，56，79，84B、46，56，38，40，79，84C、40，38，46，56，79，84D、40，38，46，84，56，79三、判斷題：（1分*10=10分）1、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。（V）2、最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是rear==front（V）3、棧操作數(shù)據(jù)的原則是先進(jìn)先出。（X）4、在任意一棵二叉樹(shù)中，終端結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1。）5、一個(gè)棧的輸入序列是12345,則棧的輸出序列不可能是43512。（V）TOC\o"1-5"\h\z6、串是一個(gè)有窮字符序列。（V）7、在滿(mǎn)二叉樹(shù)中，存在度為1的結(jié)點(diǎn)。（X）8、根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹(shù)。（X）9、深度為K的二叉樹(shù)至多有2K-1個(gè)結(jié)點(diǎn)。（V）10、圖的拓?fù)渑判蚴俏ㄒ坏?。（X）11、一個(gè)算法可以有零個(gè)輸入或輸出。（X）12、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。（X）13、隊(duì)列操作數(shù)據(jù)的原則是先進(jìn)先出。（V）14、空串與空格串是一個(gè)概念。（X）15、一個(gè)棧的輸入序列是12345,則棧的輸出序列可以是43512。（X）16、在任意一棵二叉樹(shù)中，終端結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1（V）17、由樹(shù)轉(zhuǎn)化為二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。（V）18、一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有1個(gè)連通分量，最多有n個(gè)連通分量。（V）19、用折半查找表的元素的速度一定比用順序法快。（X）20、N個(gè)頂點(diǎn)的圖或網(wǎng)的最小生成樹(shù)有N-1條邊。（V）21、一個(gè)算法可以有零個(gè)輸入或輸出。（X）22、隊(duì)列操作數(shù)據(jù)的原則是先進(jìn)先出。（V）23、棧和隊(duì)列邏輯上都是線性表。（V）24、空串與空格串是一個(gè)概念。（X）25、用折半查找表的元素的速度一定比用順序法快。（X）26、由樹(shù)轉(zhuǎn)化為二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。（V）27、在滿(mǎn)二叉樹(shù)中，存在度為1的結(jié)點(diǎn)。（X）28、根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹(shù)。（X）29、一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為n-1條。（V）30、圖或網(wǎng)的生成樹(shù)是唯一的。（X）31、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。（V）32、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。（X）33、棧和隊(duì)列邏輯上都是線性表。（V）34、空串與空格串是一個(gè)概念。（X）35、一個(gè)棧的輸入序列是12345,則棧的輸出序列可以是43512。（X）36、串是一個(gè)有窮字符序列。（V）37、滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)。（V）38、希爾排序與直接插入排序都是穩(wěn)定的排序。（X）39、深度為K的二叉樹(shù)至多有2K-1個(gè)結(jié)點(diǎn)。（V）40、圖或網(wǎng)的生成樹(shù)是唯一的。（X）五、編程（10分）將下圖中的二叉樹(shù)先序、中序和后序遍歷，寫(xiě)出遍歷序列，并還原成森

林。解：還原后的森林為:林。解：還原后的森林為:先序：ABCEDFGHIJK中序：BECDAGHFJIK后序：EDCBHGJKIFA已知一個(gè)電文字符集中有6個(gè)字符｛A,B,C,D,E,F｝,它們使用的頻率為｛0.06,0.02,0.04,0.03,0.07,0.12｝,設(shè)計(jì)一個(gè)哈夫曼編碼。（提示：哈夫曼樹(shù)的每個(gè)分支左分支設(shè)為0,右分支設(shè)為1,要求同層中葉子結(jié)點(diǎn)權(quán)值從左到右，從小到大）。解：將頻率值乘以100得：｛6,2,4,3,7,12｝。設(shè)哈夫曼樹(shù)的左分支為0,右分支為1,則求得的哈夫曼樹(shù)如下圖：所以哈夫曼編碼為：字符頻率編碼A0.0600B0.021010C0.04100D0.031011E0.0701F0.1211

已知下圖G,（1）畫(huà)出G的鄰接矩陣；（2）分別以頂點(diǎn)①和②為開(kāi)始，寫(xiě)出G的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。解：（1）該圖的鄰接矩陣為:011110、0解：（1）該圖的鄰接矩陣為:011110、0100010010011101010001111000000100010001010（2）①開(kāi)始對(duì)該圖進(jìn)行深度優(yōu)先搜索的遍歷序列為：①②⑤③④⑦⑥開(kāi)始對(duì)該圖進(jìn)行廣度優(yōu)先搜索的遍歷序列為：①②③④⑤⑥⑦開(kāi)始對(duì)該圖進(jìn)行深度優(yōu)先搜索的遍歷序列為：②①③④⑦⑥⑤②開(kāi)始對(duì)該圖進(jìn)行廣度優(yōu)先搜索的遍歷序列為：②①⑤③④⑥⑦已知下圖為帶權(quán)圖，寫(xiě)出用普里姆算法求該圖的最小生成樹(shù)過(guò)程并畫(huà)出最小生成樹(shù)。解：最小生成樹(shù)的求解過(guò)程為:5.用迪杰斯特拉算法,求下圖中從頂點(diǎn)0到其它各頂點(diǎn)的最短路徑。5.用迪杰斯特拉算法,始點(diǎn)終點(diǎn)八、、最短路徑路徑長(zhǎng)度01(0,2,1)702(0,2)103(0,4,3)504(0,4)30(0,4,3,5)6.已知一組記錄為｛46,74,53,進(jìn)行排序時(shí)的每一趟排序結(jié)果。解：TOC\o"1-5"\h\z初始狀態(tài)：4674第一趟排序結(jié)果：4653第二趟排序結(jié)果：4614第三趟排序結(jié)果：1426第四趟排序結(jié)果：1426第五趟排序結(jié)果：1426第六趟排序結(jié)果：14（2614,26,38,65｝,給出采用冒泡排序法531426386514263865(74)263853(6574)3846(536574)38(46536574)(3846536574)3846536574)將下圖中的森林轉(zhuǎn)換成一棵二叉樹(shù)，并對(duì)這棵二叉樹(shù)進(jìn)行先序、中序和后序遍歷，寫(xiě)出其遍歷序列。中序：BECDAGHFJIK后序：中序：BECDAGHFJIK后序：EDCBHGJKIFA已知一個(gè)電文字符集中有8個(gè)字符｛A,B,C,D,E,F,G,H｝,它們使用的頻率為｛0.04,0.21,0.06,0.07,0.15,0.18,0.12,0.03｝,設(shè)計(jì)一個(gè)哈夫曼編碼。（提示：哈夫曼樹(shù)的每個(gè)分支左分支設(shè)為0,右分支設(shè)為1,要求同層中葉子結(jié)點(diǎn)權(quán)值從左到右，從小到大）。解：將頻率值乘以100得：｛4,21,6,7,15,18,12,3｝。設(shè)哈夫曼樹(shù)的左分支為0,右分支為1,則求得的哈夫曼樹(shù)如下圖：

所以哈夫曼編碼為:字符頻率編碼A0.040101B0.2110C0.061100D0.071101E0.15111F0.1800G0.12011H0.030100用迪杰斯特拉算法，求下圖中從頂點(diǎn)0到其它各頂點(diǎn)的最短路徑。解：始點(diǎn)終點(diǎn)八、、最短路徑路徑長(zhǎng)度(0,2,1)2(0,2)93(0,4,3)354(0,4)205(0,4,3,5)4710.已知序列{35,24,16,78,22,15,29,70,54,31,20,90,77,24},畫(huà)出用這個(gè)序列生成的二叉排序樹(shù)。在原圖中如果刪除15,有幾種情況，將刪除后二叉排序樹(shù)畫(huà)出。在原圖中如果刪除22,有幾種情況，將刪除后二叉排序樹(shù)畫(huà)出。在原圖中如果刪除78,有幾種情況，將刪除后二叉排序樹(shù)畫(huà)出。

解：（1）生成的二叉排序樹(shù)為:（2）在原況，直接將15中如果刪除15,因?yàn)?5為葉子結(jié)點(diǎn)，刪除只有一種情寸除即可。刪除后的二叉排序樹(shù)如下圖：（3）在原圖中如果刪除22,因?yàn)?2只有一個(gè)左子樹(shù)，刪除只有一種情況，用它的左子樹(shù)根結(jié)點(diǎn)20替換22即可。刪除后的二叉排序樹(shù)如下圖：中如果刪除15,因?yàn)?5為葉子結(jié)點(diǎn)，刪除只有一種情寸除即可。刪除后的二叉排序樹(shù)如下圖：（4）在原圖中如果刪除78,因?yàn)?8有兩個(gè)子樹(shù)，刪除有兩種情況：第一種是用它左子樹(shù)中最大值77來(lái)替換它；第二種方法是用它右子樹(shù)中最小值90來(lái)替換它。刪除后的二叉排序樹(shù)如下圖：

11.假定對(duì)有序表｛3,4,5,7,24,30,42,54,63,72,87,95｝進(jìn)行折半查找，試回答下列問(wèn)題：畫(huà)出描述折半查找過(guò)程的判定樹(shù)；若查找元素54,需依次與那些元素比較？若查找元素90,需依次與那些元素比較？解：(1)二叉判定樹(shù)為：若查找元素54,則需要與30、63、42、54比較。若查找元素90,則需要與30、63、87、95比較。12.設(shè)有一組關(guān)鍵字{9,1,23,14,55,20,80,27},采用哈希函數(shù)：H(key)=key%7，表長(zhǎng)為10,用開(kāi)放地址法的二次探測(cè)再散列方法Hi=(H(key)+di)%10(di=12,22,32,???,)解決沖突。解：H(9)=9%7=2H(1)=1%7=1H(23)=23%7=2(沖突)產(chǎn)生沖突，H=(H(23)+d)%10=(2+1)%10=3H(14)=14%7=01H(55)=55%7=6H(20)=20%7=6(沖突)產(chǎn)生沖突，H=(H(20)+d)%10=(6+1)%10=7H(80)=80%7=3(沖突)1產(chǎn)生沖突，H=(H(80)+d)%10=(3+1)%10=4

H(27)=27%7=6(沖突)產(chǎn)生沖突，H=(H(27)+d)%10=(6+1)%10=7(仍沖突)仍有沖突，H1=(H(27)+d1)%14=(6-1)%10=5所以哈希表面下圖：201234567891419238027552013.將下圖中的二叉樹(shù)先序、中序和后序遍歷，寫(xiě)出遍歷序列，并還原成森林。解：還原后的森林為:先序：ABCEDFGHIJKLMN中序：BECDAGIJHFLMNK后序：EDCBJIHGNMLKFA解：還原后的森林為:先序：ABCEDFGHIJKLMN14.給定一組權(quán)值｛3,6,9，14,8,5,4，19,25｝，試設(shè)計(jì)相應(yīng)的哈夫曼樹(shù)，并求其帶權(quán)路徑長(zhǎng)度WPL。解：WPL=268哈夫曼樹(shù)如下：

15.已知下圖，畫(huà)出該圖的（1）鄰接矩陣和（2）分別以頂點(diǎn)①和③為起點(diǎn)進(jìn)行深度優(yōu)先遍歷。（3）分別以頂點(diǎn)④和⑤為起點(diǎn)進(jìn)行廣度優(yōu)先遍歷解：（1）該圖的鄰接矩陣為:解：（1）該圖的鄰接矩陣為:010011011001010011011001011011（2）①開(kāi)始對(duì)該圖進(jìn)行深度優(yōu)先搜索的遍歷序列為：①②③④⑤⑥③開(kāi)始對(duì)該圖進(jìn)行深度優(yōu)先搜索的遍歷序列為：③②①⑤④⑥（3）④開(kāi)始對(duì)該圖進(jìn)行廣度優(yōu)先搜索的遍歷序列為：④②③⑤⑥①⑤開(kāi)始對(duì)該圖進(jìn)行廣度優(yōu)先搜索的遍歷序列為：⑤①④⑥②③16.已知圖下圖，（1）寫(xiě)出該圖的鄰接矩陣；（2）寫(xiě)出全部拓?fù)渑判?

解：(1)該圖的鄰接矩陣為:023MMM/IMM0M5MMMMA=MM0310MMMMMM0M4MMMMMM0M3MMMMM10M6MMMMMM03MMMMMMM」0（2）拓?fù)渑判虻男蛄袨椋篤1,V2,V3,V4,V6,V5,V7,V8V1,V3,V2,V4,V6,V5,V7,V817.已知序列{32,45,16,7,28,40,30,19,7,56,43,78},畫(huà)出用這個(gè)序列生成的二叉排序樹(shù)。在原圖中如果刪除40,有幾種情況，將刪除后二叉排序樹(shù)畫(huà)出。在原圖中如果刪除45,有幾種情況，將刪除后二叉排序樹(shù)畫(huà)出。解：(1)二叉排序樹(shù)為：(2)刪除40時(shí)有一種情況，用其子樹(shù)根結(jié)點(diǎn)43代替，如下圖:

18.已知一組記錄為｛46,74,53，14,26,38,65｝，給出采用直接插入排序法進(jìn)行排序時(shí)的每一趟排序結(jié)果。解：r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]初始狀態(tài)：(46)745314263865第趟插入：74(4674)5314263865第二趟插入：53(465374)14263865第三趟插入：14(14465374)263865第四趟插入：26(1426465374)3865第五趟插入：38(142638465374)65第六趟插入：65(14263846536574),用其右子樹(shù)中的最小值56代替如下右圖。如下左圖。第二種，,,用其右子樹(shù)中的最小值56代替如下右圖。如下左圖。第二種，,19.將下圖中的森林轉(zhuǎn)換成一棵二叉樹(shù)并對(duì)這棵二叉樹(shù)進(jìn)行先序、中序和后序遍歷，寫(xiě)出遍歷序列。先序：ABCEDFGHIJKLMN中序：BECDAGIJHFLMNK后序：EDCBJIHGNMLKFA20.已知一個(gè)電文字符集中有8個(gè)字符，它們使用的頻率為｛0.04,0.26,0.06,0.09,,0.15,0.21,0.12,0.07｝,設(shè)計(jì)一個(gè)哈夫曼編碼。（提示：哈夫曼樹(shù)的每個(gè)分支左分支設(shè)為0,右分支設(shè)為1,要求同層中葉子結(jié)點(diǎn)權(quán)值從左到右，從小到大）。解：將頻率值乘以100得：｛4,26,6,9,15,21,12,7）設(shè)哈夫曼樹(shù)的左分支為0,右分支為1,則求得的哈夫曼樹(shù)如下圖：TOC\o"1-5"\h\z所以哈夫曼編碼為：字符頻率編碼A0.040100B0.2610C0.060101D0.091111E0.15110F0.2100G0.21011H0.07111021.畫(huà)出該圖