• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

模拟笔试记录-快手2020校园招聘秋招笔试-工程C试卷

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

选择题

1、关于java的异常处理机制,以下说法正确的是:

当某个线程抛出OutOfMemoryError时,其他线程有可能不受影响
当大量抛出RuntimeException时,不会影响系统的吞吐量
java.lang.Exception是java.lang.Error的父类
finally块代码一定会被执行

finally块代码并不一定会执行,不是很懂java的try、catch、finally。

2、错误原因:512+256+128+...+1=1023,不要算错

3、关于mysql,下面说法不正确的是:

mysql中的utf8类型最大只支持3个bytes
desc关键字可以作为table的字段名
filesort是通过读取磁盘文件进行排序,会极大降低查询性能
smallint占用2个bytes的存储空间

utf8类型最大只支持3个bytes,utf8mb4类型最大只支持4个bytes。
filesort并非是对磁盘文件进行排序。好像是先对每个缓冲块进行快速排序,然后对各个块进行归并排序。

5、查找表结构用以下哪一项?

DESC

mysql中,查询表结构用DESC,可以显示各列名以及各列的限制(是否主码,是否非空)。

6、如何强制垃圾回收器立即回收一个对象?

调用System.gc()方法
调用Runtime.gc()方法
将对象赋值null
无法强制垃圾回收器立即执行

System.gc()只是提醒垃圾回收器执行,不是强制其执行。

7、关于sleep()和wait(),以下描述错误的一项是?

sleep是Thread类的方法,wait是Object类的方法;
sleep不释放对象锁,wait放弃对象锁;
sleep暂停线程、但监控状态仍然保持,结束后会自动恢复;
wait后进入等待锁定池,只有针对此对象发出notify方法后获得对象锁进入运行状态。

notifyAll方法也可以。

参考资料:sleep()和wait()的区别及wait方法的一点注意事项 - shiki0921 - 博客园

sleep是Thread类的方法,导致此线程暂停执行指定时间,给其他线程执行机会,但是依然保持着监控状态,过了指定时间会自动恢复,调用sleep方法不会释放锁对象。

当调用sleep方法后,当前线程进入阻塞状态。目的是让出CPU给其他线程运行的机会。但是由于sleep方法不会释放锁对象,所以在一个同步代码块中调用这个方法后,线程虽然休眠了,但其他线程无法访问它的锁对象。这是因为sleep方法拥有CPU的执行权,它可以自动醒来无需唤醒。而当sleep结束指定休眠时间后,这个线程不一定立即执行,因为此时其他线程可能正在运行。

wait方法是Object类里的方法,当一个线程执行到wait方法时,它就进入到一个和该对象相关的等待池中,同时释放了锁对象,等待期间可以调用里面的同步方法,其他线程可以访问,等待时不拥有CPU的执行权,否则其他线程无法获取执行权。当一个线程执行了wait方法后,必须调用notify或者notifyAll方法才能唤醒,而且是随机唤醒,若是被其他线程抢到了CPU执行权,该线程会继续进入等待状态。由于锁对象可以是任意对象,所以wait方法必须定义在Object类中,因为Obeject类是所有类的基类。

8、下列协议中,将MAC地址转为IP地址的协议是:

RARP

ARP(Address Resolution Protocol)地址解析协议,是根据IP地址获取物理地址的一个TCP/IP协议。
RARP(Reverse Address Resolution Protocol)是反向地址解析协议。

10、在TCP/IP体系结构中,直接为ICMP提供服务的协议是:

IP

不过啥是ICMP呀。

11、下列关于进程和线程的叙述中,正确的是:

不管系统是否支持线程,进程都是资源分配的基本单位
线程是资源分配的基本单位,进程是调度的基本单位
系统级线程和用户级线程的切换都需要内核的支持
同一进程中的各个线程拥有各自不同的地址空间

B选项:明显线程是用来调度的,进程才是资源分配的。D选项:同一进程的线程贡献这个进程的资源。

12、若某单处理器多进程系统中有多个就绪态进程,则下列关于处理机调度的叙述中,错误的是:

在进程结束时能进行处理机调度
创建新进程后能进行处理机调度
在进程处于临界区时不能进行处理机调度
在系统调用完成并返回用户态时能进行处理机调度

好像是这么理解:B选项:假如一开始没有进程,那么创建新进程完成后就会进行处理机调度。C选项:有时,临界区是类似进程访问打印机之类的外设,在等待外设的过程中造成的。这个时候是可以进行处理机调度的。其他情况不清楚是否可以。

13、关于TCP协议的描述,以下错误的是?

面向连接
可提供多播服务
可靠交付
报文头部长,传输开销大

TCP是连接的、可靠的,UDP是无连接的,不可靠的。(TCP是一个虚拟连接,握手的过程就是为了建立虚拟连接,发送还需要对方进行确认,拥有拥塞控制。UDP是无连接的,只顾自己发送,一直尽力去做好,在一些需要实时性的传输中,UDP可以没这么卡)
TCP仅支持单播,不能提供多播与广播,每次是只面向连接的两台设备的。
TCP加了很多东西,UDP只是简单加了报文头表示这个是UDP协议。

