点击「查看答案」展开答案解析。

来源： 牛客原题　|　题量： 33 题

第1题（单选题） 内存页式管理方式中，首先淘汰在内存中空闲（未被修改或读取）时间最长的帧，这种替换策略是_____.（ ） 　A. 先进先出法（FIFO） 　B. 最近最少使用法（LRU） 　C. 优先级调度 　D. 轮转法

查看答案

答案：B（最近最少使用法 LRU） 「未被修改或读取时间最长」即最久未被访问，正是 LRU（淘汰最久未使用的页面）；FIFO 淘汰的是驻留时间最长的。

第2题（单选题） 进程P1使用资源情况：申请资源S1．．•申请资源S2，…释放资源S1；进程P2使用资源情况：申请资源S2，…申请资源S1，…释放资源S2，系统并发执行进程P1，P2，系统将( ) 　A. 必定产生死锁 　B. 可能产生死锁 　C. 不会产生死锁 　D. 以上说法都不对

查看答案

答案：B（可能产生死锁） P1 持有 S1 等 S2、P2 持有 S2 等 S1，可能形成循环等待而死锁，但不是必然（若一方先完成释放则不发生）。

第3题（单选题） 引用和指针，下面说法不正确的是：（） 　A. 引用和指针在声明后都有自己的内存空间 　B. 引用必须在声明时初始化，而指针不用 　C. 引用声明后，引用的对象不可改变，对象的值可以改变，指针可以随时改变指向的对象以及对象的值 　D. 空值NULL不能引用，而指针可以指向NULL。

查看答案

答案：A 引用是别名，不占独立内存空间（A 错）；引用必须初始化且不能改绑定，不能为 NULL（B、C、D 正确）。

第4题（单选题） 关于排序，下面说法不正确的是 　A. 快排时间复杂度为O(N*logN)，空间复杂度为O(logN) 　B. 归并排序是一种稳定的排序,堆排序和快排均不稳定 　C. 序列基本有序时，快排退化成冒泡排序，直接插入排序最快 　D. 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)

查看答案

答案：D 堆排序是原地排序，空间复杂度 O(1) 而非 O(logN)（D 错）；其余三项均正确。

第5题（单选题） 用二进制来编码字符串“abcdabeaa”,需要能够根据编码，解码回原来的字符串，最少需要多长的二进制字符串？ 　A. 17 　B. 18 　C. 19 　D. 29

查看答案

答案：C（19） 哈夫曼编码。字符频次：a=4, b=2, c=1, d=1, e=1。编码长度 a=1, b=3, c=3, d=3, e=3。总长 = 4×1 + 2×3 + 1×3×3 = 4 + 6 + 9 = 19。

第6题（单选题） TCP关闭过程中，主动关闭方不可能处于的状态是（） 　A. FIN_WAIT_1 　B. FIN_WAIT_2 　C. CLOSE_WAIT 　D. TIME_WAIT

查看答案

答案：C（CLOSE_WAIT） CLOSE_WAIT 是被动关闭方收到 FIN 后进入的状态；主动关闭方经历 FIN_WAIT_1 → FIN_WAIT_2 → TIME_WAIT。

第7题（单选题） 已知二叉树的前序序列为BCDEFAG，中序序列为DCFAEGB，请问后序序列为___ 　A. DAFEGCB 　B. DAEGFCB 　C. DAFGECB 　D. DAEFGCB

查看答案

答案：C（DAFGECB） 由前序 BCDEFAG + 中序 DCFAEGB 重建：根为 B，左子树后序 DAFGEC，右子树为空，整体后序 DAFGECB。

第8题（单选题） 假如有两个表的连接是这样的： table_1 INNER JOIN table_2 其中table_1和table_2是两个具有公共属性的表，这种连接会生成哪种结果集？ 　A. 包括table_1中的所有行，不包括table_2的不匹配行 　B. 包括table_2中的所有行，不包括table_1的不匹配行 　C. 包括和两个表的所有行 　D. 只包括table_1和table_2满足条件的行

查看答案

答案：D INNER JOIN（内连接）只返回两表中满足连接条件的匹配行。

第9题（单选题） 请写出下面程序的输出：

