第二、填空題。(每空4分,總計40分)
1. 閱讀下列說明和流程圖,將應填入(n)的字句寫在答題紙的對應欄內。
【說明】
正弦函式可以用如下的泰勒級數展開式來計算:
下面的流程圖描述了利用上述展開式計算並列印 的近似值的過程,其中用 (>0)表示誤差要求,小於該誤差即可結束計算,列印結果。
【流程圖】
2. 閱讀下列函式說明和C程式碼,將應填入(n)處的字句寫在答題紙的對應欄內。
【說明】設有一個帶表頭結點的雙向迴圈連結串列L,每個結點有4個數據成員:指向前驅結點的指標prior、指向後繼結點的指標next、存放資料的成員data和訪問頻度freq。所有結點的freq初始時都為0.每當在連結串列上進行一次te(x)操作時,令元素值x的結點的訪問頻度freq加1,並將該結點前移,連結到現它的訪問頻度相等的結點後面,使得連結串列中所有結點保持按訪問頻度遞減的'順序排列,以使頻繁訪問的結點總是靠近表頭。
【函式】
void Locate(int &x)
{ << span="">結點型別說明>
*p=first->next;
while(p!=first && 1 ) p=p->next;
if (p!=first)
{ 2 ;
<< span="">結點型別說明>
*current=p;
current->prior->next=current->next;
current->next->prior=current->prior;
p=current->prior;
while(p!=first && 3 ) p=p->prior;
current->next= 4 ;
current->prior=p;
p->next->prior=current;
p->next= 5 ;
}
else
printf(“Sorry. Not find!”); *沒找到*
}
第三、附加題(30分)
“揹包問題”的基本描述是:有一個揹包,能盛放的物品總重量為S,設有N件物品,其重量分別為w1,w2,…,wn,希望從N件物品中選擇若干物品,所選物品的重量之和恰能放入該揹包,即所選物品的重量之和等於S。遞迴和非遞迴解法都能求得“揹包問題”的一組解,試寫出“揹包問題”的非遞迴解法。