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

一、判斷下列敘述的對錯。
(1) 線性表的邏輯順序與物理順序總是一致的。
(2) 線性表的順序存儲表示優(yōu)于鏈式存儲表示。
(3) 線性表若采用鏈式存儲表示時所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。
(4) 二維數(shù)組是其數(shù)組元素為線性表的線性表。
(5) 每種數(shù)據(jù)結(jié)構(gòu)都應具備三種基本運算：插入、刪除和搜索。


二、設單鏈表中結(jié)點的結(jié)構(gòu)為
typedef struct node { //鏈表結(jié)點定義
ElemType data; //數(shù)據(jù)
struct node * Link; //結(jié)點后繼指針
} ListNode;
(1) 已知指針p所指結(jié)點不是尾結(jié)點，若在*p之后插入結(jié)點*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的尾結(jié)點（由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個結(jié)點的理想平衡二叉樹（即除離根比較遠的比較底層外其他各層都是滿的，比較底層有若干結(jié)點）有多少層？若設根結(jié)點在第0層，則樹的高度h如何用n來表示（注意n可能為0）？


五、從供選擇的答案中選擇與下面有關圖的敘述中各括號相匹配的詞句，將其編號填入相應的括號內(nèi)。
(1) 對于一個具有n個結(jié)點和e條邊的無向圖，若采用鄰接表表示，則頂點表的大小為（ A ），所有邊鏈表中邊結(jié)點的總數(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}, 按堆結(jié)構(gòu)的定義, 則它一定( ⑤ )堆。
(4) 在進行直接插入排序時, 其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（ ⑥ ）關；而在進行直接選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（ ⑦ ）關。
(5) 利用關鍵碼分別為10, 20, 30, 40的四個結(jié)點，能構(gòu)造出（ ⑧ ）種不同的二叉搜索樹。


七、設帶表頭結(jié)點的雙向鏈表的定義為
typedef int ElemType;

typedef struct dnode { //雙向鏈表結(jié)點定義
ElemType data; //數(shù)據(jù)
struct dnode * lLink, * rLink; //結(jié)點前驅(qū)與后繼指針
} DblNode;

typedef DblNode * DblList; //雙向鏈表
試設計一個算法，改造一個帶表頭結(jié)點的雙向鏈表，所有結(jié)點的原有次序保持在各個結(jié)點的右鏈域rLink中，并利用左鏈域lLink把所有結(jié)點按照其值從小到大的順序連接起來。

八、設有一個關鍵碼的輸入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 },
(1) 從空樹開始構(gòu)造平衡二叉搜索樹, 畫出每加入一個新結(jié)點時二叉樹的形態(tài)。若發(fā)生不平衡, 指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。
(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 { //生成樹的邊結(jié)點
int fromVex, toVex; //邊的起點與終點
int weight; //邊上的權(quán)值
} TreeEdgeNode;
typedef TreeEdgeNode MST[n-1>; //比較小生成樹定義

void PrimMST ( AdjMatrix G, MST T, int rt ) {
//從頂點rt出發(fā)構(gòu)造圖G的比較小生成樹T，rt成為樹的根結(jié)點
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 ) //選具有比較小權(quán)值的候選邊
{ 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指向待插入結(jié)點, 初始時指向第一個結(jié)點
while ( s != NULL ) { //處理所有結(jié)點
pre = L; p = L->lLink;
//指針p指向待比較的結(jié)點, pre是p的前驅(qū)指針
while ( p != NULL && s->data < p->data )
//循lLink鏈尋找結(jié)點 *s的插入位置
{ pre = p; p = p->lLink; }
pre->lLink = s; s->lLink = p; s = s->rLink;
//結(jié)點 *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