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

1、數(shù)據(jù)結(jié)構(gòu)試題及答案一、 單項(xiàng)選擇題緒論1. 計(jì)算機(jī)中的算法一般具有輸入、輸出和（ c ）五個(gè)基本性質(zhì)。a確定性、有窮性、穩(wěn)定性 b易讀性、確定性、可行 性c有窮性、確定性、可行性 d可行性、可移植性、可 擴(kuò)展性2. 數(shù)據(jù)的最小單位是(b )。（a）數(shù)據(jù)元素 (b) 數(shù)據(jù)項(xiàng) (c) 數(shù)據(jù)類型 (d) 數(shù)據(jù)變量3. 以下數(shù)據(jù)結(jié)構(gòu)中（d）屬非線性結(jié)構(gòu)。a.棧 b.串 c.隊(duì)列 d. 平衡二 叉樹4. 以下不屬于存儲(chǔ)結(jié)構(gòu)是（b） 。a.棧 b.線索樹 c.哈希表 d. 雙 鏈表5. 算法的時(shí)間復(fù)雜度取決于（c）。a. 問題的規(guī)模 b. 待處理數(shù)據(jù)的初始狀態(tài)c. a 和 b d. 計(jì)算機(jī)的配置6. 在（

2、d）中將會(huì)用到棧結(jié)構(gòu)。a. 遞歸調(diào)用 b. 函數(shù)調(diào)用 c. 表達(dá)式求值 d. 以上場 景都有7. 某算法的空間復(fù)雜度為 o(1)，則（b）。1a. 該算法執(zhí)行不需要任何輔助空間b. 該算法執(zhí)行所需輔助空間大小與問題規(guī)模 n 無關(guān)c. 該算法執(zhí)行不需要任何空間d. 該算法執(zhí)行所需全部空間大小與問題規(guī)模 n 無關(guān)8. 順序表和鏈表相比存儲(chǔ)密度較大，這是因?yàn)椋╞ ）。a. 順序表的存儲(chǔ)空間是預(yù)先分配的b. 順序表不需要增加指針來表示元素之間的邏輯關(guān)系c. 鏈表中所有節(jié)點(diǎn)的地址是連續(xù)的d. 順序表中所有元素的存儲(chǔ)地址是不連續(xù)的9. 設(shè) n 是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度為 （ a）

