數(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ì)解析。

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

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

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

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

A.

B.

D.

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

A.

B.

D.

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

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

5.散列文件是一種(　　)

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

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

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

C.

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

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

8.二維數(shù)組A[n][m]以列優(yōu)先順序存儲，數(shù)組A中每個元素占用1個字節(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.隊列
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ī)存儲器內(nèi)表示時，根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計算出該結(jié)點(diǎn)的存儲地址，這種方法稱為(　　)

A.索引存儲方法
B.順序存儲方法
C.鏈?zhǔn)酱鎯Ψ椒?br/>D.散列存儲方法

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

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

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

A.O(1)

B.

D.

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

A.需判別隊是否空
B.需判別隊是否滿
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分)請在每小題的空格中填上正確答案。錯填、不填均無分。

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

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

13.從一個長度為n的順序表中刪除第i個元素(1≤i≤n)時，需向前移動_______個元素。

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

15.在隊列結(jié)構(gòu)中，允許插入的一端稱為_______。

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

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

18.有m個葉結(jié)點(diǎn)的哈夫曼樹所具有的結(jié)點(diǎn)數(shù)為_______。

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

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

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

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

113.選擇排序的平均時間復(fù)雜度為_______。

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

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

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

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

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

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

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

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

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