全國2014年4月高等教育自學考試
數(shù)據(jù)結(jié)構(gòu)導論試題
課程代碼：02142
請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。
選擇題部分
注意事項：
1.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。
2.每小題選出答案后，用2B鉛筆把答題紙上對應題目的答案標號涂黑。如需改動，用橡皮擦干凈后，再選涂其他答案標號。不能答在試題卷上。
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應代碼涂黑。錯涂、多涂或未涂均無分。
1.下列幾種算法時間復雜度中，小的是
A.O(log2n) B.O(n)
C.O(n2) D.O(1)
2.數(shù)據(jù)的存儲方式中除了順序存儲方式和鏈式存儲方式之外，還有
A.索引存儲方式和樹形存儲方式 B.線性存儲方式和散列存儲方式
C.線性存儲方式和索引存儲方式 D.索引存儲方式和散列存儲方式
3.表長為n的順序表中做刪除運算的平均時間復雜度為
A.O(1) B.O(log2n)
C.O(n) D.O(n2)
4.順序表中定位算法(查找值為x的結(jié)點序號小值)的平均時間復雜度為
A.O(1) B.O(log2n)
C.O(n) D.O(n2)
5.元素的進棧次序為A，B，C，D，E，出棧的第一個元素為E，則第四個出棧的元素為
A.D B.C
C.B D.A
6.帶頭結(jié)點的鏈隊列中，隊列頭和隊列尾指針分別為front和rear，則判斷隊列空的條件為
A.front==rear B.front!=NULL
C.rear!==NULL D.front==NULL
7.深度為5的二叉樹，結(jié)點個數(shù)多為
A.31個 B.32個
C.63個 D.64個
8.如果結(jié)點A有2個兄弟結(jié)點，結(jié)點B為A的雙親，則B的度為
A.1 B.3
C.4 D.5
9.將題9圖所示的一棵樹轉(zhuǎn)換為二叉樹，結(jié)點C是
A.A的左孩子
B.A的右孩子
C.B的右孩子
D.E的右孩子
10.n為圖的頂點個數(shù)，e為圖中弧的數(shù)目，則圖的拓撲排序算法的時間復雜度為
A.O(n) B.O(e)
C.O(n-e) D.O(n+e)
11.無向圖的鄰接矩陣是
A.對角矩陣 B.稀疏矩陣
C.上三角矩陣 D.對稱矩陣
12.在具有101個元素的順序表中查找值為x的元素結(jié)點時，平均比較元素的次數(shù)為
A.50 B.51
C.100 D.101
13.構(gòu)造散列函數(shù)的方法很多，常用的構(gòu)造方法有
A.數(shù)字分析法、除留余數(shù)法、平方取中法
B.線性探測法、二次探測法、除留余數(shù)法
C.線性探測法、除留余數(shù)法、鏈地址法
D.線性探測法、二次探測法、鏈地址法
14.就平均時間性能而言，快速排序方法佳，其時間復雜度為
A.O(n) B.O(nlog2n)
C.O(n2) D.O(1og2n)
15.下述算法中，不穩(wěn)定的排序算法是
A.直接插入排序 B.冒泡排序
C.堆排序 D.歸并排序
非選擇題部分
注意事項：
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。
二、填空題(本大題共13小題，每小題2分，共26分)
16.數(shù)據(jù)的基本單位是_________。
17.雙向循環(huán)鏈表中，在p所指結(jié)點的后面插入一個新結(jié)點*t，需要修改四個指針，分別為
t->prior=P；t->next=p->next；_________；p->next=t；。
18.在帶有頭結(jié)點的循環(huán)鏈表中，尾指針為rear，判斷指針P所指結(jié)點為首結(jié)點的條件是_________。
19.若線性表中常用的操作是求表長和讀表元素，則順序表和鏈表這兩種存儲方式中，較節(jié)省時間的是_________。
20.不含任何數(shù)據(jù)元素的棧稱為_________。
21.稀疏矩陣一般采用的壓縮存儲方法是_________。
22.100個結(jié)點的二叉樹采用二叉鏈表存儲時，用來指向左、右孩子結(jié)點的指針域有_________個。
23.已知完全二叉樹的第5層有5個結(jié)點，則整個完全二叉樹有_________個結(jié)點。
24.n個頂點的有向圖G用鄰接矩陣A[1..n，1..n]存儲，其第i列的所有元素之和等于頂點
Vi的_________。
25.具有10個頂點的有向完全圖的弧數(shù)為_________。
26.要完全避免散列所產(chǎn)生的“堆積’’現(xiàn)象，通常采用_________解決沖突。
27.在長度為n的帶有崗哨的順序表中進行順序查找，查找不成功時，與關(guān)鍵字的比較次數(shù)為_________。
28.歸并排序算法的時間復雜度是_________。
三、應用題(本大題共5小題，每小題6分，共30分)
29.稀疏矩陣A如題29圖所示，寫出該稀疏矩陣A的三元組表示法。
30.設(shè)二叉樹的中序遍歷序列為BDCEAFHG，后序遍歷序列為DECBHGFA，試畫出該二叉樹。
31.寫出題31圖所示無向圖的鄰接矩陣，并寫出每個頂點的度。
題31圖
32.已知散列表的地址空間為0至13，散列函數(shù)H(k)=kmod11，(mod為求余運算)，待散列序列為(26，61，38，84，49)，用二次探測法解決沖突，構(gòu)造該序列的散列表，要求寫出處理沖突的過程。
33.將一組鍵值(80，50，65，13，86，35，96，57，39，79，59，15)應用二路歸并排序算法從小到大排序，試寫出各趟的結(jié)果。
四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)
34.設(shè)單鏈表及鏈棧S的結(jié)構(gòu)定義如下：
typedef struct node
{ Data Type data；
struct node*next；
｝linkstack；
編寫一個算法void ReverseList(1inkstack *head)，借助于棧S將帶頭結(jié)點單鏈表head中序號為奇數(shù)的結(jié)點逆置，序號為偶數(shù)的結(jié)點保持不變。(例如：單鏈表的邏輯結(jié)構(gòu)為(a1，a2，a3，a4，a5，a6)，逆置后變?yōu)?a5，a2，a3，a4，a1，a6))。
說明：棧的初始化運算用InitStack(S)；進棧運算用Push(S，x)；判?？者\算用EmptyStack(S)；出棧運算用Pop(S)；取棧頂元素運算用Gettop(S)。
35.以二叉鏈表作為存儲結(jié)構(gòu)，試編寫遞歸算法實現(xiàn)求二叉樹中葉子結(jié)點個數(shù)。
數(shù)據(jù)結(jié)構(gòu)導論試題
課程代碼：02142
請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。
選擇題部分
注意事項：
1.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。
2.每小題選出答案后，用2B鉛筆把答題紙上對應題目的答案標號涂黑。如需改動，用橡皮擦干凈后，再選涂其他答案標號。不能答在試題卷上。
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應代碼涂黑。錯涂、多涂或未涂均無分。
1.下列幾種算法時間復雜度中，小的是
A.O(log2n) B.O(n)
C.O(n2) D.O(1)
2.數(shù)據(jù)的存儲方式中除了順序存儲方式和鏈式存儲方式之外，還有
A.索引存儲方式和樹形存儲方式 B.線性存儲方式和散列存儲方式
C.線性存儲方式和索引存儲方式 D.索引存儲方式和散列存儲方式
3.表長為n的順序表中做刪除運算的平均時間復雜度為
A.O(1) B.O(log2n)
C.O(n) D.O(n2)
4.順序表中定位算法(查找值為x的結(jié)點序號小值)的平均時間復雜度為
A.O(1) B.O(log2n)
C.O(n) D.O(n2)
5.元素的進棧次序為A，B，C，D，E，出棧的第一個元素為E，則第四個出棧的元素為
A.D B.C
C.B D.A
6.帶頭結(jié)點的鏈隊列中，隊列頭和隊列尾指針分別為front和rear，則判斷隊列空的條件為
A.front==rear B.front!=NULL
C.rear!==NULL D.front==NULL
7.深度為5的二叉樹，結(jié)點個數(shù)多為
A.31個 B.32個
C.63個 D.64個
8.如果結(jié)點A有2個兄弟結(jié)點，結(jié)點B為A的雙親，則B的度為
A.1 B.3
C.4 D.5
9.將題9圖所示的一棵樹轉(zhuǎn)換為二叉樹，結(jié)點C是
A.A的左孩子
B.A的右孩子
C.B的右孩子
D.E的右孩子
10.n為圖的頂點個數(shù)，e為圖中弧的數(shù)目，則圖的拓撲排序算法的時間復雜度為
A.O(n) B.O(e)
C.O(n-e) D.O(n+e)
11.無向圖的鄰接矩陣是
A.對角矩陣 B.稀疏矩陣
C.上三角矩陣 D.對稱矩陣
12.在具有101個元素的順序表中查找值為x的元素結(jié)點時，平均比較元素的次數(shù)為
A.50 B.51
C.100 D.101
13.構(gòu)造散列函數(shù)的方法很多，常用的構(gòu)造方法有
A.數(shù)字分析法、除留余數(shù)法、平方取中法
B.線性探測法、二次探測法、除留余數(shù)法
C.線性探測法、除留余數(shù)法、鏈地址法
D.線性探測法、二次探測法、鏈地址法
14.就平均時間性能而言，快速排序方法佳，其時間復雜度為
A.O(n) B.O(nlog2n)
C.O(n2) D.O(1og2n)
15.下述算法中，不穩(wěn)定的排序算法是
A.直接插入排序 B.冒泡排序
C.堆排序 D.歸并排序
非選擇題部分
注意事項：
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。
二、填空題(本大題共13小題，每小題2分，共26分)
16.數(shù)據(jù)的基本單位是_________。
17.雙向循環(huán)鏈表中，在p所指結(jié)點的后面插入一個新結(jié)點*t，需要修改四個指針，分別為
t->prior=P；t->next=p->next；_________；p->next=t；。
18.在帶有頭結(jié)點的循環(huán)鏈表中，尾指針為rear，判斷指針P所指結(jié)點為首結(jié)點的條件是_________。
19.若線性表中常用的操作是求表長和讀表元素，則順序表和鏈表這兩種存儲方式中，較節(jié)省時間的是_________。
20.不含任何數(shù)據(jù)元素的棧稱為_________。
21.稀疏矩陣一般采用的壓縮存儲方法是_________。
22.100個結(jié)點的二叉樹采用二叉鏈表存儲時，用來指向左、右孩子結(jié)點的指針域有_________個。
23.已知完全二叉樹的第5層有5個結(jié)點，則整個完全二叉樹有_________個結(jié)點。
24.n個頂點的有向圖G用鄰接矩陣A[1..n，1..n]存儲，其第i列的所有元素之和等于頂點
Vi的_________。
25.具有10個頂點的有向完全圖的弧數(shù)為_________。
26.要完全避免散列所產(chǎn)生的“堆積’’現(xiàn)象，通常采用_________解決沖突。
27.在長度為n的帶有崗哨的順序表中進行順序查找，查找不成功時，與關(guān)鍵字的比較次數(shù)為_________。
28.歸并排序算法的時間復雜度是_________。
三、應用題(本大題共5小題，每小題6分，共30分)
29.稀疏矩陣A如題29圖所示，寫出該稀疏矩陣A的三元組表示法。
30.設(shè)二叉樹的中序遍歷序列為BDCEAFHG，后序遍歷序列為DECBHGFA，試畫出該二叉樹。
31.寫出題31圖所示無向圖的鄰接矩陣，并寫出每個頂點的度。
題31圖
32.已知散列表的地址空間為0至13，散列函數(shù)H(k)=kmod11，(mod為求余運算)，待散列序列為(26，61，38，84，49)，用二次探測法解決沖突，構(gòu)造該序列的散列表，要求寫出處理沖突的過程。
33.將一組鍵值(80，50，65，13，86，35，96，57，39，79，59，15)應用二路歸并排序算法從小到大排序，試寫出各趟的結(jié)果。
四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)
34.設(shè)單鏈表及鏈棧S的結(jié)構(gòu)定義如下：
typedef struct node
{ Data Type data；
struct node*next；
｝linkstack；
編寫一個算法void ReverseList(1inkstack *head)，借助于棧S將帶頭結(jié)點單鏈表head中序號為奇數(shù)的結(jié)點逆置，序號為偶數(shù)的結(jié)點保持不變。(例如：單鏈表的邏輯結(jié)構(gòu)為(a1，a2，a3，a4，a5，a6)，逆置后變?yōu)?a5，a2，a3，a4，a1，a6))。
說明：棧的初始化運算用InitStack(S)；進棧運算用Push(S，x)；判?？者\算用EmptyStack(S)；出棧運算用Pop(S)；取棧頂元素運算用Gettop(S)。
35.以二叉鏈表作為存儲結(jié)構(gòu)，試編寫遞歸算法實現(xiàn)求二叉樹中葉子結(jié)點個數(shù)。