3、。x=1;while (x=n)x=5*x;a. o(log n) b.o(n) c.o(nlog n)5 5d.o(n5)10.數(shù)據(jù)結(jié)構(gòu)是指 （d） 。a. 一種數(shù)據(jù)類型 c. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合b. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) d. 一組性質(zhì)相同的數(shù)據(jù)元素的集合11.以下算法的時(shí)間復(fù)雜度為 （a） 。 void fun(int n) int i=1;while (iprior=q; q-next=p;p-prior-next=q; q-prior=p-prior;b. q-prior=p-prior; p-prior-next=q; q-next=p;p-prior=q-n

4、ext;c. q-next=p; p-next=q; p-prior-next=q; q-next=p;d. p-prior-next=q; q-next=p; q-prior=p-prior; p- prior=q;20.在一個(gè)雙鏈表中，刪除 p 所指節(jié)點(diǎn)（非首、尾節(jié)點(diǎn)）的操作是(a) 。a.p-prior-next=p-next;p-next-prior=p-prior;4b. p-prior=p-prior-prior;p-prior-prior=p;c. p-next-prior=p;p-next=p-next-next;d. p-next=p-prior-prior;p-prior=

5、p-prior-prior;21.在長度為 n 的順序表中插入一個(gè)元素，對(duì)應(yīng)算法的時(shí)間復(fù)雜度為（c）。a.o(1) b.o(log n) c.o(n) d.o(n2)2棧和隊(duì)列22.設(shè) n 個(gè)元素進(jìn)棧序列是 1、2、3、n，其輸出序列是若 p =3，1則 p 的值為 c 。2a.一定是 2 b.一定是 1 c.不可能是 1 d. 以上都不對(duì)23.設(shè) n 個(gè)元素進(jìn)棧序列是 p ，p ，p ，p ，其輸出序列是 p 、1 2 3 n 1p 、p ，若 p =3，則 p 的值 a 。2 n 3 1a.可能是 2 b.一定是 2c.不可能是 1 d.一定是 124. 設(shè)棧的輸入序列是 1、2、3、4，

6、則（ d）不可能是其出棧序 列。a.1，2，4，3 b.2，1，3，4 c.1，4，3，2 d.4，3， 1，225.在數(shù)據(jù)處理過程中常需要保存一些中間數(shù)據(jù)，如果要實(shí)現(xiàn)后保存的數(shù)據(jù)先處理，則應(yīng)采用（b）來保存這些數(shù)據(jù)。a.線性表 b.棧 c.隊(duì)列 d. 單 鏈表26.在數(shù)據(jù)處理過程中常需要保存一些中間數(shù)據(jù)，如果先保存的數(shù)據(jù)先處理，則使用（ b）來保存這些數(shù)據(jù)。5a.線性表 b. 隊(duì)列 c. 棧 d.單鏈表27.在環(huán)形隊(duì)列中，元素的排列順序（c ）。a.與隊(duì)頭和隊(duì)尾指針的取值有關(guān) b.與元素值的大小有關(guān)28. c.由元素進(jìn)隊(duì)的先后順序確定 d. 與存放隊(duì)中元素的數(shù)組大小有關(guān)設(shè)循環(huán)隊(duì)列的最大容量是

7、 n，front 是頭指針，rear 是尾 指針，則隊(duì)空的判定條件為（c）。a. (rear+1)%n=front b. rear+1=frontc. rear=front d. rear=0，且 front=029.若某循環(huán)隊(duì)列有隊(duì)首指針 front 和隊(duì)尾指針 rear，在隊(duì)不滿時(shí)進(jìn)隊(duì)操作僅會(huì)改變指針（b）。a.front b.rear c.front 和 rear d. 以上都 不隊(duì)30.判定一個(gè)循環(huán)隊(duì)列 q(最多元素為 m) 為滿隊(duì)列的條件是 (c ) 。(a) q-front=q-rear (b) q-front!=q-rear(c)q-front=(q-rear+1)%m (d)q

8、-front!= (q-rear+1)%m31.棧和隊(duì)列的共同特點(diǎn)是(a )。(a)只允許在端點(diǎn)處插入和刪除元素 (b)都是先進(jìn)后出(c)都是先進(jìn)先出 (d)沒有共同點(diǎn)32.設(shè)環(huán)形隊(duì)列中數(shù)組的下標(biāo)為 0n-1，其隊(duì)頭、隊(duì)尾指針分別為 front 和 rear（front 指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，rear 指向隊(duì)尾元素的位置），則其元素個(gè)數(shù)為（d） 。a. rear-front b. rear-front-1c. (rear-front)n+1 d. (rear-front+n)n33.若用一個(gè)大小為 6 的數(shù)組來實(shí)現(xiàn)環(huán)形隊(duì)列，隊(duì)頭指針 front 指6向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，隊(duì)尾

9、指針 rear 指向隊(duì)尾元素的位置。若當(dāng)前 rear 和 front 的值分別為 0 和 3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear 和 front 的值分別為(b)。 a. 1 和 5 b. 2 和 4c. 4 和 2 d. 5 和 134.35.中綴表達(dá)式 a*(b+c)-d 的對(duì)應(yīng)的后綴表達(dá)式是 （b） 。a. a b c d * + - b. a b c +* d - c. a b c * + d - d.- + * a b c d設(shè)輸入序列為 a，b，c，d，借助一個(gè)棧規(guī)定 a 最先輸出，則不可能的輸出序列為（ c） a a，b，d，c b a，d，c，b c a，d，b

10、，c d a，c，d，b串?dāng)?shù)組和廣義表36.37.在 kmp 算法中，串“ababaabab”的 next 數(shù)組值為（a）。 a. -1,0,0,1,2,3,1,2,3 b. -1,0,0,1,2,1,1,2,3c. -1,0,0,1,2,3,4,1,2 d. -1,0,0,1,2,3,1,2,2 設(shè)二維數(shù)組 a35，每個(gè)數(shù)組元素占用 2 個(gè)存儲(chǔ)單元，若按列優(yōu)先順序進(jìn)行存儲(chǔ)，a00的存儲(chǔ)地址為 100，則 a23的存儲(chǔ) 地址是 （a）。a. 122 b. 126c. 114 d. 11638.設(shè)數(shù)組 a0.5, 0.6的每個(gè)元素占 5 個(gè)存儲(chǔ)單元。則將其按行優(yōu)先存儲(chǔ)在起始地址為 1000 的連

