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

🎇C++笔试强训

---

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

---

💦🔥

---

选择题

💦第一题

二分查找的时间复杂度（）

A O(N*log(N))
B O(N)
C O(log(N))
D O(N^2)

二分查找的数据要求是有序的，根据前后两个下标得出中间节点，然后拿key和他相比，如果大则在右区间继续找，小则左区间，每次比较会少一半数据，依次重复使用这种方法

得出公式 2 ^ x = n ——》 x = log2(n)

这道题的答案是C

---

💦第二题

有一个单向链表中有一个A、B两个相邻元素，有一个指针p指向元素A，现将一个指针r指向的S元素要插入到A和B之间，该进行操作（）

A p->next=p->next->next
B r-next=p;p->next=r->next
C r->next=p->next;p->next=r
D r=p->next;->next=r->next
E r->next=p;p->next=r
F p=p->next->next

这道题考察单链表的插入，数据结构的题需要多画图

这道题的答案是C

---

💦第三题

双向链表中有两个指针域,llink和rlink分别指向前驱和后继,设p指向链表中的一个结点,现要求删去p所指结点,则正确的删除是()(链中结点数大于2,p不是第一个结点)

A p->llink->rlink:=p->llink; p->llink->rlink:=p->rlink; dispose§;

B dispose§; p->llink->rlink:=p->llink; p->llink->rlink:=p->rlink;

C p->link->rlink:=p->llink; dispose§; p->llink->rlink:=p->rlink;

D 以上A,B,C都不对

已知不是删除头节点

如果要释放节点就会delete p；

这道题的答案是D

---

💦第四题

一个栈的入栈序列是A,B,C,D,E,则栈的不可能输出序列是（）

A EDCBA
B DECBA
C DCEAB
D ABCDE

这是考察栈的性质，栈是后入先出，这种题基本都是送分题

这道题的答案是C

---

💦第五题

循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端
均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正
确的是（）

A 队空：end1 = = end2；队满：end1 = =(end2+1) mod M
B 队空：end1= =end2；队满：end2==(end1+1) mod (M-1)
C 队空：end2==(end1+1) mod M；队满：end1==(end2+1) mod M
D 队空：end1==(end2+1) mod M；队满：end2==(end1+1) mod (M-1)

数据结构的题目需要多画图，只要有图所有的问题都会迎刃而解

这道题的答案是A

---

💦第六题

已知二叉树后序遍历序列是bfegcda，中序遍历序列是badefcg，它的前序遍历序列是（）

A abcdefg
B abdcefg
C adbcfeg
D abecdfg

二叉树必须有中序和其他排序才可以确定二叉树，只需要知道排序方法是怎么样就可以恢复出来了

中序确定左右

这道题的答案是B

---

💦第七题

某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）

A 不存在这样的二叉树
B 200
C 198
D 199

这道题如果知道二叉树的性质，做道题很简单

这道题的答案是B

---

💦第八题

以下序列不是堆的是（）

A (100,85,98,77,80,60,82,40,20,10,66)
B (100,98,85,82,80,77,66,60,40,20,10)
C (10,20,40,60,66,77,80,82,85,98,100)
D (100,85,40,77,80,60,66,98,82,10,20)

A选项是个大堆

B选项也是个大堆

C选项是个小堆

D不是堆

这道题的答案是D

---

💦第九题

设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79}，用链地址法构造哈希表,哈希函数为H(key)=key MOD 13，哈希地址为1的链中有（）个记录

A 1
B 2
C 3
D 4

只要将数据%13 得的值是1 的数据统计起来就可以知道了

这道题的答案是D

---

💦第十题

以下哪种排序是不稳定排序（）

A 冒泡
B 插入排序
C 归并排序
D 快速排序

越快的越不稳定，现实里淹死的都是会游泳的

这道题的答案是D``

---

编程题

🔥 第一题

链接：汽水瓶

• 解题思路

本题题意简单，每次空瓶的数量除以2，直到最后空瓶的数量少于两瓶，就累加到了课兑换的数量。

• 代码演示

#include 
using namespace std;

//方法一：概念法
int calcNumber_1(int n)
{
    int sum = 0;
    while(n > 1)
    {
        int res = n / 3; //所能兑换的个数
        int left = n % 3; //遗留个数

        sum += res;
        n = left + res;

        if(n == 2)
        {
            sum++;
            break;
        }
    }
    return sum;
}

//方法二:取巧法
int calcNumber_2(int n)
{
    return n/2;//观察结果，能喝的数目是空瓶子的一半
}
int main()
{
    int n,res;
    while(cin >> n)
    {
        if(n == 0)
            break;
        //res = calcNumber_1(n);
        res = calcNumber_2(n);
        cout << res << 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

---

🔥 第二题

链接：查找a，b两个字符串中最长的公共子串

• 解题思路

本题需要用动态规划求解，MCS[i][j]记录短字符串 s1 前 i 个字符和长字符串 s2 前 j 个字符的最长子串的长度，初始化所有值为 0。当 s1[i-1] = s2[j-1]时，MCS[i][j] = MCS[i - 1][j - 1] + 1，这里使用一个额外的值start 来记录最长子串在短字符串 s1 中出现的起始位置，maxlen记录当前最长子串的长度，当MCS[i][j] >maxlen 时，maxlen = MCS[i][j]， 则start = i - maxlen ；档s1[i-1] != s2[j-1]时不需要任何操作，最后获取substr(start, maxlen)即为所求。

• 代码演示：

#include 
#include 
#include 
using namespace std;

string getComSubstr(string &str1,string &str2)
{
    if(str1.size() > str2.size())
        swap(str1,str2);

        int len1 = str1.size();
        int len2 = str2.size();

        int start = 0,max_size = 0;

        vector<vector<int>> MSC(len1+1 ,vector<int>(len2+1 , 0));
        for(int i = 1;i < len1;++i)
        {
            for(int j = 1;j < len2;++j)
            {
                if(str2[j - 1] == str1[i - 1])
                    MSC[i][j] = MSC[i - 1][j - 1] + 1;

                if(MSC[i][j] > max_size)
                {
                    max_size = MSC[i][j];
                    start = i - max_size;
                }
            }
        }
        return str1.substr(start,max_size);
}

int main()
{
     string str1,str2;
     while(cin >> str1 >> str2)
     {
         string substr = getComSubstr(str1,str2);
         cout << substr << 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

---