1、除第九題外，其他各題每題10分，第九題20分。
2、所有試題的答案寫在答題紙上。
一、判斷下列敘述的對錯。
(1) 線性表的邏輯順序與物理順序總是一致的。
(2) 線性表的順序存儲表示優(yōu)于鏈式存儲表示。
(3) 線性表若采用鏈式存儲表示時所有結點之間的存儲單元地址可連續(xù)可不連續(xù)。
(4) 二維數(shù)組是其數(shù)組元素為線性表的線性表。
(5) 每種數(shù)據(jù)結構都應具備三種基本運算：插入、刪除和搜索。
二、設單鏈表中結點的結構為
typedef struct node { //鏈表結點定義
ElemType data; //數(shù)據(jù)
struct node * Link; //結點后繼指針
} 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的四個結點，能構造出（ ⑧ ）種不同的二叉搜索樹。
七、設帶表頭結點的雙向鏈表的定義為
typedef int ElemType;
typedef struct dnode { //雙向鏈表結點定義
ElemType data; //數(shù)據(jù)
struct dnode * lLink, * rLink; //結點前驅與后繼指針
} DblNode;
typedef DblNode * DblList; //雙向鏈表
試設計一個算法，改造一個帶表頭結點的雙向鏈表，所有結點的原有次序保持在各個結點的右鏈域rLink中，并利用左鏈域lLink把所有結點按照其值從小到大的順序連接起來。
八、設有一個關鍵碼的輸入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 },
(1) 從空樹開始構造平衡二叉搜索樹, 畫出每加入一個新結點時二叉樹的形態(tài)。若發(fā)生不平衡, 指明需做的平衡旋轉的類型及平衡旋轉的結果。
(2) 計算該平衡二叉搜索樹在等概率下的查找成功的平均查找長度和查找不成功的平均查找長度。
九、下面是求連通網(wǎng)絡的最小生成樹的Prim算法的實現(xiàn)，中間有5個地方缺失，請閱讀程序后將它們補上。
const int MaxInt = INT_MAX; //INT_MAX的值在中
const int n = 6; //圖的頂點數(shù), 應由用戶定義
typedef int AdjMatrix[n>[n>; //用二維數(shù)組作為鄰接矩陣表示
typedef struct { //生成樹的邊結點
int fromVex, toVex; //邊的起點與終點
int weight; //邊上的權值
} TreeEdgeNode;
typedef TreeEdgeNode MST[n-1>; //最小生成樹定義
void PrimMST ( AdjMatrix G, MST T, int rt ) {
//從頂點rt出發(fā)構造圖G的最小生成樹T，rt成為樹的根結點
TreeEdgeNode e; int i, k = 0, min, minpos, v;
for ( i = 0; i < n; i++ ) //初始化最小生成樹T
if ( i != rt ) {
T[k>.fromVex = rt;
T[k>.toVex = I ;
T[k++>.weight = G[rt>;
}
for ( k = 0; k < n-1; k++ ) { //依次求MST的候選邊
min = MaxInt ;
for ( i = k; i < n-1; i++ ) //遍歷當前候選邊集合
if ( T.weight < min ) //選具有最小權值的候選邊
{ min = T.weight; minpos = i ; }
if ( min == MaxInt ) //圖不連通, 出錯處理
{ 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++ ) //修改候選邊集合
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. ③
六、① 出 ② 入 ③ 極小 ④ n-1
⑤ 是（最?。?⑥ 有 ⑦ 無 ⑧ 14
七、算法如下
void sort ( DblNode * L ) {
DblNode * s = L->rlink;
//指針s指向待插入結點, 初始時指向第一個結點
while ( s != NULL ) { //處理所有結點
pre = L; p = L->lLink;
//指針p指向待比較的結點, pre是p的前驅指針
while ( p != NULL && s->data < p->data )
//循lLink鏈尋找結點 *s的插入位置
{ pre = p; p = p->lLink; }
pre->lLink = s; s->lLink = p; s = s->rLink;
//結點 *s在lLink方向插入到 *pre與 *p之間
}
八、關鍵碼的輸入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }
在等概率下查找成功的平均查找長度
在等概率下查找不成功的平均查找長度
九 ① T[k>.toVex = i
② min = MaxInt
③ minpos = i
④ exit(1)
⑤ T.fromVex = v