牛客网模拟笔试（三月场）

上周参加了牛客网的模拟笔试（三月场），后面因为有事情就没有做编程题目，想来挺后悔的。然后编程题的题解是牛客网提供的题解~目前还没有开放做题权限，所以蚊子也不能补题，嘤~

选择题

1.若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用()遍历方法最合适 C

A 前序
B 中序
C 后序
D 按层次

解析：

用二叉链表存储结构也就是左孩子右兄弟的存储结构。后序遍历比较合理。正常的逻辑应该就是：做好当前结点子树内部的交换，然后交换当前结点的左右子树。刚好符合后序遍历的算法逻辑。

1. 交换好左子树
2. 交换好右子树
3. 交换左子树与右子树

2.链表不具备的特点是（ ）A

A 可随机访问任何一个元素
B 插入、删除操作不需要移动元素
C 无需事先估计存储空间大小
D 所需存储空间与线性表长度成正比

3.下列关于栈的叙述正确的是（）D

A 栈是非线性结构
B 栈是一种树状结构
C 栈具有先进先出的特征
D 栈有后进先出的特征

4.某棵完全二叉树上有698个节点，则该二叉树的叶子节点数为 A

A 349
B 350
C 255
D 351

解析：

树是完全二叉树，根据树有698个节点可判断出树有10层，前9层节点总数为2^9-1=511，所以第10层节点数为 698-511 = 187

所以最后一层的节点数是187，所以第9层有93个度为2的节点和1个度为1的节点，共94个，

所以第9层还会有 256-94 = 162 个叶子节点

叶子节点总数：187 + 162 = 349

5.输入若已经是排好序的，下列排序算法最快的是（） A

A 插入排序
B Shell排序
C 合并排序
D 快速排序

解析：

快速排序在元素基本无序的情况下是最好的选择，在基本递增或递减中时间复杂度是O(n^2)

归并排序时间复杂度稳定在O(nlogn)

希尔排序很难说，跟选择的增量有关，一般小于O(n^2)，大于O(n)

插入排序是在序列已有序的情况下最快的，时间复杂度是O(n)，另外在数数据规模较小时插入排序效果也很好。

一般不选择传统的冒泡排序，如果题目中有一个选项是冒泡排序，要想一下是否隐含着改进冒泡排序的含义。

6.在网络7层协议中，如果想使用UDP协议达到TCP协议的效果,可以在哪层做文章? C

A 应用层
B 表示层
C 会话层
D 传输层
E 网络层

解析：

因为UDP要达到TCP的功能就必须实现拥塞控制的功能,而且是在路由之间实现,这个在底层明显是做不到拥塞控制的,在应用层也是做不到的,因为应用层之间和应用程序挂钩,一般只能操控主机的程序,而表示层是处理所有与数据表示及运输有关的问题，包括转换、加密和压缩,在传输层是不可能的,因为你已经使用了UDP协议,无法在本层转换它,只有在会话层.

会话层（SESSION LAYER）允许不同机器上的用户之间建立会话关系。会话层循序进行类似的 传输层 的普通数据的传送，在某些场合还提供了一些有用的增强型服务。允许用户利用一次会话在远端的分时系统上登陆，或者在两台机器间传递文件。 会话层提供的服务之一是管理对话控制。会话层允许信息同时双向传输，或任一时刻只能单向传输。如果属于后者，类似于物理信道上的半双工模式，会话层将记录此时该轮到哪一方

7.主机甲和乙已建立了 TCP 连接,甲始终以 MSS=1KB 大小的段发送数据,并一直有数据 发送;乙每收到一个数据段都会发出一个接收窗口为 10KB 的确认段。若甲在 t 时刻发生超 时时拥塞窗口为 8KB,则从 t 时刻起,不再发生超时的情况下,经过 10 个 RTT 后,甲的发送窗口是() A

A 10KB
B 12KB
C 14KB
D 15KB

解析：

TCP当中的拥塞控制算法，慢开始门限设置为出现拥塞时的发送窗口大小的一半。因此发生拥塞时候，慢开始门限设置为8/2=4， 然后把拥塞窗口设置为 1 ，执行慢开始算法。 当然收到单个确认但此确认多个数据报的时候就加相应的数值。所以一次传输轮次之后拥塞窗口就加倍。这就是乘法增长。1->2->4,经过两个来回，到达门限值4， 拥塞避免算法让拥塞窗口缓慢增长，即每经过一个往返时间 RTT 就把发送方的拥塞窗口 加 1 ，而不是加倍。这样拥塞窗口按线性规律缓慢增长。4->5->6…->10,而发送端不能超过接收端10，因此最后为10

