鄭州大學《數(shù)據(jù)結(jié)構(gòu)與算法分析》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁鄭州大學

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