算法基礎(chǔ)試題及答案1.在一個(gè)包含n個(gè)元素的數(shù)組中查找特定元素，若數(shù)組已排序，最有效的查找算法是（）。A.順序查找B.二分查找C.哈希查找D.隨機(jī)查找(答案：B)2.以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度為O(n^2)（）。A.快速排序B.歸并排序C.堆排序D.計(jì)數(shù)排序(答案：A)3.給定一個(gè)有向無(wú)環(huán)圖(DAG)，要找出其中最長(zhǎng)的路徑，適合使用的算法是（）。A.深度優(yōu)先搜索(DFS)B.廣度優(yōu)先搜索(BFS)C.動(dòng)態(tài)規(guī)劃D.拓?fù)渑判蚪Y(jié)合動(dòng)態(tài)規(guī)劃(答案：D)4.在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，使用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先搜索(DFS)的時(shí)間復(fù)雜度是（）。A.O(n)B.O(e)C.O(n+e)

D.O(n*e)(答案：C)5.以下哪種數(shù)據(jù)結(jié)構(gòu)最適合實(shí)現(xiàn)棧的操作（）。A.數(shù)組B.鏈表C.隊(duì)列D.哈希表(答案：A或B，兩者均可實(shí)現(xiàn)棧)6.給定一個(gè)字符串"algorithm"，其逆序字符串是（）。A.mhtirogla

B.htirogla

C.mhtirogl

D.htirogl(答案：A)7.在一個(gè)二叉搜索樹(shù)中，插入一個(gè)新節(jié)點(diǎn)的平均時(shí)間復(fù)雜度是（）。A.O(1)B.O(logn)

C.O(n)D.O(nlogn)(答案：B)8.以下哪種算法用于解決0-1背包問(wèn)題最為有效（）。A.貪心算法B.動(dòng)態(tài)規(guī)劃C.分治算法D.回溯算法(答案：B)9.給定一個(gè)數(shù)組[1,3,5,7,9]，使用二分查找查找元素5，第一次比較的中間元素是（）。A.1B.3C.5D.7(答案：C，假設(shè)數(shù)組索引從0開(kāi)始，中間索引為(0+4)/2=2)10.在一個(gè)具有n個(gè)頂點(diǎn)的完全圖中，邊的數(shù)量是（）。A.nB.n(n-1)

C.n(n-1)/2

D.2n(答案：C)11.以下哪種算法用于檢測(cè)圖中的環(huán)最為有效（）。A.DFS

B.BFSC.Dijkstra算法D.Prim算法(答案：A)12.給定一個(gè)鏈表1->2->3->4->5，反轉(zhuǎn)該鏈表后，頭節(jié)點(diǎn)是（）。A.1

B.2

C.4

D.5(答案：D)13.在一個(gè)哈希表中，處理沖突的方法不包括（）。A.開(kāi)放定址法B.鏈地址法C.排序法D.再哈希法(答案：C)14.以下哪種排序算法是穩(wěn)定的（）。A.快速排序B.冒泡排序C.選擇排序D.堆排序(答案：B)15.給定一個(gè)二叉樹(shù)，其前序遍歷序列為ABDC，中序遍歷序列為BDAC，則其后序遍歷序列是（）。A.DBCA

B.BDCA

C.BACD

D.DCBA(答案：B)16.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（）倍。A.1

B.2

C.3D.4(答案：B)17.以下哪種算法用于求解最短路徑問(wèn)題最為有效（）。A.DFSB.BFS（無(wú)權(quán)圖）C.Dijkstra算法（有權(quán)圖）D.Floyd算法(答案：C，針對(duì)有權(quán)圖；B針對(duì)無(wú)權(quán)圖，但題目未限定，C更通用)18.給定一個(gè)數(shù)組[10,20,30,40,50]，若使用快速排序，且選擇第一個(gè)元素作為基準(zhǔn)，第一次劃分后，基準(zhǔn)元素的正確位置是（）。A.0B.1C.2D.4(答案：A，因?yàn)樗性囟即笥诨鶞?zhǔn)，所以基準(zhǔn)仍在原位)19.在一個(gè)具有n個(gè)元素的堆中，插入一個(gè)新元素的時(shí)間復(fù)雜度是（）。A.O(1)B.O(logn)

