?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2010年10月真題（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2010年10月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2010年10月真題及答案（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

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

1.下列描述中正確的是(　　)

A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位
B.數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對(duì)象
C.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合
D.算法和程序原則上沒(méi)有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)兩者是通用的

2.歸并排序的時(shí)間復(fù)雜度是(　　)

A.

B.

D.

3.二分查找的時(shí)間復(fù)雜度是(　　)

A.

B.

D.

4.順序存儲(chǔ)的表中有90000個(gè)元素，已按關(guān)鍵字值升序排列，假設(shè)對(duì)每個(gè)元素進(jìn)行查找的概率相同，且每個(gè)元素的關(guān)鍵字值皆不相同，用順序查找法查找時(shí)，需平均比較的次數(shù)為(　　)

A.25000
B.30000
C.45000
D.90000

5.散列文件是一種(　　)

A.順序文件
B.索引文件
C.鏈接文件
D.計(jì)算尋址文件

6.兩個(gè)矩陣A：m×n，B：n×p相乘，其時(shí)間復(fù)雜度為(　　)

A.O(n)
B.O(mnp)

C.

7.常用于函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)是(　　)

A.棧
B.隊(duì)列
C.鏈表
D.數(shù)組

8.二維數(shù)組A[n][m]以列優(yōu)先順序存儲(chǔ)，數(shù)組A中每個(gè)元素占用1個(gè)字節(jié)，A[1][1]為首元素，其地址為0，則元素A[i][j]的地址為(　　)

A.(i-1)×m+(j-1)
B.(j-1)×n+(i-1)
C.(j-1)×n+i
D.j×n+i

9.圖的廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是(　　)

A.隊(duì)列
B.樹
C.棧
D.集合

10.序列(21，19，37，5，2)經(jīng)冒泡排序法由小到大排序，在第一次執(zhí)行交換后所得結(jié)果為(　　)

A.(19，21，37，5，2)
B.(21，19，5，37，2)
C.(21，19，37，2，5)
D.(2，21，19，37，5)

11.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，這種方法稱為(　　)

A.索引存儲(chǔ)方法
B.順序存儲(chǔ)方法
C.鏈?zhǔn)酱鎯?chǔ)方法
D.散列存儲(chǔ)方法

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

A.直接前趨
B.直接后繼
C.開(kāi)始結(jié)點(diǎn)
D.終端結(jié)點(diǎn)

13.在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法所需的時(shí)間復(fù)雜度為(　　)

A.O(1)

B.

D.

14.在鏈隊(duì)列中執(zhí)行入隊(duì)操作，(　　)

A.需判別隊(duì)是否空
B.需判別隊(duì)是否滿
C.限制在鏈表頭p進(jìn)行
D.限制在鏈表尾p進(jìn)行

15.一整數(shù)序列26，59，77，31，51，11，19，42，以二路歸并排序從小到大排序，第一階段的歸并結(jié)果為(　　)

A.31，51，11，42，26，77，59，19
B.26，59，31，77，11，51，19，42
C.11，19，26，31，42，59，51，77
D.26，11，19，31，51，59，77，42

二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

11.下列程序段的時(shí)間復(fù)雜度為_(kāi)______。i=0; s=0;while( s<n){   i++;    s=s+i;}

12.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序存儲(chǔ)結(jié)構(gòu)、_______、散列存儲(chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu)4種。

13.從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動(dòng)_______個(gè)元素。

14.在單鏈表中，插入一個(gè)新結(jié)點(diǎn)需修改_______個(gè)指針。

15.在隊(duì)列結(jié)構(gòu)中，允許插入的一端稱為_(kāi)______。

16.稀疏矩陣采用的壓縮存儲(chǔ)方法是_______。

17.向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行p->next=top和_______操作。

18.有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹所具有的結(jié)點(diǎn)數(shù)為_(kāi)______。

19.在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上而下、自左至右地給所有結(jié)點(diǎn)編號(hào)。設(shè)根結(jié)點(diǎn)編號(hào)為1。若編號(hào)為i的結(jié)點(diǎn)有右孩子，那么其右孩子的編號(hào)為_(kāi)______。

110.在一棵樹中，_______結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。

111.一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)是_______。

112.n個(gè)頂點(diǎn)的無(wú)向圖G用鄰接矩陣A[n][n]存儲(chǔ)，其中第i列的所有元素之和等于頂點(diǎn)Vi的_______。

113.選擇排序的平均時(shí)間復(fù)雜度為_(kāi)______。

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

21.在棧的輸入端元素的輸入順序?yàn)?，2，3，4，5，6，進(jìn)棧過(guò)程中可以退棧，則退棧時(shí)能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，寫出進(jìn)棧、退棧過(guò)程，若不能，簡(jiǎn)述理由。(用push(x)表示x進(jìn)棧，pop(x)表示x退棧)

22.已知一棵二叉樹的中根遍歷序列為CBEDFAGH，后根遍歷序列為CEFDBHGA，畫出該二叉樹。

23.給定表(15，11，8，20，14，13)，試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹，畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調(diào)整為平衡二叉排序樹。

24.如題32圖所示無(wú)向圖，(1)寫出其鄰接矩陣;(2)寫出三種以頂點(diǎn)A為起點(diǎn)的深度優(yōu)先搜索頂點(diǎn)序列。題32圖

25.用冒泡排序法對(duì)數(shù)據(jù)序列(49，38，65，97，76，134，27，49)進(jìn)行排序，寫出排序過(guò)程。并說(shuō)明冒泡排序是否為穩(wěn)定排序。

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

31.編寫計(jì)算二叉樹中葉子結(jié)點(diǎn)數(shù)目的算法。

32.開(kāi)散列表的類型定義如下：typedef struct tagnode{  keytype key;   struct tagnode*next; }*pointer,node;typedef pointer openhash[n];試寫出開(kāi)散列表上的查找算法。