哈工大數(shù)據(jù)結(jié)構(gòu)和算法模擬題

...WORD文檔下載可編輯.專業(yè)資料整理分享《數(shù)據(jù)結(jié)構(gòu)與算法》模擬題一、填空題：〔共15分〔每空一分按照排序時,存放數(shù)據(jù)的設(shè)備,排序可分為<1>排序和<2>排序。圖的常用的兩種存儲結(jié)構(gòu)是<3>和<4>。數(shù)據(jù)結(jié)構(gòu)中的三種基本的結(jié)構(gòu)形式是<5>和<6>、<7>。一個高度為6的二元樹,最多有<8>個結(jié)點。線性查找的時間復(fù)雜度為：<9>,折半查找的時間復(fù)雜度為：<10>、堆分類的時間復(fù)雜度為：<11>。在采用散列法進(jìn)行查找時,為了減少沖突的機(jī)會,散列函數(shù)必須具有較好的隨機(jī)性,在我們介紹的幾種散列函數(shù)構(gòu)造法中,隨機(jī)性最好的是<12>法、最簡單的構(gòu)造方法是<13>。線性表的三種存儲結(jié)構(gòu)是：數(shù)組、<14>、<15>。二、回答下列問題：〔共30分現(xiàn)有如右圖的樹,回答如下問題：根結(jié)點有：葉結(jié)點有：具有作大度的結(jié)點：結(jié)點的祖先是：結(jié)點的后代是：棧存放在數(shù)組A[m]中,棧底位置是m-1。試問：棧空的條件是什么？棧滿的條件是什么？數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)型的區(qū)別與聯(lián)系：已知一株非空二元樹,其先根與中根遍歷的結(jié)果為：先根：ABCDEFGHI中跟：CBEDAGFHI將此二元樹構(gòu)造出來。分析下列程序的運行時間：voidmystery<intn>{inti,j,k;for<i=1;i<n;i++>for<j=i+1;j<=n;j++>for<k=1;k<=j;k++>{somestatementrequiringO<1>time;}}Bvoidpodd<intn>{intI,j,x,y;for<I=1;I<=n;I++>if<odd<I>>{for<j=I;j<=n;j++>x=x+1;for<j=1;j<=I;j++>y=y+1;}}已知數(shù)學(xué)表達(dá)式是<3+b>sin<x+5>—a/x2,求該表達(dá)式的波蘭表示法的前綴和后綴表示〔要求給出過程。三、實現(xiàn)下列算法：〔共３0分在指針實現(xiàn)的線性表L中,實現(xiàn)在線性表L中刪除關(guān)鍵字為x的結(jié)點。<共7分>設(shè)有如下圖的雙向環(huán)形鏈表L=<a,b,c,d>。請寫出將該表轉(zhuǎn)換為L=<b,a,c,d>的簡單操作?！补?分ababcdLLDRLL在線索二元樹中,由結(jié)點P求其先根順序的后繼?！补?分在二元查找樹F中,實現(xiàn)插入記錄R?！补?分四、對下面的帶權(quán)連通無向圖,用Prim〔普里姆算法,構(gòu)造一株最小生成樹。畫出構(gòu)造過程的每一步?！?2分10281612222514