杭電《數(shù)據(jù)結(jié)構(gòu)》習(xí)題答案

1、軟件技術(shù)基礎(chǔ)之?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題1) 選擇題1. *下面關(guān)于線性表的敘述中，正確的是（ d ）a) 線性表的每個元素都有一個直接前驅(qū)和直接后繼b) 線性表中至少要有一個元素c) 線性表中的元素必須按遞增或遞減的順序排列d) 除第一個元素和最后一個元素外，其余每個元素有且僅有一個直接前驅(qū)和直接后繼2. 下面關(guān)于線性表的敘述中，錯誤的是（ b ）a) 采用順序存儲的線性表必須占用一片連續(xù)的存儲單元b) 采用順序存儲的線性表便于進行插入和刪除操作c) 采用鏈接存儲的線性表，不必占用一片連續(xù)的存儲單元d) 采用鏈接存儲的線性表，便于進行插入和刪除操作3. 設(shè)有棧s和隊列q，初始狀態(tài)皆為空，元素a1、a2、a

2、3、a4、a5、a6依次入棧，出棧的元素依次進入隊列q，若6個元素的出棧序列為： a2、 a4、a3、a6、 a5、 a1，則棧的容量至少是（ c ）a) 6b) 4c) 3d) 24. 設(shè)在棧中，由頂向下已存放元素c、b、a，在第4個元素d入棧前，棧中元素可以出棧，試問d入棧后，不可能的出棧序列是（ c ）a) d c b a b) c b d ac) c a d bd) c d b a5. *在一棵二叉樹的先序遍歷、中序遍歷、后序遍歷序列中，所有葉節(jié)點的先后順序（ b ）a) 都不相同b) 完全相同c) 先序和中序相同，后序不同d) 中序和后序相同，先序不同6. 設(shè)二叉樹根結(jié)點的層次為0，

3、一棵高度為h的滿二叉樹的結(jié)點個數(shù)是（ c ）a) 2hb) 2h1c) 2h1d) 2h117. 已知一棵二叉樹的前序序列為abdgcfk，中序序列為dgbafck，則結(jié)點的后序序列為（ b ）a) acfkdbgb) gdbfkcac) kcfagdbd) abcdfkg8. 欲得到二叉搜索樹（bst）各結(jié)點值的遞增序列，試問應(yīng)該采用何種遍歷方法（ b ）a) 先序遍歷b) 中序遍歷c) 后序遍歷d) 層次遍歷9. *與數(shù)據(jù)元素本身這是存儲的內(nèi)容的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（ c ）a) 存儲結(jié)構(gòu)b) 存儲形式c) 邏輯結(jié)構(gòu)d) 運算實現(xiàn)10. 有一棵非空的二叉樹（第0層為根結(jié)

4、點），其第i層上至多有（ a ）個節(jié)點a) 2ib) 2i1c) 2i1d) i11. 雙向鏈表結(jié)點結(jié)構(gòu)如下：llinkrlinkdata其中：llink是指向前趨結(jié)點的指針域，data是存放數(shù)據(jù)元素的數(shù)據(jù)域，rlink是指向后繼結(jié)點的指針域。下面給出的算法段是要把一個新結(jié)點q作為非空雙向鏈表的結(jié)點p的前趨，插入到此雙向鏈表中。能正確完成要求的算法段是（ c ）a) qllink=pllink;qrlink= p;pllink=q;pllink rlink=qb) pllink=q;qrlink= p;pllink rlink=q;qllink=pllinkc) qllink=pllink;q

5、rlink= p;pllink rlink=q;pllink=q12. 若某線性表中最常用的操作是取第i個元素隨機訪問！和第i個元素的前趨元素，則采用（ a ）存儲方式最節(jié)省時間a) 順序表b) 單鏈表c) 雙鏈表d) 單循環(huán)鏈表13. 設(shè)數(shù)組data0m作為循環(huán)隊列sq的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為（ d ）a) front := front + 1b) front := (front + 1) mod mc) rear := (rear + 1)mod md) front :=(front + 1)mod (m + 1)14. 用數(shù)組a0m-1

