專升本數(shù)據(jù)結(jié)構(gòu)考前必看

1、1名詞解釋：棧和隊列棧是只允許在一端進行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除 故棧也稱后進先出(LIFO)表。隊列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊尾，允許劇除的一端叫隊頭0最先插入隊的元素最丸離 開(刪除，故隊列也常稱先進先出(FIFO)表。2假設(shè)以S和X分別表示入棧和出棧操作則對初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示(如SXSX) O(1) 試指出判別給定序列是否合法的一股規(guī)則。(2) 兩個不同合法序列(對同一輸入序列)能否得到相同的輸出元素序列？如能得到，請舉列說明。【答案】(1)通常有兩條規(guī)則。第一是

2、給定序列中S的個數(shù)和X的個數(shù)相等：第一是從給定序列的開始.到給定序列中的任一 位宜S的個數(shù)要大于或等rX的個數(shù)。C2)可以得到相同的輸出元素序列。例如輸入元素為A. B, C.則兩個輸入的合法 序列ABC和BAC均可得到輸出元素序列ABC.對于合法序列ABC.我們使川木題約定的SXSXSX操作序列：對于合法序列BA C,我們使用SSXXSX操作序列。3如果輸入序列為123456,試問能否通過棧結(jié)構(gòu)斜到以下兩個樣列：435612和135426.請說明為什么不能或如何才能得到?！敬鸢浮枯斎胄蛄袨?23456.不能斜出435612.其理由是，輸出序列最后兩元素是12.前面4個元素(4356)御到后棧

3、中元 素剩12.且2在棧頂.不可能棧底元素1在棧頂元素2之前出棧。得到135426的過程如下：1入棧并出棧.毎到部分輸岀序列1： 然后2和3入棧 3出棧，部分輸出序列變?yōu)?13：接著4和5入棧.5. 4和2依次岀棧.部分輸出序列變?yōu)?3542：最后6入棧并退 棧得最終結(jié)果135426。4. 簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件?！敬鸢浮吭O(shè)順序存儲隊列用一維數(shù)組qm表示，«中10為隊列中元素個數(shù)隊列中元素在向g中的下標從0到設(shè)隊頭指 針為front.隊尾指針是rear.約定front指向隊頭元素的前一位Srear 向隊尾元素o front等于-1時隊空，"ar

4、等 于m-1時為隊滿。由于隊列的性質(zhì)("刪除R在隊頭而“插入”在隊尾)，所以艸隊尾指針rear等于m-1時.若front不等 于-1則隊列中仍有空閑笊元.所以隊列并不是真滿。這時若再有入隊操作.會造成假“溢出".其解決辦法有一，一是將隊 列元素向前"平移”(占用0至rear-front-1 > :二是將隊列看成首尾相連即循環(huán)隊列(0丁1) 在循環(huán)隊列下.仍定 義front=rear時為隊空.而判斷隊滿則用兩種辦法，一是用“犧牲一個元"即rearl=front (準確記是(rearl) %m=front. m是隊列容S)時為隊滿。另一種解法是“設(shè)標記

5、”方法，如設(shè)標記tag. tag等于0情況下，若刪除 時尋致front=rear為隊空：tag=l情況下，若1*1插入導(dǎo)致front=rear則為隊滿 5若以I. 2、3、4作為雙端隊列的輸入序列，試分別求出以下條件的輸出序列：(1) 能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列：(2) 能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列：(3) 既不能由輸入受限雙端隊列得到.也不能由輸出受限雙端隊列得到的輸出序列?！敬鸢浮?I) 4132(2) 4213(3) 42311描述以下槪念的區(qū)別：空格串與空串?！敬鸢浮靠崭袷且粋€字符，其ASCII碼值是32

