noi考試題及答案

一、單項(xiàng)選擇題（每題2分，共10題）1.以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)廣度優(yōu)先搜索？A.棧B.隊(duì)列C.堆答案：B2.對(duì)數(shù)組{3,1,4,1,5,9}進(jìn)行排序，哪種排序算法平均時(shí)間復(fù)雜度最低？A.冒泡排序B.選擇排序C.快速排序答案：C3.二叉樹的前序遍歷序列為ABDCE，中序遍歷序列為BDAEC，則后序遍歷序列是？A.DBECAB.DBEACC.ECDBA答案：A4.以下哪個(gè)不是算法的特性？A.有窮性B.確定性C.可移植性答案：C5.一個(gè)圖有10個(gè)頂點(diǎn)，要保證其連通，至少需要多少條邊？A.9B.10C.11答案：A6.若一棵完全二叉樹有699個(gè)節(jié)點(diǎn)，則葉子節(jié)點(diǎn)的個(gè)數(shù)是？A.349B.350C.351答案：B7.計(jì)算斐波那契數(shù)列第n項(xiàng)，哪種方法效率最高？A.遞歸B.循環(huán)C.記憶化遞歸答案：C8.以下哪種排序算法是穩(wěn)定的？A.歸并排序B.希爾排序C.堆排序答案：A9.表達(dá)式(3+4)2-1的后綴表達(dá)式是？A.34+21-B.342+1-C.34+12-答案：A10.哈希表中解決沖突的方法不包括？A.開放定址法B.鏈地址法C.二分查找法答案：C二、多項(xiàng)選擇題（每題2分，共10題）1.以下屬于動(dòng)態(tài)規(guī)劃算法特點(diǎn)的有（）A.分解子問題B.避免重復(fù)計(jì)算C.自底向上求解答案：ABC2.以下哪些數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)優(yōu)先隊(duì)列（）A.堆B.鏈表C.數(shù)組答案：AC3.圖的遍歷方法有（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判虼鸢福篈B4.以下排序算法中，時(shí)間復(fù)雜度為O(n^2)的有（）A.冒泡排序B.選擇排序C.插入排序答案：ABC5.下列屬于貪心算法適用的問題有（）A.活動(dòng)安排問題B.背包問題C.哈夫曼編碼答案：AC6.樹的存儲(chǔ)結(jié)構(gòu)有（）A.雙親表示法B.孩子表示法C.孩子兄弟表示法答案：ABC7.常見的查找算法有（）A.順序查找B.二分查找C.哈希查找答案：ABC8.以下關(guān)于遞歸算法的說法正確的有（）A.遞歸算法一定有遞歸出口B.遞歸算法效率一定低C.遞歸算法通常比非遞歸算法占用更多?？臻g答案：AC9.以下哪些是數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)的類型（）A.線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.圖形結(jié)構(gòu)答案：ABC10.以下關(guān)于算法復(fù)雜度的說法正確的是（）A.時(shí)間復(fù)雜度衡量算法執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)的變化B.空間復(fù)雜度衡量算法執(zhí)行過程中所需額外空間隨輸入規(guī)模增長(zhǎng)的變化C.復(fù)雜度分析有助于評(píng)估算法優(yōu)劣答案：ABC三、判斷題（每題2分，共10題）1.線性表的順序存儲(chǔ)結(jié)構(gòu)插入和刪除操作效率高。（×）2.快速排序在最壞情況下時(shí)間復(fù)雜度是O(n^2)。（√）3.完全二叉樹一定是滿二叉樹。（×）4.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索都可以用來判斷圖是否連通。（√）5.貪心算法一定能得到全局最優(yōu)解。（×）6.哈希表查找的平均時(shí)間復(fù)雜度是O(1)。（√）7.歸并排序是一種不穩(wěn)定的排序算法。（×）8.二叉排序樹中序遍歷結(jié)果是有序的。（√）9.隊(duì)列是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)。（×）10.動(dòng)態(tài)規(guī)劃算法的關(guān)鍵在于找出狀態(tài)轉(zhuǎn)移方程。（√）四、簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。答案：棧是先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，元素進(jìn)出遵循“后進(jìn)先出”原則；隊(duì)列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素進(jìn)出遵循“先進(jìn)先出”原則。2.簡(jiǎn)述Dijkstra算法的基本思想。答案：用于求圖中某一頂點(diǎn)到其他各頂點(diǎn)的最短路徑。以起始點(diǎn)為中心，不斷選擇距離起始點(diǎn)最近且未確定最短路徑的頂點(diǎn)，更新其鄰接頂點(diǎn)的距離，直到所有頂點(diǎn)最短路徑確定。3.簡(jiǎn)述平衡二叉樹的定義。答案：平衡二叉樹是一種二叉排序樹，它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。4.簡(jiǎn)述分治算法的步驟。答案：分治算法步驟為分解、求解、合并。將原問題分解為若干個(gè)規(guī)模較小的子問題，分別求解子問題，再將子問題的解合并得到原問題的解。五、討論題（每題5分，共4題）1.討論在實(shí)際應(yīng)用中如何選擇合適的排序算法。答案：若數(shù)據(jù)量小且對(duì)穩(wěn)定性有要求，可選冒泡排序、插入排序；數(shù)據(jù)量較大時(shí)，平均性能快的快速排序較優(yōu)；若要求穩(wěn)定且數(shù)據(jù)量較大，歸并排序合適；對(duì)空間要求高且數(shù)據(jù)量不大，選擇排序可考慮。2.討論哈希表中沖突解決方法的優(yōu)缺點(diǎn)。答案：開放定址法優(yōu)點(diǎn)是無需額外鏈表空間，缺點(diǎn)是容易產(chǎn)生聚集現(xiàn)象；鏈地址法優(yōu)點(diǎn)是沖突處理簡(jiǎn)單，不易聚集，缺點(diǎn)是需額外鏈表空間，遍歷鏈表有開銷。3.討論遞歸算法和迭代算法的優(yōu)缺點(diǎn)。答案：遞歸算法優(yōu)點(diǎn)是代碼簡(jiǎn)潔，符合問題自然遞歸結(jié)構(gòu)；缺點(diǎn)是占用棧空間大，可能棧溢出，效率低。迭代算法優(yōu)點(diǎn)是空