6、存放循環(huán)隊列的元素值，若其頭尾指針分別為front和rear，則循環(huán)隊列中當(dāng)前元素的個數(shù)為（ a ）a) (rear front + m) mod mb) (rear front + 1) mod mc) (rear front 1 + m) mod md) (rear front) mod m15. 以下有關(guān)數(shù)據(jù)結(jié)構(gòu)的敘述，正確的是（ c ）a) 線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)b) 二叉樹的第i層有2i1個結(jié)點，深度為k的二叉樹上有2k1個結(jié)點c) 嚴(yán)格地講二維數(shù)組不是線性表，但可以看成是線性表在下述含義上的擴展：二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表d) 棧的操作方式是先進先出16.

7、二維數(shù)組mi,j的元素是4個字符（每個字符占用一個存儲單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5。m按行存儲時的元素m3,5的起始地址與m按列存儲時的元素（ b ）的起始地址相同a) m2,4b) m3,4c) m3,5d) m4,4m0:4, 0:5a +i*6+j=a+3*6+5a+j*5+i3*6+5= j*5+i i,jn,17. 設(shè)計一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用（ b ）數(shù)據(jù)結(jié)構(gòu)最佳a) 線性表的順序存儲結(jié)構(gòu)b) 棧c) 隊列d) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)18. 深度為6（根的層次為1）的二叉樹至多有結(jié)點（ c ）a) 31b) 32c) 63d)

8、 6419. 將含有100個結(jié)點的完全二叉樹從根這一層開始，每層從左到右依次對結(jié)點編號，根結(jié)點的編號為1。編號為71的雙親的編號為（ b ）a) 34b) 35c) 36d) 無法確定20. 如圖所示二叉樹的中序遍歷序列是（ b ）a) a b c d g e fb) d f e b a g cc) d b a e f c gd) d e f b a g c21. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，則它的前序遍歷序列為（ d ）a) a c b e d b) d e c a bc) d e a b cd) c e d b a22. 如果t2是由樹t轉(zhuǎn)換而來的二叉

9、樹，那么t中結(jié)點的前序就是t2中結(jié)點（ a ）a) 前序b) 中序c) 后序d) 層次序23. 如果t2是由樹t轉(zhuǎn)換而來的二叉樹，那么t中結(jié)點的后序就是t2中結(jié)點（ b ）a) 前序b) 中序c) 后序d) 層次序24. 若某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh，中序遍歷的結(jié)點訪問順序是bgdaechf，則其后序遍歷的結(jié)點訪問順序是（ d ）a) bdgcefhab) gdbecfhac) bdgechfad) gdbehfca25. *在計算遞歸函數(shù)時，如不使用遞歸過程，則一般情況下必須借助于（ a ）數(shù)據(jù)結(jié)構(gòu)a) 棧b) 樹c) 雙向隊列d) 廣義表26. 二叉樹的前序遍歷序列中

10、，任意一個結(jié)點均處在其子女結(jié)點的前面。這種說法（ a ）a) 正確b) 錯誤27. 由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹時一種特殊的樹。這種說法（ b ）a) 正確b) 錯誤28. *二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值，小于其右孩子的值。這種說法（ b ）a) 正確b) 錯誤29. 設(shè)二叉樹根結(jié)點的層次為0，一棵高度為h的滿二叉樹中的結(jié)點個數(shù)是（ d ）a) 2hb) 2h-1c) 2h-1d) 2h+1-130. 含n個頂點的聯(lián)通圖中任意一條簡單路徑，其長度不可能超過（ c ）a) 1b) n/2c) n1d) n31. *實現(xiàn)任意二叉樹的后序遍歷的非

11、遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹采用（ c ）存儲結(jié)構(gòu)a) 二叉鏈表b) 廣義表存儲結(jié)構(gòu)c) 三叉鏈表d) 順序存儲結(jié)構(gòu) 32. 具有65個結(jié)點的完全二叉樹深度為（ b ）（根的層次號為1）a) 8b) 7c) 6d) 533. 以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在具有n個結(jié)點的二叉鏈表中（n0），空鏈域的個數(shù)為（ c =2n-(n-1) =n+1 ）a) 2n-1b) n-1c) n+1d) 2n+134. 在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（ a ）a) 只有右子樹上的所有結(jié)點b) 只有右子樹上的部分結(jié)點c) 只有左子樹上的所有結(jié)點d) 只有左子樹上的部分結(jié)點35. 已知一

