賀州學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁賀州學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的順序表中，在第i個元素（1<=i<=n）之前插入一個新元素時，需要向后移動的元素個數(shù)為：A.n-iB.iC.n-i+1D.n-i-12、對于一個具有n個節(jié)點的無向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/23、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB4、對于一個具有n個元素的哈希表，負載因子（loadfactor）為0.7，當(dāng)表中元素數(shù)量超過一定閾值時需要進行擴容。以下關(guān)于擴容操作的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)模緼.O(1)B.O(n)C.O(logn)D.O(nlogn)5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)優(yōu)先級隊列？（）A.二叉樹B.鏈表C.堆D.棧6、棧是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它遵循后進先出（LIFO）的原則。以下關(guān)于棧的說法中，錯誤的是？（）A.棧可以用數(shù)組或鏈表實現(xiàn)。B.棧的插入和刪除操作只能在棧頂進行。C.?？梢杂糜趯崿F(xiàn)函數(shù)調(diào)用、表達式求值等。D.棧的容量是無限的，可以存儲任意數(shù)量的元素。7、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序8、在一個具有n個元素的有序單鏈表中，要查找一個特定元素，平均時間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)9、對于一個具有n個元素的堆，進行堆排序。以下關(guān)于堆排序的平均時間復(fù)雜度和空間復(fù)雜度的描述，哪一個是準(zhǔn)確的？A.平均時間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)B.平均時間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)C.平均時間復(fù)雜度為O(logn)，空間復(fù)雜度為O(logn)D.平均時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)10、在一個具有n個元素的最小堆中，刪除堆頂元素后，為了恢復(fù)堆的性質(zhì)，需要進行的調(diào)整操作的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、對于一個大根堆，若要刪除堆頂元素并保持堆的性質(zhì)，以下哪種操作是正確的？A.將堆底元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素直接刪除，不進行其他操作C.將堆頂元素與任意子節(jié)點交換，然后調(diào)整D.以上都不對12、對于一個采用鏈?zhǔn)酱鎯Φ年犃?，若隊頭指針和隊尾指針相同，則隊列的狀態(tài)為：A.隊空B.隊滿C.不確定D.隊列中只有一個元素13、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n/214、以下關(guān)于快速排序的描述，錯誤的是：A.快速排序在平均情況下的時間復(fù)雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時間復(fù)雜度為O(n^2)D.快速排序不需要額外的存儲空間15、對于一個具有n個元素的有序鏈表，若要在其中插入一個新元素并保持有序，平均需要移動的元素個數(shù)為？（）A.n/2B.nC.lognD.nlogn16、在一個用鏈表實現(xiàn)的隊列中，若要刪除隊尾元素，需要進行哪些操作？A.遍歷鏈表找到隊尾元素并刪除B.將隊尾元素的前一個元素設(shè)為隊尾C.直接刪除隊尾元素D.以上都不對17、在一個具有n個元素的最小堆中，插入一個新元素后，為了重新調(diào)整為最小堆，最壞情況下需要比較多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)18、在一個鏈隊列中，假設(shè)隊頭指針為front，隊尾指針為rear，刪除隊頭元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL19、對于一個具有n個元素的快速排序，在最好情況下，其時間復(fù)雜度為？（）A.O(nlogn)B.O(n^2)C.O(n)D.O(logn)20、在一個帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹時，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋如何在一個具有n個元素的循環(huán)鏈表中，進行插入操作，并分析其時間復(fù)雜度和空間復(fù)雜度。2、（本題10分）數(shù)組和鏈表在存儲數(shù)據(jù)方面有哪些不同之處？各自的優(yōu)缺點是什么？3、（本題10分）論述在歸并排序中，如何合并兩個已排序的子序列，給出具體的實現(xiàn)代碼。4、（本題10分）深入探討在一個具有n個元素的二叉搜索樹中，如何實現(xiàn)樹的平衡化操作，如AVL樹的旋轉(zhuǎn)調(diào)整。三、設(shè)計題（本大題共2