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