- 相關(guān)推薦
全國2013年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題
一、單項選擇題(本大題共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)于鏈隊列的運算說法正確的是
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個結(jié)點的完全二叉樹是
A.滿二叉樹 B.二叉排序樹
C.哈夫曼樹 D.空樹
9.將含有80個結(jié)點的完全二叉樹從根這一層開始,每層從左到右依次對結(jié)點編號,根結(jié)點的編號為1。則關(guān)于編號40的結(jié)點的左右孩子的說法正確的是
A.左孩子編號為79，右孩子編號為80
B.左孩子不存在，右孩子編號為80
C.左孩子編號為80，右孩子不存在
D.左孩子不存在，右孩子不存在
10.將題10圖所示的一棵樹轉(zhuǎn)換為二叉樹，結(jié)點D是
A.A的右孩子
B.B的右孩子
C.C的右孩子
D.E的右孩子
11.無向圖的鄰接矩陣是 題10圖
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.下面算法程序段的時間復(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;}
17.設(shè)p指向單鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入q所指的結(jié)點，需執(zhí)行的語句序列是①p->next=q;②__________;③p->next=NULL。
18.向一個長度為100的順序表中第50個元素之前插入一個元素時，需向后移動的元素個數(shù)為__________。
19.一個帶頭結(jié)點的鏈棧LS，現(xiàn)將一個新結(jié)點入棧，指向該結(jié)點的指針為p，入棧操作為p->next=LS->next和__________。
20.隊列操作的原則是__________。
21.含有n個頂點的連通圖中的任意一條簡單路徑，其最大長度為__________。
22.在一棵度為3的樹中，度為3的結(jié)點數(shù)為1個，度為2的結(jié)點數(shù)為2個，度為1的結(jié)點數(shù)為3個，則度為0的結(jié)點數(shù)為__________個。
23.某二叉樹的中序遍歷序列為BACDEFGH，后序遍歷序列為BCAEDGHF，則根結(jié)點F的左子樹上共有__________個結(jié)點。
24.設(shè)有向圖G的鄰接矩陣為A,如果
25.一個有序表A含有15個數(shù)據(jù)元素，且第一個元素的下標為1，按二分查找算法查找元素A[14]，所比較的元素下標依次是__________。
26.用n個值構(gòu)造一棵二叉排序樹，它的最大深度為__________。
27.設(shè)記錄數(shù)為n，則冒泡排序算法在最好情況下所作的比較次數(shù)為__________。
28.二路歸并排序算法的時間復(fù)雜度為__________。
三、應(yīng)用題(本大題共5小題，每小題6分，共30分)
29.設(shè)有編號為A，B，C，D的四輛列車，順序進入一個棧式結(jié)構(gòu)的站臺，試寫出這四輛列車開出站臺的所有可能的順序。
30.已知一棵二叉樹的先序遍歷序列為ABCDEFGHK，中序遍歷序列為CBEDFAGKH，試建立該二叉樹并寫出它的后序遍歷序列。
31.利用克魯斯卡爾(Kruskal)算法構(gòu)造題31圖的最小生成樹，畫出它的構(gòu)造過程。
題31圖
32.給定表(27，19，50，1，75，12，40，90，66，32，22)，試按元素在表中的次序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。
33.對初始關(guān)鍵字序列48，39，68，95，88，12，27，48的記錄進行冒泡排序(升序)，給出排序過程。
四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)
34.試寫出判斷帶頭結(jié)點的單鏈表head中的元素值是否是遞減的算法。
35.試寫出在有序表T中用二分查找法查找鍵值為key的元素的算法。
【全國1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題】相關(guān)文章：
全國自學(xué)考試社區(qū)護理學(xué)試題03-03
2017自學(xué)考試《中國文化導(dǎo)論》模擬試題及答案12-03
2017自學(xué)考試《中國文化導(dǎo)論》備考試題及答案12-03
2017自學(xué)考試《中國文化導(dǎo)論》自測試題12-03
全國2011年4月自學(xué)考試心理學(xué)試題03-02
全國2013年1月自學(xué)考試工程經(jīng)濟試題03-04
關(guān)于全國高等教育自學(xué)考試談判與推銷技巧的考試試題03-30