第1頁(yè)學(xué)院：專(zhuān)業(yè)班級(jí)：姓名：學(xué)院：專(zhuān)業(yè)班級(jí)：姓名：學(xué)號(hào)：裝訂線內(nèi)不要答題學(xué)院/專(zhuān)業(yè)：__________姓名：__________學(xué)號(hào)：__________注意事項(xiàng)：1、本試卷滿分100分。2、考試時(shí)間120分鐘。題號(hào)一二三四五六七得分得分評(píng)閱人一、單項(xiàng)選擇題（總共10題，每題3分，從下列各題的4個(gè)選項(xiàng)中選出一個(gè)正確答案，并將其代號(hào)寫(xiě)在答題紙相應(yīng)位置處）1.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，哪一項(xiàng)是正確的？A.數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于其存儲(chǔ)結(jié)構(gòu)B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)獨(dú)立于其邏輯結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)唯一決定其存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)只影響其操作的時(shí)間復(fù)雜度2.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表3.一個(gè)棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（）。A.edcbaB.decbaC.dceabD.abcde4.深度為5的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)不可能是（）。A.15B.16C.17D.185.對(duì)具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)進(jìn)行中序遍歷，其時(shí)間復(fù)雜度為（）。A.O(n)B.O(n)C.O(logn)D.O(nlogn)6.以下關(guān)于圖的敘述中，正確的是（）。A.圖的遍歷是從給定的源點(diǎn)出發(fā)，按照某種搜索方法沿著圖的邊訪問(wèn)圖中的所有頂點(diǎn)B.圖的深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的前序遍歷C.圖的廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的中序遍歷D.圖的遍歷只能采用深度優(yōu)先搜索或廣度優(yōu)先搜索7.已知一個(gè)有序表為{10,20,30,40,50,60,70}，當(dāng)用二分查找法查找值為40的元素時(shí)，經(jīng)過(guò)（）次比較后查找成功。A.1B.2C.3D.48.以下排序方法中，穩(wěn)定的排序方法是（）。A.快速排序B.堆排序C.冒泡排序D.希爾排序9.設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍虼鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（）。A.13B.33C.18D.4010.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)應(yīng)用的敘述中，錯(cuò)誤的是（）。A.棧可以用于實(shí)現(xiàn)遞歸算法B.隊(duì)列可以用于實(shí)現(xiàn)廣度優(yōu)先搜索算法C.二叉排序樹(shù)可以用于實(shí)現(xiàn)排序功能D.哈希表可以用于實(shí)現(xiàn)數(shù)據(jù)的高效查找，但不能用于實(shí)現(xiàn)數(shù)據(jù)的插入和刪除操作二、多項(xiàng)選擇題（總共5題，每題4分，從下列各題的5個(gè)選項(xiàng)中選出2-4個(gè)正確答案，并將其代號(hào)寫(xiě)在答題紙相應(yīng)位置處，多選、少選、錯(cuò)選均不得分）1.下列哪些是線性結(jié)構(gòu)（）。A.數(shù)組B.棧C.隊(duì)列D.二叉樹(shù)E.圖2.以下關(guān)于棧的操作中，正確的是（）。A.棧頂元素可以隨時(shí)被訪問(wèn)B.棧底元素可以隨時(shí)被訪問(wèn)C.入棧操作會(huì)改變棧頂指針D.出棧操作會(huì)改變棧頂指針E.棧為空時(shí)不能進(jìn)行出棧操作3.對(duì)于一棵二叉排序樹(shù)，以下說(shuō)法正確的是（）。A.左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值B.右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值C.中序遍歷該二叉排序樹(shù)可以得到一個(gè)有序序列D.前序遍歷該二叉排序樹(shù)可以得到一個(gè)有序序列E.后序遍歷該二叉排序樹(shù)可以得到一個(gè)有序序列4.以下哪些排序算法的時(shí)間復(fù)雜度為O(n)（）。A.冒泡排序B.選擇排序C.插入排序D.快速排序E.歸并排序5.哈希表的沖突處理方法有（）。A.開(kāi)放定址法B.鏈地址法C.rehash法D.二次探測(cè)法E.再散列法三、判斷題（總共10題，每題2分，判斷下列各題，正確的在答題紙相應(yīng)位置處填“√”，錯(cuò)誤的填“×”）1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。（）2.順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入和刪除操作效率高。（）3.棧和隊(duì)列都是操作受限的線性表，它們的操作都是按先進(jìn)后出的原則進(jìn)行的。（）4.完全二叉樹(shù)一定是滿二叉樹(shù)。（）5.二叉排序樹(shù)的查找效率與二叉樹(shù)的高度有關(guān)。（）6.圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷都可以訪問(wèn)到圖中的所有頂點(diǎn)。（）7.二分查找法只適用于有序的順序表。（）8.快速排序是一種不穩(wěn)定的排序方法，其平均時(shí)間復(fù)雜度為O(nlogn)。（）9.稀疏矩陣壓縮存儲(chǔ)的目的是節(jié)省存儲(chǔ)空間。（）10.哈希表的平均查找長(zhǎng)度與哈希函數(shù)無(wú)關(guān)。（）四、簡(jiǎn)答題（總共3題，每題10分）1.簡(jiǎn)述順序表和鏈表的優(yōu)缺點(diǎn)。2.簡(jiǎn)述圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的基本思想。3.簡(jiǎn)述哈希表的基本概念，并說(shuō)明哈希函數(shù)的設(shè)計(jì)原則。五、算法設(shè)計(jì)題（總共2題，每題15分）1.設(shè)計(jì)一個(gè)算法，判斷一個(gè)給定的二叉樹(shù)是否為平衡二叉樹(shù)。平衡二叉樹(shù)的定義為：任意結(jié)點(diǎn)的左右子樹(shù)高度差的絕對(duì)值不超過(guò)1，并且左右子樹(shù)都是一棵