2006年百度招聘考试笔试题

2006 年百度招聘考试笔试题 一、选择题：15 分 共 10 题 1.一个含有 n 个顶点和 e 条边的简单无向图，在其邻接矩阵存储结构中共有____个零元素。 A．e B．2e C．n2-e D．n2-2e 2.____是面向对象程序设计语言中的一种机制。这种机制实现了方法的定义与具体的对象 无关，而对方法的调用则可以关联于具体的对象。 A．继承（Inhertance） B．模板（Template） C．对象的自身引用（Self-Reference） D．动态绑定（Dynamic Binding） 3.应用层 DNS 协议主要用于实现 网络服务功能. A. IP 地址到网络设备名字的映射 B. IP 地址到网络硬件地址的映射 C. 网络设备名字到 IP 地址的映射 D. 网络硬件地址到 IP 地址的映射 4.linux 默认情况下，一个进程最多能打开多少文件？ A.64 B. 128 C. 512 D. 1024 5.下面结构体 struct s1 { char ch, *ptr; union { short a, b; unsigned int c:2, d:1; } struct s1 *next; }; 的大小是_____： A. 12 字节 B.16 字节 C.20 字节 D. 24 字节 6.任何一个基于"比较"的内部排序的算法，若对 6 个元素进行排序，则在最坏情况下所需的 比较次数至少为____。 A．10 B．11 C．21 D．36 7.以下不是进程间通讯的是___ A 共享内存 B 信号量 C 线程局部存储 D 消息队列 8.下面程序，求 count 的值 int func(x) { int count= 0; x=9999; while(x) { Count ++; x = x&(x-1); } return count; } A 8； B 10； C 5； D 11 9.使用 malloc 系统调用分配的内存是在____ 上分配的？ A 栈； B bss； C 物理内存； D 堆 10.最坏情况下，合并两个大小为 n 的已排序数组所需要的比较次数_____ A.2n B.2n-1 C.2n+1 D.2n-2 二、简答题：20 分，共 3 题 1.（5 分）下面这段代码是把中英文混合字符串(汉字用两个字节表示，特点是第一个字节 的最高位为 1)中的大写字母转化为小写字母，请找出其中的 bug，注意各种异常情况。 for (char *piterator = szWord; *piterator != 0; piterator++) { if (*piterator & 0x80 != 0) { piterator++; } else if (*piterator >= 'A' && *piterator <= 'Z') piterator += 32; } 2.（5 分）对给定的上亿条无序的 url，请按照 domain、site 以及 path 分别排序，并请指出 排序过程中可能会遇到的哪些问题？如何提高效率？ 例如：http://www.baidu.com/path/about.html，domain、site 以及 path 的定义分别如下： Domain:baidu.com Site:www.baidu.com Path: www.baidu.com/path 3.（10 分）某型 CPU 的一级数据缓存大小为 16K 字节，cache 块大小为 64 字节；二级缓存 大小为 256K 字节，cache 块大小为 4K 字节，采用二路组相联。经测试，下面两段代码运 行时效率差别很大，请分析哪段代码更好，以及可能的原因。 为了进一步提高效率，你还可以采取什么办法？ A 段代码 int matrix[1023][15]; const char *str = "this is a str"; int i, j, tmp, sum = 0; tmp = strlen(str); for(i = 0; i < 1023; i++) { for(j = 0; j < 15; j++) { sum += matrix[j] + tmp; } } B 段代码 int matrix[1025][17]; const char *str = "this is a str"; int i, j, sum = 0; for(i = 0; i < 17; i++) { for(j = 0; j < 1025; j++) { sum += matrix[j] + strlen(str); } } 三、编程题：30 分 共 1 题 注意：要求尽可能提供完整代码，如果可以编译运行酌情加分。 1.内存中有一个长数组，条目数为 10 万，数组单元为结构体 struct array，sizeof(struct array) 为 512 字节。结构有一 int 型成员变量 weight。现需要取得按 weight 值从大到小排序的前 500 个数组单元，请实现算法，要求效率尽可能高。 四、设计题：35 分 共 1 题 注意：请尽可能详细描述你的数据结构、系统架构、设计思路等，建议多写一些伪代码或 者流程说明。 1.请设计一个字典。以字符串为索引，存储用户定义的定长结构。要求有增、删、查、改 的功能。已经给定一个函数，可以由字符串映射到一个签名，每个签名由两个 unsigned int 类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复（或者重复的概率 可以忽略），并且签名分布足够均匀。 请描述你的数据结构？内存如何申请？增、删、查、改的功能如何实现？如果操作很频繁 该如何优化？