#include <iostream>
using namespace std;
unsigned int GetTestNum() {
    static unsigned int a = 0;  
    static unsigned int b = 1;  
    int c = a + b;
    a = b;
    b = c;
    return c;
}
int main(int argc, char* argv[]) {
    for (int i = 0; i < 9; i++) {
        GetTestNum();
    }   
    cout << GetTestNum() << endl;
}

　A. 1 　B. 144 　C. 89 　D. 55

查看答案

答案：C（89） 该函数用 static 变量模拟斐波那契：依次产生 1,2,3,5,8,13,21,34,55,89… 循环 9 次后第 10 次调用返回 89。

第10题（单选题） 如下函数，在32 bit系统foo(2^31-3)的值是：

int foo(int x)
 {
     return x&-x;
 }

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

查看答案

答案：C（2） C 中 ^ 是异或，且 - 优先级高于 ^，故 2^31-3 = 2^(31-3) = 2^28 = 30。x&-x 取最低位 1，30=0b11110，结果为 2。

第11题（单选题）

int func(int x) { 
    int countx = 0; 
    while(x) { 
        countx ++; 
        x = x & (x - 1); 
    } 
    return countx; 
} 

如果x=254，函数返回值为： 　A. 6 　B. 7 　C. 8 　D. 0

查看答案

答案：B（7） x &= x-1 每次消掉最低位 1，循环次数即 1 的个数。254 = 0b11111110 有 7 个 1。

第12题（单选题） 在进程状态转换时，下列哪一种状态是不可能发生的： 　A. 等待态->运行态 　B. 运行态->就绪态 　C. 运行态->等待态 　D. 就绪态->运行态

查看答案

答案：A（等待态→运行态） 等待态只能先转为就绪态再被调度为运行态，不能直接到运行态。

第13题（单选题） 如果i=5；那么a=(++i)–;之后，a和i的值各是多少？ 　A. a=6.i=6 　B. a=5.i=6 　C. a=6.i=5 　D. a=5.i=5

查看答案

答案：C（a=6, i=5） (++i)--：先 ++i 得 i=6，赋值 a=6，再对表达式结果 6 做 –（无副作用），故 a=6, i=5。

第14题（单选题） DNS协议位于OSI模型中的哪一层： 　A. 应用层 　B. 网络层 　C. 传输层 　D. 会话层

查看答案

答案：A（应用层） DNS 是应用层协议（OSI 第 7 层），基于 UDP/TCP 53 端口。

第15题（单选题） 下列算法中不属于稳定排序的是： 　A. 插入排序 　B. 冒泡排序 　C. 快速排序 　D. 归并排序

查看答案

答案：C（快速排序） 插入、冒泡、归并是稳定排序；快排和堆排序不稳定。

第16题（单选题） 二叉树的根节点计为第1层结点，则第9层最多有多少个结点？ 　A. 18 　B. 256 　C. 128 　D. 64

查看答案

答案：B（256） 第 9 层最多 2^(9-1) = 256 个结点。

第17题（单选题） 下列描述，正确的一共有多少个？ 1)const char *p，这是一个常量指针，p的值不可修改 2)在64位机上，char *p= “abcdefghijk”; sizeof(p)大小为12 3)inline会检查函数参数，所以调用开销显著大于宏 4)重载是编译时确定的，虚函数是运行时绑定的； 　A. 1 　B. 2 　C. 3 　D. 4

查看答案

答案：A（1） 仅 4) 正确。1) const char *p 是「指向常量的指针」，p 本身可改；2) 64 位机指针 sizeof=8；3) inline 开销不显著大于宏且更安全。

第18题（单选题） 下面关于linux文件系统的软链接文件和硬链接文件，描述不正确的是 　A. 软链接文件可以指向另外一个文件系统的文件 　B. 硬链接文件会增加被指向文件的引用计数 　C. 删除被指向文件时，对应的软链接文件会失效 　D. 删除被指向文件时，对应的硬链接文件会失效

查看答案

答案：D 删除被指向文件时，硬链接文件不受影响（引用计数减 1，文件仍存在），D 描述不正确。

第19题（单选题） 下列描述，错误的是： 　A. 文件系统IO自带缓冲，以减小对磁盘文件的访问，提高系统性能 　B. 通过select和epoll能同时监听处理多个IO事件 　C. 使用linuxIPC中的pipe机制，生产者写入数据到消费者消费数据，依次要经过如下拷贝：生产者用户空间到生产者内核空间的拷贝，生产者内核空间到消费者内核空间的拷贝，消费者内核空间到消费者用户空间的拷贝。 　D. C标准IO库自带缓冲，以减小fread或fwrite等带来的系统开销

