二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）
請在每個空格中填上正確答案。錯填、不填均無分。
16．?dāng)?shù)據(jù)的鏈?zhǔn)酱鎯�結(jié)構(gòu)的特點是借助________表示數(shù)據(jù)元素之間的邏輯關(guān)系。
17．如果需要對線性表頻繁進(jìn)行________或________操作，則不宜采用順序存儲結(jié)構(gòu)。
18．如圖所示，可以利用一個向量空間同時實現(xiàn)兩個類型相同的棧。其中棧1為空的條件是top1=0，棧2為空的條件是top2=n-1，則“棧滿”的判定條件是________。

19．靜態(tài)存儲分配的順序串在進(jìn)行插入、置換和________等操作時可能發(fā)生越界。
20．廣義表L=（a，（b，( )））的深度為________。
21．任意一棵完全二叉樹中，度為1的結(jié)點數(shù)最多為________。
22．求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中________的數(shù)目正相關(guān)。
23．在5階B-樹中，每個結(jié)點至多含4個關(guān)鍵字，除根結(jié)點之外，其他結(jié)點至少含________個關(guān)鍵字。
24．若序列中關(guān)鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是________的。
25．常用的索引順序文件是________文件和________文件。

三、解答題(本大題共4小題，每小題5分，共20分)
26．如圖所示，在n×n矩陣A中，所有下標(biāo)值滿足關(guān)系式i+j＜n+l的元素a_ij的值均為0，現(xiàn)將A中其它元素按行優(yōu)先順序依次存儲到長度為n(n+1)/2的一維數(shù)組sa中，其中元素a_1，n存儲在sa［0］。
(1)設(shè)n=10，元素a_4，9存儲在sa［p］，寫出下標(biāo)p的值；
(2)設(shè)元素a_i，j存儲在sa［k］中，寫出由i,j和n計算k的一般公式。

27．由字符集{s，t，a，e，I}及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據(jù)該哈夫曼樹進(jìn)行譯碼，寫出原來的電文。

28．已知無向圖G的鄰接表如圖所示，
(1)畫出該無向圖；
(2)畫出該圖的廣度優(yōu)先生成森林。

29．對序列(48，37，63，96，22，31，50，55，11)進(jìn)行升序的堆排序，寫出構(gòu)建的初始(大根)堆及前兩趟重建堆之后的序列狀態(tài)。
初始堆：
第1趟：
第2趟：

四、算法閱讀題(本大題共4小題，每小題5分，共20分)
30．閱讀下列算法，并回答問題：

(1)無向圖G如圖所示，寫出算法
f30(&G)的返回值；
(2)簡述算法f30的功能。
#define MaxNum 20
int visited[MaxNum]；
void DFS(Graph *g，int i)；
　　/*從頂點vi出發(fā)進(jìn)行深度優(yōu)先搜索，訪問頂點vj時置visited[j]為1*/
int f30(Graph *g)
　　{ int i，k；
　　　for (i=0； in； i++)／*g->n為圖g的頂點數(shù)目*／
　　　　　visited[i]=0；
　　　for (i=k=0； in; i++)
　　　　　if (visited[i]= =0)
　　　　　　　{ k++；
　　　　　　　　DFS(g，i)；
　　　　　　　}
　　　return k；
　　}
31．假設(shè)學(xué)生成績按學(xué)號增序存儲在帶頭結(jié)點的單鏈表中，類型定義如下：
typedef struct Node {
　　int id; /*學(xué)號*/
　　int score； /*成績*/
　　struct Node *next；
　　} LNode， *LinkList；
閱讀算法f31，并回答問題：
(1)設(shè)結(jié)點結(jié)構(gòu)為，成績鏈表A和B如圖所示，畫出執(zhí)行算法
f31(A，B)后A所指的鏈表；

(2)簡述算法f31的功能。
void f31(LinkList A, LinkList B)
　　{ LinkList p, q;
　　　p=A->next;
　　　q=B->next;
　　　while (p && q)
　　　　　{ if (p->idid)
　　　　　　　　p=p->next;
　　　　　　else if (p->id>q->id)
　　　　　　　　q=q->next;
　　　　　　else
　　　　　　　　{ if (p->score<60)
　　　　　　　　　　if (q->score<60)
　　　　　　　　　　　　p->score=q->score;
　　　　　　　　　　else p->score=60;
　　　　　　　　　p=p->next;
　　　　　　　　　q=q->next;
　　　　　　　　}
　　　　　　}
　　}
32．閱讀下列算法，并回答問題：
(1)設(shè)串s=“OneWorldOneDream”，t=＂One＂，pos是一維整型數(shù)組，寫出算法
f32(s，t，pos)執(zhí)行之后得到的返回值和pos中的值；
(2)簡述算法f32的功能。
int strlen(char*s)； /*返回串s的長度*/
int index(char*st，char*t)；
　�。�*若串t在串st中出現(xiàn)，則返回在串st中首次出現(xiàn)的下標(biāo)值，否則返回-1*/
int f32(char*s, char*t, int pos［］)
　　{ int i, j, k, ls, lt;
　　　ls=strlen(s);
　　　1t=strlen(t);
　　　if (ls= =0||1t= =0) return-1;
　　　k=0;
　　　i=0;
　　　do {
　　　　　j=index(s+i, t);
　　　　　if (j>=0)
　　　　　　　{ pos［k++］=i+j;
　　　　　　　　i+=j+1t;
　　　　　　　}
　　　　　}while(i+1t<=1s && j >=0);
　　　return k;
　　}
33．二叉排序樹的存儲結(jié)構(gòu)定義為以下類型：
typedef int KeyType;
typedef struct node {
　　KeyType key; /*關(guān)鍵字項*/
　　InfoType otherinfo; /*其它數(shù)據(jù)項*/
　　struct node *1child, *rchild; /*左、右孩子指針*/
　　} BSTNode, *BSTree；
閱讀算法f33，并回答問題：

(1)對如圖所示的二叉排序樹T，寫出f33(T，8)
返回的指針?biāo)�指結(jié)點的關(guān)鍵字；
(2)在哪些情況下算法f33返回空指針?
(3)簡述算法f33的功能。
BSTNode *f33(BSTree T, KeyType x)
{ BSTNode *p;
　if (T= =NULL) return NULL;
　p=f33(T->1child, x);
　if (p!=NULL)return p;
　if (T->key>x)return T;
　return f33(T-> rchild, x);
}

五、算法設(shè)計題（本題10分）
34．假設(shè)線性表采用順序存儲結(jié)構(gòu)，其類型定義如下：
#define ListSize 100
typedef struct {
　　int data［ListSize］;
　　int length;
　　} SeqList, *Table;
編寫算法，將順序表L中所有值為奇數(shù)的元素調(diào)整到表的前端。