《數(shù)據(jù)結(jié)構(gòu)與算法》模擬題

《數(shù)據(jù)結(jié)構(gòu)與算法》模擬題一、填空題：（共15分）（每空一分）按照排序時(shí)，存放數(shù)據(jù)的設(shè)備，排序可分為<1>內(nèi)部排序和<2>外部排序。圖的常用的兩種存儲結(jié)構(gòu)是<3>鄰接矩陣存儲和<4>鄰接表面存儲。數(shù)據(jù)結(jié)構(gòu)中的三種基本的結(jié)構(gòu)形式是<5>x線性結(jié)構(gòu)和<6>樹形結(jié)構(gòu)、<7>圖形結(jié)構(gòu)。一個(gè)高度為6的二元樹，最多有<8>63個(gè)結(jié)點(diǎn)。線性查找的時(shí)間復(fù)雜度為：<9>，折半查找的時(shí)間復(fù)雜度為：<10>、堆分類的時(shí)間復(fù)雜度為：<11>。在采用散列法進(jìn)行查找時(shí)，為了減少沖突的機(jī)會，散列函數(shù)必須具有較好的隨機(jī)性，在我們介紹的幾種散列函數(shù)構(gòu)造法中，隨機(jī)性最好的是<12>隨機(jī)數(shù)法、最簡單的構(gòu)造方法是<13>除留余數(shù)法。線性表的三種存儲結(jié)構(gòu)是：數(shù)組、<14>鏈表、<15>靜態(tài)鏈表。二、回答下列問題：（共30分）現(xiàn)有如右圖的樹，回答如下問題：根結(jié)點(diǎn)有：6葉結(jié)點(diǎn)有：5具有作大度的結(jié)點(diǎn)：9和10結(jié)點(diǎn)的祖先是：0和2結(jié)點(diǎn)的后代是：10棧存放在數(shù)組A[m]中，棧底位置是m-1。試問：?？盏臈l件是什么？棧滿的條件是什么？數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)型的區(qū)別與聯(lián)系：已知一株非空二元樹，其先根與中根遍歷的結(jié)果為：

先根：ABCDEFGHI

中跟：CBEDAGFHI將此二元樹構(gòu)造出來。分析下列程序的運(yùn)行時(shí)間：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;}}B）voidpodd(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á)式的波蘭表示法的前綴和后綴表示（要求給出過程）。

三、實(shí)現(xiàn)下列算法：（共３0分）在指針實(shí)現(xiàn)的線性表L中，實(shí)現(xiàn)在線性表L中刪除關(guān)鍵字為x的結(jié)點(diǎn)。(共7分)設(shè)有如下圖的雙向環(huán)形鏈表L=(a,b,c,d)。請寫出將該表轉(zhuǎn)換為L=(b,a,c,d)的簡單操作。（共7分）ababcdLLDRLL在線索二元樹中，由結(jié)點(diǎn)P求其先根順序的后繼。（共8分）先根：ABCDEFGHI

中跟：CBEDAGFHI

將此二元樹構(gòu)造出來。遍歷的基本方法：先左子樹后右子樹。1,先根遍歷可以確定根節(jié)點(diǎn)為A,2,依據(jù)1步，可以在中根遍歷中確定左子樹為：CBED,右為：GFHI3,在可以重復(fù)1,2步。就可以得到結(jié)果。ABFCDGHI4,O(n^3)+O(1)

在二元查找樹F中，實(shí)現(xiàn)插入記錄R。（共8分）

四、對下面的帶權(quán)連通無向圖，用Prim（普里姆）算法，構(gòu)造一株最小生成樹。畫出構(gòu)造過程的每一步。（12分）1