C.O(n)D.O(nlogn)(答案：B)20.以下哪種數(shù)據(jù)結(jié)構(gòu)最適合實(shí)現(xiàn)隊(duì)列的操作（）。A.數(shù)組B.鏈表C.棧D.哈希表(答案：B，數(shù)組也可實(shí)現(xiàn)但鏈表更靈活)21.給定一個(gè)字符串"abcde"，其所有子串的數(shù)量是（）。A.5B.10

C.15

D.20(答案：C，n*(n+1)/2=5*6/2=15)22.在一個(gè)二叉樹(shù)中，若葉子節(jié)點(diǎn)的數(shù)量為n0，度為1的節(jié)點(diǎn)數(shù)量為n1，度為2的節(jié)點(diǎn)數(shù)量為n2，則有（）。A.n0=n1+1B.n0=n2+1C.n1=n2+1D.n0=n1+n2(答案：B)23.以下哪種算法用于解決圖的最小生成樹(shù)問(wèn)題（）。A.DFS

B.BFSC.Prim算法D.Dijkstra算法(答案：C)24.給定一個(gè)數(shù)組[5,3,8,4,2]，使用冒泡排序進(jìn)行第一輪排序后，數(shù)組變?yōu)椋ǎ.[3,5,4,2,8]

B.[3,5,8,4,2]

C.[3,4,2,5,8]

D.[5,3,4,2,8](答案：A)25.在一個(gè)哈希表中，裝載因子定義為（）。A.表中元素?cái)?shù)量與表大小的比值B.表大小與元素?cái)?shù)量的比值C.表中沖突的數(shù)量D.表中空槽的數(shù)量(答案：A)26.以下哪種算法用于字符串匹配最為有效（）。A.暴力匹配B.KMP算法C.Boyer-Moore算法D.深度優(yōu)先搜索(答案：B或C，兩者均有效，KMP更基礎(chǔ))27.給定一個(gè)二叉搜索樹(shù)，刪除一個(gè)葉子節(jié)點(diǎn)后，該樹(shù)（）。A.不再是二叉搜索樹(shù)B.仍然是二叉搜索樹(shù)C.可能變成鏈表D.無(wú)法確定(答案：B)28.在一個(gè)具有n個(gè)頂點(diǎn)的圖中，若每個(gè)頂點(diǎn)的度數(shù)都相同，則該圖是（）。A.完全圖B.正則圖C.樹(shù)D.環(huán)(答案：B)29.以下哪種排序算法需要額外的存儲(chǔ)空間（）。A.冒泡排序B.選擇排序C.歸并排序D.堆排序(答案：C)30.給定一個(gè)鏈表，判斷其是否有環(huán)，最適合使用的算法是（）。A.DFS

B.BFSC.快慢指針D.遞歸(答案：C)31.在一個(gè)二叉樹(shù)中，若已知前序遍歷和中序遍歷，能否唯一確定后序遍歷（）。A.能B.不能C.取決于樹(shù)的結(jié)構(gòu)D.無(wú)法判斷(答案：A)32.以下哪種算法用于解決旅行商問(wèn)題（TSP）最為有效（）。A.貪心算法B.動(dòng)態(tài)規(guī)劃C.回溯算法D.近似算法(答案：D，精確解法復(fù)雜度高，近似算法更實(shí)用)33.給定一個(gè)數(shù)組[1,2,3,4,5]，使用選擇排序進(jìn)行第一輪排序后，數(shù)組變?yōu)椋ǎ?。A.[1,2,3,4,5]

B.[1,3,2,4,5]

