2025年大學(xué)大二（計(jì)算機(jī)科學(xué)與技術(shù)）數(shù)據(jù)結(jié)構(gòu)與算法測(cè)試題及答案

（考試時(shí)間：90分鐘滿分100分）班級(jí)______姓名______第I卷（選擇題，共40分）每題只有一個(gè)正確答案，請(qǐng)將正確答案填寫在括號(hào)內(nèi)。(總共20題，每題2分，每題選出符合題意的一項(xiàng)，并在括號(hào)內(nèi)填寫該選項(xiàng)的字母)1.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說(shuō)法，正確的是（）A.數(shù)據(jù)結(jié)構(gòu)只研究數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)只研究數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)以及它們之間的相互關(guān)系D.數(shù)據(jù)結(jié)構(gòu)只研究數(shù)據(jù)在計(jì)算機(jī)中的表示2.線性表的順序存儲(chǔ)結(jié)構(gòu)中，元素之間的邏輯關(guān)系是通過(guò)（）表示的。A.指針B.數(shù)組下標(biāo)C.鏈表節(jié)點(diǎn)D.順序存儲(chǔ)單元的鄰接關(guān)系3.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1≤i≤n）時(shí)，需要移動(dòng)（）個(gè)元素。A.n-iB.n-i+1C.iD.i-14.若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)（）的情況。A.3，2，1B.2，1，3C.3，1，2D.1，3，25.一個(gè)棧的輸入序列為1，2，3，4，5，則下列序列中不可能是棧的輸出序列的是（）A.2，3，4，1，5B.5，4，1，3，2C.2，3，1，4，5D.1，5，4，3，26.隊(duì)列的操作特點(diǎn)是（）A.先進(jìn)后出B.先進(jìn)先出C.隨機(jī)進(jìn)出D.后進(jìn)先出7.循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（）A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front8.對(duì)于一棵具有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)它為一棵（）二叉樹時(shí)具有最小高度。A.完全B.滿C.二叉排序D.線索9.深度為5的滿二叉樹有（）個(gè)節(jié)點(diǎn)。A.15B.16C.31D.3210.若二叉樹中度為2的節(jié)點(diǎn)有15個(gè)，度為1的節(jié)點(diǎn)有10個(gè)，則葉子節(jié)點(diǎn)有（）個(gè)。A.25B.30C.31D.1611.已知二叉樹的前序序列為ABDEGCFH，中序序列為DBGEACHF，則后序序列為（）A.DGEBHFCAB.ABCDEFGHC.GEDHFBCAD.ACEGBDFH12.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為（）A.O(n)B.O(1)C.O(log2n)D.O(n2)13.對(duì)一組數(shù)據(jù)進(jìn)行排序，若關(guān)鍵字序列基本有序，則采用（）排序算法效率最高。A.快速B.冒泡C.歸并D.選擇14.下面關(guān)于哈希表的說(shuō)法，錯(cuò)誤的是（）A.哈希表的平均查找長(zhǎng)度與哈希函數(shù)、哈希表的裝填因子有關(guān)B.哈希表的查找效率主要取決于哈希函數(shù)和處理沖突的方法C.哈希表一定不會(huì)出現(xiàn)沖突D.哈希表是一種以空間換時(shí)間的存儲(chǔ)結(jié)構(gòu)15.在哈希表中，沖突是指（）A.兩個(gè)元素具有相同的序號(hào)B.兩個(gè)元素的鍵值不同，而其他屬性相同C.不同鍵值的元素對(duì)應(yīng)到相同的存儲(chǔ)地址D.數(shù)據(jù)元素過(guò)多16.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A.棧B.隊(duì)列C.文件D.樹17.一棵哈夫曼樹共有215個(gè)節(jié)點(diǎn)，對(duì)其進(jìn)行哈弗曼編碼，能得到（）個(gè)不同的碼字。A.107B.108C.214D.21518.以下關(guān)于圖的說(shuō)法，正確的是（）A.圖的遍歷只能采用深度優(yōu)先搜索B.圖的遍歷只能采用廣度優(yōu)先搜索C.圖的遍歷可以采用深度優(yōu)先搜索或廣度優(yōu)先搜索D.圖的遍歷沒有固定的方法19.具有n個(gè)頂點(diǎn)的無(wú)向圖最多有（）條邊。A.n(n-1)/2B.n(n+1)/2C.nD.n-120.一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)不具備的特點(diǎn)是（）A.便于插入和刪除操作B.便于隨機(jī)訪問(wèn)任一頂點(diǎn)的所有鄰接頂點(diǎn)C.便于進(jìn)行圖的遍歷D.節(jié)省存儲(chǔ)空間第II卷（非選擇題，共60分）21.（10分）簡(jiǎn)述線性表的兩種存儲(chǔ)結(jié)構(gòu)及其優(yōu)缺點(diǎn)。22.（10分）已知一棵二叉樹的中序序列和后序序列分別為DBEAFIHCG和DEBHIFGCA，請(qǐng)畫出該二叉樹。23.（10分）用簡(jiǎn)單選擇排序法對(duì)序列{50，38，65，97，76，13，27}進(jìn)行排序，寫出每一趟排序后的結(jié)果。24.（15分）閱讀以下材料：有一個(gè)表示工程進(jìn)度的AOE網(wǎng)，頂點(diǎn)表示事件，邊表示活動(dòng)，邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間。已知該AOE網(wǎng)如下：頂點(diǎn)V0表示工程開始，頂點(diǎn)V7表示工程結(jié)束。邊<V0,V1>權(quán)值為6，<V0,V2>權(quán)值為4，<V1,V3>權(quán)值為5，<V,V4>權(quán)值為1，<V2,V5>權(quán)值為7，<V3,V5>權(quán)值為4，<V4,V6>權(quán)值為2，<V5,V6>權(quán)值為4，<V6,V7>權(quán)值為4。（1）計(jì)算每個(gè)事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間。（2）找出關(guān)鍵路徑，并計(jì)算關(guān)鍵路徑的長(zhǎng)度。25.（15分）閱讀以下材料：有一個(gè)學(xué)生成績(jī)管理系統(tǒng)，需要存儲(chǔ)學(xué)生的信息（學(xué)號(hào)、姓名、成績(jī)等），并能夠進(jìn)行插入、刪除、查詢等操作。（1）設(shè)計(jì)一種合適的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)學(xué)生信息。（2）編寫一個(gè)函數(shù)實(shí)現(xiàn)插入學(xué)生信息的操作。（3）編寫一個(gè)函數(shù)實(shí)現(xiàn)刪除學(xué)生信息的操作。答案1.C2.D3.A4.C5.B6.B7.A8.B9.C10.D11.A12.C13.B14.C15.C16.D17.B18.C19.A20.B21.線性表的兩種存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是可以隨機(jī)訪問(wèn)元素，存儲(chǔ)密度大；缺點(diǎn)是插入和刪除操作效率低，可能需要移動(dòng)大量元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是插入和刪除操作效率高，不需要移動(dòng)元素；缺點(diǎn)是不能隨機(jī)訪問(wèn)元素，需要額外的指針空間，存儲(chǔ)密度小。22.（畫出二叉樹，這里文字描述：根節(jié)點(diǎn)為A，左子樹中序?yàn)镈BE，后序?yàn)镈EB，左子樹結(jié)構(gòu)為根B，B的左子樹為D，右子樹為E；右子樹中序?yàn)镕IHCG，后序?yàn)镠IFGCA，右子樹結(jié)構(gòu)為根C，C的左子樹為F，右子樹中序?yàn)镮HG，后序?yàn)镠IG，右子樹結(jié)構(gòu)為根G，G的左子樹為I，右子樹為H）23.初始序列：50，38，65，97，76，13，27第一趟：13，38，65，97，76，50，27第二趟：13，27，65，97，76，50，38第三趟：13，27，38，97，76，50，65第四趟：13，27，38，50，76，97，65第五趟：13，27，38，50，65，97，76第六趟：13，27，38，50，65，76，9724.（1）事件V0最早發(fā)生時(shí)間為0，最遲發(fā)生時(shí)間為0；V1最早發(fā)生時(shí)間為6，最遲發(fā)生時(shí)間為6；V2最早發(fā)生時(shí)間為4，最遲發(fā)生時(shí)間為6；V3最早發(fā)生時(shí)間為11，最遲發(fā)生時(shí)間為11；V4最早發(fā)生時(shí)間為7，最遲發(fā)生時(shí)間為7；V5最早發(fā)生時(shí)間為11，最遲發(fā)生時(shí)間為11；V6最早發(fā)生時(shí)間為15，最遲發(fā)生時(shí)間為15；V7最早發(fā)生時(shí)間為19，最遲發(fā)生時(shí)間為19。（2）關(guān)鍵路徑為V0-V1-V3-V5-V6-V7，長(zhǎng)度為19。25.（1）可以使用結(jié)構(gòu)體數(shù)組來(lái)存儲(chǔ)學(xué)生信息，結(jié)構(gòu)體包含學(xué)號(hào)、姓名、成績(jī)等成員。（2）插入函數(shù)示例：voidinsertStudent(Studentstudents[],intn,StudentnewStudent){students[n]=newStudent;(n)++;}（3）刪除函數(shù)示例：voiddeleteStudent(Studentstudents[],intn,intid){for(inti=