全國2008年10月高等教育自學(xué)考試

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

課程代碼：02142

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)

在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。

1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()

A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)

B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)

D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

2.關(guān)于算法的描述，不正確

．．．的是()

A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)

B.所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界

C.健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)

D.算法的優(yōu)劣與算法描述語言無關(guān)

3.在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指向該結(jié)點(diǎn)的()

A.直接前趨

B.直接后繼

C.開始結(jié)點(diǎn)

D.終端結(jié)點(diǎn)

4.將兩個(gè)各有n個(gè)元素的有序表合并成一個(gè)有序表，其最少的比較次數(shù)為()

A.n

B.2n-1

C.2n

D.n2

5.棧和隊(duì)列共同具有的特點(diǎn)是()

A.都是先進(jìn)后出

B.都是先進(jìn)先出

C.只允許在端點(diǎn)進(jìn)行操作運(yùn)算

D.既能先進(jìn)先出，也能先進(jìn)后出

6.若用一個(gè)有6個(gè)單元的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，rear和front的初值分別為0和3。則從隊(duì)列中刪除一個(gè)元素，再添加兩個(gè)元素后，rear和front的值分別為()

A.1和5

B.2和4

C.4和2

D.5和1

7.數(shù)組A［0..5］［0..5］的每個(gè)元素占5個(gè)字節(jié)，將其以列為主序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A［5］［5］的地址是()

A.1175

B.1180

C.1205

D.1210

8.含有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí)，空指針域的個(gè)數(shù)為()

A.n-1

B.n

C.n+1

D.n+2

9.在一棵深度為H的完全二叉樹中，所含結(jié)點(diǎn)的個(gè)數(shù)不少于

．．．()

A.2H-1-1

B.2H-1

C.2H-1

D.2H

10.一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖，它所包含的連通分量數(shù)為()

A.0

B.1

C.n

D.不確定

11.下列說法中不正確的是()

A.無向圖的極大連通子圖稱為連通分量

B.連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)

C.連通圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點(diǎn)

D.有向圖的遍歷不可采用廣度優(yōu)先搜索算法

12.對(duì)一棵二叉排序樹采用中根遍歷進(jìn)行輸出的數(shù)據(jù)一定是()

A.遞增或遞減序列

B.遞減序列

C.無序序列

D.遞增序列

13.一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，查找成功時(shí)的比較次數(shù)為()

A.1

B.2

C.4

D.8

14.一組記錄的關(guān)鍵字為{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.關(guān)于VSAM文件存取操作的說法，正確的是()

A.不能順序存取，只能按關(guān)鍵字隨機(jī)存取

B.不能順序存取，不能按關(guān)鍵字隨機(jī)存取

C.只能順序存取，不能按關(guān)鍵字隨機(jī)存取

D.既能順序存取，也能按關(guān)鍵字隨機(jī)存取

二、填空題(本大題共13小題，每小題2分，共26分)

請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。

16.在任何問題中，數(shù)據(jù)元素都不是孤立的，它們之間總存在某種關(guān)系，通常稱這種關(guān)系為________。

17.存儲(chǔ)結(jié)點(diǎn)之間通常有四種基本存儲(chǔ)方式，即順序存儲(chǔ)方式、索引存儲(chǔ)方式、________和散列存儲(chǔ)方式。

18.在一個(gè)長度為n的順序表中第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)________個(gè)元素。

19.對(duì)一棵深度為10的滿二叉樹按層編號(hào)，則編號(hào)為51的結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)編號(hào)為________。

20.用S 表示入棧操作，X 表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342的出棧順序，相應(yīng)的S 和X 操作串為________。

21.具有n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)為________。

22.一棵具有n 個(gè)結(jié)點(diǎn)的樹，所有非終端結(jié)點(diǎn)的度均為k ，則該樹中葉子結(jié)點(diǎn)個(gè)數(shù)為________。

23.在無向圖G 的鄰接矩陣A 中，若A ［i ］［j ］等于0，則A ［j ］［i ］等于________。

24.兩個(gè)串是相等的，當(dāng)且僅當(dāng)兩個(gè)串的長度相等且________的字符都相同。

25.某二叉樹的后根遍歷序列為abd ，中根遍歷序列為adb ，則它的先根遍歷序列為________。

26.先在所有的記錄中選出鍵值最小的記錄，將它與第一個(gè)記錄交換；然后在其余的記錄中再選出最小的記錄與第二個(gè)記錄交換，依此類推，直至所有記錄排序完成。這種排序方法稱為________。

27.對(duì)含有n 個(gè)結(jié)點(diǎn)e 條邊的無向連通圖，利用prim 算法生成最小生成樹的時(shí)間復(fù)雜度為________。

28.對(duì)n 個(gè)元素進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)為________。

三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

29.設(shè)有編碼為A ，B ，C ，D 的4列火車，依次進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，試寫出這4列火車開出站臺(tái)的所有可能的順序。

30.畫出題30圖所示的二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)。

題30圖

31.對(duì)于題31圖，試給出：

（1）鄰接矩陣；

（2）鄰接表。

題31圖

32.給定表（39，14，22，8，65，28，88，29，67，13，10），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹，畫出插入完成后的二叉排序樹。

33.用插入排序算法對(duì)數(shù)據(jù)序列（47，33，61，82，72，11，25，57

）進(jìn)行排序，寫出整個(gè)

插入排序的每一趟過程。

四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)

34.設(shè)兩個(gè)數(shù)據(jù)元素均為整型數(shù)據(jù)的線性表A=(a1，a2，…，a n)和B=(b1，b2，…，b m)。若n=m 且a i=b i（i=1，2,…，n）則認(rèn)為A=B；若a i=b i（i=1，2,…，j）且a j+1B。試編寫一個(gè)比較A和B的算法，當(dāng)AB時(shí)，輸出1。要求線性表的存儲(chǔ)結(jié)構(gòu)使用鏈接存儲(chǔ)。

35.設(shè)二叉樹的結(jié)點(diǎn)類型定義如下：

typedef struct node{

datatype data;

struct node*lchild,*rchild;

}Bitree;

Bitree*t;

試編寫一個(gè)計(jì)算二叉樹深度的遞歸算法(int Depth(Bitree*t))。