第1頁學院：專業(yè)班級：姓名：學院：專業(yè)班級：姓名：學號：裝訂線內(nèi)不要答題學院/專業(yè)：__________姓名：__________學號：__________注意事項：1、本試卷滿分100分。2、考試時間120分鐘。題號一二三四五六七得分得分評閱人一、單項選擇題(總共10題，每題3分，每題只有一個正確答案，請將正確答案填入括號內(nèi))1.線性表采用鏈式存儲時，其地址（）。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可2.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A.順序表B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表3.以下關于棧的敘述中，正確的是（）。A.棧底元素一定是最后入棧的元素B.棧頂元素一定是最先入棧的元素C.棧操作遵循先進后出的原則D.以上說法均錯誤4.若進棧序列為1，2，3，4，進棧過程中可以出棧，則（）不可能是一個出棧序列。A.1，4，3，2B.2，3，4，1C.3，1，4，2D.3，4，2，15.深度為5的完全二叉樹的結(jié)點數(shù)不可能是（）。A.15B.16C.17D.186.一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。A.250B.500C.501D.以上都不對7.對線性表進行二分查找時，要求線性表必須（）。A.以順序方式存儲B.以鏈式方式存儲C.以順序方式存儲，且結(jié)點按關鍵字有序排列D.以鏈式方式存儲，且結(jié)點按關鍵字有序排列8.散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應當以（）取其值域的每個值。A.最大概率B.最小概率C.平均概率D.同等概率9.下面關于B樹和B+樹的敘述中，不正確的是（）。A.B樹和B+樹都是平衡的多叉樹B.B樹和B+樹都可用于文件的索引結(jié)構C.B樹和B+樹都能有效地支持順序檢索D.B樹和B+樹都能有效地支持隨機檢索10.已知一棵二叉樹的先序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，則該二叉樹的后序遍歷序列為（）。A.DEFBCAB.DFEBCAC.DFBECAD.BDFECA二、多項選擇題(總共5題，每題4分，每題有兩個或兩個以上正確答案，請將正確答案填入括號內(nèi))1.以下哪些是線性表的基本操作（）。A.查找B.插入C.刪除D.排序2.棧的應用包括（）。A.表達式求值B.遞歸調(diào)用C.深度優(yōu)先搜索D.廣度優(yōu)先搜索3.以下關于二叉樹的說法正確的是（）。A.二叉樹的每個結(jié)點最多有兩棵子樹B.二叉樹可以為空C.二叉樹的左右子樹有順序之分D.滿二叉樹一定是完全二叉樹4.以下哪些排序算法是穩(wěn)定的（）。A.冒泡排序B.選擇排序C.插入排序D.歸并排序5.以下關于圖的說法正確的是（）。A.圖可以分為有向圖和無向圖B.圖的遍歷可以采用深度優(yōu)先搜索和廣度優(yōu)先搜索C.最小生成樹問題可以用Prim算法和Kruskal算法解決D.拓撲排序可以判斷一個有向圖是否存在環(huán)三、判斷題(總共10題，每題2分，請判斷對錯，在括號內(nèi)打√或×)1.線性表的順序存儲結(jié)構優(yōu)于鏈式存儲結(jié)構。（）2.棧是一種先進先出的數(shù)據(jù)結(jié)構。（）3.完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是葉子結(jié)點。（）4.二叉排序樹的中序遍歷序列是有序的。（）5.快速排序在最壞情況下的時間復雜度為O(n)。（）6.散列表的平均查找長度與散列函數(shù)無關。（）7.圖的鄰接矩陣存儲方式適用于存儲稀疏圖。（）8.拓撲排序的結(jié)果是唯一的。（）9.堆排序是一種穩(wěn)定的排序算法。（）10.順序查找適用于任何存儲結(jié)構的線性表。（）四、簡答題(總共3題，每題10分)1.簡述線性表順序存儲結(jié)構和鏈式存儲結(jié)構的優(yōu)缺點。2.簡述深度優(yōu)先搜索和廣度優(yōu)先搜索的基本思想，并說明它們在圖遍歷中的應用場景。3.簡述最小生成樹的概念，并說明Prim算法和K