長安大學成教期末考試題及答案

一、單項選擇題（每題2分，共10題，20分）1.以下哪種數(shù)據(jù)結構是線性結構（）A.樹B.圖C.棧D.集合2.若某算法的時間復雜度用T(n)表示，其中n是問題規(guī)模，則T(n)=O(2^n)表示該算法（）A.是多項式時間算法B.是指數(shù)時間算法C.時間復雜度與n無關D.是常數(shù)時間算法3.下列排序算法中，平均時間復雜度最小的是（）A.冒泡排序B.選擇排序C.插入排序D.快速排序4.鏈表不具有的特點是（）A.可隨機訪問任一元素B.插入刪除不需要移動元素C.不必事先估計存儲空間D.所需空間與線性表長度成正比5.棧和隊列的共同點是（）A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點6.一棵完全二叉樹共有360個結點，則在該二叉樹中度為1的結點個數(shù)為（）A.0B.1C.180D.1817.具有3個結點的二叉樹有（）種不同形態(tài)。A.3B.4C.5D.68.對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（）A.log?nB.n/2C.nD.n+19.哈希表的平均查找長度與（）有關。A.哈希函數(shù)B.裝填因子C.處理沖突的方法D.以上都是10.下列關于圖的說法正確的是（）A.有向圖一定有環(huán)B.無向圖一定連通C.圖的鄰接矩陣表示法適用于稠密圖D.圖的鄰接表表示法適用于稀疏圖答案1.C2.B3.D4.A5.C6.B7.C8.C9.D10.D二、多項選擇題（每題2分，共10題，20分）1.以下屬于數(shù)據(jù)結構中邏輯結構的有（）A.線性結構B.樹形結構C.圖形結構D.順序結構2.以下哪些算法屬于貪心算法的應用（）A.迪杰斯特拉（Dijkstra）算法B.普里姆（Prim）算法C.克魯斯卡爾（Kruskal）算法D.哈夫曼編碼3.以下關于棧的描述正確的有（）A.棧是一種先進后出的數(shù)據(jù)結構B.?？梢杂脕韺崿F(xiàn)表達式求值C.棧在遞歸調(diào)用中起重要作用D.棧的插入和刪除操作只能在棧頂進行4.以下屬于二叉樹遍歷方式的有（）A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷5.以下排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.歸并排序C.基數(shù)排序D.選擇排序6.關于圖的存儲結構，下列說法正確的是（）A.鄰接矩陣適合存儲稠密圖B.鄰接表適合存儲稀疏圖C.十字鏈表是有向圖的一種存儲結構D.鄰接多重表是無向圖的一種存儲結構7.以下哪些數(shù)據(jù)結構可以用來實現(xiàn)優(yōu)先隊列（）A.堆B.棧C.隊列D.二叉排序樹8.下列關于算法的特性描述正確的有（）A.有窮性B.確定性C.可行性D.輸入輸出9.以下屬于線性表的存儲結構的有（）A.順序存儲結構B.鏈式存儲結構C.索引存儲結構D.散列存儲結構10.以下關于哈希表的說法正確的有（）A.哈希表的查找效率取決于哈希函數(shù)的設計B.處理哈希沖突的方法有開放定址法和鏈地址法等C.哈希表中裝填因子越大，查找效率越高D.哈希表可以用于快速查找和數(shù)據(jù)存儲答案1.ABC2.ABCD3.ABCD4.ABCD5.ABC6.ABCD7.A8.ABCD9.AB10.ABD三、判斷題（每題2分，共10題，20分）1.數(shù)據(jù)的邏輯結構與存儲結構是一一對應的。（）2.算法的時間復雜度是指執(zhí)行算法所需要的計算工作量。（）3.棧和隊列都是特殊的線性表。（）4.完全二叉樹的葉子結點只可能在最后兩層。（）5.排序算法中的穩(wěn)定性是指排序前后相同元素的相對位置不變。（）6.圖的廣度優(yōu)先搜索類似于樹的層次遍歷。（）7.順序存儲結構的優(yōu)點是存儲密度大，且插入、刪除操作效率高。（）8.哈希表中，裝填因子越大，發(fā)生沖突的可能性越小。（）9.二叉排序樹的中序遍歷序列是一個有序序列。（）10.任何一個遞歸算法都可以轉換為對應的非遞歸算法。（）答案1.×2.√3.√4.√5.√6.√7.×8.×9.√10.√四、簡答題（每題5分，共4題，20分）1.簡述線性表順序存儲結構和鏈式存儲結構的優(yōu)缺點。順序存儲優(yōu)點：存儲密度大，可隨機訪問；缺點：插入刪除操作需移動大量元素。鏈式存儲優(yōu)點：插入刪除效率高，無需連續(xù)存儲空間；缺點：存儲密度小，不可隨機訪問。2.簡述深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的基本思想。DFS思想：從起點開始，盡可能深地探索，直到無法繼續(xù)，再回溯。BFS思想：從起點開始，一層一層向外擴展探索。3.簡述堆排序的基本步驟。先將待排序序列構建成一個堆，然后將堆頂元素與堆尾元素交換，再對剩余元素重新調(diào)整成堆，重復此過程直到整個序列有序。4.簡述哈希表中處理沖突的開放定址法。開放定址法是當發(fā)生沖突時，通過某種探測序列在哈希表中尋找下一個空的地址來存放新元素，常見探測序列有線性探測、二次探測等。五、討論題（每題5分，共4題，20分）1.討論在實際應用中，如何選擇合適的數(shù)據(jù)結構和算法。要考慮問題規(guī)模、數(shù)據(jù)特點、時間和空間復雜度要求等。如數(shù)據(jù)量小且操作簡單，可選簡單數(shù)據(jù)結構；大數(shù)據(jù)量且對時間要求高，需選高效算法和合適數(shù)據(jù)結構，還得平衡時間和空間。2.討論排序算法在不同場景下的適用性。如數(shù)據(jù)量小且基本有序，冒泡、插入排序合適；大數(shù)據(jù)量，快速、歸并排序更優(yōu)；對穩(wěn)定性有要求，冒泡、歸并等穩(wěn)定排序可選；對空間要求高，原地排序算法優(yōu)先。3.討論圖的遍歷算法在實際生活中的應用。在地圖導航中，用廣度優(yōu)先搜索找最短路徑；在社交網(wǎng)絡分