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

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

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

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

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

5、時(shí)間復(fù)雜度為O(n)。()6在二叉擾索尉中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越大的結(jié)點(diǎn)離樹(shù)根越近，則得到的將是最優(yōu) 二叉扌叟索樹(shù)。()7.對(duì)一個(gè)有向圖進(jìn)行拓?fù)渑判?，一定可以將圖中的所有頂點(diǎn)秤列成一個(gè)線性有序的拓?fù)湫蛄小５梅衷u(píng)雅人S3、運(yùn)體翹(曲小15 6分共30分)】巳知一棵二戈軻的中斤和后序序列如下求岀該二叉軻的所有分支結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(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)我個(gè)頂點(diǎn)鄰搖好按除頂點(diǎn)ASCII碼值的次序儲(chǔ)體 的，試分JM寫(xiě)出從頂點(diǎn)a開(kāi)始進(jìn)行深度和廣度授索追歷所鮒到的頂點(diǎn)序列深度找猱頂點(diǎn)序列，ruta*頂點(diǎn)序?qū)?3已知一個(gè)芾權(quán)厠的頂點(diǎ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、出從頂點(diǎn)0到其余各頂點(diǎn)的最矩路徑，在下表中填寫(xiě)應(yīng)的路徑長(zhǎng)度。頂點(diǎn)：012345路徑長(zhǎng) gh |0|4. 設(shè)散列表的長(zhǎng)度m=7,散列函數(shù)為H(K) = Kmod m,若采用線性探查法解決沖突，依次插入的關(guān)鎮(zhèn)硝序列為 19 14, 23, 68, 20, 84,分別求出查我14、20、84時(shí)的搜索長(zhǎng)度。查找14、20、84的扌叟索長(zhǎng)度分別為；5. 已知一個(gè)數(shù)據(jù)集合為36, 25, 30, 62, 40, 53, 46,試把它調(diào)整為一個(gè)最大堆。最犬堆：)分評(píng)卷人五、算法分析£6(每小題6分其12分)1. 該算法功能為：從否頭捋針為I的單磁表中刪陳號(hào)X值相同的所育結(jié)點(diǎn)朋毎表中的點(diǎn)結(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> ;算法功能整用分評(píng)卷人六、算法設(shè)計(jì)題(甸小題6分共12分L已知二又樹(shù)中的結(jié)點(diǎn)類型BinTrzNwk定文為：struct BinTrceNodc char dam； BinTrccNodc * left, * rigbii) iJt中da“為結(jié)點(diǎn)和xiKhc分別為招樹(shù)左.右子女紹點(diǎn)的需針域，抿滋下面國(guó)效/

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

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