11、續(xù)內(nèi)存單元中，則元素 a55 的存儲(chǔ)地址為（a ）。7c. d.( n +1)n( n +1)39.a1200 b1180 c1205 d1175將 10 階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組 a 中，則數(shù)組 a 的長度最少為（d ）。a.100 b.40 c.80 d.40.若一個(gè)棧采用數(shù)組 s0.n-1存放其元素，初始時(shí)棧頂指針為n，則以下元素 x 進(jìn)棧的正確操作是（c） 。 a.top+;stop=x; b.stop=x;top+;c.top-;stop=x; b.stop=x;top-;41.一個(gè) nn 的對(duì)稱矩陣 a，如果采用以列優(yōu)先（即以列序?yàn)橹餍颍┑膲嚎s方式存放到一個(gè)一維數(shù)組 b 中，則

12、 b 的容量為 c 。a. n2b.n2 22 2 2樹結(jié)構(gòu)42.在下列存儲(chǔ)形式中，_d_ 不是 m 叉樹（m2）的存儲(chǔ)形式？a雙親表示法 b孩子鏈表表示法 c孩子兄弟表示法 d順 序存儲(chǔ)表示法43.若一棵 3 次樹中有 a 個(gè)度為 1 的節(jié)點(diǎn)，b 個(gè)度為 2 的節(jié)點(diǎn)，c個(gè)度為 3 的節(jié)點(diǎn)，則該樹中有（d） 個(gè)葉子節(jié)點(diǎn)。a.1+2b+3cb.a+2b+3cc.2b+3cd.1+b+2c44.設(shè)樹 t 的度為 4，其中度為 1、2、3、4 的結(jié)點(diǎn)個(gè)數(shù)分別為 4、2、1、1，則 t 中的葉子結(jié)點(diǎn)個(gè)數(shù)是（d） 。a.5 b.6 c.7 d.845.一棵二叉樹的后序遍歷序列為 dabec，中序遍歷序列

13、為 debac，則先序遍歷序列為 d 。8a.acbed b.decabc.deabc d.cedba46.一棵深度為 h（h1）的完全二叉樹至少有（a）個(gè)結(jié)點(diǎn)。a. 2h-1b. 2h47.c. 2h+1 d. 2h-1+1設(shè)森林 f 中有 4 棵樹，第 1、2、3、4 棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為a、b、c、d，將森林 f 轉(zhuǎn)換為一顆二叉樹 b，則二叉樹 b 根結(jié)點(diǎn)的左 子樹上的結(jié)點(diǎn)個(gè)數(shù)是（a） 。a.a-1 b.ac. a+b+cd.b+c+d48.由權(quán)值分別為 9、2、7、5 的四個(gè)葉子節(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（b ）。a.23 b.44 c.37 d.2749.一棵含有 n

14、 個(gè)結(jié)點(diǎn)的線索二叉樹中，其線索個(gè)數(shù)為（c） 。 a. 2n b. n-1c. n+1 d. n50. 設(shè)給定權(quán)值總數(shù)有 n 個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（d ） a 不確定 b 2n c 2n+1 d 2n-1第 1 次必定是 2 個(gè)葉子組成二叉樹,產(chǎn)生 1 新結(jié)點(diǎn),接下來有 2 種情況： 1.此新結(jié)點(diǎn)與原剩下的葉子再組成二叉樹又產(chǎn)生 1 新結(jié)點(diǎn),這樣就只 有第 1 次時(shí)由 2 個(gè)葉子產(chǎn)生 1 新結(jié)點(diǎn),以后每次由 1 葉子與新結(jié)點(diǎn)產(chǎn) 生新結(jié)點(diǎn),故 n 個(gè)葉子共有 2n-1 個(gè)結(jié)點(diǎn).2.剩下的葉子中又有 2 個(gè)葉子(比第 1 次產(chǎn)生的新結(jié)點(diǎn)權(quán)小)結(jié)合產(chǎn)生 新結(jié)點(diǎn),其它類似,那么必然會(huì)由 2 個(gè)都是

15、新結(jié)點(diǎn)再產(chǎn)生新結(jié)點(diǎn),所以 實(shí)際上數(shù)量與第 1 種一樣,共有 2n-1 個(gè).圖結(jié)構(gòu)51.無向圖的鄰接矩陣是一個(gè)（ c）。a 上三角矩陣 b 對(duì)角矩陣 c 對(duì)稱矩陣d零矩陣952.如圖所示有向圖的一個(gè)拓?fù)湫蛄惺?b )。(a)abcdef (b)fcbead(c) fedcba) (d) daebcf53.一個(gè)含有 n 個(gè)頂點(diǎn)的無向連通圖采用鄰接矩陣存儲(chǔ)，則該矩陣一定是（a）。a. 對(duì)稱矩陣 b. 非對(duì)稱矩陣 c. 稀疏矩陣 d. 稠密矩陣54.設(shè)無向連通圖有 n 個(gè)頂點(diǎn) e 條邊，若滿足（a），則圖中一定有回路。a. en b. enext!=null。16棧和隊(duì)列5. 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)是

