2013年1月數(shù)據(jù)結構導論自考試題

全國2013年1月數(shù)據(jù)結構導論自考試題

一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應代碼涂黑。錯涂、多涂或未涂均無分。
1.數(shù)據(jù)的基本單位是
A.數(shù)據(jù)元素 B.數(shù)據(jù)項
C.字段 D.域
2.算法的空間復雜度是指
A.算法中輸入數(shù)據(jù)所占用的存儲空間的大小
B.算法本身所占用的存儲空間的大小
C.算法中所占用的所有存儲空間的大小
D.算法中需要的輔助變量所占用存儲空間的大小
3.從一個長度為100的順序表中刪除第30個元素,需向前移動的元素個數(shù)為
A.29 B.30
C.70 D.71
4.若線性表最常用的操作是存取第i個元素及其后繼的值,則最節(jié)省操作時間的存儲結構是
A.單鏈表 B.雙鏈表
C.單循環(huán)鏈表 D.順序表
5.判斷鏈棧LS是否為空的條件是
A.LS->next= =LS B.LS->next= =NULL
C.LS! =NULL D.LS= =NULL
6.關于鏈隊列的運算說法正確的是
A.入隊列需要判斷隊列是否滿 B.出隊列需要判斷隊列是否空
C.入隊列需要判斷隊列是否空 D.出隊列需要判斷隊列是否滿
7.元素的進棧次序為A,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個結點的完全二叉樹是
A.滿二叉樹 B.二叉排序樹
C.哈夫曼樹 D.空樹
9.將含有80個結點的完全二叉樹從根這一層開始,每層從左到右依次對結點編號,根結點的編號為1。則關于編號40的結點的左右孩子的說法正確的是
A.左孩子編號為79，右孩子編號為80
B.左孩子不存在，右孩子編號為80
C.左孩子編號為80，右孩子不存在
D.左孩子不存在，右孩子不存在
10.將題10圖所示的一棵樹轉換為二叉樹，結點D是
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分)
16.下面算法程序段的時間復雜度為__________。
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.設p指向單鏈表的最后一個結點，要在最后一個結點之后插入q所指的結點，需執(zhí)行的語句序列是①p->next=q;②__________;③p->next=NULL。
18.向一個長度為100的順序表中第50個元素之前插入一個元素時，需向后移動的元素個數(shù)為__________。
19.一個帶頭結點的鏈棧LS，現(xiàn)將一個新結點入棧，指向該結點的指針為p，入棧操作為p->next=LS->next和__________。
20.隊列操作的原則是__________。
21.含有n個頂點的連通圖中的任意一條簡單路徑，其最大長度為__________。
22.在一棵度為3的樹中，度為3的結點數(shù)為1個，度為2的結點數(shù)為2個，度為1的結點數(shù)為3個，則度為0的結點數(shù)為__________個。
23.某二叉樹的中序遍歷序列為BACDEFGH，后序遍歷序列為BCAEDGHF，則根結點F的左子樹上共有__________個結點。
24.設有向圖G的鄰接矩陣為A,如果<Vi,Vj>是圖中的一條弧,則A［i］［j］的值為_______。
25.一個有序表A含有15個數(shù)據(jù)元素，且第一個元素的下標為1，按二分查找算法查找元素A［14］，所比較的元素下標依次是__________。
26.用n個值構造一棵二叉排序樹，它的最大深度為__________。
27.設記錄數(shù)為n，則冒泡排序算法在最好情況下所作的比較次數(shù)為__________。
28.二路歸并排序算法的時間復雜度為__________。

三、應用題(本大題共5小題，每小題6分，共30分)
29.設有編號為A，B，C，D的四輛列車，順序進入一個棧式結構的站臺，試寫出這四輛列車開出站臺的所有可能的順序。
30.已知一棵二叉樹的先序遍歷序列為ABCDEFGHK，中序遍歷序列為CBEDFAGKH，試建立該二叉樹并寫出它的后序遍歷序列。
31.利用克魯斯卡爾（Kruskal）算法構造題31圖的最小生成樹，畫出它的構造過程。
32.給定表（27，19，50，1，75，12，40，90，66，32，22），試按元素在表中的次序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。
33.對初始關鍵字序列48，39，68，95，88，12，27，48的記錄進行冒泡排序（升序），給出排序過程。

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

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