2014年百度校园招聘南京站PC客户端开发笔试题

2014 年百度校园招聘南京站 PC 客户端开发笔试题 一、问答题：50 分 1、写出 new 和 malloc、delete 和 free 的区别 从面向对象来说，new/delete 和 malloc/free 的区别是：malloc/free 只是 单纯的进行内存空间的分配和释放，而使用 new/delete 时，不仅分配了内存空间， 若 new/delete 的是一个类，还会调用类(经测试，基本类型好像不会进行默认初始 化)的构造函数或析构函数。 简单来说，两者的区别主要有： 1. malloc 与 free 是 C++/C 语言的标准库函数，new/delete 是 C++的运 算符，与”+“、”-“、”*“、”/“有一样的地位。 2. new/delete 是可以重载的，而重载之后，就成为了函数。 3. malloc 在申请内存的时候，必须要提供申请的长度，而且返回的指针是 void*型，必须要强转成需要的类型。 4. 当 new/delete 在类中被重载的时候，可以自定义申请过程，比如记录所申 请内存的总长度，以及跟踪每个对象的指针。 5. new/delete，其实内部也调用了 malloc/free。 两者的共同点有： 1. 都必须配对使用，防止内存泄露。 2. 都可用于申请动态内存和释放内存，都是在堆中分配内存。 3. free 和 delete 可以释放 NULL 指针。 2、写两个继承类，解释虚表指针和虚表的作用 每一个类都有虚表。 虚表可以继承，如果子类没有重写虚函数，那么子类虚表中仍然会有该函数的 地址，只不过这个地址指向的是基类的虚函数实现。如果基类有 3 个虚函数，那么 基类的虚表中就有三项(虚函数地址)，派生类也会有虚表，至少有三项，如果重写了 相应的虚函数，那么虚表中的地址就会改变，指向自身的虚函数实现。如果派生类 有自己的虚函数，那么虚表中就会添加该项。 派生类的虚表中虚函数地址的排列顺序和基类的虚表中虚函数地址排列顺序相 同。 3、写出 static 的用法和作用 static 是 C++中很常用的修饰符，它被用来控制变量的存储方式和可见性。函 数内部定义的变量，在程序执行到它的定义处时，编译器为它在 栈上分配空间，大家知道，函数在栈上分配的空间在此函数执行结束时会释放 掉，这样就产生了一个问题: 如果想将函数中此变量的值保存至 下一次调用时，如何实现? 最容易想到的方法是定义一个全局的变量，但定义为 一个全局变量有许多缺点，最明显的缺点是破坏了此变量的 访问范围(使得在此函数中定义的变量，不仅仅受此函数控制)。 需要一个数据 对象为整个类而非某个对象服务,同时又力求不破坏类的封装 性,即要求此成员隐藏在类的内部，对外不可见。 4、写出计算机的存储器层次，及原因 以处理器为中心，计算机系统的存储依次为寄存器、高速缓存、主存储器、磁 盘缓存、磁盘和可移动存储介质等 7 个层次。距离处理器越近的存储工作速度越高， 容量越小。其中，寄存器、高速缓存、主存储器为操作系统存储管理的管辖范围， 磁盘和可移动存储介质属于操作系统设备管理的管辖范围。 5、写出对 windows 中的句柄的理解 所谓句柄实际上是一个数据，是一个 Long (整长型)的数据。 句柄是 WONDOWS 用来标识被应用程序所建立或使用的对象的唯一整数， WINDOWS 使用各种各样的句柄标识诸如应用程序实例，窗口，控制，位图，GDI 对象等等。WINDOWS 句柄有点象 C 语言中的文件句柄。 二、算法题：30 分 1、计算字符串的相似度-《编程之美》3.3 int calStringDis(string strA, int pABegin,int pAEnd,string strB, int pBBegin,int pBEnd) { if (pABegin > pAEnd) { if (pBBegin > pBEnd) return 0; else return pBEnd – pBBegin + 1; } if (pBBegin > pBEnd) { if(pABegin > pAEnd) return 0; else return pAEnd – pABegin + 1; } if (strA[pABegin] == strB[pBBegin]) { return calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd); } else { int t1 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+2,pBEnd); int t2 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+1,pBEnd); int t3 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+2,pBEnd); return minValue(t1,t2,t3)+1; } } 2、判断链表是否存在闭环 //using step1 and step2 here //if exists a loop, then the pointer which use step2 will catch up with the pointer which uses step1 int HasLoop(LinkList L) { int step1 = 1; int step2 = 2; LinkList p = L; LinkList q = L; //while (p != NULL && q != NULL && q->next == NULL) while (p != NULL && q != NULL && q->next != NULL) { p = p->next; if (q->next != NULL) q = q->next->next; printf("p:%d, q:%d n", p->data, q->data); if (p == q) return 1; } return 0; } 三、系统设计题：选做一题 20 分 1、连连看游戏中，写出两种算法的大致原理，来判断两个图案是否能够连线。 并详细解释，写出其中一个算法的伪代码。 2、解释 延迟过程调用 deferred procedure call (DPC) 和异步过程调用 asynchronous procdure call (APC) 的工作机制。详细描述利用 APC 实现 DLL 注入。