數(shù)據(jù)結(jié)構(gòu)與算法（C語言版）試卷及答案

1、單項(xiàng)選擇題（每題2分，共10題）1.線性表采用順序存儲(chǔ)結(jié)構(gòu)，訪問第i個(gè)元素的時(shí)間復(fù)雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n2)2.棧的操作特性是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.以上都不對(duì)3.具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為（）A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/24.對(duì)數(shù)據(jù)元素序列{8,16,2,33,9,19}進(jìn)行冒泡排序，第一趟排序后結(jié)果為（）A.{2,8,16,9,19,33}B.{2,8,16,33,9,19}C.{8,2,16,9,19,33}D.{8,16,2,9,19,33}5.一棵完全二叉樹有100個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)數(shù)為（）A.50B.51C.49D.486.順序查找長(zhǎng)度為n的線性表，平均查找長(zhǎng)度為（）A.nB.(n+1)/2C.n/2D.2n7.隊(duì)列的插入操作在（）進(jìn)行。A.隊(duì)頭B.隊(duì)尾C.任意位置D.隊(duì)中8.哈夫曼樹中權(quán)值為10、12、16、21、30的結(jié)點(diǎn)，構(gòu)造的哈夫曼樹帶權(quán)路徑長(zhǎng)度為（）A.200B.202C.188D.1969.對(duì)n個(gè)元素進(jìn)行快速排序，平均時(shí)間復(fù)雜度為（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)10.鄰接表是圖的一種（）存儲(chǔ)結(jié)構(gòu)。A.順序B.鏈?zhǔn)紺.索引D.散列2、多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）A.棧B.隊(duì)列C.樹D.圖2.下列排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.選擇排序C.插入排序D.歸并排序3.圖的遍歷方法有（）A.廣度優(yōu)先搜索B.深度優(yōu)先搜索C.先序遍歷D.中序遍歷4.二叉樹的遍歷方式有（）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷5.以下哪些是棧的應(yīng)用場(chǎng)景（）A.表達(dá)式求值B.括號(hào)匹配C.深度優(yōu)先搜索輔助D.廣度優(yōu)先搜索輔助6.哈希表解決沖突的方法有（）A.開放定址法B.鏈地址法C.再哈希法D.建立公共溢出區(qū)7.以下關(guān)于堆的說法正確的是（）A.大頂堆每個(gè)結(jié)點(diǎn)的值大于或等于其子結(jié)點(diǎn)的值B.小頂堆每個(gè)結(jié)點(diǎn)的值小于或等于其子結(jié)點(diǎn)的值C.堆排序是一種基于堆結(jié)構(gòu)的排序算法D.堆可以用數(shù)組來存儲(chǔ)8.以下哪些是隊(duì)列的應(yīng)用場(chǎng)景（）A.打印隊(duì)列B.廣度優(yōu)先搜索輔助C.進(jìn)程調(diào)度D.表達(dá)式求值9.以下關(guān)于樹和二叉樹的說法正確的是（）A.樹中每個(gè)結(jié)點(diǎn)的度可以任意B.二叉樹每個(gè)結(jié)點(diǎn)的度最大為2C.二叉樹一定是有序樹D.樹可以轉(zhuǎn)化為二叉樹10.以下哪些屬于查找算法（）A.順序查找B.二分查找C.哈希查找D.快速查找3、判斷題（每題2分，共10題）1.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更節(jié)省存儲(chǔ)空間。（）2.棧和隊(duì)列都是特殊的線性表。（）3.二叉樹的中序遍歷結(jié)果一定是有序的。（）4.圖的深度優(yōu)先搜索遍歷結(jié)果是唯一的。（）5.快速排序在最壞情況下時(shí)間復(fù)雜度為O(n2)。（）6.堆排序是一種不穩(wěn)定的排序算法。（）7.哈希表查找效率與哈希函數(shù)、處理沖突方法及裝填因子有關(guān)。（）8.隊(duì)列的刪除操作在隊(duì)頭進(jìn)行。（）9.平衡二叉樹一定是完全二叉樹。（）10.順序查找適合于存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線性表。（）4、簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。答：棧操作特性是先進(jìn)后出，元素進(jìn)出都在棧頂；隊(duì)列操作特性是先進(jìn)先出，元素在隊(duì)尾插入，隊(duì)頭刪除。2.簡(jiǎn)述冒泡排序的基本思想。答：比較相鄰元素，若順序錯(cuò)誤就把它們交換過來。對(duì)整個(gè)數(shù)組重復(fù)此步驟，每一趟會(huì)將最大（或最小）元素“浮”到數(shù)組末尾，直到整個(gè)數(shù)組有序。3.簡(jiǎn)述圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)特點(diǎn)。答：用一個(gè)二維數(shù)組表示圖，數(shù)組元素值表示頂點(diǎn)間是否有邊及邊的權(quán)值。優(yōu)點(diǎn)是直觀，方便判斷頂點(diǎn)間是否有邊；缺點(diǎn)是存儲(chǔ)空間大，對(duì)于稀疏圖浪費(fèi)空間。4.簡(jiǎn)述二分查找的適用條件。答：適用于有序的順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)。每次將查找區(qū)間縮小一半，通過比較中間元素與目標(biāo)元素大小，確定下一步查找區(qū)間，直到找到或確定不存在。5、討論題（每題5分，共4題）1.討論在實(shí)際應(yīng)用中，如何選擇合適的排序算法。答：數(shù)據(jù)量小且接近有序，可選插入排序；數(shù)據(jù)量較大，平均性能選快速排序，穩(wěn)定性要求高選歸并排序，數(shù)據(jù)基本有序且要求穩(wěn)定可選冒泡排序，對(duì)空間要求高可選堆排序。2.討論哈希表在處理沖突時(shí)，開放定址法和鏈地址法的優(yōu)缺點(diǎn)。答：開放定址法優(yōu)點(diǎn)是無需額外指針空間，缺點(diǎn)是會(huì)產(chǎn)生聚集現(xiàn)象影響查找效率；鏈地址法優(yōu)點(diǎn)是沖突處理簡(jiǎn)單，無聚集現(xiàn)象，缺點(diǎn)是需要額外指針空間，鏈表長(zhǎng)時(shí)查找效率下降。3.討論二叉樹遍歷方式在不同應(yīng)用場(chǎng)景下的選擇。答：先序遍歷用于訪問根節(jié)點(diǎn)優(yōu)先的場(chǎng)景，如復(fù)制樹結(jié)構(gòu)；中序遍歷適合對(duì)有序數(shù)據(jù)處理，如二叉排序樹中序遍歷可得有序序列；后序遍歷用于刪除樹節(jié)點(diǎn)等需先處理子樹的情況；層次遍歷用于按層次訪問節(jié)點(diǎn)，如打印樹的層次結(jié)構(gòu)。4.討論圖的兩種遍歷方法（廣度優(yōu)先搜索和深度優(yōu)先搜索）的應(yīng)用場(chǎng)景。答：廣度優(yōu)先搜索適合求最短路徑、連通分量等問題；深度優(yōu)先搜索適用于拓?fù)渑判?、判斷圖是否有環(huán)等場(chǎng)景，通過遞歸深入探索圖的結(jié)構(gòu)。答案單項(xiàng)選擇題1.A2.B3.B4.A5.A6.B7.B8.B9.B10.B多項(xiàng)選擇題1.AB2.AC