全國10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

全國201310月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題精品好資料-精品好資料-如有侵權(quán)請聯(lián)系網(wǎng)站刪除精品好資料-精品好資料-如有侵權(quán)請聯(lián)系網(wǎng)站刪除考試結(jié)束前

全國2013年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。選擇題部分注意事項：在答題紙規(guī)定的位置上。2B鉛筆把答題紙上對應(yīng)題目的答案標(biāo)號涂黑。如需改動，用橡皮擦干凈后，再選涂其他答案標(biāo)號。不能答在試題卷上。一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”黑。錯涂、多涂或未涂均無分。下列幾種算法時間復(fù)雜度中，最大的是A．O（1）C.O（nlog2n）

B.O（n）D.O（n2）數(shù)據(jù)結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列形成一條“鏈”的結(jié)構(gòu)是集合C.樹形結(jié)構(gòu)

B.圖結(jié)構(gòu)D.線性結(jié)構(gòu)100的順序表中做插入運算，平均移動元素的次數(shù)為A．25C.50

B.33D.100已知尾指針的單向循環(huán)鏈表中，在第一個結(jié)點后面插入一個新結(jié)點，該算法的時間復(fù)雜度為A．O（1） B.O（log2n）C.O（n） D.O(n2)下列表述正確的是棧空時出棧產(chǎn)生“上溢”，棧滿時進棧產(chǎn)生“下溢B.?？諘r出棧產(chǎn)生“下溢”，棧滿時進棧產(chǎn)生“上溢”C.?？諘r出棧和棧滿時進棧均產(chǎn)生“上溢”D.?？諘r出棧和棧滿時進棧均產(chǎn)生“下溢”6.隊列操作的原則是A.先進先出 進先出C.先進后出 只進不出6的滿二叉樹有A．63個結(jié)點 B.64個結(jié)點C.127個結(jié)點 D.128個結(jié)點3342213個，則度為0的結(jié)點有A.8個 B.10個C.11個 D.12個T220個，則葉子結(jié)點數(shù)為A．19個 B.20個C.21個 D.22個10個葉結(jié)點的哈夫曼樹中共有A．10個結(jié)點 B.11個結(jié)點C.19個結(jié)點 D.21個結(jié)點求圖中兩個結(jié)點之間的最短路徑采用的算法是廣度優(yōu)先搜索（BFS）C.普里姆（Prim）算法A．log2nC.n/2二叉排序樹中，根的

克魯斯卡爾（Kruskal）算法D.迪杰斯特拉（Dijkstra）B.（n-1）/2D.（n+1）/2A．左子樹是二叉排序樹、右子樹不一定是二叉排序樹B.左子樹是二叉排序樹、右子樹也是二叉排序樹C.左子樹不一定是二叉排序樹、右子樹是二叉排序樹D.左子樹不一定是二叉排序樹、右子樹也不一定是二叉排序樹14．冒泡排序的時間復(fù)雜度為A．O(n)C.O(n2)關(guān)于穩(wěn)定性的表述，正確的是

B.O(nlog2n)D.O(log2n)A．穩(wěn)定性是排序方法本身的特性，與數(shù)據(jù)無關(guān)B.穩(wěn)定性不是排序方法本身的特性，與數(shù)據(jù)有關(guān)C.穩(wěn)定性是排序方法本身的特性，與數(shù)據(jù)有關(guān)D.非選擇題部分注意事項：用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題(本大題共13小題，每小題2分，共26分)數(shù)據(jù)中不可分割的最小標(biāo)識單位是 。p所指結(jié)點的后面插入一個新結(jié)點*t，需要修改四個指針，分別為：t->prior=p； ；p->next->prior=t；p->next=t；。headp所指結(jié)點為首結(jié)點的條件是 。1，2，3，…，nnk個出棧的元素是 。在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為 。21．100個結(jié)點的二叉樹采用三叉鏈表存儲時，空指針域NULL有 個。某二叉樹的先序遍歷序列為ABKLMNO，中序遍歷序列為BLKANMO，則該二叉樹中結(jié)點A右孩子為結(jié)點 。一個二叉樹的最少結(jié)點個數(shù)為 。圖中第一個頂點和最后一個頂點相同的路徑稱為回路。除第一個頂點和最后一個頂點相同外其余頂點不重復(fù)的回路，稱為 。設(shè)查找表有n個數(shù)據(jù)元素，則二分查找算法的平均查找長度為 。用鍵值通過散列函數(shù)獲取存儲位置的這種存儲方式構(gòu)造的存儲結(jié)構(gòu)稱為 。若在線性表中采用二分查找法查找元素，則該線性表必須按值有序，并且采用 存儲結(jié)構(gòu)。堆分為最小堆和最大堆，若鍵值序列值序列{k1,k2,…，kn}。

,…，kn

}，滿足kik2i (i1,2,kk

,n)，則這n個鍵2三、應(yīng)用題(本大題共5小題，每小題6分，共30分)X，Y，Z，試寫出出棧的所有可能的輸出序列及其操作步驟。精品好資料-如有侵權(quán)請聯(lián)系網(wǎng)站刪除設(shè)二叉樹的先序遍歷序列為DCBAHEIFG，中序遍歷序列為ABCHDIEFG，試畫 該二叉樹寫 后序遍歷序列。已知連通帶權(quán)圖如題31圖所示，試?yán)闷绽锬罚≒rim）算法，從頂點A 發(fā)，構(gòu)造它的最小生成樹，畫 構(gòu)造過程。題31圖32．給定表（28，15，55，3，71，75，10，22，56），試按元素在表中的順序?qū)⑺鼈円来尾迦胍怀跏紩r為空的二叉排序樹，畫 插入完成后的二叉排序樹。33．應(yīng)用直接選擇排序算法，對初始關(guān)鍵字序列為48，35，61，98，82，18，29，48的記錄進行從小到大排序，寫 排序過程和結(jié)果。四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)34.單鏈表的結(jié)點結(jié)構(gòu)定義如下：typedefstructnode{intdata;structnode}Node,*LinkList;試編寫在帶頭結(jié)點的單鏈表head中查找第1個元素值小于x的結(jié)點的實現(xiàn)算法Node*GetLinklist(LinkListhead，intx)，若找到，則返回指向該結(jié)點的指針，否則返回NULL。35．假設(shè)樹采用孩子兄弟鏈表表示法，其結(jié)構(gòu)定義如下：t