查看答案

答案：C pipe 是同一内核缓冲区，写入与读取各发生一次用户态↔内核态拷贝（共两次），不存在「生产者内核→消费者内核」的拷贝，C 错误。

第20题（单选题） 下列网络知识点，描述不正确的是__ 　A. 字节序是一种特殊的协议，在涉及到多个字节联合解析时才有意义，所以单字节编码的ASCII编码无需关注 　B. rpc自带的序列化/反序列化，内部一般会处理好字节序，此时调用者无需关注字节序 　C. ping127.0.0.1，网络包并不会传递到物理网卡 　D. tcp通信相比udp通信，具有可靠和有记录边界等优点。

查看答案

答案：D TCP 是字节流，无消息边界；UDP 才有报文边界。D 描述错误。

第21题（单选题） 有以下函数，其作用是什么？

int func(int num, int i) { 
	int tmp = ~((1 << (i + 1)) -1); 
	return num & tmp;
 } 

　A. 检查num的i位是否为0 　B. 将num的倍数据取反 　C. 将num最高位到i位（含）清零 　D. 将num的i位到0位（含）清零

查看答案

答案：D tmp = ~((1<<(i+1))-1) 使低 i+1 位（第 0..i 位）为 0、高位为 1，num & tmp 即将 num 的第 i 位到第 0 位（含）清零。

第22题（单选题） 关于epoll和select，以下说法哪个是错误的： 　A. select单个进程可监视的fd数量受到限制 　B. epoll和select都可以实现同时监听多个I/O事件的状态 　C. epoll基于轮训机制，select基于操作系统支持的I/O通知机制 　D. epoll支持水平触发和边沿触发两种模式

查看答案

答案：C 说反了：select 基于轮询、epoll 基于内核事件通知（回调）；其余三项正确。

第23题（单选题） 下列不属于标准冯诺依曼计算机体系结构部件的是 　A. 输入与输出设备 　B. 控制器 　C. 寄存器 　D. 运算器

查看答案

答案：C（寄存器） 冯·诺依曼五大部件：运算器、控制器、存储器、输入设备、输出设备；寄存器不属于五大部件。

第24题（单选题） n个节点的二叉树，最多可以有多少层？ 　A. n/2 　B. log(n) 　C. n-1 　D. n

查看答案

答案：D（n） 退化为链状的二叉树每层仅一个结点，最多 n 层。

第25题（单选题） 如下那一段代码不能给地址0xaae0275c赋值为1？ 　A. volatile int *p = (int *)0xaae0275c; *p = 1; 　B. volatile int *p = (int *)0xaae0275c; p[0] = 1; 　C. *(volatile int *)0xaae0275c = 1; 　D. (volatile int *)0xaae0275c[0] = 1;

查看答案

答案：D (volatile int *)0xaae0275c[0] = 1 中 [] 优先级高于强制转换，语义错误；A、B、C 均能正确给该地址赋 1。

第26题（单选题） 下面关于二叉树的说法正确的是： 　A. 满二叉树是完全二叉树 　B. 满二叉树中有可能存在度数为1的节点 　C. 完全二叉树是满二叉树 　D. 完全二叉树中某个节点可以没有左孩子，只有右孩子

查看答案

答案：A 满二叉树一定是完全二叉树（A 对）；满二叉树无度为 1 的结点、完全二叉树不一定是满二叉树、完全二叉树不能只有右孩子没有左孩子。

第27题（单选题） 已知二叉树的前序序列为BCDEFAG，中序序列为DCFAEGB，请问后序序列为___ 　A. DAFEGCB 　B. DAEGFCB 　C. DAFGECB 　D. DAEFGCB

查看答案

答案：C（DAFGECB） 同第 7 题，后序为 DAFGECB。

第28题（单选题） 下列描述，错误的是？ 　A. 函数参数传值，相比传指针，很多时候开销会更大 　B. 函数使用引用做形参时，无法对该引用形参赋值为NULL 　C. 函数返回指针时，要避免指针指向内部临时变量 　D. 函数传值时，如果函数体内对形参值做修改，同样会影响到实参的值

查看答案

答案：D 值传递修改形参不影响实参，D 错误；其余三项正确。

