軟件工程師筆試題目11-騰訊

第二、填空題。（每空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。遞歸和非遞歸解法都能求得“揹包問題”的一組解，試寫出“揹包問題”的非遞歸解法。