天津科技大學(xué)09年《算法設(shè)計(jì)與分析》試卷

1、算法分析與設(shè)計(jì)樣題算法分析與設(shè)計(jì)樣題一、填空題（每空一、填空題（每空2分，共分，共2626分）分）(1)算法是由若干條指令組成的有窮序列，且滿足幾條性質(zhì)，其中有限性是指。(2)根據(jù)符號(hào)?定義，用它評(píng)估算法的復(fù)雜性，得到的只是該復(fù)雜性的一個(gè)下界。這個(gè)下界的階越高，則。(3)由分治法產(chǎn)生的子問(wèn)題往往是，這就為使用提供了方便。(4)動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是。(5)貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以。(6)回溯法在包含問(wèn)題的所有解的解

2、空間樹中，按照，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。(7)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致兩種不同的分支限界法，它們是。(8)一般情況下，可將概率算法分為四類：數(shù)值概率算法、蒙特卡羅算法、。(9)在進(jìn)行問(wèn)題的計(jì)算復(fù)雜性分析時(shí)，使用的較重要的三個(gè)計(jì)算模型是隨機(jī)存取機(jī)RAM、。(10)通常將可在看作是易解問(wèn)題，而將需要指數(shù)時(shí)間解決的問(wèn)題看作是難問(wèn)題。(11)回溯法和分支限界法使用的兩類典型的解空間樹分別為。(12)在計(jì)算機(jī)上產(chǎn)生偽隨機(jī)數(shù)最常

3、用的方法是。二、對(duì)于下列各組函數(shù)f(n)和g(n)確定f(n)=O(g(n))或f(n)=?(g(n))或f(n)=?(g(n))并簡(jiǎn)述理由。(每小題3分，共12分)(1)f(n)=logn6g(n)=8logn5(2)f(n)=100ng(n)=log2n(3)f(n)=nlognng(n)=logn(4)f(n)=2ng(n)=10n3三、試述分治法的基本思想并用于兩個(gè)大整數(shù)的乘法分析其算法復(fù)雜性。(12分)四、試給出基于分治策略的