UDP TCP
是否连接 无连接 面向连接
是否可靠 不可靠传输,不使用流量控制和拥塞控制 可靠传输,使用流量控制和拥塞控制
连接对象个数 支持一对一,一对多,多对一和多对多交互通信 只能是一对一通信
传输方式 面向报文 面向字节流
首部开销 首部开销小,仅8字节 首部最小20字节,最大60字节
适用场景 适用于实时应用(IP电话、视频会议、直播等) 适用于要求可靠传输的应用(文件传输)

参考资料:
TCP的可靠传输机制_网络_sinat_28557957的博客-CSDN博客
TCP/IP详解之:广播和多播 - 墨城烟雨 - 博客园
怎么理解TCP的面向连接和UDP的无连接(不面向连接)?_网络_infi-CSDN博客
主要看这个:一文搞懂TCP与UDP的区别 - Fundebug - 博客园

15、有关C++程序运行时的函数地址,下列说法正确的是:

每个函数的地址都是固定的,同一个程序重复运行多次,每次函数地址都一样
每个函数的地址是不固定的,但在操作系统版本、硬件版本不变的情况下是固定的,同一个程序重复在相同软硬件环境下运行多次,每次函数地址都一样
地址是否固定要看系统配置和编译选项,如果开启了地址随机化,那地址是每次都变的,如果没开启,那么地址每次都一样
每个函数的地址都是不定的,同一个程序重复运行多次,每次地址都不同

好像地址随机化是为了对抗反汇编的。默认是没有的。

17、关于TCP协议状态描述正确的是

只有执行主动关闭端才会出现TIME_WAIT
当接受到FIN报文时,会进入CLOSING状态
数据传输完成后发送FIN报文后进入TIME_WAIT状态
client和server端最终都会经历TIME_WAIT状态

参考上面的TCP的解除连接的四次挥手。

开始:双方是建立连接状态。

1、客户端发送FIN,自己进入FIN_WAIT状态。并停止自己发送新的数据。

2、服务端接收FIN,自己进入CLOSE_WAIT状态,告诉应用层客户端到服务端的连接已经停止,返回一个ACK。服务端若还有数据发送,客户端依然需要接收。

3、客户端接收ACK,然后还要等待服务端发送剩余的数据。

4、服务端发送数据完毕,发送FIN,自己进入LAST_ACK状态,等待客户端的ACK。

5、客户端接收FIN,返回ACK,进入CLOSE_WAIT状态,然后等待超时(2MSL,两倍最长报文寿命),若没有收到服务器继续发送的FIN(意味着自己返回的ACK丢失了,要重发ACK),则关闭连接。

6、直到服务端收到ACK,关闭连接,否则持续发送FIN。

所以服务器关闭连接会早一点。

【问题1】为什么连接的时候是三次握手,关闭的时候却是四次握手?

答:因为当Server端收到Client端的SYN连接请求报文后,可以直接发送SYN+ACK报文。其中ACK报文是用来应答的,SYN报文是用来同步的。但是关闭连接时,当Server端收到FIN报文时,很可能并不会立即关闭SOCKET,所以只能先回复一个ACK报文,告诉Client端,"你发的FIN报文我收到了"。只有等到我Server端所有的报文都发送完了,才能发送FIN报文,因此不能一起发送。故需要四次握手。

【问题2】为什么TIME_WAIT状态需要经过2MSL(最大报文段生存时间)才能返回到CLOSE状态?

答:虽然按道理,四个报文都发送完毕,可以直接进入CLOSE状态了,但是必须假想网络是不可靠的,有可能最后一个ACK丢失。所以TIME_WAIT状态就是用来重发可能丢失的ACK报文。在Client发送出最后的ACK回复,但该ACK可能丢失。Server如果没有收到ACK,将不断重复发送FIN片段。所以Client不能立即关闭,它必须确认Server接收到了该ACK。Client会在发送出ACK之后进入到TIME_WAIT状态。Client会设置一个计时器,等待2MSL的时间。如果在该时间内再次收到FIN,那么Client会重发ACK并再次等待2MSL。所谓的2MSL是两倍的MSL(Maximum Segment Lifetime)。MSL指一个片段在网络中最大的存活时间,2MSL就是一个发送和一个回复所需的最大时间。如果直到2MSL,Client都没有再次收到FIN,那么Client推断ACK已经被成功接收,则结束TCP连接。

参考资料:(5条消息)TCP的三次握手与四次挥手理解及面试题(很全面)_网络_lucky_jun-CSDN博客

18、关于epoll和select的区别,哪个说法是错误的?

epoll和select都是I/O多路复用的技术,都可以实现同时监听多个I/O事件的状态。
epoll相比select效率更高,主要是基于其操作系统支持的I/O事件通知机制,而select是基于轮询机制。
epoll支持水平触发和边沿触发两种模式。
select能并行支持I/O比较小,且无法修改。

完全不懂这是什么。

编程题

21、尺取/二分

