2013年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考試題

全國(guó)2013年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考試題

一、單項(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是
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.二路歸并排序

非選擇題部分
注意事項(xiàng)：
用黑色字跡的簽字筆或鋼筆將答案寫(xiě)在答題紙上，不能答在試題卷上。

二、填空題(本大題共13小題，每小題2分，共26分)
16.下面算法程序段的時(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;}
17.設(shè)p指向單鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入q所指的結(jié)點(diǎn)，需執(zhí)行的語(yǔ)句序列是①p->next=q;②__________;③p->next=NULL。
18.向一個(gè)長(zhǎng)度為100的順序表中第50個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng)的元素個(gè)數(shù)為_(kāi)_________。
19.一個(gè)帶頭結(jié)點(diǎn)的鏈棧LS，現(xiàn)將一個(gè)新結(jié)點(diǎn)入棧，指向該結(jié)點(diǎn)的指針為p，入棧操作為p->next=LS->next和__________。
20.隊(duì)列操作的原則是__________。
21.含有n個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其最大長(zhǎng)度為_(kāi)_________。
22.在一棵度為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è)。
23.某二叉樹(shù)的中序遍歷序列為BACDEFGH，后序遍歷序列為BCAEDGHF，則根結(jié)點(diǎn)F的左子樹(shù)上共有__________個(gè)結(jié)點(diǎn)。
24.設(shè)有向圖G的鄰接矩陣為A,如果<Vi,Vj>是圖中的一條弧,則A［i］［j］的值為_(kāi)______。
25.一個(gè)有序表A含有15個(gè)數(shù)據(jù)元素，且第一個(gè)元素的下標(biāo)為1，按二分查找算法查找元素A［14］，所比較的元素下標(biāo)依次是__________。
26.用n個(gè)值構(gòu)造一棵二叉排序樹(shù)，它的最大深度為_(kāi)_________。
27.設(shè)記錄數(shù)為n，則冒泡排序算法在最好情況下所作的比較次數(shù)為_(kāi)_________。
28.二路歸并排序算法的時(shí)間復(fù)雜度為_(kāi)_________。

三、應(yīng)用題(本大題共5小題，每小題6分，共30分)
29.設(shè)有編號(hào)為A，B，C，D的四輛列車(chē)，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，試寫(xiě)出這四輛列車(chē)開(kāi)出站臺(tái)的所有可能的順序。
30.已知一棵二叉樹(shù)的先序遍歷序列為ABCDEFGHK，中序遍歷序列為CBEDFAGKH，試建立該二叉樹(shù)并寫(xiě)出它的后序遍歷序列。
31.利用克魯斯卡爾（Kruskal）算法構(gòu)造題31圖的最小生成樹(shù)，畫(huà)出它的構(gòu)造過(guò)程。
32.給定表（27，19，50，1，75，12，40，90，66，32，22），試按元素在表中的次序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹(shù)，畫(huà)出插入完成后的二叉排序樹(shù)。
33.對(duì)初始關(guān)鍵字序列48，39，68，95，88，12，27，48的記錄進(jìn)行冒泡排序（升序），給出排序過(guò)程。

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

34.試寫(xiě)出判斷帶頭結(jié)點(diǎn)的單鏈表head中的元素值是否是遞減的算法。
35.試寫(xiě)出在有序表T中用二分查找法查找鍵值為key的元素的算法。