【C++笔试强训】第十八天

🎇C++笔试强训

---

• 博客主页：一起去看日落吗
• 分享博主的C++刷题日常，大家一起学习
• 博主的能力有限，出现错误希望大家不吝赐教
• 分享给大家一句我很喜欢的话：夜色难免微凉，前方必有曙光 🌞。

---

💦🔥

---

选择题

💦第一题

以下关于STL的描述中，（）是错的

A STL容器是线程不安全的
B 当容量不够时，STL的一个典型实现是vector内部内存扩展方式为翻倍
C std::sort是稳定排序
D std::bitset不是一个STL容器

这道题是关于STL的

STL容器都是线程不安全的，一旦放在多线程里面，需要用户自己加锁

当容量不够时，STL的一个典型实现是vector内部内存扩展方式为翻倍，有的版本是二倍，有些是1.5倍

std::sort是排序算法，底层是个插入排序和快排，快排的特点是不稳定

bitset是一个位集合，不是一个容器，并不是装类型，是装二进制位，容器可以装很多类型不同的集合

这道题的答案是C

---

💦第二题

以下STL的容器存放的数据，哪个肯定是排好序的（）

A vector
B deque
C list
D map

map的底层是红黑树，是棵二叉排序树，是按中序遍历的，所以肯定是排序好的

这道题的答案是D

---

💦第三题

以下哪种STL容器中的对象是连续存储的（）

A list
B vector
C map
D set

map 和 set 都是红黑树

只有向量vector是连续存储的

这道题的答案是B

---

💦第四题

STL中的哪种结构在增加成员时可能会引起原有成员的存储位置发生改变（）

A map
B set
C list
D vector

可能会引起原有成员的存储位置发生改变，一般会发生在连续程序里面，插入需要扩容

这道题的答案是D

---

💦第五题

STL中的一级容器有:

A vector, deque, list, set, multiset, map, multimap.
B 序列容器，关联容器，容器适配器
C set, multiset, map, multimap.
D vector, deque, list.

这道题要了解一个问题，STL一般是通过维度来分的

vector, deque, list.都是基本类型，不牵扯组合类型

这道题的答案是D

---

💦第六题

STL中的unordered_map和priority_queue使用的底层数据结构分别是什么（）

A rbtree,queue
B hashtable,heap
C rbtree,heap
D hashtable,queue

底层结构指的是适配器，STL有六大组件，空间适配器，容器，算法，迭代器，仿函数，适配器

适配器常见的是stack 和 queue ——> 通过deque实现的
priority_queue——> vector
map set ——> rbtree
unordered_map —— hash_map ——> hashtable
unordered_set —— hash_set

unordered_map实现的是哈希表，priority_queue默认实现一个大堆

这道题的答案是B

---

💦第七题

下面关于迭代器失效的描述哪个是错误的（）

A vector的插入操作不会导致迭代器失效
B map的插入操作不会导致迭代器失效
C vector的删除操作只会导致指向被删除元素及后面的迭代器失效
D map的删除操作只会导致指向被删除元素的迭代器失效

vector的插入操作最有可能导致迭代器失效

一般是插入或者删除可能会导致迭代器失效，但每种容器具体情况可能不一样，需要具体分析，插入和删除需要扩容和挪动数组

map的插入操作不会导致迭代器失效，只需要修改新插入节点的指针

vector的删除操作只会导致指向被删除元素及后面的迭代器失效，删除后数据会往前移动

map的删除操作只会导致指向被删除元素的迭代器失效

这道题的答案是A

---

💦第八题

如何捕获异常可以使得代码通过编译？

class A {
public:
	A(){}
};
void foo(){
	throw new A;
}
1
2
3
4
5
6
7

A catch (A && x)
B catch (A * x)
C catch (A & x)
D 以上都是

• throw:抛出异常信息,类似于执行返回语句,因为它将终止函数的执行,但是它不是将控制权交给调用程序,而是导致程序沿着函数调用序列后退,直到找到包含try块的函数.
• catch:类似于函数定义,但并不是函数定义,关键字catch表明这是给一个处理程序, 里面的A *x 会接受throw传过来错误信息.

题目中问的是能否通过编译，只有B会捕获到异常，进行异常处理，而A和C由于和throw抛出的异常类型不匹配，导致这个异常不被捕获，从而成为未捕获的异常，调用terminate函数结束程序。

这道题的答案是B

---

💦第九题

有如下程序段：

