（第2頁）制卷人簽名：制卷日期制卷人簽名：制卷日期：審核人簽名：：審核日期：………………………………………………裝……訂……線…………………學(xué)院專業(yè)/班級學(xué)號姓名題號一二三四五六七八總分閱卷教師得分………………一、單項(xiàng)選擇題（總共10題，每題3分，每題給出的四個選項(xiàng)中，只有一個選項(xiàng)是符合題目要求的，請將正確選項(xiàng)前的字母填在題后的括號內(nèi)）1.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法，正確的是（）A.數(shù)據(jù)結(jié)構(gòu)只研究數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)只研究數(shù)據(jù)的存儲結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)及其之間的關(guān)系D.數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)無關(guān)2.線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.散列存取3.棧的特點(diǎn)是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.進(jìn)出無序4.隊(duì)列的操作原則是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.進(jìn)出無序5.深度為5的完全二叉樹的結(jié)點(diǎn)數(shù)不可能是（）A.15B.16C.17D.186.具有n個頂點(diǎn)的連通圖至少有（）條邊。A.n-1B.nC.n+1D.2n7.對線性表進(jìn)行二分查找時(shí)，要求線性表必須（）A.以順序方式存儲B.以鏈?zhǔn)椒绞酱鎯.以順序方式存儲，且數(shù)據(jù)元素有序D.以鏈?zhǔn)椒绞酱鎯?，且?shù)據(jù)元素有序8.以下排序算法中，平均時(shí)間復(fù)雜度為O(nlogn)的是（）A.冒泡排序B.選擇排序C.插入排序D.快速排序9.哈希表的平均查找長度主要取決于（）A.哈希表的大小B.數(shù)據(jù)元素的個數(shù)C.哈希函數(shù)和沖突處理方法D.數(shù)據(jù)元素的類型10.若一棵二叉樹的先序遍歷序列為ABCDEF，中序遍歷序列為CBAEDF，則后序遍歷序列為（）A.CBEFDAB.FEDCBAC.CBFEDAD.ABCDEF二、多項(xiàng)選擇題（總共5題，每題4分，每題給出的五個選項(xiàng)中，有二至五個選項(xiàng)是符合題目要求的，請將正確選項(xiàng)前的字母填在題后的括號內(nèi)。多選、少選、錯選均不得分）1.以下屬于數(shù)據(jù)的邏輯結(jié)構(gòu)的有（）A.線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.圖狀結(jié)構(gòu)D.順序結(jié)構(gòu)E.鏈?zhǔn)浇Y(jié)構(gòu)2.棧和隊(duì)列的共同點(diǎn)是（）A.都是線性結(jié)構(gòu)B.都有插入和刪除操作C.都允許在端點(diǎn)處進(jìn)行操作D.都不允許在中間位置進(jìn)行操作E.操作原則相同3.以下關(guān)于二叉樹的說法，正確的有（）A.二叉樹的每個結(jié)點(diǎn)最多有兩個子結(jié)點(diǎn)B.二叉樹可以為空C.二叉樹的左右子樹有順序之分D.滿二叉樹一定是完全二叉樹E.完全二叉樹一定是滿二叉樹4.以下排序算法中，哪些是穩(wěn)定的排序算法（）A.冒泡排序B.選擇排序C.插入排序D.快速排序E.歸并排序5.對于哈希表，以下說法正確的有（）A.哈希表能直接通過關(guān)鍵字計(jì)算出存儲地址B.哈希表的查找效率比順序查找高C.哈希表可能會產(chǎn)生沖突D.沖突處理方法會影響哈希表的性能E.哈希表的大小固定后不能改變?nèi)?、判斷題（總共10題，每題2分，請判斷下列各題的正誤，正確的在題后的括號內(nèi)打“√”，錯誤的打“×”）1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中的存儲方式。（）2.線性表的順序存儲結(jié)構(gòu)中，插入和刪除操作的時(shí)間復(fù)雜度都是O(1)。（）3.棧可以用來實(shí)現(xiàn)遞歸算法。（）4.隊(duì)列可以用來實(shí)現(xiàn)廣度優(yōu)先搜索算法。（）5.二叉樹的度為2。（）6.完全二叉樹中，若一個結(jié)點(diǎn)沒有左子結(jié)點(diǎn)，則它一定沒有右子結(jié)點(diǎn)。（）7.圖的遍歷算法有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種。（）8.快速排序是一種穩(wěn)定的排序算法。（）9.哈希表的查找效率與哈希函數(shù)和沖突處理方法無關(guān)。（）10.中序遍歷二叉排序樹可以得到一個有序序列。（）四、簡答題（總共3題，每題10分，請簡要回答下列問題）1.簡述線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。2.簡述棧和隊(duì)列的區(qū)別，并舉例說明它們在實(shí)際應(yīng)用中的場景。3.簡述圖的鄰接矩陣存儲方式和鄰接表存儲方式的特點(diǎn)。五、算法設(shè)計(jì)題（總共2題，每題1