問答題給定線性序集中n個元素和一個整數(shù)k，1≤k≤n，要求找出這n個元素中第k小的元素，請設(shè)計一個最壞時間復(fù)雜度為O（n）的算法，并對其時間復(fù)雜度進行分析說明。
您可能感興趣的試卷
你可能感興趣的試題
2.問答題請解釋什么是P問題，NP問題。
4.單項選擇題給定6個小區(qū)之間的交通圖。若小區(qū)i與小區(qū)j之間有路可通，則將頂點i與頂點j之間用邊連接，邊上的權(quán)值表示這條道路的長度。現(xiàn)在打算在這n個小區(qū)中選定一個小區(qū)建一所醫(yī)院。這家醫(yī)院應(yīng)建在小區(qū)（），才能使距離醫(yī)院最遠的小區(qū)到醫(yī)院的路程最短。
A.A
B.B
C.C
D.E
5.單項選擇題
一個凸N邊形，可以用N-3條互不相交的對角線將凸N邊形分成N-2個三角形，這稱為凸N邊形的一種三角剖分。例如N＝5時，共有以下5種三角剖分：
當N＝8時，總共有（）種三角剖分。
A.8
B.132
C.14
D.140
最新試題
回溯法采用的搜索策略是（）。
題型：單項選擇題
馬的遍歷問題能否有可行解，與（）有關(guān)。
題型：多項選擇題
在使用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同，即將一個問題分成大小相等的多個子問題的處理方法是行之有效的。
題型：判斷題
應(yīng)用分支限界法的三個關(guān)鍵問題包括（）。
題型：多項選擇題
在N皇后問題中，需要將棋盤當做一個二維數(shù)組來分析，對于該二維數(shù)組，以下說法正確的是（）。
題型：多項選擇題
Prim算法適合稀疏圖，其時間復(fù)雜度只與邊的數(shù)目有關(guān)。
題型：判斷題
已知f（1）=1，f（n）=f（n-1）+n，那么f（50）的作用是（）。
題型：單項選擇題
回溯法的主要用途包括求問題的所有解、求問題的最優(yōu)解和求問題的任一解。
題型：判斷題
在求解部分背包問題時采用的貪心策略是（）。
題型：單項選擇題
根據(jù)活結(jié)點表的組織方式不同，分支限界法包括（）等形式。
題型：多項選擇題