6、?？崭翊怯煽崭窠M成的弗.其長度等于空格的個數(shù)?？沾遣缓魏巫址拇?即空串的長度是零.2. 設(shè)SI, S2為串.請給出使S1/*S2=S2/*S1成立的所有可能的條件(嚴為連接符)°si利s2均為空串：兩串之一為空串：兩串串值相等(即兩串長度相等且對應(yīng)位置上的字符相同)°兩串中一個弗長是另一個串長(包括串長為I僅有一個字符的情況)的數(shù)倍.而且長串就好欽是由數(shù)個短串經(jīng)過連接操作【答案】(1)(2)(3)(3) 得到的。54應(yīng)用題1設(shè)有一個一維數(shù)勿訕川.假設(shè)AOlO存放位S在644.川2|存放位置在676.每個元素占一個空間問同33)存放在什 么位置？答案i設(shè)數(shù)組元素Aij

7、存放在起始地址為Loc ( ij )的存儲飛元中。V Loc ( 2-2 > =Loc ( 0.0 ) + 2 * n+ 2 = 644 +2 n + 2 = 676,A 11= ( 676-2 644/2=15A Loc (33) =Loc ( 0.0 ) +3 * 15 + 3 = 644 + 45 + 3 = 692.2.設(shè)有一個山初的對稱矩陣兒 為r節(jié)約存儲，可以只對角線及對角線以上的元素或者只存對角線或?qū)蔷€以下的元素。 前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行/<放于一個一維數(shù)組8中稱之為對稱矩陣A的壓縮存儲方式。 試問：(1) 存放對稱矩陣A上三角部分或

8、下三角部分的一維數(shù)組B冇多少元素？(2)若在一維數(shù)組B中從0號位a開始存放，則對稱矩陣中的任一元素絢在只存下三角部分的情形下應(yīng)存于一維數(shù)組的什么下標位置 ?給出計算公式?！敬鸢浮?1) 數(shù)組B共有1+2 + 3+ n= < 11+1 ) *n/2個元素。j-則數(shù)組元素Ai|jl前面有i-ltf (iM-(2) 只存下三角部分時，若i>1-第0行第0列不算)，第I行有I個元素.第2行有2個元素.第H行有b 1個元素。在第i行中，第j號元素排在第j個元素位置因此數(shù)組元素Aij在數(shù)組B中的存放位置為：1+2 + + (M) +j= < i-1) *i/2+j若ivj.數(shù)組元素A訓(xùn)j

9、在數(shù)組B中沒有存放可以找它的對稱元素AUllih在數(shù)組B的笫<j-l) *j/2 + i位g中找到。 如果第0行第0列也il入數(shù)組B從0號位置開始存放則數(shù)組元素AiM在數(shù)組B中的存放位置可以改為：當(dāng)i>j時，=1* <i+l） /2+j出ivj時，=j* （j+l） /2 + i3. 利用廣義表的head和lail操作寫出函數(shù)表達式把以下各題中的飛元素banana從廣義表中分離出來: LI （apple, pear, banana, orange）L2 （L3 （U （(1)(2)(3)(4)(5)<appie, pear) . (banana, orange)(app

10、le) , (pear) , (baiianA) , (orange)< C <apple) ) ) , ( (pear) ) . <bananA) ,orange)< C (apple) .pcar) ,bananA) .orange)【答案】(1)(2)(4)(5)Head Head Head Head Head(Tail (Tail (LI) > > (Head (Tail (Head (Tail (Head (Tail(Tail (Head(L2)(Tail (Hzd tL3)(Tail (U) > ><L5)L5 （淼林和一叉樹是

11、三種不同的數(shù)據(jù)結(jié)構(gòu).將樹.森林轉(zhuǎn)化為二叉樹的基木目的是什么并指出樹和一叉樹L從概念上講.樹.的主耍區(qū)別.【答案】樹的孩子兄弟鏈表表示法和一叉樹二叉鏈表表示法.木質(zhì)是一樣的，只是解釋不同.也就是說樹（樹是森林的特例 即淼林中只有一樑樹的特殊情況）可用二叉樹惟一表示.并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和一叉樹的區(qū)別有兔一是一叉樹的度至多為2樹無此限制：一是一叉樹冇左右子樹之分即使在只有一個分支的情況下， 也必須抬出是左子樹還是右予樹樹無此限制：三是二叉樹允許為空樹一般不允許為空（個別書上允許為空。2.若在內(nèi)存中冷放一個完全二叉樹.在一叉樹上只進行下浙兩個操作：（1）尋找某個結(jié)點雙親

12、:（2）尋找某個結(jié)點的子女：請問應(yīng)該用何種結(jié)構(gòu)來存儲該二叉樹？【答案】用順序存儲結(jié)構(gòu)存儲n個結(jié)點的完全一叉樹。編號為i的結(jié)點，其雙親編號Li/2j（i=l時無雙親），其左子女是2i若2iSn 否則i無左子女）右子女是2i+H若2i+l9否則無右子女h3求含有n個結(jié)點、采用順序存儲結(jié)構(gòu)的完全一叉樹中的序號最小的葉子結(jié)點的下標C要求弓出簡要步驟?！敬鸢浮扛鶕?jù)完全一叉樹的性質(zhì)最后一個結(jié)點（編號為n）的雙親結(jié)點的編號是Lii/2這是最后一個分支結(jié)點，在它之后是 第一個終端（葉子結(jié)點，故序號最小的葉子結(jié)點的下標是Ln/2_ku4試證明同一棵一叉厠的所有葉子結(jié)點.在先序序列、中序序列以及后序序列中都按相同

13、的相對位置出現(xiàn)（即先后順序相 同）例如先序a匹，后序妙，中序paj【答案】先序遍歷是“根左右”，中序遍歷是“左根右”后序遍歷是“左右根"-三種遍歷中只是訪問“根”結(jié)點的時機不 同，對左右子樹均是按左右順序來遍歷的 W此所有葉子都按相同的相對位g出現(xiàn)。5. 試找出滿足下列條件的一叉樹：1）先序序列與后序序列相同：2）中序序列與后序序列相同：3）先序序列與中序序列相同：4） 序序列與層次序列相同：【答案】先序遍歷一叉樹的順序是“根一左子樹一右子樹”，中序遍歷“左予樹一根一右子樹"，后遍歷順序是：火左子樹 一右子樹一HT 根據(jù)以上原則解答如下：1）若先序序列與后序序列相同則或為空

14、樹.或為只有根結(jié)點的一叉樹。2）若中序序列與后序序列相同則或為空樹或為任一結(jié)點至多只有左子樹的一叉樹。（3）著先序序列與中序序列相同.則或為空樹.或為任一結(jié)點至多只有右子樹的一叉樹。（4）若中序序列與層次遍歷序列相同.則或為空樹.或為任一結(jié)點至多只有右子樹的一叉樹6. 已知一棵二叉樹的中序序列和后序序列分別為GLDHBEIACJFK和LGHDIEBJKFCA<2）轉(zhuǎn)換為對應(yīng)的淼林。（2）題圖（I）給出這探一叉樹：7.-棵非空一叉樹其先序序列和后序序列正好相反.甌出一叉樹的形狀?！敬鸢浮肯刃蛐蛄惺歉笥?quot;后樣序列是"左右根".可見對任意結(jié)點若至多只有左子女或至

15、多只有右子女，均可使丸序序列與后序序列相反.圖示如下: 8假設(shè)一棵一叉樹的層次次序（按層次遞増順序排列，同一層次自左向右）為ABECFGDHI沖序序列為BCDAFEHIG.請畫 岀該一叉樹，并將轉(zhuǎn)換為對應(yīng)的淼林?！敬鸢浮堪磳哟伪闅v，第一個結(jié)點（若樹不空為根，該結(jié)點在中序序列中把序列分成左右兩部分：左子樹和右予樹e若左子 樹不空，整次序列中第一個結(jié)點為左子樹的根：若右子樹為空，則層次序列中第三個結(jié)點為右子樹的根.對右子樹也作類似的 分析。層次序列的特點是，從左到右每個結(jié)點或是、”1前情況下子樹的根或是葉子。EFDB JIH A9已知一個淼林的丸序序列和后序序列如下，請構(gòu)造出該淼林。先序序列：AB

16、CDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK【答案】森林的先序序列和后序序列對應(yīng)其轉(zhuǎn)換的一叉樹的先序序列和中序序列應(yīng)丸據(jù)此構(gòu)造一叉樹，再構(gòu)造出森林10. 一樑1叉樹的先序.中序、后序序列如下.其中一部分未標出，請構(gòu)造出該二叉樹。 先序序列J -CDE.GHI.K 中序序列：CB_FA_JKIG 后序序列:-II.設(shè)有正文AADBAACACCDACACAAD.字符集為八B. C. D,設(shè)il一套二進制編碼使得上述正文的編碼最短。 【答案】字符A. B. C. D出現(xiàn)的次數(shù)為9. I. 5, 3. U哈夫曼編碼如下：A:l B:000, C:OI D;00hAOE網(wǎng)的性質(zhì)(1

17、)只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各有向邊所代表的活動才能開始。(2)只有在進入某點的各有向邊所代表的活動都已結(jié)束，該頂點所代表的時事件才能發(fā)生。整個工程只有一個開始點.一個結(jié)束點。AOV網(wǎng)用頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)，簡稱AOV網(wǎng)。在網(wǎng)中，若從頂點i到頂點j有一條有向路徑，貝ili是j的前驅(qū)AOV網(wǎng)是一種有向無環(huán)圖 強連通圖是指一個有向圖中任意兩點V1、v2間存在V1到v2的路徑及v2到V1的路徑的圖。1. 設(shè)有一有向圖為G=(V E)。其中 V(vl v2 v3 v4 v5, E=<v2- vl>. <v3. v2&g

18、t;- <v4, v3x <v4- v2>. <vL v4x <v4, v5>- <v5_vl>,請畫出該有向圖并判斷是否是強連通圖。分析：作該題的關(guān)鍵是弄清楚以下兩點(1) 邊集E中<vivj>表示一條以Vi為弧尾 vj為弧頭的有向弧。(2) 強連通圖是任總兩頂點間都在路徑的有向圖。2.価出I個頂點、2個頂點、3個頂點.4個頂點和5個頂點的無向完全圖。 1)/2.【答案】0并說明在n個頂點的無向完全圖中邊的條數(shù)為n(n1個頂點的 無向兗全團2個頂點的 無向芫全國A國 3個頂點的 無向完全圖4個頂點的 無向完全圖5個頂點的 無向壬全S

19、【解析】W為在有n個頂點的無向完全圖中.每一個頂點與其它任一頂點都有一條邊相連.所以每一個頂點有n1條邊與其他頂點相連，則 n個頂點有mn-1)條邊。但在無向圖中頂點i到頂點j與頂點j到頂點i魁同一條邊所以總共有n(n 1)/2條邊。3對n個頂點的無向圖G.采用鄰接矩陣表示，如何判別下列有關(guān)問題：(1) 圖中有多少條邊？(2) 任意兩個頂點ilnj是否有邊相連？(3) 任意一個頂點的度是鄉(xiāng)少？【答案】(1) 無向圖的鄰接矩陣是對稱的.故它的邊數(shù)應(yīng)是上三角或下三角的非0元個數(shù)。(2) 鄰接矩陣中如果第i行第j列的元素非0則表示頂點i與頂點j相連。(3) 任慮一個頂點Vi的度是第i行或第i列上非0

20、元的個數(shù)。4熟悉圖的存儲結(jié)構(gòu)，畫出下浙有向圖的鄰接矩陣、鄰接表、逆鄰接表、十字鏈表。寫出鄰接表表示的圖從頂點A出發(fā)的深段優(yōu)先列和廣反優(yōu)先遍歷序列?！敬鸢浮苦徑泳仃嚾缦?鄰接表如下:AABCDE¥02345T|a 0 I A2 人深度優(yōu)先遍歷序列為ABCFED,廣度優(yōu)先遍歷序列為ABDCEF5.已知下面是某無向圖的鄰接表.迪出該無向圖.并分別給出從A出發(fā)的深度優(yōu)丸搜索生成樹和廣度優(yōu)先捜索生成樹。【解析】作該題的關(guān)鍵是弄清楚鄰接表的概念理解深度優(yōu)先搜索和廣度優(yōu)先捜索的全過程以及二者的區(qū)別。 【答案】該無向圖如下所示：深度優(yōu)丸搜索生成樹為:廣度優(yōu)先搜索生成樹為:6.請分別用Prim算法和K

21、ruskal算法構(gòu)造以下網(wǎng)絡(luò)的最小生成樹并求出該樹的代價。第一步第二步第三步242第五步首先將n個頂點看成n個互不連通的分S， 所有頂點都在同一連通分fi上?！敬鸢浮课觥縆ruscal算法的操作步驟：從邊集中找鍛小代價的邊，如果落在不同連通分a上，則將其加入最小生成樹直到析】Prim算法的操作步驟：首先從一個只有一個頂點的集合開始通過加入與其中頂點相關(guān)聯(lián)的最小代價的邊*擴充頂點集，直到 所有頂點都在一個集合中。7.寫出求以下AOE網(wǎng)的關(guān)鍵路徑的過程。給出每一個爭件和每一個活動的最早開始時間和最晚開始時間。要求:【解析】求關(guān)鍵路徑首先求關(guān)鍵活動，關(guān)鍵活動ai的求解過程如下(1)(2)(4) 【答

22、案】求爭件的嚴早發(fā)生時間ve(j)最晚發(fā)生時間vl(j);最早發(fā)生時間從00開始按拓撲排序向前遞推到ve(6)最晚發(fā)生時間從vl(6)按逆拓撲排序向后遞推到vl(O: 計算e(i),l(i)：設(shè)at由弧vjk>表示.持續(xù)時間記為diKvjJo,則有下式成立c(i)=vc(j)I(i)=vl(k)-du«<j-k>)找出e(i)-l(i)=O的活動既是關(guān)惟活動。ve V1 I活動 eEl【答案】(3)OQ1&3M5678910002247749o4l9257 0 5ggi o041701031關(guān)鍵路徑為：a0->a4->a6->a98. 拓撲

23、排序的結(jié)果不是唯-的，試寫出下圖任總2個不同的拓撲序列?！窘馕觥拷忸}關(guān)鍵是弄清拓撲推序的步驟（1）在A0V網(wǎng)中，選一個沒有前驅(qū)的結(jié)點且輸岀：（2）刪除該頂點和以它為尾的?。海?）重復(fù)上述步驟直至全部頂點均輸 出或不再有無前驅(qū)的頂點?！敬鸢浮浚?） 0132465（2） 01234659. 給定帯權(quán)有向圖G和源點VI利用迪杰斯特拉（Dij恣（ra）算法求從vl到其余各頂點的最短路徑。【解析】求解該題的關(guān)鍵是掌握迪杰斯特拉（Dijksira）算法的設(shè)il原理從一個頂點V到另一頂點W的最短路徑或者是WVk）或者是（VM，v山它的長度或者是從V到Vk弧上的權(quán)值，或者是Djl與與到Vk弧上 的權(quán)值之和，

24、其中Dj|是已經(jīng)找到的從V到VJ的最短路徑?！敬鸢浮縎是已找到最短路徑的終點的集合。終點從vl到各終點的D值和最短路徑的求解i=2i3i=4i=5i=6v25(vl,v2)5 (vlv2)v34(vl,v5>v43276732767327679(vl,v2,v5-v4»v532767327676 (vlv2v5)v6327673276712 (vl,v2-v6)9(vLv2-v5,v6)9 (vLv2,v5a6)V)v3v2v5v4v6SvLvSJ(vLv2)(vl,v2-v5vLv2,v5.v4)vI.v2v5n610. 利用冋0対算法求下圖巾?對頂點之間的路徑。析】Floy

25、d算法是依次添加頂點來修改相應(yīng)路徑，也就是說若（Yivk） fli（vkvj）分別是從Vi到vk和從vk到vj的中間頂點的序號不大于kJ的最短路徑，則將（vi 、kvj）和已經(jīng)斜到的從Vi到vj且中間頂點序號不大于匕1的最短路徑相比較，其長度較短者便是從Vi到vj的中間頂點的序號不大于k的最短路徑。經(jīng)過II次比較后必求得Vi到vj的最短 路徑依次，可求得對頂點間的最短路徑。求解的關(guān)鍵是求解如下的一個n階方陣序列：D 嘰 D.DUD"“氏中D 叩arcsiilljlDk匕MinDE>ijh叫iHk|+Dk小k|jl) 0<k<n-l【答案】DD“D®D2)1

26、4I803803X03120399800ppM>p（o）pillp l2>20ACABACABACACBACACBICBCBCBCBACB2BABABACBABACBABAC每對頂點2間的最短路徑及長度總結(jié)如下: 頂點A到頂點C報短路徑為： 頂點A到頂點B報短路徑為： 頂點C到頂點A報短路徑為： 頂點C到頂點B最短路徑為： 頂點B到頂點A報短路徑為： 頂點B到頂點C報短路徑為：A->C.長度為：1 A->C->B.長度為: C>B>A,長度為:C>B長度為：3 B>A長度為：9B->A->C,長度為:412101.順序査找時間為

27、O（n二分法資找時間為O（log2n）,散列法為0（1）,為什么有商效率的査找方法而低效率的方法不被放棄？ 【答案】不同的査找方法適用的范隔不同.為效率的査找方法并不是在所有情況下都比其他査找方法效率要商，而且也不是在所有情況下都可以采用。2. 對含有n個互不相同元素的集合，同時找最大元和最小元至少需進行多少次比較？【答案】nl次【解析】設(shè)變ftinaxflimin用于存放最大元利報小元（的位g）,第一次取兩個元素進行比較.大的放入max,小的放入mim從 第2次開始.每次取一個元素先和max比較如果大于max則以它替換max并結(jié)束木次比較：若小于max則再與min相比較.在 最好的情況下.比

28、較下去都不用和min相比較.所以這種情況下.至少要進行nl次比較就能找到最大元和最小元。3. 若對具有n個元素的有序的順序表和無序的順序表分別進行順序査找，試在下述兩種情況下分別討論兩看在等槪率時的平均 査找長度：（1）査找不成功，即表中無關(guān)鍵字等于給定值K的記錄：（2）賁找成功.即表中有關(guān)惟字等干給定值K的記錄?！敬鸢浮浚?）不成功時需要n+l次比較（2）成功時平均為5+1X2次【解析】有序表和無序表順序査找時都需要進行n+l次比較才能確定査找失敗。W此平均査找長度都為（1+1。査找成功時. 平均査找長度都為（n+1 ）/2.有序表和無序表也是一樣的。因為順序査找與表的初始序列狀態(tài)無關(guān)。4.

29、 設(shè)有序表為（abcdefghijkpqh請分別畫出對給定值a. g和n進行折半査找的過程?！敬鸢浮浚?）査找a的過程如下（圓括號表示為前比較的關(guān)鍵字），經(jīng)過三次比校.査找成功。下標12345678910111213區(qū)間第一次比較abcdef（8）hijkPqaq第二次比較ab(c)defghijkpq第三次比較(a)bcdeffihijkpqabl（2）g的査找過程如下，一次比較成功|a b C d e f g） h i j k p q |（3）n的査找過程如下，經(jīng)過四次比校，査找失敗。下標12345678910111213區(qū)間第一次比較abcdef(g)hijkPqaql第二次比較abcd

30、efghi(j)kPq|hq】第三次比較abcdefghiIk(p)qkq第四次比較abcdefghiI(k)pqk|5. 為什么右伴的収鏈表不能進行折*逬找？【答案】W為鏈表無法進行隨機訪問.如果要訪問鏈表的中間結(jié)點就必須丸從頭結(jié)點開始進行依次訪問.這就要浪費很多時 間，還不如進行順序査找，而且.用鏈/儲結(jié)構(gòu)將無法判定一分的過程是否結(jié)束，W此無法用鏈表實現(xiàn)二分查找.6 構(gòu)適有12個元素的一分資找的判定樹并求解下列問題：(1) «元素的査找長度厳大是多少？(2) 査找長度為I. 2、3、4的元素?有多少？具休是哪些元素？(3) 査找第5個元素依次要比較哪些元素？【答案】12個元素的判

31、斷樹如下圖所示：(1)(2)1、 4. 7、(3)最大査找長度是樹的深度4。 査找長度為I的元素有I個.為第6個，H個.査找長度為4的元素有5個.為第2、5、8. 10、12個' 査找第五個元素依次比較6. 3. 4. 5。査找長度為2的元素有2個，為第3個和第9個.査找長度為3的元素有4個.為第7.以數(shù)據(jù)集合(123456)的不同序列為輸入. 【答案】構(gòu)造4樑商度為4的二叉排序樹。圖I8直接在一叉排序樹中査找關(guān)鍵碼K與從中序遍歷輸出的有序序列中用二分査找法査找關(guān)鍵碼K.其數(shù)據(jù)比校次數(shù)是否相 同？【答案】不相同?！窘馕觥縒為二分査找得到的判定樹和一叉排序«的形狀不一定相同iu

32、ii出新一叉樹09.已知一棵一叉排序樹如下：（1）假如刪除關(guān)鍵字28（2）若點找56.需和哪些關(guān)惟字比較?？捎媒Y(jié)點28左子樹上最大的結(jié)點代替它如圖需和38、49、55、56進行4次比較。17【答案】（I）也可用其右子樹上報小的（I）刪除元素28后.需修改二叉排序樹的形態(tài). 結(jié)點代替它，如圖（2） °（2）若要査找56.10. 設(shè)散列函數(shù)為h（key）=kcy%lOb解決沖突的方法為線性探測，表中用“1”表示空元。202304507707k表HT屮直找707將會發(fā)生什么？100（1） >（2）若將刪去的表項標記為”2”査找時探測到“2”繼續(xù)向前捜索.探測到”1“時終止捜索。請問用

33、這種方法刪去304后能否正確地童找到707?【答案】（1）査找707時，首先根據(jù)散列函數(shù)訃算得出該元素應(yīng)在散列表中的0爪元.但超在0取元沒有找到，W此將向下一笊元探 測，結(jié)果發(fā)現(xiàn)該敢元是"（為空爪元），所以結(jié)束査找.這將尋致707無法找到。（2）如果改用”2“作為刪除標記.則可以正確找到707所在的結(jié)點。11已知散列表的地址區(qū)間為0II.散列函數(shù)為H（k）=k%II. 采用線性探測法處理沖夬將關(guān)鍵字序列20307015812186319依次存儲到散列表中，試構(gòu)逍出該散列表，并求出在等 概率情況下的平均査找長度。【答案】構(gòu)適散列表如下（每個元素的査找長度標注在該元素的下方。012345

34、6789101119127015 1183020863 1511211130搜索次數(shù)等概率情況下成功時的平均査找長度為（IX5+2 + 3+4+5） /9=19/912. 設(shè)散列函數(shù)為H（k）kII, 采用拉鏈法處理沖突將上例中關(guān)鍵字序列依次存儲到散列表中，并求出在等槪率情況下的平均査找長度。 【答案】-lUH23454 701-115 a|在等槪率情況下成功的平均査找長度為:（1*5+2*2+3*1+4*1）/9=16/913. 假定一個待散列存儲的線性表為（3275.296348942546&70）,散列地址空間為HT|I3.若采用除留余數(shù)法構(gòu)造散列 函數(shù)和線性探測法處理沖突試求出

35、每一元素的初始散列地址和最終散列地址畫岀用后御到的散列表，求出平均査找長度。【答案】構(gòu)適的散列表如下:03456789101112|2994183246 |70 Us 1 756325序號12315678910元素值32752963489125461870初始地址61最終地址61在等概率情況下成功的平均査找長度為（1*7+2*5+3*1+4*0/14=24/1414. 散列表的地址區(qū)間為015.敬列函數(shù)為H（key）=key%13.設(shè)有一組關(guān)鍵字U9.OI.23.I4.55.20.84. 采用線性探測法解決沖突依次存放在散列表中。問：（1）元素84存放在散列表中的地址是多少？（2）捜索元素84

36、需要的比較次數(shù)是多少？【答案】構(gòu)造的散列表如下：012345678 910 11121314151145519208423（1）元素84存放在散列表中的地址是8。（2）捜索元素84需要的比較3次。94應(yīng)用題1什么是內(nèi)排序？什么是外排序？什么排序方法是穩(wěn)定的？什么排序方法是不穩(wěn)定的？【答案】內(nèi)排序是排序過程中參與排序的數(shù)據(jù)全部在內(nèi)"中所做的排序，排序過程中無需進行內(nèi)外存數(shù)據(jù)傳送決定排序方法 時間性能的主要是數(shù)據(jù)排序碼的比較次數(shù)和數(shù)據(jù)對彖的移動次數(shù)。外排序是在排序的過程中參與排序的數(shù)據(jù)太多.在內(nèi)存中容納不下，因此在排序過程中需要不斷進行內(nèi)外存的信息傳送的排序假設(shè)在待排序的丈件中冷在兩個或

37、兩個以上的記錄具有相同的關(guān)鍵字.若采用某種排序方法后，使御這些具有相同關(guān)鍵字的記 錄在排序前后相對次序依熱保持不變則認為該推序方法是穩(wěn)宦的，否則就認為扌*序方法是不穩(wěn)定的。2冒泡排序算法是否穩(wěn)定？為什么？【答案】冒泡排序算法是穩(wěn)定的。W為依據(jù)該排序算法的基木思想，排序過程只比較相鄰兩個記錄的關(guān)鍵字，若交換記錄也只 在相鄰二個記錄之間進行，從而可知在交換過程中不會出現(xiàn)跨越多個記錄的情形。即使是相鄰兩個記錄關(guān)鍵字相同時，經(jīng)過比 較也不會產(chǎn)生相鄰記錄的交換。所以冒泡排序法不會改變相同關(guān)鍵字記錄的相對次序，故是穩(wěn)定的。3.在起泡排序過程中什么情況下排序碼會朝向與排序相反的方向移動，試舉例說明。在快速排序過程中有這種現(xiàn)彖嗎？【答案】如果在待排序序列的后面的若干排序碼比前面的排序碼小，則在起泡排序的過程中排序碼可能向與最終它應(yīng)移向的 位a相反的