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

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

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

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

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

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

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

5.問答題設(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）。使用動態(tài)規(guī)劃方法構(gòu)造一棵最佳二叉排序樹（計算出C、W、R陣的結(jié)果）。