笔试真题刷题平台
精选近几年名企笔试真题，笔试之前刷刷真题，有备无患
三、填空题
阅读下列函数说明和C代码，将应填进（n）处的字句写在答题纸的对应栏内。
【说明】设有一个带表头结点的双向循环链表L,每个结点有4个数据成员：指向先驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0.每当在链表上进行一次L.Locate（x）操纵时，令元素值x的结点的访问频度freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
【函数】
void Locate(int &x)
{
< 结点类型说明 >
*p = first->next;
while (p != first && ____-) p = p->next;
if (p != first)
{
____________ ;
< 结点类型说明 >
*current = p;
current->prior->next = current->next;
current->next->prior = current->prior;
p = current->prior;
while (p != first &&____________ ) p = p->prior;
current->next = __________________ ;
current->prior = p;
p->next->prior = current;
p->next = __________________ ;
}
else
printf(“Sorry. Not find!\n”); \*没找到*\
}
p->freq++
p->data!=x
current->freq>p->freq
p->next
current
四、问答题
“背包题目”的基本描述是：有一个背包，能盛放的物品总重量为S,设有N件物品，其重量分别为w1，w2，…，wn，希望从N件物品中选择若干物品，所选物品的重量之和恰能放进该背包，即所选物品的重量之和即是S。递归和非递归解法都能求得“背包题目”的一组解，试写出“背包题目”的非递归解法
// ---------------------------------------------------
// 注1: 一般要求一个解,此程序是得到所有解
// 注2: 由于32位unsigned int限制,最多32个物品
// ---------------------------------------------------
#include "stdafx.h"
#include <iostream>
using namespace std;
// 物品总数
const int N_ITEM = 5;
// 背包能装的重量
const int BAG = 15;
// 初始化每个物品的重量
int item[N_ITEM] = {2, 3, 5, 7, 8};
// 标记数组
int flag[N_ITEM] = {0, 0, 0, 0, 0};
// 结果计数器
int resultCount = 0;
// 打印结果
void Print();
int main()
{
// 打印已知条件
cout << "BAG Weight:" << BAG << endl;
cout << "Item Number:" << N_ITEM << endl;
for ( int i=0; i!=N_ITEM; i++)
{
cout << "Item." << i+1 << " W=" << item[i] << "\t" ;
}
cout << endl;
unsigned int count = 0;
unsigned int all_count = 1;
for ( int i=0; i!=N_ITEM; i++)
{
all_count *= 2;//all_count记录可能解的个数
}
while (1)
{
// 模拟递归...列举所有flag数组可能
// 其实就这个for循环是关键
for ( int i=0; i!=N_ITEM; i++)
{
if ( 0 == flag[i] )
{
flag[i] = 1;
continue ;
}
else
{
flag[i] = 0;
break ;
}
}
// 本次重量,初始化0
int temp = 0;
// 按标记计算所有选中物品重量和
for ( int i=0; i!=N_ITEM; i++)
{
if ( 1 == flag[i] )
{
temp += item[i];
}
}
// 满足背包重量就打印
if ( temp == BAG )
{
resultCount++;
Print();
}
// 如果遍历了所有情况就break掉while(1)循环
count++;
if (count == all_count)
{
break ;
}
}
return 0;
}
void Print()
{
cout << "Result " << resultCount << endl;
for ( int i=0; i!=N_ITEM; i++)
{
if ( 1 == flag[i] )
{
cout << "Item." << i+1 << " Weight:" << item[i] << "\t" ;
}
}
cout << endl;
}
