《數(shù)據(jù)結(jié)構(gòu)與算法期末考試試卷》

《數(shù)據(jù)結(jié)構(gòu)與算法期末考試試卷》

單項(xiàng)選擇題（每題2分，共10題）1.線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，訪(fǎng)問(wèn)第i個(gè)元素的時(shí)間復(fù)雜度是（）A.O(1)B.O(n)C.O(logn)D.O(n^2)2.棧的特點(diǎn)是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.只進(jìn)不出3.隊(duì)列的操作原則是（）A.先進(jìn)先出B.先進(jìn)后出C.后進(jìn)后出D.隨意進(jìn)出4.具有n個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)為（）A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/25.對(duì)n個(gè)記錄進(jìn)行冒泡排序，在最好情況下的時(shí)間復(fù)雜度為（）A.O(1)B.O(n)C.O(n^2)D.O(nlogn)6.以下哪種數(shù)據(jù)結(jié)構(gòu)適合實(shí)現(xiàn)優(yōu)先隊(duì)列（）A.棧B.隊(duì)列C.堆D.鏈表7.二叉樹(shù)的第i層最多有（）個(gè)節(jié)點(diǎn)。A.2^iB.2^(i-1)C.2iD.2i-18.查找效率最高的二叉排序樹(shù)是（）A.平衡二叉樹(shù)B.完全二叉樹(shù)C.滿(mǎn)二叉樹(shù)D.普通二叉樹(shù)9.對(duì)數(shù)據(jù)元素序列（49，72，68，13，38，50，97，27）進(jìn)行排序，采用初始增量為4的希爾排序，第一趟排序后的結(jié)果是（）A.(49,72,68,13,38,50,97,27)B.(13,27,38,49,50,68,72,97)C.(49,13,68,38,50,97,27,72)D.(49,72,68,13,97,50,38,27)10.圖的廣度優(yōu)先搜索類(lèi)似于二叉樹(shù)的（）A.先序遍歷B.中序遍歷C.后序遍歷D.層序遍歷多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線(xiàn)性數(shù)據(jù)結(jié)構(gòu)的有（）A.數(shù)組B.棧C.隊(duì)列D.樹(shù)2.棧的應(yīng)用場(chǎng)景包括（）A.表達(dá)式求值B.括號(hào)匹配C.深度優(yōu)先搜索D.廣度優(yōu)先搜索3.以下哪些是二叉樹(shù)遍歷的方式（）A.先序遍歷B.中序遍歷C.后序遍歷D.層序遍歷4.排序算法中，時(shí)間復(fù)雜度為O(n^2)的有（）A.冒泡排序B.選擇排序C.插入排序D.快速排序5.圖的存儲(chǔ)結(jié)構(gòu)有（）A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表6.哈希表沖突處理的方法有（）A.開(kāi)放定址法B.鏈地址法C.再哈希法D.建立公共溢出區(qū)7.以下關(guān)于堆的說(shuō)法正確的是（）A.大頂堆的每個(gè)節(jié)點(diǎn)的值大于或等于其子節(jié)點(diǎn)的值B.小頂堆的每個(gè)節(jié)點(diǎn)的值小于或等于其子節(jié)點(diǎn)的值C.堆是完全二叉樹(shù)D.堆排序是一種穩(wěn)定排序8.屬于動(dòng)態(tài)存儲(chǔ)分配的數(shù)據(jù)結(jié)構(gòu)有（）A.鏈表B.數(shù)組C.棧D.隊(duì)列（鏈?zhǔn)酱鎯?chǔ)）9.對(duì)圖進(jìn)行深度優(yōu)先搜索時(shí)，可能產(chǎn)生的邊類(lèi)型有（）A.樹(shù)邊B.回邊C.前向邊D.交叉邊10.以下算法中，具有分治思想的有（）A.快速排序B.歸并排序C.二分查找D.冒泡排序判斷題（每題2分，共10題）1.順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除操作效率高。（）2.棧和隊(duì)列都是特殊的線(xiàn)性表。（）3.完全二叉樹(shù)一定是滿(mǎn)二叉樹(shù)。（）4.快速排序在最壞情況下的時(shí)間復(fù)雜度是O(n^2)。（）5.圖的最小生成樹(shù)是唯一的。（）6.哈希表的查找效率只與哈希函數(shù)有關(guān)，與處理沖突的方法無(wú)關(guān)。（）7.堆排序是一種不穩(wěn)定的排序算法。（）8.鏈表適合隨機(jī)訪(fǎng)問(wèn)。（）9.對(duì)一個(gè)有序數(shù)組進(jìn)行二分查找，其時(shí)間復(fù)雜度為O(logn)。（）10.拓?fù)渑判蜻m用于有向無(wú)環(huán)圖。（）簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述棧和隊(duì)列的主要區(qū)別。答：棧是先進(jìn)后出，只能在棧頂進(jìn)行插入和刪除操作；隊(duì)列是先進(jìn)先出，在隊(duì)尾插入，隊(duì)頭刪除。2.簡(jiǎn)述二叉排序樹(shù)的性質(zhì)。答：若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；若它的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；它的左、右子樹(shù)也分別為二叉排序樹(shù)。3.簡(jiǎn)述選擇排序的基本思想。答：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類(lèi)推，直到所有元素均排序完畢。4.簡(jiǎn)述圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的基本思路。答：深度優(yōu)先搜索：從起始頂點(diǎn)出發(fā)，沿著一條路徑盡可能深地探索下去，直到無(wú)法繼續(xù)，再回溯。廣度優(yōu)先搜索：從起始頂點(diǎn)開(kāi)始，依次訪(fǎng)問(wèn)其鄰接頂點(diǎn)，再對(duì)這些鄰接頂點(diǎn)的鄰接頂點(diǎn)進(jìn)行訪(fǎng)問(wèn)，按層次依次進(jìn)行。討論題（每題5分，共4題）1.討論在實(shí)際應(yīng)用中，如何根據(jù)需求選擇合適的排序算法。答：若數(shù)據(jù)量小且基本有序，可選插入排序；數(shù)據(jù)量小但無(wú)序，選擇排序可考慮；數(shù)據(jù)量大，快速排序平均性能好，但最壞情況差，歸并排序穩(wěn)定且性能較好；對(duì)穩(wěn)定性有要求，可考慮歸并排序等。2.分析哈希表在不同沖突處理方法下的優(yōu)缺點(diǎn)。答：開(kāi)放定址法優(yōu)點(diǎn)是地址連續(xù)，缺點(diǎn)是易產(chǎn)生聚集現(xiàn)象；鏈地址法優(yōu)點(diǎn)是處理沖突簡(jiǎn)單，不易聚集，缺點(diǎn)是指針增加存儲(chǔ)開(kāi)銷(xiāo)；再哈希法不易聚集但計(jì)算復(fù)雜；建立公共溢出區(qū)簡(jiǎn)單但查找效率可能受影響。3.討論二叉樹(shù)遍歷方式在不同場(chǎng)景下的應(yīng)用。答：先序遍歷用于復(fù)制二叉樹(shù)、求二叉樹(shù)高度等；中序遍歷可對(duì)二叉排序樹(shù)進(jìn)行有序輸出；后序遍歷用于釋放二叉樹(shù)空間等；層序遍歷可按層次處理節(jié)點(diǎn)，如按層打印二叉樹(shù)。4.探討圖的存儲(chǔ)結(jié)構(gòu)對(duì)圖算法效率的影響。答：鄰接矩陣適合稠密圖，空間開(kāi)銷(xiāo)大，判斷邊存在性快；鄰接表適合稀疏圖，空間開(kāi)銷(xiāo)小，但判斷邊存在性慢；十字鏈表和鄰接多重表適合復(fù)雜操作，不同存儲(chǔ)結(jié)構(gòu)對(duì)深度、廣度優(yōu)先搜索等算法效率有不同影響。答案單項(xiàng)選擇題1.A2.B3.A4.B5.B6.C7.B8.A9.C10.D多項(xiàng)選擇題1.ABC2.