遼寧石油化工大學《數(shù)據(jù)結構實驗》2021-2022學年期末試卷

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

《數(shù)據(jù)結構實驗》2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下關于快速排序的描述，錯誤的是：A.快速排序在平均情況下的時間復雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時間復雜度為O(n^2)D.快速排序不需要額外的存儲空間2、若要對一個具有n個元素的有序鏈表進行二分查找，是否可行？（）A.可行B.不可行C.有時可行D.取決于鏈表長度3、在一個具有n個節(jié)點的圖中，使用弗洛伊德算法求所有節(jié)點對之間的最短路徑，其時間復雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)4、在一個采用哈希表存儲的數(shù)據(jù)結構中，哈希函數(shù)將關鍵字映射到存儲位置。若發(fā)生哈希沖突，通常采用開放定址法解決。以下關于開放定址法的時間復雜度的描述，哪一個是恰當?shù)模緼.查找操作的時間復雜度在平均情況下為O(1)，最壞情況為O(n)B.查找操作的時間復雜度始終為O(1)C.查找操作的時間復雜度在平均情況下為O(logn)，最壞情況為O(nlogn)D.查找操作的時間復雜度始終為O(n)5、對于一個有向圖，使用鄰接矩陣存儲，判斷是否存在從頂點i到頂點j的邊的時間復雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)6、排序算法的穩(wěn)定性是指在排序過程中，如果兩個元素的值相等，它們在排序后的相對位置是否保持不變。以下關于排序算法穩(wěn)定性的說法中，錯誤的是？（）A.冒泡排序、插入排序和歸并排序是穩(wěn)定的排序算法。B.選擇排序、快速排序和希爾排序是不穩(wěn)定的排序算法。C.穩(wěn)定性對于某些應用場景非常重要，例如在對具有多個關鍵字的記錄進行排序時。D.所有的排序算法都可以通過修改代碼來實現(xiàn)穩(wěn)定性。7、已知一個有序表為{11,22,33,44,55,66,77,88,99}，使用折半查找法查找值為77的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.48、對于一個具有n個節(jié)點的二叉樹，若每個節(jié)點都有左子樹和右子樹，則其葉子節(jié)點的個數(shù)至少為？A.n/2B.(n+1)/2C.n-1D.logn9、對于一個具有n個頂點和e條邊的有向圖，其鄰接矩陣中非零元素的個數(shù)最多為？（）A.eB.2eC.n^2D.n(n-1)10、對于一個具有n個元素的循環(huán)隊列，隊頭指針為front，隊尾指針為rear，隊列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front11、對于一個采用鏈式存儲的隊列，若隊頭指針和隊尾指針相同，則隊列的狀態(tài)為：A.隊空B.隊滿C.不確定D.隊列中只有一個元素12、圖是一種復雜的數(shù)據(jù)結構。在有向圖中，頂點的入度是指指向該頂點的邊的數(shù)量。若要計算一個有向圖中所有頂點的入度，哪種算法較為合適？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓撲排序D.以上都可以13、已知一個圖的鄰接表存儲結構，若要判斷任意兩個頂點之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索14、在一個具有n個元素的順序存儲的線性表中，要在第i個位置插入一個新元素（1<=i<=n+1），需要移動的元素個數(shù)約為？A.n-iB.iC.n-i+1D.n-i-115、對于一個具有n個頂點和e條邊的有向完全圖，其弧的條數(shù)為（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/216、在一個用順序存儲結構實現(xiàn)的棧中，若棧頂指針top指向棧頂元素的上一個位置，當棧為空時，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）17、對于一棵二叉樹，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC18、在一個具有n個元素的順序表中，若要在第i個元素（1<=i<=n）之前插入一個新元素，需要移動的元素個數(shù)為？（）A.n-iB.iC.n-i+1D.n-i-119、以下關于線性表的描述，正確的是：A.線性表的元素在邏輯上和存儲上都必須是連續(xù)的B.線性表只能采用順序存儲結構C.線性表的長度是固定不變的D.線性表可以是空表，即不含任何元素20、對于一個具有n個頂點和e條邊的無向連通圖，其生成樹中邊的條數(shù)為（）。A.nB.n-1C.eD.e-1二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在Trie樹中，如何節(jié)省存儲空間，例如采用壓縮存儲或節(jié)點合并等方法。2、（本題10分）什么是二叉搜索樹的刪除操作的非遞歸實現(xiàn)？請描述其實現(xiàn)過程。3、（本題10分）請詳細闡述在順序表中進行插入和刪除操作時，平均移動元素個數(shù)的計算方法以及為什么會有這樣的移動情況。4、（本題10分）論述在貪心算法中，如何證明所得到的解是最優(yōu)的或者是