編程算法筆試題及答案

單項(xiàng)選擇題（每題2分，共10題）1.以下哪種排序算法的平均時(shí)間復(fù)雜度為O(nlogn)？A.冒泡排序B.選擇排序C.快速排序D.插入排序2.若有一個(gè)鏈表，要?jiǎng)h除其第i個(gè)節(jié)點(diǎn)，需要遍歷鏈表幾次？A.1次B.i次C.i-1次D.2次3.下面哪個(gè)不是算法的特性？A.有窮性B.確定性C.輸入D.無(wú)限性4.遞歸算法的實(shí)現(xiàn)通常借助什么數(shù)據(jù)結(jié)構(gòu)？A.數(shù)組B.棧C.隊(duì)列D.哈希表5.一棵完全二叉樹(shù)有10個(gè)節(jié)點(diǎn)，其葉子節(jié)點(diǎn)個(gè)數(shù)為？A.4B.5C.6D.76.以下哪種算法適合處理大規(guī)模數(shù)據(jù)的排序？A.歸并排序B.插入排序C.冒泡排序D.選擇排序7.對(duì)有序數(shù)組進(jìn)行二分查找，時(shí)間復(fù)雜度是？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)8.深度優(yōu)先搜索算法常用的數(shù)據(jù)結(jié)構(gòu)是？A.隊(duì)列B.棧C.哈希表D.堆9.以下哪個(gè)是動(dòng)態(tài)規(guī)劃算法的核心思想？A.分治B.貪心C.最優(yōu)子結(jié)構(gòu)D.回溯10.字符串匹配算法中，效率較高的是？A.暴力匹配B.樸素匹配C.KMP算法D.簡(jiǎn)單匹配答案：1.C2.C3.D4.B5.B6.A7.B8.B9.C（10.C）多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有？A.數(shù)組B.鏈表C.棧D.樹(shù)2.排序算法中，哪些是穩(wěn)定的排序算法？A.冒泡排序B.快速排序C.歸并排序D.選擇排序3.以下哪些算法可用于查找？A.順序查找B.二分查找C.哈希查找D.深度優(yōu)先查找4.圖的遍歷算法有？A.廣度優(yōu)先遍歷B.深度優(yōu)先遍歷C.Dijkstra算法D.Floyd算法5.以下哪些是算法設(shè)計(jì)的基本方法？A.分治法B.動(dòng)態(tài)規(guī)劃法C.貪心算法D.回溯法6.數(shù)據(jù)結(jié)構(gòu)中，哪些是邏輯結(jié)構(gòu)？A.線性結(jié)構(gòu)B.樹(shù)形結(jié)構(gòu)C.存儲(chǔ)結(jié)構(gòu)D.圖形結(jié)構(gòu)7.以下哪些算法可用于最短路徑問(wèn)題？A.Dijkstra算法B.Floyd算法C.Prim算法D.Kruskal算法8.遞歸算法可能會(huì)用到的操作有？A.調(diào)用自身B.保存局部變量C.處理邊界條件D.循環(huán)9.以下哪些是動(dòng)態(tài)規(guī)劃適用的問(wèn)題特點(diǎn)？A.最優(yōu)子結(jié)構(gòu)B.重疊子問(wèn)題C.無(wú)后效性D.貪心選擇性質(zhì)10.哈希表的沖突解決方法有？A.開(kāi)放定址法B.鏈地址法C.再哈希法D.建立公共溢出區(qū)答案：1.ABC2.AC3.ABC4.AB5.ABCD6.ABD7.AB8.ABC9.ABC（10.ABCD）判斷題（每題2分，共10題）1.算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定是相互影響的。（）2.任何一個(gè)遞歸算法都可以轉(zhuǎn)換為非遞歸算法。（）3.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）4.快速排序在最壞情況下時(shí)間復(fù)雜度為O(n^2)。（）5.圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷結(jié)果一定相同。（）6.動(dòng)態(tài)規(guī)劃算法一定比貪心算法效率高。（）7.哈希表查找的平均時(shí)間復(fù)雜度為O(1)。（）8.棧是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。（）9.二叉樹(shù)的前序遍歷和中序遍歷可以唯一確定一棵二叉樹(shù)。（）10.算法的輸入可以為空。（）答案：1.×2.√3.×4.√5.×6.×7.√8.×9.√（10.×）簡(jiǎn)答題（總4題，每題5分）1.簡(jiǎn)述深度優(yōu)先搜索算法的基本步驟。從起始節(jié)點(diǎn)開(kāi)始，沿著一條路徑盡可能深地探索，直到無(wú)法繼續(xù)或達(dá)到目標(biāo)，若未找到目標(biāo)，則回溯到前一步，繼續(xù)探索其他路徑。2.什么是貪心算法？總是做出在當(dāng)前看來(lái)是最好的選擇，不從整體最優(yōu)上加以考慮，它所做出只是在某種意義上的局部最優(yōu)解。3.簡(jiǎn)述字符串匹配的KMP算法優(yōu)點(diǎn)。無(wú)需回溯已匹配的字符，通過(guò)利用之前匹配的部分信息計(jì)算下次匹配位置，提高匹配效率，時(shí)間復(fù)雜度為O(m+n)。4.簡(jiǎn)述歸并排序的基本原理。將數(shù)組分成兩個(gè)子數(shù)組，分別對(duì)兩個(gè)子數(shù)組進(jìn)行排序，然后將排序好的子數(shù)組合并成一個(gè)有序的數(shù)組。討論題（總4題，每題5分）1.比較深度優(yōu)先搜索和廣度優(yōu)先搜索的優(yōu)缺點(diǎn)。深度優(yōu)先搜索能快速深入探索，但可能陷入死胡同；廣度優(yōu)先搜索能保證找到最短路徑，但消耗空間大。2.動(dòng)態(tài)規(guī)劃與分治法的區(qū)別。分治法是分解問(wèn)題為子問(wèn)題，子問(wèn)題相互獨(dú)立，解決后合并；動(dòng)態(tài)規(guī)劃也分解為子問(wèn)題，但子問(wèn)題有重疊，通過(guò)保存子問(wèn)題解避免重復(fù)計(jì)算。3.在實(shí)際應(yīng)用中，如何選擇合適的排序算法？考慮數(shù)據(jù)規(guī)模、初始狀態(tài)、穩(wěn)定性要求等。規(guī)模小可選簡(jiǎn)單