數(shù)據(jù)結構和算法模擬題

...WORD文檔下載可編輯.專業(yè)資料整理分享《數(shù)據(jù)結構與算法》模擬題一、填空題：〔共15分〔每空一分按照排序時,存放數(shù)據(jù)的設備,排序可分為<1>內部排序和<2>外部排序。圖的常用的兩種存儲結構是<3>鄰接矩陣存儲和<4>鄰接表面存儲。數(shù)據(jù)結構中的三種基本的結構形式是<5>x線性結構和<6>樹形結構、<7>圖形結構。一個高度為6的二元樹,最多有<8>63個結點。線性查找的時間復雜度為：<9>,折半查找的時間復雜度為：<10>、堆分類的時間復雜度為：<11>。在采用散列法進行查找時,為了減少沖突的機會,散列函數(shù)必須具有較好的隨機性,在我們介紹的幾種散列函數(shù)構造法中,隨機性最好的是<12>隨機數(shù)法、最簡單的構造方法是<13>除留余數(shù)法。線性表的三種存儲結構是：數(shù)組、<14>鏈表、<15>靜態(tài)鏈表。二、回答下列問題：〔共30分現(xiàn)有如右圖的樹,回答如下問題：根結點有：6葉結點有：5具有作大度的結點：9和10結點的祖先是：0和2結點的后代是：10棧存放在數(shù)組A[m]中,棧底位置是m-1。試問：棧空的條件是什么？棧滿的條件是什么？數(shù)據(jù)結構和抽象數(shù)據(jù)型的區(qū)別與聯(lián)系：已知一株非空二元樹,其先根與中根遍歷的結果為：先根：ABCDEFGHI中跟：CBEDAGFHI將此二元樹構造出來。分析下列程序的運行時間：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ù)學表達式是<3+b>sin<x+5>—a/x2,求該表達式的波蘭表示法的前綴和后綴表示〔要求給出過程。三、實現(xiàn)下列算法：〔共３0分在指針實現(xiàn)的線性表L中,實現(xiàn)在線性表L中刪除關鍵字為x的結點。<共7分>設有如下圖的雙向環(huán)形鏈表L=<a,b,c,d>。請寫出將該表轉換為L=<b,a,c,d>的簡單操作?！补?分ababcdLLDRLL在線索二元樹中,由結點P求其先根順序的后繼?！补?分先根：ABCDEFGHI

中跟：CBEDAGFHI

將此二元樹構造出來。遍歷的基本方法：先左子樹后右子樹。1,先根遍歷可以確定根節(jié)點為A,2,依據(jù)1步,可以在中根遍歷中確定左子樹為：CBED,右為：GFHI3,在可以重復1,2步。就可以得到結果。ABFCDGHI4,O<n^3>+O<1>在二元查找樹F中,實現(xiàn)插入記錄R?！补?分四、對下面的帶權連通無向圖,用Prim〔普里姆算法,構造一株最小生成樹。畫出構造過程的每一步?！?2分