12、棵二叉樹的前序遍歷結(jié)果為abcdef，中序遍歷結(jié)果為cbaedf，則后序遍歷結(jié)果為（ a ）a) cbefdab) fedcbac) cbedfad) 不定36. 一棵滿二叉樹共有n個結(jié)點，其中m個為樹葉，則（ b ）n=2h-1=2h-1 2-1=m2-1, m=2h-1a) n=m+1b) m=(n+1)/2c) n=2md) n=2m37. 設(shè)矩陣a(aij,1i,j10)的元素滿足：aij 0(ij, 1i,j10)aij0(ij, 1i,j10)現(xiàn)將a的所有非0元素以行序存放在首地址為2000的存儲區(qū)域中，每個元素占4個單元，則元素9,5的首地址為（ aord(i,j)=i(i-1)

13、/2+j-1 ）a) 2160b) 2164c) 2336d) 234038. 設(shè)高度為h的二叉樹上只有度為0和2的結(jié)點，則此類二叉樹中所含的結(jié)點數(shù)至少為（ b ），至多為（ e ）a) 2hb) 2h-1c) 2h+1d) h-1e) 2h-1f) 2h-1g) 2(h+1)-1h) 2h+139. 已知一有向圖的鄰接表出表存儲結(jié)構(gòu)如下：（1）、根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（ b ）a) v1v2v3v5v4b) v1v3v4v5v2c) v1v3v2v4v5d) v1v4v3v5v2（2）、根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是

14、（ c ）a) v1v2v3v4v5b) v1v2v3v5v4c) v1v3v2v4v5d) v1v4v3v2v5（3）、能否根據(jù)鄰接表畫出該有向圖？為什么？答：能，因為該鄰接表已經(jīng)表明了該圖的所有節(jié)點以及所有節(jié)點之間的關(guān)系，即g（v，e）中的集合v和e都表達(dá)清楚了。40. 鄰接表存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法結(jié)構(gòu)類似于二叉樹的（ a ）a) 先序遍歷b) 中序遍歷c) 后序遍歷d) 按層遍歷41. 若某鏈表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素，則采用（ d ）存儲方式最節(jié)省運算時間。a) 單鏈表b) 雙鏈表c) 單循環(huán)鏈表d) 帶頭結(jié)點的雙循環(huán)鏈表42. 下面關(guān)于

15、數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的敘述是（ c ）a) 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高b) 鏈表中的每一個結(jié)點都包含恰好一個指針c) 將一棵樹轉(zhuǎn)換成為二叉樹后，根結(jié)點沒有右子樹43. 一個nn的帶狀矩陣aaij如下： a11 a12 a21 a22 a23 a32 a33 a34 a an-1 n an n-1 an n 將帶狀區(qū)域的元素aij（|ij|1）按行序為主序存儲在一維數(shù)組b1.3n-2中，元素aij在b中的存儲位置是（ b ）ord(i,j)=3(i-1)-1+2+j-ia) i+2j-1b) 2i+j-2c) 3i-j+1d) i+j+244. 設(shè)樹t的度為4，其中

16、度為1、2、3和4的結(jié)點的個數(shù)分別為4、2、1、1，則t中葉子結(jié)點的個數(shù)是（ d ）x+4+2+1+1=節(jié)點總數(shù)14223141x=8 a) 5b) 6c) 7d) 845. （x）對樹中的一個結(jié)點x，在先根序列的序號為pre(x)，在后跟序列中的序號為post(y)。若樹中結(jié)點x是結(jié)點x和結(jié)點y的祖先，下列四個條件哪個條件正確（ ）a) pre(x) pre(y) 和 post(x) post(y)b) pre(x) post(y)c) pre(x) pre(y) 和 post(x) pre(y) 和 post(x)post(y)46. 設(shè)有向圖g有n個頂點，它的鄰接矩陣為a，g中第i個頂點

