班級班級學號姓名本科．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．密．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．封．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．線．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．試卷說明：1、試卷滿分100分，120分鐘完成試卷；2、鋼筆或圓珠筆直接答在試題中（除題目有特殊規(guī)定外）；3、答卷前將密封線內(nèi)的項目填寫清楚。題號一二三四五總分合分人復核人滿分100得分一、單項選擇題(本大題總共15小題，每題2分，共30分）1.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法，正確的是（）A.數(shù)據(jù)結(jié)構(gòu)只研究數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)只研究數(shù)據(jù)的存儲結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D.數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)的運算無關(guān)2.線性表的順序存儲結(jié)構(gòu)中，元素之間的邏輯關(guān)系是通過（）表示的。A.指針B.線性表的長度C.元素的存儲位置D.以上都不對3.在一個長度為n的順序表中，刪除第i個元素（1≤i≤n）時，需要移動（）個元素。A.n-iB.n-i+1C.iD.i-14.棧的特點是（）A.先進先出B.后進先出C.進優(yōu)于出D.出優(yōu)于進5.隊列的特點是（）A.先進先出B.后進先出C.進優(yōu)于出D.出優(yōu)于進6.深度為5的滿二叉樹有（）個結(jié)點。A.15B.16C.31D.327.對于一棵具有n個結(jié)點的二叉樹，其高度最多為（）A.nB.n/2C.log2n+1D.n/2+18.已知二叉樹的前序序列為ABCDEFG，中序序列為CBEDAFG，則后序序列為（）A.CEBFGDAB.CEDBGFAC.ECDBGFAD.EDCBGFA9.以下排序算法中，平均時間復雜度為O(nlogn)的是（）A.冒泡排序B.選擇排序C.插入排序D.快速排序10.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A.1B.2C.3D.411.數(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)12.算法的時間復雜度取決于（）A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.計算機的配置D.A和B13.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A.順序表B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表14.若進棧序列為1，2，3，4，進棧過程中可以出棧，則（）不可能是一個出棧序列。A.3，4，2，1B.1，4，3，2C.4，3，2，1D.2，3，4，115.一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）A.250B.500C.501D.以上都不對二、填空題(本大題總共5題，每題4分，共20分)1.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的______結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。2.線性表的鏈式存儲結(jié)構(gòu)中，每個結(jié)點包含______和數(shù)據(jù)域兩部分。3.棧的基本運算有______、______、______和______。4.二叉樹的遍歷方式主要有______、______和______。5.常見的排序算法中，______排序算法是穩(wěn)定的。三、簡答題(本大題總共6題，每題4分，共24分)1.簡述數(shù)據(jù)結(jié)構(gòu)的定義。2.簡述線性表順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。3.簡述棧和隊列的區(qū)別。4.簡述二叉樹的性質(zhì)。5.簡述排序算法的分類及各類的特點。6.簡述圖的存儲結(jié)構(gòu)及適用場景。四、算法設計題(本大題總共2題，每題6分，共12分)1.設計一個算法，將一個順序表中的所有元素逆置。2.設計一個算法，判斷一個二叉樹是否平衡。五、綜合應