【笔试真题】网易2013年题目(附答案)(1).pdf

1、一:给了一个用递归实现的快排的代码,要求改写成用栈实现的/*快速排序的非递归实现*/int partition(int a,int left,int right)if(a=NULL)return-1;if(left=right)return-1;int X=aleft;int i=left;int j=right;while(i j)while(i=X)j-；if(i j)ai+=aj;while(i j&ai X)i+；if(i j)aj-=ai;ai=X;return i;void quick_sort2(int a,int left,int right)stack s;int mid=p

2、artition(a,left,right);if(mid=-1)return;if(left mid-1)s.push(left);s.push(mid-1);if(mid+1 right)s.push(mid+1);s.push(right);while(!s.empty)int r=s.top();s.pop()int l=s.top();s.pop();mid=partition(a,l,r);if(mid=-1)return;if(l mid-1)s.push(l);s.push(mid-1);if(mid+1 r)s.push(mid+1);s.push(r);二:游戏中让玩家参与

3、抽奖,抽装备.玩家先被等概率传送到十二个房间(对应十二星座),第i个房间中拿到装备的概率是 i/50.玩家抽奖失败后可以花 100 金币再抽一次(第一次不用),如果抽中了则不能再抽.先是问要抽到装备平均要花多少金币;又问:玩家不喜欢传到 12 个不同房间的设定,现在要求只能传到一个房间,这个房间提供有 12 种装备,要求每种装备被抽中的概率和之前的一样.就此实现一个生成随机数的算法.三:先是给出了 P,V 原语及信号量的定义,然后有一个场景:一个水果忍者不停的往一个篮子中捡水果,水果有西瓜和梨两种,篮子最多装 10 个水果,装不了就等待.同时鸣人和佐助分别从篮子中拿西瓜和梨吃,只要有的吃就拿,

4、否则就等待.用 PV 原语 写一段伪代码模拟这个过程.Semaphore empty=10;/篮子里空位的个数Semaphore watermelon=0,pear=0;Semaphore mutex=1;int fruits=0;ninja()P(mutex);P(empty);if(rand()%2)V(watermelon);elseV(pear);V(mutex);naruto()P(mutex);P(watermelon);V(empty);V(mutex);sasuke()P(mutex);P(pear);V(empty);V(mutex);四:给出了跳表的结构,要求实现一个跳表上

5、的查询操作 search(k),然后分析 search 的时间复杂度.最后再写一个 insert()的操作.五:有 N 个广告牌(N=10 万)可以投放广告,有 k 个用户(k10 亿)在这些广告牌上投放广告.操作rent(i,j,k)将从 i 到 j 块 广告牌展示用户 k 的广告,如果原来有别的广告就覆盖掉.操作 query(i)返回第 i 个广告牌上现在投放的是哪个广告.rent 和 query 操作出现的频率相等.要求设计一个数据结构和相应的算法,尽可能快的实现这两种操作.六:给出了一段英文文献,是关于 code block 的,然后要求根据文献中给出的算法写一段代码.要用到 STL.

6、七:判定给定的字符串序列是否是人类基因片段，人类基因片段的特点是：大写字母后边跟相应小写字母，或者是小的基因片段连在一起。写函数判断。1.LRU 算法最少使用页面置换算法。LRU 算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。因此，我们只需要在每次调换时，找到最少使用的那个页面调出内存。这就是 LRU 算法的全部内容。2，在 c+中调用 c 函数extern C/函数声明3，用 typedef 声明函数指针typedef (*)(参数表)typedef void(*PF)(

7、int x);void func1(int x);PF pFunc;/声明一个函数指针只需要用 PF 类型名pFunc=func1;/此处也可以使用 pFunc=&func1;4，程序内存分配的方式内存分配方式有三种：1 从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static 变量。2 在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。3 从堆上分配，亦称动态内存分配。程序在运行的时候用 malloc 或

8、new 申请任意多少的内存，程序员自己负责在何时用 free 或 delete 释放内存。动态内存的生存期由程序员决定，使用非常灵活，但如果在堆上分配了空间，就有责任回收它，否则运行的程序会出现内存泄漏，频繁地分配和释放不同大小的堆空间将会产生堆内碎块。1.变量在内存地址的分布为：堆-栈-代码区-全局静态-常量数据2.同一区域的各变量按声明的顺序在内存的中依次由低到高分配空间（只有未赋值的全局变量是个例外）。3.全局变量和静态变量如果不赋值，默认为 0。栈中的变量如果不赋值，则是一个随机的数据。4.编译器会认为全局变量和静态变量是等同的，已初始化的全局变量和静态变量分配在一起，未初始化的全局变

9、量和静态变量分配在另一起。5.主函数中栈的地址都要高于子函数中参数及栈地址，证明了栈的伸展方向是由高地址向低地址扩展的。5，进程和线程的内存共享，堆和栈哪个公有哪个私有代码区、全局数据区、堆区是各线程公有的，栈区是各线程独立的。6，库函数调用是否跟操作系统有关无关7，内核态和什么态，系统调用时的上下文切换8，tcp/ip 协议中哪些协议属于网络层IP，ICMP，OSPF，EIGRP，IGMP，RIP，ARP，RARP 等9,给一段程序找 bug10，进程和线程之间的通信方式进程间的通信方式：1.管道（pipe）及有名管道（named pipe）：管道可用于具有亲缘关系的父子进程间的通信，有名管

