站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記。…………密………………封………………線…………第1頁(yè)，共1頁(yè)廣東理工學(xué)院《大數(shù)據(jù)結(jié)構(gòu)與算法》2025學(xué)年第一學(xué)期期末試卷(B)題號(hào)一二三四總分得分注意事項(xiàng)考生須在答題卡指定位置填寫姓名、學(xué)號(hào)、專業(yè)等信息，在試卷上作答無(wú)效。答題時(shí)須使用黑色簽字筆或鋼筆，字跡清晰，卷面整潔?？荚嚱Y(jié)束后，將試卷、答題卡一并交回，不得攜帶出考場(chǎng)。一、單項(xiàng)選擇題（每題2分，共30分）1.以下哪個(gè)不是數(shù)據(jù)結(jié)構(gòu)的基本邏輯結(jié)構(gòu)？A.集合結(jié)構(gòu)B.線性結(jié)構(gòu)C.樹(shù)形結(jié)構(gòu)D.網(wǎng)絡(luò)結(jié)構(gòu)2.線性表的順序存儲(chǔ)結(jié)構(gòu)中，元素之間的邏輯關(guān)系是通過(guò)什么體現(xiàn)的？A.指針B.線性表的存儲(chǔ)位置C.元素的值D.以上都不對(duì)3.在一個(gè)長(zhǎng)度為n的順序表中，刪除第i個(gè)元素（1≤i≤n）時(shí)，需要移動(dòng)多少個(gè)元素？A.n-iB.n-i+1C.iD.i-14.棧的特點(diǎn)是？A.先進(jìn)先出B.后進(jìn)先出C.隨機(jī)進(jìn)出D.以上都不對(duì)5.隊(duì)列的操作原則是？A.先進(jìn)先出B.后進(jìn)先出C.隨機(jī)進(jìn)出D.以上都不對(duì)6.一個(gè)棧的輸入序列為1,2,3,4,5，則下列序列中不可能是棧的輸出序列的是？A.5,4,3,2,1B.4,3,5,1,2C.4,5,3,2,1D.1,2,3,4,57.若進(jìn)棧序列為1,2,3,4，進(jìn)棧過(guò)程中可以出棧，則下列不可能的一個(gè)出棧序列是？A.1,4,3,2B.2,3,4,1C.3,1,4,2D.3,4,2,18.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是？A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)9.深度為5的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)不可能是？A.15B.16C.17D.1810.一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是？A.250B.500C.501D.以上都不對(duì)11.對(duì)有序表(2,5,7,10,14,15,18,23,35,41,52)進(jìn)行折半查找，查找元素10的比較次數(shù)是？A.2B.3C.4D.512.已知關(guān)鍵字集合K={60,40,49,23,25,13,95,196,85}，創(chuàng)建平衡二叉排序樹(shù)，其根結(jié)點(diǎn)的值為？A.49B.60C.23D.4013.以下排序算法中，平均時(shí)間復(fù)雜度為O(nlogn)且穩(wěn)定的是？A.快速排序B.堆排序C.歸并排序D.冒泡排序14.以下哪個(gè)算法的時(shí)間復(fù)雜度不是O(n^2)？A.選擇排序B.插入排序C.快速排序D.冒泡排序15.哈希表的平均查找長(zhǎng)度主要取決于？A.哈希表的大小B.哈希函數(shù)C.表中元素的個(gè)數(shù)D.哈希函數(shù)和處理沖突的方法二、填空題（每題2分，共20分）1.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括數(shù)據(jù)的______結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。2.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和______域。3.棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是______和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。4.隊(duì)列是一種特殊的線性表，它的操作原則是______。5.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的連通圖，其生成樹(shù)的邊數(shù)為_(kāi)_____。6.一棵二叉樹(shù)第i（i≥1）層上最多有______個(gè)結(jié)點(diǎn)。7.中序遍歷二叉排序樹(shù)可以得到一個(gè)______序列。8.對(duì)一組記錄(54,38,96,23,15,72,60,45,83)進(jìn)行快速排序，以第一個(gè)記錄為基準(zhǔn)，一趟快速排序后的結(jié)果為_(kāi)_____。9.直接插入排序的時(shí)間復(fù)雜度為_(kāi)_____。10.哈希表的沖突是指______。三、簡(jiǎn)答題（每題10分，共30分）1.簡(jiǎn)述線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。2.簡(jiǎn)述圖的深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）算法的基本思想。3.簡(jiǎn)述三種常見(jiàn)的排序算法（選擇排序、插入排序、冒泡排序）的基本思想，并比較它們的時(shí)間復(fù)雜度和穩(wěn)定性。四、算法設(shè)計(jì)題（10分）設(shè)計(jì)一個(gè)算法，判斷一個(gè)給定的字符串是否為回文串?；匚拇侵刚醋x都相同的字符串，例如“l(fā)evel”、“abba”等。要求用偽代碼描述算法。五、綜合應(yīng)用題（