北京聯(lián)合大學《數(shù)據(jù)結(jié)構與算法（C描述）》2022-2023學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁北京聯(lián)合大學《數(shù)據(jù)結(jié)構與算法（C描述）》

2022-2023學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個元素的無序數(shù)組，若要對其進行排序，以下哪種算法在最壞情況下時間復雜度最高？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序2、對于一個具有n個元素的堆，進行刪除操作并調(diào)整堆的時間復雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、以下哪種數(shù)據(jù)結(jié)構常用于實現(xiàn)字符串的最長公共子序列問題？A.二維數(shù)組B.棧C.隊列D.樹4、在數(shù)據(jù)結(jié)構中，塊狀鏈表結(jié)合了鏈表和數(shù)組的優(yōu)點，以下關于塊狀鏈表的特點，描述不正確的是（）A.適合頻繁的插入和刪除操作B.可以提高隨機訪問的效率C.每個塊內(nèi)部是有序的D.空間復雜度比普通鏈表低5、在數(shù)據(jù)結(jié)構中，伸展樹（SplayTree）通過自調(diào)整保持較好的性能，以下關于伸展樹的操作，不正確的是（）A.查找操作會將被查找的節(jié)點旋轉(zhuǎn)到根節(jié)點B.插入操作可能會引起多次旋轉(zhuǎn)C.伸展樹的平均性能較好D.伸展樹的空間復雜度較高6、在數(shù)據(jù)結(jié)構中，優(yōu)先隊列可以用堆來實現(xiàn)，以下關于堆調(diào)整的描述，錯誤的是（）A.插入元素時，從下往上調(diào)整堆B.刪除堆頂元素時，從上往下調(diào)整堆C.調(diào)整堆的過程中，節(jié)點的值可能會交換D.調(diào)整堆的時間復雜度與堆的大小無關7、在數(shù)據(jù)結(jié)構中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結(jié)束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復訪問8、在一個哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法9、在數(shù)據(jù)結(jié)構中，哈弗曼編碼是一種用于數(shù)據(jù)壓縮的編碼方式，以下關于哈弗曼編碼的描述，錯誤的是（）A.出現(xiàn)頻率高的字符編碼較短B.編碼是唯一的C.解碼過程簡單D.對所有數(shù)據(jù)都能達到很好的壓縮效果10、設有一個具有n個頂點的帶權無向圖，使用普里姆（Prim）算法求最小生成樹。在算法執(zhí)行過程中，需要選擇一個頂點作為起始點。以下關于起始點選擇對算法時間復雜度的影響，哪一個是恰當?shù)模緼.起始點的選擇對時間復雜度沒有影響B(tài).選擇不同的起始點可能導致時間復雜度不同C.選擇頂點度最小的作為起始點可以降低時間復雜度D.選擇頂點度最大的作為起始點可以降低時間復雜度11、在一個具有n個元素的小根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進行調(diào)整，其時間復雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)12、設有一個字符串S="helloworld"，要計算字符串S的長度（不包括結(jié)束符'\0'），以下函數(shù)正確的是？（）A.intlength(char*s){intcount=0;while(*s!='\0'){count++;s++;}returncount;}B.intlength(char*s){intcount=0;for(;*s!='\0';s++){count++;}returncount;}C.intlength(char*s){intcount=0;do{count++;s++;}while(*s!='\0');returncount;}D.intlength(char*s){intcount=0;while(s[count]!='\0'){count++;}returncount;}13、在一個順序存儲的棧中，若棧頂指針top為-1，則表示棧（）A.已滿B.為空C.已損壞D.無法確定14、對于一個具有n個頂點和e條邊的無向圖，使用深度優(yōu)先搜索算法進行遍歷。以下關于算法中使用的標記數(shù)組的空間復雜度的描述，哪一項是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)15、對于一個用鏈表表示的線性表，在表頭插入一個新元素和在表尾插入一個新元素，哪個操作更復雜？A.表頭插入B.表尾插入C.復雜度相同D.取決于鏈表長度16、在一個具有n個元素的單鏈表中，若要在第i個位置（1<=i<=n）插入一個新元素，平均需要遍歷多少個節(jié)點？（）A.i-1B.iC.(i-1)/2D.i/217、對于一個具有n個元素的雙向循環(huán)鏈表，若要刪除第i個節(jié)點（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.518、數(shù)據(jù)結(jié)構是計算機科學中重要的基礎課程，它研究數(shù)據(jù)的組織、存儲和管理方式。以下關于數(shù)據(jù)結(jié)構的說法中，錯誤的是？（）A.數(shù)據(jù)結(jié)構可以分為線性結(jié)構和非線性結(jié)構兩大類。B.線性結(jié)構包括數(shù)組、鏈表、棧和隊列等。C.非線性結(jié)構包括樹、圖和集合等。D.數(shù)據(jù)結(jié)構只與編程語言有關，與實際應用場景無關。19、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD20、在一個具有n個頂點的連通圖中，生成樹的邊數(shù)一定為？（）A.n-1B.nC.n+1D.2n二、簡答題（本大題共4個小題，共40分)1、（本題10分）在一個二叉搜索樹中，如何實現(xiàn)刪除操作并保證樹的性質(zhì)不變？2、（本題10分）闡述后綴樹在信息檢索中的應用和優(yōu)化策略。3、（本題10分）詳細說明如何在一個具有n個元素的有序數(shù)組中，進行二分查找的非遞歸實現(xiàn)，并分析其時間復雜度和空間復雜度。4、（本題10分）論