北方民族大學《數(shù)據(jù)結構實驗》2021-2022學年期末試卷

自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁北方民族大學《數(shù)據(jù)結構實驗》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、已知一個圖的鄰接矩陣如下所示，則從頂點V1出發(fā)進行深度優(yōu)先遍歷，可能得到的頂點訪問序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V52、若一棵二叉樹的葉子節(jié)點數(shù)為n0，度為2的節(jié)點數(shù)為n2，則n0和n2之間的關系是？（）A.n0=n2-1B.n0=n2+1C.n0=2n2-1D.n0=2n2+13、若要在一棵二叉搜索樹中查找一個特定的值，平均時間復雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)4、在一個具有n個元素的順序存儲的循環(huán)隊列中，隊滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front5、以下哪種數(shù)據(jù)結構能夠在O(1)的時間復雜度內實現(xiàn)元素的隨機訪問？（）A.鏈表B.隊列C.棧D.數(shù)組6、對于一個具有n個頂點的無向圖，若其所有頂點的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.207、以下關于圖的存儲結構的描述，錯誤的是：A.鄰接矩陣適合存儲稠密圖B.鄰接表適合存儲稀疏圖C.十字鏈表是鄰接表和逆鄰接表的結合D.鄰接多重表只適合無向圖8、在一個循環(huán)隊列中，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，則判斷隊滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front9、以下哪種數(shù)據(jù)結構常用于實現(xiàn)優(yōu)先級隊列？（）A.二叉樹B.鏈表C.堆D.棧10、對于一個具有n個元素的有序鏈表，進行折半查找，其時間復雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進行折半查找11、在一個具有n個節(jié)點的完全二叉樹中，若底層從左到右依次編號，節(jié)點i的左孩子節(jié)點編號是多少（假設根節(jié)點編號為1）？A.2iB.2i+1C.i*2D.以上都不對12、對于一棵具有n個節(jié)點的二叉搜索樹，其平均查找長度的上限大約為？A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)13、在一個具有n個節(jié)點的無向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以14、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEABC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EACDB15、以下哪種數(shù)據(jù)結構常用于實現(xiàn)操作系統(tǒng)中的進程調度？A.隊列B.棧C.樹D.圖16、對于一個具有n個元素的冒泡排序，在最壞情況下，需要進行多少次比較操作？（）A.n(n-1)/2B.nC.n+1D.n-117、對于一個具有n個元素的待排序序列，若采用冒泡排序算法進行排序，在最壞情況下需要進行的比較次數(shù)為？（）A.n(n-1)/2B.nlognC.n-1D.n18、在一個具有n個元素的鏈表中，若要在表頭插入一個新元素，平均需要修改幾個指針？（）A.1B.2C.nD.n+119、以下哪種數(shù)據(jù)結構常用于實現(xiàn)字符串的最長公共子序列問題？A.二維數(shù)組B.棧C.隊列D.樹20、設有一個具有n個節(jié)點的二叉平衡樹，若要插入一個新節(jié)點并保持平衡，以下關于插入操作的平均時間復雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋在平衡二叉搜索樹中，如何通過調整策略降低樹的高度。2、（本題10分）詳細闡述在圖的最短路徑算法中，如何處理動態(tài)的邊權值變化。3、（本題10分）解釋線段樹在處理區(qū)間相交問題時的思路和算法。4、（本題10分）解釋如何在一個二叉搜索樹中進行查找操作的多線程優(yōu)化，給出算法步驟和實現(xiàn)代碼，并分析其線程安全和