16、 0n-1，其隊(duì)頭隊(duì)尾指針分別為 f 和r（f 指向隊(duì)首元素的前一位置，r 指向隊(duì)尾元素），則其元素個(gè)數(shù)為 (r-f+n)n 。6. 設(shè)棧 s 和隊(duì)列 q 的初始狀態(tài)都為空，元素 a、b、c、d、e 和 f 依次通過棧 s，一個(gè)元素出棧后即進(jìn)入隊(duì)列 q，若 6 個(gè)元素出隊(duì)的序列是 b、d、c、f、e、a，則棧 s 的容量至少應(yīng)該存 3 個(gè)元素？串和數(shù)組7. 在 kmp 算法中，設(shè)模式串 p=abcabaa，那么 p 的 nextval 數(shù)組為 （-1,0,0,-1,0,2,1）。8. 若將 n 階上三角矩陣 a 按列優(yōu)先順序壓縮存放在一維數(shù)組b1.n(n+1)/2中，a 中第一個(gè)非零元素 a

17、存于 b 數(shù)組的 b 中，則1,1 1應(yīng)存放到 b 中的非零元素 a （1in，1ji）的下標(biāo) i、j 與 k k i,j的對(duì)應(yīng)關(guān)系是j( j -1) 2+i。9. 設(shè)二維數(shù)組 a35，每個(gè)數(shù)組元素占用 2 個(gè)存儲(chǔ)單元，若按列優(yōu)先順序進(jìn)行存儲(chǔ)，a00的存儲(chǔ)地址為 100，則 a23的存儲(chǔ)地 址是 。10.兩個(gè)串是相等的，當(dāng)且僅當(dāng)兩個(gè)串的長度相等且 各對(duì)應(yīng)位置上的_的字符都相同。11.對(duì)矩陣進(jìn)行壓縮是為了_節(jié)省存儲(chǔ)空間_。17樹結(jié)構(gòu)12.設(shè)某棵二叉樹中度數(shù)為 0 的結(jié)點(diǎn)有 m 個(gè)，度數(shù)為 1 的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（2m+n-1）個(gè)結(jié)點(diǎn)。13.設(shè)某棵二叉樹中有 2000 個(gè)結(jié)點(diǎn)，則該二叉

18、樹的最小高度為_11_。14.一棵二叉樹的先序遍歷序列為 abcdef ，中序遍歷序列為cbaedf，則后序遍歷序列為 cbefda 。15.設(shè)森林 f 對(duì)應(yīng)的二叉樹為 b，b 中有 m 個(gè)節(jié)點(diǎn)，其根節(jié)點(diǎn)的右子樹的節(jié)點(diǎn)個(gè)數(shù)為 n，森林 f 中第一棵樹的節(jié)點(diǎn)個(gè)數(shù)是 m-n 。16.高度為 7 的完全二叉樹至少有_32_個(gè)葉子結(jié)點(diǎn)。圖結(jié)構(gòu)17.設(shè) 完 全 無 向 圖 中 有 n 個(gè) 頂 點(diǎn) ， 則 該 完 全 無 向 圖 中 共 有（n(n-1)/2）條邊。18.對(duì)于有 n 個(gè)頂點(diǎn) e 條邊的有向圖，求單源最短路徑的 dijkstra算法的時(shí)間復(fù)雜度為 o(n2) 。19.在一個(gè)具有 n 個(gè)頂點(diǎn)的

