鄭州大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》2021-2022學(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ù)結(jié)構(gòu)與算法分析》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)循環(huán)隊(duì)列，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAX_SIZE，那么判斷隊(duì)空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-12、在二叉樹(shù)中，判斷兩棵二叉樹(shù)是否完全相同，以下方法不正確的是（）A.同時(shí)進(jìn)行先序遍歷，比較節(jié)點(diǎn)值B.同時(shí)進(jìn)行中序遍歷，比較節(jié)點(diǎn)值C.同時(shí)進(jìn)行后序遍歷，比較節(jié)點(diǎn)值D.比較兩棵樹(shù)的節(jié)點(diǎn)數(shù)量3、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，若要在棧頂插入一個(gè)元素，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、若要在一棵二叉搜索樹(shù)中查找一個(gè)特定的值，平均時(shí)間復(fù)雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)5、在一個(gè)長(zhǎng)度為n的順序表中，刪除第i個(gè)元素（1<=i<=n）時(shí)，需要移動(dòng)的元素個(gè)數(shù)為：A.n-iB.i-1C.n-i+1D.i6、在一個(gè)具有n個(gè)元素的大頂堆中，插入一個(gè)新元素后，需要進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)7、已知一個(gè)有序表為{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值為35的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.48、已知一個(gè)完全二叉樹(shù)的節(jié)點(diǎn)總數(shù)為100，其葉子節(jié)點(diǎn)的個(gè)數(shù)為（）。A.49B.50C.51D.不確定9、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)LRU（最近最少使用）頁(yè)面置換算法？A.隊(duì)列B.棧C.哈希表D.雙鏈表10、一棵完全二叉樹(shù)的第5層（根為第1層）有16個(gè)葉子節(jié)點(diǎn)，則該完全二叉樹(shù)的節(jié)點(diǎn)總數(shù)最少為（）。A.47B.55C.63D.6411、對(duì)于一個(gè)具有n個(gè)元素的雙向鏈表，若要在第i個(gè)位置（1<=i<=n）之前插入一個(gè)新節(jié)點(diǎn)，平均需要修改多少個(gè)指針？（）A.1B.2C.3D.412、平衡二叉樹(shù)是一種特殊的二叉搜索樹(shù)，其目的是為了保證查找效率。以下哪種操作可能會(huì)導(dǎo)致平衡二叉樹(shù)失去平衡？A.插入節(jié)點(diǎn)B.刪除節(jié)點(diǎn)C.查找節(jié)點(diǎn)D.以上都可能13、在一個(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è)用數(shù)組實(shí)現(xiàn)的小根堆，若要將堆頂元素與最后一個(gè)元素交換，然后重新調(diào)整堆，以下關(guān)于調(diào)整的方向，哪一項(xiàng)是正確的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先從堆頂向下調(diào)整，再?gòu)亩训紫蛏险{(diào)整D.以上都不對(duì)15、在數(shù)據(jù)結(jié)構(gòu)中，棧是一種特殊的線性表，遵循先進(jìn)后出的原則。以下關(guān)于棧的操作，錯(cuò)誤的是（）A.入棧操作將元素添加到棧頂B.出棧操作取出并刪除棧頂元素C.可以在棧的任意位置進(jìn)行插入和刪除操作D.棧頂指針始終指向棧頂元素16、在數(shù)據(jù)結(jié)構(gòu)中，對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，使用二分查找算法查找一個(gè)特定元素，其平均時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)17、在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈表中，若要判斷鏈表是否為空，應(yīng)檢查？（）A.頭結(jié)點(diǎn)的指針是否為空B.頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的指針是否指向頭結(jié)點(diǎn)C.尾結(jié)點(diǎn)的指針是否為空D.尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的指針是否指向頭結(jié)點(diǎn)18、二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)，以下關(guān)于二叉樹(shù)的性質(zhì)的說(shuō)法中，錯(cuò)誤的是？（）A.二叉樹(shù)的每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。B.二叉樹(shù)的左子樹(shù)和右子樹(shù)是有順序的。C.滿二叉樹(shù)是一種特殊的二叉樹(shù)，所有的葉節(jié)點(diǎn)都在同一層。D.完全二叉樹(shù)是一種特殊的滿二叉樹(shù)，所有的節(jié)點(diǎn)都在同一層。19、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)LRU（最近最少使用）緩存淘汰策略？（）A.隊(duì)列B.棧C.哈希表D.雙向鏈表20、在一個(gè)長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入分析在一個(gè)具有n個(gè)元素的順序表中，如何進(jìn)行排序算法的性能比較和分析。2、（本題10分）簡(jiǎn)述哈希表的負(fù)載因子是什么，以及它對(duì)哈希表性能的影響。3、（本題10分）在圖的遍歷中，如何判斷一個(gè)圖是否為二部圖？請(qǐng)說(shuō)明具體方法。4、（本題10分）詳細(xì)論述在利用哈希表存儲(chǔ)整數(shù)數(shù)據(jù)時(shí)，如何確定哈希表的大小，以及如何處理哈希沖突以