全國2008年10月高等教育自學考試
數據結構導論試題
課程代碼：02142
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。
1.從邏輯上可以把數據結構分為()
A.動態結構、靜態結構
B.順序結構、鏈式結構
C.線性結構、非線性結構
D.初等結構、構造型結構
2.關于算法的描述，不正確
．．．的是()
A.算法最終必須由計算機程序實現
B.所謂時間復雜度是指最壞情況下，估算算法執行時間的一個上界
C.健壯的算法不會因非法的輸入數據而出現莫名其妙的狀態
D.算法的優劣與算法描述語言無關
3.在單鏈表中，存儲每個結點需要有兩個域，一個是數據域，另一個是指針域，指針域指向該結點的()
A.直接前趨
B.直接后繼
C.開始結點
D.終端結點
4.將兩個各有n個元素的有序表合并成一個有序表，其最少的比較次數為()
A.n
B.2n-1
C.2n
D.n2
5.棧和隊列共同具有的特點是()
A.都是先進后出
B.都是先進先出
C.只允許在端點進行操作運算
D.既能先進先出，也能先進后出
6.若用一個有6個單元的數組來實現循環隊列，rear和front的初值分別為0和3。則從隊列中刪除一個元素，再添加兩個元素后，rear和front的值分別為()
A.1和5
B.2和4
C.4和2
D.5和1
7.數組A［0..5］［0..5］的每個元素占5個字節，將其以列為主序存儲在起始地址為1000的內存單元中，則元素A［5］［5］的地址是()
A.1175
B.1180
C.1205
D.1210
8.含有n個結點的二叉樹采用二叉鏈表存儲時，空指針域的個數為()
A.n-1
B.n
C.n+1
D.n+2
9.在一棵深度為H的完全二叉樹中，所含結點的個數不少于
．．．()
A.2H-1-1
B.2H-1
C.2H-1
D.2H
10.一個具有n個頂點的無向連通圖，它所包含的連通分量數為()
A.0
B.1
C.n
D.不確定
11.下列說法中不正確的是()
A.無向圖的極大連通子圖稱為連通分量
B.連通圖的廣度優先搜索中一般要采用隊列來暫存剛訪問過的頂點
C.連通圖的深度優先搜索中一般要采用棧來暫存剛訪問過的頂點
D.有向圖的遍歷不可采用廣度優先搜索算法
12.對一棵二叉排序樹采用中根遍歷進行輸出的數據一定是()
A.遞增或遞減序列
B.遞減序列
C.無序序列
D.遞增序列
13.一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值為82的結點時，查找成功時的比較次數為()
A.1
B.2
C.4
D.8
14.一組記錄的關鍵字為{45，80，55，40，42，85}，則利用堆排序的方法建立的初始堆為
() A.80，45，55，40，42，85 B.85，80，55，40，42，45
C.85，80，55，45，42，40
D.85，55，80，42，45，40
15.關于VSAM文件存取操作的說法，正確的是()
A.不能順序存取，只能按關鍵字隨機存取
B.不能順序存取，不能按關鍵字隨機存取
C.只能順序存取，不能按關鍵字隨機存取
D.既能順序存取，也能按關鍵字隨機存取
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.在任何問題中，數據元素都不是孤立的，它們之間總存在某種關系，通常稱這種關系為________。
17.存儲結點之間通常有四種基本存儲方式，即順序存儲方式、索引存儲方式、________和散列存儲方式。
18.在一個長度為n的順序表中第i個元素（1≤i≤n）之前插入一個元素時，需向后移動________個元素。
19.對一棵深度為10的滿二叉樹按層編號，則編號為51的結點，它的雙親結點編號為________。
20.用S 表示入棧操作，X 表示出棧操作，若元素入棧順序為1234，為了得到1342的出棧順序，相應的S 和X 操作串為________。
21.具有n 個葉子結點的哈夫曼樹，其結點總數為________。
22.一棵具有n 個結點的樹，所有非終端結點的度均為k ，則該樹中葉子結點個數為________。
23.在無向圖G 的鄰接矩陣A 中，若A ［i ］［j ］等于0，則A ［j ］［i ］等于________。
24.兩個串是相等的，當且僅當兩個串的長度相等且________的字符都相同。
25.某二叉樹的后根遍歷序列為abd ，中根遍歷序列為adb ，則它的先根遍歷序列為________。
26.先在所有的記錄中選出鍵值最小的記錄，將它與第一個記錄交換；然后在其余的記錄中再選出最小的記錄與第二個記錄交換，依此類推，直至所有記錄排序完成。這種排序方法稱為________。
27.對含有n 個結點e 條邊的無向連通圖，利用prim 算法生成最小生成樹的時間復雜度為________。
28.對n 個元素進行冒泡排序時，最少的比較次數為________。
三、應用題(本大題共5小題，每小題6分，共30分)
29.設有編碼為A ，B ，C ，D 的4列火車，依次進入一個棧式結構的站臺，試寫出這4列火車開出站臺的所有可能的順序。
30.畫出題30圖所示的二叉樹的二叉鏈表存儲結構。
題30圖
31.對于題31圖，試給出：
（1）鄰接矩陣；
（2）鄰接表。
題31圖
32.給定表（39，14，22，8，65，28，88，29，67，13，10），試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。
33.用插入排序算法對數據序列（47，33，61，82，72，11，25，57
）進行排序，寫出整個
插入排序的每一趟過程。
四、算法設計題(本大題共2小題，每小題7分，共14分)
34.設兩個數據元素均為整型數據的線性表A=(a1，a2，…，a n)和B=(b1，b2，…，b m)。若n=m 且a i=b i（i=1，2,…，n）則認為A=B；若a i=b i（i=1，2,…，j）且a j+1B。試編寫一個比較A和B的算法，當A
35.設二叉樹的結點類型定義如下：
typedef struct node{
datatype data;
struct node*lchild,*rchild;
}Bitree;
Bitree*t;
試編寫一個計算二叉樹深度的遞歸算法(int Depth(Bitree*t))。
咨詢在線客服