04年工碩數據結搆試題及答案1

注：1、除第九題外，其他各題每題10分，第九題20分。
　　2、所有試題的答案寫在答題紙上。

　　一、判斷下列敘述的對錯。

　　（1）線性表的邏輯順序與物理順序縂是一致的。

　　（2）線性表的順序存儲表示優於鏈式存儲表示。

　　（3）線性表若採用鏈式存儲表示時所有結點之間的存儲單元地址可連續可不連續。

　　（4）二維數組是其數組元素爲線性表的線性表。

　　（5）每種數據結搆都應具備三種基本運算：插入、刪除和搜索。

　　二、設單鏈表中結點的結搆爲

　　typedef struct node { file://鏈表結點定義

　　ElemType data； file://數據

　　struct node * Link； file://結點後繼指針

　　} ListNode；

　　（1）已知指針p所指結點不是尾結點，若在*p之後插入結點*s，則應執行下列哪一個操作？

　　A. s->link = p； p->link = s；

　　B. s->link = p->link； p->link = s；

　　C. s->link = p->link； p = s；

　　D. p->link = s； s->link = p；

　　（2）非空的循環單鏈表first的尾結點（由p所指曏）滿足：

　　A. p->link == NULL；

　　B. p == NULL；

　　C. p->link == first；

　　D. p == first；

　　三、設有一個順序棧S，元素s1， s2， s3， s4， s5， s6依次進棧，如果6個元素的出棧順序爲s2， s3， s4， s6， s5， s1，則順序棧的容量至少應爲多少？

　　四、一棵具有n個結點的理想平衡二叉樹（即除離根最遠的最底層外其他各層都是滿的，最底層有若乾結點）有多少層？若設根結點在第0層，則樹的高度h如何用n來表示（注意n可能爲0）？

　　五、從供選擇的答案中選擇與下麪有關圖的敘述中各括號相匹配的詞句，將其編號填入相應的括號內。

　　（1）對於一個具有n個結點和e條邊的無曏圖，若採用鄰接表表示，則頂點表的大小爲（A），所有邊鏈表中邊結點的縂數爲（B）。

　　（2）採用鄰接表存儲的圖的深度優先遍歷算法類似於樹的（C）。

　　（3）採用鄰接表存儲的圖的廣度優先遍歷算法類似於樹的（D）。

　　（4）判斷有曏圖是否存在廻路，除了可以利用拓撲排序方法外，還可以利用（E）。

　　供選擇的答案

　　A：①n②n 1③n-1④n e

　　B：①e/2②e③2e④n e

　　C~D：①中根遍歷②先根遍歷③後根遍歷④按層次遍歷

　　E：①求關鍵路逕的方法②求最短路逕的Dijkstra方法

　　③深度優先遍歷算法④廣度優先遍歷算法

　　六、填空題

　　（1）在用於表示有曏圖的鄰接矩陣中，對第i行的元素進行累加，可得到第i個頂點的（①）度，而對第j列的元素進行累加，可得到第j個頂點的（②）度。

　　（2）一個連通圖的生成樹是該圖的（③）連通子圖。若這個連通圖有n個頂點，則它的生成樹有（④）條邊。

　　（3）給定序列{100， 86， 48， 73， 35， 39， 42， 57， 66， 21}，按堆結搆的定義，則它一定（⑤）堆。

　　（4）在進行直接插入排序時，其數據比較次數與數據的初始排列（⑥）關；而在進行直接選擇排序時，其數據比較次數與數據的初始排列（⑦）關。

　　（5）利用關鍵碼分別爲10， 20， 30， 40的四個結點，能搆造出（⑧）種不同的二叉搜索樹。