南京信息工程大學(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分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個節(jié)點的帶權(quán)有向圖中，若存在負(fù)權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用2、已知一個帶權(quán)有向圖G=(V,E)，頂點集合V={1,2,3,4,5}，邊集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求從頂點1到頂點5的最短路徑，經(jīng)過的中間頂點依次為？（）A.2,4B.3,4C.2,3D.3,53、在一個用數(shù)組實現(xiàn)的循環(huán)隊列中，若隊頭指針front=5，隊尾指針rear=2，隊列容量為10，則隊列中的元素個數(shù)是多少？A.7B.6C.5D.44、在數(shù)據(jù)結(jié)構(gòu)中，對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素，其平均時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)5、對于一個具有n個元素的哈希表，若采用鏈地址法處理沖突，以下關(guān)于查找操作的平均時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個順序存儲的循環(huán)隊列中，隊頭指針front和隊尾指針rear都指向同一個位置時，隊列的狀態(tài)可能是？（）A.隊滿B.隊空C.既不滿也不空D.以上都有可能7、對于一個具有n個元素的冒泡排序，在最壞情況下，需要進(jìn)行多少次比較操作？（）A.n(n-1)/2B.nC.n+1D.n-18、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)字典操作（添加、刪除、查找），且平均時間復(fù)雜度較低？A.數(shù)組B.鏈表C.二叉搜索樹D.哈希表9、對于一個具有n個頂點和e條邊的無向連通圖，其生成樹中邊的條數(shù)為（）。A.nB.n-1C.eD.e-110、在一個具有n個元素的循環(huán)鏈表中，查找第i個元素（1<=i<=n），平均需要遍歷的節(jié)點個數(shù)約為？A.n/2B.nC.2nD.n/411、設(shè)有一個廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)12、在數(shù)據(jù)結(jié)構(gòu)中，塊狀鏈表結(jié)合了鏈表和數(shù)組的優(yōu)點，以下關(guān)于塊狀鏈表的特點，描述不正確的是（）A.適合頻繁的插入和刪除操作B.可以提高隨機(jī)訪問的效率C.每個塊內(nèi)部是有序的D.空間復(fù)雜度比普通鏈表低13、對于一個采用順序存儲結(jié)構(gòu)的完全二叉樹，若已知根節(jié)點在數(shù)組中的位置為1，則其第i個節(jié)點的左孩子節(jié)點在數(shù)組中的位置為？A.2iB.2i+1C.i*2D.i*2-114、對于一個具有n個元素的雙向循環(huán)鏈表，若要刪除第i個節(jié)點（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.515、對于一個具有n個節(jié)點的帶權(quán)有向圖，使用迪杰斯特拉算法求最短路徑，其時間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)16、在一個m行n列的二維數(shù)組中，按列優(yōu)先存儲時，元素aij的存儲地址為？（）A.LOC(a11)+[(j-1)*m+(i-1)]*dB.LOC(a11)+[(i-1)*m+(j-1)]*dC.LOC(a11)+[(j-1)*n+(i-1)]*dD.LOC(a11)+[(i-1)*n+(j-1)]*d17、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進(jìn)行先序遍歷，比較節(jié)點值B.同時進(jìn)行中序遍歷，比較節(jié)點值C.同時進(jìn)行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)圖的存儲？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊列D.數(shù)組和哈希表19、若一個鏈表的每個節(jié)點只包含數(shù)據(jù)域和指針域，且指針域只指向其后繼節(jié)點，這種鏈表稱為：A.單向鏈表B.雙向鏈表C.循環(huán)鏈表D.靜態(tài)鏈表20、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA二、簡答題（本大題共4個小題，共40分)1、（本題10分）在數(shù)據(jù)結(jié)構(gòu)中，闡述如何使用線段樹解決區(qū)間查詢和更新問題，給出算法步驟和實現(xiàn)代碼，并分析其性能優(yōu)勢。2、（本題10分）比較冒泡排序和堆排序在時間復(fù)雜度上的優(yōu)劣。3、（本題10分）詳細(xì)闡述在具有n個頂點的圖中，如何使用迪杰斯特拉（Dijkstra）算法求解每對頂點之間的最短路徑，并分析其時間復(fù)雜度。4、（本題10分）闡述如何在一個循環(huán)隊列中實現(xiàn)元素的入隊和出隊操作，給出算法步驟和實現(xiàn)代碼，并分析其時間復(fù)雜度和空間復(fù)雜