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

1、數(shù)據(jù)結(jié)構(gòu)與算法模擬題一、填空題：（共15分）（每空一分）1. 按照排序時(shí)，存放數(shù)據(jù)的設(shè)備，排序可分為<1> 內(nèi)部 排序和<2> 外部 排序。2. 圖的常用的兩種存儲(chǔ)結(jié)構(gòu)是<3> 鄰接矩陣 和<4> 鄰接表 。3. 數(shù)據(jù)結(jié)構(gòu)中的三種基本的結(jié)構(gòu)形式是<5> x線性結(jié)構(gòu) 和<6> 樹形結(jié)構(gòu) 、<7> 圖形結(jié)構(gòu) 。4. 一個(gè)高度為6的二元樹，最多有<8> 63 個(gè)結(jié)點(diǎn)。5. 線性查找的時(shí)間復(fù)雜度為：O(n) ，折半查找的時(shí)間復(fù)雜度為：O(nlogn) 、堆分類的時(shí)間復(fù)雜度為：O(nlogn) 。6. 在采用

2、散列法進(jìn)行查找時(shí)，為了減少?zèng)_突的機(jī)會(huì)，散列函數(shù)必須具有較好的隨機(jī)性，在我們介紹的幾種散列函數(shù)構(gòu)造法中，隨機(jī)性最好的是隨機(jī)數(shù)法 法、最簡單的構(gòu)造方法是除留余數(shù)法 。7. 線性表的三種存儲(chǔ)結(jié)構(gòu)是：數(shù)組、鏈表 、靜態(tài)鏈表 。二、回答下列問題：（共30分）1. 現(xiàn)有如右圖的樹，回答如下問題：A） 根結(jié)點(diǎn)有：6B） 葉結(jié)點(diǎn)有：5C） 具有作大度的結(jié)點(diǎn)：9和10D） 結(jié)點(diǎn)o的祖先是：0和2E） 結(jié)點(diǎn)o的后代是：102. 棧存放在數(shù)組Am中，棧底位置是m-1。試問：A） ?？盏臈l件是什么？top=m-1B） 棧滿的條件是什么？棧滿top=03. 數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)型的區(qū)別與聯(lián)系：數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種

3、或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)。抽象數(shù)據(jù)類型：是指一個(gè)數(shù)學(xué)模型（數(shù)據(jù)結(jié)構(gòu)）以及定義在該模型（數(shù)據(jù)結(jié)構(gòu)）上的一組操作。 4. 已知一株非空二元樹，其先根與中根遍歷的結(jié)果為：先根：ABCDEFGHI 中跟：CBEDAGFHI 將此二元樹構(gòu)造出來。5. 分析下列程序的運(yùn)行時(shí)間：A) void mystery(int n)int i, j, k; for(i=1; i<n; i+) for(j=i+1; j<=n; j+) for(k=1; k<=j; k+)some statement requiring O(1) time; 這個(gè)應(yīng)該是時(shí)間復(fù)雜度吧

4、 ： O(n3)B）void podd(int n) int I, 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; O（n2）6. 已知數(shù)學(xué)表達(dá)式是(3+b)sin(x+5)a/x2，求該表達(dá)式的波蘭表示法的前綴和后綴表示（要求給出過程）。我感覺它的前綴表示法為-*+3bSIN+x5*/ax0.5，后綴表示法為3b+x5+SIN*ax/0.5*-。 三、實(shí)現(xiàn)下列算法：（共0分）1. 在指針實(shí)現(xiàn)的線性表L中，實(shí)現(xiàn)在線性表L 中刪除關(guān)鍵字為x

5、的結(jié)點(diǎn)。(共7分)intdeleteValueList(structList*L,elemTypex) inti,j; /*從線性表中順序查找出值為x的第一個(gè)元素*/ for(i=0;i<L->size;i+) if(L->listi=x) break; /*若查找失敗，表明不存在值為x的元素，返回0*/ if(i=L->size) return0; /*刪除值為x的元素L->listi*/ for(j=i+1;j<L->size;j+) L->listj-1=L->listj; L->size-; return1;2. 設(shè)有如下圖的雙向環(huán)形鏈表L=(a, b, c, d) 。請(qǐng)寫出將該表轉(zhuǎn)換為L=(b, a, c, d)的簡單操作。（共7分）abcdLL D RLL abcdLL D RLL L->RL->RL = D->RL ; D->RL = L->RL; LàRL->LL->RL=D->LL; D->LL=L