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

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記。…………密………………封………………線…………第1頁，共1頁北方民族大學(xué)

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