poj題目大全及答案

一、單項(xiàng)選擇題（每題2分，共10題）1.以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先隊(duì)列？A.數(shù)組B.鏈表C.堆D.棧2.二分查找適用于？A.無(wú)序數(shù)組B.有序數(shù)組C.鏈表D.哈希表3.深度優(yōu)先搜索通常用什么數(shù)據(jù)結(jié)構(gòu)輔助實(shí)現(xiàn)？A.隊(duì)列B.棧C.堆D.哈希表4.快速排序的平均時(shí)間復(fù)雜度是？A.O(n)B.O(n^2)C.O(nlogn)D.O(logn)5.以下哪個(gè)是圖的存儲(chǔ)結(jié)構(gòu)？A.鄰接矩陣B.二叉樹(shù)C.哈希表D.棧6.計(jì)算兩個(gè)數(shù)的最大公約數(shù)常用什么算法？A.歐幾里得算法B.迪杰斯特拉算法C.弗洛伊德算法D.克魯斯卡爾算法7.廣度優(yōu)先搜索通常用什么數(shù)據(jù)結(jié)構(gòu)輔助實(shí)現(xiàn)？A.棧B.隊(duì)列C.堆D.哈希表8.插入排序的時(shí)間復(fù)雜度是？A.O(n)B.O(n^2)C.O(nlogn)D.O(logn)9.以下哪種排序算法是穩(wěn)定的？A.快速排序B.歸并排序C.選擇排序D.堆排序10.拓?fù)渑判蜻m用于什么圖？A.有向無(wú)環(huán)圖B.有向有環(huán)圖C.無(wú)向圖D.完全圖二、多項(xiàng)選擇題（每題2分，共10題）1.以下屬于排序算法的有？A.冒泡排序B.計(jì)數(shù)排序C.桶排序D.基數(shù)排序2.圖的遍歷方式有？A.深度優(yōu)先遍歷B.廣度優(yōu)先遍歷C.前序遍歷D.中序遍歷3.數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)有？A.數(shù)組B.鏈表C.棧D.隊(duì)列4.以下哪些算法可用于圖的最短路徑問(wèn)題？A.迪杰斯特拉算法B.弗洛伊德算法C.貝爾曼-福特算法D.克魯斯卡爾算法5.以下哪些是哈希函數(shù)的設(shè)計(jì)方法？A.直接定址法B.除留余數(shù)法C.平方取中法D.折疊法6.以下屬于樹(shù)的遍歷方式的有？A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷7.動(dòng)態(tài)規(guī)劃算法的特點(diǎn)有？A.最優(yōu)子結(jié)構(gòu)性質(zhì)B.重疊子問(wèn)題C.貪心選擇性質(zhì)D.自底向上計(jì)算8.以下哪些數(shù)據(jù)結(jié)構(gòu)可用于實(shí)現(xiàn)符號(hào)表？A.哈希表B.二叉搜索樹(shù)C.平衡二叉樹(shù)D.紅黑樹(shù)9.貪心算法的適用條件有？A.最優(yōu)子結(jié)構(gòu)性質(zhì)B.貪心選擇性質(zhì)C.重疊子問(wèn)題D.無(wú)后效性10.以下屬于字符串匹配算法的有？A.暴力匹配算法B.KMP算法C.BM算法D.RK算法三、判斷題（每題2分，共10題）1.棧是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。（）2.哈希表查找的時(shí)間復(fù)雜度一定是O(1)。（）3.二叉樹(shù)一定是平衡的。（）4.迪杰斯特拉算法不能處理帶負(fù)權(quán)邊的圖。（）5.快速排序在最壞情況下時(shí)間復(fù)雜度為O(n^2)。（）6.廣度優(yōu)先搜索遍歷圖時(shí)需要使用棧。（）7.平衡二叉樹(shù)的左右子樹(shù)高度差的絕對(duì)值不超過(guò)1。（）8.堆排序是穩(wěn)定的排序算法。（）9.拓?fù)渑判虻慕Y(jié)果唯一。（）10.動(dòng)態(tài)規(guī)劃算法通常采用遞歸方式實(shí)現(xiàn)。（）四、簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。答案：棧是先進(jìn)后出，元素只能在棧頂進(jìn)行插入和刪除操作；隊(duì)列是先進(jìn)先出，元素在隊(duì)尾插入，隊(duì)頭刪除。2.簡(jiǎn)述哈希表的原理。答案：哈希表通過(guò)哈希函數(shù)將關(guān)鍵字映射到一個(gè)有限的地址空間中，以實(shí)現(xiàn)快速查找。當(dāng)發(fā)生沖突時(shí)，需要用開(kāi)放定址法、鏈地址法等方法解決。3.簡(jiǎn)述深度優(yōu)先搜索和廣度優(yōu)先搜索的區(qū)別。答案：深度優(yōu)先搜索沿著一條路徑盡可能深地探索，用棧輔助；廣度優(yōu)先搜索一層一層地遍歷，用隊(duì)列輔助，DFS更適合找路徑，BFS更適合找最短路徑。4.簡(jiǎn)述貪心算法的基本步驟。答案：先確定貪心策略，即根據(jù)問(wèn)題選擇一個(gè)最優(yōu)量度標(biāo)準(zhǔn)；然后按照貪心策略對(duì)輸入數(shù)據(jù)排序；最后按照貪心策略依次處理數(shù)據(jù)得出最優(yōu)解。五、討論題（每題5分，共4題）1.討論排序算法在不同場(chǎng)景下的選擇。答案：數(shù)據(jù)量小且要求穩(wěn)定選冒泡、插入排序；數(shù)據(jù)量一般且不要求穩(wěn)定選快速排序；數(shù)據(jù)量極大選基數(shù)排序等。對(duì)數(shù)據(jù)有序度敏感的，如基本有序選插入排序。2.討論圖的存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)。答案：鄰接矩陣直觀易實(shí)現(xiàn)，適合稠密圖，但空間復(fù)雜度高；鄰接表節(jié)省空間，適合稀疏圖，但查找邊效率低。3.討論動(dòng)態(tài)規(guī)劃和分治法的異同。答案：相同點(diǎn)是都將大問(wèn)題分解為子問(wèn)題。不同點(diǎn)在于動(dòng)態(tài)規(guī)劃子問(wèn)題有重疊，需記錄子問(wèn)題解，自底向上求解；分治法子問(wèn)題相互