#include 
using namespace std;
class A {
public:
	~A() {
		cout << "~A()";
	}
};
class B{
public:
	virtual ~B() {
		cout << "~B()";
	}
};
class C: public A, public B {
public:
	~C() {
		cout << "~C()";
	}
};
int main() {
	C * c = new C;
	B * b1 = dynamic_cast<B *>(c);
	A * a2 = dynamic_cast<A *>(b1);
	delete a2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

则程序输出：

A _C()B()~A()
B _C()A()~B()
C A)B)都有可能
D 以上都不对

这道题考的是动态转换

main()函数中，第一句只用了new，调用了构造函数，没用delete，不会调用析构函数，内存泄露。第二句、第三句只是定义了指向不同对象的指针，不会产生对象，所以构造函数、析构函数都没调用，最后一句delete调用析构函数，因为基类A的析构函数不是虚函数，所以只调用A的析构函数，输出：~A()，如果A的析构函数加上virtual, 输出：~~C()~~B()~A()，与直接delete c输出一样。 析构函数声明为虚函数，这样析构时，先调用派生类的析构函数，再调用基类的析构函数，防止内存泄露。

这道题的答案是D

---

💦第十题

以下程序输出结果是____

class A
{
public:
	A ():m_iVal(0){test();}
	virtual void func() { std::cout<<m_iVal<<‘ ’;}
	void test(){func();}
	public:
	int m_iVal;
};
class B : public A
{
public:
	B(){test();}
	virtual void func()
	{
		++m_iVal;
		std::cout<<m_iVal<<‘ ’;
	}
};
int main(int argc ,char* argv[])
{
	A*p = new B;
	p->test();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

A 1 0
B 0 1
C 0 1 2
D 2 1 0
E 不可预期
F 以上都不对

这道题的答案是C

---

编程题

🔥 第一题

链接：统计每个月兔子的总数

• 解题思路

第n个月的兔子数量由两部分组成，一部分是上个月的兔子f(n-1)，另一部是满足3个月大的兔子，会生一只兔
子f(n-2)。所以第n个月兔子总数： f(n) = f(n - 1) + f(n - 2)。本题是在变相考察斐波那契数列。

• 代码演示

#include 
using namespace std;

//迭代法
// int Fib(int n)
// {
//     if(n <= 2)
//         return 1;
//     int f,f1 = 1,f2 = 1;
//     for(int i = 3 ;i <= n;++i)
//     {
//         f = f1 + f2;
//         f1 = f2;
//         f2 = f;
//     }
//     return f;
// }


//递归法,如果数据过大可能会栈溢出
int Fib(int n)
{
    if(n <= 2)
        return 1;
    return Fib(n-1)+Fib(n-2);
}

int main()
{
    int month;
    int sum = 0;
    while(cin >> month)
    {
        sum = Fib(month);
        cout << sum << endl; 
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

🔥 第二题

链接：字符串通配符

• 解题思路

本题可以通过递归求解。从前向后一次匹配，遇到相同字符，都向后移动一个字符，如果通配符遇到"?“，则
不需匹配，自动跳过一个字符，如果通配符遇到”*"，则可以匹配任意多个字符，包括0个，此时可以有三种
选择，1，匹配0个，通配符向后移动一个字符，字符串不动。2，匹配1个，通配符和字符串都向后移动一个
字符。3，匹配多个，通配符不动，字符串向后移动一个字符。

递归的终止条件：通配符或者字符串遇到’\0’。当他们同时结束。

• 代码演示

#include 
#include 
using namespace std;
bool match(const char* pattern, const char* str) {
    //当前字符结束，返回true
    if (*pattern == '\0' && *str == '\0')
        return true;
    //两个字符串有一个先结束，则返回false
    if (*pattern == '\0' || *str == '\0')
        return false;
    if (*pattern == '?') {
    //新增用例，题目强调?只能够匹配数字和字母，所以增加新的判断
        if (!isdigit(*str) && !isalpha(*str))
            return false;
    //遇到?号，匹配一个字符，跳过一个位置
        return match(pattern + 1, str + 1);
    } else if (*pattern == '*') {
    // 遇到*号，匹配0个(str不挪动)，1个（两者都向前挪动一个字符）或多个(str向前挪动一个字符)
        while (*pattern == '*') {
            pattern++;
        }
        pattern--;
        if (!isdigit(*str) && !isalpha(*str))
            return match(pattern + 1, str);
        return match(pattern + 1, str) || match(pattern + 1, str + 1) ||
               match(pattern, str
                     + 1);
    } else if (tolower(*pattern) == tolower(*str)) {
     //忽略大小写
    //如果当前字符相等，匹配下一个字符
        return match(pattern + 1, str + 1);
    }
    return false;
}
int main() {
    string pattern, str;
    while (cin >> pattern >> str) {
        bool ret = match(pattern.c_str(), str.c_str());
        if (ret)
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---