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