19、有向圖中，構(gòu)成強(qiáng)連通圖時(shí)至少有 n條邊。20.如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次廣度優(yōu)先遍歷即可訪問所有頂點(diǎn)，則該圖一定是 連通圖 。21.拓?fù)渑判?方法可以判斷一個(gè)有向圖是否存在回路。1822.在無向圖 g 的鄰接矩陣 a 中，若 aij等于 0，則 aji等于_0_。23. 在 有 n 個(gè) 頂 點(diǎn) 的 有 向 圖 中 ， 每 個(gè) 頂 點(diǎn) 的 度 最 大 可 達(dá) 2(n-1) 。查找24.對(duì)有序表 a120按照二分查找方法進(jìn)行查找，那么查找成功時(shí)的最大查找長度為_5_。25.對(duì)含有 n 個(gè)元素的順序表采用順序查找方法，不成功時(shí)的比較次數(shù)是（n ）。26. 對(duì)有 18 個(gè)元素的有序表 r1.1

20、8進(jìn)行二分查找，則查找 r3 的比較序列的下標(biāo)為 9、4、2、3 。27.對(duì)有序表 a120按二分查找方法進(jìn)行查找，查找成功時(shí)的最大查找長度為_3.7_。1 +2*2 + 4*3 + 8*4+ 5*5 = 74 平均長度是 74 /20 =3.7排序28.設(shè)二叉排序樹上有 n 個(gè)結(jié)點(diǎn)，則查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（log29.n2）。堆排序算法的時(shí)間復(fù)雜度最壞的情況下為（ n log n2）。30.有一種排序方法，它每一趟都將未排序序列中的一個(gè)元素，插入到已排序序列的合適位置，該排序方法是（插入排序 ）。1931. 對(duì)含有 n 元素的關(guān)鍵字序列進(jìn)行直接選擇排序時(shí)，所需進(jìn)行的 關(guān)鍵字之間的比較次

21、數(shù)為 n(n-1)/2 。32. 在一棵平衡二叉樹中，每個(gè)節(jié)點(diǎn)的平衡因子的取值范圍是 （-11 ）三、判斷題(每題 1 分,共 5 分)1.2.線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。 ( )非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（ ）3.不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為x的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為o(n)。（ ）4.鏈隊(duì)列執(zhí)行出隊(duì)操作不會(huì)改變頭指針的值,但可能會(huì)改變尾 指針的值。( )5.二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（ ）6.稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來表示稀疏矩陣中的非0元素。（ ）7.8.9.所謂取廣義表的表尾就是返回廣義表中最后一個(gè)

22、元素。 ( )由二叉樹的先序序列和中序序列可以惟一確定該二叉樹 ()中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。 ()10.()11.()滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。2012.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問過。（ ）13.如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（ ）14.若一個(gè)無向圖的以頂點(diǎn)1為起點(diǎn)的深度遍歷序列唯一，則可唯一確定該圖（ ）15.如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等,則稱這兩個(gè)關(guān)鍵字為同義詞。 ()16.分塊查找的基本思想是首

23、先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。 （ ）17.在采用線性探測(cè)法處理沖突的散列表中，所有同義詞在表中相鄰。（x）18.19.直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為 o(n)。 (x)設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為o(nlog2n)。（ ）20.向二叉排序樹中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。（ ）21四、綜合應(yīng)用題（）線性表1. 什么是 adt？并舉例說明。要點(diǎn)：adt 即抽象數(shù)據(jù)類型，是指用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問題的數(shù)學(xué)模型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算，不考 慮計(jì)算機(jī)的具體

