深信服 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，求所有的出栈顺序（看成全排列了，要排除一些情况）