百度笔试题目及答案(一)
第一题简答题
1.多线程和多进程模式有什么区别?在用两种模型开发服务程序时,分别有什么优缺点?采用长连接和短连接模式有什么区别?分别有什么优缺点?采用同步和异步模式有什么区别?分别有什么优缺点。
(1)启动进程的时候,操作系统会为进程分配资源,其中最主要的资源是内存空间,因为程序是在内存中运行的。在进程中,有些程序流程块是可以乱序执行的,并且这个代码块可以同时被多次执行。实际上,这样的代码块就是线程体。线程是进程中乱序执行的代码流程。当多个线程同时运行的时候,这样的执行模式成为并发执行。
对于一个进程中的多个线程来说,多个线程共享进程的内存块,当有新的线程产生的时候,操作系统不分配新的内存,而是让新线程共享原有的进程块的内存。因此,线程间的通信很容易,速度也很快。不同的进程因为处于不同的内存块,因此进程之间的通信相对困难。线程切换快,但实现稍复杂。进程易实现,较稳定,但性能与线程相比较差。
(2)所谓长连接,指在一个TCP连接上可以连续发送多个数据包,在TCP连接保持期间,如果没有数据包发送,需要双方发检测包以维持此连接,一般需要自己做在线维持。
短连接是指通信双方有数据交互时,就建立一个TCP连接,数据发送完成后,则断开此TCP连接,一般银行都使用短连接。
长连接多用于操作频繁,点对点的通讯,而且连接数不能太多情况,。每个TCP连接都需要三步握手,这需要时间,如果每个操作都是先连接,再操作的话那么处理速度会降低很多,所以每个操作完后都不断开,次处理时直接发送数据包就OK了,不用建立TCP连接。而像WEB网站的http服务一般都用短链接,因为长连接对于服务端来说会耗费一定的资源,而像WEB网站这么频繁的成千上万甚至上亿客户端的连接用短连接会更省一些资源,如果用长连接,而且同时有成千上万的用户,如果每个用户都占用一个连接的话,那可想而知吧。所以并发量大,但每个用户无需频繁操作情况下需用短连好。
(3)同步:调用方调用一个程序,等待返回,然后再继续下面的程序处理
异步: 调用方调用一个程序,不等待返回,继续执行下面的程序。
1)异步通信简单,双方时钟可允许一定误差。同步通信较复杂,双方时钟的允许误差较小。
2)通信效率:异步通信低,同步通信高。
2.请写出以下程序的运行结果,并解释导致这样运行结果的关键性原因。
#include
using std::cout;
class P
{
public:
virtual void print()
{
cout << "P";
}
};
class Q: public P
{
public:
virtual void print()
{
cout << "Q";
}
};
int main()
{
P * p = new P;
Q * q = static_cast (p);
q->print();
delete p;
cout << endl;
q = new Q;
p = q;
q->print();
p->print();
cout << endl;
p = new (q) P;
q->print();
p->print();
cout << endl;
p->~P();
delete q;
return 0;
}
P
QQ
PP
第二题 算法与程序设计题
1.给定如下的n*n的数字矩阵,每行从左到右是严格递增, 每列的数据也是严格递增
1 2 3
3 5 6
4 8 9
现在要求设计一个算法, 给定一个数k 判断出k是否在这个矩阵中。 描述算法并且给出时间复杂度(不考虑载入矩阵的消耗)
算法思想:
沿着对角线查找,获得i,使得k位于a[i][i]与a[i+1][i+1]之间。
k只可能存在于a[i][i]对应的右上角矩阵 和a[i+1][i+1]对应的左下角矩阵。
使用递归法继续查找即可。
时间复杂度 O(n)
int searchK(int int_arr[][],int n,int startlow,int startclm,int k)
{
int lefttemp=0;
int downtemp=0;
int i=0;
i++; if (i==n) return 0; else if(arr[i][i]==k) reuturn 1; else return searchK(int_arr,n,startlow,startclm+i,k)+searchK(int_arr,n,startlow+i,startclm,k); } 2.设 一个64位整型n,各个bit位是1的个数为a个. 比如7, 2进制就是 111, 所以a为3。 现在给出m个数, 求各个a的值。要求代码实现。 #include #include using namespace std; int count(long long v) { int num=0; while(v) { v &=(v-1); //执行效率为V中1的个数,时间复杂度比通过除操作、位操作比较高出很多 num++; } return num; } void main() { vector long long i; cout<<"输入需要计算的'数,Ctrl+z 停止" < while(cin>>i) { //输入随机个数的数,使用Ctrl+z 停止,之后回车键继续。 _back(i); }; for(vector { int n=count(arr[idx]); cout< } } 第三题 系统设计题 实现一个简化的搜索提示系统。给定一个包含了用户query的日志文件,对于输入的任意一个字符串s,输出以s为前缀的在日志中出现频率最高的前10条query。 由于是分布式系统,假设至少有26台机器,每个机器存储以26个字母开头的query日志文件(如机器1存的是a字母开头的,机器2存的是以b字母开头的……) 每个机器上维护着一张哈希表,对于每条query, 在哈希表表中存放其地址(哈希地址为链式的),并对其进行排序,按频率由高到低进行排序。 当用户进行搜索时,可以很快定位到某台机器,并根据哈希表,返回出现频率最高的前10条query。 提示: 1、可以预处理日志 2、假设query不超过10亿条,每个query不超过50字节。 3、考虑在大查询量的情况下如何实现分布式服务 百度笔试题目及答案(二) 一、选择题:15 分 共 10 题 1. 在排序方法中,关键码比较次数与记录地初始排列无关的是: A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序 选择 A 2. 以下多线程对 int 型变量x的操作,哪几个需要进行同步: A. x=y; B. x++; C. ++x; D. x=1; 选择 B, C 3. 代码 void func() { static int val; … } 中,变量 val 的内存地址位于: A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈 选择 A 4. 同一进程下的线程可以共享以下: A. stack B. data section C. register set D. thread ID 选择 A, B 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 选择 EG 6. short a[100],sizeof(a) 返回? A. 2 B. 4 C. 100 D. 200 E. 400 选择 D 7. 以下哪种不是基于组件的开发技术_____。 A. XPCOM B. XP C. COM D. CORBA 选择 B 8. 以下代码打印的结果是(假设运行在 i386 系列计算机上): 字串2 struct st_t { int status; short *pdata; char errstr[32]; }; st_t st[16]; char *p = (char *)( st[2]tr + 32 ); printf( "%d", ( p - (char *)(st) ) ); A. 32 B. 114 C. 120 D. 1112 选择 C,因为st[2]的起始地址比st[0]的起始地址高80位, st[2]tr的起始地址比st[2]的起始地址高8位 再加上32位就等于 120. 9. STL 中的哪种结构是连续形式的存储: A. map B. set C. list D. vector 选择 D 10. 一个栈的入栈序列是 A,B,C,D,E,则栈的不可能的输出序列是: A. EDCBA B. DECBA C. DCEAB D. ABCDE 选择 C 二、简答题:20 分,共 2 题 1. (5 分)重复多次 fclose 一个打开过一次的 FILE *fp 指针会有什么结果,并请解释。 导致 fp 所指的文件被多次释放, 导致不可预期的后果. 5. 一个B类网的子网掩码是,这个子网能拥有的最大主机数是: A. 240 B. 255 C.4094 D. 65534 6. 以下代码执行后,val的值是___: unsigned long val = 0; char a = 0x48; char b = 0x52; val = b << 8 | a; A 20992 B 21064 C 72 D 0 选择 B,b 的十进制为 82,二进制为 101,0010 b 左移 8 位为 101,0010,0000,0000 a 的十进制为 72, 二进制为 100,1000 b<<8 | a 为 21064 7. 内存的速度远远高于磁盘速度,所以为了解决这个矛盾,可以采用: 字串2 A 并行技术 B 虚存技术 C 缓冲技术 D 通道技术 9. 同一进程下的线程可以共享以下 A. stack B. data section C. register set D. thread ID 选择 B,C 10. 以下哪种操作最适合先进行排序处理? A 找最大、最小值 B 计算算术平均值 C 找中间值 D 找出现次数最多的值 选择 A 一、选择题:15 分 共 10 题 1. 在排序方法中,关键码比较次数与记录地初始排列无关的是: A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序 2. 以下多线程对 int 型变量x的操作,哪几个需要进行同步: A. x=y; B. x++; C. ++x; D. x=1; 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 系列计算机上): struct st_t { int status; short *pdata; char errstr[32]; }; st_t st[16]; char *p = (char *)( st[2]tr + 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 题
while(int_arr[startlow+i][startclm+i]