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

（考試時(shí)間：90分鐘滿分100分）班級(jí)______姓名______第I卷（選擇題，共40分）答題要求：本大題共20小題，每小題2分，共40分。在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的，請(qǐng)將正確答案的序號(hào)填在括號(hào)內(nèi)。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ù)的存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其操作D.數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)無(wú)關(guān)2.線性表的順序存儲(chǔ)結(jié)構(gòu)中，元素之間的邏輯關(guān)系是通過（）表示的。A.指針B.線性表的存儲(chǔ)位置C.數(shù)組下標(biāo)D.以上都不對(duì)3.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.單鏈表C.雙向鏈表D.循環(huán)鏈表4.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1≤i≤n）時(shí)，需向前移動(dòng)（）個(gè)元素。A.n-iB.n-i+1C.iD.i-15.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以6.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL7.設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（）A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p8.棧和隊(duì)列的共同特點(diǎn)是（）A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)9.若進(jìn)棧序列為1，2，3，4，進(jìn)棧過程中可以出棧，則下列不可能的一個(gè)出棧序列是（）A.1，4，3，2B.2，3，4，1C.3，1，4，2D.3，4，2，110.一個(gè)棧的輸入序列為1，2，3，4，若輸出序列的第一個(gè)元素是3，則輸出序列的第二個(gè)元素是（）A.1B.2C.4D.不能確定11.循環(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-front12.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（）A.1和5B.2和4C.4和2D.5和113.樹最適合用來表示（）A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)14.一棵深度為5的滿二叉樹有（）個(gè)結(jié)點(diǎn)。A.15B.16C.31D.3215.若一棵二叉樹的前序遍歷序列為A，B，C，后序遍歷序列為C，B，A，則根結(jié)點(diǎn)為（）A.AB.BC.CD.無(wú)法確定16.已知二叉樹的中序遍歷序列為ABCDEFG，后序遍歷序列為BDCAFGE，則前序遍歷序列為（）A.EACBDGFB.EACBDFGC.EACDBGFD.EABCDGF17.具有n個(gè)頂點(diǎn)的有向圖最多有（）條邊。A.n(n-1)/2B.n(n-1)C.nD.n+118.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)19.圖的深度優(yōu)先搜索類似于樹的（）遍歷。A.先序B.中序C.后序D.層次20.以下排序方法中，平均時(shí)間復(fù)雜度為O(n^2)的是（）A.快速排序B.堆排序C.冒泡排序D.歸并排序第II卷（非選擇題，共60分）答題要求：本大題共5小題，共60分。請(qǐng)將答案寫在相應(yīng)的答題區(qū)域內(nèi)。21.（10分）簡(jiǎn)述線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。22.（10分）已知一個(gè)棧的進(jìn)棧序列為1，2，3，4，5，試寫出所有可能的出棧序列。23.（10分）一棵二叉樹的先序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，畫出該二叉樹。24.（15分）閱讀以下材料：有一個(gè)表示學(xué)生信息的結(jié)構(gòu)體數(shù)組，每個(gè)學(xué)生結(jié)構(gòu)體包含學(xué)號(hào)、姓名、成績(jī)等信息。要求編寫一個(gè)函數(shù)，能夠根據(jù)學(xué)生的成績(jī)對(duì)結(jié)構(gòu)體數(shù)組進(jìn)行降序排序。請(qǐng)回答以下問題：（1）選擇一種合適的排序算法，并簡(jiǎn)述其基本思想。（2）寫出實(shí)現(xiàn)該排序算法的C語(yǔ)言代碼。25.（15分）閱讀以下材料：有一個(gè)無(wú)向圖，其鄰接矩陣如下：0101101001011010要求：（1）畫出該無(wú)向圖。（2）計(jì)算該無(wú)向圖的連通分量個(gè)數(shù)。（3）判