17、vi的度為（ c ）a)b)c)d) 47. 二叉樹的先序遍歷和中序遍歷如下：先序遍歷：efhigjk中序遍歷：hfiejkg該二叉樹根的右子樹的根是（ c ）a) eb) fc) gd) h2) 填空題1. 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，分別是 數(shù)據(jù)的邏輯結(jié)構(gòu) 、 物理結(jié)構(gòu) 、算法結(jié)構(gòu)。2. 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類，它們是 線性結(jié)構(gòu) 、 非線性結(jié)構(gòu) 。3. 數(shù)據(jù)結(jié)構(gòu)的四種基本的存儲方法是 順序存儲 、 鏈?zhǔn)酱鎯?、索引存儲、散列存儲。4. 數(shù)據(jù)的基本單位是 數(shù)據(jù)元素 。5. 在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是 !(

18、p-next) 。6. 設(shè)一個鏈棧的棧頂指針為top，棧中結(jié)點兩個字段分別為info和next，其中next是指示后繼結(jié)點的指針，?？盏臈l件是 (!top) 。如果棧不空，則退棧操作為：p:=top; top:=top-next ;dispose(p);7. 設(shè)r指向單鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入指針s所指的結(jié)點，需執(zhí)行的三條語句是： r-next=s ; r:=s; r.next:=nil;8. 數(shù)組通常只有兩種運算： 讀 和寫（給定下標(biāo)，修改相應(yīng)的元素），這決定了數(shù)組通常采用 順序表 來實現(xiàn)存儲。9. 多維數(shù)組的兩種存儲方式是 按行序存儲 和 按列序存儲 。10. 棧和隊列

19、均可視為特殊的線性表，所不同的在于他們的 添加 和 刪除 運算的限定不一樣。11. 圖的主要存儲結(jié)構(gòu)有兩種，分別為 相鄰矩陣 和 鄰接表 。12. 將一棵樹轉(zhuǎn)化成二叉樹的步驟是 。13. 從概念上講，樹和二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化成二叉樹的基本目的是： 。14. 設(shè)n個節(jié)點的m叉樹采用m叉鏈表（即每個結(jié)點有m個指針域，用來存放每個子樹的根結(jié)點的存儲地址）存儲結(jié)構(gòu)，請問會有 nm-（n-1） 個空指針域。15. 已知一個圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是 列的和 。16. 已知一個圖的鄰接矩陣表示，刪除所有從第i個結(jié)點出發(fā)的弧的方法是 清除第i行 。17. 設(shè)f是由t1、t

20、2、t3三棵樹組成的森林，與f對應(yīng)的二叉樹為b，已知t1、t2、t3的結(jié)點個數(shù)分別是n1、n2、n3，則二叉樹b的根結(jié)點的左子樹和右子樹中的結(jié)點個數(shù)分別為n11和 n2n3 。18. 用數(shù)組a1.n順序存儲完全二叉樹的各結(jié)點，則當(dāng)i(n-1)/2時，結(jié)點ai的右子女是結(jié)點 a2i+1 。3) 應(yīng)用題1. 答：用三元組法表示稀疏矩陣可以節(jié)省存儲空間。用三元組表示該稀疏矩陣： （6，6，8）（1，6，2）（2，1，1）（2，5，3）（3，4，5）（3，6，7）（4，2，8）（5，5，5）（6，4，6） 2. 答：1）插入節(jié)點66后的二叉搜索樹60704058756557682）刪除節(jié)點60后的二搜

21、索叉樹（1）從左子樹取節(jié)點58704075576568（2）從右子樹取節(jié)點657040755868573）用一維數(shù)組表達(dá)圖二所示的樹的存儲結(jié)構(gòu)（60，40，70，0，58，65，75，0，0，57，0，0，0，68，0，0）4）用一維數(shù)組表達(dá)二叉樹的存儲結(jié)構(gòu)的缺點為容易浪費存儲空間。3. 答： 1）說明每個頂點的度(degree)頂點度1323334252632）圖的表示法中,相對于相鄰矩陣,鄰接表有下列好處 存儲效率高，訪問方便。 3）該圖的相鄰矩陣 010011101100010101011000100001100010 4）該圖的鄰接表表示 5）根據(jù)第4小題的鄰接表從頂點1開始的深度遍歷

