【C++笔试强训】第二十一天

🎇C++笔试强训

---

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

---

💦🔥

---

选择题

💦第一题

设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度（）

A O(log2n)
B O(1)
C O(n2)
D O(n)

注意是是有序的单链表，要保证插入是有序的，所以要先遍历链表，所以跟元素个数有关，所以是O（n）

这道题的答案是D

---

💦第二题

在一个单链表中，若删除 P 所指结点的后续结点，则执行?

A p = p->next；p->next = p->next->next;
B p->next = p->next;
C p->next = p->next->next;
D p = p->next->next

这道题的答案是C

---

💦第三题

设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用()最节省时间

A 带头结点的双循环链表
B 单循环链表
C 带尾指针的单循环链表
D 单链表

需要尾插尾删，需要找到他的前驱节点

如果是单链表和单循环链表，需要把链表遍历一次，到最后才能找到前驱节点

而带头双向链表可以通过头节点找到最后一个位置的前驱

带尾指针的单循环链表即使找到了，也要有一个指针遍历到尾部

这道题的答案是A

---

💦第四题

单链表实现的栈，栈顶指针为Top(仅仅是一个指针)，入栈一个P节点时，其操作步骤为（）

A Top->next=p;
B p->next=Top->next;Top->next=p;
C p->next=Top;Top=p->next;
D p->next=Top;Top=Top->next;

这道题是用链表实现栈，入栈是进行头插，其实会分有无头节点两种情况，所以需要根据答案来看

这道题的答案是B

---

💦第五题

用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）

A 仅修改队头指针
B 仅修改队尾指针
C 队头、队尾指针都可能要修改
D 队头、队尾指针都要修改

出队是头删，入队是尾插

如果队列里面只有一个元素，所以出队需要修改队头和队尾

这道题的答案是C

---

💦第六题

在具有 2n 个结点的完全二叉树中，叶子结点个数为（）

A n
B n+1
C n-1
D n/2

这种题虽然是考察性质，但是做题的时候只需要按照完全二叉树的方式构造，然后代入就可以知道了

这道题的答案是A

---

💦第七题

在任意一棵非空二叉排序树T1中， 删除某结点v之后形成二叉排序树 T2，再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（ ）。

I．若 v 是 T1的叶结点，则 T1 与 T3 不同

II． 若 v 是 T1的叶结点，则 T1与 T3相同

III．若 v 不是 T1 的叶结点，则 T1 与 T3 不同

IV．若v 不是 T1 的叶结点，则 T1 与 T3 相同

A 仅 I、 III
B 仅 I、 IV
C 仅 II、 III
D 仅 II、 IV

二叉排序树是二叉搜索树，我们随便弄一颗出来

数据结构画图是关键

这道题的答案是C

---

💦第八题

下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）

A 二叉排序树
B 哈夫曼树
C AVL树
D 堆

从任意叶子到根有序，根据上题的图可以二叉排序树不是，哈夫曼树是最小生成树，哈夫曼树加权的值是不存在数据内的，所以不行，AVL是高度平衡化的二叉搜索树，只要求高度平衡，也不一定有序，而堆排序是大堆或者小堆，所以一定有序

这道题的答案是D

---

💦第九题

散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。由于散列函数不是一对一的关系，所以选择好的（ ）方法是散列文件的关键。

A 散列函数
B 除余法中的质数
C 冲突处理
D 散列函数和冲突处理

哈希表的冲突问题是不可避免的，所以最好的方法是选择一个好的函数和冲突处理

这道题的答案是D

---

💦第十题

将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是（）

A 2-6-3-5-4-1-7
B 6-2-3-5-4-1-7
C 6-5-3-2-4-1-7
D 1-4-7-5-6-3-2

我们先把数据建个大堆，因为需要升序排列

然后将堆顶元素跟最后一个元素交换，然后调整成大堆

这道题的答案是C

---

编程题

🔥 第一题

链接：洗牌

• 题目解析

本题题目的意思是模拟洗牌过程，牌被分成两组，且每组数量相等，然后每组牌从最后一个牌交叉排列，最
后再把排列逆序就是一次洗牌的过程，K次需要重复K次这样的过程。

• 解题思路

每次读取一个数之后，算出他经过k次洗牌后的位置，只用一个长度为2n数组用来输出

根据当前数的位置，可以算出经过一次洗牌后的位置

如果当前数小于等于n（即在左手），则他下次出现的位置是 2*当前位置

与之对应的当前位置 + n（即在右手）的牌,则他下次出现的位置是 2*当前位置 + 1

• 代码演示

#include 
#include 
using namespace std;

int main()
{
    int T,n,k;
    cin >> T;
    while(T--)
    {
        cin >> n >> k;
        int num = 2 * n;
        vector<int> card(num);

        for(int i = 0;i < num;i++)
            cin >> card[i];

        //开始洗牌
        for(int i = 0;i < k;++i)
        {
            vector<int> tmp(card.begin(),card.end());
            for(int j = 0;j < n;j++)
            {
                card[2*j] = tmp[j];//左手牌排放的位置
                card[2*j+1] = tmp[j+n];//右手牌排放的位置
            }
        }

        //输出洗牌的顺序
        for(int i = 0;i < num -1 ;++i)
        {
            cout << card[i] << " ";
        }
        cout << card[num-1] << 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

---

🔥 第二题

链接：MP3光标位置

• 题目解析

本题的意思是第一行输入歌曲数量，第二行输入指令，最后需要显式的输出也为两行，第一行为当前歌曲所在的列表，第二行为光标所指向的歌曲。

• 解题思路

本题比较简单，通过解析指令，进行移动即可，分两种情况，歌曲数目不大于4和大于4的情况。

• 代码演示

#include 
#include 
using namespace std;

int main()
{
    int n;
    string cmd;
    while(cin >> n >> cmd)
    {
        //将n首歌进行编号1:n，其中num代表当前光标所在的歌曲编号，first代表当前页的第一首歌编号
        int num = 1,first = 1;
        if(n <= 4)//歌曲小于4
        {
            for(int i = 0;i < cmd.size();++i)
            {
                //解析命令
                if(num == 1 && cmd[i] == 'U')
                    num = n;
                else if(num == n && cmd[i] == 'D')
                    num = 1;
                else if(cmd[i] == 'U')
                    num--;
                else
                    num++;
            }
            for(int i = 1;i <= n;++i)
            {
                cout << i << " ";
            }
            cout << endl;
            cout << num << endl;
        }
        
        else
        {
            for(int i = 0;i < cmd.size();++i)
            {
                if(first == 1 && num == 1 && cmd[i] == 'U')
                {
                    first = n - 3;//将first跳入最后一页
                    num = n;
                }
                else if(first == n - 3 && num == n && cmd[i] == 'D')
                {
                    first = num = 1;
                }
                else if(first != 1 && num == first && cmd[i] == 'U')
                {
                    first--;
                    num--;
                }
                else if(first != n-3 && num == first + 3 && cmd[i] == 'D')
                {
                    first++;
                    num++;
                }
                else if(cmd[i] == 'U')
                    num--;
                else
                    num++;
            }
            for(int i = first;i <= first+3;++i)
            {
                cout << i << " ";
            }
            cout << endl;
            cout << num << 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

---