2016CVTE校招在线笔试题

柔情只为你懂 2022-06-09 14:49 424阅读 0赞

> 2016CVTE校招在线笔试题  
> [https://www.nowcoder.com/test/458195/summary][https_www.nowcoder.com_test_458195_summary]

### 以下说法正确的有() ###

A. 多个进程操作同一个文件时，应该要考虑到文件的一致性问题
    B. 可通过文件在不同进程间进行数据传递和共享
    C. 可以通过全局变量在不同进程间传递数据
    D. 一个进程可以访问到所有物理内存空间

> 正确答案: A B
> 
>  *  进程间通信靠：管道、消息队列、信号、共享内存、套接口等
>  *  父子进程内存空间相互独立，全局变量也只能在同一进程的多个线程敏感词享。fork后子进程中是父进程的完全复制(其中有写时复制技术），不管什么变量，fork后父子进程中都是一样的，但两者之间没有关系，任何一个进程修改变量后，在另一个进程中都不能知道，更不能访问另一个进程中的变量，即使是全局变量. C错误！
>  *  [进程间通信（IPC）介绍][IPC]

### IP数据报分片的重组通常发生在() ###

A. 源主机和数据报经过的路由器上
    B. 源主机上
    C. 数据报经过的路由器上
    D. 目的主机上

> 正确答案: D
> 
>  *  重组发生在目的主机，分片发生在路由器上
>  *  1.**IP数据报分片的原因**：  
>     在TCP/IP分层中，数据链路层用 MTU (Maximum Transmission Unit，最大传输单元)来限制所能传输的数据包大小，MTU是指一次传送的数据最大长度，不包括数据链路层数据帧的帧头，如以太网的MTU为1500字节，实际上数据帧的最大长度为1512字节，其中以太网数据帧的帧头为12字节。  
>     2.**分片的思想**：  
>     当发送的IP数据报的大小超过了MTU时，IP层就需要对数据进行分片，否则数据将无法发送成功。  
>     IP 分片发生在 IP 层 ，不仅 **源端主机** 会进行分片，中间的 **路由器** 也有可能分片，因为不同的网络的 MTU 是不一样的，如果传输路径上的某个网络的 MTU 比源端网络的 MTU 要小，路由器就可能对 IP 数据报再次进行分片。而分片数据的 **重组** 只会发生在 **目的端** 的 IP 层。

### 引入多道程序技术以后，处理器的利用率() ###

A. 降低了
    B. 没有变化，只是程序的执行方便了
    C. 大大提高
    D. 没有影响

> 正确答案: C
> 
> **多道程序设计**是指在主存中同时存放多道用户作业，使它们都处于执行的开始点和开始点之间，**这些程序共享计算机系统资源**。  
> 多道程序设计的主要优点有：  
> (1)**提高CPU的利用率**。在多道程序环境下，多个程序共享计算机资源当某个程序等待I/O操作时，CPU可以执行其他程序，大大提高CPU的利用率。  
> (2)**提高设备的利用率**。在多道程序环境下，多个程序共享系统的设备，大大提高系统设备的利用率。  
> (3)**提高系统的吞吐量**。在多道程序环境下，减少了程序的等待时间，提高了系统的吞吐量。

### 关于TCP协议以下说法正确的是：（） ###

A. 通讯双方被动关闭的一方进入TIME_WAIT状态
    B. TIME_WAIT状态会持续2个MSL
    C. TIME_WAIT状态会持续1个MSL
    D. 通讯双方主动关闭的一方进入TIME_WAIT状态

> 正确答案: B D
> 
> TCP建立连接和断开连接过程  
> ![这里写图片描述][SouthEast]  
> 假设Client端发起中断连接请求，也就是发送FIN报文。Server端接到FIN报文后，意思是说”我Client端没有数据要发给你了”，但是如果你还有数据没有发送完成，则不必急着关闭Socket，可以继续发送数据。所以你先发送ACK，”告诉Client端，你的请求我收到了，但是我还没准备好，请继续你等我的消息”。这个时候Client端就进入`FIN_WAIT` 状态，继续等待Server端的 FIN 报文。当Server端确定数据已发送完成，则向Client端发送FIN报文，”告诉Client端，好了，我这边数据发完了，准备好关闭连接了”。Client端收到FIN报文后，”就知道可以关闭连接了，但是他还是不相信网络，怕Server端不知道要关闭，所以**发送ACK后**进入**`TIME_WAIT`**状态，如果Server端没有收到ACK则可以重传。“，Server端收到ACK后，”就知道可以断开连接了”。**Client端等待了2MSL后依然没有收到回复，则证明Server端已正常关闭**，那好，我Client端也可以关闭连接了。Ok，TCP连接就这样关闭了！  
> [什么是2MSL][2MSL]  
> [为什么TCP的TIME\_WAIT状态要保持2MSL?][TCP_TIME_WAIT_2MSL]

--------------------

### 以下说法正确的是() ###

A. 在计算机中，运算器访问寄存器的速度是最快的
    B. 在等待中断的过程中，CPU不可以处理其他任务
    C. 同一段代码每次运行的时间一定是一样的
    D. 软中断是由软件触发的一种中断

> 正确答案: A
> 
>  *  A中访问寄存器最快，依据：寄存器>cache>RAM>ROM
>  *  **硬中断**：  
>     1、 硬中断是由硬件产生的，比如，像磁盘，网卡，键盘，时钟等。每个设备或设备集都有它自己的IRQ（中断请求）。基于IRQ，CPU可以将相应的请求分发到对应的硬件驱动上（注：硬件驱动通常是内核中的一个子程序，而不是一个独立的进程）。  
>     2、 处理中断的驱动是需要运行在CPU上的，因此，当中断产生的时候，CPU会中断当前正在运行的任务，来处理中断。在有多核心的系统上，一个中断通常只能中断一颗CPU（也有一种特殊的情况，就是在大型主机上是有硬件通道的，它可以在没有主CPU的支持下，可以同时处理多个中断。）。
>  *  **软中断**：  
>     软中断的处理非常像硬中断。然而，它们仅仅是由当前正在运行的进程所产生的。软中断并不会直接中断CPU。也只有当前正在运行的代码（或进程）才会产生软中断。这种中断是一种需要内核为正在运行的进程去做一些事情（通常为I/O）的请求。

### 一个栈的入栈序列为ABCDE,则不可能的出栈序列为（） ###

A. ECDBA
    B. DCEAB
    C. DECBA
    D. ABCDE

> 正确答案: A B

### TCP首部报文信息中跟建立链接有关的是（） ###

A. PSH
    B. SYN
    C. FIN
    D. ACK

> 正确答案: B D
> 
> URG:Urget pointer is valid (紧急指针字段值有效)  
> SYN: 表示建立连接  
> FIN: 表示关闭连接  
> ACK: 表示响应  
> PSH: 表示有 DATA数据传输  
> RST: 表示连接重置。  
> [TCP数据报首部][TCP]

### 已知图的邻接表如下所示，根据算法，则从节点0出发按广度优先遍历的节点序列是 ###

![这里写图片描述][SouthEast 1]

A. 0 1 2 3
    B. 0 1 3 2
    C. 0 3 2 1
    D. 0 3 1 2

> 正确答案: C
> 
> [图基本算法 图搜索（广度优先、深度优先）][Link 1]

### 以下说法正确的有() ###

A. 在时间片轮询调度算法中，时间片越短则CPU利用率越高
    B. 优先级越高的进程占用CPU的运行时间就一定越多
    C. 在遍历大型二维数组int a[x][y]时，先遍历x或先遍历y的处理时间都是一样的
    D. 使用cache可以提高CPU的利用率

> 正确答案: D  
> A选项，时间片越短，说明其它进程或线程获得CPU，此时需要进行中断，CPU不能处理其它任务。  
> B选项，优先级越高，说明它获得CPU的可能性越大，但本身该作业所需占用CPU的时间就很少。  
> C选项，因为是按行顺序进行存储的，所以先遍历x，再遍历y相对要快一点，这涉及到预取操作。

### 设一组初始关键字记录关键字为（19,15,12,18,21,36,45,10),则以19位基准记录的一趟快速排序结束后的结果为() ###

A. 10,15,12,18,19,36,45,21
    B. 10,15,12,18,19,45,36,21
    C. 15,10,12,18,19,36,45,21
    D. 10,15,12,19,18,45,36,21

> 正确答案: A
> 
> 先从后往前扫描，比19小的与19交换，再从前往后扫描，比是19大的与19交换  
> 依次为：  
> 19 ， 15 ，12 ，18 ，21， 36 ， 45 ，10 // 从后往前扫描 10比19小，交换  
> 10 ， 15， 12,，18，21，36，45，19， 从前往后扫描，21 比19大，交换  
> 10 ， 15 ， 12 ，18 ， 19 ，36， 45， 21 // 19前边都比19小，后边都比19大，一趟比较结束

### 具有1000个节点的二叉树的最小深度为（）(第一层深度为1） ###

A. 11
    B. 12
    C. 9
    D. 10

> 正确答案: D
> 
> n个节点的二叉树与深度k的关系为 `n`最大 `2^k-1`

### 若进栈序列为1,2,3.4假定进栈和出栈可以穿插进行，则可能的出栈序列是() ###

A. 2,4,1,3
    B. 3,1,4,2
    C. 3,4,1,2
    D. 1,2,3,4

> 正确答案: D

### 以下程序统计给定输入中每个大写字母的出现次数(不需要检查输入合法性) ###

void AlphabetCounting(char a[],int n){
      int count[26]={},i,kind=0;
      for(i=0;i<n;++i) (1);
      for(i=0;i<26;++i){
        if(++kind>1) putchar(';');
        printf("%c=%d",(2));
       }
    }
    A. ++count[a[i]-'Z'];'Z'-i,count['Z'-i]
    B. ++count['A'-a[i]];'A'+i,count[i]
    C. ++count[i];i,count[i]
    D. ++count['Z'-a[i]];'Z'-i,count[i]

> 正确答案: D
> 
> 题意为输入设定全部是大写（ASCII码A-Z为65-90，递增），所以有两种情况：  
> 一、count\[0;25\]存储A-Z的个数，即count\[0\]存储A的个数，于是(1)++count\[a\[i\]-‘A’\]；(2)’A’+i，count\[i\]；  
> 二、count\[0;25\]存储Z-A的个数，即count\[0\]存储Z的个数，于是(1)++count\[‘Z’-a\[i\]\]；(2)’Z’-i，count\[i\]。  
> 所以答案为D

### 设非空二叉树中度数为0的结点数为n0，度数为1的结点数为n1,度数为2的结点数为n2,则下列等式成立的是（） ###

A. n0=n1+n2
    B. n0=2n1+1
    C. n0=n2+1
    D. n0=n1+1

> 正确答案: C
> 
> ![这里写图片描述][SouthEast 2]

### IP地址205.140.36.68的哪一部分表示网络号() ###

A. 205
    B. 205.140
    C. 68
    D. 205.140.36

> 正确答案: D
> 
> 1． A类IP地址  
> 一个A类IP地址由1字节的网络地址和3字节主机地址组成 ，网络地址的最高位必须是“0”， 地址范围从1.0.0.0 到126.0.0.0。  
> 2． B类IP地址  
> 一个B类IP地址由2个字节的网络地址和2个字节的主机地址组成 ，网络地址的最高位必须是“10”，地址范围从 128 .0.0.0到191.255.255.255。  
> 3． C类IP地址  
> 一个C类IP地址由3字节的网络地址和1字节的主机地址组成 ，网络地址的最高位必须是“110”。范围从 192 .0.0.0到223.255.255.255。

### 一棵深度为4的三叉树，最多有多少个节点？（） ###

A. 24
    B. 40
    C. 36
    D. 54

> 正确答案: B
> 
> ![这里写图片描述][SouthEast 3]  
> ![这里写图片描述][SouthEast 4]

### 有两个袋子，白色袋子里有7个红球和3个蓝球，黑色袋子里有3个红球和7个蓝球。每次取一个球，取完立刻放回，所有球都从某一个袋子里取，袋子的选择是随机的。共取出6个红球和4个蓝球。问所有球是从黑色袋子里取出的概率是（） ###

A. 0.1
    B. 0.48
    C. 0.66
    D. 0.16

> 正确答案: D
> 
> p(自黑袋取|取6红4蓝) = p(取6红4蓝，从黑袋中取)/p（取6红4蓝）；  
> 其中：  
> p(取6红4蓝，从黑袋中取) = p(从黑袋中取)\*p(黑袋中取出6红4蓝),  
> p（取6红4蓝） = p(黑袋子中取6红4蓝，从黑袋中取) + p(红袋子中取6红4蓝，从白袋中取)

a = 0.5 * pow(0.7, 6) * pow(0.3, 4)
    b = 0.5 * pow(0.3, 6) * pow(0.7, 4)
    P = a / (a + b) = 0.15517241379310343

### 关于二叉树，下面说法正确的是() ###

A. 二叉树中至少有一个节点的度为2
    B. 一个具有1025个节点的二叉树，其高度范围在11到1025之间
    C. 对于n个节点的二叉树，其高度为nlogn
    D. 二叉树的先序遍历是EFHIGJK,中序遍历为HFIEJKG,该二叉树的右子树的根为G

> 正确答案: B D
> 
> [根据二叉树的中序遍历和前序遍历，还原二叉树][Link 2]

### 以下选项中采用分治方法的算法有（） ###

A. 堆排序算法
    B. 插入排序算法
    C. 归并排序算法
    D. 二分查找算法
    E. 快速排序算法

> 正确答案: C D E
> 
> 存在疑问

### 已知有向图G=（V，E） ###

其中V=\{V1，V2,V3，V4，V5，V6,V7\} ，E=\{ < V1,V2>,< V1,V3>, < V1,V4 > , < V2,V5>, < V2,V6>,< V3,V5>, < V3,V6>,< V4,V6>,< V5,V7>,< V6,V7>\}， 则G的拓扑序列是：（）

A. V1, V4，V2，V6, V3，V5，V7
    B. V1，V2，V3，V4, V5，V6，V7
    C. V1，V3, V4，V2，V6，V5，V7
    D. V1，V3，V4, V6，V2, V5，V7

> 正确答案: B C
> 
> **拓扑序列的求解方法**：  
> (1)、找到一个没有后继的顶点(如果有一条边从A指向B,那么B是A的后继)。  
> (2)、从图中删除这个顶点，在列表的前面插入顶点的标记。  
> (3)、重复步骤1和2.直到所有的顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结果。

### 下面算法中可以判断出一个有向图是否有环的是：（） ###

A. 求最短路径
    B. 深度优先遍历
    C. 广度优先遍历
    D. 拓扑排序

> 正确答案: B D
> 
> 判断 无向图 中是否存在回路（环）的算法描述  
> 如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。  
> 算法：  
> 第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。  
> 第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。  
> 如果最后还有未删除顶点，则存在环，否则没有环。

有向图是否有环的判定算法，主要有深度优先和拓扑排序两种方法。

[https_www.nowcoder.com_test_458195_summary]: https://www.nowcoder.com/test/458195/summary
[IPC]: http://www.cnblogs.com/CheeseZH/p/5264465.html
[SouthEast]: /images/20220609/b8847e3d400f4705bd3c0e5489bfd57a.png
[2MSL]: http://blog.csdn.net/xiaofei0859/article/details/6044694
[TCP_TIME_WAIT_2MSL]: http://blog.csdn.net/unix21/article/details/16918307
[TCP]: http://blog.chinaunix.net/uid-26413668-id-3408115.html
[SouthEast 1]: /images/20220609/49d0db6be3b446eebb83e6859158c926.png
[Link 1]: http://www.cnblogs.com/dzkang2011/p/bfs_dfs.html
[SouthEast 2]: /images/20220609/5ce11187645c48379ae2823b6ee17fee.png
[SouthEast 3]: /images/20220609/438ca5d1030a45df9ac50348570f739c.png
[SouthEast 4]: /images/20220609/5ff6c78f562c4015a40779f43d72e722.png
[Link 2]: http://www.cnblogs.com/xinchrome/p/4905608.html