菏澤學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁菏澤學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)帶頭結(jié)點(diǎn)的雙向鏈表中，若要在p所指結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)q，需要修改幾個(gè)指針？（）A.2B.4C.6D.82、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用插入排序進(jìn)行排序，其最壞情況下的時(shí)間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)3、以下關(guān)于樹的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是不正確的？（）A.孩子兄弟表示法可以方便地實(shí)現(xiàn)樹的遍歷B.雙親表示法便于查找一個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)C.孩子鏈表表示法在處理多叉樹時(shí)空間利用率較高D.以上存儲(chǔ)結(jié)構(gòu)在時(shí)間復(fù)雜度上沒有明顯差異4、在一個(gè)用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列中，若隊(duì)頭指針front=5，隊(duì)尾指針rear=2，隊(duì)列容量為10，則隊(duì)列中的元素個(gè)數(shù)是多少？A.7B.6C.5D.45、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4,5，下列序列中不可能是出棧序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,56、在一棵二叉搜索樹中，刪除一個(gè)只有左子樹的節(jié)點(diǎn)，其右子樹的節(jié)點(diǎn)需要（）A.替換被刪除節(jié)點(diǎn)B.保持不動(dòng)C.全部刪除D.移動(dòng)到左子樹7、在一棵平衡二叉樹中，插入一個(gè)新結(jié)點(diǎn)后，可能需要進(jìn)行的調(diào)整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調(diào)整8、對(duì)于一個(gè)具有n個(gè)元素的無序數(shù)組，使用快速排序算法進(jìn)行排序，在平均情況下的空間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖中，使用鄰接矩陣存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷，其時(shí)間復(fù)雜度為？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)10、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，若采用Prim算法生成最小生成樹，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)11、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在有向圖中，頂點(diǎn)的入度是指指向該頂點(diǎn)的邊的數(shù)量。若要計(jì)算一個(gè)有向圖中所有頂點(diǎn)的入度，哪種算法較為合適？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.以上都可以12、在一個(gè)大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個(gè)元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個(gè)元素交換，然后從堆頂向下調(diào)整D.無需調(diào)整13、在數(shù)據(jù)結(jié)構(gòu)中，對(duì)于線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，以下說法正確的是：順序存儲(chǔ)結(jié)構(gòu)可以隨機(jī)訪問元素，但插入和刪除操作效率較低；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)插入和刪除操作方便，但不能隨機(jī)訪問。那么在頻繁進(jìn)行插入和刪除操作的情況下，應(yīng)優(yōu)先選擇哪種存儲(chǔ)結(jié)構(gòu)？（）A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.兩者均可D.無法確定14、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？（）A.二叉樹B.鏈表C.堆D.棧15、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個(gè)有向圖，通?？梢允褂媚姆N存儲(chǔ)結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可16、對(duì)于一個(gè)具有n個(gè)元素的堆排序，其空間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持動(dòng)態(tài)集合的操作，如合并、查找等？（）A.鏈表B.二叉樹C.并查集D.哈希表18、在一個(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)19、對(duì)于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的棧，若要判斷棧是否已滿，應(yīng)判斷？（）A.top==n-1B.top==nC.top>=n-1D.top>=n20、若要對(duì)一個(gè)具有n個(gè)元素的無序數(shù)組進(jìn)行排序，以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述在一個(gè)具有n個(gè)元素的有序鏈表中，如何進(jìn)行合并操作，使其合并后仍然有序。2、（本題10分）詳細(xì)說明如何在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中計(jì)算每個(gè)頂點(diǎn)的強(qiáng)連通分量大小。3、（本題10分）解釋在平衡二叉搜索樹中，刪除操作可能導(dǎo)致的不平衡情況及相應(yīng)的調(diào)整方法。4、（本題10分）詳細(xì)闡述在選擇排序的變體中，如堆選擇排序，如何利用堆的性質(zhì)優(yōu)化選擇過程。三、設(shè)計(jì)題（