資料結構試題及答案

《資料結構》自考複習思考試題

一、單選題：從選擇的答案中選出正確的答案，將其字母編號填入下列敘述中的括號內。（每小題 3分，共24分）

（1）向乙個有127個元素原順序表中插入乙個新元素並儲存原來順序不變，平均要移動（）個元素。

a、8 b、63.5 c、63 d、7

（2）設有乙個二維數a[m][n],假設a[0][0]存放位置在644(10),a[2][2]存放位置在676(10),每個元素佔乙個空間，則a[4][5]在（）位置，(10)表明用10進數表示。

a、692(10) b、626(10) c、709(10) d、724(10)

(3)乙個有序順表有255個物件，採用順序搜尋法查表，搜尋長度為（）。

a、128 b、127 c、126 d、255

（4）含5個結點（元素值均不相同）的二叉搜尋樹有（）種。

a、54 b、42 c、36 d、65

（5）在分析析半搜尋的效能時時常加入失敗結點，即外結點，從而形成擴充的二叉樹。若設失敗結點所在層次為,那麼搜尋失敗到達失敗點時所做的資料比較次數是（）。

a、li+1 b、li+2 c、li-1 d、li

（6）設有乙個含200個表項的雜湊表，用線性探查法解決衝突，按關鍵碼查詢時找到乙個表項的平均探查次數不超過1.5，則雜湊儲存空間應能夠至少容納（）個表項。（設搜尋成功的平均搜尋長度為snl=(n+1/(1-a))/2,其中a 為裝填因子）

a、400 b、526 c、624 d、676

（7）n 個頂點的連通圖至少有（）條邊。

a、n-1 b 、n c、n+1 d、0

(8)乙個二叉樹按順序方式儲存在乙個維陣列中，如圖

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

則結點e在二叉樹的第（）層。

a、1 b、2 c、3 d、4

二、閱讀理解題：說明下面遞迴過程的功能（10分）

int unknown (bintreenode * t) o;

elseif (tlefchild= =null&&trigihtchild= =null)return 1;

else return unknown (t

三、簡答題（每小題12分，共36分）

1、如下列所示的連通圖，請畫出

（1）以頂點①為根的深度優先生成樹；（6分）

（2）如果有關節點，請找出所有的關節點。（6分）

2、設有13個初始歸併段，其長度分別為28，16，37，42，5，9，13，14，20，17，30，12，18。試畫出4路歸併時的最佳歸併樹，並計算它的帶權路徑長度wpl。

3、設雜湊表ht[0..12],即表的大小為m=13。採用雙雜湊法解決衝突。雜湊函式和再雜湊函式分別為：

h0（key）=key% 13; 注：%是求餘數運算（=mod）

hi=(hi-1+rev(key+1)%11+1)%13;

ⅰ=1,2,3………,m-1

其中，函式rev(x)表示顛倒10進製數x的各位，如rev(37)=73, rev(7)=7等。若插入的關鍵碼序列為｛2，8，31，20，19，18，53，27｝試畫出插入這8個關鍵碼後的雜湊表。

0 1 2 3 4 5 6 7 8 9 10 11 12

四、（10分）

已知一棵樹二叉如下，請分別寫出按箭序、中序、後序和層次遍歷時得到的結點序列。abc

de f

gh前序：

中序：後序：

層次：五、綜合演算法題（10分）

有一種簡單的排序演算法，叫做計數排序（count sorting）。這種排序演算法對乙個待排序的表（用陣列表示）進行排序，並將排序結果放到另乙個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同。

計數排序演算法針對表中的每個記錄，掃瞄待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小。假設針對某乙個記錄，統計出的計數值為c,那麼，這個記錄在新的有序表中的合適的存放位置即為c。

（1）給出適用於計數排序的資料表定義；（4分）

（2）使用c++語言編寫實現計數排序的演算法；（4分

（3）對於有n個記錄的表，關鍵碼比較次數是多少？（2分）

六、程式填空題（10分）

下面給出的是乙個在二叉樹中查詢值為x的結點，並列印該結點所有祖先結點的演算法。在此演算法中，假設值為x的結點不多於乙個。此演算法採用後序的排序的非遞迴遍歷形式。

因退棧時需要區分右子樹。用棧st儲存結點指標ptr以及標誌tag。top是棧頂指標。

void print (bintreenode * t; typt&x)｛

stack st;int i,top;top=0; //置空棧

while(t!=null&&t!=x||top!=0 ｛while(t!=null&&tdata!=x) ｛

//尋找值為x的結點

st[top].ptr=t;

st[top].tag=0;

if (t!=null&&tdata= =x)//找到值為x的結點

for(i=1i++)

cout< else

}(1) 請將缺失的語句補上（共4分，每空 1分）12

34（2）請給出對於右圖所示的二叉樹，使用上述演算法搜尋值為9的結點和值為10 的結點的結果，以及在棧st中的變化。（top 是棧頂指標）（6分）

①⑨資料結構試題參***及評分標準

一、單選題（共24分，每空3分）

解答（1）b （2）c （3）a （4）b （5）d （6）a （7）a （8）b

二、閱讀理解題（10分）

解答計算二叉樹的葉結點的個數。

三、簡答題（每小題12分，共36分）

1 解答

（1）該連通圖從1出發深度優先搜尋，得到的深度優先生成樹為：（6分）

（２）　關節點為　①②③⑦⑧

２、　解答　：因為所以不需要新增空段，最佳歸併樹為：

5 9 13 12 16 14 17 18 28 37 20 30

3965115

261３　、解答

雜湊表雜湊函式與再雜湊函式為

插入關鍵碼序列為

ｈ０（２）＝２，比較次數為１

ｈ０（８）＝８，比較次數為１

ｈ０（３１）＝５，比較次數為１

ｈ０（２０）＝７，比較次數為１

ｈ０（１９）＝６，比較次數為１

ｈ０（１８）＝５，衝突，ｈ１＝９，比較次數為２

ｈ０（５３）＝１，比較次數為１

ｈ０（２７）＝１，衝突，ｈ１＝７，衝突，ｈ２＝０，比較次數為３

插入８個關鍵碼後的雜湊表

0 1 2 3 4 5 6 7 8 9 10 11 12

四、　各遍歷次序如下（１０分）

前序分）

中序分）

後序分）

層次分）

五、　綜合演算法題

（１）資料表定義（４分）

解答：const int defaultsize=100;

template class datalist;

template class element

void setkey (const type x)

}template class datalist

puevate:

element * vector ;

int maxsize,currentsize;

}（2）計數排序的演算法

解答１：

template

void countsort (datalist &initlist,datalist&resultlist){

資料結構試題及答案

資料結構試題及答案

資料結構試題及答案

資料結構試題及答案

相關推薦