中央廣播電大數據結構試題及答案2

1、中央廣播電視大學20082009學年度第二學期、幵放本科“期末考試數據結構試題一、單項迭擇題（在括號內填寫所迭擇的標號，每小題2分，共L8分）1-當一個作為實際參數傳遞的對象占用的存儲空間較大并且需要修改時，則對應的形彗應說明為（）。A. 基本類型 B.引用型C.傳值型 D.常值引用型2. 在一個長度為n的順序表的任一位羞插入一個新元素的時間復雜度為（）。A. O（n）B O<n/2）C. 0（1）D. 0（ n1）3. 棧的插入和刪除操作在（）進行.QA棧頂B棧底"C任議位置D.中間位復“4. 已知一個廠義表為A（a, b, c）. （d, e, 0）,從A中取出原子e的運算

2、是（）A. Tail(Hcad(A»B. Head(TaiKA)C. HeacKTailCHeadCTaiKD. HeadCHeadCTailCTaiKA)5. 在一棵二叉樹的徒接存儲中，每個存儲結點至少要包含（）個指針域。AI B2 C3 D46有向團中的一個頂點的度數等于該頂點的（）。A入度B.出度C入度與出度之和 D.（入度十出度）/27.與鄰接矩陣相比，鄰接表更適合于存儲（）。A.無向團 B.連通團C. 稀疏圖 D.稠密圖8在通常情況下，查找數據較快的方法是（）查找方法。A.順序 B.折半C二叉樹 D散列9.在一棵m階B樹中，每個結點所包含的子樹個數最多為（）個。A m/2

3、B m-1C. m D. m4-l二、填空題（在橫線處填寫合適的內容，每小題2分，共14分）1. 在單璉表中設蚤表頭附加結旦的作用是在插入和刪除表中任一個元素時的操作都（）。2.設眾序棧的址大容議為MaxSizctcp-一1表示?？諅扰兴雇墩臈l件爬top-3. 在一棵高皮為4的完全二叉樹中，最多包含有（）個結點。假:£樹根結點的高皮為0。4在一個最大堆中，堆頂結點的值是所有結點中的<）o5. 具有n個頂點的連通圖的生成樹含有（）條邊。6. 在對n個結點逬行的堆排序中，對任意一個分支結點進行調整（篩）運章的時間復雜度（。7假定一個線性表的關健碼序列為(12, 23, 74, 5

4、5, 63, 40, 82, 36)，若按key%3條件。進行劃 分，使得同一余數的元素成為一個子表，則元素74所在子表的長度為()o三、利斷題(在每小題前面打對號表示正確或打叉號表示錯誤，毎小題2分，共14分)()1.在順序耒中，邏輯上相鄰的元素在物理位置上不一定相鄰。()2.璉式棧占順序棧相比，一個明顯的優(yōu)點泉通常不會出現棧満的情況。()3.當向一個最小堆插入一個具有最小值的元素時，該元素需要逐層向上調整，直到被調整到堆頂位置為 止。()4.在一棵二靈樹中，很定每個結點只有右子女，沒有左子女，則對它分別進行前舟遍歷和后序遍歷吋，將 具有相同的結果。()5.向具有n個結點的堆中插入一個元素的

5、時間復雜度為O(n)。()6在二叉擾索尉中，若各結點的搜索概率不等，使得搜索概率越大的結點離樹根越近，則得到的將是最優(yōu) 二叉扌叟索樹。()7.對一個有向圖進行拓撲排序，一定可以將圖中的所有頂點秤列成一個線性有序的拓撲序列。得分評雅人S3、運體翹(曲小15 6分共30分)】巳知一棵二戈軻的中斤和后序序列如下求岀該二叉軻的所有分支結點數和葉子結點數 中序用列:c»biJe»«»gJ厲序厚列；CY,d,bRfm2.已知圖G-<V,E>.其中E® «a.b>.<a.<t>.<a,e>,<b

6、,a>.<c*b>,<eJ>.<d,e>,<e»c>)假定該圖采用鄰按衣作為存嶄結構我個頂點鄰搖好按除頂點ASCII碼值的次序儲體 的，試分JM寫出從頂點a開始進行深度和廣度授索追歷所鮒到的頂點序列深度找猱頂點序列，ruta*頂點序対:3已知一個芾權厠的頂點集V和邊集G分別為：V=0, 1, 2, 3, 4, 5)E=(0, 1)19, (0, 2)10, (0, 3)14, (1, 2)6, (1, 5)5, (2, 3)26, (2, 4)15, (3, 4)18, (4, 5) 6;試根據迪克斯特拉(Dijkstra)算法求

