2017年山東青島大學數(shù)據(jù)結構考研真題

》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2017年山東青島大學數(shù)據(jù)結構考研真題一、單項選擇題（本大題共10道小題，每小題2分，共20分）1．計算機算法指的是（）。A．計算方法B.排序方法C.解決問題的步驟序列D.存儲結構2．鏈表不具有的特點是（）。A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比3．連續(xù)存儲設計時，存儲單元的地址（）。A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)4．一個遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分5．棧和隊列的共同點是（）。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點6．任何一棵二叉樹的葉子結點在先序、中序和后序遍歷中的相對次序（）。A．不發(fā)生改變B．發(fā)生改變C．不能確定D．以上都不對7．由帶權為{8，2，5，7}的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為（）。A．23B．37C．46D438．若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索可以訪問圖中所有的頂點，則該圖一定是（）圖。A．非連通B．連通C．強連通D．有向9．適用于折半查找的表的存儲方式及元素排列要求為（）。A．鏈接方式存儲，元素無序B．鏈接方式存儲，元素有序C．順序方式存儲，元素無序D．順序方式存儲，元素有序10．對n個關鍵字作快速排序，在最壞情況下，算法的時間復雜度是（）。A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)二、簡答題（本大題共6道小題，每題5分，共30分）1．如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？2．有5個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？3．簡述樹與二叉樹的轉(zhuǎn)化方法。試舉一個例子說明。4．簡要說明圖的各種遍歷方法。5．簡述順序查找和折半查找的優(yōu)缺點。6．簡要說明歸并排序的基本思想。三、綜合應用題（本大題共4道小題，每題12分，共48分）1．已知一棵二叉樹的中序遍歷序列為BCAFEC，后序遍歷序列為CBECFA，試畫出該二叉樹，并給出該二叉樹的先序序列。2．對于下圖所示的有向圖，試給出：(1)鄰接表；(2)從頂點v1出發(fā)的深度優(yōu)先遍歷序列；(3)從頂點v3出發(fā)的廣度優(yōu)先遍歷序到。3．設將關鍵字集合Keys=｛2,6,7,5,4,3,1｝中的元素依次插入到一個空的平衡二叉排序樹中，畫出所得的平衡二叉排序樹。假設查找每一個元素的概率相同，查找此平衡二叉樹排序中任一結點的平均查找長度為多少？4．某設待排序的關鍵字集合為{12，2，16，30，28，10，16*，20，6，18}，試分別回答下面的問題。①給出希爾排序（增量選取5，3，1）的結果；②寫出快速排序第一趟之后的狀態(tài)；③把關鍵字集合調(diào)整成堆頂元素取最大值的堆。四、算法分析題（本大題共3道小題，每題10分，共30分）1．下面的算法是在帶頭結點的單鏈表L中，刪除第i個元素，并由e返回其值，請在空白處填入正確的語句。2．閱讀下面的代碼，試說明算法的功能。3．下面代碼是中序遍歷二叉樹T的非遞歸算法。請在空白處填入正確的語句。

五、算法設計題（本大題共2道小題，每題11分，共22分）1．已知L1、L2分別為兩個循環(huán)單鏈表（帶頭結點）的指針