知识点：

• 当cwnd（拥塞窗口值）<ssthresh（慢开始门限值）时，使用慢开始算法。加倍增长
• 当cwnd>ssthresh时，改用拥塞避免算法。加1线性增长
• 当cwnd=ssthresh时，慢开始与拥塞避免算法任意。

8.linux 系统中，给文件授予可执行权限的命令是（） D

A chown
B mv
C sudo
D chmod

解析：

• chown:给文件赋予拥有权的。
• mv:是移动文件的。
• sudo:拥有root权限执行文件，并不能给文件赋予执行权限。
• chmod:不仅可以给文件赋予执行权限还可以赋予读写权限。

9.下面关于Linux文件系统的inode描述错误的是：A

A inode和文件是一一对应的
B inode描述了文件大小和指向数据块的指针
C 通过inode可获得文件占用的块数
D 通过inode可实现文件的逻辑结构和物理结构的转换

解析：

一般情况下，文件名和inode号码是”一一对应”关系，每个inode号码对应一个文件名。但是，Unix/Linux系统允许，多个文件名指向同一个inode号码。这意味着，可以用不同的文件名访问同样的内容；对文件内容进行修改，会影响到所有文件名；但是，删除一个文件名，不影响另一个文件名的访问。这种情况就被称为”硬链接”（hard link）。 除了硬链接以外，还有一种特殊情况。文件A和文件B的inode号码虽然不一样，但是文件A的内容是文件B的路径。读取文件A时，系统会自动将访问者导向文件B。因此，无论打开哪一个文件，最终读取的都是文件B。这时，文件A就称为文件B的”软链接”（soft link）或者”符号链接（symbolic link）。 这意味着，文件A依赖于文件B而存在，如果删除了文件B，打开文件A就会报错：”No such file or directory”。这是软链接与硬链接最大的不同：文件A指向文件B的文件名，而不是文件B的inode号码，文件B的inode”链接数”不会因此发生变化。

10.进程阻塞的原因不包括____。A

A 时间片切换
B 等待I/O
C 进程sleep
D 等待解锁

解析：

进程有3个状态：就绪态。执行态、阻塞态。三种状态的转换包含有：
就绪->执行，执行->就绪，执行->阻塞，阻塞->就绪
等待I/O、进程sleep、等待解锁等原因都会导致进程暂停。关于”时间片切换”，当进程已经获得了除cpu外所有的资源，这时的状态就是就绪态，当分配到了时间
片就成了执行态，当时间片用完之前一直未进入阻塞态的话，此后便继续进入就绪态。所以进程的就绪与阻塞是完全不同的。

11.如何减少换页错误？B

A 进程倾向于占用CPU
B 访问局部性（locality of reference）满足进程要求
C 进程倾向于占用I/O
D 使用基于最短剩余时间（shortest remaining time）的调度机制

解析：

换页错误又称缺页错误，当一个程序试图访问没有映射到物理内存的地方时，就会出现缺页错误， 这时操作系统就要去虚拟内存中加载这块内存页。

百度了一下，减少换页错误的方法，即降低缺页中断率：

1. 内存页框数。增加作业分得的内存块数。
2. 页面大小。页面划分越大，中断率越低。
3. 替换算法的优劣影响缺页中断次数 。
4. 程序局部性。程序局部性好可减少缺页中断。

12.在内存分配的”最佳适应法”中，空闲块是按（）。C

A 始地址从小到大排序
B 始地址从大到小排序
C 块的大小从小到大排序
D 块的大小从大到小排序

13.某网站的数据库有一个成绩表myscore，希望找出成绩表中平均得分小于90的所有试卷。B

A select paper_id from myscore where sum(score) < 90 group by paper_id
B select paper_id from myscore group by paper_id having avg(score) < 90
C select paper_id from myscore where avg(score) < 90
D select paper_id from myscore where avg(score) < 90 group by paper_id

14.有土豆，萝卜各一筐，土豆有 240 个，萝卜有 313 个，把这两筐平均分给一些小朋友，一直土豆分到最后余 2 个，萝卜分到最后还余 7 个，求最多有多少个小朋友参加分水果？ D

A 14
B 17
C 28
D 34

15.4个袋子，15个球，每个袋子至少放一个球，而且袋子中的球数量不能重复，有多少种方式？ C

A 4
B 5
C 6
D 7

解析：

1,2,3,9
1,2,4,8
1,2,5,7
1,3,4,7
1,3,5,6
2,3,4,6