24、結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。舉例：參見教材 p10 或 p28。2. 試說明順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)（5 分）答：a)順序存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)相鄰的數(shù)據(jù)元素的存放地址也相鄰優(yōu)點(diǎn)：存儲(chǔ)密度大（=1），存儲(chǔ)空間利用率高。能夠隨機(jī)存取缺點(diǎn)：插入或刪除元素不方便，需要移動(dòng)大量的數(shù)據(jù)元素b) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)相鄰的數(shù)據(jù)元素的存放地址不一 定相鄰優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度?。?1），存儲(chǔ)空間利用率低。不能夠隨機(jī)存22取串、數(shù)組3. 一棵完全二叉樹上有 1001 個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)是多少？ （需寫出推導(dǎo)過程，8 分）答 ： 二 叉 樹 中 度 為 1 的 結(jié) 點(diǎn)

25、個(gè) 數(shù) 只 能 是 1 或 0 。 設(shè) n =1 ，1n=n +n +n =n +n +1=1001，由性質(zhì) 1 可知 n =n +1，由兩式可求 n =500.5， 0 1 2 0 2 0 2 0不成立；設(shè) n =0，n=n +n +n =n +n =1001，由性質(zhì) 1 可知 n =n +1，由1 0 1 2 0 2 0 2兩式可求 n =501。本題答案為：501。0評(píng)分標(biāo)準(zhǔn)：只給出結(jié)果給 3 分，推導(dǎo)過程占 5 分。4. （8 分）已知一棵二叉樹的先序遍歷序列為 abdghceif，它的中 序遍歷序列是 bgdhaeicf，請(qǐng)構(gòu)造出這棵二叉樹，并給出其層次 遍歷序列答:（8 分）最后構(gòu)

26、造的二叉樹如圖 1 所示（4 分），其層次遍歷序列 為 abcdefghi（4 分）。abcdefg hi圖 1 一棵二叉樹樹5. 已知某二叉樹的中序和后序遍歷序列分別為 bfdjgachkei 和fjgdbkhieca ，請(qǐng)畫出該二叉樹，并給出該二叉樹的先序遍歷序列。23m= （8 分）二叉樹如下圖所示： 6 分先序遍歷序列為：abdfgjcehki 2分6. 已知一棵度為 m 的樹中有 n 個(gè)度為 1 的節(jié)點(diǎn)，n 個(gè)度為 2 的節(jié)1 2點(diǎn)，n 個(gè)度為 m 的節(jié)點(diǎn)，問該樹中有多少個(gè)葉子節(jié)點(diǎn)? m解：依題意，設(shè) n 為總的節(jié)點(diǎn)個(gè)數(shù)，n 為葉子節(jié)點(diǎn)（即度為 0 的節(jié)點(diǎn)）0的個(gè)數(shù)，則有：n=n +

27、n +n +n0 1 2 m又有：n-1=度的總數(shù)，即，n-1=n 1+n 2+n m1 2 m兩式相減得：1=n -n -2n -(m-1)n0 2 3 m則有：n =1+n +2n +(m-1)n 0 2 3 m1 + (i -1) nii=2。7. 已知一棵度為 4 的樹中，其度為 0、1、2、3 的結(jié)點(diǎn)數(shù)分別為 14、4、3、2，求該樹的結(jié)點(diǎn)總數(shù) n 和度為 4 的結(jié)點(diǎn)個(gè)數(shù)，并給出推導(dǎo)過 程。答：結(jié)點(diǎn)總數(shù) n=n +n +n +n +n ，即 n=23+n ，又有：度之和=n-1=00 1 2 3 4 4n +1n +2n +30 1 2n +4n ，即 n=17+4n ，綜合兩式得：

28、 n =2，n=25。所以，該樹的 3 4 4 4結(jié)點(diǎn)總數(shù)為 25，度為 4 的結(jié)點(diǎn)個(gè)數(shù)為 2?！驹u(píng)分說明】結(jié)果為 4 分，過程占 6 分。8. 假設(shè)通信電文使用的字符集為 a,b,c,d,e,f,g,h,各字符在電文24中出現(xiàn) 的頻度分別為 : 7,19,2,6,32,3,21,10，試為這 8 個(gè)字符設(shè)計(jì)哈夫曼編 碼。要求:(1). 畫出你所構(gòu)造的哈夫曼樹 (要求樹中左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的 權(quán)值); (2). 按左分支為 0 和右分支為 1 的規(guī)則,分別寫出與每個(gè)字符對(duì)應(yīng)的編碼。 （3）問該字 符串的編碼至少有多少位(2) 每個(gè)字符對(duì)應(yīng)的編碼 ：a : 1010 e:11b :

