北京郵電大學(xué)《數(shù)據(jù)管理與數(shù)據(jù)庫(kù)》2022-2023學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)北京郵電大學(xué)《數(shù)據(jù)管理與數(shù)據(jù)庫(kù)》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則a85的地址為？（）A.33B.32C.18D.402、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向圖中，若邊的數(shù)量遠(yuǎn)遠(yuǎn)小于n(n-1)/2，則適合使用哪種存儲(chǔ)方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以3、在一個(gè)B樹(shù)中，每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-14、對(duì)于一個(gè)循環(huán)隊(duì)列，若隊(duì)列的最大容量為m，當(dāng)前front指針為5，rear指針為2，則隊(duì)列中的元素個(gè)數(shù)為（）A.7B.3C.m-3D.m-75、一棵哈夫曼樹(shù)中，葉子節(jié)點(diǎn)的編碼長(zhǎng)度一定（）非葉子節(jié)點(diǎn)的編碼長(zhǎng)度。A.大于B.等于C.小于D.不小于6、在一個(gè)用鄰接矩陣表示的無(wú)向圖中，矩陣中的元素表示什么？A.頂點(diǎn)之間的距離B.頂點(diǎn)之間是否有邊C.邊的權(quán)重D.以上都有可能7、在一個(gè)帶權(quán)無(wú)向圖中，使用普里姆算法構(gòu)造最小生成樹(shù)時(shí)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個(gè)連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對(duì)8、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持動(dòng)態(tài)集合的操作，如合并、查找等？（）A.鏈表B.二叉樹(shù)C.并查集D.哈希表9、在一個(gè)大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個(gè)元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個(gè)元素交換，然后從堆頂向下調(diào)整D.無(wú)需調(diào)整10、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關(guān)于桶排序的描述，錯(cuò)誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時(shí)間復(fù)雜度為O(n)C.空間復(fù)雜度較高D.適用于大規(guī)模數(shù)據(jù)排序11、在一個(gè)具有n個(gè)元素的二叉排序樹(shù)中，查找一個(gè)不存在的元素，其時(shí)間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)12、已知一個(gè)哈希表的長(zhǎng)度為11，哈希函數(shù)為H(key)=key%11，采用二次探測(cè)法處理沖突。若依次插入關(guān)鍵字15、38、61、84，則在查找關(guān)鍵字61時(shí)需要進(jìn)行幾次探測(cè)？（）A.1B.2C.3D.413、在一個(gè)用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列中，若隊(duì)頭指針front=5，隊(duì)尾指針rear=2，隊(duì)列容量為10，則隊(duì)列中的元素個(gè)數(shù)是多少？A.7B.6C.5D.414、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表存儲(chǔ)時(shí)，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)15、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個(gè)有向圖，通?？梢允褂媚姆N存儲(chǔ)結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可16、對(duì)于一棵二叉搜索樹(shù)，進(jìn)行中序遍歷得到的序列是一個(gè)有序序列。若對(duì)其進(jìn)行刪除操作，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.平均時(shí)間復(fù)雜度為O(logn)，最壞情況為O(n)B.時(shí)間復(fù)雜度始終為O(logn)C.平均時(shí)間復(fù)雜度為O(n)，最壞情況為O(nlogn)D.時(shí)間復(fù)雜度始終為O(n)17、在一個(gè)具有n個(gè)元素的大頂堆中，若要將堆頂元素與最后一個(gè)元素交換，然后調(diào)整堆，其時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)18、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，其深度為（以2為底取對(duì)數(shù)，向下取整）加1。若已知節(jié)點(diǎn)個(gè)數(shù)為100，則其深度為多少？（）A.6B.7C.8D.919、線段樹(shù)是一種用于處理區(qū)間查詢和更新的數(shù)據(jù)結(jié)構(gòu)。對(duì)于線段樹(shù)的應(yīng)用，以下說(shuō)法錯(cuò)誤的是（）A.可以快速計(jì)算給定區(qū)間內(nèi)元素的和B.可以用于查找區(qū)間內(nèi)的最大值和最小值C.構(gòu)建線段樹(shù)的時(shí)間復(fù)雜度為O(n)D.線段樹(shù)的空間復(fù)雜度與節(jié)點(diǎn)數(shù)量成正比20、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的反轉(zhuǎn)是一個(gè)常見(jiàn)的操作，以下關(guān)于鏈表反轉(zhuǎn)的實(shí)現(xiàn)方法，錯(cuò)誤的是（）A.使用三個(gè)指針依次遍歷并調(diào)整節(jié)點(diǎn)的鏈接關(guān)系B.遞歸方式實(shí)現(xiàn)時(shí)不需要額外的輔助空間C.迭代方式的時(shí)間復(fù)雜度為O(n)D.遞歸方式的空間復(fù)雜度比迭代方式低二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋如何對(duì)一個(gè)無(wú)序數(shù)組進(jìn)行堆排序，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。2、（本題10分）詳細(xì)說(shuō)明如何在一個(gè)有序數(shù)組中查找兩個(gè)數(shù)之差的絕對(duì)值最小的組合。3、（本題10分）對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，如何使用廣度優(yōu)先搜索算法計(jì)算頂點(diǎn)的度？4、（本題10分）對(duì)于一個(gè)用十字鏈表存儲(chǔ)的稀疏矩陣，解釋其存儲(chǔ)結(jié)構(gòu)和優(yōu)勢(shì)，說(shuō)明如何進(jìn)行矩陣的加法和乘法運(yùn)算。三、設(shè)計(jì)題（本大題共2個(gè)小