懷化學院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁懷化學院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》

2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個元素的有序鏈表，進行二分查找的時間復雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.不能進行二分查找2、已知一個有序表為{11,22,33,44,55,66,77,88,99}，使用折半查找法查找值為77的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.43、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)4、在一棵二叉搜索樹中，刪除一個有兩個子節(jié)點的節(jié)點時，通常采用的方法是：A.用左子樹的最大值替代該節(jié)點B.用右子樹的最小值替代該節(jié)點C.隨機選擇左子樹或右子樹的節(jié)點替代D.不進行替代，直接刪除5、以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實現(xiàn)一個可以快速查找最大值和最小值的數(shù)據(jù)集合？A.鏈表B.棧C.隊列D.堆6、在一個具有n個節(jié)點的二叉樹中，若采用中序遍歷得到的節(jié)點序列是有序的，則該二叉樹可能是什么類型？A.滿二叉樹B.完全二叉樹C.二叉搜索樹D.以上都有可能7、在一個鏈式存儲的隊列中，若隊頭指針為front，隊尾指針為rear，要刪除隊頭元素，需要進行的操作是？（）A.front=front->next;B.rear=front;C.rear=rear->next;D.front=NULL;8、在一個具有n個元素的循環(huán)雙鏈表中，若要在表頭插入一個新元素，以下關(guān)于插入操作的時間復雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、對于一個有向無環(huán)圖（DAG），進行拓撲排序的方法不止一種。以下關(guān)于拓撲排序的描述，錯誤的是（）A.可以使用深度優(yōu)先搜索實現(xiàn)B.結(jié)果不唯一C.可以用于判斷圖中是否存在環(huán)D.所有節(jié)點的入度在排序過程中不會改變10、在一棵二叉搜索樹中，刪除一個節(jié)點后，為了保持二叉搜索樹的性質(zhì)，需要進行的調(diào)整操作可能包括（）A.左旋B.右旋C.左右旋結(jié)合D.以上都有可能11、對于一個有向圖，使用鄰接矩陣存儲，判斷是否存在從頂點i到頂點j的邊的時間復雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)12、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)13、在一個具有n個頂點的有向圖中，若存在環(huán)，則使用拓撲排序算法會？A.正常排序B.無法排序C.部分排序D.排序結(jié)果不確定14、對于一個具有n個元素的大頂堆，若要獲取堆中的第k大元素（1<=k<=n），以下哪種方法效率較高？A.先排序再獲取B.每次刪除堆頂元素k-1次C.構(gòu)建一個大小為k的小頂堆，然后逐步替換D.以上方法效率相同15、對于一個具有n個節(jié)點的無向連通圖，其生成樹的邊數(shù)為（）A.n-1B.nC.n+1D.2n16、以下關(guān)于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的描述，哪一項是正確的？（）A.深度優(yōu)先搜索使用隊列實現(xiàn)B.廣度優(yōu)先搜索使用棧實現(xiàn)C.兩種搜索算法都可以用于判斷圖是否連通D.深度優(yōu)先搜索一定能找到最短路徑17、對于一個采用順序存儲的棧，若棧頂指針top等于-1時，表示：A.棧滿B.?？誄.棧中只有一個元素D.棧中至少有一個元素18、對于一個具有n個節(jié)點的二叉樹，進行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個根節(jié)點B.所有節(jié)點只有左子樹C.所有節(jié)點只有右子樹D.是一棵滿二叉樹19、對于一個具有n個元素的無序數(shù)組，若要對其進行排序，以下哪種算法在最壞情況下時間復雜度最高？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序20、在一個具有n個元素的循環(huán)鏈表中，查找第i個元素（1<=i<=n），平均需要比較的次數(shù)為（）。A.nB.n/2C.(n+1)/2D.(n-1)/2二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細說明快速排序算法的基本思想和步驟，并分析其在最壞情況下的時間復雜度和平均情況下的時間復雜度。2、（本題10分）對于一個具有n個頂點的無向圖，如何使用廣度優(yōu)先搜索算法計算各個頂點的最短路徑長度？3、（本題10分）詳細闡述基數(shù)排序中如何處理不同進制的數(shù)據(jù)。4、（本題10分）詳細說明如何在一個具有n個元素的堆中，進行刪除操作，并分析其時間復雜度和空間復雜度。三、設(shè)計題（本大題共2個小題，共2