常州大學(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、對于一個有向圖，使用鄰接矩陣存儲，判斷是否存在從頂點i到頂點j的邊的時間復(fù)雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)2、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)3、在一棵平衡二叉樹中，插入一個新節(jié)點后可能導(dǎo)致失衡，需要進行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整4、在一個具有n個節(jié)點的帶權(quán)有向圖中，若存在負權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用5、對于一個采用鏈表存儲的棧，若要獲取棧的大?。ㄔ財?shù)量），以下關(guān)于操作的時間復(fù)雜度的描述，哪一個是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由節(jié)點和邊組成。以下關(guān)于樹的說法中，錯誤的是？（）A.樹中的每個節(jié)點都有一個父節(jié)點（除了根節(jié)點）和零個或多個子節(jié)點。B.二叉樹是一種特殊的樹，每個節(jié)點最多有兩個子節(jié)點。C.樹可以用于實現(xiàn)文件系統(tǒng)、數(shù)據(jù)庫索引等。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。7、在一個哈希表中，若采用線性探測法解決哈希沖突，當(dāng)發(fā)生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機位置D.以上都不對8、設(shè)有一個廣義表L=(a,(b,c),d)，其長度和深度分別為？（）A.3和2B.3和3C.4和2D.4和39、棧和隊列在計算機科學(xué)中有很多應(yīng)用，以下關(guān)于它們的應(yīng)用場景的說法中，錯誤的是？（）A.?？梢杂糜趯崿F(xiàn)表達式求值、括號匹配等。B.隊列可以用于實現(xiàn)任務(wù)調(diào)度、消息隊列等。C.棧和隊列可以用于實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊列只能在編程語言的底層實現(xiàn)中使用，不能在實際應(yīng)用中直接使用。10、在一個鏈?zhǔn)酱鎯Φ年犃兄校M行入隊和出隊操作時，指針的移動方向分別是（）A.入隊向前，出隊向后B.入隊向后，出隊向前C.均向前D.均向后11、在一棵平衡二叉樹中，插入一個新結(jié)點后，可能需要進行的調(diào)整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調(diào)整12、設(shè)有一個具有n個頂點的有向圖，采用鄰接表存儲。若要計算每個頂點的出度，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項是恰當(dāng)?shù)模緼.O(n)B.O(n+e)C.O(n^2)D.O(e)13、對于一個用鏈表實現(xiàn)的棧，若要獲取棧中元素的個數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護一個計數(shù)器C.以上效率相同D.以上都不對14、在一個具有n個節(jié)點的無向圖中，若邊的數(shù)量遠遠小于n(n-1)/2，則適合使用哪種存儲方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以15、在一個具有n個節(jié)點的二叉樹中，若采用后序遍歷得到的節(jié)點序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定16、在一個具有n個節(jié)點的無向圖中，若要判斷兩個節(jié)點之間是否存在路徑，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.普里姆算法D.克魯斯卡爾算法17、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，若要刪除一條邊，平均需要修改多少個指針？（）A.1B.2C.eD.2e18、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序19、在一個鏈?zhǔn)酱鎯Φ年犃兄?，若隊頭指針為front，隊尾指針為rear，要刪除隊頭元素，需要進行的操作是？（）A.front=front->next;B.rear=front;C.rear=rear->next;D.front=NULL;20、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表存儲，則其空間復(fù)雜度為：A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入解釋在鏈表中，如何實現(xiàn)頭插法和尾插法創(chuàng)建鏈表，并比較它們在不同場景下的優(yōu)缺點。2、（本題10分）解釋如何在一個帶權(quán)無向圖中計算任意兩個頂點之間路徑的最大權(quán)值和最小值之差。3、（本題10分）詳細論述在利用二叉樹進行后序線索化的過程中，如何建立線索和遍歷線索二叉樹，并給出相應(yīng)的算法步驟和代碼示例。4、（本題10分）解釋在鏈表中刪除一個節(jié)點時，如何正確更新指針以保持鏈表的完整性，并舉例說明。三、設(shè)計題（本大