數(shù)據(jù)結(jié)構(gòu)試題庫及答案

單項選擇題（每題2分，共10題）1.線性表采用順序存儲結(jié)構(gòu)，訪問第i個元素的時間復(fù)雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)2.棧的特點是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.只進(jìn)不出3.隊列的特點是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.只進(jìn)不出4.具有n個結(jié)點的完全二叉樹的深度為（）A.log?nB.log?n+1C.?log?n?+1D.?log?n?5.對n個元素進(jìn)行冒泡排序，最好情況下的時間復(fù)雜度為（）A.O(1)B.O(n)C.O(n^2)D.O(nlogn)6.哈希表的平均查找長度與（）有關(guān)。A.哈希函數(shù)B.裝填因子C.處理沖突的方法D.以上都是7.圖的深度優(yōu)先遍歷類似于樹的（）遍歷。A.先序B.中序C.后序D.層次8.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A.存儲B.物理C.邏輯D.物理和存儲9.順序查找法適用于存儲結(jié)構(gòu)為（）的線性表。A.順序存儲B.鏈?zhǔn)酱鎯.順序存儲或鏈?zhǔn)酱鎯.索引存儲10.一個棧的輸入序列為1,2,3,4,5，則不可能的輸出序列是（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,5多項選擇題（每題2分，共10題）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）A.棧B.隊列C.樹D.圖2.下列排序算法中，時間復(fù)雜度為O(n^2)的有（）A.冒泡排序B.選擇排序C.插入排序D.快速排序3.樹的遍歷方式有（）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷4.以下哪些是圖的存儲結(jié)構(gòu)（）A.鄰接矩陣B.鄰接表C.十字鏈表D.廣義表5.數(shù)據(jù)結(jié)構(gòu)包括（）三個方面。A.數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)的存儲結(jié)構(gòu)C.數(shù)據(jù)的運算D.數(shù)據(jù)的類型6.對于哈希表，處理沖突的方法有（）A.開放定址法B.鏈地址法C.再哈希法D.建立公共溢出區(qū)7.下列屬于查找算法的有（）A.順序查找B.二分查找C.哈希查找D.冒泡查找8.棧的基本運算有（）A.入棧B.出棧C.讀棧頂元素D.判斷棧是否為空9.隊列的基本運算有（）A.入隊B.出隊C.讀隊頭元素D.判斷隊列是否為空10.以下關(guān)于二叉排序樹的說法正確的有（）A.左子樹上所有結(jié)點的值均小于根結(jié)點的值B.右子樹上所有結(jié)點的值均大于根結(jié)點的值C.左右子樹也都是二叉排序樹D.中序遍歷二叉排序樹可以得到一個有序序列判斷題（每題2分，共10題）1.順序存儲結(jié)構(gòu)的優(yōu)點是存儲密度大，且插入、刪除操作效率高。（）2.棧和隊列都是特殊的線性表。（）3.二叉樹的前序遍歷和中序遍歷序列相同，則該二叉樹每個結(jié)點都沒有左子樹。（）4.圖的廣度優(yōu)先遍歷需要使用隊列輔助實現(xiàn)。（）5.快速排序在最壞情況下的時間復(fù)雜度為O(n^2)。（）6.哈希表是一種基于關(guān)鍵字直接訪問的數(shù)據(jù)結(jié)構(gòu)。（）7.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（）8.對于一個有n個頂點的無向圖，它的鄰接矩陣是一個n×n的對稱矩陣。（）9.二分查找要求線性表必須是順序存儲且有序的。（）10.堆排序是一種不穩(wěn)定的排序算法。（）簡答題（每題5分，共4題）1.簡述順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。答案：順序存儲優(yōu)點是存儲密度大，可隨機(jī)訪問；缺點是插入、刪除操作效率低，需連續(xù)空間。鏈?zhǔn)酱鎯?yōu)點是插入、刪除操作靈活，無需連續(xù)空間；缺點是存儲密度小，不可隨機(jī)訪問。2.簡述棧在表達(dá)式求值中的應(yīng)用。答案：利用兩個棧，一個存操作數(shù)，一個存運算符。掃描表達(dá)式，操作數(shù)入操作數(shù)棧，運算符按優(yōu)先級處理：優(yōu)先級低的運算符等待，高的入運算符棧。遇到括號先處理括號內(nèi)。最后按運算符棧依次計算操作數(shù)棧元素。3.簡述二叉樹的性質(zhì)。答案：性質(zhì)有：第i層最多有2^(i-1)個結(jié)點；深度為k的二叉樹最多有2^k-1個結(jié)點；對任何二叉樹，葉子結(jié)點數(shù)比度為2的結(jié)點數(shù)多1；具有n個結(jié)點的完全二叉樹深度為?log?n?+1。4.簡述選擇排序的基本思想。答案：在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。討論題（每題5分，共4題）1.討論不同排序算法在不同數(shù)據(jù)規(guī)模和數(shù)據(jù)特點下的適用性。答案：小規(guī)模數(shù)據(jù)，冒泡、選擇、插入排序簡單易實現(xiàn)。數(shù)據(jù)基本有序時，插入排序效率高。大規(guī)模數(shù)據(jù)，快速、歸并、堆排序較好。快速排序平均性能佳，但最壞情況差；歸并排序穩(wěn)定；堆排序空間需求小。2.討論圖的遍歷算法（深度優(yōu)先和廣度優(yōu)先）在實際應(yīng)用中的場景。答案：深度優(yōu)先遍歷適合搜索解空間、檢測連通性等，如迷宮尋路、判斷圖是否連通。廣度優(yōu)先遍歷適用于求最短路徑問題，如社交網(wǎng)絡(luò)中找兩人間最短關(guān)系路徑。3.討論哈希表中處理沖突方法對性能的影響。答案：開放定址法實現(xiàn)簡單，但易發(fā)生聚集現(xiàn)象影響性能；鏈地址法解決沖突簡單，適合數(shù)據(jù)量大情況，不易聚集，性能較穩(wěn)定；再哈希法增加計算成本但減少沖突；建立公共溢