C.[1,2,4,3,5]

D.[1,2,3,5,4](答案：A，第一輪只是找到最小元素并放在首位，此處已在首位)（若修改為[5,4,3,2,1]，則答案為[1,4,3,2,5]的類(lèi)似形式，但按原題選A）34.在一個(gè)圖中，若從頂點(diǎn)v出發(fā)，存在一條路徑到達(dá)頂點(diǎn)u，則稱(chēng)v和u是（）。A.相鄰的B.連通的C.獨(dú)立的D.隔離的(答案：B)35.以下哪種數(shù)據(jù)結(jié)構(gòu)最適合實(shí)現(xiàn)優(yōu)先隊(duì)列（）。A.數(shù)組B.鏈表C.堆D.棧(答案：C)36.給定一個(gè)字符串"hello"，其所有可能排列的數(shù)量是（）。A.5B.10C.60D.120(答案：D，5!=120)37.在一個(gè)二叉搜索樹(shù)中，查找最小元素的時(shí)間復(fù)雜度是（）。A.O(1)B.O(logn)

C.O(n)D.O(nlogn)(答案：B，最壞情況下為O(n)，但平均為O(logn))（嚴(yán)格來(lái)說(shuō)最壞O(n)，但通?？紤]平均情況選B）38.以下哪種算法用于解決圖中的單源最短路徑問(wèn)題（）。A.Floyd算法B.Bellman-Ford算法C.Prim算法D.Kruskal算法(答案：B)39.給定一個(gè)數(shù)組[7,6,5,4,3,2,1]，使用插入排序進(jìn)行排序，需要多少次插入操作才能將數(shù)組完全排序（）。A.6B.7C.12D.21(答案：A，每次插入一個(gè)元素到已排序部分，共n-1次)40.在一個(gè)哈希表中，若發(fā)生沖突，且使用鏈地址法處理，則查找一個(gè)元素的時(shí)間復(fù)雜度是（）。A.O(1)B.O(logn)

C.O(n)D.取決于沖突鏈的長(zhǎng)度(答案：D)41.以下哪種算法用于計(jì)算圖的連通分量（）。A.DFS

B.BFSC.Dijkstra算法D.拓?fù)渑判?答案：A或B)42.給定一個(gè)二叉樹(shù)，其深度為d，則該樹(shù)的最少節(jié)點(diǎn)數(shù)量是（）。A.dB.d+1

C.2^dD.2^d-1(答案：A，僅根節(jié)點(diǎn)到某一葉子路徑時(shí))（若考慮滿二叉樹(shù)則選D，但題目問(wèn)最少）43.在一個(gè)排序算法中，若每次比較都能將搜索范圍減半，則該算法是（）。A.順序查找B.二分查找C.插值查找D.斐波那契查找(答案：B)44.以下哪種數(shù)據(jù)結(jié)構(gòu)最適合實(shí)現(xiàn)圖的鄰接表表示（）。A.數(shù)組B.鏈表C.棧D.隊(duì)列(答案：B，數(shù)組也可但鏈表更靈活)45.給定一個(gè)字符串"abc"，其所有非空子串的數(shù)量是（）。A.3

B.6

C.9

D.12(答案：B，3+2+1=6)46.在一個(gè)二叉搜索樹(shù)中，刪除一個(gè)度為2的節(jié)點(diǎn)后，通常需要（）。A.找到其前驅(qū)或后繼節(jié)點(diǎn)替換B.直接刪除C.將樹(shù)轉(zhuǎn)為鏈表D.無(wú)法刪除(答案：A)47.以下哪種算法用于解決圖中的所有頂點(diǎn)對(duì)最短路徑問(wèn)題（）。A.Dijkstra算法B.Bellman-Ford算法C.Floyd算法D.Prim算法(答案：C)48.給定一個(gè)數(shù)組[2,4,6,8,10]，若使用線性查找查找元素8，需要比較多少次（）