腾讯2009年校园招聘软件开发职位方向笔试试题A卷.doc

腾讯2009年校园招聘软件开发职位方向笔试试题A卷考试时长：120 分钟第一、单项选择题。（每个选项3 分，20 个选项，共60 分）1. 在一个单链表中，若p 所指的结点不是最后结点，在p 所指结点之后插入s 所指结点，则应执行操作（ ）。A. s link = p ; p link = s B. s link = p link ; p link = sC. s link = p link ; p = s D. p link = s ; s link = p2. 在下列排序方法中，不稳定的方法有（ ）。A. 归并排序与基数排序B. 插入排序与希尔排序C. 堆排序与快速排序D. 选择排序与冒泡排序3. 在多级存储体系中，“Cache-主存”结构的作用是解决（ ）的问题。A. 主存容量不足B. 辅存与CPU 速度不匹配C. 主存与辅存速度不匹配D. 主存与CPU 速度不匹配4. 在需要经常查找结点的前驱与后继的场合中，使用（ ）比较合适。A. 单链表B. 循环链表C. 链栈5. 带头结点的单链表head 为空的判断条件（ ）。A. head = NULL B. head next = NULLC. head next = head D. head <> NULL6. 将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。A. 优先队列B. 队列C. 循环队列D. 栈7. 下列描述的不是链表的优点是（ ）。A. 逻辑上相邻的结点物理上不必邻接B. 插入、删除运算操作方便，不必移动结点C. 所需存储空间比线性表节省D. 无需事先估计存储空间的大小8. SQL 语言集数据查询、数据操作、数据定义和数据控制功能于一体，语句INSERT、DELETE、UPDATE 实现（ ）功能。A. 数据查询B. 数据控制C. 数据定义D. 数据操作9. 设某种二叉树有如下特点：每个结点要么是叶子结点，要么有2 棵子树。如果一棵这样的二叉树中有m（m>0）个叶子结点，那么该二叉树上的结点总数为（ ）。A. 2m+1 B. 2m-1 C. 2(m-1) D. 2m10. TCP/IP 协议栈的网络层的主要功能是通过（ ）来完成的。A. IP 协议B. TCP 协议C. 以太网协议D. IGP 协议11. 实现不同的作业处理方式（如：批处理、分时处理、实时处理等），主要是基于操作系统对（ ）管理采取了不同的策略。A. 处理机B. 存储C. 数据库D. 文件12. 下面关于编译系统和解释系统的观点中，错误的是（ ）。A. 解释程序不产生目标代码，它直接执行源程序或源程序的内部形式B. 使用编译系统时会区分编译阶段和运行阶段C. 一般来说，解释系统比编译系统复杂，但是可移植性好D. 一般来说，建立在编译基础上的系统在执行速度上要优于建立在解释执行基础上的系统13. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的（ ）方法是散列文件的关键。A. 散列函数B. 除余法中的质数C. 冲突处理D. 散列函数和冲突处理14. 衡量查找算法效率的主要标准是（ ）。A. 元素个数B. 所需的存储量C. 平均查找长度D. 算法难易程度15. 对于#include <filename.h>和#include “filename.h”，以下说法错误的是（ ）。A. #include <filename.h>只搜索标准库路径B. #include “filename.h”只搜索用户工作路径C. #include <filename.h>搜索范围比#include “filename.h”小D. 两者可能等价16. 类定义的外部，可以被访问的成员有（ ）。A. 所有类成员B. private 或protected 的类成员C. public 的类成员D. public 或private 的类成员17. 下列的模板说明中，正确的有（ ）（ 两个答案）。A. template <typename T1， typename T2> B. template <class T1, T2>C. template <class T1, class T2> D. template <typename T1; typename T2>18. 中断响应时间是指（ ）。A. 从中断处理开始到中断处理结束所用的时间B. 从发出中断请求到中断处理结束所用的时间C. 从发出中断请求到进入中断处理所用的时间D. 从中断处理结束到再次中断请求的时间19. （ ）面向对象程序设计语言不同于其他语言的主要特点。A. 继承性B. 消息传递C. 多态性D. 封装性20. TCP/IP 模型的体系结构中，ICMP 协议属于（ ）。A. 应用层B. 网络层C. 数据链路层D. 传输层第二、填空题。（每空4 分，总计40 分）1. 阅读下列说明和流程图，将应填入（n）的字句写在答题纸的对应栏内。【说明】正弦函数可以用如下的泰勒级数展开式来计算： 下面的流程图描述了利用上述展开式计算并打印sin (x )的近似值的过程，其中用>0）表示误差要求，小于该误差即可结束计算，打印结果。【流程图】2. 阅读下列函数说明和C 代码，将应填入（n）处的字句写在答题纸的对应栏内。【说明】设有一个带表头结点的双向循环链表L,每个结点有4 个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data 和访问频度freq。所有结点的freq 初始时都为0.每当在链表上进行一次L.Locate（x）操作时，令元素值x 的结点的访问频度freq 加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。【函数】void Locate(int &x) <结点类型说明>*p=first->next;while(p!=first && 1 ) p=p->next;if (p!=first) 2 ;<结点类型说明>*current=p;current->prior->next=current->next;current->next->prior=current->prior;p=current->prior;while(p!=first && 3 ) p=p->prior;current->next= 4 ;current->prior=p;p->next->prior=current;p->next= 5 ;elseprintf(“Sorry. Not find!n”); *没找到*第三、附加题（30 分）“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S,设有N 件物品，其重量分别为w1，w2，wn，希望从N 件物品中选择若干物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。递归和非递归解法都能求得“背包问题”的一组解，试写出“背包问题”的非递归解法。腾讯笔试题目zz1、请定义一个宏，比较两个数a、b 的大小，不能使用大于、小于、if 语句2、如何输出源文件的标题和目前执行行的行数3、两个数相乘，小数点后位数没有限制，请写一个高精度算法4、写一个病毒5、有A、B、C、D 四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时1、2、5、10分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在17 分钟内这四个人都过桥？2.如何输出源文件的标题和目前执行行的行数（不晓得怎么搞，在等兄弟给我答案在！）3.两个数相乘，小数点后位数没有限制，请写一个高精度算法算法提示：/想法来自北师大一个同学给我看的另一个题目以及他的java 程序。输入string a, string b； 计算string c=a*b; 返回c;1， 纪录小数点在a,b 中的位置l1,l2， 则需要小数点后移动位置数为l=length(a)+length(b)-l1-l2-2;2， 去掉a,b 中的小数点，（a,b 小数点后移，使a,b 变为整数）3， 计算c=a*b; （要么用java 的BigInterger 搞, 要么自己用C+写高精度数乘法，超过百万位，用FFT,我就不细说，这都预先写过就别做了）4， 输出c,（注意在输出倒数第l 个数时，输出一个小数点。若是输出的数少于l 个，就补0）4.写一个病毒(没搞过，_)5.让你在100000000 个浮点数中找出最大的10000 个，要求时间复杂度优。/本算法使用快排，O(n*lg(n)/最低可以找到线性算法，使用预先区域统计划分！类试于构造Quad Trees! 写起来代码会长些！#include <stdio.h>#include <stdlib.h>#define Max 100000000int aMax+10;int cmp(const void *a, const void *b)int *x = (int *) a;int *y = (int *) b;return *x-*y;int main()int n=0;while(scanf("%d",&an)=1) n+;qsort(a,n,4,cmp);for(int i=0;i<3;i+) printf("%d",a);return 1;5、有A、B、C、D 四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时1、2、5、10分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在17 分钟内这四个人都过桥？Solution:The First Time： A(1)和B(2)过桥，A(1)返回Cost：1+2The Second Time： C(5)和D(10)过桥，B(2)返回Cost：10+2The Third Time A(1)和B(2)过桥Cost：2Total Time Cost： (1+2)+(10+2)+2=17 minutes1、请定义一个宏，比较两个数a、b 的大小，不能使用大于、小于、if 语句#define Max(a,b) ( a/b)?a:b2、如何输出源文件的标题和目前执行行的行数int line = _LINE_;char *file = _FILE_;cout<<"file name is "<<(file)<<",line is "<3、两个数相乘，小数点后位数没有限制，请写一个高精度算法4、写一个病毒while (1)int *p = new int10000000;5、不使用额外空间,将A,B 两链表的元素交*归并6、将树序列化转存在数组或链表中struct stint i;short s;char c;sizeof(struct st);7、char * p1;void * p2;int p3;char p410;sizeof(p1.p4) =?8、4，4，4，10二分查找快速排序双向链表的删除结点。