考題算法設(shè)計(jì)與分析

1、57、在字符串的模式匹配過(guò)程中，如果模式串的每個(gè)字符依次和主串中一個(gè)連續(xù)的字符序列相等，則稱為匹配成功。如果不能在主串中找到與模式串相同的子串，則稱為匹配失敗。在布魯特-福斯模式匹配算法(樸素的或基本的模式匹配)中，若主串和模式串的長(zhǎng)度分別為n和m(且n遠(yuǎn)大于m)，且恰好在主串末尾的m個(gè)字符處匹配成功，則在上述的模式匹配過(guò)程中，字符的比較次數(shù)最多為_。 An*m B(n-m+1)*m C(n-m-1)*m D(n-m)*n某貨車運(yùn)輸公司有一個(gè)中央倉(cāng)庫(kù)和n個(gè)運(yùn)輸目的地，每天要從中央倉(cāng)庫(kù)將貨物運(yùn)輸?shù)剿羞\(yùn)輸目的地，到達(dá)每個(gè)運(yùn)輸目的地一次且僅一次，最后回到中央倉(cāng)庫(kù)。在兩個(gè)地點(diǎn)i和j之間運(yùn)輸貨物存在費(fèi)

2、用Cij。為求解旅行費(fèi)用總和最小的運(yùn)輸路徑，設(shè)計(jì)如下算法：首先選擇離中央倉(cāng)庫(kù)最近的運(yùn)輸目的地1，然后選擇離運(yùn)輸目的地1最近的運(yùn)輸目的地2，每次在來(lái)訪問(wèn)過(guò)的運(yùn)輸目的地中選擇離當(dāng)前運(yùn)輸目的地最近的運(yùn)輸目的地，最后回到中央倉(cāng)庫(kù)。 該算法采用了_算法設(shè)計(jì)策略，其時(shí)間復(fù)雜度為_。63、 A分治 B動(dòng)態(tài)規(guī)劃 C貪心 D回溯64、 65、現(xiàn)要對(duì)n個(gè)實(shí)數(shù)(僅包含正實(shí)數(shù)和負(fù)實(shí)數(shù))組成的數(shù)組A進(jìn)行重新排列，使得其中所有的負(fù)實(shí)數(shù)都位于正實(shí)數(shù)之前。求解該問(wèn)題的算法的偽代碼如下所示，則該算法的時(shí)間和空間復(fù)雜度分別為_。 i=0; j=n-1; while ij do while Ai0 do i=i+1; while

3、Aj0 do j=j-1; if ij do 交換Ai和Aj; 33、針對(duì)應(yīng)用在運(yùn)行期的數(shù)據(jù)特點(diǎn)，修改其排序算法使其更高效，屬于_維護(hù)。 A正確性 B適應(yīng)性 C完善性 D預(yù)防性34、下圖所示的邏輯流實(shí)現(xiàn)折半查找功能，最少需要_個(gè)測(cè)試用例可以覆蓋所有的可能路徑。 A1 B2 C3 D457、在KMP模式匹配算法中，需要求解模式串p的next函數(shù)值，其定義如下(其中，j是字符在模式串中的序號(hào))。對(duì)于模式串“abaabaca”，其next函數(shù)值序列為_。 A01111111 B01122341 C01234567 D011.2233462、迪杰斯特拉(Dijkstra)算法用于求解圖上的單源點(diǎn)最短路

4、徑。該算法按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑，本質(zhì)上說(shuō)，該算法是一種基干_策略的算法。 A分治 B動(dòng)態(tài)規(guī)劃 C貪心 D回溯63、在有n個(gè)無(wú)序無(wú)重復(fù)元素值的數(shù)組中查找第i小的數(shù)的算法描述如下：任意取一個(gè)元素r，用劃分操作確定其在數(shù)組中的位置，假設(shè)元素r為第k小的數(shù)。若i等于k，則返回該元素值；若i小于k，則在劃分的前半部分遞歸進(jìn)行劃分操作找第i小的數(shù)；否則在劃分的后半部分遞歸進(jìn)行劃分操作找第k-i小的數(shù)。該算法是一種基于_策略的算法。 A分治 B動(dòng)態(tài)規(guī)劃 C貪心 D回溯64、對(duì)n個(gè)元素值分別為-1、0或1的整型數(shù)組A進(jìn)行升序排序的算法描述如下：統(tǒng)計(jì)A中-1、0和1的個(gè)數(shù)，設(shè)分別為n1、n2和n3，然

5、后將A中的前n1個(gè)元素賦值為-1，第n1+1到n1+n2個(gè)元素賦值為0，最后n3個(gè)元素賦值為1。該算法的時(shí)間復(fù)雜度和空間復(fù)雜度分別為_。 A B C D65、設(shè)算法A的時(shí)間復(fù)雜度可用遞歸式表示，算法B時(shí)間復(fù)雜度可用遞歸式表示，若要使得算法B漸進(jìn)地快于算法A，則a的最大整數(shù)為_。 A48 B49 C13 D1448、 以下關(guān)于高級(jí)程序設(shè)計(jì)語(yǔ)言翻譯的敘述中，正確的是_。 A可以先進(jìn)行語(yǔ)法分析，再進(jìn)行詞法分析 B在語(yǔ)法分析階段可以發(fā)現(xiàn)程序中的所有錯(cuò)誤 C語(yǔ)義分析階段的工作與目標(biāo)機(jī)器的體系結(jié)構(gòu)密切相關(guān) D目標(biāo)代碼生成階段的工作與目標(biāo)機(jī)器的體系結(jié)構(gòu)密切相關(guān)49、 下圖所示為一個(gè)有限自動(dòng)機(jī)(其中，A是初態(tài)

6、、C是終態(tài))，該自動(dòng)機(jī)可識(shí)別_。 A0000 B1111 C0101 D101050、 傳值與傳地址是函數(shù)調(diào)用時(shí)常采用的信息傳遞方式，_。 A在傳值方式下，是將形參的值傳給實(shí)參 B在傳值方式下，形參可以是任意形式的表達(dá)式 C在傳地址方式下，是將實(shí)參的地址傳給形參 D在傳地址方式下，實(shí)參可以是任意形式的表達(dá)式62、 要在88的棋盤上擺放8個(gè)“皇后”，要求“皇后”之間不能發(fā)生沖突，即任何兩個(gè)“皇后”不能在同一行、同一列和相同的對(duì)角線上，則一般采用_來(lái)實(shí)現(xiàn)。 A分治法 B動(dòng)態(tài)規(guī)劃法 C貪心法 D回溯法63、 分治算法設(shè)計(jì)技術(shù)_。 A一般由三個(gè)步驟組成：?jiǎn)栴}劃分、遞歸求解、合并解 B一定是用遞歸技術(shù)來(lái)實(shí)現(xiàn) C將問(wèn)題劃分為庀個(gè)規(guī)模相等的子問(wèn)題 D劃分代價(jià)很小而合并代價(jià)很大64、 某算法的時(shí)間復(fù)雜度可用遞歸式表示，若用表示，則