22、為： 1、2、3、4、6、5廣度優(yōu)先遍歷為：1、2、5、6、3、4我的大學(xué)愛情觀目錄：1、 大學(xué)概念2、 分析愛情健康觀3、 愛情觀要三思4、 大學(xué)需要對愛情要認(rèn)識和理解5、 總結(jié)1、什么是大學(xué)愛情：大學(xué)是一個相對寬松，時間自由，自己支配的環(huán)境，也正因為這樣，培植愛情之花最肥沃的土地。大學(xué)生戀愛一直是大學(xué)校園的熱門話題，戀愛和學(xué)業(yè)也就自然成為了大學(xué)生在校期間面對的兩個主要問題。戀愛關(guān)系處理得好、正確，健康，可以成為學(xué)習(xí)和事業(yè)的催化劑，使人學(xué)習(xí)努力、成績上升；戀愛關(guān)系處理的不當(dāng)，不健康，可能分散精力、浪費時間、情緒波動、成績下降。因此，大學(xué)生的戀愛觀必須樹立在健康之上，并且樹立正確的戀愛觀是十分

23、有必要的。因此我從下面幾方面談?wù)勛约旱膶Υ髮W(xué)愛情觀。2、什么是健康的愛情：1) 尊重對方，不顯示對愛情的占有欲，不把愛情放第一位，不癡情過分；2) 理解對方，互相關(guān)心，互相支持，互相鼓勵，并以對方的幸福為自己的滿足; 3) 是彼此獨立的前提下結(jié)合；3、什么是不健康的愛情：1)盲目的約會，忽視了學(xué)業(yè);2)過于癡情，一味地要求對方表露愛的情懷，這種愛情常有病態(tài)的夸張;3)缺乏體貼憐愛之心，只表現(xiàn)自己強烈的占有欲;4)偏重于外表的追求;4、大學(xué)生處理兩人的在愛情觀需要三思：1. 不影響學(xué)習(xí)：大學(xué)戀愛可以說是一種必要的經(jīng)歷，學(xué)習(xí)是大學(xué)的基本和主要任務(wù)，這兩者之間有錯綜復(fù)雜的關(guān)系，有的學(xué)生因為愛情，過分

24、的忽視了學(xué)習(xí)，把感情放在第一位；學(xué)習(xí)的時候就認(rèn)真的去學(xué)，不要去想愛情中的事，談戀愛的時候用心去談，也可以交流下學(xué)習(xí)，互相鼓勵，共同進步。2. 有足夠的精力：大學(xué)生活，說忙也會很忙，但說輕松也是相對會輕松的！大學(xué)生戀愛必須合理安排自身的精力，忙于學(xué)習(xí)的同時不能因為感情的事情分心，不能在學(xué)習(xí)期間，放棄學(xué)習(xí)而去談感情，把握合理的精力，分配好學(xué)習(xí)和感情。3、 有合理的時間；大學(xué)時間可以分為學(xué)習(xí)和生活時間，合理把握好學(xué)習(xí)時間和生活時間的“度”很重要；學(xué)習(xí)的時候，不能分配學(xué)習(xí)時間去安排兩人的在一起的事情，應(yīng)該以學(xué)習(xí)為第一；生活時間，兩人可以相互談?wù)剳賽?，用心去談，也可以交流下學(xué)習(xí)，互相鼓勵，共同進步。5、

25、大學(xué)生對愛情需要認(rèn)識與理解，主要涉及到以下幾個方面：（1） 明確學(xué)生的主要任務(wù)“放棄時間的人，時間也會放棄他?！贝髮W(xué)時代是吸納知識、增長才干的時期。作為當(dāng)代大學(xué)生，要認(rèn)識到現(xiàn)在的任務(wù)是學(xué)習(xí)學(xué)習(xí)做人、學(xué)習(xí)知識、學(xué)習(xí)為人民服務(wù)的本領(lǐng)。在校大學(xué)生要集中精力，投入到學(xué)習(xí)和社會實踐中，而不是因把過多的精力、時間用于談情說愛浪費寶貴的青春年華。因此，明確自己的目標(biāo)，規(guī)劃自己的學(xué)習(xí)道路，合理分配好學(xué)習(xí)和戀愛的地位。（2） 樹林正確的戀愛觀提倡志同道合、有默契、相互喜歡的愛情：在戀人的選擇上最重要的條件應(yīng)該是志同道合，思想品德、事業(yè)理想和生活情趣等大體一致。擺正愛情與學(xué)習(xí)、事業(yè)的關(guān)系：大學(xué)生應(yīng)該把學(xué)習(xí)、事業(yè)放在首位，擺正愛情與學(xué)習(xí)、事業(yè)的關(guān)系，不能把寶貴的大學(xué)時間，鍛煉自身的時間都用于談情說有愛