软件工程师笔试题目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。递归和非递归解法都能求得“背包问题”的一组解,试写出“背包问题”的非递归解法。