全國2014年4月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

1、自考人網(wǎng)校專本套讀2018春季招生進(jìn)行中，零學(xué)歷2.5年拿本科，支持學(xué)費(fèi)分期，0利率0手 續(xù)費(fèi)！工作太忙加班太多瑣事繁雜 學(xué)習(xí)低效無心備考屢屢掛科你還打算考多久?升職加薪急需學(xué)歷工作太忙加班太多瑣事繁雜 學(xué)習(xí)低效無心備考屢屢掛科你還打算考多久?升職加薪急需學(xué)歷高起點(diǎn)?？?專升本起點(diǎn)本科上NI族提H學(xué)Ifi首部零基礎(chǔ)幡速拿加耦無需定時(shí)定點(diǎn)上課，輕松取證沒壓力無基本學(xué)歷要求，小學(xué)畢業(yè)也能拿本科無考試掛科煩惱無考試掛科煩惱，2.5年準(zhǔn)時(shí)畢業(yè)多中國自考人溫馨提示：試卷網(wǎng)( HYPERLINK )試題均來自互聯(lián)網(wǎng)，部分試題答案由網(wǎng)友提供整理而成，非官方標(biāo)準(zhǔn)答案，僅供廣大 考生參考。如需獲取更權(quán)威的官方參

2、考答案，請(qǐng)大家聯(lián)系中國自考人網(wǎng)校( HYPERLINK )在線老師，或 關(guān)注微信公眾號(hào)自考人，開通精華版課程即可獲得試題答案免費(fèi)下載權(quán)限.全國2014年4月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142請(qǐng)考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。選擇題部分注意事項(xiàng)：.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的 位置上。.每小題選出答案后，用2B鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。如需改動(dòng)，用橡皮擦干凈后，再選涂 其他答案標(biāo)號(hào)。不能答在試題卷上。一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符

3、合題目要求的，請(qǐng)將其選出并將答題紙”的相應(yīng)代碼涂黑。錯(cuò)涂、 多涂或未涂均無分。.下列幾種算法時(shí)間復(fù)雜度中，最小的是A.O(log2n)B.O(n)C.O(n2)D.O(1).數(shù)據(jù)的存儲(chǔ)方式中除了順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式之外，還有A.索引存儲(chǔ)方式和樹形存儲(chǔ)方式B.線性存儲(chǔ)方式和散列存儲(chǔ)方式C.線性存儲(chǔ)方式和索引存儲(chǔ)方式D.索引存儲(chǔ)方式和散列存儲(chǔ)方式.表長為n的順序表中做刪除運(yùn)算的平均時(shí)間復(fù)雜度為A.O(1)B.O(log2n)C.O(n)D.O(n2)應(yīng)用市場搜索“自考人”下載自考APP神器，隨時(shí)隨地?zé)o憂備考，自測練習(xí)強(qiáng)化鞏固，考試重點(diǎn)輕松裝進(jìn)口袋！自考人網(wǎng)校專本套讀2018春季招生進(jìn)行中，零

4、學(xué)歷2.5年拿本科，支持學(xué)費(fèi)分期， 續(xù)費(fèi)！0利率0手.順序表中定位算法(查找值為x的結(jié)點(diǎn)序號(hào)最小值)的平均時(shí)間復(fù)雜度為A.O(1)C.O(n)B.O(log2n)D.O(n2).元素的進(jìn)棧次序?yàn)锳，B，C，D，E，出棧的第一個(gè)元素為E，則第四個(gè)出棧的元素為A.DB.C自考人網(wǎng)校專本套讀2018春季招生進(jìn)行中，零學(xué)歷2.5年拿本科，支持學(xué)費(fèi)分期， 續(xù)費(fèi)！0利率0手.順序表中定位算法(查找值為x的結(jié)點(diǎn)序號(hào)最小值)的平均時(shí)間復(fù)雜度為A.O(1)C.O(n)B.O(log2n)D.O(n2).元素的進(jìn)棧次序?yàn)锳，B，C，D，E，出棧的第一個(gè)元素為E，則第四個(gè)出棧的元素為A.DB.CC.BD.A.帶頭結(jié)

