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

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

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

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。

1.數(shù)據(jù)的基本單位是(　　)

A.數(shù)據(jù)元素
B.數(shù)據(jù)項
C.字段
D.域

2.算法的空間復(fù)雜度是指(　　)

A.算法中輸入數(shù)據(jù)所占用的存儲空間的大小
B.算法本身所占用的存儲空間的大小
C.算法中所占用的所有存儲空間的大小
D.算法中需要的輔助變量所占用存儲空間的大小

3.從一個長度為100的順序表中刪除第30個元素，需向前移動的元素個數(shù)為(　　)

A.29
B.30
C.70
D.71

4.若線性表最常用的操作是存取第i個元素及其后繼的值，則最節(jié)省操作時間的存儲結(jié)構(gòu)是(　　)

A.單鏈表
B.雙鏈表
C.單循環(huán)鏈表
D.順序表

5.判斷鏈棧LS是否為空的條件是(　　)

A.LS->next= =LS
B.LS->next= =NULL
C.LS! =NULL
D.LS= =NULL

6.關(guān)于鏈隊列的運(yùn)算說法正確的是(　　)

A.入隊列需要判斷隊列是否滿
B.出隊列需要判斷隊列是否空
C.入隊列需要判斷隊列是否空
D.出隊列需要判斷隊列是否滿

7.元素的進(jìn)棧次序?yàn)锳，B，C，D，E，則出棧中不可能的序列是(　　)

A.A，B，C，D，E
B.B，C，D，E，A
C.E，A，B，C，D
D.E，D，C，B，A

8.具有63個結(jié)點(diǎn)的完全二叉樹是(　　)

A.滿二叉樹
B.二叉排序樹
C.哈夫曼樹
D.空樹

9.將含有80個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層從左到右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1。則關(guān)于編號40的結(jié)點(diǎn)的左右孩子的說法正確的是(　　)

A.左孩子編號為79，右孩子編號為80
B.左孩子不存在，右孩子編號為80
C.左孩子編號為80，右孩子不存在
D.左孩子不存在，右孩子不存在

10.將題10圖所示的一棵樹轉(zhuǎn)換為二叉樹，結(jié)點(diǎn)D是(　　)題10圖

A.A的右孩子
B.B的右孩子
C.C的右孩子
D.E的右孩子

11.無向圖的鄰接矩陣是(　　)

A.對稱矩陣
B.稀疏矩陣
C.對角矩陣
D.上三角矩陣

12.圖的廣度優(yōu)先搜索遍歷的過程類似于樹的(　　)

A.前序遍歷
B.中序遍歷
C.后序遍歷
D.按層次遍歷

13.要解決散列引起的沖突問題，最常用的方法是(　　)

A.數(shù)字分析法、除留余數(shù)法、平方取中法
B.除留余數(shù)法、線性探測法、平方取中法
C.線性探測法、二次探測法、鏈地址法
D.除留余數(shù)法、線性探測法、二次探測法

14.下列表述中，正確的是(　　)

A.序列(102，81，55，62，50，40，58，35，20)是堆
B.序列(102，81，55，62，50，40，35，58，20)是堆
C.序列(102，81，55，58，50，40，35，62，20)是堆
D.序列(102，71，55，40，50，62，35，58，20)是堆

15.下列算法中，不穩(wěn)定的排序算法是(　　)

A.冒泡排序
B.快速排序
C.直接插入排序
D.二路歸并排序

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

11.下面算法程序段的時間復(fù)雜度為________。for( i=1 ;i<=n ;i++ )     for( j=1; j<=i; j++ )     {    x=a[i][j];          a[i][j]=a[j][i];          a[j][i]=x;}

12.設(shè)p指向單鏈表的最后一個結(jié)點(diǎn)，要在最后一個結(jié)點(diǎn)之后插入q所指的結(jié)點(diǎn)，需執(zhí)行的語句序列是①p->next=q;②________;③p->next=NULL。

13.向一個長度為100的順序表中第50個元素之前插入一個元素時，需向后移動的元素個數(shù)為________。

14.一個帶頭結(jié)點(diǎn)的鏈棧LS，現(xiàn)將一個新結(jié)點(diǎn)入棧，指向該結(jié)點(diǎn)的指針為p，入棧操作為p->next=LS->next和________。

15.隊列操作的原則是________。

16.含有n個頂點(diǎn)的連通圖中的任意一條簡單路徑，其最大長度為________。

17.在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為1個，度為2的結(jié)點(diǎn)數(shù)為2個，度為1的結(jié)點(diǎn)數(shù)為3個，則度為0的結(jié)點(diǎn)數(shù)為________個。

18.某二叉樹的中序遍歷序列為BACDEFGH，后序遍歷序列為BCAEDGHF，則根結(jié)點(diǎn)F的左子樹上共有________個結(jié)點(diǎn)。

19.設(shè)有向圖G的鄰接矩陣為A，如果<V_i，V_j>是圖中的一條弧，則A[i][j]的值為_______。

110.一個有序表A含有15個數(shù)據(jù)元素，且第一個元素的下標(biāo)為1，按二分查找算法查找元素A[14]，所比較的元素下標(biāo)依次是________。

111.用n個值構(gòu)造一棵二叉排序樹，它的最大深度為________。

112.設(shè)記錄數(shù)為n，則冒泡排序算法在最好情況下所作的比較次數(shù)為________。

113.二路歸并排序算法的時間復(fù)雜度為________。

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

21.設(shè)有編號為A，B，C，D的四輛列車，順序進(jìn)入一個棧式結(jié)構(gòu)的站臺，試寫出這四輛列車開出站臺的所有可能的順序。

22.已知一棵二叉樹的先序遍歷序列為ABCDEFGHK，中序遍歷序列為CBEDFAGKH，試建立該二叉樹并寫出它的后序遍歷序列。

23.利用克魯斯卡爾(Kruskal)算法構(gòu)造題31圖的最小生成樹，畫出它的構(gòu)造過程。                               題31圖

24.給定表(27，19，50，1，75，12，40，90，66，32，22)，試按元素在表中的次序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。

25.對初始關(guān)鍵字序列48，39，68，95，88，12，27，48的記錄進(jìn)行冒泡排序(升序)，給出排序過程。

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

31.試寫出判斷帶頭結(jié)點(diǎn)的單鏈表head中的元素值是否是遞減的算法。

32.試寫出在有序表T中用二分查找法查找鍵值為key的元素的算法。