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

（考試時間：90分鐘滿分100分）班級______姓名______第I卷（選擇題共40分）每題只有一個正確答案，請將正確答案填在括號內(nèi)。(總共20題，每題2分，每題選出符合題意的選項)1.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，錯誤的是（）A.數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合B.數(shù)據(jù)結(jié)構(gòu)的基本操作是指對數(shù)據(jù)元素的插入、刪除、修改、查找等C.數(shù)據(jù)結(jié)構(gòu)只研究數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D.數(shù)據(jù)結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)2.線性表的順序存儲結(jié)構(gòu)中，元素之間的邏輯關(guān)系是通過（）體現(xiàn)的。A.指針B.線性表的長度C.相鄰存儲位置D.元素的存儲序號3.若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A.順序表B.單鏈表C.雙向鏈表D.循環(huán)鏈表4.在一個長度為n的順序表中，刪除第i個元素（1≤i≤n）時，需要向前移動（）個元素。A.n-iB.n-i+1C.iD.i-15.單鏈表中，增加一個頭結(jié)點的目的是（）A.使用統(tǒng)一的頭指針，方便運算B.標(biāo)識表中首結(jié)點的位置C.使單鏈表至少有一個結(jié)點D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?.帶頭結(jié)點的單鏈表head為空的判定條件是（）A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL7.雙向鏈表中有兩個指針域，llink和rlink，分別指向前驅(qū)及后繼結(jié)點。設(shè)p指向鏈表中的一個結(jié)點，q指向一待插入結(jié)點，現(xiàn)要求在p前插入q，則正確的插入為（）A.p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;B.q->llink=p->llink;p->llink->rlink=q;q->rlink=p;p->llink=q->rlink;C.q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;D.p->llink->rlink=q;q->rlink=p;q->llink=p->llink;p->llink=q;8.棧和隊列的共同特點是（）A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點處插入和刪除元素D.沒有共同點9.一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（）A.edcbaB.decbaC.dceabD.abcde10.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（）A.1和5B.2和4C.4和2D.5和111.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是（）A.39B.52C.111D.11912.深度為5的二叉樹至多有（）個結(jié)點。A.16B.32C.31D.１０13.設(shè)二叉樹中有20個葉子結(jié)點，5個度為1的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為（）A.45B.46C.44D.不可能有這樣的二叉樹14.若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用（）遍歷方法最合適。A.前序B.中序C.后序D.按層次15.對n個關(guān)鍵字進(jìn)行快速排序，最大遞歸深度為（）A.nB.n/2C.log2nD.nlog2n16.對一組數(shù)據(jù)（25,84,21,47,15,27,68,35,20）進(jìn)行排序，前3趟的排序結(jié)果如下：第一趟：20,15,21,25,47,27,68,35,84第二趟：15,20,21,25,27,47,35,68,84第三趟：15,20,21,25,27,35,47,68,84則所采用的排序方法是（）A.冒泡排序B.選擇排序C.快速排序D.插入排序17.哈希表的平均查找長度與（）有關(guān)。A.哈希函數(shù)B.哈希表的裝填因子C.哈希表的大小D.以上都是18.順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。A.順序存儲或鏈?zhǔn)酱鎯.散列存儲C.壓縮存儲D.索引存儲19.折半查找有序表（4,6,10,12,20,30,50,70,88,100）。若查找表中元素58，則它將依次與表中（）比較大小，查找結(jié)果是失敗。A.20,70,30,50B.30,88,70,50C.20,50D.30,88,5020.設(shè)有一個二維數(shù)組A[10][20]，其每個元素占2個字節(jié)，第一個元素的存儲地址為1000。若按行優(yōu)先順序存儲，則元素A[5][10]的存儲地址為（）A.1160B.1170C.1180D.1190第II卷（非選擇題共60分）填空題（每題2分，共10分）請將正確答案填在橫線上。1.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和____________。2.順序表中邏輯上相鄰的元素，其物理位置____________。3.棧的操作特性是____________，隊列的操作特性是____________。4.二叉樹第i層上至多有____________個結(jié)點。5.對于長度為n的線性表，在最壞情況下，冒泡排序的比較次數(shù)為____________。簡答題（每題5分，共15分）1.簡述線性表順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。2.簡述棧和隊列的區(qū)別。3.簡述二叉排序樹的定義及特點。算法設(shè)計題（每題10分，共20分）1.設(shè)計一個算法，將帶頭結(jié)點的單鏈表逆置。2.已知一棵二叉樹的前序遍歷序列和中序遍歷序列，設(shè)計算法重建該二叉樹。綜合應(yīng)用題（每題10分，共15分）1.有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100}，當(dāng)用折半查找法查找值為82的元素時，需要經(jīng)過多少次比較？2.假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)是多少？請給出計算表達(dá)式。答案1.C2.C3.A4.A5.A6.B7.D8.C9.C10.B11.C12.C13.C14.C15.C16.D17.D18.A19.B20.B填空題答案：1.數(shù)據(jù)的運算2.也相鄰3.后進(jìn)先出；先進(jìn)先出4.2^(i-1)5.n(n-1)/2簡答題答案：1.順序存儲結(jié)構(gòu)優(yōu)點：存儲密度大，可隨機(jī)存?。蝗秉c：插入刪除操作效率低，可能導(dǎo)致大量元素移動。鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)點：插入刪除操作效率高，無需移動元素；缺點：存儲密度小，需額外指針空間，不能隨機(jī)存取。2.棧是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，只有一個入口和一個出口；隊列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，有一個入口和一個出口。3.二叉排序樹定義：左子樹上所有結(jié)點的值均小于根結(jié)點的值；右子樹上所有結(jié)點的值均大于根結(jié)點的值；左、右子樹也分別為二叉排序樹。特點：中序遍歷二叉排序樹可得到一個有序序列。算法設(shè)計題答案：1.算法思路：遍歷單鏈表，將每個結(jié)點的next指針指向前驅(qū)結(jié)點。2.算法思路：從前序遍歷序列中取出第一個元素作為根結(jié)點，在中序遍歷序列中找到該根結(jié)點，其左邊部分為左子樹中序序列，右邊部分為右子樹中序序列，再根據(jù)左子樹中序序列長度從前序遍歷序列中取出相應(yīng)元素構(gòu)建左子樹，剩余元素構(gòu)建右子樹。綜合應(yīng)用題答案：1.第