2、所有試題的答案寫(xiě)在答題紙上。
一、判斷下列敘述的對錯。
?。?）線(xiàn)性表的邏輯順序與物理順序總是一致的。
?。?）線(xiàn)性表的順序存儲表示優(yōu)于鏈式存儲表示。
?。?）線(xiàn)性表若采用鏈式存儲表示時(shí)所有結點(diǎn)之間的存儲單元地址可連續可不連續。
?。?）二維數組是其數組元素為線(xiàn)性表的線(xiàn)性表。
?。?）每種數據結構都應具備三種基本運算：插入、刪除和搜索。
二、設單鏈表中結點(diǎn)的結構為
typedef struct node { file://鏈表結點(diǎn)定義
ElemType data； file://數據
struct node * Link； file://結點(diǎn)后繼指針
} ListNode；
?。?）已知指針p所指結點(diǎn)不是尾結點(diǎn)，若在*p之后插入結點(diǎn)*s，則應執行下列哪一個(gè)操作？
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；
?。?）非空的循環(huán)單鏈表first的尾結點(diǎn)（由p所指向）滿(mǎn)足：
A. p->link == NULL；
B. p == NULL；
C. p->link == first；
D. p == first；
三、設有一個(gè)順序棧S，元素s1， s2， s3， s4， s5， s6依次進(jìn)棧，如果6個(gè)元素的出棧順序為s2， s3， s4， s6， s5， s1，則順序棧的容量至少應為多少？
四、一棵具有n個(gè)結點(diǎn)的理想平衡二叉樹(shù)（即除離根最遠的最底層外其他各層都是滿(mǎn)的，最底層有若干結點(diǎn)）有多少層？若設根結點(diǎn)在第0層，則樹(shù)的高度h如何用n來(lái)表示（注意n可能為0）？
五、從供選擇的答案中選擇與下面有關(guān)圖的敘述中各括號相匹配的詞句，將其編號填入相應的括號內。
?。?）對于一個(gè)具有n個(gè)結點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則頂點(diǎn)表的大小為（A），所有邊鏈表中邊結點(diǎn)的總數為（B）。
?。?）采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類(lèi)似于樹(shù)的（C）。
?。?）采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類(lèi)似于樹(shù)的（D）。
?。?）判斷有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用（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)先遍歷算法
六、填空題
?。?）在用于表示有向圖的鄰接矩陣中，對第i行的元素進(jìn)行累加，可得到第i個(gè)頂點(diǎn)的（①）度，而對第j列的元素進(jìn)行累加，可得到第j個(gè)頂點(diǎn)的（②）度。
?。?）一個(gè)連通圖的生成樹(shù)是該圖的（③）連通子圖。若這個(gè)連通圖有n個(gè)頂點(diǎn)，則它的生成樹(shù)有（④）條邊。
?。?）給定序列{100， 86， 48， 73， 35， 39， 42， 57， 66， 21}，按堆結構的定義，則它一定（⑤）堆。
?。?）在進(jìn)行直接插入排序時(shí)，其數據比較次數與數據的初始排列（⑥）關(guān)；而在進(jìn)行直接選擇排序時(shí)，其數據比較次數與數據的初始排列（⑦）關(guān)。
?。?）利用關(guān)鍵碼分別為10， 20， 30， 40的四個(gè)結點(diǎn)，能構造出（⑧）種不同的二叉搜索樹(shù)。
七、設帶表頭結點(diǎn)的雙向鏈表的定義為
typedef int ElemType；
typedef struct dnode { file://雙向鏈表結點(diǎn)定義
ElemType data； file://數據
struct dnode * lLink， * rLink； file://結點(diǎn)前驅與后繼指針
DblNode；
typedef DblNode * DblList； file://雙向鏈表
試設計一個(gè)算法，改造一個(gè)帶表頭結點(diǎn)的雙向鏈表，所有結點(diǎn)的原有次序保持在各個(gè)結點(diǎn)的右鏈域rLink中，并利用左鏈域lLink把所有結點(diǎn)按照其值從小到大的順序連接起來(lái)。
八、設有一個(gè)關(guān)鍵碼的輸入序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07 ，
?。?）從空樹(shù)開(kāi)始構造平衡二叉搜索樹(shù)，畫(huà)出每加入一個(gè)新結點(diǎn)時(shí)二叉樹(shù)的形態(tài)。若發(fā)生不平衡，指明需做的平衡旋轉的類(lèi)型及平衡旋轉的結果。
?。?）計算該平衡二叉搜索樹(shù)在等概率下的查找成功的平均查找長(cháng)度和查找不成功的平均查找長(cháng)度。
九、下面是求連通網(wǎng)絡(luò )的最小生成樹(shù)的Prim算法的實(shí)現，中間有5個(gè)地方缺失，請閱讀程序后將它們補上。
const int MaxInt = INT_MAX； file://INT_MAX的值在中
const int n = 6； file://圖的頂點(diǎn)數，應由用戶(hù)定義
typedef int AdjMatrix[n>[n>； file://用二維數組作為鄰接矩陣表示
typedef struct file://生成樹(shù)的邊結點(diǎn)
int fromVex， toVex； file://邊的起點(diǎn)與終點(diǎn)
int weight； file://邊上的權值
TreeEdgeNode；
typedef TreeEdgeNode MST[n-1>； file://最小生成樹(shù)定義
void PrimMST （ AdjMatrix G， MST T， int rt ） {
file://從頂點(diǎn)rt出發(fā)構造圖G的最小生成樹(shù)T，rt成為樹(shù)的根結點(diǎn)
TreeEdgeNode e； int i， k = 0， min， minpos， v；
for （ i = 0； i < n； i++ ） file://初始化最小生成樹(shù)T
if （ i ！= rt ） {
T[k>.fromVex = rt；
T[k>.toVex = I ；
T[k++>.weight = G[rt>；
}
for （ k = 0； k < n-1； k++ ） { file://依次求MST的候選邊
min = MaxInt ；
for （ i = k； i < n-1； i++ ） file://遍歷當前候選邊集合
if （ T.weight < min ） file://選具有最小權值的候選邊
{ min = T.weight； minpos = i ； }
if （ min == MaxInt ） file://圖不連通，出錯處理
{ cerr 《“Graph is disconnected！”《 endl； exit（1） ； }
e = T[minpos>； T[minpos> = T[k> ； T[k> = e；
v = T[k>.toVex；
for （ i = k+1； i < n-1； i++ ） file://修改候選邊集合
if （ G[v>[T.toVex> < T.weight ）
T.weight = G[v>[T.toVex>；
T.fromVex = v ；
參考答案
一、（1）錯（2）錯（3）對（4）錯（5）對
二、（1） B （2） C
三、3
四、h =élog2（n+1）ù-1
五、A.①B.③C.②D.④E.③
六、①出②入③極?、躰-1
?、菔牵ㄗ钚。抻孝邿o(wú)⑧14
七、算法如下
void sort （ DblNode * L ） {
DblNode * s = L->rlink；
file://指針s指向待插入結點(diǎn)，初始時(shí)指向第一個(gè)結點(diǎn)
while （ s ！= NULL ） { file://處理所有結點(diǎn)
pre = L； p = L->lLink；
file://指針p指向待比較的結點(diǎn)， pre是p的前驅指針
while （ p ！= NULL && s->data < p->data ）
file://循lLink鏈尋找結點(diǎn)*s的插入位置
{ pre = p； p = p->lLink； }
pre->lLink = s； s->lLink = p； s = s->rLink；
file://結點(diǎn)*s在lLink方向插入到*pre與*p之間
}
八、關(guān)鍵碼的輸入序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07 }
在等概率下查找成功的平均查找長(cháng)度
在等概率下查找不成功的平均查找長(cháng)度
九
?、賂[k>.toVex = i
?、趍in = MaxInt
?、踡inpos = i
?、躤xit（1）
?、軹.fromVex = v
聯(lián)系客服
