2025年大學(xué)一年級（計算機(jī)科學(xué)與技術(shù)）數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)試題及答案

（考試時間：90分鐘滿分100分）班級______姓名______第I卷（選擇題，共40分）每題給出的四個選項中，只有一個選項是符合題目要求的。(總共20題，每題2分，在每小題給出的四個選項中，選出最符合題目要求的一項)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ù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)無關(guān)2.線性表的順序存儲結(jié)構(gòu)中，元素之間的邏輯關(guān)系是通過A.指針表示B.相鄰存儲位置表示C.數(shù)組下標(biāo)表示D.以上都不對3.在一個長度為n的順序表中，刪除第i個元素（1≤i≤n）時，需要移動的元素個數(shù)是A.n-iB.n-i+1C.iD.i-14.棧的特點是A.先進(jìn)先出B.后進(jìn)先出C.隨機(jī)進(jìn)出D.以上都不對5.若進(jìn)棧序列為1，2，3，4，進(jìn)棧過程中可以出棧，則下列不可能的一個出棧序列是A.1，4，3，2B.2，3，4，1C.3，1，4，2D.3，4，2，16.隊列的特點是A.先進(jìn)先出B.后進(jìn)先出C.隨機(jī)進(jìn)出D.以上都不對7.循環(huán)隊列中，隊滿的條件是A.（rear+1）%maxsize==frontB.rear==frontC.rear+1==frontD.以上都不對8.對于一棵具有n個結(jié)點的二叉樹，若一個結(jié)點的編號為i（1≤i≤n），則它的左孩子結(jié)點的編號為A.2iB.2i+1C.2i-1D.不確定9.深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為A.15B.16C.31D.3210.已知二叉樹的前序序列為ABDECF，中序序列為DBEAFC，則后序序列為A.DEBFCAB.DEFBCAC.DBEACFD.ABCDEF11.以下哪種排序算法的平均時間復(fù)雜度為O(n^2)A.快速排序B.冒泡排序C.歸并排序D.堆排序12.對關(guān)鍵字集合K={60，40，49，23，25，13，95}進(jìn)行排序，當(dāng)一趟排序結(jié)束后，結(jié)果為23，40，49，25，13，60，95，則采用的排序方法是A.冒泡排序B.選擇排序C.插入排序D.快速排序13.哈希表的平均查找長度主要取決于A.哈希表的大小B.數(shù)據(jù)元素的多少C.哈希函數(shù)和處理沖突的方法D.以上都不對14.順序查找法適用于查找A.有序表B.無序表C.哈希表D.二叉排序樹15.折半查找法適用于查找A.有序表B.無序表C.哈希表D.二叉排序樹16.一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為A.nnB.(n-1)(n-1)C.n(n-1)D.(n-1)n17.一個具有n個頂點的有向圖，其邊數(shù)最多為A.n(n-1)B.n(n+1)C.nnD.(n+18.圖的深度優(yōu)先搜索類似于樹的A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷19.圖的廣度優(yōu)先搜索類似于樹的A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷20.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)應(yīng)用的說法，錯誤的是A.?？捎糜趯崿F(xiàn)表達(dá)式求值B.隊列可用于實現(xiàn)廣度優(yōu)先搜索C.二叉排序樹可用于實現(xiàn)快速排序D.哈希表可用于實現(xiàn)查找功能第II卷（非選擇題，共60分）21.（10分）簡述線性表的兩種存儲結(jié)構(gòu)及其優(yōu)缺點。22.（10分）已知一個棧的進(jìn)棧序列為1，2，3，4，5，寫出所有可能的出棧序列。23.（10分）畫出一棵具有5個結(jié)點的二叉樹，要求其前序序列為ABCDE，中序序列為CBAED。24.（15分）閱讀以下材料：給定關(guān)鍵字集合K={30，10，40，20，50}，采用快速排序算法進(jìn)行排序?？焖倥判虻幕舅枷胧沁x擇一個基準(zhǔn)元素，將數(shù)組分為兩部分，使得左邊部分的元素都小于等于基準(zhǔn)元素，右邊部分的元素都大于等于基準(zhǔn)元素，然后對左右兩部分分別進(jìn)行排序。請回答以下問題：（1）第一次劃分后，數(shù)組的狀態(tài)是怎樣的？（2）簡述快速排序的遞歸過程。25.（15分）閱讀以下材料：有一個無向圖G，其頂點集合V={v1，v2，v3，v4，v5}，邊集合E={(v1,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5)}。請回答以下問題：（1）畫出該無向圖。（2）寫出該圖的鄰接矩陣。（3）從頂點v1出發(fā)，進(jìn)行深度優(yōu)先搜索