1、職加薪你還打算考多久?選擇題部分2.每小題選出答案后2B鉛筆把答題紙上對應題目的答案標30分)多涂或未涂均無分。B.O(n)D.O(1)A.O(1)進口袋!如需改動，用橡皮擦干凈后，再選涂在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將1.下列幾種算法時間復雜度中，最小的是3.表長為n的順序表中做刪除運算的平均時間復雜度為C.O(n)應用市場搜索A.O(log 2n)C.O(n2)全國2014年4月自學考試數據結構導論試題課程代碼：02142請考生按規定用筆將所有試題的答案涂、寫在答題紙上。B.O(log 2n)D.O(n2)下載自考APP神器，隨時隨地無憂備考，自測練習強化

2、鞏固，考試重點輕松裝溫馨提示：試卷網( )試幽均來自互聯網，部分試題答案由網友提供整理而成，非官方標準答案，僅供廣大 考生春考.如需獲取更權威的官方春考答案.謂大家聯系“中國自考人網校(www.zk&com工n )H在老師，同 關注微信公眾號“自考人”，開通精華版課程即可獲得試題答案免期下載權限.自考人網校專本套讀2018春季招生進行中，零學歷2.5年拿本科，支持學費分期，0利率0手續費！4 .順序表中定位算法(查找值為x的結點序號最小值)的平均時間復雜度為A.O(1)B.O(log2n)C.O(n)D.O(n2)5 .元素的進棧次序為A,B,C,D,E,出棧的第一個元素為E,則第四個

3、出棧的元素為A.DB.CC.BD.A6 .帶頭結點的鏈隊列中，隊列頭和隊列尾指針分別為front和rear,則判斷隊列空的條件為A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL7 .深度為5的二叉樹，結點個數最多為A.31個B.32個C.63個D.64個8 .如果結點A有2個兄弟結點，結點B為A的雙親，則B的度為A.1B.3C.4D.5題9圖9 .將題9圖所示的一棵樹轉換為二叉樹，結點C是A.A的左孩子B.A的右孩子C.B的右孩子D.E的右孩子10 .n為圖的頂點個數，e為圖中弧的數目，則圖的拓撲排序算法的時間復雜度為A.O(n)B.O(e)C

4、.O(n-e)D.O(n+e)11 .無向圖的鄰接矩陣是A.對角矩陣B.稀疏矩陣C.上三角矩陣D.對稱矩陣12 .在具有101個元素的順序表中查找值為x的元素結點時，平均比較元素的次數為A.50B.51C.100D.10113 .構造散列函數的方法很多，常用的構造方法有A.數字分析法、除留余數法、平方取中法B.線性探測法、二次探測法、除留余數法C.線性探測法、除留余數法、鏈地址法D.線性探測法、二次探測法、鏈地址法14 .就平均時間性能而言，快速排序方法最佳，其時間復雜度為A.O(n)B.O(nlog2n)C.O(n2)D.O(1og2n)15 .下述算法中，不穩定的排序算法是A.直接插入排序

5、B.冒泡排序C.堆排序D.歸并排序非選擇題部分注意事項：用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題(本大題共13小題，每小題2分，共26分)16 .數據的基本單位是。17 .雙向循環鏈表中，在p所指結點的后面插入一個新結點*t,需要修改四個指針，分別為t->prior=P;t->next=p->next;p->next=t;。18 .在帶有頭結點的循環鏈表中，尾指針為rear,判斷指針P所指結點為首結點的條件是。19 .若線性表中最常用的操作是求表長和讀表元素，則順序表和鏈表這兩種存儲方式中，較節省時間的是20 .不含任何數據元素的棧稱為。

6、21 .稀疏矩陣一般采用的壓縮存儲方法是。22 .100個結點的二叉樹采用二叉鏈表存儲時，用來指向左、右孩子結點的指針域有個。23 .已知完全二叉樹的第5層有5個結點，則整個完全二叉樹有個結點。24 .n個頂點的有向圖G用鄰接矩陣A1.n,1.n存儲，其第i列的所有元素之和等于頂點Vi的。25 .具有10個頂點的有向完全圖的弧數為。26 .要完全避免散列所產生的堆積現象，通常采用解決沖突。27 .在長度為n的帶有崗哨的順序表中進行順序查找，查找不成功時，與關鍵字的比較次數為。28 .歸并排序算法的時間復雜度是。三、應用題(本大題共5小題，每小題6分，共30分)29 .稀疏矢I陣A如題29圖所示

7、，寫出該稀疏矩陣A的三元組表示法。0A 0000 0 00 0 00 0 57 0 0020800000000_題29圖30 .設二叉樹的中序遍歷序列為BDCEAFHG,后序遍歷序列為DECBHGFA，試畫出該二叉樹。31 .寫出題31圖所示無向圖的鄰接矩陣，并寫出每個頂點的度。題31圖32 .已知散列表的地址空間為0至13,散列函數H(k尸kmodll,(mod為求余運算)，待散列序列為(26,61,38,84,49),用二次探測法解決沖突，構造該序列的散列表，要求寫出處理沖突的過程。33 .將一組鍵值(80,50,65,13,86,35,96,57,39,79,59,15)應用二路歸并排序

8、算法從小到大排序，試寫出各趟的結果。四、算法設計題(本大題共2小題，每小題7分，共14分)34 .設單鏈表及鏈棧S的結構定義如下：typedefstructnodeDataTypedata;structnode*next;linkstack；編寫一個算法voidReverseList(1inkstack*head),借助于棧S將帶頭結點單鏈表head中序號為奇數的結點逆置，序號為偶數的結點保持不變。(例如：單鏈表的邏輯結構為(a1，a2,a3,電，a5,%),逆置后變為(a5,a2,a3,也，山，a6)o說明：棧的初始化運算用InitStack(S);進棧運算用Push(S,x);判?？者\算用Empty