單項選擇題在有n個無序無重復(fù)元素值的數(shù)組中查找第i小的數(shù)的算法描述如下：任意取一個元素r，用劃分操作確定其在數(shù)組中的位置，假設(shè)元素r為第k小的數(shù)。若i等于k，則返回該元素值；若i小于k，則在劃分的前半部分遞歸進(jìn)行劃分操作找第i小的數(shù)；否則在劃分的后半部分遞歸進(jìn)行劃分操作找第k-i小的數(shù)。該算法是一種基于（）策略的算法。

A.分治
B.動態(tài)規(guī)劃
C.貪心
D.回溯


你可能感興趣的試題

5.問答題閱讀下列說明和C代碼，將應(yīng)填入（n）處的字句寫在答題紙的對應(yīng)欄內(nèi)。 說明：設(shè)某一機(jī)器由n個部件組成，每一個部件都可以從m個不同的供應(yīng)商處購得。供應(yīng)商j供應(yīng)的部件i具有重量Wij和價格Cij。設(shè)計一個算法，求解總價格不超過上限cc的最小重量的機(jī)器組成。采用回溯法來求解該問題。首先定義解空間。解空間由長度為n的向量組成，其中每個分量取值來自集合{1，2，…，m}，將解空間用樹形結(jié)構(gòu)表示。接著從根節(jié)點開始，以深度優(yōu)先的方式搜索整個解空間。從根節(jié)點開始，根節(jié)點成為活節(jié)點，同時也成為當(dāng)前的擴(kuò)展節(jié)點。向縱深方向考慮第一個部件從第一個供應(yīng)商處購買，得到一個新節(jié)點。判斷當(dāng)前的機(jī)器價格（C11）是否超過上限（cc），重量（W11）是否比當(dāng)前已知的解（最小重量）大，若是，應(yīng)回溯至最近的一個活節(jié)點；若否，則該新節(jié)點成為活節(jié)點，同時也成為當(dāng)前的擴(kuò)展節(jié)點，根節(jié)點不再是擴(kuò)展節(jié)點。繼續(xù)向縱深方向考慮第二個部件從第一個供應(yīng)商處購買，得到一個新節(jié)點。同樣判斷當(dāng)前的機(jī)器價格（C11+C21）是否超過上限（cc），重量（W11+W21）是否比當(dāng)前已知的解（最小重量）大。若是，應(yīng)回溯至最近的一個活節(jié)點；若否，則該新節(jié)點成為活節(jié)點，同時也成為當(dāng)前的擴(kuò)展節(jié)點，原來的節(jié)點不再是擴(kuò)展節(jié)點。以這種方式遞歸地在解空間中搜索，直到找到所要求的解或者解空間中已無活節(jié)點為止。 C代碼：下面是該算法的C語言實現(xiàn)。 （1）變量說明n：機(jī)器的部件數(shù)。m：供應(yīng)商數(shù)。cc：價格上限。w［］［］：二維數(shù)組，w［i］［j］表示第j個供應(yīng)商供應(yīng)的第i個部件的重量。c［］［］：二維數(shù)組，c［i］［j］表示第j個供應(yīng)商供應(yīng)的第i個部件的價格。bestW：滿足價格上限約束條件的最小機(jī)器重量。bestC：最小重量機(jī)器的價格。bestX［］：最優(yōu)解，一維數(shù)組，bestX［i］表示第i個部件來自哪個供應(yīng)商。cw：搜索過程中機(jī)器的重量。cp：搜索過程中機(jī)器的價格。x［］：搜索過程中產(chǎn)生的解，x［i］表示第i個部件來自哪個供應(yīng)商。i：當(dāng)前考慮的部件，從0到n-1。j：循環(huán)變量 （2）函數(shù)backtrack

代碼如下：
7.單項選擇題分治算法設(shè)計技術(shù)（）

A.一般由三個步驟組成：問題劃分、遞歸求解、合并解
B.一定是用遞歸技術(shù)來實現(xiàn)
C.將問題劃分為k個規(guī)模相等的子問題
D.劃分代價很小而合并代價很大

最新試題

要在8×8的棋盤上擺放8個"皇后"，要求"皇后"之間不能發(fā)生沖突，即任何兩個"皇后"不能在同一行、同一列和相同的對角線上，則一般采用（）來實現(xiàn)。

題型：單項選擇題

設(shè)算法A的時間復(fù)雜度可用遞歸式表示，算法B的時間復(fù)雜度可用遞歸表示，若要使得算法B漸進(jìn)地快于算法A，則a的最大整數(shù)為（）

題型：單項選擇題

代碼如下：

題型：問答題

分治算法設(shè)計技術(shù)（）

題型：單項選擇題

在有n個無序無重復(fù)元素值的數(shù)組中查找第i小的數(shù)的算法描述如下：任意取一個元素r，用劃分操作確定其在數(shù)組中的位置，假設(shè)元素r為第k小的數(shù)。若i等于k，則返回該元素值；若i小于k，則在劃分的前半部分遞歸進(jìn)行劃分操作找第i小的數(shù)；否則在劃分的后半部分遞歸進(jìn)行劃分操作找第k-i小的數(shù)。該算法是一種基于（）策略的算法。

題型：單項選擇題

某算法的時間復(fù)雜度可用遞歸式表示，若由Θ表示，則正確的是（）

題型：單項選擇題

對n個元素值分別為-1、0或1的整型數(shù)組A進(jìn)行升序排序的算法描述如下：統(tǒng)計A中-1、0和1的個數(shù)，設(shè)分別為n1、n2和n3，然后將A中的前n1個元素賦值為-1，第n1+1到n1+n2個元素賦值為0，最后n3個元素賦值為1。該算法的時間復(fù)雜度和空間復(fù)雜度分別為（）。

題型：單項選擇題