江蘇科技大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁江蘇科技大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個具有n個元素的順序表中，要在中間位置插入一個新元素，平均移動元素的個數(shù)約為？A.n/2B.nC.lognD.12、在一個具有n個元素的雙向鏈表中，在p所指的節(jié)點(diǎn)之后插入一個新節(jié)點(diǎn)q，其操作步驟為（）。A.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B.q->next=p->next;q->prior=p;p->next=q;p->next->prior=q;C.p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D.p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;3、對于一個棧，進(jìn)行入棧和出棧操作時，若棧頂指針top初始值為-1，當(dāng)進(jìn)行5次入棧和3次出棧操作后，top的值為多少？（）A.1B.2C.3D.44、已知一個棧的進(jìn)棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,55、在一個具有n個頂點(diǎn)和e條邊的無向圖中，采用鄰接表存儲，其時間復(fù)雜度為？（）A.O(n+e)B.O(n2)C.O(e2)D.O(ne)6、在數(shù)據(jù)結(jié)構(gòu)中，紅黑樹的插入操作可能會導(dǎo)致樹的不平衡，需要進(jìn)行調(diào)整。以下關(guān)于調(diào)整過程的描述，不正確的是（）A.可能需要進(jìn)行顏色修改和旋轉(zhuǎn)操作B.調(diào)整后的紅黑樹仍然滿足紅黑樹的性質(zhì)C.調(diào)整的目的是使樹的高度盡量降低D.每次插入操作都需要進(jìn)行多次調(diào)整7、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，有鄰接矩陣和鄰接表兩種存儲方式。對于一個稀疏圖，以下說法正確的是（）A.鄰接矩陣比鄰接表更節(jié)省存儲空間B.鄰接表更適合用于存儲和遍歷C.兩種存儲方式的時間復(fù)雜度相同D.稀疏圖的邊數(shù)很少，節(jié)點(diǎn)數(shù)很多8、在一個具有n個元素的棧中，若要獲取棧底元素但不刪除，需要進(jìn)行多少次操作？（）A.1B.n-1C.nD.n+19、在一個帶頭結(jié)點(diǎn)的雙向鏈表中，若要在p所指結(jié)點(diǎn)之后插入一個新結(jié)點(diǎn)q，需要修改幾個指針？（）A.2B.4C.6D.810、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個有向圖，通?？梢允褂媚姆N存儲結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可11、哈希表的沖突解決方法和性能優(yōu)化可以用于提高哈希表的效率，以下關(guān)于它們的說法中，錯誤的是？（）A.開放定址法和鏈地址法是哈希表的兩種主要沖突解決方法，它們各有優(yōu)缺點(diǎn)。B.可以通過調(diào)整哈希函數(shù)、增加哈希表的大小和采用二次探測等方法來優(yōu)化哈希表的性能。C.哈希表的性能優(yōu)化需要根據(jù)實(shí)際情況進(jìn)行選擇，不同的應(yīng)用場景可能需要不同的優(yōu)化方法。D.哈希表的沖突解決方法和性能優(yōu)化只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價值。12、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，以下關(guān)于二叉樹的性質(zhì)的說法中，錯誤的是？（）A.二叉樹的每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)。B.二叉樹的左子樹和右子樹是有順序的。C.滿二叉樹是一種特殊的二叉樹，所有的葉節(jié)點(diǎn)都在同一層。D.完全二叉樹是一種特殊的滿二叉樹，所有的節(jié)點(diǎn)都在同一層。13、若一棵二叉樹的葉子節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2，則n0和n2之間的關(guān)系是？（）A.n0=n2-1B.n0=n2+1C.n0=2n2-1D.n0=2n2+114、以下關(guān)于樹的遍歷算法的描述，哪一項(xiàng)是不正確的？（）A.先序遍歷先訪問根節(jié)點(diǎn)B.中序遍歷先訪問左子樹C.后序遍歷先訪問右子樹D.三種遍歷算法都可以用遞歸或非遞歸方式實(shí)現(xiàn)15、一棵完全二叉樹的第5層（根為第1層）有16個葉子節(jié)點(diǎn)，則該完全二叉樹的節(jié)點(diǎn)總數(shù)最少為（）。A.47B.55C.63D.6416、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)17、對于一個用鄰接矩陣存儲的圖，若要判斷兩個頂點(diǎn)之間是否存在邊，時間復(fù)雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)18、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖19、在一個具有n個節(jié)點(diǎn)的二叉樹中，若采用后序遍歷得到的節(jié)點(diǎn)序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定20、以下哪種排序算法對大規(guī)模數(shù)據(jù)排序時，通常不被優(yōu)先選擇？A.冒泡排序B.插入排序C.快速排序D.歸并排序二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)說明隊列的特點(diǎn)和基本操作，闡述循環(huán)隊列是如何解決順序隊列中“假溢出”問題的，并給出循環(huán)隊列的隊空和隊滿的判斷條件。2、（本題10分）詳細(xì)論述在利用哈希表存儲對象時，如何處理對象的相等性判斷和哈希值計算，以保證正確的存儲和查找。3、（本題10分）詳細(xì)闡述在一個具有n個頂點(diǎn)和e條邊的帶權(quán)有向圖中，如何使用迪杰斯特拉算法求解單源最短路徑問題。4、（本題10分）詳細(xì)說明如何在一個具有n個元素的隊列中，實(shí)現(xiàn)元素