廣西財經學院《數據結構》2024 - 2025 學年第一學期期末試卷

（第2頁）制卷人簽名：制卷日期制卷人簽名：制卷日期：審核人簽名：：審核日期：………………………………………………裝……訂……線…………………學院專業/班級學號姓名題號一二三四五六七八總分閱卷教師得分………………一、單項選擇題（總共10題，每題3分，每題只有一個正確答案，請將正確答案填寫在括號內）1.線性表采用鏈式存儲結構時，其地址（）。A.必須是連續的B.部分地址必須是連續的C.一定是不連續的D.連續與否均可以2.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節省時間。A.順序表B.雙鏈表C.帶頭結點的雙循環鏈表D.單循環鏈表3.棧和隊列的共同點是（）。A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D.沒有共同點4.一個棧的入棧序列是1，2，3，4，則棧不可能的輸出序列是（）。A.4321B.1234C.4132D.23415.深度為5的完全二叉樹的結點數不可能是（）。A.15B.16C.17D.186.若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結點的孩子結點（）。A.只有eB.有e、bC.有e、cD.無法確定7.設森林F對應的二叉樹為B，它有m個結點，B的根為p，p的右子樹結點個數為n，森林F中第一棵樹的結點個數是（）。A.m-nB.m-n-1C.n+1D.條件不足，無法確定8.對n個記錄的文件進行快速排序，所需要的輔助存儲空間為（）。A.O(1)B.O(log2n)C.O(n)D.O(n2)9.下列排序方法中，平均時間復雜度為O(nlog2n)且穩定的排序方法是（）。A.快速排序B.堆排序C.歸并排序D.基數排序10.哈希表的平均查找長度（）。A.與記錄個數n有關B.與裝填因子α有關C.與記錄的關鍵字有關D.與表的結構有關二、多項選擇題（總共5題，每題4分，每題有兩個或兩個以上正確答案，請將正確答案填寫在括號內）1.以下屬于數據結構中邏輯結構的有（）。A.線性結構B.樹形結構C.圖狀結構D.順序存儲結構E.鏈式存儲結構2.下列關于棧的敘述中正確的是（）。A.棧頂元素最先被刪除B.棧底元素最后才能被刪除C.棧底元素是最先被插入的D.棧是先進后出的線性表E.棧是后進先出的線性表3.二叉樹的遍歷方式有（）。A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷E.深度遍歷4.下列排序算法中，屬于不穩定排序的有（）。A.冒泡排序B.快速排序C.選擇排序D.堆排序E.歸并排序5.哈希表查找中，可能會產生沖突的原因有（）。A.哈希函數選擇不當B.記錄的關鍵字不同C.裝填因子過大D.哈希表容量不足E.記錄的關鍵字相同三、判斷題（總共10題，每題2分，請判斷下列說法是否正確，正確的打√，錯誤的打×）1.數據的邏輯結構是指數據在計算機中的存儲形式。（）2.線性表的順序存儲結構優于鏈式存儲結構。（）3.棧是一種先進先出的線性表。（）4.隊列是一種后進后出的線性表。（）5.完全二叉樹一定是滿二叉樹。（）6.二叉樹的中序遍歷序列是唯一的。（）7.快速排序是一種穩定的排序算法。（）8.歸并排序的時間復雜度不受初始記錄序列的影響。（）9.哈希表的查找效率與哈希函數無關。（）10.裝填因子α越大，哈希表中發生沖突的可能性越小。（）四、簡答題（總共3題，每題10分，請簡要回答下列問題）1.簡述線性表的順序存儲結構和鏈式存儲結構的優缺點。2.簡述棧和隊列的區別，并舉例說明它們在實際應用中的場景。3.簡述排序算法的