沈陽城市學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁沈陽城市學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的無序數(shù)組中，使用選擇排序進行排序。以下關(guān)于選擇排序的時間復(fù)雜度的描述，哪一項是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)2、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB3、以下哪種數(shù)據(jù)結(jié)構(gòu)在處理頻繁的插入和刪除操作時，不需要移動大量元素？（）A.數(shù)組B.鏈表C.棧D.隊列4、對于一個具有n個元素的哈希表，負(fù)載因子越大，發(fā)生沖突的可能性如何變化？（）A.越大B.越小C.不變D.不確定5、對于一個采用鏈?zhǔn)酱鎯Φ年犃?，若隊頭指針和隊尾指針相同，則隊列的狀態(tài)為：A.隊空B.隊滿C.不確定D.隊列中只有一個元素6、在一個循環(huán)隊列中，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，則判斷隊滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front7、對于一個具有n個節(jié)點的完全二叉樹，若底層從左到右填充，則第i個節(jié)點的左孩子節(jié)點的編號為？A.2iB.2i+1C.i*2D.i*2+18、在一個具有n個元素的線性表中，采用順序查找法查找一個特定元素，若查找成功，平均查找長度為？（）A.(n+1)/2B.n/2C.lognD.n9、在一個具有n個節(jié)點的二叉樹中，若每個節(jié)點都有左右孩子，則葉子節(jié)點的數(shù)量與度為2的節(jié)點數(shù)量有什么關(guān)系？A.葉子節(jié)點數(shù)量=度為2的節(jié)點數(shù)量+1B.葉子節(jié)點數(shù)量=度為2的節(jié)點數(shù)量-1C.葉子節(jié)點數(shù)量=度為2的節(jié)點數(shù)量D.以上都不對10、在一個具有n個元素的雙向鏈表中，若要刪除尾結(jié)點，需要修改幾個指針？（）A.1B.2C.3D.411、在一個具有n個節(jié)點的二叉樹中，若采用后序遍歷得到的節(jié)點序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定12、在一個鏈?zhǔn)酱鎯Φ木€性表中，若要刪除第i個元素（1<=i<=n），需要找到其前驅(qū)節(jié)點的時間復(fù)雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)13、在一個長度為n的有序線性表中進行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)14、對于一個具有n個節(jié)點的線索二叉樹，若n個節(jié)點中有m個空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-115、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)優(yōu)先級隊列？A.鏈表B.隊列C.棧D.堆16、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)表達式求值？A.二叉樹B.棧C.隊列D.哈希表17、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則存儲空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)18、在一個循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，若rear>front，則隊列中的元素個數(shù)為？A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE19、對于一個有向無環(huán)圖，進行拓?fù)渑判蚩梢缘玫揭粋€線性的序列。以下關(guān)于拓?fù)渑判虻恼f法，錯誤的是？（）A.可以使用深度優(yōu)先搜索來實現(xiàn)B.結(jié)果可能不唯一C.若存在回路則無法進行拓?fù)渑判駾.其時間復(fù)雜度為O(n2)20、對于一個具有n個元素的有序鏈表，進行二分查找的時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.不能進行二分查找二、簡答題（本大題共4個小題，共40分)1、（本題10分）說明二叉樹的遍歷算法在二叉樹的葉子節(jié)點之和問題、樹的直徑問題中的應(yīng)用。2、（本題10分）深入探討在一個具有n個元素的二叉搜索樹中，如何進行插入操作的優(yōu)化。3、（本題10分）詳細(xì)說明如何在一個具有n個元素的堆中，進行刪除操作，并分析其時間復(fù)雜度和空間復(fù)雜度。4、（本題10分）詳細(xì)解釋棧這種數(shù)據(jù)結(jié)構(gòu)的特點和操作，以及它在計算機程序中的常見應(yīng)用場景，比如表達式求值。三、設(shè)計題（本大