2018年csp考試題目及答案

單項選擇題（每題2分，共10題）1.以下哪種數(shù)據(jù)結(jié)構(gòu)常用于廣度優(yōu)先搜索？A.棧B.隊列C.樹D.圖答案：B2.對于一個有n個頂點的無向連通圖，其最少邊數(shù)是？A.n-1B.nC.n+1D.2n答案：A3.快速排序平均時間復(fù)雜度是？A.O(n)B.O(n^2)C.O(nlogn)D.O(logn)答案：C4.以下哪個不是常見的排序算法？A.插入排序B.拓?fù)渑判駽.歸并排序D.冒泡排序答案：B5.若一棵完全二叉樹有10個節(jié)點，其深度是？A.3B.4C.5D.6答案：B6.以下哪種語言不是面向?qū)ο缶幊陶Z言？A.C++B.JavaC.PythonD.C答案：D7.已知數(shù)組a[5]={1,2,3,4,5}，a[3]的值是？A.3B.4C.5D.6答案：B8.對長度為n的有序數(shù)組進(jìn)行二分查找，最壞情況下比較次數(shù)是？A.nB.n/2C.lognD.nlogn答案：C9.棧的操作特點是？A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.按順序進(jìn)出答案：B10.以下哪個符號是C++中的注釋符號？A.//B.//C.兩者都是D.兩者都不是答案：C多項選擇題（每題2分，共10題）1.以下屬于圖的遍歷方式的有（）A.深度優(yōu)先遍歷B.廣度優(yōu)先遍歷C.先序遍歷D.后序遍歷答案：AB2.以下哪些算法可以用于字符串匹配（）A.暴力匹配B.KMP算法C.快速排序D.歸并排序答案：AB3.關(guān)于哈希表，正確的說法有（）A.哈希表可以提高查找效率B.哈希表可能會出現(xiàn)沖突C.哈希函數(shù)設(shè)計很重要D.哈希表只能存儲整數(shù)答案：ABC4.以下哪些是動態(tài)規(guī)劃的特點（）A.把問題分解為子問題B.避免重復(fù)計算C.自底向上計算D.空間復(fù)雜度一定低答案：ABC5.以下屬于數(shù)據(jù)結(jié)構(gòu)的有（）A.鏈表B.數(shù)組C.棧D.隊列答案：ABCD6.以下哪些排序算法是穩(wěn)定的（）A.冒泡排序B.插入排序C.歸并排序D.快速排序答案：ABC7.樹的遍歷方式包括（）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：ABCD8.以下哪些是面向?qū)ο缶幊痰奶匦裕ǎ〢.封裝B.繼承C.多態(tài)D.重載答案：ABC9.以下哪些算法的時間復(fù)雜度是O(n^2)（）A.冒泡排序B.選擇排序C.插入排序D.歸并排序答案：ABC10.關(guān)于遞歸算法，正確的是（）A.遞歸算法一定有終止條件B.遞歸算法效率一定高C.遞歸算法容易理解D.遞歸算法空間復(fù)雜度可能高答案：ACD判斷題（每題2分，共10題）1.線性表的順序存儲結(jié)構(gòu)插入和刪除操作效率高。（）答案：錯2.二叉樹的前序遍歷和后序遍歷結(jié)果順序相反。（）答案：錯3.圖的鄰接矩陣表示法適合稀疏圖。（）答案：錯4.堆排序是穩(wěn)定排序算法。（）答案：錯5.隊列的操作特點是先進(jìn)后出。（）答案：錯6.動態(tài)規(guī)劃算法一定比貪心算法好。（）答案：錯7.哈希表查找效率一定是O(1)。（）答案：錯8.遞歸算法一定比非遞歸算法占用空間大。（）答案：錯9.無向圖一定存在生成樹。（）答案：錯10.快速排序在最壞情況下時間復(fù)雜度是O(n^2)。（）答案：對簡答題（每題5分，共4題）1.簡述棧和隊列的區(qū)別。答案：棧是先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，操作在棧頂進(jìn)行；隊列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)從隊尾入隊，隊頭出隊。2.簡述冒泡排序的基本思想。答案：比較相鄰元素，若順序錯誤就把它們交換過來。對整個數(shù)組重復(fù)此步驟，每一趟能將一個最大（或最小）元素“浮”到數(shù)組一端，直到整個數(shù)組有序。3.簡述深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的區(qū)別。答案：DFS沿著一條路徑盡可能深地探索，直到無法繼續(xù)再回溯；BFS則是按層次依次訪問節(jié)點，先訪問距離起始節(jié)點近的節(jié)點。4.簡述貪心算法的基本要素。答案：貪心選擇性質(zhì)，即每一步選擇都是當(dāng)前看來最優(yōu)的；最優(yōu)子結(jié)構(gòu)性質(zhì)，即問題的最優(yōu)解包含子問題的最優(yōu)解。討論題（每題5分，共4題）1.討論在實際應(yīng)用中如何選擇合適的排序算法。答案：數(shù)據(jù)量小且對穩(wěn)定性有要求可選冒泡、插入排序；數(shù)據(jù)量大，平均性能要求高可選快速、歸并排序；對空間要求高可選堆排序。還要考慮數(shù)據(jù)初始狀態(tài)等因素。2.討論哈希表沖突的解決方法及其優(yōu)缺點。答案：開放定址法簡單，但可能產(chǎn)生聚集現(xiàn)象；鏈地址法解決沖突方便，不易產(chǎn)生聚集，但增加了鏈表存儲開銷。具體選擇取決于實際應(yīng)用場景對空間和時間的要求。3.討論遞歸算法和迭代算法的優(yōu)缺點。答案：遞歸算法代碼簡潔易理解，但空間復(fù)雜度高，可能棧溢出；迭代算法空間效率高，執(zhí)行效率有時也高