杭電《數(shù)據(jù)結構》習題答案

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

2、a1、a2、a3、a4、a5、a6依次入棧，出棧的元素依次進入隊列q，若6個元素的出棧序列為： a2、 a4、a3、a6、 a5、 a1，則棧的容量至少是（ c ）第 14 頁 共 14 頁a) 6b) 4c) 3d) 24. 設在棧中，由頂向下已存放元素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) 中序和后序相同，

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

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

5、nkc) qllink=pllink;qrlink= p;pllink rlink=q;pllink=q12. 若某線性表中最常用的操作是取第i個元素隨機訪問！和第i個元素的前趨元素，則采用（ a ）存儲方式最節(jié)省時間a) 順序表b) 單鏈表c) 雙鏈表d) 單循環(huán)鏈表13. 設數(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

6、 (m + 1)14. 用數(shù)組a0m-1存放循環(huán)隊列的元素值，若其頭尾指針分別為front和rear，則循環(huán)隊列中當前元素的個數(shù)為（ a ）a) (rear front + m) mod mb) (rear front + 1) mod mc) (rear front 1 + m) mod md) (rear front) mod m15. 以下有關數(shù)據(jù)結構的敘述，正確的是（ c ）a) 線性表的線性存儲結構優(yōu)于鏈式存儲結構b) 二叉樹的第i層有2i1個結點，深度為k的二叉樹上有2k1個結點c) 嚴格地講二維數(shù)組不是線性表，但可以看成是線性表在下述含義上的擴展：二維數(shù)組是其數(shù)據(jù)元素為線性表的線

7、性表d) 棧的操作方式是先進先出16. 二維數(shù)組mi,j的元素是4個字符（每個字符占用一個存儲單元）組成的串，行下標i的范圍從0到4，列下標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. 設計一個判別表達式中左右括號是否配對出現(xiàn)的算法，采用（ b ）數(shù)據(jù)結構最佳a) 線性表的順序存儲結構b) 棧c) 隊列d) 線性表的鏈式存儲結構18. 深度為6（根的層次為1）的二叉樹至多有結點（

8、c ）a) 31b) 32c) 63d) 6419. 將含有100個結點的完全二叉樹從根這一層開始，每層從左到右依次對結點編號，根結點的編號為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

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

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

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

12、) 只有左子樹上的部分結點35. 已知一棵二叉樹的前序遍歷結果為abcdef，中序遍歷結果為cbaedf，則后序遍歷結果為（ a ）a) cbefdab) fedcbac) cbedfad) 不定36. 一棵滿二叉樹共有n個結點，其中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. 設矩陣a(aij,1i,j10)的元素滿足：aij 0(ij, 1i,j10)aij0(ij, 1i,j10)現(xiàn)將a的所有非0元素以行序存放在首地址為2000的存儲區(qū)域中，每個元素占4個單元，則元素9,5的首地

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

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

15、) 帶頭結點的雙循環(huán)鏈表42. 下面關于數(shù)據(jù)結構的敘述中，正確的敘述是（ c ）a) 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高b) 鏈表中的每一個結點都包含恰好一個指針c) 將一棵樹轉換成為二叉樹后，根結點沒有右子樹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)

16、 i+j+244. 設樹t的度為4，其中度為1、2、3和4的結點的個數(shù)分別為4、2、1、1，則t中葉子結點的個數(shù)是（ d ）x+4+2+1+1=節(jié)點總數(shù)14223141x=8 a) 5b) 6c) 7d) 845. （x）對樹中的一個結點x，在先根序列的序號為pre(x)，在后跟序列中的序號為post(y)。若樹中結點x是結點x和結點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. 設有向圖g有n

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

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

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

20、 清除第i行 。17. 設f是由t1、t2、t3三棵樹組成的森林，與f對應的二叉樹為b，已知t1、t2、t3的結點個數(shù)分別是n1、n2、n3，則二叉樹b的根結點的左子樹和右子樹中的結點個數(shù)分別為n11和 n2n3 。18. 用數(shù)組a1.n順序存儲完全二叉樹的各結點，則當i(n-1)/2時，結點ai的右子女是結點 a2i+1 。3) 應用題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后的二叉搜索樹60704058

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

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

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

24、者之間有錯綜復雜的關系，有的學生因為愛情，過分的忽視了學習，把感情放在第一位；學習的時候就認真的去學，不要去想愛情中的事，談戀愛的時候用心去談，也可以交流下學習，互相鼓勵，共同進步。49. 有足夠的精力：大學生活，說忙也會很忙，但說輕松也是相對會輕松的！大學生戀愛必須合理安排自身的精力，忙于學習的同時不能因為感情的事情分心，不能在學習期間，放棄學習而去談感情，把握合理的精力，分配好學習和感情。a) 有合理的時間；大學時間可以分為學習和生活時間，合理把握好學習時間和生活時間的“度”很重要；學習的時候，不能分配學習時間去安排兩人的在一起的事情，應該以學習為第一；生活時間，兩人可以相互談談戀愛，用心

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