數(shù)據(jù)結(jié)構(gòu)原理及應(yīng)用考試題單項(xiàng)選擇題（每題2分，共20分）1.數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容是A.數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)的各種基本操作D.以上三項(xiàng)都是2.下列哪種數(shù)據(jù)結(jié)構(gòu)最適合用來表示具有一對(duì)多關(guān)系的數(shù)據(jù)？A.數(shù)組B.鏈表C.樹D.圖3.在順序存儲(chǔ)結(jié)構(gòu)的線性表中，插入和刪除元素時(shí)平均需要移動(dòng)的元素個(gè)數(shù)為A.O(1)B.O(n)C.O(n^2)D.O(logn)4.棧和隊(duì)列的共同特點(diǎn)是A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)5.在二叉樹的先序遍歷序列中，若結(jié)點(diǎn)A在結(jié)點(diǎn)B的前面，則在下列遍歷序列中A也一定在B前面的是A.中序遍歷B.后序遍歷C.層次遍歷D.以上都不對(duì)6.已知哈希表的地址空間為0到11，哈希函數(shù)為H(key)=key%12，采用線性探測法解決沖突。若依次插入的鍵值為25，14，29，15，20，則20的地址為A.4

B.5C.6

D.77.在圖的深度優(yōu)先搜索（DFS）中，如果采用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，則對(duì)每一個(gè)頂點(diǎn)，需要訪問其鄰接矩陣中的A.一行B.一列C.一行和一列D.與該頂點(diǎn)相關(guān)的元素8.下列排序算法中，時(shí)間復(fù)雜度為O(n^2)的是A.快速排序B.堆排序C.歸并排序D.冒泡排序9.在一個(gè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為A.?n/2?

B.?n/2?

C.n-1D.?(n+1)/2?10.在最小堆中，最小元素位于A.堆頂B.堆底C.堆的中間位置D.不確定多項(xiàng)選擇題（每題4分，共40分）1.下列哪些數(shù)據(jù)結(jié)構(gòu)屬于線性結(jié)構(gòu)？A.數(shù)組B.鏈表C.棧D.圖E.隊(duì)列2.在鏈表中，以下哪些操作可以在O(1)時(shí)間復(fù)雜度內(nèi)完成？A.在鏈表頭部插入元素B.在鏈表尾部插入元素（單鏈表）C.查找鏈表中第i個(gè)元素D.刪除鏈表中值為x的第一個(gè)節(jié)點(diǎn)E.在鏈表頭部刪除元素3.下列關(guān)于二叉樹的敘述中，正確的是A.二叉樹的度為2B.二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2C.二叉樹中不存在度為1的結(jié)點(diǎn)D.二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹的次序不能顛倒E.任何一棵二叉樹都可以轉(zhuǎn)換為一棵對(duì)應(yīng)的樹或森林4.在哈希表的裝填因子α固定的情況下，哈希表的查找效率主要取決于A.哈希函數(shù)的設(shè)定B.處理沖突的方法C.哈希表的大小D.待查找元素的個(gè)數(shù)E.元素的插入順序5.下列排序算法中，哪些是基于比較的排序算法？A.冒泡排序B.插入排序C.選擇排序D.快速排序E.基數(shù)排序6.下列哪些圖論算法可以用來解決最短路徑問題？A.Dijkstra算法B.Floyd-Warshall算法C.深度優(yōu)先搜索（DFS）D.廣度優(yōu)先搜索（BFS）E.Kruskal算法7.在圖的遍歷過程中，以下哪些說法是正確的？A.深度優(yōu)先搜索（DFS）使用棧實(shí)現(xiàn)B.廣度優(yōu)先搜索（BFS）使用隊(duì)列實(shí)現(xiàn)C.DFS可以檢測到圖中的環(huán)D.BFS通常用于尋找無權(quán)圖中的最短路徑E.DFS和BFS都是非遞歸算法8.下列關(guān)于堆的說法中，正確的是A.堆是一棵完全二叉樹B.最大堆中所有父節(jié)點(diǎn)的鍵值都大于或等于其子節(jié)點(diǎn)的鍵值C.最小堆是一種特殊的完全二叉搜索樹D.在最大堆中，最大元素一定位于堆頂E.堆排序的時(shí)間復(fù)雜度為O(nlogn)9.下列哪些操作可以在平衡二叉樹（AVL樹）上高效完成？A.查找元素B.插入元素C.刪除元素D.查找最小元素E.查找最大元素10.在設(shè)計(jì)哈希表時(shí)，以下哪些因素會(huì)影響哈希表的性能？A.哈希函數(shù)的選擇B.處理沖突的方法C.哈希表的大小D.元素的插入順序E.元素的刪除操作判斷題（每題2分，共20分）1.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，所有元素在內(nèi)存中的存儲(chǔ)位置必須是連續(xù)的。A.正確B.錯(cuò)誤2.在二叉樹中，度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。A.正確B.錯(cuò)誤3.棧是一種后進(jìn)先出的線性表。A.正確B.錯(cuò)誤4.快速排序的最壞時(shí)間復(fù)雜度為O(n)。A.正確B.錯(cuò)誤5.在圖的鄰接表中，頂點(diǎn)在表中的順序?qū)D的遍歷結(jié)果沒有影響。A.正確B.錯(cuò)誤6.任意一棵二叉樹都可以唯一地轉(zhuǎn)換為一棵對(duì)應(yīng)的二叉搜索樹。A.正確B.錯(cuò)誤7.在哈希表中，裝填因子α越大，哈希表的沖突概率越小。A.正確B.錯(cuò)誤8.堆排序是一種不穩(wěn)定的排序算法。A.正確B.錯(cuò)誤9.在有向圖中，若從頂點(diǎn)A到頂點(diǎn)B有路徑，則從B到A也一定有路徑。A.正確B.錯(cuò)誤10.圖的遍歷是指從圖中的某一頂點(diǎn)出發(fā)，訪問圖中所有頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次的過程。A.正確B.錯(cuò)誤填空題（每題2分，共20分）1.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)組和鏈表是兩種最基本的________結(jié)構(gòu)。2.在二叉樹的層次遍歷中，通常使用________數(shù)據(jù)結(jié)構(gòu)來輔助實(shí)現(xiàn)。3.在堆排序算法中，初始時(shí)將一個(gè)無序序列構(gòu)建成________堆。4.若一個(gè)圖的邊集E={(A,B),(B,C),(C,D),(D,A),(A,E)}，則該圖中有________個(gè)環(huán)。5.在快速排序算法中，每次劃分后，基準(zhǔn)元素被放置在劃分后的________位置。6.在哈希表中，處理沖突的兩種基本方法是________和開放地址法。7.在深度優(yōu)先搜索（DFS）過程中，可以利用________數(shù)據(jù)結(jié)構(gòu)來記錄訪問過的頂點(diǎn)。8.在圖的鄰接矩陣表示法中，若圖中有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)________階方陣。9.在最小生成樹算法中，Kruskal算法適用于________圖，而Prim算法既適用于稠密圖也適用于稀疏圖。10.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表表示時(shí)，其空間復(fù)雜度為________。答案：單項(xiàng)選擇題1.D2.C3.B4.C5.B6.D7.A8.D9.D10.A多項(xiàng)選擇題1.AB