29、 00 f:10001c : 10000 g:01d : 1001 h:1011(3) (2+3)*5+( 6+7+ 10)*4+*3+( 19+ 21+32 )*2=261 9. 畫出與下圖所示森林對(duì)應(yīng)的二叉樹。25圖10.下圖所示為一有向圖，請(qǐng)給出該圖的下述要求：（12 分）（1）每個(gè)頂點(diǎn)的入度和出度；（2）鄰接表11.對(duì)于圖 1 所示的帶權(quán)有向圖，采用 dijkstra 算法求從頂點(diǎn) 0到其他頂點(diǎn)的最短路徑，要求給出求解過程，包括鄰接矩陣、每一步 的 s 集合、dist 和 path 數(shù)組元素。4237061239122圖 一個(gè)有向圖答：該圖對(duì)應(yīng)的鄰接矩陣如下：26 3 7 00 6 9

30、 2 0 1 2 0 2 0 在求最短路徑時(shí)，s（存放頂點(diǎn)集），dist（存放最短路徑長度）和 path（存放最短路徑）的變化如下：spath0 1 2 3 40dist0 1 2 3 4-0 6 9 20 0 000, 40, 1 ,4 0 5 9 9 20 5 6 7 210 4 0 4 00 4 1 1 00,1,2,40,1,2,3,40 5 6 7 20 5 6 7 20 4 1 1 00 4 1 1 0最后得到的結(jié)果如下：頂點(diǎn) 0 到頂點(diǎn) 1 的最短距離為 5，最短路徑為：0、4、1頂點(diǎn) 0 到頂點(diǎn) 2 的最短距離為 6，最短路徑為：0、4、1、2 頂點(diǎn) 0 到頂點(diǎn) 3 的最短距離

31、為 7，最短路徑為：0、4、1、3 頂點(diǎn) 0 到頂點(diǎn) 4 的最短距離為 2，最短路徑為：0、4。12. （10 分）對(duì)于如圖 1 所示的帶權(quán)無向圖，直接給出利用普里姆算法（從頂點(diǎn) 0 開始構(gòu)造）和克魯斯卡爾算法構(gòu)造出的最小生成樹 的結(jié)果（注意：按求解的順序給出最小生成樹的所有邊，每條邊用(i， j)表示）。272411374052642385圖 一個(gè)帶權(quán)無向圖 g利用普里姆算法從頂點(diǎn) 0 出發(fā)構(gòu)造的最小生成樹為：(0,1)，(0,3)， (1,2)，(2,5)，(5,4)，（5 分）。利用克魯斯卡爾算法構(gòu)造出的最小生成樹為：(0,1)，(0,3)，(1,2)， (5,4)，(2,5) ，（5

32、分）。說明：順序錯(cuò)誤不給分。13.什么是最小生成樹？有哪兩種主 要 求解最小生成樹的算法？任選一種求解的最小生成樹，要求給出求解過程。下 列 圖最小生成樹為：321234或：123 34154165161最小生成樹：連通圖的極小連通子圖，含有全部 n 個(gè)頂點(diǎn)，只有 n 1 條邊。28最小生成樹算法： 算法查找普里姆（prim）算法和 克魯斯卡爾（kruscal）14.設(shè)有一組關(guān)鍵字 32,13,49,24,38,21,4,12，其哈希函數(shù)為：h(key)=key % 7，采用開放地址法的線性探查法解決沖突，試在 09 的哈希地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并求等概率下查找 成功和查找失敗的平均查找長度。（10 分）keyh(key)最 終 地址計(jì) 算 次數(shù)324411366149001243313835321012447412584哈希表如下：6 分0 14 2232435361748199 1asl成4功2832=(1+1+1+1+3+2+4+4)/8=17/82 分asl失敗=(3+2+1+7+6+5+4)/7=42 分29排序15.對(duì)下面數(shù)據(jù)表，寫出采用快速排序算法排序的每一趟結(jié)果，并標(biāo)出第一趟排序中的數(shù)據(jù)移動(dòng)情況。（12 分）（25，101，22，34，15，44，76，66，100，8，54，20，2，5，18）16.不同的排序方