7、出從頂點0到其余各頂點的最矩路徑，在下表中填寫應的路徑長度。頂點：012345路徑長 gh |0|4. 設散列表的長度m=7,散列函數為H(K) = Kmod m,若采用線性探查法解決沖突，依次插入的關鎮(zhèn)硝序列為 19 14, 23, 68, 20, 84,分別求出查我14、20、84時的搜索長度。查找14、20、84的扌叟索長度分別為；5. 已知一個數據集合為36, 25, 30, 62, 40, 53, 46,試把它調整為一個最大堆。最犬堆：)分評卷人五、算法分析£6(每小題6分其12分)1. 該算法功能為：從否頭捋針為I的單磁表中刪陳號X值相同的所育結點朋毎表中的點結構為(da

8、uJink).閱ifi算法茯劃有&線的上張?zhí)盍R合適的內容.void purge_linkM( Us iNode & L. int X)(if(L "NULL) returniLiriNock * p> * pl* p2jp pl new List Node ipl>link"fcp2-tLiwhile (p2>if(p2>dau= = X) (pl>link=p2>link» delete p2< p2cpl >link；>&址 «8JL = p>)inkidelete2

9、. 拒出下面算法的功能ini unknown(int A ini n) if(n = = 1) return 人0$ini tcinp*,runkaownCA« n 1):iR An 1 J5>iemp) return An 1J i elc return lcrnj> ;算法功能整用分評卷人六、算法設計題(甸小題6分共12分L已知二又樹中的結點類型BinTrzNwk定文為：struct BinTrceNodc char dam； BinTrccNodc * left, * rigbii) iJt中da“為結點和xiKhc分別為招樹左.右子女紹點的需針域，抿滋下面國效/

10、明編弓岀求-操二又樹中葉子結點總敷的算法該總最值由函效遞回假定金數BT初始彳 佝這棵二叉樹的根結點.ini BTrccLcafC&untCBinTreeNode BT) i2. 取犀下闔函數“幾理旳恥通過掃描一遍山2數俎達到蛍飭攤列數據的目的便得/ 有負值敘莖位于所有非負值和0值敷愣之前.濟補充完整rcArra.iKc函數體中遺瀝部分M 其能夠完成所麼求的功陡.void reArrangcCT daiaCJ«ir>t sixe)iint Qisixe 1 $T tempiwhic<daui<0 && iVj> i+ + * whi】e(

11、cUtaj>0 && j>i)j</拄下面空行添加if語旬的內容i+ + 8 j、單項選擇題（在括號內填寫所選擇的標號，每小題2分，共L8分）1B 2A 3A 4C 5B6. C 7. C 8. D 9. C二、填空題（在橫線處填寫合適的內容，每小題2分，共14分）1. 相同2. MaxSize13314最大值5 n1G. O（logn）72三、判斷題（在毎小題前面打對號表示正確或打叉號表示錯誤，毎小眈分，共14分1 X 2. V 3. V 4. x 5 x6. V 7. x四、運算題（毎小題6分，共3吩）1. 分支結點數：4、葉子結點數：3/全對給6分，否則

12、。分2. 深度搜索頂點序列；6 b, d, e, c/3分廣度搜索頂點序列；6 b, d, e, c /3分3. 譯分標準：對1個給1分，全對給6分?，F點：0!23451 01C10 I 1425Z14. 查找23、68、84的搜索長度分別為；I、3、4 /毎個數據占2分5. 最大堆：62, 40, 53, 25, 36, 30, 46五、算法分析髓（毎小國6分，共12分）pl-p2、p2=p2A】inkX p2p->IMk）每空 3 分2求出井返回效組An中門個數黠的直大值.木上法設i+a（W小理6分，共12分1.評分標準；根據須程酌情給分ini BTrccLcfCount（Bin 1 rceNodc * Bl）i(BT® NULL) return Oielse if(BT->lefi-NULL &a