acm考試題目及答案

單項選擇題（每題2分，共10題）1.以下哪種排序算法平均時間復(fù)雜度為O(nlogn)？A.冒泡排序B.選擇排序C.歸并排序D.插入排序2.在ACM競賽中，通常使用的輸入輸出方式不包括？A.scanf和printfB.cin和coutC.read和writeD.fscanf和fprintf3.深度優(yōu)先搜索算法一般使用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)？A.隊列B.棧C.優(yōu)先隊列D.哈希表4.以下哪個是計算最大公約數(shù)的函數(shù)名（C++STL中）？A.lcmB.gcdC.maxD.min5.若要在一個有序數(shù)組中查找特定元素，最佳的算法是？A.順序查找B.二分查找C.插值查找D.斐波那契查找6.對于一個有n個頂點的無向完全圖，邊的數(shù)量是？A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/27.以下哪種數(shù)據(jù)結(jié)構(gòu)適合實現(xiàn)棧？A.單鏈表B.循環(huán)鏈表C.雙向鏈表D.以上都可以8.計算a的b次方對m取模（a^b%m），高效的算法是？A.直接計算a^b再取模B.快速冪算法C.遞歸計算D.循環(huán)計算9.在動態(tài)規(guī)劃算法中，通常用來保存子問題解的數(shù)據(jù)結(jié)構(gòu)是？A.數(shù)組B.鏈表C.樹D.圖10.以下哪種算法常用于圖的最短路徑問題？A.普里姆算法B.克魯斯卡爾算法C.迪杰斯特拉算法D.拓?fù)渑判蛩惴ù鸢福?.C2.C3.B4.B5.B6.B7.D8.B9.A10.C多項選擇題（每題2分，共10題）1.以下屬于ACM常用編程語言的有？A.CB.C++C.JavaD.Python2.圖的遍歷算法有？A.廣度優(yōu)先搜索B.深度優(yōu)先搜索C.迪杰斯特拉算法D.弗洛伊德算法3.以下哪些數(shù)據(jù)結(jié)構(gòu)可以用于實現(xiàn)優(yōu)先隊列？A.數(shù)組B.堆C.鏈表D.哈希表4.排序算法中，穩(wěn)定的排序算法有？A.冒泡排序B.選擇排序C.插入排序D.歸并排序5.字符串處理中，常用的操作有？A.查找子串B.替換子串C.拼接字符串D.比較字符串6.動態(tài)規(guī)劃算法的要素包括？A.最優(yōu)子結(jié)構(gòu)B.重疊子問題C.貪心選擇性質(zhì)D.無后效性7.計算幾何中，常用的幾何圖形有？A.點B.直線C.多邊形D.圓8.以下哪些算法屬于貪心算法？A.哈夫曼編碼B.背包問題（0-1背包）C.活動安排問題D.旅行商問題9.圖的存儲結(jié)構(gòu)有？A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表10.以下關(guān)于時間復(fù)雜度和空間復(fù)雜度的說法正確的有？A.時間復(fù)雜度反映算法執(zhí)行時間與輸入規(guī)模的關(guān)系B.空間復(fù)雜度反映算法執(zhí)行所需空間與輸入規(guī)模的關(guān)系C.算法的時間復(fù)雜度和空間復(fù)雜度可以相互轉(zhuǎn)換D.通常優(yōu)先優(yōu)化算法的時間復(fù)雜度答案：1.ABCD2.AB3.AB4.ACD5.ABCD6.ABD7.ABCD8.AC9.ABCD10.AB判斷題（每題2分，共10題）1.快速排序在最壞情況下時間復(fù)雜度為O(n^2)。（）2.廣度優(yōu)先搜索使用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。（）3.哈希表查找元素的平均時間復(fù)雜度為O(1)。（）4.動態(tài)規(guī)劃算法一定比遞歸算法效率高。（）5.拓?fù)渑判蜻m用于有向無環(huán)圖。（）6.所有的排序算法平均時間復(fù)雜度都不能低于O(nlogn)。（）7.計算幾何中，判斷兩條線段是否相交可以通過叉積運算。（）8.貪心算法總能得到全局最優(yōu)解。（）9.圖的最短路徑問題一定有解。（）10.對于稀疏圖，使用鄰接矩陣存儲更節(jié)省空間。（）答案：1.√2.×3.√4.×5.√6.×7.√8.×9.×10.×簡答題（每題5分，共4題）1.簡述二分查找的基本思想二分查找針對有序數(shù)組，每次將查找區(qū)間縮小一半。取數(shù)組中間元素與目標(biāo)元素比較，若相等則找到；若目標(biāo)元素小于中間元素，在左半?yún)^(qū)間繼續(xù)查找；反之在右半?yún)^(qū)間查找，直到找到或區(qū)間為空。2.簡述深度優(yōu)先搜索和廣度優(yōu)先搜索的區(qū)別深度優(yōu)先搜索用棧實現(xiàn)，沿著一條路徑盡可能深地探索，直到無法繼續(xù)再回溯。廣度優(yōu)先搜索用隊列實現(xiàn)，按照層次依次訪問節(jié)點，先訪問的節(jié)點其鄰接節(jié)點也先被訪問。3.簡述貪心算法的基本步驟首先確定問題的最優(yōu)子結(jié)構(gòu)性質(zhì)；然后選擇一個貪心策略，每次做出當(dāng)前看來最優(yōu)的選擇；接著根據(jù)貪心策略逐步構(gòu)造最優(yōu)解，每一步選擇都基于前面的選擇且不改變已做出的選擇。4.簡述動態(tài)規(guī)劃算法的解題步驟分析問題，確定最優(yōu)子結(jié)構(gòu)；定義狀態(tài)，通常用數(shù)組表示；找出狀態(tài)轉(zhuǎn)移方程，描述不同狀態(tài)之間的關(guān)系；確定初始狀態(tài)；按狀態(tài)轉(zhuǎn)移方程逐步計算，得出最終結(jié)果。討論題（每題5分，共4題）1.討論在ACM競賽中，如何優(yōu)化算法的時間復(fù)雜度和空間復(fù)雜度優(yōu)化時間復(fù)雜度可選擇更高效算法，如用快速排序替代冒泡排序；減少不必要的計算，使用記憶化等。優(yōu)化空間復(fù)雜度可復(fù)用空間，如動態(tài)規(guī)劃滾動數(shù)組；合理選擇數(shù)據(jù)結(jié)構(gòu)，稀疏圖用鄰接表存儲等。2.討論在處理大規(guī)模數(shù)據(jù)時，ACM選手可能面臨的挑戰(zhàn)及應(yīng)對策略挑戰(zhàn)有內(nèi)存不足、計算時間過長。應(yīng)對策略包括優(yōu)化算法復(fù)雜度；采用分治思想，將數(shù)據(jù)分塊處理；合理使用數(shù)據(jù)結(jié)構(gòu)減少內(nèi)存占用；使用并行計算加速處理過程等。3.討論如何在ACM競賽中快速準(zhǔn)確地理解題意并設(shè)計算法快速讀題，標(biāo)記關(guān)鍵信息。理解問題本質(zhì)，聯(lián)想相關(guān)算法模型。通過簡單測試數(shù)據(jù)輔助理解。設(shè)計算法時先考慮暴力解法，再逐步優(yōu)化，同時注意邊界條件和特殊情況處理，多練習(xí)積累經(jīng)