站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁東北師范大學《數(shù)據(jù)結(jié)構(gòu)與算法》2025學年第一學期期末試卷(B)題號一二三四總分得分注意事項考生須在答題卡指定位置填寫姓名、學號、專業(yè)等信息，在試卷上作答無效。答題時須使用黑色簽字筆或鋼筆，字跡清晰，卷面整潔。考試結(jié)束后，將試卷、答題卡一并交回，不得攜帶出考場。一、精心選一選（本大題總共15小題，每題2分，共30分）1.以下哪個不是數(shù)據(jù)結(jié)構(gòu)的基本邏輯結(jié)構(gòu)？A.集合結(jié)構(gòu)B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.動態(tài)結(jié)構(gòu)2.線性表的順序存儲結(jié)構(gòu)中，元素之間的邏輯關(guān)系是通過什么體現(xiàn)的？A.指針B.數(shù)組下標C.鏈表節(jié)點D.哈希值3.在一個長度為n的順序表中，刪除第i個元素（1≤i≤n）時，需要移動多少個元素？A.n-iB.n-i+1C.iD.i-14.棧的特點是？A.先進先出B.后進先出C.隨機進出D.按優(yōu)先級進出5.隊列的操作原則是？A.先進先出B.后進先出C.隨機進出D.按優(yōu)先級進出6.若進棧序列為1,2,3,4，進棧過程中可以出棧，則下列不可能的出棧序列是？A.1,4,3,2B.2,3,4,1C.3,1,4,2D.3,4,2,17.深度為5的完全二叉樹的節(jié)點數(shù)最多為？A.15B.16C.31D.328.已知二叉樹的前序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，則后序遍歷序列為？A.DEBFCAB.DBEAFCC.ABDCEFD.ABCDEF9.圖的鄰接矩陣表示法適用于哪種圖？A.有向圖B.無向圖C.有向圖和無向圖D.稀疏圖10.對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是？A.nB.n×nC.n-1D.(n-1)×(n-1)11.下列排序算法中，平均時間復雜度為O(n^2)的是？A.快速排序B.歸并排序C.冒泡排序D.堆排序12.對關(guān)鍵字集合K={60,40,49,23,25,13,95,196,85}，以第一個關(guān)鍵字60為基準進行一趟快速排序的結(jié)果是？A.23,40,49,25,13,60,85,95,196B.13,23,25,40,49,60,85,95,196C.13,23,25,40,49,60,95,85,196D.13,23,25,40,49,60,196,95,8513.哈希表的平均查找長度主要取決于？A.哈希表的大小B.哈希函數(shù)C.關(guān)鍵字的個數(shù)D.裝填因子14.以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實現(xiàn)優(yōu)先隊列？A.棧B.隊列C.堆D.鏈表15.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的？A.存儲結(jié)構(gòu)B.物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.物理和存儲結(jié)構(gòu)二、準確填一填（本大題總共5題，每題4分，共20分）1.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括數(shù)據(jù)的______結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。2.順序表中邏輯上相鄰的元素，其物理位置______。3.棧頂元素的位置是______。4.二叉樹的第i層上最多有______個節(jié)點（i≥1）。5.對于一個具有n個頂點的連通圖，其生成樹的邊數(shù)為______。三、細心判一判（本大題總共6題，每題4分，共24分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)決定了數(shù)據(jù)的存儲結(jié)構(gòu)。（）2.線性表的順序存儲結(jié)構(gòu)中插入和刪除操作效率較高。（）3.棧和隊列都是特殊的線性表。（）4.完全二叉樹一定是滿二叉樹。（）5.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷結(jié)果一定相同。（）6.排序算法的時間復雜度與數(shù)據(jù)的初始狀態(tài)無關(guān)。（）四、靈活答一答（本大題總共2題，每題6分，共12分）1.簡述線性表的兩種存儲結(jié)構(gòu)及其優(yōu)缺點。2.簡述圖的鄰接表表示法及其適用場景。五、綜合用一用(14分)1.已知一個有序表為{10,20,30,40,50