5、點(diǎn)的鏈隊(duì)列中，隊(duì)列頭和隊(duì)列尾指針分別為front和rear，則判斷隊(duì)列空的條件為A.front=rearB.front!二NULLC.rear!=NULLD.front=NULL.深度為5的二叉樹，結(jié)點(diǎn)個(gè)數(shù)最多為A.31 個(gè)C.63 個(gè)B.32 個(gè)D.64 個(gè).如果結(jié)點(diǎn)A有2個(gè)兄弟結(jié)點(diǎn)，結(jié)點(diǎn)B為A的雙親，則B的度為A.1B.3C.4D.5.將題9圖所示的一棵樹轉(zhuǎn)換為二叉樹，結(jié)點(diǎn)C是 A.A的左孩子B.A的右孩子 C.B的右孩子 D.E的右孩子.n為圖的頂點(diǎn)個(gè)數(shù)，e為圖中弧的數(shù)目，則圖的拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為A.O(n)B.O(e)C.O(n-e).無向圖的鄰接矩陣是A.對(duì)角矩陣C.上三角矩

6、陣D.O(n+e)B.稀疏矩陣D.對(duì)稱矩陣.在具有101個(gè)元素的順序表中查找值為x的元素結(jié)點(diǎn)時(shí)，平均比較元素的次數(shù)為A.50B.51C.100D.101.構(gòu)造散列函數(shù)的方法很多,A.數(shù)字分析法、B.線性探測法、C.線性探測法、除留余數(shù)法、二次探測法、常用的構(gòu)造方法有平方取中法除留余數(shù)法除留余數(shù)法、鏈地址法D.線性探測法、二次探測法、鏈地址法.就平均時(shí)間性能而言，快速排序方法最佳，其時(shí)間復(fù)雜度為A.O(n)B.O(nlog2n)A.O(n)應(yīng)用市場搜索“自考人”下載自考APP神器，隨時(shí)隨地?zé)o憂備考，自測練習(xí)強(qiáng)化鞏固，考試重點(diǎn)輕松裝 進(jìn)口袋！自考人網(wǎng)校專本套讀2018春季招生進(jìn)行中，零學(xué)歷2.5年

7、拿本科，支持學(xué)費(fèi)分期，0利率0手 續(xù)費(fèi)！D.O(1og2n)B.冒泡排序D.O(1og2n)B.冒泡排序.下述算法中，不穩(wěn)定的排序算法是A.直接插入排序C.堆排序D.C.堆排序非選擇題部分注意事項(xiàng):用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題（本大題共13小題，每小題2分，共26分）.數(shù)據(jù)的基本單位是。.雙向循環(huán)鏈表中，在p所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t，需要修改四個(gè)指針，分別為；p-next=t；。t-prior=P ；p-next=t；。 TOC o 1-5 h z .在帶有頭結(jié)點(diǎn)的循環(huán)鏈表中，尾指針為rear，判斷指針P所指結(jié)點(diǎn)為首結(jié)點(diǎn)的條件是。.若線性表中

8、最常用的操作是求表長和讀表元素，則順序表和鏈表這兩種存儲(chǔ)方式中，較節(jié)省時(shí)間的是.不含任何數(shù)據(jù)元素的棧稱為。.稀疏矩陣一般采用的壓縮存儲(chǔ)方法是。22.100個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí)，用來指向左、右孩子結(jié)點(diǎn)的指針域有個(gè)。.已知完全二叉樹的第5層有5個(gè)結(jié)點(diǎn)，則整個(gè)完全二叉樹有個(gè)結(jié)點(diǎn)。.n個(gè)頂點(diǎn)的有向圖G用鄰接矩陣A1.n，1.n存儲(chǔ)，其第i列的所有元素之和等于頂點(diǎn)V.的。.具有10個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為。.要完全避免散列所產(chǎn)生的“堆積”現(xiàn)象，通常采用 解決沖突。.在長度為n的帶有崗哨的順序表中進(jìn)行順序查找，查找不成功時(shí)，與關(guān)鍵字的比較次數(shù)為.歸并排序算法的時(shí)間復(fù)雜度是。三、應(yīng)用題（本大題

