一、选择题：15分 共10题&
1.&&& 在排序方法中，关键码比较次数与记录地初始排列无关的是&&& .&
A. Shell排序&&&&& B. 归并排序&&&&&& C. 直接插入排序&&&&&&& D. 选择排序
2.&&& 以下多线程对int型变量x的操作，哪几个需要进行同步：&
A. x=y;&&&&&&&& B. x++;&&&&&&&& C. ++x;&&&&&&&&&&& D. x=1;
3.&&& 代码&
void func() {&
&&&&&&& …&
中，变量val的内存地址位于：&
A. 已初始化数据段&&& B.未初始化数据段&&&&& C.堆&&&&&&&&&&&&& D.栈
4.&&& 同一进程下的线程可以共享以下&
A. stack&&&&&&&&&&& B. data section&
C. register set&&&&&&& D. thread ID
5.&&& TCP和IP分别对应了 OSI中的哪几层？&
A.& Application layer&
B.& Data link layer&
C.& Presentation layer&
D.& Physical layer&
E.& Transport layer&
F.& Session layer&
G.& Network layer
6.&&& short a[100]，sizeof(a)返回？&
A 2&&&& B 4&&&&&& C 100&&&&&& D 200&&&&&&& E 400
7.&&& 以下哪种不是基于组件的开发技术_____。&
A XPCOM&&&&&&& B XP&&&&&&&&&& C COM&&&&&&&&&&&&&&& D CORBA
8.&&& 以下代码打印的结果是（假设运行在i386系列计算机上）：&
&&& struct st_t&
&&&&&&& int&&&&
&&&&&&& short*&
&&&&&&& char&& errstr[32];&
&&& st_t& st[16];&
&&& char* p = (char*)(st[2].errstr + 32);&
&&& printf(&%d&, (p - (char*)(st)));
A 32&&&&&&&&& B 114&
C 120&&&&&&&& D 1112
9.&&& STL中的哪种结构是连续形式的存储&
A& map&&&&& B& set&&&&&&&& C& list&&&&& D& vector
10.&&& 一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是（ ）&
A、EDCBA；&& B、DECBA；&&& C、DCEAB；&&& D、ABCDE
二、简答题：20分，共2题
1.&&& （5分）重复多次fclose一个打开过一次的FILE *fp指针会有什么结果，并请解释。&
考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异常。
2.&&& （15分）下面一段代码，想在调用f2(1)时打印err1，调用f2(2)时打印err4，但是代码中有一些问题，请做尽可能少的修改使之正确。&
1&&& static int f1(const char *errstr, unsigned int flag) {&
2&&&&&&& int copy, index,&
3&&&&&&& const static char **__err = {“err1”, “err2”, “err3”, “err4”};&
5&&&&&&& if(flag & 0x10000)&
6&&&&&&&&&&& copy = 1;&
7&&&&&&& index = (flag & 0x300000) && 20;&
9&&&&&&& if(copy) {&
10&&&&&&&&&&& len = flag & 0xF;&
11&&&&&&&&&&& errstr = malloc(len);&
12&&&&&&&&&&& if(errstr = NULL)&
13&&&&&&&&&&&&&&& return -1;&
14&&&&&&&&&&& strncpy(errstr, __err[index], sizeof(errstr));&
15&&&&&&& } else&
16&&&&&&&&&&& errstr =& __err +&&&&&
19&&& void f2(int c) {&
20&&&&&&& char *&
22&&&&&&& swtch(c) {&
23&&&&&&& case 1:&
24&&&&&&&&&&& if(f1(err, 0x110004) != -1)&
25&&&&&&&&&&&&&&& printf(err);&
26&&&&&&& case 2:&
27&&&&&&&&&&& if(f2(err, 0x30000D) != -1)&
28&&&&&&&&&&&&&&& printf(err);&
29&&&&&&& }&
三、编程题：30分 共1题&
注意：要求提供完整代码，如果可以编译运行酌情加分。
1.&&& 求符合指定规则的数。&
给定函数d(n) = n + n的各位之和，n为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如93可以看成由78生成。&&
定义数A：数A找不到一个数B可以由d(B)=A，即A不能由其他数生成。现在要写程序，找出1至10000里的所有符合数A定义的数。&
四、设计题：35分 共1题&
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1.&&& 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：&
1)&&& 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表&
2)&&& 给定一个SONG_ID，为其添加一个新的URL_ID&
3)&&& 添加一个新的SONG_ID&
4)&&& 给定一个URL_ID，将其置为不可用
限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？&
To: wchb0()&
strncpy(*errstr, __err[index - 1], strlen(*errstr));&
这句改改就行了吧：）
先做前10题
static int f1(char **errstr, unsigned int flag) {
int copy = 0, index,
const static char *__err[4] = {&err1&, &err2&, &err3&, &err4&};
if(flag & 0x10000)&
copy = 1;&
index = (flag & 0x300000) && 20;
if(copy) {&
len = flag & 0xF;&
*errstr = (char*)malloc(len * sizeof(char));&
if(*errstr == NULL)&
return -1;&
strncpy(*errstr, __err[index - 1], sizeof(errstr));&
*errstr =& (char*)(*(__err + index));&&
void f2(int c) {&
char **err = (char**)malloc(sizeof(char*));
switch(c) //dongguo
if(f1(err, 0x110004) != -1)&
printf(*err);&
printf(&n&);
if(f1(err, 0x30000D) != -1)&
printf(*err);&
printf(&n&);
free(err);
简答第二题
2.&&& 以下多线程对int型变量x的操作，哪几个需要进行同步：&
A. x=y;&&&&&&&& B. x++;&&&&&&&& C. ++x;&&&&&&&&&&& D. x=1;
------------------------------------------------------------------
&只有 D 不需要。
00411A25& mov&&&&&&&& eax,dword ptr [y]&
00411A28& mov&&&&&&&& dword ptr [x],eax
x++;
00411A2B& mov&&&&&&&& eax,dword ptr [x]&
00411A2E& add&&&&&&&& eax,1&
00411A31& mov&&&&&&&& dword ptr [x],eax
++x;
00411A34& mov&&&&&&&& eax,dword ptr [x]&
00411A37& add&&&&&&&& eax,1&
00411A3A& mov&&&&&&&& dword ptr [x],eax
00411A3D& mov&&&&&&&& dword ptr [x],1
1.&&& 求符合指定规则的数
#include &stdio.h&
void get(int num,int a[])
for(i=0;i&4;i++)
sum+= num%10;
if(num == 0)
if(sum&10000)
a[sum] = 1;
int main()
int a[10000]={0};
int i,j=0;
for(i=0;i&10000;i++)
for(i=0;i&10000;i++)
if(a[i]==0)
printf(&%d/t&,i);
j++;
if(j%10 == 0) printf(&/n&);
3.&&& 代码&
void func() {&
&&&&&&& …&
中，变量val的内存地址位于：&
A. 已初始化数据段&&& B.未初始化数据段&&&&& C.堆&&&&&&&&&&&&& D.栈
【 在 lifeistrue (lifeistrue) 的大作中提到: 】
:四、设计题：35分 共1题&
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1.&&& 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：&
1)&&& 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表&
2)&&& 给定一个SONG_ID，为其添加一个新的URL_ID&
3)&&& 添加一个新的SONG_ID&
4)&&& 给定一个URL_ID，将其置为不可用
限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
:================================================
内存不够存储这些url，所以将数据写入若干个文件中。
每一首歌曲对应的存储在文件中的信息格式为（url1, url2……）。
文件的总大小大约为2^24*2^10*4 =2^36 =64GB.根据SongID即可计算出在哪个文件的哪个位置，那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际，大约是ms级别。
将每首歌曲的信息存入文件中，由于每首歌的url不超过2^10个，所以在文件中每首歌的存储结构是2^10个int数，每个int数字标识着一个url。-1表示url不存在。初始化时将文件中每个int数初始化为-1.
这样每个SongID对应的信息占用的空间为2^10*4=4KB，设每个文件大小1G，那么每个文件可存储2^18=256K个Song的信息。总共需要64个文件，把这些文件编号从0-63.
对于任意一个SongID，他所对应的url信息所在的文件编号是：SongID&&18,在文件中的位置是：(SongID&0x3FFFF)&&12.
另外内存中用一个2^24大小的short int型数组来保存每一首歌曲对应的url的个数，计数组名为urlCount[]，初始化时值为-1,表示对应的Song_ID不存在。此数组占用空间2^25Byte=32MB;
url是否可用的信息用位图来标识。位图保存在内存中，占用的空间为2^30/8=2^27 Byte=128MB.
对所要求的操作：
:1)&&& 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表&
通过SONG_ID计算出文件号和对应在文件中的位置，从urlCount[]中读取url个数，读出所有的url,并对每个url_ID查询位图看是否可用，若可用，将此url加入返回列表。
:2)&&& 给定一个SONG_ID，为其添加一个新的URL_ID&
通过SONG_ID计算出文件号和对应在文件中的位置，设为start，在通过urlCount[]得到url个数，假设有n个url,那么将新的URL_ID写入文件的start+sizeof(int)*n处。修改urlCount[SONG_ID]的值。
:3)&&& 添加一个新的SONG_ID
检查将对应的urlCount[SONG_ID]，若为-1，则修改为0,若大于等于0，则表明改Song_ID已经存在。
:4)&&& 给定一个URL_ID，将其置为不可用&
修改url位图，标识URL_ID对应的位，表示为不可用。
一、选择题：15分 共10题&
1.&&& 在排序方法中，关键码比较次数与记录地初始排列无关的是（AD）
A. Shell排序&&&&& B. 归并排序&&&&&& C. 直接插入排序&&&&&&& D. 选择排序
2.&&& 以下多线程对int型变量x的操作，哪几个需要进行同步： （ABC?）
A. x=y;&&&&&&&& B. x++;&&&&&&&& C. ++x;&&&&&&&&&&& D. x=1;
3.&&& 代码&
void func() {&
&&&&&&& …&
中，变量val的内存地址位于： （B）
A. 已初始化数据段&&& B.未初始化数据段&&&&& C.堆&&&&&&&&&&&&& D.栈
4.&&& 同一进程下的线程可以共享以下 （BC）&
A. stack&&&&&&&&&&& B. data section&
C. register set&&&&&&& D. thread ID
5.&&& TCP和IP分别对应了 OSI中的哪几层？（EG）&
A.& Application layer&
B.& Data link layer&
C.& Presentation layer&
D.& Physical layer&
E.& Transport layer&
F.& Session layer&
G.& Network layer
6.&&& short a[100]，sizeof(a)返回？ (D)
A 2&&&& B 4&&&&&& C 100&&&&&& D 200&&&&&&& E 400
7.&&& 以下哪种不是基于组件的开发技术_____。(不清楚)&
A XPCOM&&&&&&& B XP&&&&&&&&&& C COM&&&&&&&&&&&&&&& D CORBA
8.&&& 以下代码打印的结果是（假设运行在i386系列计算机上）：（C）有人试着运行过吗？&
&&& struct st_t&
&&&&&&& int&&&&
&&&&&&& short*&
&&&&&&& char&& errstr[32];&
&&& st_t& st[16];&
&&& char* p = (char*)(st[2].errstr + 32);&
&&& printf(&%d&, (p - (char*)(st)));
A 32&&&&&&&&& B 114&
C 120&&&&&&&& D 1112
9.&&& STL中的哪种结构是连续形式的存储 （D）
A& map&&&&& B& set&&&&&&&& C& list&&&&& D& vector
10.&&& 一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是（C ）&
A、EDCBA；&& B、DECBA；&&& C、DCEAB；&&& D、ABCDE
to XINYONGHUCSDN(柯风):
和你做的不同的选择题：
TO cpfly8421()&&
归并排序最根本的操作是将两个排好序的文件合并成一个更大的排好序的文件，那么出示输入的数据对合并的影响是哪些数据比较的次数比较多，哪些少一定，对总体来说比较的次数是不变的（对一个特定的写好的归并程序来说）。归并排序只与数据的数目有关，与顺序无关。
因此我选(BD)
上面好像写成了AD，笔误了。是BD.
4.同一进程中的不同线程是共享数据段的，要不然线程相对于进程的线程间通信的优势就没有了。所以我选BD。
6.sizeof得到的是字节数。
7.我清楚。
8。C st[2].errstr + 32的地址p实际上与st[3]的地址相同， sizeof(st) = 4 + 4 + 32 = 40;
6。D& sizeof（short）× 100 ＝ 200
三：求符合的数字
void main(void)
&& func(10000);
void func(int n)
&& for(int i = 1; i &= i++)
&&&&& check(i);
void check(int n)
&& int i = 0, j = 0;
&& int sum = 0;
&& for(int i = 1; i & i++)&& //这个地方有没有更好的办法判断退出，减少循环？
&&&&&& sum =
&&&&&& for(j = j & 0; j / 10)
&&&&&&&&& sum += j % 10;
&&&&&& if(sum == n)
&&&&&& }&&&&
&& if(sum != n)
&&&&& printf(&find one! n = %d&, n);
if(sum != n)
&&&&& printf(&find one! n = %d&, n);
1.&&& 求符合指定规则的数。&
给定函数d(n) = n + n的各位之和，n为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如93可以看成由78生成。&&
定义数A：数A找不到一个数B可以由d(B)=A，即A不能由其他数生成。现在要写程序，找出1至10000里的所有符合数A定义的数。&
//========================
#include &string.h&
#include &stdio.h&
int main()
& return find_num();
int find_num()
#define N 10000
&&&&&&& char num[N+1];
&&&&&&& int sum=0, j=0, i=0;
&&&&&&& memset(num, 0, sizeof num);
&&&&&&& for(i=1; i&=N; ++i)
&&&&&&&&&&&&&&& sum = j =
&&&&&&&&&&&&&&& while(j!=0)
&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&& sum += j%10;
&&&&&&&&&&&&&&&&&&&&&&& j /= 10;
&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&& if(sum &= N) num[sum] = 1;
&&&&&&& for(i=1; i&=N; ++i)
&&&&&&&&&&&&&&& if(num[i]==0) printf(&%d/n&, i);
&&&&&&& return 0;
//==================
输出结果：
#include &iostream&
const int MAX = 10000;
int main()
bool result[MAX];
memset(result, 1, MAX);
int q = 0;
int b = 0;
int s = 0;
int g = 0;
for (q = 0; q & 10; ++q)
for (b = 0; b & 10; ++b)
for (s = 0; s & 10; ++s)
for (g = 0; g & 10; ++g)
int num = q * 1000 + b * 100 + s * 10 + g + q + b + s +
if (num & 0 && num & MAX)
result[num - 1] =
for (int i = 0; i & MAX; ++i)
if (result[i])
cout && i + 1 &&
程序题,我做的.
#include &stdio.h&
#include &stdlib.h&
#define total 200
int main(int argc, char* argv[])
&&& int result[total];
&&& for (int i = 1; i &= i++)
&&&&&&& result[i] =
&&& for (int j = 1; j &= j++)
&&&&&&& int v =
&&&&&&& unsigned int k =
&&&&&&& while( k & 0 )
&&&&&&&&&&& v += k % 10;&&
&&&&&&&&&&& k = k / 10;&&
&&&&&&& //
&&&&&&& if ((v != j) && (v &= total))
&&&&&&&&&&& result[v] = -1;
&&&&&&&&&&& result[0]++;
&&& int dd& = 0;
&&& for (int m = 1; m &= m++)
&&&&&&& if(result[m] != -1)
&&&&&&&&&&& if (dd % 10 == 0)
&&&&&&&&&&&&&&& printf(&%d/n&, m);
&&&&&&&&&&& else
&&&&&&&&&&&&&&& printf(&%d &, m);
&&&&&&& }&&&&&&
&&& return 0;&&&&
YeTimmy(啥时候才能为国家做点贡献-_-#) 的代码不错。只是这里：
if (num & 0 && num & MAX)
result[num - 1] =
条件可以稍微改进一下。把数组大小整成MAX+1，然后把num&0去掉。
if (num &= MAX)
result[num] =
result[0]自然地成了FALSE，也就不会输出了。多用一个空间，省掉两个条件，划算！
求符合指定规则的数
int szElements[10045];
int szAddValue[] = { 2, 11, 101, 1001};
void Calculate(int iBaseValue, int iPos)
if ( iPos != 0)
Calculate( iBaseValue, iPos - 1);
for ( int i = 1; i &= 9; i ++)
&&&&&&&& {
&&& iBaseValue += szAddValue[iPos];
&&& szElement[iBaseValue] = 1;
&&& Calculate(iBaseValue, iPos - 1);
&&&&&&&& }
void PrintResult()
for ( int i = 0; i & 10000; i ++)
if ( !szElement[i] )
cout && i &&
我想了两个小时,结果出来了但不知道考什么,请高手指教!
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
static int f1(char * errstr, unsigned int flag)&
{//字符串函数不支持常指针，故修改传递的指针errstr和__err
int copy = 0, index,
static char *__err[] = {&err1&, &err2&, &err3&, &err4&};//VC支持此种定义&
if(flag & 0x10000)&
copy = 1;&
index = (flag & 0x300000) && 20;&
if(copy) //copy表示要做什么？？？请高手解释哈！！！
len = flag & 0xF; //len是做下用途吗？??
//重新从原堆开始的地方分配空间，以便f2读取
//errstr = (char*)realloc(errstr, strlen(__err[index]) + len);
errstr = (char*)realloc(errstr, strlen(__err[index]) + 1);//请教高手是否更好？？？
if(errstr == NULL)&
return -1;
strcpy(errstr, __err[index]);//strncpy不会在后边添加'/0'
strcpy(errstr, __err[index]); //修改&&
void f2(int c) {
char *err = (char*)malloc(5); //不能指向栈空间！
switch(c)&
if(f1(err, 0x010004) != -1) //0xx010004第六位是数组__err的索引&
printf(&f(1)= %s&,err);&
printf(&/n&);
if(f1(err, 0x30000D) != -1)&
printf(&f(2)= %s&,err);&
printf(&/n&);
free(err);
void main()
//是不是考察栈，堆与全局数据之间的操作???如用C++的string类实现就容易多了
#include &iostream&
using std::
using std::
int main()
int a,b,c,d;//1~10000里各个位数
&&&&&&&& int j=0;//计数器
for(int n=1;n&=10000;n++)
for(int i=1;i&=n;i++)
b=(i%100-a)/10;
c=(i%1000-b)/100;
d=(i-c)/1000;//求出各个数位
e=a+b+i;//c+d+i;//求出函数
j++;//统计不符合要求的个数
if(j==n)//当完全找不到符合要求的数打印数
cout&&n&&&/n&;
上面漏写一行：
&&&&&&&& int a,b,c,d;//1~10000里各个位数
/////////////////
&&&&&&&&//所求函数数
/////////////////
&&&&&&&& int j=0;//计数器
在VC6.0下测试有效
综合下选择题，有意见请指出
1.&&& 在排序方法中，关键码比较次数与记录地初始排列无关的是&&& .& (BD,上面高手的意见)
A. Shell排序&&&&& B. 归并排序&&&&&& C. 直接插入排序&&&&&&& D. 选择排序
2.&&& 以下多线程对int型变量x的操作，哪几个需要进行同步： （ABC，上面用汇编证明)
A. x=y;&&&&&&&& B. x++;&&&&&&&& C. ++x;&&&&&&&&&&& D. x=1;
3.&&& 代码&&&&&&&&&&&&&&&&& B,没有异议
void func() {&
&&&&&&& …&
中，变量val的内存地址位于：&
A. 已初始化数据段&&& B.未初始化数据段&&&&& C.堆&&&&&&&&&&&&& D.栈
4.&&& 同一进程下的线程可以共享以下&&&&& BC，也没异议吧
A. stack&&&&&&&&&&& B. data section&
C. register set&&&&&&& D. thread ID
5.&&& TCP和IP分别对应了 OSI中的哪几层？ EG，通常只用在传输与网络层吧
A.& Application layer&
B.& Data link layer&
C.& Presentation layer&
D.& Physical layer&
E.& Transport layer&
F.& Session layer&
G.& Network layer
6.&&& short a[100]，sizeof(a)返回？ （D）
A 2&&&& B 4&&&&&& C 100&&&&&& D 200&&&&&&& E 400
VC6下测试，不过这应该与编译器有关，不一定都为2字节
7.&&& 以下哪种不是基于组件的开发技术_____。（B是说极限编程吗，CORBA是LINUX下滴COM，算吧）
A XPCOM&&&&&&& B XP&&&&&&&&&& C COM&&&&&&&&&&&&&&& D CORBA
8.&&& 以下代码打印的结果是（假设运行在i386系列计算机上）：&
&&& struct st_t&
&&&&&&& int&&&&
&&&&&&& short*&
&&&&&&& char&& errstr[32];&
&&& st_t& st[16];&
&&& char* p = (char*)(st[2].errstr + 32);&
&&& printf(&%d&, (p - (char*)(st)));
A 32&&&&&&&&& B 114&
C 120&&&&&&&& D 1112
VC6下测试，答案为120
个人理解：st[2].errstr + 32 这个就是st[3]的地址啊！
而st_t的大小为 4+4+32 ＝ 30，所以st[3]的地址就为 3*40 = 120
不正确请指出
9.&&& STL中的哪种结构是连续形式的存储& （D）
A& map&&&&& B& set&&&&&&&& C& list&&&&& D& vector
10.&&& 一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是（ 不用说 C ）&
A、EDCBA；&& B、DECBA；&&& C、DCEAB；&&& D、ABCDE
结合下自己的理解与上面各仁兄滴高见，请路过再指点
1. 归并排序的比较次数可能不同，例如1 2 3 4， 需要比较4次（12 34 13 23），而1 4 2 3 需要比较5次（14 23 12 42 43），应该只有D
用动态规划方法做的编程题
#include &iostream&
int szElement[10036];
int szAddValue[] = { 2, 11, 101, 1001};
void CalculateElement( int iPos )
int iMaxElementPre = 0;
if ( iPos != 0)
iMaxElementPre = 10 * szAddValue[iPos - 1] + iPos * 9 - 11;
for ( int i = iMaxElementP i &= 0; i --)
if ( szElement[i] )
int iNewElement =
for ( int i = 1; i &= 9; i ++)
iNewElement += szAddValue[iPos];
szElement[iNewElement] = 1;
void PrintResult()
for ( int i = 0; i & 10000; i ++)
if ( !szElement[i] )
cout && i &&
int _tmain(int argc, _TCHAR* argv[])
for ( int i = 1; i & 10036; i ++)
szElement[i] = 0;
szElement[0] = 1;
for ( int i = 0; i & 4; i ++)
CalculateElement(i);
PrintResult();
下面的程序更加简洁：
#include &iostream&
int szElement[10036];
int szAddValue[] = { 2, 11, 101, 1001};
int szAssist[9];
void CalculateElement( int iPos )
int iMaxElementPre = szAddValue[iPos] + iPos * 9 - 2;
szAssist[0] = szAddValue[iPos];
for ( int i = 1; i & 9; i ++)
szAssist[i] = szAssist[i-1] + szAddValue[iPos];
for ( int i = iMaxElementP i &= 0; i --)
if ( szElement[i] )
for ( int j = 0; j & 9; j ++)
szElement[i + szAssist[j]] = 1;
void PrintResult()
for ( int i = 0; i & 10000; i ++)
if ( !szElement[i] )
cout && i &&
int _tmain(int argc, _TCHAR* argv[])
for ( int i = 1; i & 10036; i ++)
szElement[i] = 0;
szElement[0] = 1;
for ( int i = 0; i & 4; i ++)
CalculateElement(i);
PrintResult();
YeTimmy(啥时候才能为国家做点贡献-_-#) 的思路很清晰，稍做修改：
void calcElement()
&&& char a[10036] = {0, };
&&& for (int q = 0; q & 10; q++)
&&&&&&& for (int b = 0; b & 10; b++)
&&&&&&&&&&& for (int s = 0; s & 10; s++)
&&&&&&&&&&& {
&&&&&&&&&&&&&&& for (int g = 0; g & 10; g++)
&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&& a[q * 1000 + b * 100 + s * 10 + g + q + b + s + g] = 1;
&&&&&&&&&&&&&&& }
&&&&&&&&&&& }
&&& for (int i = 0; i & 10000; ++i)
&&&&&&& if (!a[i])
&&&&&&&&&&& cout && i && & &;
1 D （查了书籍，直接插入肯定不是，shell依赖直接插入，归并排序与分组有关，书上指出直接选择的算法与初始键值排序无关）
2 A B C （三者都有读内存，然后写内存的操作）
3 A （？不是很确定，但是VC编译器是这样的。如果是B的话，那么在函数内部就没有意义了）
4 B& （线程都有独立的寄存器、栈空间、线程ID）
6 D (100*sizeof(short) =& 200)
7 B (？不是很确定， XPCOM望文生义，应该给予COM。COM自身就是COM。COBRA是基于COM的）
8 C (细心算算应该没问题）
9 D （应该考查的是对STL的理解）
大家有什么不同的看法
很多题是应试教育的产物,下面给出一个1分钟想出的最后一个问题的处理方法,但是如果不查资料,要把细节写出来,那考的就不是技巧,而是背功了:
四、设计题：35分 共1题&
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1.&&& 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：&
1)&&& 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表&
2)&&& 给定一个SONG_ID，为其添加一个新的URL_ID&
3)&&& 添加一个新的SONG_ID&
4)&&& 给定一个URL_ID，将其置为不可用
限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
本人认为可以采用建立两个 song_id 和 url_id 的 B-Tree 树 ..., 其它的东西也许不需要细说了, 如那些放在内存中, 哪些放在文件中 .... , 熟悉软件的人, 查一下数据结构和算法的书, 就可以了, 个人认为这些东西只要理解就可以了, 不要去背,& Donald.E.Knuth 做东西也是查找和推论出来的, ...&
8.&&& 以下代码打印的结果是（假设运行在i386系列计算机上）：&
&&& struct st_t&
&&&&&&& int&&&&
&&&&&&& short*&
&&&&&&& char&& errstr[32];&
&&& st_t& st[16];&
&&& char* p = (char*)(st[2].errstr + 32);&
&&& printf(&%d&, (p - (char*)(st)));
A 32&&&&&&&&& B 114&
C 120&&&&&&&& D 1112&
大家注意一下,是在i386下 int变量应该是2字节吧~。觉得应该是B（114）
1.&&& 求符合指定规则的数。&
给定函数d(n) = n + n的各位之和，n为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如93可以看成由78生成。&&
定义数A：数A找不到一个数B可以由d(B)=A，即A不能由其他数生成。现在要写程序，找出1至10000里的所有符合数A定义的数。&
#include &stdio.h&
void get(int A)
& int sum =0;
& int i,j,k,X;
&&& for(i=1;i&4;i++)
&&&&& X=A;
&&&&& A/=10;
&&&&& if(A == 0)
&& /*备注1：此时i表示A是几位数*/
&&& if(i*9&=A)&&&&&&&&&&&&&&&&
&&&&& k=1;&&&&&&& /*备注2：当num&=它的位数*9时，让k从1开始查找*/
&&&&& k=A-(9*(i-1)+X);&&& /*备注3：当num&它的位数*9时，让k从A-(9*(i-1)+X)& 开始查找*/&&
& for(;k&=A;k++)
&&& for(j=1;j&=i;j++)
&&&&& sum+=k%10;&&&& /*求出此时k各个位数字的和*/
&&& if(sum+k=A)&&&&& /*发现k的各个位数的和+k=A时，既A可以找到d(B)=A中的B,此时B就是k*/
&&&&& return();
& printf(&%d/n&,A);
int main()
& for(i=0;i&10000;i++)
&&& get(i);
编程求数：
abcde转换后10000a+1000b+100c+10d+e+a+b+c+d+e
#define NUM_SAVE_MAX 2000
#define INTBYTES 4
static int save[NUM_SAVE_MAX];
void search(int *arr,int n)
&& for(int *p=p&arr+INTBYTES*n;p++)
&&&&&&&& int x=*p;
&&&&&&&& x=x%10001;
&&&&&&&& x=x%1001;
&&&&&&&& x=x%101;
&&&&&&&& x=x%11;
&&&&&&&& x=x%2;
&&&&&&& if(x!=0)
&&&&&&& int savenum=0;
&&&&&&& save[savenum]=x;
&&&&&&& savenum++;
编程求数：
abcde转换后10000a+1000b+100c+10d+e+a+b+c+d+e
#define NUM_SAVE_MAX 2000
#define INTBYTES 4
static int save[NUM_SAVE_MAX];
void search(int *arr,int n)
for(int *p=p&arr+INTBYTES*n;p++)
int savenum=0;
x=x%10001;
save[savenum]=x;
savenum++;
2.&&& 以下多线程对int型变量x的操作，哪几个需要进行同步：&
A. x=y;&&&&&&&& B. x++;&&&&&&&& C. ++x;&&&&&&&&&&& D. x=1;
我怎么觉得是ACD
& Name: 编程题：求符合指定规则的数。&
& Copyright: 2006年&
& Author: 崔卫兵&
& Date: 11-10-06 14:36
& Description: 求符合指定规则的数。&
& 给定函数d(n) = n + n的各位之和，n为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如93可以看成由78生成。&&
& 定义数A：数A找不到一个数B可以由d(B)=A，即A不能由其他数生成。现在要写程序，找出1至10000里的所有符合数A定义的数。&
#include &iostream&
short NumSum(short);
int main(int argc, char *argv[])
&&& short sArr[10000]={0};
&&& short len=10000;//sizeof(sArr)/sizeof(short)
&&& for(int i=1;i&i++){
&&&&&&& short tmp=NumSum(i);
&&&&&&& if(tmp&=10000){
&&&&&&&&&&& sArr[tmp-1]=1;
&&&&&&& }&&&&
&&& for(int i=0;i&i++){
&&&&&&& if(sArr[i]==0)
&&&&&&&&&&& cout&&i+1&&
&&& system(&PAUSE&);
&&& return EXIT_SUCCESS;
short NumSum(short num){
&&&&& short newNum=
&&&&& newNum+=num/1000+num%;num%100/10+num%10;
&&&&& return newN
三、编程题：30分 共1题&
1.&&& 求符合指定规则的数。&
&&& class Program
&&&&&&& static ArrayList allNum=new ArrayList();
&&&&&&& static void Main(string[] args)
&&&&&&&&&&&
&&&&&&&&&&& for (int i = 1; i &= 10000; i++)
&&&&&&&&&&& {
&&&&&&&&&&&&&&& buffer=jisuan(i);
&&&&&&&&&&&&&&& if (check(buffer)) allNum.Add(buffer);
&&&&&&&&&&& }
&&&&&&&&&&& for (int j = 1; j &= 10000; j++)
&&&&&&&&&&& {
&&&&&&&&&&&&&&& if (check(j)) Console.WriteLine(j);
&&&&&&&&&&& }
&&&&&&& static bool check(int i)
&&&&&&&&&&& foreach (int num in allNum)
&&&&&&&&&&& {
&&&&&&&&&&&&&&& if (i == num)
&&&&&&&&&&& }
&&&&&&&&&&&
&&&&&&& static int jisuan(int i)
&&&&&&&&&&& int sum =
&&&&&&&&&&& foreach (char c in i.ToString().ToCharArray())
&&&&&&&&&&& {
&&&&&&&&&&&&&&& sum += int.Parse(c.ToString());
&&&&&&&&&&& }
&&&&&&&&&&&
三 1&& POJ 1316
Problem Id:1316& User Id:jiang5448&
Memory:192K& Time:0MS
Language:G++& Result:Accepted
#include &iostream&
bool e[10000];
int d (int n)
&&& int s=n;
&&& while (n)
&&&&&&&&& s+=n%10;
&&&&&&&&& n/=10;
int main()
&&& for (i=0;i&10000;i++)
&&& for (i=1;i&10000;i++)
&&& if (d(i)&10000)
&&& e[d(i)]=
&&& for (i=1;i&10000;i++)
&&& if (!e[i])
&&& cout&&i&&
&&& return 0;
编程题，算法复杂度为O（lgn * lgn）
char szElements[10036];
int szAddValue[] = {2, 11, 101, 1001};
char szAssist[27];
void Calculate( int iPos )
int iCurAddValue = szAddValue[iPos];
int iMaxElementPre = iCurAddValue + iPos * 9 - 2;
int nMergeElements = iMaxElementPre - iCurAddValue + 1;
if ( nMergeElements & 0 )
memcpy(szAssist, szElements + iCurAddValue, nMergeElements);
memcpy(szElements + iCurAddValue * 10, szAssist, nMergeElements);
memcpy(szElements + iCurAddValue, szElements, iCurAddValue);
for ( int i = 0; i & nMergeE i ++)
if (szAssist[i])
szElements[i + iCurAddValue ] = 1;
for ( int i = 2, iOffset = 2 * iCurAddV i &= 9; i ++)
memcpy(szElements + iOffset, szElements + iCurAddValue, iCurAddValue);
void main()
memset( szElements, 0, 10036);
szElements[0] = 1;
for ( int i = 0; i & 4; i ++)
Calculate(i);
for ( int i = 1; i &= 10000; i ++)
if (!szElements[i])
printf(&%d/n&, i);
上面少写了一句 for ( int i = 2, iOffset = 2 * iCurAddV i &= 9; i ++)
改为 for ( int i = 2, iOffset = 2 * iCurAddV i &= 9; i ++， iOffset += iCurAddValue)
修改代码的结果如下：
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
//#define DEBUG
static int f1( char **errstr, unsigned int flag)& //change&&& char *errstr& --&char **errstr
int copy, index,&
//const static char **__err = {&err1&, &err2&,&err3&,&err4&};& //此行换为下行
const char __err[4][10] = {&err1&, &err2&,&err3&,&err4&};
if(flag & 0x10000)&
copy = 1;&
index = (flag & 0x300000) && 20;
#ifdef DEBUG
printf(&copy %u index:%u/n&,copy,index);
len = flag & 0&
&&& *errstr = malloc(len);&
if(*errstr == NULL) //change =& -&& ==
return -1;&
strncpy(*errstr, __err[index-1], len); //change -1 sizeof(errstr)=4 --&len
&*errstr = __err +&
void f2(int c)&
switch(c)&
if(f1(&err, 0x110004) != -1)&
printf(&%s/n&,err);&
if(f1(&err, 0x30000D) != -1)&& //change& f2 -&f1
printf(&%s/n&,err);
free(err); //add
int main(int argc,char *argv[])
四、设计题：35分 共1题&
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1.&&& 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：&
1)&&& 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表&
2)&&& 给定一个SONG_ID，为其添加一个新的URL_ID&
3)&&& 添加一个新的SONG_ID&
4)&&& 给定一个URL_ID，将其置为不可用
限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
因为“每首歌的URL不超过2^10个”，似乎在提示每个SONG_ID的URL_ID占用同样的内存，那么1g内存每个SONG_ID仅有64byte，而2^10个URL_ID即使一个bit存一个，也需要128byte，显然行不通的。
存2^30条URL_ID，即一个URL_ID最多1byte的内存。而由于每个SONG_ID占用的内存不同，所以至少还得存储这个信息。以最少信息论，假设每个URL_ID占一个bit，则一个SONG_ID占用内存的长度最大会有2^20bit（转换成字节、字等占用的内存更多，但计算会方便一些，快一些）...即长度最少要占用21bit。
另外，需要一个bit存一个URL_ID，至少还需要存一个MIN_URL_ID(然后第nbit为1代表MIN_URL_ID+n这个URL_ID也属于这个SONG_ID)，SONG_ID因为基本可以认为不会删除，所以不于保存，直接按index来。
也就是说，要存储一个SONG_ID，至少需要内存 32＋21+URL_ID_CNT bits.所以总内存需:
（32＋21） × 2^24& + 2^30& & 1G
&汗一个，写到这里忽然发现1G内存存1g个URL_ID,很明显直接就是不够...&
所以，要占用1g以下内存，基本上可以认为需要用硬盘做数据交换，但似乎总感觉不爽，毕竟从题意上看，是不适合这样的。当然了，1个文件2g最大，也不明白意思。直觉上认为跟分布运算有关。
PS:因为URL_ID变化较大，（很可能随时增加或者减少一个）所以不适合用连续存储的方式。
假设有如下数据段，进行二路归并：
A：1 2 3 4 5 6
比较次数：6次
A：1 2 3 4 5 6
比较次数：1次
看到那个求小于100000的那个题的没一个对的！
看看14可以合成不？
f(a+1)=c;
b到c之间的都是不可合成的数。
原因：如果b与c间有d可以由合成即f(x)=d;
=& x&a && x&a+1
=& ...........
我觉得3.1应该倒着推！从0到1000，看看都可以生成什么数，然后把生成的数标志位置为true，最后检查一下有那些数仍然为false就可以了。
#include &iostream&
bool flag[2000]={false};& //1-2000
int main()
for(int i=0;i&10;++i)
for(int j=0;j&10;++j)
for(int k=0;k&10;++k)
flag[i*100+j*10+k*1 + i+j+k]=
for(int num=0;num&1000;++num)
if(flag[num]==false)
cout&&num&&& &;
以１００ 为例子
一个容易看懂的：
#include &iostream&
#include &cmath&
#include &vector&
#include &list&
#include &algorithm&
#include &iterator&
int main()
& vector&int&
& list&int&
& for ( int& n = 1; n & 100; ++n )
&&&&& int j = ( (n%10) + (n/10) + n& );
&&&&& if ( j & 100 )
& a.push_back(j);
& sort( a.begin(), a.end() );
& for ( int i = 1; i &= 100; ++i )
&&& b.push_back(i);
& for ( int j = 0; j & a.size(); ++j )
&&&&& b.remove( a[j] );
& ostream_iterator&int,char& out ( cout, &/n& );
& copy( b.begin(), b.end(), out );
& cout && & Done!& &&
& return 0;
&&g++ baidu.C
&& ./a.out
这样就没有１００啦
#include &iostream&
#include &cmath&
#include &vector&
#include &list&
#include &algorithm&
#include &iterator&
int main()
vector&int&
for ( int n = 1; n & 100; ++n )
int j = ( (n%10) + (n/10) + n );
if ( j &= 100 )
a.push_back(j);
sort( a.begin(), a.end() );
for ( int i = 1; i &= 100; ++i )
b.push_back(i);
for ( int j = 0; j & a.size(); ++j )
b.remove( a[j] );
ostream_iterator&int,char& out ( cout, &/n& );
copy( b.begin(), b.end(), out );
cout && & Done!& &&
&g++ baidu.C
TO qdyongge:
&&&&&&&& =====================================================&
&&&&&&&& ||晕，看到那个求小于100000的那个题的没一个对的！
&&&&&&&& ||看看14可以合成不？
&&&&&&&& ||f(a)=b;
&&&&&&&& ||f(a+1)=c;
&&&&&&&& ||b到c之间的都是不可合成的数。
&&&&&&&& ||原因：如果b与c间有d可以由合成即f(x)=d;
&&&&&&&& ||=& x&a && x&a+1
&&&&&&&& ||=& ...........
&&&&&&&& =====================================================
你的说法不对噢!认真的思考一下: 14=7+7;
其次:你的这个理论:&(a)=b;f(a+1)=c;b到c之间的都是不可合成的数&有什么数学根据吗?
用一个简单证伪:
&&&& f(999)=999+9+9+9=1026;
&&&& f(999+1)==1001;
&&&& 在之间可合成的数很多,就列一个吧.如:;9+9+8
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：36773次
排名：千里之外
原创：39篇
转载：50篇
(3)(7)(32)(2)(7)(1)(10)(8)(10)(6)(3)(1)