在网上看到百度07年的招聘试题，原文在这里，发现大部分不会做，没有一个题目有把握，利用网络资源吧每一个题，都尽可能详细的找到答案，记录在这里。
一、选择题：15 分 共 10 题
1. 在排序方法中，关键码比较次数与记录地初始排列无关的是：
A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序
解：这一题自己的解答是D，选择排序的比较次数是固定的，要进行(1/2)n*(n-1)次比较。而插入排序，根据原序列的情况不同，比较次数不同，如果远序列是按照从小到大有序的排列，则只需要n此比较就可以；如果最糟的情况下，即逆序排列，则要进行(1/2)n*(n-1)此比较。Shell排序，在本质上可以看成是插入排序，所以也是与数列的初始排列有关的。归并排序，可以设一个这样的例子，一个长度为n的数列，最后一次归并前半部分为和后半部分分别是有序的，若前半部分所有的元素都小于后半部分，这时最后一次归并就只要比较n/2次；另外，最后一次归并前，前部分每个隔一个元素比后半部分的大，这样前后部分的元素交替进入有序数列，这样就要进行n次比较。
2. 以下多线程对 int 型变量x的操作，哪几个需要进行同步：
A. x=y; B. x++; C. ++x; D. x=1;
解：下面是反汇编的代码，从汇编代码中就能看出此题肯定要选BC，A的争议比较大。
x = y;
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
x = 1;
00411A3D mov dword ptr [x],1这个题目，还有非常专业的解释在这里：http://www.parallellabs.com/2010/04/15/atomic-operation-in-multithreaded-application/可以好好看下一
3. 代码
void func()
{
static int val;
…
}
中，变量 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 系列计算机上）：
字串2
struct st_t
{
int status;
short *pdata;
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, len;
3 const static char **__err = { "err1", "err2", "err3", "err4" };
字串2
4
5 if( flag & 0x10000 )
6 copy = 1;
7 index = ( flag & 0x300000 ) >> 20;
8
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 + index;
17 }&nbs
p;
18
19 void f2( int c ) {
20 char *err;
21
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 }
三、编程题：30 分 共 1 题
注意：要求提供完整代码，如果可以编译运行酌情加分。
1. 求符合指定规则的数。
给定函数 d(n) = n + n 的各位之和，n 为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如 93 可以看成由 78 生成。 字串3
定义数 A：数 A 找不到一个数 B 可以由 d(B)=A，即 A 不能由其他数生成。现在要写程序，找出 1 至 10000 里的所有符合数 A 定义的数。
输出：
1
3
…
四、设计题：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 个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
没有评论:
发表评论