中央廣播電大數(shù)據(jù)結(jié)構(gòu)試題及答案2

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

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

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

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

5、時間復(fù)雜度為O(n)。()6在二叉擾索尉中，若各結(jié)點的搜索概率不等，使得搜索概率越大的結(jié)點離樹根越近，則得到的將是最優(yōu) 二叉扌叟索樹。()7.對一個有向圖進行拓撲排序，一定可以將圖中的所有頂點秤列成一個線性有序的拓撲序列。得分評雅人S3、運體翹(曲小15 6分共30分)】巳知一棵二戈軻的中斤和后序序列如下求岀該二叉軻的所有分支結(jié)點數(shù)和葉子結(jié)點數(shù) 中序用列: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>)假定該圖采用鄰按衣作為存嶄結(jié)構(gòu)我個頂點鄰搖好按除頂點ASCII碼值的次序儲體 的，試分JM寫出從頂點a開始進行深度和廣度授索追歷所鮒到的頂點序列深度找猱頂點序列，ruta*頂點序?qū)?3已知一個芾權(quán)厠的頂點集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;試根據(jù)迪克斯特拉(Dijkstra)算法求

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

8、uJink).閱ifi算法茯劃有&線的上張?zhí)盍R合適的內(nèi)容.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> ;算法功能整用分評卷人六、算法設(shè)計題(甸小題6分共12分L已知二又樹中的結(jié)點類型BinTrzNwk定文為：struct BinTrceNodc char dam； BinTrccNodc * left, * rigbii) iJt中da“為結(jié)點和xiKhc分別為招樹左.右子女紹點的需針域，抿滋下面國效/

10、明編弓岀求-操二又樹中葉子結(jié)點總敷的算法該總最值由函效遞回假定金數(shù)BT初始彳 佝這棵二叉樹的根結(jié)點.ini BTrccLcafC&untCBinTreeNode BT) i2. 取犀下闔函數(shù)“幾理旳恥通過掃描一遍山2數(shù)俎達到蛍飭攤列數(shù)據(jù)的目的便得/ 有負值敘莖位于所有非負值和0值敷愣之前.濟補充完整rcArra.iKc函數(shù)體中遺瀝部分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語旬的內(nèi)容i+ + 8 j、單項選擇題（在括號內(nèi)填寫所選擇的標號，每小題2分，共L8分）1B 2A 3A 4C 5B6. C 7. C 8. D 9. C二、填空題（在橫線處填寫合適的內(nèi)容，每小題2分，共14分）1. 相同2. MaxSize13314最大值5 n1G. O（logn）72三、判斷題（在毎小題前面打?qū)μ柋硎菊_或打叉號表示錯誤，毎小眈分，共14分1 X 2. V 3. V 4. x 5 x6. V 7. x四、運算題（毎小題6分，共3吩）1. 分支結(jié)點數(shù)：4、葉子結(jié)點數(shù)：3/全對給6分，否則

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