全國2014年4月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題
課程代碼：02331
請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。
選擇題部分
注意事項：
1.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。
2.每小題選出答案后，用2B鉛筆把答題紙上對應(yīng)題目的答案標(biāo)號涂黑。如需改動，用橡皮擦干凈后，再選涂其他答案標(biāo)號。不能答在試題卷上。
一、單項選擇題（本大題共15小題，每小題2分，共30分）
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。
1.與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)的概念是
A.棧 B.鏈表
C.順序表 D.二叉鏈表
2.順序表中有10個數(shù)據(jù)元素，若第一個元素的存儲地址是1000，則最后一個元素地址是1036，第5個元素的地址是
A．1010 B.1016
C.1018 D.1019
3.設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5、6依次入棧，得到的出棧序列是（2,4,3,6,5,1）,則棧的容量至少是
A.2 B.3
C.4 D..6
4.下列關(guān)于隊列的敘述中,錯誤的是
A.隊列是一種先進(jìn)先出的線性表
B.隊列是一種后進(jìn)后出的線性表
C.循環(huán)隊列中進(jìn)行出隊操作時要判斷隊列是否為空
D.在鏈隊列中進(jìn)行入隊操作時要判斷隊列是否為滿
5.對稀疏矩陣進(jìn)行壓縮存儲的目的是
A.便于運算 B.節(jié)省存儲空間
C.便于輸入輸出 D.降低時間復(fù)雜度
6.一棵二叉樹的第7層上最多含有的結(jié)點數(shù)為
A.14 B.64
C.127 D.128
7.下列選項為完全二叉樹的是
8.用鄰接表表示n個頂點e條邊的無向圖,其邊表結(jié)點的總數(shù)是
A. n×e B. e
C. 2e D. n+e
9.無向圖中所有頂點的度數(shù)之和與所有邊數(shù)之比是
A.1/2 B.1
C.2 D.4
10.采用鄰接矩陣存儲圖時,廣度優(yōu)先搜索遍歷算法的時間復(fù)雜度為
A. O（n） B. O（n+e）
C. O（n2） D. O（n3）
11.對序列（15,9,7,8,20,-1,4）進(jìn)行排序,若一趟排序后的結(jié)果為（-1,15,9,7,8,20,4）,則采用的排序方法是
A.歸并排序 B.快速排序
C.直接選擇排序 D.冒泡排序
12.比較次數(shù)與待排序列初始狀態(tài)無關(guān)的排序方法是
A.快速排序 B.冒泡排序
C.直接插入排序 D.直接選擇排序
13.查找較快,且插入和刪除操作也比較方便的查找方法是
A.分塊查找 B.二分查找
C.順序查找 D.折半查找
14.下列關(guān)于m階B樹的敘述中,錯誤的是
A.根結(jié)點至多有m棵子樹
B.所有葉子都在同一層次上
C.每個非根內(nèi)部結(jié)點至少有[m/2]棵子樹
D.結(jié)點內(nèi)部的關(guān)鍵字可以是無序的
15.在散列查找中處理沖突時,可以采用開放定址法。下列不是開放定址法的是
A.線性探查法 B.二次探查法
C.雙重散列法 D.拉鏈法
非選擇題部分
注意事項：
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上,不能答在試題卷上。
二、填空題（本大題共10小題,每小題2分,共20分）
16.數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、________和數(shù)據(jù)的運算。
17.頭指針為L的帶頭結(jié)點的雙循環(huán)鏈表,結(jié)點的前趨指針域為prior,后繼指針域為next,判斷該鏈表為空的條件是________。
18.普里姆（Prim）算法完成的功能是求圖的________。
19.若三維數(shù)組a［4］［5］［6］的基地址是100,每個元素占用2個存儲單元,則數(shù)組a中最后一個元素的存儲地址是________。
20.二叉樹的線索鏈表利用________存放遍歷時得到的前趨或后繼結(jié)點的指針。
21.采用鄰接矩陣存儲n個頂點e條邊的無向圖,其鄰接矩陣的大小為________。
22.若無向圖中任意兩個不同的頂點間都有路徑,則稱該圖為________。
23.在直接插入排序、冒泡排序和快速排序中,平均時間性能最佳的是________。
24.假設(shè)m個關(guān)鍵字互為同義詞,若用線性探查法把這m個關(guān)鍵字存入散列表中,至少要進(jìn)行的探查次數(shù)是________。
25.順序查找算法的平均時間復(fù)雜度為________。
三、解答題（本大題共4小題,每小題5分,共20分）
26.用X代表進(jìn)棧操作,S代表出棧操作。給出利用棧將字符串"a*b-c"改變?yōu)?ab*c-"的操作步驟。例如：將"ABC"改變?yōu)?BCA",則其操作步驟為XXSXSS。
27.假定電文字符集為{A,B,C,D,E,F,G,H},它們在電文中出現(xiàn)的次數(shù)分別為{19,6,12,5,38,3,13,4）,為這8個字符設(shè)計哈夫曼編碼。畫出哈夫曼樹并給出編碼。要求在構(gòu)造哈夫曼樹的過程中,權(quán)值較小結(jié)點放在左側(cè),編碼時左分支生成代碼0,右分支生成代碼1。
28.設(shè)圖以鄰接表存儲,如題28圖所示。
（1）寫出從頂點v1出發(fā)圖的深度優(yōu)先搜索遍歷序列。
（2）寫出從頂點v1出發(fā)圖的廣度優(yōu)先搜索遍歷序列。
29.（1）一個排序方法穩(wěn)定的含義是什么？
（2）快速排序是穩(wěn)定的嗎？舉例說明。
四、算法閱讀題（本大題共4小題,每小題5分,共20分）
30.閱讀下列算法,并回答問題：
void f30（SeqStack S）
{ int k=0；
CirQueue Q；
SeqStack T；
InitQueue（&Q）； //初始化隊列Q
InitStack（&T）； //初始化棧T
while （!StackEmpty（&S））
{ k++;
if （k%2!=0） Push（&T, Pop（&S））;
else EnQueue（&Q, Pop（&S））;
} //第一個循環(huán)
while （!QueueEmpty（&Q）） //第二個循環(huán)
Push（&S, DeQueue（&Q））;
while（!StackEmpty（&T）） //第三個循環(huán)
Push（&S,Pop（&T））；
}
設(shè)棧S=（1,2,3,4,5,6,7）,其中7為棧頂元素。調(diào)用函數(shù)f30（S）后,
（1）第一個循環(huán)結(jié)束后,棧T和隊列Q中的內(nèi)容各是什么？
（2）第三個循環(huán)語句結(jié)束后,棧S中的內(nèi)容是什么？
31.二叉樹的二叉鏈表類型定義如下：
typedef struct node {
DataType data；
struct node *lchild, *rchild;
} BinNode;
typedef BinNode *BinTree；
閱讀下列算法,并回答問題：
void f31（BinTree BT）
{ BinNode *s;
if （BT）
{ s=BT->lchild；
BT->lchild=BT->rchild;
BT->rchild=s；
f31（BT->lchild）；
f31（BT->rchild）；
}
}
（1）該算法的功能是什么？
（2）以下算法功能是否等價于上面的算法？
void f3la（BinTree BT）
{ BinNode *s;
if（BT）
{ f31a（BT->lchild）；
f31a（BT->rchild）；
s=BT->lchild;
BT->lchild=BT->rchild;
BT->rchild=s；
}
}
32.單鏈表類型定義如下：
typedef struct node {
int data;
struct node *next;
} ListNode;
typedef ListNode *LinkList;
用不帶頭結(jié)點的單鏈表存儲待排數(shù)據(jù),鏈表頭指針為head。下列直接選擇排序算法對鏈表按升序進(jìn)行排序,請在答題紙相應(yīng)位置填寫適當(dāng)內(nèi)容使算法完整。
void f32（LinkList head）
{ ListNode *p, *q, *r;
int tmp;
p=head;
while（p）
{ q=p；
r=->next;
while（ (1) ）
{ if（ (2) ） q=r；
r=r->next;
}
tmp=q->data;
q->data=p->data;
p->data=tmp;
p= (3) ；
}
}
33.實現(xiàn)二分查找的遞歸章法如下,在答題紙相應(yīng)位置填寫適當(dāng)?shù)膬?nèi)容使算法完整。
typedef struct{
KeyType key;
InfoType otherinfo;
}NodeType;
typedef NodeType SeqList［n+l］;
int f33（SeqList R, int low, int high, KeyType K）
{ int mid;
if（low>high）
return 0；
mid= （1） ；
if（R［mid］.key==K）
return （2） ；
if（R［mid］.key<K）
f33（R, mid+l, high, K）；
else
(3) ；
}
五、算法設(shè)計題（本題10分）
34.單鏈表類型定義如下：
typedef struct node {
int data;
struct node *next;
} ListNode;
typedef ListNode *LinkList;
設(shè)計算法在帶頭結(jié)點的單鏈表L中刪除數(shù)據(jù)值最小的結(jié)點（設(shè)鏈表中各結(jié)點數(shù)據(jù)值
均不相同）。函數(shù)的原型為：void f34（LinkList L）
