北方民族大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法實驗》2021-2022學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁北方民族大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法實驗》2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進(jìn)行先序遍歷，比較節(jié)點值B.同時進(jìn)行中序遍歷，比較節(jié)點值C.同時進(jìn)行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量2、在循環(huán)鏈表中，尾指針rear指向鏈表的尾節(jié)點，若要在鏈表中插入一個新的節(jié)點，使其成為新的尾節(jié)點，以下操作正確的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;3、對于一個棧，進(jìn)行入棧和出棧操作時，若棧頂指針top初始值為-1，當(dāng)進(jìn)行5次入棧和3次出棧操作后，top的值為多少？（）A.1B.2C.3D.44、已知一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的右子樹為空的條件是？（）A.A為根節(jié)點B.B為根節(jié)點C.C為根節(jié)點D.無法確定5、樹的遍歷方式有多種，以下關(guān)于它們的說法中，錯誤的是？（）A.前序遍歷是先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹。B.中序遍歷是先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。C.后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。6、設(shè)有一個長度為n的順序表，要在第i個元素之前插入一個新元素，并且移動元素的平均次數(shù)為n/2，則插入算法的平均時間復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)7、對于一個有向圖進(jìn)行深度優(yōu)先遍歷，若從頂點v開始，訪問完v的鄰接點后，接著應(yīng)該訪問哪個頂點？（）A.按照頂點編號順序的下一個未訪問頂點B.v的第一個鄰接點C.任意一個未訪問的鄰接點D.以上都不對8、設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為：A.連接B.模式匹配C.求子串D.求串長9、以下哪種數(shù)據(jù)結(jié)構(gòu)可以快速查找一個有序數(shù)組中的中位數(shù)？A.二叉搜索樹B.堆C.哈希表D.鏈表10、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)字典操作，并且能夠快速查找、插入和刪除元素？（）A.棧B.隊列C.二叉搜索樹D.數(shù)組11、在一個鏈?zhǔn)酱鎯Φ臈Ｖ?，若要在棧頂插入一個元素，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、在一個循環(huán)隊列中，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，則判斷隊滿的條件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front13、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一個元素，其存儲地址為1，每個元素占一個存儲單元，則a85的地址為？（）A.33B.32C.18D.4014、以下關(guān)于線性表的描述，正確的是：A.線性表的元素在邏輯上和存儲上都必須是連續(xù)的B.線性表只能采用順序存儲結(jié)構(gòu)C.線性表的長度是固定不變的D.線性表可以是空表，即不含任何元素15、對于一個具有n個元素的哈希表，負(fù)載因子（loadfactor）為0.7，當(dāng)表中元素數(shù)量超過一定閾值時需要進(jìn)行擴容。以下關(guān)于擴容操作的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(1)B.O(n)C.O(logn)D.O(nlogn)16、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)LRU（最近最少使用）緩存淘汰策略？（）A.隊列B.棧C.哈希表D.雙向鏈表17、以下哪種數(shù)據(jù)結(jié)構(gòu)可以高效地支持集合的并、交、差等操作？A.二叉搜索樹B.哈希表C.并查集D.平衡二叉樹18、對于一個采用順序存儲的棧，若要判斷棧是否為空，以下哪種方法是最有效的？A.檢查棧頂元素是否為NULLB.檢查棧頂指針是否為-1C.檢查棧頂指針是否等于棧的最大容量D.檢查棧中元素的數(shù)量是否為019、一個有序序列為{12,18,24,35,47,50,62,83,90,115,134}，當(dāng)用二分法查找值為90的元素時，需要比較的次數(shù)是（）。A.1B.2C.3D.420、在一棵二叉搜索樹中，刪除一個有兩個子節(jié)點的節(jié)點時，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點B.用右子樹的最小值替代該節(jié)點C.隨機選擇左子樹或右子樹的節(jié)點替代D.不進(jìn)行替代，直接刪除二、簡答題（本大題共4個小題，共40分)1、（本題10分）簡述數(shù)據(jù)結(jié)構(gòu)中棧的定義、特點及基本操作，并舉例說明棧在實際中的應(yīng)用。2、（本題10分）解釋什么是樹狀數(shù)組數(shù)據(jù)結(jié)構(gòu)，說明其特點和應(yīng)用場景，并闡述如何進(jìn)行區(qū)間求和和單點更新操作。3、（本題10分）論述伸展樹在處理有序數(shù)據(jù)時的性能特點和優(yōu)化方法。4、（本題10分）論述AVL樹在進(jìn)行旋轉(zhuǎn)操作時，如何保持二叉搜索樹的性質(zhì)