2、所有試題的答案寫在答題紙上。
一、判斷下列敘述的對錯。
（1）線性表的邏輯順序與物理順序總是一致的。
�。�2）線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎尽?/p>
�。�3）線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r所有結(jié)點(diǎn)之間的存儲單元地址可連續(xù)可不連續(xù)。
�。�4）二維數(shù)組是其數(shù)組元素為線性表的線性表。
�。�5）每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除和搜索。
二、設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為
typedef struct node { file://鏈表結(jié)點(diǎn)定義
ElemType data； file://數(shù)據(jù)
struct node * Link； file://結(jié)點(diǎn)后繼指針
} ListNode；
（1）已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(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的尾結(jié)點(diǎn)（由p所指向）滿足：
A. p->link == NULL；
B. p == NULL；
C. p->link == first；
D. p == first；
三、設(shè)有一個順序棧S，元素s1， s2， s3， s4， s5， s6依次進(jìn)棧，如果6個元素的出棧順序?yàn)閟2， s3， s4， s6， s5， s1，則順序棧的容量至少應(yīng)為多少？
四、一棵具有n個結(jié)點(diǎn)的理想平衡二叉樹（即除離根最遠(yuǎn)的最底層外其他各層都是滿的，最底層有若干結(jié)點(diǎn)）有多少層？若設(shè)根結(jié)點(diǎn)在第0層，則樹的高度h如何用n來表示（注意n可能為0）？
五、從供選擇的答案中選擇與下面有關(guān)圖的敘述中各括號相匹配的詞句，將其編號填入相應(yīng)的括號內(nèi)。
�。�1）對于一個具有n個結(jié)點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則頂點(diǎn)表的大小為（A），所有邊鏈表中邊結(jié)點(diǎn)的總數(shù)為（B）。
�。�2）采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于樹的（C）。
�。�3）采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于樹的（D）。
�。�4）判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ�，還可以利用（E）。
供選擇的答案
A：①n②n+1③n-1④n+e
B：①e/2②e③2e④n+e
C~D：①中根遍歷②先根遍歷③后根遍歷④按層次遍歷
E：①求關(guān)鍵路徑的方法②求最短路徑的Dijkstra方法
③深度優(yōu)先遍歷算法④廣度優(yōu)先遍歷算法
六、填空題
�。�1）在用于表示有向圖的鄰接矩陣中，對第i行的元素進(jìn)行累加，可得到第i個頂點(diǎn)的（①）度，而對第j列的元素進(jìn)行累加，可得到第j個頂點(diǎn)的（②）度。
�。�2）一個連通圖的生成樹是該圖的（③）連通子圖。若這個連通圖有n個頂點(diǎn)，則它的生成樹有（④）條邊。
�。�3）給定序列{100， 86， 48， 73， 35， 39， 42， 57， 66， 21}，按堆結(jié)構(gòu)的定義，則它一定（⑤）堆。
�。�4）在進(jìn)行直接插入排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（⑥）關(guān)；而在進(jìn)行直接選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（⑦）關(guān)。
�。�5）利用關(guān)鍵碼分別為10， 20， 30， 40的四個結(jié)點(diǎn)，能構(gòu)造出（⑧）種不同的二叉搜索樹。
