資源描述：
《算法設(shè)計與分析a&k》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、網(wǎng)絡(luò)學(xué)院算法試題A及答案一．填空題：（前四小題每題3分，第5小題4分，共16分）1.算法的特性有_0至多個輸入，至少一個輸出，指令無歧義性，指令條數(shù)有限且每條指令執(zhí)行時間有限.2．程序性能是指_運行一個程序所需的內(nèi)存大小和時間多少_.性能評估主要包含兩方面,即性能分析_與性能測量__,前者采用_分析__的方法，后者采用__測量_的方法。3.估算程序運行時間的方法有_操作計數(shù)法_和_程序的執(zhí)行步數(shù)__.4．遞歸函數(shù)的兩大基本要素是_遞歸方程和邊界條件_.5．在回溯法中，一個問題的解空間是指一個大的解決方案可以看作是由若干個小的決策組成。很多時候它們構(gòu)成一個決策序列。解決一個問題的所有可能的決
2、策序列構(gòu)成該問題的解空間.二．簡答題：（每題6分，共24分）1.什么是實例特征？答：所謂實例特征是指決定問題規(guī)模的那些因素.如，輸入和輸出的數(shù)量或相關(guān)數(shù)的大小，如對n個元素進行排序、n′n矩陣的加法等，都可以n作為實例特征.2．什么是最優(yōu)子結(jié)構(gòu)性質(zhì)?答：所謂最優(yōu)子結(jié)構(gòu)性質(zhì)，即為一個問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。3．什么是貪心選擇性質(zhì)？答：所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到.這是貪心算法可行的第一個基本要素.4.對下述的順序搜索函數(shù)，假定以被查數(shù)組的長度n為實例特征，分析其空間復(fù)雜性intSequentia
3、lSearch(inta[],constint&x,intn){//在a[0:n-1]中搜索x，若找到則回所在的位置，否則返回-1inti;for(i=0;i4、數(shù)中分配，不能再加到函數(shù)SequentialSearch所需的空間上去。三．計算和編程題：（每小題15分,共60分）1．考慮金錢兌換問題：有一個貨幣系統(tǒng)，它有n種硬幣，它們的面值為v1,v2,…,vn，其中v1=1.我們想這樣來兌換價值為y的錢，要讓硬幣的數(shù)目最少。更形式地，我們要讓下面的量在約束條件下最小.其中x1,x2,…,xn是非負整數(shù).1)用貪心算法求解該問題；2)如果硬幣的面值有1分，5分，7分和11分，給出反例說明用貪心算法并不總是有效的。1)貪心偽代碼為：Greedy_exchange(intv[],inty,intnum[],intn){inti=0,fori=0tondo
5、num[i]=0;Sort(v);//從大到小排序whiley>0do{num[i]=y/v[i];y=y%num[i++]；}returnnum;}2)反例：假如要給顧客找15分錢，按照上述貪心策略，則應(yīng)將15分分解為：11分+1分+1分+1分+1分。而事實上15分可分解為：5分+5分+5分。顯然后者的張數(shù)更少。2.假設(shè)有n(n?N且n>1)個硬幣，已知其中有一個是假幣且假幣較真幣輕.請設(shè)計分治算法求解該問題.并給出其復(fù)雜度分析.Feit_money(low,high)//假定偽幣較真幣輕{floatmid;ifhigh-low=1thenifA[low]6、rnA[low];elseifA[low]>A[high]returnA[high];5elsemid=(low+high)/2;if(high-low+1)%2==0thensum1=sum(low,mid);sum2=sum(mid+1,high);elsesum1=sum(low,mid-1);sum2=sum(mid+1,high);endififsum1=sum2thenreturnA[mid];elseifsum17、(mid+1,high);endifendifreturn0;}其時間復(fù)雜度為：O(logn).3.對于以下5個矩陣：A1:10′5,A2:5′4,A3:4′9,A4:9′10,A5:10′2求出這5個矩陣相乘需要的最小數(shù)乘次數(shù)及相應(yīng)的加括號方式.（注：要求給出計算公式和計算過程）解答：計算公式為：例如：m123451020056096039220180560292303602524018050S123451011112