小明最近在做病毒自动检测,他发现,在某些library 的代码段的二进制表示中,如果包含子串并且恰好有k个1,就有可能有潜在的病毒。library的二进制表示可能很大,并且子串可能很多,人工分析不可能,于是他想写个程序来先算算到底有多少个子串满足条件。如果子串内容相同,但是开始或者结束位置不一样,则被认为是不同的子串。

注:子串一定是连续的。例如"010"有6个子串,分别是 "0, "1", "0", "01", "10", "010"。

数据范围:1<=n<=1e6, 0<=k<=1e6

题解:很明显的一个尺取的题目,尺取的步骤是用l和r框住恰好k个1,然后数向左向右的全0分别有多少个。需要注意的是k=0的时候要另外处理。搞得好像很多细节的样子,早知道直接二分就可以了,枚举每个左端点,然后在前缀和上面二分找出差分为k的一段,这一段都是可行的。或者对连续的0进行压缩,对于每个1,存放其右侧的连续的0的数量。然后特殊处理一下第一个1的左侧,每次就是k个1直接尺取,不需要太多情况。

char s[1000005];
 
void test_case() {
    int n, k;
    scanf("%d%s", &k, s + 1);
    n = strlen(s + 1);
    if(k > n) {
        puts("0");
        return;
    }
    if(k == 0) {
        ll ans = 0;
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            if(s[i] == '0')
                ++cnt;
            else {
                ans += 1ll * cnt * (cnt + 1) / 2;
                cnt = 0;
            }
        }
        ans += 1ll * cnt * (cnt + 1) / 2;
        printf("%lld\n", ans);
        return;
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i)
        cnt += (s[i] == '1');
    if(cnt < k) {
        puts("0");
        return;
    }
    ll ans = 0;
    int l = 1, r = 0;
    cnt = 0;
    while(1) {
        while(l <= n && s[l] == '0')
            ++l;
        if(l > n)
            break;
        //printf("[%d,%d] cnt=%d\n", l, r, cnt);
        if(r == 0) {
            r = l;
            cnt = 1;
        }
        //printf("[%d,%d] cnt=%d\n", l, r, cnt);
        while(r + 1 <= n && cnt + (s[r + 1] == '1') < k) {
            ++r;
            cnt += (s[r] == '1');
        }
        if(r + 1 <= n && s[r + 1] == '1' && cnt + 1 == k) {
            ++r;
            cnt += (s[r] == '1');
        }
        //printf("[%d,%d] cnt=%d\n", l, r, cnt);
        if(cnt == k) {
            int pre0 = 0, suf0 = 0;
            int pl = l - 1, pr = r + 1;
            while(pl >= 1 && s[pl] == '0') {
                ++pre0;
                --pl;
            }
            while(pr <= n && s[pr] == '0') {
                ++suf0;
                ++pr;
            }
            ans += 1ll * (pre0 + 1) * (suf0 + 1);
            //printf("l=%d r=%d\n", pre0, suf0);
        }
        cnt -= (s[l] == '1');
        ++l;
    }
    printf("%lld\n", ans);
}

23、dp

给定一组石头,每个石头有一个正数的重量。每一轮开始的时候,选择两个石头一起碰撞,假定两个石头的重量为x,y,x<=y,碰撞结果为:

  1. 如果x==y,碰撞结果为两个石头消失
  2. 如果x!=y,碰撞结果两个石头消失,生成一个新的石头,新石头重量为y-x

最终最多剩下一个石头为结束。求解最小的剩余石头质量是多少。

数据范围:所有石头的重量总和不超过10000。

题解:并不是每次取出最大的两个贪心,这样会WA,正解是dp。注意到消除石头的过程,非常像是给其中小的那个加负号,大的那个加正号,然后整体作为一个结果放回去。意思就是最终只需要给这些数字定正负,然后求这个值的绝对值的最小值。可以用个滚动数组记录dp[i][j]为前i个石头是否能组合出重量j,dp完成之后,得到一个全部石头的重量sum,对于可以组合出的重量j(dp[n][j]为true),就尝试用abs(j-(sum-j))更新答案。

24、暴力

在你面前有n个蓄水池,他们组成了树形结构(由n-1条边连接)。蓄水池节点编号从1开始到n。对每个蓄水池节点来说,他的儿子蓄水池节点都摆放在他的下面,并且和它用水管相连,根据重力,水会向下流动。现在我们要在蓄水池上做一些操作:

  1. 把节点v填满水。然后v的所有儿子节点水也会被填满。
  2. 清空节点v的水。然后v所有的父亲节点水都会被清空。
  3. 询问每个蓄水池节点是否有水。
    初始状态时候,每个节点都是空的。
    现在我们会依次进行一系列操作,我们想提前知道每次操作后的结果,你能帮忙解决吗?

数据范围:n<=1000

题解:看样例瞎猜树的根是1,然后写个dfs暴力更新。假如n变得更大,树剖的 \(O(nlog^2n)\) 肯定是可行的一种方案,但是有没有可能进行树上差分呢?感觉是不行的。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#使用原生的Directx和OpenGL绘图发布时间:2022-07-13
下一篇:
Linux下C语言的调试--转发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap