2、所有試題的答案寫在答題紙上。
一、判斷下列敘述的對錯。
�。�1）線性表的邏輯順序與物理順序總是一致的。
（2）線性表的順序存儲表示優(yōu)于鏈式存儲表示。
�。�3）線性表若采用鏈式存儲表示時所有結點之間的存儲單元地址可連續(xù)可不連續(xù)。
�。�4）二維數(shù)組是其數(shù)組元素為線性表的線性表。
（5）每種數(shù)據(jù)結構都應具備三種基本運算：插入、刪除和搜索。
二、設單鏈表中結點的結構為
typedef struct node { file://鏈表結點定義
ElemType data； file://數(shù)據(jù)
struct node * Link； file://結點后繼指針
} ListNode；
（1）已知指針p所指結點不是尾結點，若在*p之后插入結點*s，則應執(zhí)行下列哪一個操作？
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）非空的循環(huán)單鏈表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），所有邊鏈表中邊結點的總數(shù)為（B）。
�。�2）采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于樹的（C）。
�。�3）采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于樹的（D）。
�。�4）判斷有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用（E）。
供選擇的答案
A：①n②n+1③n-1④n+e
B：①e/2②e③2e④n+e
C~D：①中根遍歷②先根遍歷③后根遍歷④按層次遍歷
E：①求關鍵路徑的方法②求最短路徑的Dijkstra方法
�、凵疃葍�(yōu)先遍歷算法④廣度優(yōu)先遍歷算法
六、填空題
�。�1）在用于表示有向圖的鄰接矩陣中，對第i行的元素進行累加，可得到第i個頂點的（①）度，而對第j列的元素進行累加，可得到第j個頂點的（②）度。
�。�2）一個連通圖的生成樹是該圖的（③）連通子圖。若這個連通圖有n個頂點，則它的生成樹有（④）條邊。
（3）給定序列{100， 86， 48， 73， 35， 39， 42， 57， 66， 21}，按堆結構的定義，則它一定（⑤）堆。
�。�4）在進行直接插入排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（⑥）關；而在進行直接選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（⑦）關。
�。�5）利用關鍵碼分別為10， 20， 30， 40的四個結點，能構造出（⑧）種不同的二叉搜索樹。