16.下列关于 java 语言的特点，描述错误的是（） C

A java是跨平台的编程语言
B java支持分布式计算
C java是面向过程的编程语言
D java支持多线程

17.instanceof运算符能够用来判断一个对象是否为: C

A 一个类的实例
B 一个实现指定接口的类的实例
C 全部正确
D 一个子类的实例

解析：

instance是java的二元运算符，用来判断他左边的对象是否为右面类（接口，抽象类，父类）的实例

18.关于PreparedStatement与Statement描述错误的是（）D

A 一般而言，PreparedStatement比Statement执行效率更高
B PreparedStatement会预编译SQL语句
C Statement每次都会解析/编译SQL，确立并优化数据获取路径
D Statement执行扫描的结果集比PreparedStatement大

解析：

1、创建时的区别：

​ Statement statement = conn.createStatement();
​ PreparedStatement preStatement = conn.prepareStatement(sql);
​ 执行的时候:
​ ResultSet rSet = statement.executeQuery(sql);
​ ResultSet pSet = preStatement.executeQuery();

由上可以看出，PreparedStatement有预编译的过程，已经绑定sql，之后无论执行多少遍，都不会再去进行编译，而 statement 不同，如果执行多变，则相应的就要编译多少遍sql，所以从这点看，preStatement 的效率会比 Statement要高一些

2、安全性问题：

preStatement是预编译的，所以可以有效的防止 SQL注入等问题，所以 preStatement 的安全性 比 Statement 高

3、代码的可读性 和 可维护性：preStatement的代码的可读性 和 可维护性明显更高

19.有这么一段程序：C

public class Test{
	public String name="abc";
	public static void main(String[] args){
		Test test=new Test();
		Test testB=new Test();
		System.out.println(test.equals(testB)+","+test.name.equals(testB.name));
	}
}

请问以上程序执行的结果是（）C
A true,true
B true,false
C false,true
D false,false

20.对于一个已经不被任何变量引用的对象，当垃圾回收器准备回收该对象所占用的内存时，将自动调用该对象的哪个方法（）A
A finalize
B notify
C notifyAll
D hashCode

编程题

21.【加减二叉树】
二叉树是除了叶子节点之外所有的节点都最多有两个子节点的树。满二叉树则是除叶子节点外所有节点都有两个子节点的树，且所有叶子节点到根节点的距离都相等。

现在有一棵无限大的满二叉树，根节点编号为 1 。编号为 i 的节点的左儿子编号为 2 * i ，右儿子2 * i + 1（比如根节点 1 的左儿子为 2，右儿子为 3，2 的左儿子为 4，右儿子为
5）牛牛在这棵树上做一个游戏，他从妞妞那里得到了两个数 n 和 k ，妞妞希望他拿着数字 0 从根节点开始往下走，每次选择一条边移动，到达一个节点时选择加上这个节点的编号或者减去这个节点的编号。在走到第 k 个节点时所得到的数字刚好等于 n。

这样的路径当然有很多。为了增加难度，妞妞决定让牛牛告诉她经过的节点的编号和最小的路径。
妞妞很聪明，给出的问题都是一定存在答案的。
你能帮帮牛牛吗？
输入描述：

一行，两个数字 n，k。

输出描述：

共 k 行，第 i 行输出第 i 步到达的节点编号，如果加上这个编号输出 '+'，减去这个编号输出 '-'。

备注：

1 <= n <= 1000000000。
1 <= n <= 2^k <= 2^60。

示例1：
输入

3 2

输出

1 +
2 +

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	long long n, k, a, d, b, i;
	while(~scanf("%lld%lld", &n, &k)){
        a = 1LL<<k;
        d = a - n;
        b = d / 2;
        for(i = 0; i < k; i++) {
            if((1LL<<i) & b)printf("%lld -\n",(1LL<<i));
            else {
                if(i == k - 1) {
                    if(d & 1) 
                        printf("%lld +\n",(1LL<<i));
                    else 
                        printf("%lld +\n",(1LL<<i)+1LL);
                }
                else 
                    printf("%lld +\n",(1LL<<i));
            }
        }
    }
	return 0;
}

解析

所有 n 都不大于 $2^k$。考虑到 n 等于 $2^k$ 时，一直往左走最后一步往右走。n等于2^k-1时一直往左走。n 等于 $2^k-d​$ 时，分 d 是奇数偶数讨论最后一步的走法（奇左偶右），前面 k-1 步一直往左走，令减去的值刚好等于 d/2 向下取整。

