（第2頁）制卷人簽名：制卷日期制卷人簽名：制卷日期：審核人簽名：：審核日期：………………………………………………裝……訂……線…………………學(xué)院專業(yè)/班級(jí)學(xué)號(hào)姓名題號(hào)一二三四五六七八總分閱卷教師得分………………一、單項(xiàng)選擇題（總共10題，每題3分，每題只有一個(gè)正確答案，請(qǐng)將正確答案填入括號(hào)內(nèi)）1.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以2.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表3.棧和隊(duì)列的共同點(diǎn)是（）。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)4.一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（）。A.5，4，3，2，1B.4，5，3，2，1C.4，3，5，1，2D.1，2，3，4，55.若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)是（）。A.9B.11C.12D.不確定6.設(shè)哈夫曼樹中的葉結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（）個(gè)空指針域。A.2m-1B.2mC.2m+1D.4m7.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）。A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)8.深度為k的完全二叉樹至少有（）個(gè)結(jié)點(diǎn)。A.2k-1B.2kC.2k+1D.2k-29.對(duì)長(zhǎng)度為n的線性表進(jìn)行二分查找，在最壞情況下所需要的比較次數(shù)為（）。A.log2nB.n/2C.nD.n+110.下列排序方法中，平均時(shí)間復(fù)雜度為O(nlogn)且空間復(fù)雜度為O(1)的是（）。A.快速排序B.堆排序C.歸并排序D.冒泡排序二、多項(xiàng)選擇題（總共5題，每題4分，每題有兩個(gè)或兩個(gè)以上正確答案，請(qǐng)將正確答案填入括號(hào)內(nèi)）1.以下哪些是線性結(jié)構(gòu)（）。A.順序表B.棧C.隊(duì)列D.二叉樹2.下列關(guān)于棧的敘述中，正確的是（）。A.棧頂元素最先能被刪除B.棧底元素最后才能被刪除C.棧底元素是最先被插入的D.棧是先進(jìn)后出的線性表3.一棵二叉樹的前序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDGF，則后序遍歷序列為（）。A.CBEFDGAB.FEDCBAC.CBFEDGAD.ABCDEFG4.下列哪些算法的平均時(shí)間復(fù)雜度是O(n)（）。A.冒泡排序B.選擇排序C.插入排序D.快速排序5.對(duì)于順序存儲(chǔ)的線性表，訪問元素和插入元素的時(shí)間復(fù)雜度分別為（）。A.O(1)B.O(n)C.O(logn)D.O(n)三、判斷題（總共10題，每題2分，判斷對(duì)錯(cuò)，對(duì)的打√，錯(cuò)的打×）1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（）2.棧和隊(duì)列都是操作受限的線性表。（）3.完全二叉樹一定是滿二叉樹。（）4.哈夫曼樹的帶權(quán)路徑長(zhǎng)度最小。（）5.圖的鄰接矩陣存儲(chǔ)方式只適用于無向圖。（）6.任何一個(gè)遞歸算法都可以轉(zhuǎn)換成非遞歸算法。（）7.排序算法中的比較次數(shù)越少，算法效率越高。（）8.順序查找法適用于任何存儲(chǔ)結(jié)構(gòu)的線性表。（）9.二叉排序樹的中序遍歷序列是一個(gè)有序序列。（）10.線性表的長(zhǎng)度是指線性表中數(shù)據(jù)元素的個(gè)數(shù)。（）四、簡(jiǎn)答題（總共3題，每題10分）1.簡(jiǎn)述順序表和鏈表的優(yōu)缺點(diǎn)。2.簡(jiǎn)述深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）遍歷圖的基本思想，并說明它們?cè)趹?yīng)用場(chǎng)景上的區(qū)別。3.簡(jiǎn)述快速排序的基本思想，并分析其平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度。五、算法設(shè)計(jì)