2021届阅文C 方向笔试卷
时长:120分钟 总分:100分
212浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 13 |
1.
找出出现次数最多的整数
给定一个整数集合，集合中可能有重复的数字，输出其中出现次数最多的整数。
如果有多个整数，他们出现的次数相同，并且都是出现次数都是最多的，那么按照这些整数的大小排序，最终输出最大的那个整数。
输入描述：
整数集合，整数之间用空格分隔输入样例：
1 2 2 4 3 5 5 4 6 4 输出描述：
出现次数最多的整数，如果有多个这样的整数，那么输出值最大的那个整数输出样例
4
2.
找第K大的整数
给定一个整数集合，找出第K大的整数。整数集合中可能有重复的元素，对于重复的元素，排名时不重复计入。
举个例子：
假设整数集合为：4 1 9 2 4 8 2 8 7，那么第1大的数是9，第2大的数是8，第3大的数是7。尽管集合有两个8，但不影响7在整个集合中的排名。
输入描述：
第一行为一个整数：K，表示要查找第K大的数
第二行为一个整数集合，整数间用空格分隔
输入样例：
3
4 1 9 2 4 8 2 8 7 输出描述：
第K大的整数
输出样例
7
3.
设计一个scope pointer
C++中如果动态分配的内存没有被正确的删除，那么就会导致内存泄漏，例如以下代码：
void f() {
int *p = new int(3)
std::cout << *p << std::endl
} 当p超出作用域后，由于没有被手动删除，因此会导致内存泄漏。
请设计一个scope pointer：ScopedPtr，其具有以下特点：
1. 使用一个动态分配的int初始化（构造函数）。
2. 当该scope pointer超出作用域后，会自动释放动态分配的内存。
3. 可以通过解引用操作符获取到该动态分配的int的引用。
4. 该scope pointer不能被复制。
请实现该ScopedPtr，可以让以下代码编译通过正常运行：
#include <iostream>
class ScopedPtr {
}
void test(int n) {
ScopedPtr ptr(new int(n))
*ptr *= 2
std::cout << *ptr << std::endl
}
int main () {
int n = 0
std::cin >> n
test(n)
return 0
}
输入描述：
一个整数：N
输入样例：
10 输出描述：
一个整数：N * 2输出样例
20
4.
正整数压缩算法
我们知道一个32位的正整数需要4个字节来表示，但对于3，23这类小的正整数，其实用一个字节就可以表示了，因此我们可以通过一些算法来对32位的正整数进行编码，从而达到压缩的目的。这里我们采用如下方式来压缩正整数：
1. 每个字节由8个bit组成，我们将最高位的bit作为标志位。
2. 如果标志位为0，那么说明后续还有其它字节。
3. 如果标志位为1，那么表示后续没有更多的字节了。
举两个例子：
1. 25的二进制表示为：0001, 1001，因为只需要一个字节表示，因此将其最高bit设置为1，得到压缩后的二进制表示为：1001, 1001。
2. 300的二进制表示为：0000, 0001, 0010, 1100，需要两个字节表示。因此，我们将该二进制的低7个bit拿出来作为最后一个字节，同时由于是最后一个字节，因此，其标志位设置为1，从而得到压缩后的最后一个字节为1010, 1100；去除最低的7个bit后，剩余部分组成前一个字节，同时因为还有后续字节，因此将其标志位设置为0， 从而得到压缩后的字节为：0000, 0010。将两个字节拼接，得到300压缩后的二进制表示：0000, 0010, 1010, 1100
5.
实现一个动态调整大小的数组
我们知道C++的数组需要在编译时决定大小，但很多时候，我们往往不能提前预估数组的大小，为此我们设计一个动态数组，即：当向数组中添加新元素时，如果数组空间不够，那么自动对数组进行扩容；如果从数组中删除了较多元素，那么也可以自动对数组进行缩容。
请实现一个简化的动态数组，该数组存储整数（int），只提供三个操作：
1. 向数组尾部追加一个新元素，如果空间不够，那么自动扩容，同时要求该追加操作的均摊时间复杂度为O(1)：void push(int num)
2. 从数组尾部删除一个元素，如果数组不为空，返回被删除的元素，如果数组为空，返回-1，不执行删除操作。当删除较多元素后，可以对数组进行缩容，但要求从尾部删除元素的操作，均摊时间复杂度为O(1): int pop()
3. 根据数组下标获取对应的整数，如果下标越界，返回-1，时间复杂度O(1)：int get(int idx)
输入描述：
输入为一系列的操作，一行一个操作，操作分为三类：
1. 从尾部追加新元素，格式为：push + 空格 + 整数
2. 删除尾部元素，格式为：pop
3. 根据下标获取元素，格式为：get + 空格 + 下标索引
输入样例：
push 1
push 3
pop
push 4
get 0
get 4 输出描述：
每个操作对应一行输出：
1. 对于push操作，输出push之后数组的大小
2. 对于pop操作，输出pop()函数的返回值，即：删除的整数
3. 对于get操作，输出get()函数的返回值，即：该下标对应的整数
输出样例
1
2
3
2
1
-1
6.
移动构造函数
为类A实现默认构造函数，以std::string为参数的构造函数，移动构造函数（move constructor），重载移动赋值操作符（operator=），析构函数，同时禁止该类进行复制构造（copy constructor），使得以下代码能够运行通过：
#include <iostream>
#include <string>
class A {
public:
std::string s() const {
return *_s
}
private:
std::string *_s
}
int main() {
std::string input
std::cin >> input
A a(input)
A b(std::move(a))
std::cout << b.s() << std::endl
A c
c = std::move(b)
std::cout << c.s() << std::endl
return 0
} 输入描述： 一行字符串输入样例： abcd 输出描述： 两行字符串输出样例 abcd abcd
7.
检查给定字符串中的多种括号是否匹配
给定字符串，检查其中的括号是否匹配（可能出现的括号包括大括号，中括号和小括号），所谓匹配是指：
1. 左右括号应该一一对应，例如：abc(lasdf[lsdf]lasdf，少了一个右小括号，不匹配。
2. 左括号应该出现在对应的右括号的左边，例如：abc)sdf{lkjsdf}sdf(，第一个右小括号前没有左小括号，不匹配。
3. 一对括号之间的字符串，如果出现括号，那么这些括号也必须匹配，例如：abc(dl[lksdflksd)xd]，小括号中出现了一个左中括号（没有对应的右中括号），不匹配
匹配的例子为：abc(dl[lksdf]lksd)，左括号和右括号一一对应，因此匹配
当字符串中括号匹配时，输出字符串：true；如果不匹配，输出字符串：false
输入描述：
一行字符串输入样例：
abc(dl[lksdf]lksd) 输出描述：
如果字符串中括号匹配，那么输出：true
如果不匹配，那么输出：false
输出样例
true
8.
删除vector中的重复元素
给定vector<int>对象，删除其中的重复元素，同时保持元素本来的顺序。
输入描述：
整数集合，整数之间通过空格分隔，将这些整数存入vector<int>后，开始操作
输入样例：
14 5 14 2 8 2 2 9 8 输出描述：
去重后的元素列表，保持元素本来的顺序输出样例
14 5 2 8 9
9.
LRU链表
实现一个LRU链表（元素类型为整形），链表大小为N，当往链表中插入元素时（元素可能重复，如果是插入重复元素，那么不新增元素，只调整元素在链表中的位置），如果链表满了，那么淘汰最近没有被访问（这里只考虑插入这一个访问操作，不考虑查找）的元素，然后插入新元素。当插入M个元素后（M > N），打印链表中的所有元素。
输入描述：
第一行为链表大小N。
第二行为整数集合（可能有重复的元素），整数之间用空格分隔。这个集合的顺序，表示不断访问（插入）的顺序，即：将该集合中的元素逐个插入LRU链表中。
输入样例：
3
1 2 4 2 6 9 6 输出描述：
插入所有元素后，将链表中的元素打印出来。所有元素打印到一行，元素（整数）之间用空格分隔。输出样例
6 9 2
10.
根据IP查询城市
给定IP段到城市的映射表：【起始IP地址，终止IP地址，城市名】，根据给定的IP查询该IP对应的城市名。
其中IP以IPV4的方式给定，例如：10.12.1.3，城市名为一串英文字符，字符间没有空格。例如：
192.15.0.2 192.16.1.5 beijing
168.3.4.5 168.3.6.8 shanghai
177.2.3.4 177.4.5.6 chongqing
168.3.4.5 168.3.6.8 shanghai
177.2.3.4 177.4.5.6 chongqing
映射表中，不同城市的IP地址不重叠，即：不会出现某个城市的起始IP地址小于另一个城市的终止IP地址的情况；一个城市可能有多个IP段（起始IP地址 + 终止IP地址）；可能存在某个IP地址范围没有对应的城市信息。
如果要查询的IP地址属于某个城市，那么输出该城市的名字；如果IP地址不属于任何一个城市，那么输出字符串：none。
输入描述：
第一行为一个整数N，表示映射表有多少条记录。
从第二行开始到第N + 1行为N条IP到城市的映射记录，一行一条记录，每条记录包括起始IP地址，终止IP地址和城市名，这三部分之间用空格分隔。
从第N + 2行开始为需要查询的IP地址，一行一个IP地址。
输入样例：
3
192.15.0.2 192.16.1.5 beijing
168.3.4.5 168.3.6.8 shanghai
177.2.3.4 177.4.5.6 chongqing
192.15.1.2
192.16.2.3
168.2.3.4
168.3.5.9 输出描述：
输出需要查询的IP地址对应的城市名，一行一个城市名，如果IP没有对应的城市信息，那么输出none
输出样例
beijing
none
none
shanghai
11.
找出最大的3个整数
给定一个整数集合（集合中可能有重复的整数），找出其中最大的3个整数，如果最大的3个整数中，有重复的整数，那么去重后，将第4大的整数考虑进来，如果仍然有重复，再考虑第5大的整数……，即：最后输出的结果没有重复的整数。 例如：如果最大的4个整数为10 10 9 7，那么输出：10 9 7
输入描述：
整数集合，整数之间用空格分隔输入样例：
6 3 1 9 3 5 6 输出描述：
输出最大的三个整数，整数之间用空格分隔输出样例
9 6 5
12.
对struct进行排序
给定以下Point类，为其定义小于符号的操作符重载，使得我们可以用std::sort来对vector<Point>进行从小到大的排序（先按x从小到大排，然后按照y从小到大排），确保以下代码成功运行：
#include <iostream>
#include <vector>
#include <algorithm>
struct Point {
int x
int y
}
int main() {
int x = 0
int y = 0
std::vector<Point> vec
while (std::cin >> x >> y) {
Point p
p.x = x
p.y = y
vec.push_back(p)
}
std::sort(vec.begin(), vec.end())
for (auto iter = vec.begin() iter != vec.end() ++iter) {
std::cout << iter->x << " " << iter->y << std::endl
}
return 0
}
输入描述：
点的集合，一个点一行，每个点由x，y两个整数组成，x和y之间用空格分隔
输入样例：
4 6
3 8
4 2
9 6
8 3
9 8 输出描述：
输出格式和输入格式相同，但已经按从小到大排好序了输出样例
3 8
4 2
4 6
8 3
9 6
9 8
13.
删除map中的指定元素
实现以下代码中的remove_elements函数，给定一个std::map<std::string, int>对象，删除其中值为10的所有元素：
#include <iostream>
#include <map>
#include <string>
void remove_elements(std::map<std::string, int> &m) {
}
int main() {
std::map<std::string, int> m
std::string key
int val = 0
while (std::cin >> key >> val) {
m[key] = val
}
remove_elements(m)
for (const auto &ele : m) {
std::cout << ele.first << " " << ele.second << std::endl
}
return 0
}
输入描述：
一行一个key-value数组，key为字符串，value为整数，key和value之间用空格分隔
输入样例：
a 1
b 3
c 10
d 9
e 10 输出描述：
输出格式和输入格式相同，但删除了值为10的key-value pair
输出样例
a 1
b 3
d 9