第29题（单选题） 关于可重入和线程安全，下面描述不准确的是： 　A. 可重入函数一定线程安全，而线程安全函数不一定可重入 　B. 单线程环境中，使用不可重入函数并不会引发问题 　C. 使用互斥变量，确保非线程函数被串行调用，并不会引发问题 　D. 函数最好别使用全局变量，以便保证线程可安全或可重入

查看答案

答案：C 互斥只能保证串行访问，无法保证可重入（如信号处理中重入仍可能死锁/出错），C 描述不准确。

第30题（单选题） 关于 HTTP 协议的描述中,错误的是 ( ) 　A. 是 WWW 客户机和服务器之间的传输协议 　B. 定义了请求报文和应答报文的格式 　C. 定义了 WWW 服务器上存储文件的格式 　D. 会话过程通常包括连接、请求、应答和关闭 4 个步骤

查看答案

答案：C HTTP 是传输协议，不定义服务器上文件的存储格式，C 错误。

第31题（问答题） 在滴滴的大数据分析任务中经常会遇到根据用户的IP地址查询用户归属地的问题，现在有个文件 source.txt，其中包含了n 行IP地址（例如：114.246.68.141）；有另一个文件 ip_dict.txt，里边包含了 m 行不同 IP 段到归属地的映射关系（例如：114.246.0.0/18 北京）, IP 段之间不重合（多个IP段可能对应相同的归属地）。请设计一个算法, 要尽可能快的将 source.txt 中的全部 IP 地址转换成 “IP 归属地“形式，并给出数据结构和复杂度分析。

查看答案

要点

1. 数据结构：将 IP 段转成 32 位无符号整数区间 [start, end]，按 start 排序；或用前缀树/线段树。
2. 算法：对每个 IP 转成整数后二分查找其所属区间（upper_bound(start) 回退一个区间），O(log m) 每条；或先对 source 排序后双指针扫描。
3. 复杂度：排序 O(m log m)，查询 O(n log m)（二分）或 O(n+m)（双指针）。

第32题（问答题） 浏览器作为PC端上网的入口，是我们日常使用最频繁的软件之一；但你知道一个网页经历了怎样的过程才能呈现在我们面前吗？请尽可能详细地描述一下从输入网站地址，到页面呈现在我们面前这一过程都发生了什么。（提示：越详细越好，可以从DNS，HTTP, TCP/IP, web服务器，HTML/CSS/JS等方面展开，并针对某一项做深入描述。）

查看答案

要点

1. 输入 URL 并解析（协议/域名/端口/路径）。
2. DNS 解析域名 → IP（递归/迭代查询、缓存）。
3. 建立 TCP 连接（三次握手）；（HTTPS 则再 TLS 握手）。
4. 发送 HTTP 请求，服务器处理并返回响应。
5. 浏览器解析 HTML → 构建 DOM 树、CSSOM 树 → 渲染树 → 布局（回流）→ 绘制，JS 可能阻塞/异步加载。 深入方向：DNS 解析流程、TCP 三次握手/拥塞控制、HTTPS 证书链。

第33题（问答题） 请设计一个车辆和订单匹配系统，假设只有一个小城市，司机个数<6000、订单量峰值每分钟 <500

基本需求流程：

a) 乘客发单（设定起终点）；

b) 司机听单；

c) 系统找出合适的订单并通知司机

d) 司机接单；

e) 通知乘客有司机抢到订单； 结合你所掌握的计算机的知识，设计一个系统能满足上述需求。

要求：

A. 针对上述需求，定义服务的接口，接口要完整，能完全实现上述需求

B. 画出系统架构图

C. 简单画出系统工作流程

查看答案

要点

1. 接口定义：乘客 createOrder(from,to)、司机 listen()、系统 match(driver,order)、司机 accept(orderId)、推送 notifyPassenger(driver, order)。
2. 架构：网关 → 订单服务 / 司机服务 / 匹配引擎 / 推送服务；订单与司机按地理网格分片，Redis 存在线司机位置，消息队列异步通知。
3. 流程：乘客发单 → 订单入池 → 按距离/服务分找附近司机并广播 → 司机抢单（或系统派单）→ 锁定订单 → 通知双方。 （规模 <6000 司机、<500 单/分钟，单机 + Redis + 消息队列即可胜任。）

—

← 返回题库