西安科技大學高新學院《數(shù)據(jù)結(jié)構(gòu)》2024-----2025學年期末試卷（A卷）專業(yè)

班級

姓名

學號

題號一二三四五六七八九十成績復核簽字得分登分簽字說明：本試卷共100分；答題要求：按要求答題考生須知:1.姓名、學號、系、專業(yè)、年級、班級必須寫在密封線內(nèi)指定位置。2.答案必須用藍、黑色鋼筆或圓珠筆寫在試卷上，字跡要清晰，卷面要整潔，寫在草稿紙上的一律無效。一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題給出的四個選項中，只有一項是符合題目要求的。下列數(shù)據(jù)結(jié)構(gòu)中，不屬于線性結(jié)構(gòu)的是（）A.單鏈表B.棧C.二叉樹D.循環(huán)隊列若一個棧的入棧序列為1,2,3,4,5，且棧的操作遵循“先進后出”原則，則不可能的出棧序列是（）A.5,4,3,2,1B.2,1,5,4,3C.3,2,1,4,5D.2,3,1,5,4在單鏈表中，刪除一個節(jié)點p（非尾節(jié)點）的核心操作是（）A.p=p->nextB.p->next=pC.p->next=p->next->nextD.p=p->next->next2025年算法優(yōu)化中，常用于大規(guī)模數(shù)據(jù)“Top-K”問題（如取前10大元素）的高效數(shù)據(jù)結(jié)構(gòu)是（）A.有序數(shù)組B.小根堆C.二叉排序樹D.哈希表一棵深度為5的完全二叉樹（根節(jié)點深度為1），其節(jié)點總數(shù)最多為（）A.15B.31C.32D.63已知一棵二叉樹的前序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，則其后序遍歷序列為（）A.DEBFCAB.DBEFCAC.DEBCFAD.DBECFA在無向圖中，若頂點數(shù)為n，邊數(shù)為e，則所有頂點的度數(shù)之和為（）A.nB.eC.2eD.n+e下列排序算法中，平均時間復雜度為O(nlog?n)且空間復雜度為O(1)的是（）A.快速排序B.堆排序C.歸并排序D.冒泡排序哈希表查找中，“沖突”是指（）A.兩個不同的關(guān)鍵字映射到同一個哈希地址B.哈希表為空表C.關(guān)鍵字找不到對應(yīng)的哈希地址D.哈希函數(shù)無法計算哈希地址若用鄰接矩陣存儲一個有向圖，該矩陣的行數(shù)與列數(shù)分別等于（）A.圖的邊數(shù)、圖的頂點數(shù)B.圖的頂點數(shù)、圖的邊數(shù)C.圖的頂點數(shù)、圖的頂點數(shù)D.圖的邊數(shù)、圖的邊數(shù)在循環(huán)隊列中，若front表示隊頭指針，rear表示隊尾指針，maxSize表示隊列最大容量，則隊列判滿的條件是（）A.(rear+1)%maxSize==frontB.rear==frontC.rear==maxSize-1D.front==0下列關(guān)于二叉平衡樹（AVL樹）的描述，正確的是（）A.任意節(jié)點的左右子樹高度差的絕對值不超過1B.所有節(jié)點的左子樹節(jié)點值均大于右子樹節(jié)點值C.平衡樹的高度一定是最小的D.插入節(jié)點后無需調(diào)整即可保持平衡圖的深度優(yōu)先搜索（DFS）遍歷類似于樹的（）A.層次遍歷B.前序遍歷C.中序遍歷D.后序遍歷對數(shù)組arr=[38,65,97,76,13,27,49]進行冒泡排序，第一趟排序后數(shù)組的結(jié)果是（）A.[38,65,76,13,27,49,97]B.[38,65,13,27,49,76,97]C.[13,27,38,49,65,76,97]D.[38,13,27,49,65,76,97]2025年大數(shù)據(jù)處理中，常用于高效存儲與查詢“鍵值對”數(shù)據(jù)的結(jié)構(gòu)是（）A.二叉樹B.哈希表C.棧D.隊列二、填空題（本大題共10空，每空1分，共10分）數(shù)據(jù)結(jié)構(gòu)的三要素包括數(shù)據(jù)的邏輯結(jié)構(gòu)、__________結(jié)構(gòu)和數(shù)據(jù)的運算。單鏈表中，頭指針的作用是__________，便于訪問鏈表中的所有節(jié)點。棧的基本操作包括入棧（Push）和__________（Pop），隊列的基本操作包括入隊（Enqueue）和出隊（Dequeue）。一棵有n個節(jié)點的二叉樹，其葉子節(jié)點數(shù)為n?，度為2的節(jié)點數(shù)為n?，則n?與n?的關(guān)系為__________。圖的存儲結(jié)構(gòu)主要有鄰接矩陣和__________兩種，后者更適合存儲稀疏圖。快速排序的核心思想是__________，通過一趟排序?qū)⒋判蛐蛄蟹譃閮刹糠郑俜謩e遞歸排序。在二叉排序樹中，若按中序遍歷序列訪問節(jié)點，則得到的序列是__________序列（升序或降序）。哈希函數(shù)的構(gòu)造方法有直接定址法、數(shù)字分析法、平方取中法和__________等。2025年算法工程化中，對鏈表進行頻繁插入刪除操作時，優(yōu)先選擇__________鏈表（雙向/單向），可降低操作復雜度。圖的拓撲排序適用于__________圖（有向無環(huán)/有向有環(huán)），用于解決任務(wù)依賴關(guān)系排序問題。三、簡答題（本大題共3小題，每小題5分，共15分）（本題5分）簡述棧與隊列的異同點，說明兩者的邏輯結(jié)構(gòu)、存儲方式（順序存儲與鏈式存儲）及典型應(yīng)用場景（各舉2例），分析順序存儲時棧與隊列的“假溢出”問題及解決方案。（本題5分）結(jié)合二叉平衡樹（AVL樹）的定義，說明其插入節(jié)點后“失衡調(diào)整”的核心類型（如LL型、RR型、LR型、RL型），以LL型失衡為例，簡述調(diào)整步驟與原理，分析平衡樹在查找效率優(yōu)化中的作用。（本題5分）簡述圖的深度優(yōu)先搜索（DFS）與廣度優(yōu)先搜索（BFS）的遍歷原理，對比兩種算法的時間復雜度、空間復雜度及適用場景，舉例說明BFS在“最短路徑問題”（如無權(quán)圖最短路徑）中的應(yīng)用。四、算法設(shè)計題（本大題共2小題，每小題10分，共20分）（本題10分）已知一個帶頭節(jié)點的單鏈表L（節(jié)點結(jié)構(gòu)為data、next），請設(shè)計一個算法：（1）刪除鏈表中所有值為x的節(jié)點；（2）計算刪除操作后的鏈表長度。要求：①寫出算法的核心思路；②用C或Java語言實現(xiàn)代碼（需定義節(jié)點結(jié)構(gòu)）；③分析算法的時間復雜度與空間復雜度。（本題10分）已知一個無序數(shù)組arr（元素為整數(shù)，無重復值），請設(shè)計一個算法：（1）構(gòu)建一棵二叉排序樹；（2）判斷該二叉排序樹是否為二叉平衡樹（AVL樹）。要求：①寫出算法的核心步驟（構(gòu)建與判斷）；②用偽代碼描述關(guān)鍵邏輯；③分析構(gòu)建二叉排序樹的時間復雜度。五、綜合應(yīng)用題（本大題共2小題，每小題12.5分，共25分）（本題12.5分）某電商平臺需對用戶訂單按“下單時間”進行排隊處理，同時需支持“優(yōu)先處理VIP訂單”的功能（VIP訂單優(yōu)先級高于普通訂單）。（1）選擇合適的數(shù)據(jù)結(jié)構(gòu)（如優(yōu)先隊列）設(shè)計該訂單處理系統(tǒng)，說明數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)與存儲方式（7分）；（2）設(shè)計核心操作（如訂單入隊、訂單出隊、查詢當前待處理訂單數(shù)）的算法邏輯，用偽代碼描述，分析各操作的時間復雜度（5.5分）。（本題12.5分）某地圖應(yīng)用需實現(xiàn)“城市間最短路徑查詢”功能（假設(shè)城市間道路為無權(quán)圖，兩點間邊表