/|\\ /\\ | | / \\ / | \\
6 5 7 8 9 10 10 9 8 7 5 6
答：以孩子、兄弟的存储结构来存储这棵树，使之成为一颗二叉树，然后对二叉树进行链表的转换。 typedef struct TreeNode {
int data;
struct TreeNode *firstchild; struct TreeNode *nextsibling; }TreeNode,*Tree; void MirrorTree(Tree root) {
if(!root) return ; if(root->firstchild) {
Tree p=root->firstchild; Tree cur=p->nextsibling; p->nextsibling=NULL; while(cur) {
Tree curnext=cur->nextsibling; cur->nextsibling=p; if(p->firstchild) MirrorTree(p); p=cur; cur=curnext; }
root->firstchild=p; } }
int main(void) {
TreeNode *root=(TreeNode *)malloc(sizeof(TreeNode)); Init();
MirrorTree(root); OutPut(); }
2、假设某个网站每天有超过10亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的ip地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间段内的区域ip地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢，设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？
答：用B+树来组织，非叶子节点存储（某个时间点，页面访问量），叶子节点是访问的IP地址。这个方案的优点是查询某个时间段内的IP访问量很快，但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。答：或者可以建立二级索引，分别是时间和地点来建立索引。 四、附加题
1、写出C语言的地址对齐宏ALIGN（PALGNBYTES），其中P是要对齐的地址，ALIGNBYTES是要对齐的字节数（2的N次方），比如说：ALIGN(13,16)=16
ALIGN(P,ALIGNBYTES) ( (void*)( ((unsigned long)P+ALIGNBYTES-1)&~(ALIGNBYTES-1) ) ) 2、在高性能服务器的代码中经常会看到类似这样的代码： typedef union {
erts_smp_rwmtx_t rwmtx;
byte cache_line_align_[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(erts_smp_rwmtx_t))]; }erts_meta_main_tab_lock_t;
erts_meta_main_tab_lock_t main_tab_lock[16]; 请问其中用来填充的cache_line_align的作用是？
3、在现代web服务系统的设计中，为了减轻源站的压力，通常采用分布式缓存技术，其原理如下图所示，前端的分配器将针对不同内容的用户请求分配给不同的缓存服务器向用户提供服务。 分配器 / | \\
缓存缓存 ...缓存
服务器1 服务器2 ...服务器n
1）请问如何设置分配策略，可以保证充分利用每个缓存服务器的存储空间（每个内容只在一个缓存服务器有副本）
2）当部分缓存服务器故障，或是因为系统扩容，导致缓存服务器的数量动态减少或增加时，你的分配策略是否可以保证较小的缓存文件重分配的开销，如果不能，如何改进？
3）当各个缓存服务器的存储空间存在差异时（如有4个缓存服务器，存储空间比为4：9：15：7），如何改进你的策略，按照如上的比例将内容调度到缓存服务器？
淘宝笔经3 一共有五部分。 一、选择题
1、排序算法的时间复杂度与初始序列无关的是哪一种？
2、考查多继承、多态性之类的概念。（问题大概是？表明一种操作可以有多个类实现之类的） 3、前序遍历和中序遍历——>后续遍历 4、二分插入，求比较次数。
5、Cache调度算法平均命中率最高的是？ 6、编译原理的题目（类似中间代码的作用）
7、概率题（貌似只有这7题，又感觉漏了一题，想不起来了） 二、填空题
1、一个算式：两个数相乘等于一个数，问这些数几进制表示的。 2、排序算法（从大到小），求比较次数。
3、（C语言）看代码写结果，关于字母大小写转化的。
4、（Java语言）看代码写结果，关于++、--的利用，m++、++m等等，之后输出m的值。 5、非递归的的二分排序，补充代码。 三、简答题
1、大概是淘宝有一亿会员，淘宝抽出其中100万会员给其发消息等等的，写出自己想到的抽取的方法，必须体现公平性、分散性、每个都能被抽到的可能等等
2、编程。用Java或者C/C++写一个方法，实现输入字符串转化为Int型 四、附加题
关于数据结构和查询方法的 五、不计分题
作为一个热爱技术的你，说说各种之类。说说自己擅长的技术、说说自己经常使用的语言的架构、设计模式啊等等的还有什么最新的技术啊类似的
淘宝笔经4 选择
1、二维数组按行优先存储，A[2][3]的地址是1087，A[4][7]的地址是1153，请问A[6][7]的地址是多少？ 2、实施软件需求时，常用工具应包括那些？（每个选项都是两个，具体的就不记得了） 3、单元测试通常采用方法？ 4、二分法检索表用什么存储？ 简答
5、进程模型和线程模型有哪些优缺点 程序
6、二分查找的非递归算法 C++部分
1、下面程序运行的结果？ int i = 0, s = 0; for(;;) {
if(i == 3 || i == 5) continue; if(i == 6) break; i ++; s += i; }
cout << s << endl;
2、虚析构函数的作用？举例。 3、什么时候调用拷贝构造函数？ 4、语句int* ptr; *ptr = 10; 有问题吗？ 5、
int a[3][2] = {1, 2, 3, 4, 5, 6}; int *p[3]; p[0] = a[1];
*(p[0] + 1)指向的内容是多少？ 6、请写出下面语句的输出 char str1[] = \char str2[] = \const char str3[] = \const char str4[] = \const char* str5 = \const char* str6 = \
cout << (str1 == str2) << endl; //true or false cout << (str3 == str4) << endl; cout << (str5 == str6) << endl;
网易笔经1
首先研发的笔试是分两部分的,第一部分是30道填空和选择,第二部分是7道大题. 前面的小题说是过了线就行,不参与成绩评定和排名,但是如果不过线那后边的题就不给判. 只有后面的大题算笔试成绩的. 然后这个笔试的最大特点就是:题量超大,我觉得除非大牛否则很难做完.反正我最后一道大题是没时间写. 而且前面的小题部分考察的东西既广又深,感觉非常琐碎,所以我做的时候非常担心自己第一部分就会挂掉...不过还好没有.所以我先把第二部分几道大题发出来
一: 给了一个用递归实现的快排的代码,要求改写成用栈实现的
二:游戏中让玩家参与抽奖,抽装备.玩家先被等概率传送到十二个房间(对应十二星座),第i个房间中拿到装备的概率是i/50. 玩家抽奖失败后可以花100金币再抽一次(第一次不用),如果抽中了则不能再抽. 先是问要抽到装备平均要花多少金币; 又问:玩家不喜欢传到12个不同房间的设定,现在要求只能传到一个房间,这个房间提供有12种装备,要求每种装备被抽中的概率和之前的一样.就此实现一个生成随机数的算法. 三:先是给出了P,V原语及信号量的定义,然后有一个场景:一个水果忍者不停的往一个篮子中捡水果,水果有西瓜和梨两种,篮子最多装10个水果,装了了就等待.同时鸣人和佐助分别从篮子中拿西瓜和梨吃,只要有的吃就拿,否则就等待.用PV原语写一段伪代码模拟这个过程.
四:给出了跳表的结构,要求实现一个跳表上的查询操作search(k),然后分析search的时间复杂度. 最后再写一个insert()的操作.
五:有N个广告牌(N<=10万)可以投放广告,有k个用户(k<10亿)在这些广告牌上投放广告.操作rent(i,j,k)将从i到j块广告牌展示用户k的广告,如果原来有别的广告就覆盖掉. 操作query(i)返回第i个广告牌上现在投放的是哪个广告. rent和query操作出现的频率相等.要求设计一个数据结构和相应的算法,尽可能快的实现这两种操作.
六:给出了一段英文文献,是关于code block的, 然后要求根据文献中给出的算法写一段代码. 要用到STL. 七:判定给定的字符串序列是否是人类基因片段，人类基因片段的特点是：大写字母后边跟相应小写字母，或者是小的基因片段连在一起。写函数判断。
网易笔经2
第一部分(必做): 计算机科学基础
1. (单选)软件设计中模块划分应该遵循的准则是:
A.低内聚低耦合 B.高内聚低耦合 C.低内聚高耦合 D.高内聚高耦合 2. (单选)最坏情况下时间复杂度不是n(n-1)/2的排序算法是: A.快速排序 B.冒泡排序 C.直接插入排序 D.堆排序
3. 哈希表中解决冲突的方法通常可以分为open addressing和chaining两类, 请分别解释这两类冲突解决方法的大致实现原理
4. 简单的链表结构拥有很好的插入删除节点性能, 但随机定位(获取链表第个节点)操作性能不佳, 请你设计一种改进型的链表结构优化随机定位操作的性能, 给出设计思路及其改进后随机定位操作的时间复杂度 5. 什么是NP问题?列举典型的NP问题(至少两个)?对于一个给定的问题你通常如何判断它是否为NP问题?
6. 以下是一个tree的遍历算法, queue是FIFO队列, 请参考下面的tree, 选择正确的输出. 1 / \\ 2 3 / \\ / \\ 4 5 6 7
queue.push(tree.root) while(true){ node=queue.pop();
output(node.value);//输出节点对应数字 if(null==node) break;
for(child_node in node.children){ queue.push(child_node); } }
A. 1234567 B. 1245367 C. 1376254 D. 1327654
第二部分(选作): C/C++程序设计
1. 有三个类A B C定义如下, 请确定sizeof(A) sizeof(B) sizeof(C)的大小顺序, 并给出理由 struct A{ A() {} ~A() {} int m1; int m2; }; struct B{ B() {} ~B() {} int m1; char m2; static char m3; }; struct C{