深信服 9-15笔试 C卷
15题填空，4道编程
填空
填空比较基础，考察了数据结构（队列，二叉树），和简单编程，二进制等。
1、1 2 3 4 5 入队，然后队首弹出，6 7 8 9 10 入队，然后队首弹出，11 12 13 14 15 入队，然后队首弹出
最后求队首到队尾： 4 5 6 7 8 9 10 11 12 13 14 15
2、求阶乘和x，补全代码
int x = 0;
int y = 1;
int z = 1;
while (z < n) {
y = y * z; // 补全
x = x + y; // 补全
z ++;
}
3、给了一种表示二叉树节点的4元组，最后画出二叉树找距离根节点最远的节点（每个节点直接有距离）
4、给后序遍历和二叉树的图（上面只有节点，没有信息）求中序遍历
5、找16以内的二进制回文数（转成二进制后是回文二进制的数）
6、缓冲区满了以后，新的数据覆盖旧的数据是什么队列（双向队列or循环队列）感觉应该是循环，我当时想到LRU实现去了。
7、逻辑推理题，这个国家有两种人，在平原上的只说真话，在山里的只说假话。但是你不懂他们的语言，你只知道G和M表示 是或者不是
你给三个人提了2个问题：
1.其他两人是平原人
2.其他两人是山里人
除了第一个人回答第二个问题回答的是M，其他回答均为G
问G表示什么 ：不是
8、在一个排序的链表里插入一个数，并保存顺序，时间复杂度是多少。
O（n）或者 二分？ O（logn）
9、5个人ABCDE，他们参加选举投票，一人一票，然后围着坐（按abcde的顺序，顺时针），他们投票会投给投给他们的人的左边的人，最后没人当选，求他们投给了谁
A -> D B -> E
C -> A D -> B
E -> C
10、入队：1234，求出队：1234
11、在一个链表的节点p的后面插入，一个新的节点n的指针操作是什么?
n.next = p.next
p.next = n
n.next.pre = n;
12、平衡二叉树插入一个新的后，问改变后的二叉树的节点的左右孩子是什么。
13、给了一个代码，是两个递归的函数，互相递归，求指定函数的结果。
14、找规律
15、忘了
编程题
1、给一个字符串找有多少种病毒，如aa有1个（重复的不算），ab 有3个 [a, b, ab]，同理, abc有7个
思路：读入后统计不重复的字母，然后2的n次方-1就是答案。
2、走迷宫，迷宫0不能走，其他可以走，数字表示该点的金币，从左上走到右下角，但是有一次魔法，可以将不能走的变成金币为0的可以走的路，求最多拿到的金币。
3、翻译加密，给一个原串 1 2 3 4 5，然后先倒序 5 4 3 2 1，然后再打乱顺序排成一个数组一行， 前面表示这个数，后面表示下一个数在第几行，提示用链表，最后输出原串。
如
5 2
4 3
3 5
1 0
2 4
4、给一个字符串，如abc，求所有的出栈顺序（看成全排列了，要排除一些情况）