華中科技大學(xué)2007年數(shù)據(jù)結(jié)構(gòu)與算法分析考研真題免費(fèi)下載

二OO七年招收碩士研究生入學(xué)考試自命題試題考試科目：數(shù)據(jù)結(jié)構(gòu)耳算法分析適用專業(yè):軟件工程 —(陰畫圖題外F所有答案都必須寫在管題紙上?寫在試廳紙上及棘旣上無效,考宗后試甌隨答題紙交回)術(shù)語解釋(25分)最小生成樹z.L-."■...-、、哈?！霰淼难b填因子滿二叉樹中序遍歷抽象數(shù)據(jù)類型單項(xiàng)選擇題〔25分)1-中綴表達(dá)式氏+M(葉d)+(肝g)*h的后綴表達(dá)式是〔 )A)ab+cd+*^+h* B)abcd++4fg-t-h*4-C)abcd*+^+h+* D)abcd*-rfg+h*-l-迴泡排序時(shí)間復(fù)雜程度是( )A.)0(N) B)0(NZogN)C)0(N2) D)0(N2；ogN)試卷編気眄華中科技大學(xué)試題紙TOC\o"1-5"\h\z—棵二叉樹的中序颯歷輸出是DBHEAFICG,先序遍歷輸出是ABDEHCFIG,那么其后序適歷輸出是( )A)DIHEBFGCA B)DHB1FEGCAC)DHEIFGBCA D)DHEB1FGCA4.樹葉數(shù)目為28的一棵二叉排序樹的深度最少是( )B)5D)7A)B)5D)75.C)5.A)已知在一個(gè)堆棧中的輸入順序?yàn)锳/Cd貝懷可能的輸出順序是()「?? ?A)ABGD??B)D,C,BAC)A,C3D3 D)CAB,D??簡答題(60分)將圖中的二叉樹用孩子鏈表來表示廠畫出孩子鏈表。N用Dijkstra算法求一個(gè)用下列鄰接矩陣表示的圖中從節(jié)點(diǎn)％至其余各節(jié)點(diǎn)的最短路徑，要求得到到各書點(diǎn)的D值并標(biāo)明求解過程…「?81050508g1180010020409.|18□0?COco3081188CO010g118000CO8501L?co000008」試卷編號皿少 華中科技大學(xué)試題紙

假定問題的規(guī)模為N時(shí)，某算法的事件復(fù)雜程度記為T(N)。己知T(l)=1,T(N)=T(N/2)+N。求出用0表示該算法的吋間復(fù)雜程度。寫出對順序表直接插入排序的算法。對數(shù)組{6,5,4,3,2,1}執(zhí)行該算法，列出宜接插入排序的過程。哈希函數(shù)的形式是H(key)=keyMOD7。已知心組關(guān)鍵字為{11,22,33,44,55,66,77.88,99,llh222r333},用鏈地址法處理沖究■畫出長度為7的哈希表。如果將哈希函數(shù)改為，H(key)=(key/100+(key/10-(key/100)*10)+(key-(key/10)*10))MOD7,即key的百位.十位與個(gè)位數(shù)字之和模除7,畫出用鏈地址法處理沖突構(gòu)造的長度為了的哈希表。應(yīng)用編程題(40分)A是一個(gè)長度為N的整型數(shù)組，其中可能包含重復(fù)的元素.例如A={1,2.23,2,1,3,2],刪除數(shù)組中相同的元素后得到{123"如果數(shù)組沒有排序，寫一個(gè)C語言函數(shù)，輸入?yún)?shù)為數(shù)紐首地址和長度.刪除其中重復(fù)的元索，返回刪除后數(shù)組的長度。占述簡數(shù)的時(shí)間復(fù)雜程度是多少，以刪除前的數(shù)組長度N表7J\o如果數(shù)組A已經(jīng)羽匸好序.設(shè)計(jì)并寫出一個(gè)C語言函數(shù)完成對中的工作，要求時(shí)間復(fù)雜程度是o(N)。寫一個(gè)C語言函數(shù)將…棵二叉樹用層序遍刃列出所有節(jié)點(diǎn)，即先列出根節(jié)點(diǎn).再從左向右列出深度為I的節(jié)點(diǎn)的值，然后再左向右列列出深度為2的節(jié)點(diǎn)的值?如此繼續(xù)。樹的節(jié)點(diǎn)類型TREENODE包含一個(gè)整型值Value和兩個(gè)指針：LcftChild和RightChild。可以使用的函數(shù)(不限于)包括MakcEmptyQueue(QUEUEEnQueue(QUEUE*q?TREENODE*tn)?DeQue