9、共5小題，每小題6分，共30分）.稀疏矩陣A如題29圖所示，寫出該稀疏矩陣A的三元組表示法。 00500001000000000002000008000005000_ 0700000_題29圖.設(shè)二叉樹的中序遍歷序列為BDCEAFHG，后序遍歷序列為DECBHGFA，試畫出該二叉樹。.寫出題31圖所示無向圖的鄰接矩陣，并寫出每個(gè)頂點(diǎn)的度。應(yīng)用市場搜索“自考人”下載自考APP神器，隨時(shí)隨地?zé)o憂備考，自測練習(xí)強(qiáng)化鞏固，考試重點(diǎn)輕松裝 進(jìn)口袋！自考人網(wǎng)校專本套讀2018春季招生進(jìn)行中，零學(xué)歷2.5年拿本科，支持學(xué)費(fèi)分期，0利率0手 續(xù)費(fèi)！題31圖.已知散列表的地址空間為0至13,散列函數(shù)H(k)=k

10、mod11，(mod為求余運(yùn)算)，待散列序列為(26, 61，38, 84, 49)，用二次探測法解決沖突，構(gòu)造該序列的散列表，要求寫出處理沖突的過程。.將一組鍵值(80，50，65，13，86，35，96，57，39，79，59，15)應(yīng)用二路歸并排序算法從小到大排序，試寫出 各趟的結(jié)果。四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分).設(shè)單鏈表及鏈棧S的結(jié)構(gòu)定義如下：typedef struct node Data Type data； struct node*next； linkstack；編寫一個(gè)算法void ReverseList(1inkstack?。4)，借助于棧S將帶頭結(jié)

11、點(diǎn)單鏈表head中序號(hào)為奇數(shù)的結(jié)點(diǎn)逆置，序 號(hào)為偶數(shù)的結(jié)點(diǎn)保持不變。(例如：單鏈表的邏輯結(jié)構(gòu)為(aj a2, a3, a4，a5，a6)，逆置后變?yōu)?a5, a2，a3，a4，a/ a6)。說明：棧的初始化運(yùn)算用InitStack(S)；進(jìn)棧運(yùn)算用Push(S, x)；判?？者\(yùn)算用EmptyStack(S)；出棧運(yùn)算用Pop(S)； 取棧頂元素運(yùn)算用Gettop(S)。.以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫遞歸算法實(shí)現(xiàn)求二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)。應(yīng)用市場搜索“自考人”下載自考APP神器，隨時(shí)隨地?zé)o憂備考，自測練習(xí)強(qiáng)化鞏固，考試重點(diǎn)輕松裝 進(jìn)口袋！自考人網(wǎng)校專本套讀2018春季招生進(jìn)行中，零學(xué)歷2.5年拿本科，支持學(xué)費(fèi)分期，0利率0手 續(xù)費(fèi)！電話顧問全程 導(dǎo)學(xué)服務(wù)學(xué)習(xí)秘書 提醒服務(wù)備考期間 無限時(shí)不 心理輔導(dǎo) 限次學(xué)習(xí)量身定制 貼心監(jiān)督 學(xué)習(xí)方案, I學(xué)習(xí)進(jìn)度掃碼關(guān)電話顧問全程 導(dǎo)學(xué)服務(wù)學(xué)習(xí)秘書 提醒服務(wù)備考期間 無