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

自考責(zé)任編輯：彭雅倩 2019-06-26

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

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

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

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

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

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

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

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

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

4.若線性表最常用的操作是存取第i個(gè)元素及其后繼的值，則最節(jié)省操作時(shí)間的存儲(chǔ)結(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)于鏈隊(duì)列的運(yùn)算說(shuō)法正確的是(　　)

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

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個(gè)結(jié)點(diǎn)的完全二叉樹(shù)是(　　)

A.滿二叉樹(shù)
B.二叉排序樹(shù)
C.哈夫曼樹(shù)
D.空樹(shù)

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

A.左孩子編號(hào)為79，右孩子編號(hào)為80
B.左孩子不存在，右孩子編號(hào)為80
C.左孩子編號(hào)為80，右孩子不存在
D.左孩子不存在，右孩子不存在

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

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

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

A.對(duì)稱(chēng)矩陣
B.稀疏矩陣
C.對(duì)角矩陣
D.上三角矩陣

12.圖的廣度優(yōu)先搜索遍歷的過(guò)程類(lèi)似于樹(shù)的(　　)

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

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

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

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.下面算法程序段的時(shí)間復(fù)雜度為_(kāi)_______。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指向單鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入q所指的結(jié)點(diǎn)，需執(zhí)行的語(yǔ)句序列是①p->next=q;②________;③p->next=NULL。

13.向一個(gè)長(zhǎng)度為100的順序表中第50個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng)的元素個(gè)數(shù)為_(kāi)_______。

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

15.隊(duì)列操作的原則是________。

16.含有n個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其最大長(zhǎng)度為_(kāi)_______。

17.在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為1個(gè)，度為2的結(jié)點(diǎn)數(shù)為2個(gè)，度為1的結(jié)點(diǎn)數(shù)為3個(gè)，則度為0的結(jié)點(diǎn)數(shù)為_(kāi)_______個(gè)。

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

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

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

111.用n個(gè)值構(gòu)造一棵二叉排序樹(shù)，它的最大深度為_(kāi)_______。

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

113.二路歸并排序算法的時(shí)間復(fù)雜度為_(kāi)_______。

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

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

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

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