22.【走斜线】
有天他来到一张方格地图上，整张地图可以看做一个二维坐标轴。牛牛此刻处于原点（0,0），他想要到点（x,y）去。

牛牛有强迫症，他规定自己必须恰好k步走到点(x,y)，中途可以经过任何点包括（x,y），但是第k步一定要到达（x,y）。

一步有八种走法，直线东（+1,0）南（0,-1）西（-1,0）北（0,+1），斜线东南（+1,-1）东北（+1,+1）西南（-1,-1）西北（-1,+1）。

牛牛会在能k步到达目的地的基础下尽量走斜线，你能计算出牛牛到底走了多少条斜线吗？
输入描述：

第一行一个整数T，代表数据组数。
每组数据给出三个整数x，y，k。

输出描述：

对于每组数据，单独一行输出一个整数。
如果牛牛可以在第k步的时候到达(x,y)，输出牛牛走的斜线数量。
如果牛牛不能到达，输出-1。

备注：

对于100%的数据，1<=T<=1000，1<=x，y，k<=1000000000000000000。

示例1：
输入

2
2 3 4
7 7 9

输出

3
9

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
	int T;
	long long x, y, k, t, ans;
	scanf("%d", &T);
	while(T--) {
		scanf("%lld%lld%lld",&x,&y,&k);
		if(x > y) {
			t = x;
			x = y; 
			y = t;
		}
		if(y > k) {
			puts("-1");
			continue;
		}
		ans = k;
		if((y - x) % 2) ans--;
		else if((k - x) % 2) ans -= 2;
		printf("%lld\n", ans);
	}
	return 0;
}

解析

要到达目的地花费的最小步数是 x 和 y 的最大值，如果 k 小于这个值就一定到不了。如果 k 溢出了，那么在整个 k 步里，最多只会走两条直线。分别是如下三种情况（令x<=y）：0条直线（y-x）是偶数且（k-x）是偶数；1条直线（y-x）是奇数；2条直线（y-x）是偶数且（k-x）是奇数。

23.【得分最大】
牛牛和妞妞从他们的好朋友果果处得到了两个盒子，盒子里是一些写了分值的彩球。牛牛和妞妞发现两个盒子里的彩球数目是相等的，就决定一人一个。

妞妞拿到自己的盒子之后，决定跟牛牛玩一个游戏，规则如下：

一开始两个人盒子里的彩球数目都是n个，由妞妞先手，两人轮流实行下面两个操作中的一个（只能选其中一个执行，不能不执行。），直到两个盒子里的彩球都被
拿完位置。

1. 从自己的盒子里选一个球拿出来，把球上面的分值加在自己的总得分上边。
2. 从对方的盒子里选一个球拿出来，把这个球移出游戏（对方不能再拿这个球）。

妞妞和牛牛都十分聪明，不会出错，并且尽可能让自己的得分比对方多。妞妞想知道，在游戏结束的时候，他能比牛牛多得多少分呢？
输入描述：

第一行一个数字n，表示盒子里初始彩球的数目。
第二行n个数字a ，表示妞妞盒子里第i个彩球的分值是a。
第三行n个数字b ，表示牛牛盒子里第i个彩球的分值是b。

输出描述：

一个整数ans，表示游戏结束的时候妞妞比牛牛多的分值。

备注：

1<=n<=100000
1<=a <=1000000
1<=b <=1000000

示例1：
输入

3
2 7 7
2 8 7

输出

0

代码

#include <bits/stdc++.h>
using namespace std;

int a[100015],b[100015];

bool _cmp(int i, int j){return i > j;}

int main() {	
	int n;
	long long ans;
	while(~scanf("%d", &n)){
        for(int i = 1; i <= n; i++) 
            scanf("%d", &a[i]);
        for(int i = 1; i <= n; i++) 
            scanf("%d", &b[i]);
        sort(a + 1, a + 1 + n, _cmp);
        sort(b + 1, b + 1 + n, _cmp);
        ans = 0;
        int i = 1;
        int j = 1;
        while(i <= n || j <= n) {
            if(a[i] > b[j]) 
                ans += a[i++];
            else 
                j++;
            if(b[j] > a[i]) 
                ans -= b[j++];
            else 
                i++;
        }
        printf("%lld", ans);
    }
	return 0;
}

解析

双方都要使自己的得分尽可能比对方多，就有两种策略：使自己得分越多越好；使对方得分越少越好。所以贪心比较当前自己盒子里分值最大的彩球和对方盒子里分值最大的彩球，如果自己的分比较多，就从自己盒子里拿（自己得分越多越好），否则从对方盒子里拿（对方得分越少越好）。