算法設(shè)計(jì)與分析問(wèn)答題每日一練(2020.06.04)

來(lái)源：考試資料網(wǎng)

1.問(wèn)答題給出一個(gè)長(zhǎng)度為n的文本和長(zhǎng)度為m的模式構(gòu)成的實(shí)例，它是蠻力字符串匹配算法的一個(gè)最差輸入.并指出，對(duì)于這樣的輸入需要做多少次字符比較運(yùn)算。

參考答案：

文本：由n個(gè)0組成的文本
模式：前m-1個(gè)是0，最后一個(gè)字符是1
比較次數(shù)：m（n-m+1）

2.問(wèn)答題設(shè)有n個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)，顧客i需要的服務(wù)時(shí)間為ti，1<=i<=n。應(yīng)該如何安排n個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最??？（平均等待時(shí)間是n個(gè)顧客等待服務(wù)時(shí)間的總和除以n）。

參考答案：貪心策略：最短服務(wù)時(shí)間優(yōu)先。
將n個(gè)顧客的服務(wù)時(shí)間ti按照由小到大排序，n個(gè)顧客的服務(wù)調(diào)度方案即為排序后的順序...

點(diǎn)擊查看完整答案

3.問(wèn)答題非確定性Turing機(jī)與確定性Turing機(jī)的主要區(qū)別在什么地方？

參考答案：與DTM不同的是，NDTM的每一步動(dòng)作允許有若干個(gè)選擇，對(duì)于給定的Q×Tk的一個(gè)元素（qi， a1，a2，&#...

點(diǎn)擊查看完整答案

4.問(wèn)答題 判斷下述等式的真?zhèn)危?br />

參考答案：

5.問(wèn)答題設(shè)n=4，且（a1，a2，a3，a4）=（do，if，read，while），已知已知P（1：4）=（3，3，1，1）和Q（0：4）=（2，3，1，1，1）。使用動(dòng)態(tài)規(guī)劃方法構(gòu)造一棵最佳二叉排序樹(shù)（計(jì)算出C、W、R陣的結(jié)果）。

參考答案：