10、道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。2.信号（signal）：信号是在软件层次上对中断机制的一种模拟，它是比较复杂的通信方式，用于通知进程有某事件发生，一个进程收到一个信号与处理器收到一个中断请求效果上可以说是一致的。3.消息队列（message queue）：消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息。4.共享内存（shared memory）：可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到

11、对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。5.信号量（semaphore）：主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段。6.套接字（socket）；这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。线程之间的同步通信：1.信号量 二进制信号量 互斥信号量 整数型信号量 记录型信号量2.消息 消息队列 消息邮箱3.事件 event11，结构体的 size-内存对齐问题32 位系统默认是 4 字节对齐，64 位系统默认是 8 字节对齐12，几道概率题，包括一个电路问题，一个租自行车的分布13，算一个最小

12、生成树的权重图的遍历14，图的存储方式邻接矩阵、邻接表、十字链表、邻接多重表15，满 k 叉树第 k 层第一个结点的编号k(k-1)16，对一个顺序数组,冒泡,堆排序,快排,归并,最快和最慢冒泡 O(n2)，快排 O(nlogn)，归并 O(nlogn)，堆排序 O(nlogn)17，构造和析构函数，T*p=new Tn;delete p;T 的构造函数和析构函数各有一个输出信息,问程序执行后输出什么18，一个满二叉树,知道前序遍历结果,求后续遍历结果1、对于一个内存地址是 32 位、内存页是 8KB 的系统。0X0005F123 这个地址的页号与页内偏移分别是多少。页面大小是 8KB，那么页

13、内偏移量是从 0 x0000（0）0 x1FFF（2 的 13 次方-1）。0 x5F123/8K=2E，余数是 1123；则页号是 47 页，页内偏移量应该是 0X00001123。2、如果 X 大于 0 并小于 65536，用移位法计算 X 乘以 255 的值为：(X8)-X。X8-X 是不对的是不对的，因为移位运算符的优先级没有减号的优先级高因为移位运算符的优先级没有减号的优先级高，首先计算首先计算 8-X 为为 0，X 左移左移 0 位还是位还是 8。3、一个包含 n 个节点的四叉树，每个节点都有四个指向孩子节点的指针，这 4n 个指针中有 _个空指针。n 个节点的二叉树，一共有 2n

14、 个指针，n-1 个非空指针，故空指针为 2n-(n-1)个同理 n 个节点的四叉树，一共有 4n 个指针，n-1 个非空指针，故空指针为 4n-(n-1)个4、以下两个语句的区别是：第一个动态申请的空间里面的值是随机值，第二个进行了初始化，里面的值为 05、计算机在内存中存储数据时使用了大、小端模式，请分别写出 A=0X123456 在不同情况下的首字节大端模式：0X12小端模式：0X56X86 结构的计算机使用 小端小端模式。一般来说，大部分用户的操作系统（如 windows,FreeBsd,Linux）是小端模式的。少部分，如 MAC OS，是大端模式 的。6、在游戏设计中，经常会根据不

15、同的游戏状态调用不同的函数，我们可以通过函数指针来实现这一功能，请声明一个参数为 int*，返回值为 int 的函数指针：int(*func)(int*)7、下面程序运行后的结果为：result is to test something8、在一冒险游戏里，你见到一个宝箱，身上有 N 把钥匙，其中一把可以打开宝箱，假如没有任何提示，随机尝试，问：(1)恰好第 K 次（1=K=N）打开宝箱的概率是多少。(N-1)/N*(N-2)/(N-1)*(N-3)/(N-2)*1/2=1/N(2)平均需要尝试多少次。1/N*1+1/N*2+1/N*N=(N+1)/29、头文件中 ifndef/define/e

16、ndif 是做什么用的？防止头文件重复包含以及防止变量被重复定义10、代码里有时可以看到 extern“C”，这语句是做什么用的？C 和 C+对函数的处理方式是不同的，extern C是使 C+能够调用 C 写作的库文件的一个手段，如果要对编译器提示使用 C 的方式来处理函数的话，那么就要使用 extern C来说明。11、平均要取多少个(0，1)中的随机数才能让和超过 1。12、在下列乘法算式中，每个字母代表 09 的一个数字，而且不同的字母代表不同的数字：ABCDEFGH*AJ-EJAHFDGKCBDFHAJEC-CCCCCCCCC请写出推导的过程。本题唯一解为：A=2、B=4、C=6、D=9、E=1、F=3、G=5、H=8、J=7、K=01 1、2424 小时内，表的时针、分针、秒针完全重合多少次？分别是什么时刻。小时内，表的时针、分针、秒针完全重合多少次？分别是什么时刻。设时针的角速度是（=/6 每小时），则分针的角速度为 12，秒针的角速度为 720。分针与时针再次重合的时间为 t，则有 12t-t=2，t=12/11 小时分针与秒针再次重合的时间为 t，则有 720t-12