02142數(shù)據(jù)結(jié)構(gòu)導論201301試題及答案

1、2013年1月高等教育自學考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導論試題課程代碼：02142考生答題注意事項：1. 本卷所有試卷必須在答題卡上作答。答在試卷和草稿紙上的無效。2. 第一部分為選擇題。必須對應(yīng)試卷上的題號使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。3. 第二部分為非選擇題。必須注明大、小題號，使用0.5毫米黑色字跡筆作答。4. 合理安排答題空間，超出答題區(qū)域無效。選擇題部分一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。1.數(shù)據(jù)的基本單位是A.數(shù)據(jù)元素B.數(shù)據(jù)項C.字段D

2、.域2.算法的空間復雜度是指A.算法中輸入數(shù)據(jù)所占用的存儲空間的大小B.算法本身所占用的存儲空間的大小C.算法中所占用的所有存儲空間的大小D.算法中需要的輔助變量所占用存儲空間的大小3.從一個長度為100的順序表中刪除第30個元素,需向前移動的元素個數(shù)為A.29B.30C.70D.714.若線性表最常用的操作是存取第i個元素及其后繼的值,則最節(jié)省操作時間的存儲結(jié)構(gòu)是A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表5.判斷鏈棧LS是否為空的條件是A.LS-next= =LSB.LS-next= =NULLC.LS! =NULLD.LS= =NULL6.關(guān)于鏈隊列的運算說法正確的是A.入隊列需要判斷隊

3、列是否滿B.出隊列需要判斷隊列是否空C.入隊列需要判斷隊列是否空D.出隊列需要判斷隊列是否滿7.元素的進棧次序為A,B,C,D,E,則出棧中不可能的序列是A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A8.具有63個結(jié)點的完全二叉樹是A.滿二叉樹B.二叉排序樹C.哈夫曼樹D.空樹9.將含有80個結(jié)點的完全二叉樹從根這一層開始,每層從左到右依次對結(jié)點編號,根結(jié)點的編號為1。則關(guān)于編號40的結(jié)點的左右孩子的說法正確的是A.左孩子編號為79，右孩子編號為80B.左孩子不存在，右孩子編號為80C.左孩子編號為80，右孩子不存在D.左孩子不存在，右孩子不存在10.

4、將題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，6

5、2，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.下面算法程序段的時間復雜度為_O(n2)_。for(i=1;i=n;i+)for(j=1;jnext=q;_p=q_;p-next=NULL。18.向一個長度為100的順序表中第50個元素

6、之前插入一個元素時，需向后移動的元素個數(shù)為_51_。19.一個帶頭結(jié)點的鏈棧LS，現(xiàn)將一個新結(jié)點入棧，指向該結(jié)點的指針為p，入棧操作為p-next=LS-next和_LS-next=p_。20.隊列操作的原則是_先進先出_。21.含有n個頂點的連通圖中的任意一條簡單路徑，其最大長度為_n-1_。22.在一棵度為3的樹中，度為3的結(jié)點數(shù)為1個，度為2的結(jié)點數(shù)為2個，度為1的結(jié)點數(shù)為3個，則度為0的結(jié)點數(shù)為_5_個。23.某二叉樹的中序遍歷序列為BACDEFGH，后序遍歷序列為BCAEDGHF，則根結(jié)點F的左子樹上共有_5_個結(jié)點。24.設(shè)有向圖G的鄰接矩陣為A,如果是圖中的一條弧,則Aij的值為

7、_1_。25.一個有序表A含有15個數(shù)據(jù)元素，且第一個元素的下標為1，按二分查找算法查找元素A14，所比較的元素下標依次是_8，12，14_。26.用n個值構(gòu)造一棵二叉排序樹，它的最大深度為_n_。27.設(shè)記錄數(shù)為n，則冒泡排序算法在最好情況下所作的比較次數(shù)為_n-1_。28.二路歸并排序算法的時間復雜度為_O(nlog2n)_。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29.設(shè)有編號為A，B，C，D的四輛列車，順序進入一個棧式結(jié)構(gòu)的站臺，試寫出這四輛列車開出站臺的所有可能的順序。答：若列車A最先開出站臺，則列車可能的出站順序有：ABCD、ABDC、ACBD、ACDB、ADCB若列車B

8、最先開出站臺，則列車可能的出站順序有：BACD、BADC、BCAD、BCDA、BDCA若列車C最先開出站臺，則列車可能的出站順序有：CBAD、CBDA、CDBA若列車D最先開出站臺，則列車可能的出站順序有：DCBA綜上所述，這四輛列車開出站臺的所有可能的順序共有14種。30.已知一棵二叉樹的先序遍歷序列為ABCDEFGHK，中序遍歷序列為CBEDFAGKH，試建立該二叉樹并寫出它的后序遍歷序列。答：后序遍歷序列為：CEFDBKHGA31.利用克魯斯卡爾（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的記錄進行冒泡排序（升序），給出排序過程。答：初始關(guān)鍵字序列：48，39，68，95，88，12，27，48第一趟排序后：39，48，68，88，12，27，48，95第二趟排序后：39，48，68，12，27，48，88，95第三趟排序后：39，48，12，27，48，68，88，95第四趟排序后：39，12，27，48，48，68，88，95第五趟排序后：12，27，39，4