（第2頁）制卷人簽名：制卷日期制卷人簽名：制卷日期：審核人簽名：：審核日期：………………………………………………裝……訂……線…………………學(xué)院專業(yè)/班級學(xué)號姓名題號一二三四五六七八總分閱卷教師得分………………一、單項選擇題（總共10題，每題3分，每題只有一個正確答案，請將正確答案填寫在括號內(nèi)）1.以下關(guān)于線性表的說法，錯誤的是（）A.線性表是一種線性結(jié)構(gòu)B.線性表可以采用順序存儲或鏈?zhǔn)酱鎯.線性表的插入和刪除操作在順序存儲下效率更高D.線性表的元素具有一對一的邏輯關(guān)系2.已知一個棧的進棧序列為1,2,3,4,5，則下列不可能是其出棧序列的是（）A.5,4,3,2,1B.4,3,5,1,2C.2,1,3,4,5D.3,2,1,5,43.深度為5的完全二叉樹的結(jié)點數(shù)不可能是（）A.15B.16C.17D.184.對有序表(2,5,7,10,14,15,18,23,35,41,52)進行折半查找，查找元素10的比較次數(shù)是（）A.2B.3C.4D.55.若一棵二叉樹的前序遍歷序列為A,B,C,D，中序遍歷序列為B,A,D,C，則后序遍歷序列為（）A.B,D,C,AB.D,B,C,AC.D,C,B,AD.B,C,D,A6.以下排序算法中，平均時間復(fù)雜度為O(n)的是（）A.快速排序B.歸并排序C.冒泡排序D.堆排序7.哈希表的平均查找長度主要取決于（）A.哈希表的大小B.哈希函數(shù)C.哈希表的裝填因子D.以上都是8.對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）A.nB.nC.n(n-1)D.(n-1)9.以下關(guān)于圖的說法，正確的是（）A.連通圖的生成樹是唯一的B.無向圖的鄰接表表示比鄰接矩陣表示更節(jié)省空間C.有向圖的拓?fù)渑判蚪Y(jié)果是唯一的D.最短路徑問題只能用Dijkstra算法求解10.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）A.存儲結(jié)構(gòu)B.物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.物理和存儲結(jié)構(gòu)二、多項選擇題（總共5題，每題4分，每題有兩個或兩個以上正確答案，請將正確答案填寫在括號內(nèi)，多選、少選、錯選均不得分）1.下列關(guān)于棧和隊列的說法，正確的有（）A.棧是后進先出的數(shù)據(jù)結(jié)構(gòu)B.隊列是先進先出的數(shù)據(jù)結(jié)構(gòu)C.棧和隊列都可以采用順序存儲和鏈?zhǔn)酱鎯.棧和隊列的操作都只在一端進行2.下列哪些是二叉排序樹的性質(zhì)（）A.左子樹上所有結(jié)點的值均小于根結(jié)點的值B.右子樹上所有結(jié)點的值均大于根結(jié)點的值C.左右子樹也分別是二叉排序樹D.中序遍歷二叉排序樹可以得到一個有序序列3.以下哪些排序算法是穩(wěn)定的（）A.冒泡排序B.選擇排序C.插入排序D.歸并排序4.對于一個有向圖，以下說法正確的是（）A.強連通圖的任意兩個頂點之間都有路徑B.有向圖的鄰接矩陣中，第i行非零元素的個數(shù)表示頂點i的出度C.有向圖的鄰接矩陣中，第j列非零元素的個數(shù)表示頂點j的入度D.有向圖的拓?fù)渑判蚪Y(jié)果可能不唯一5.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法，正確的有（）A.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)B.算法的時間復(fù)雜度與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)C.數(shù)據(jù)的邏輯結(jié)構(gòu)決定了數(shù)據(jù)的運算D.數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合三、判斷題（總共10題，每題2分，請判斷下列說法的對錯，在括號內(nèi)打“√”或“×”）1.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。（）2.空棧和空隊列都是沒有元素的棧和隊列。（）3.完全二叉樹一定是滿二叉樹。（）4.折半查找只能用于有序表。（）5.二叉排序樹的刪除操作比插入操作復(fù)雜。（）6.快速排序在最壞情況下的時間復(fù)雜度為O(n)。（）7.哈希表中不存在哈希沖突。（）8.有向圖的鄰接表表示比鄰接矩陣表示更適合求頂點的入度。（）9.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索得到的生成樹是相同的。（）10.數(shù)據(jù)結(jié)構(gòu)的設(shè)計會影響算法的效率。（）四、簡答題（總共3題，每題10分）1.簡述順序表和鏈表的優(yōu)缺點。2.簡述二叉排序樹的插入和刪除操作的基本步驟。3.簡述