算法面試筆試題目及答案

一、單項(xiàng)選擇題（每題2分，共10題）1.以下哪種排序算法的平均時(shí)間復(fù)雜度為O(nlogn)？（）A.冒泡排序B.插入排序C.快速排序D.選擇排序答案：C2.一個(gè)棧的入棧序列為1,2,3,4，出棧序列不可能是（）A.4,3,2,1B.3,4,2,1C.1,4,3,2D.1,2,3,4答案：C3.二叉樹(shù)的前序遍歷順序是（）A.根節(jié)點(diǎn)、左子樹(shù)、右子樹(shù)B.左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù)C.左子樹(shù)、右子樹(shù)、根節(jié)點(diǎn)D.右子樹(shù)、左子樹(shù)、根節(jié)點(diǎn)答案：A4.下面哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性數(shù)據(jù)結(jié)構(gòu)？（）A.隊(duì)列B.棧C.二叉樹(shù)D.鏈表答案：C5.在一個(gè)長(zhǎng)度為n的數(shù)組中查找一個(gè)元素，平均時(shí)間復(fù)雜度最低的算法是（）A.順序查找B.二分查找（數(shù)組有序）C.哈希查找D.二叉查找樹(shù)查找答案：C6.遞歸算法的缺點(diǎn)是（）A.代碼簡(jiǎn)潔B.效率可能較低C.容易理解D.不需要額外空間答案：B7.對(duì)于一個(gè)有向圖，其邊的數(shù)量最多為（）A.n(n-1)/2B.n(n-1)C.n^2D.n答案：B8.動(dòng)態(tài)規(guī)劃算法的基本要素不包括（）A.最優(yōu)子結(jié)構(gòu)B.重疊子問(wèn)題C.貪心選擇性質(zhì)D.子問(wèn)題的遞歸關(guān)系答案：C9.以下哪種算法可以用來(lái)解決圖的最短路徑問(wèn)題？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.普里姆算法D.迪杰斯特拉算法答案：D10.鏈表中插入一個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度是（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)答案：A（在表頭插入）或者B（在中間或表尾插入需要先查找位置），這里假設(shè)是在表頭插入所以答案為A。二、多項(xiàng)選擇題（每題2分，共10題）1.以下哪些排序算法是穩(wěn)定的排序算法？（）A.冒泡排序B.插入排序C.歸并排序D.快速排序答案：ABC2.二叉搜索樹(shù)的特點(diǎn)包括（）A.左子樹(shù)的所有節(jié)點(diǎn)值小于根節(jié)點(diǎn)值B.右子樹(shù)的所有節(jié)點(diǎn)值大于根節(jié)點(diǎn)值C.左右子樹(shù)都是二叉搜索樹(shù)D.節(jié)點(diǎn)值沒(méi)有重復(fù)答案：ABC3.以下屬于圖的遍歷算法的有（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.弗洛伊德算法答案：AB4.數(shù)據(jù)結(jié)構(gòu)中線性表的存儲(chǔ)結(jié)構(gòu)有（）A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.索引存儲(chǔ)D.散列存儲(chǔ)答案：AB5.下列關(guān)于算法時(shí)間復(fù)雜度的說(shuō)法正確的是（）A.O(1)表示算法的時(shí)間復(fù)雜度是常數(shù)級(jí)B.O(n)表示算法的時(shí)間復(fù)雜度與輸入規(guī)模n成線性關(guān)系C.O(nlogn)比O(n^2)的時(shí)間復(fù)雜度低D.時(shí)間復(fù)雜度只考慮算法執(zhí)行的基本操作次數(shù)答案：ABCD6.棧的應(yīng)用場(chǎng)景包括（）A.函數(shù)調(diào)用B.表達(dá)式求值C.深度優(yōu)先搜索輔助結(jié)構(gòu)D.二叉樹(shù)的層次遍歷答案：ABC7.以下關(guān)于動(dòng)態(tài)規(guī)劃和貪心算法的區(qū)別，正確的有（）A.動(dòng)態(tài)規(guī)劃有最優(yōu)子結(jié)構(gòu)性質(zhì)，貪心算法不一定有B.貪心算法每次做出局部最優(yōu)選擇，動(dòng)態(tài)規(guī)劃不一定C.動(dòng)態(tài)規(guī)劃通常通過(guò)自底向上的方式求解，貪心算法是自頂向下D.動(dòng)態(tài)規(guī)劃考慮所有子問(wèn)題的解，貪心算法只考慮當(dāng)前最優(yōu)答案：BD8.以下關(guān)于哈希表的說(shuō)法正確的是（）A.哈希表通過(guò)哈希函數(shù)將關(guān)鍵字映射到存儲(chǔ)位置B.好的哈希函數(shù)可以避免沖突C.解決哈希沖突的方法有開(kāi)放定址法和鏈地址法D.哈希表的查找效率通常為O(1)答案：ACD9.以下關(guān)于隊(duì)列的說(shuō)法正確的是（）A.隊(duì)列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)B.隊(duì)列可以用數(shù)組或鏈表實(shí)現(xiàn)C.循環(huán)隊(duì)列是為了避免假溢出D.雙端隊(duì)列兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作答案：ABCD10.以下哪些算法可以用來(lái)對(duì)數(shù)組進(jìn)行排序？（）A.堆排序B.希爾排序C.計(jì)數(shù)排序D.基數(shù)排序答案：ABCD三、判斷題（每題2分，共10題）1.二叉樹(shù)的高度一定比其節(jié)點(diǎn)數(shù)小。（）答案：正確2.所有的遞歸算法都可以用非遞歸算法實(shí)現(xiàn)。（）答案：正確3.有向圖中邊是有方向的，無(wú)向圖中邊沒(méi)有方向。（）答案：正確4.哈希表中不可能存在兩個(gè)相同的關(guān)鍵字。（）答案：錯(cuò)誤5.快速排序是一種不穩(wěn)定的排序算法。（）答案：正確6.棧和隊(duì)列都是操作受限的線性表。（）答案：正確7.動(dòng)態(tài)規(guī)劃算法的子問(wèn)題一定是相互獨(dú)立的。（）答案：錯(cuò)誤8.對(duì)于一個(gè)連通圖，其最小生成樹(shù)是唯一的。（）答案：錯(cuò)誤9.二叉搜索樹(shù)的中序遍歷結(jié)果是一個(gè)有序序列。（）答案：正確10.所有的排序算法在最壞情況下的時(shí)間復(fù)雜度都為O(n^2)。（）答案：錯(cuò)誤四、簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述快速排序的基本思想。答案：快速排序是一種分治算法。首先選擇一個(gè)基準(zhǔn)元素，將數(shù)組分為兩部分，左邊部分的元素都小于等于基準(zhǔn)元素，右邊部分的元素都大于基準(zhǔn)元素。然后對(duì)左右兩部分分別遞歸進(jìn)行快速排序，直到整個(gè)數(shù)組有序。2.什么是二叉樹(shù)的后序遍歷？答案：二叉樹(shù)的后序遍歷順序是先遍歷左子樹(shù)，再遍歷右子樹(shù)，最后遍歷根節(jié)點(diǎn)。3.簡(jiǎn)述哈希表解決沖突的一種方法。答案：鏈地址法。把所有哈希地址相同的元素放在同一個(gè)單鏈表中，這個(gè)單鏈表稱(chēng)為同義詞鏈表。哈希表中每個(gè)位置存放的是指向同義詞鏈表的指針。4.說(shuō)明動(dòng)態(tài)規(guī)劃算法的主要步驟。答案：首先分析問(wèn)題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題。然后定義狀態(tài)，寫(xiě)出狀態(tài)轉(zhuǎn)移方程。接著確定邊界條件，最后按照狀態(tài)轉(zhuǎn)移方程自底向上計(jì)算出最優(yōu)解。五、討論題（每題5分，共4題）1.比較深度優(yōu)先搜索和廣度優(yōu)先搜索的優(yōu)缺點(diǎn)。答案：深度優(yōu)先搜索優(yōu)點(diǎn)是占用空間少，能較快找到一條從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑。缺點(diǎn)是可能陷入無(wú)限分支，不一定能找到最優(yōu)解。廣度優(yōu)先搜索優(yōu)點(diǎn)是能找到最短路徑，缺點(diǎn)是占用空間大，因?yàn)橐鎯?chǔ)多層節(jié)點(diǎn)。2.討論在什么情況下選擇插入排序而不是快速排序。答案：當(dāng)數(shù)據(jù)量較小且基本有序時(shí)，插入排序效率較高。因?yàn)椴迦肱判蛟谶@種情況下時(shí)間復(fù)雜度接近O(n)，而快速排序在數(shù)據(jù)基本有序時(shí)性能會(huì)下降，平均時(shí)間復(fù)雜度為O(nlogn)。3.如何判斷一個(gè)算法的好壞？答案：可以從時(shí)間復(fù)雜度、空間復(fù)雜度、算法的正確性、算法的穩(wěn)定