一、编程题
1、【请在自己电脑上的编程软件上做 C语言没有标准答案 运行测试无误即为正确】
字符串插入
有两个字符串str和substr，str的字符个数不超过10，substr的字符个数为3。（字符个数不包括字符串结尾处的’\0’。）将substr插入到str中ASCII码最大的那个字符后面，若有多个最大则只考虑第一个。
时间限制：1000
内存限制：65536
输入
输入包括若干行，每一行为一组测试数据，格式为 str substr
输出
对于每一组测试数据，输出插入之后的字符串。
样例输入
abcab eee
12343 555
样例输出
abceeeab
12345553
参考答案：
无
解析：【喵呜刷题小喵解析】本题要求将字符串substr插入到字符串str中ASCII码最大的那个字符后面，若有多个最大则只考虑第一个。首先，我们需要定义三个字符数组：str、substr和output。其中，str和substr用于存储输入，output用于存储输出。然后，我们使用一个循环来读取输入，直到文件结束。对于每一组输入，我们遍历str，找到ASCII码最大的字符的索引，并将substr插入到该字符后面。具体实现时，我们使用两个指针i和j来遍历str和output。当i指向的字符是最大ASCII码字符时，我们将substr插入到output中，并将i加1，以便跳过已经插入的substr。否则，我们将str中的字符插入到output中。最后，我们在output的末尾添加字符串结束符'\0'，并输出output。注意，本题的时间限制和内存限制很小，因此我们需要尽可能地优化算法。在本题中，我们可以使用指针来遍历字符串，避免使用字符串函数，以提高效率。
2、机器翻译
VariantF的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M，软件会将新单词存入一个未使用的内存单元；若内存中已存入M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
时间限制：1000
内存限制：262144
输入
第一行为两个正整数M 和N，代表内存容量和文章的长度。 第二行为N 个非负整数，按照文章的顺序，每个数（大小不超过1000000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。 对于50%的数据，1<=N、M<=1000； 对于100%的数据，1<=N、M<=1000000。
输出
一个整数，为软件需要查词典的次数。
样例输入
3 7
1 2 1 5 4 4 1
样例输出
5
提示
整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况: 空：内存初始状态为空。 1． 1：查找单词1 并调入内存。 2． 1 2：查找单词2 并调入内存。 3． 1 2：在内存中找到单词1。 4． 1 2 5：查找单词5 并调入内存。 5． 2 5 4：查找单词4 并调入内存替代单词1。 6． 2 5 4：在内存中找到单词4。 7． 5 4 1：查找单词1 并调入内存替代单词2。 共计查了5 次词典。
参考答案：
无
解析：【喵呜刷题小喵解析】：本题主要考察编程和算法。机器翻译软件需要按照题目中描述的工作机制来运行，同时记录软件需要去外存查找词典的次数。1. 创建一个空的内存列表`memory`来存储已存入内存的单词。2. 遍历输入文章中的每个单词。3. 如果内存列表的长度小于内存容量`M`，则将新单词添加到内存列表的末尾。4. 如果内存列表的长度等于内存容量`M`，则需要清空最早进入内存的那个单词，腾出单元来，存放新单词。5. 如果新单词不在内存列表中，则需要去外存查找词典，并将查找到的单词和译义放入内存。6. 在整个翻译过程中，记录查找词典的次数`dictionary_lookup`。本题的解题思路就是根据题目描述模拟机器翻译软件的工作过程，同时统计查找词典的次数。【喵呜AI答案】中的代码实现了上述思路，首先定义了一个函数`translation_software`，接受内存容量`M`、文章长度`N`和文章中的单词列表`words`作为输入，返回查找词典的次数。然后在主程序中读取输入，调用函数并输出结果。
3、栈基本操作
依次读入序列元素1,2,…,n进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行。给定一个输入序列，判断栈空时弹出的元素构成的序列是否可能等于给定的序列，如果是则输出栈的操作过程，否则输出"NO"。
时间限制：1000
内存限制：65535
输入
输入分两行 第一行为n的值（即序列元素个数） 第二行为给定的输入序列（序列元素均为整型）
输出
如果输入序列能够由题目规定的操作得到，则输出对栈的操作过程 否则直接输出"NO"
样例输入
7
4 5 3 6 2 7 1
样例输出
PUSH 1
PUSH 2
PUSH 3
PUSH 4
POP 4
PUSH 5
POP 5
POP 3
PUSH 6
POP 6
POP 2
PUSH 7
POP 7
POP 1
提示
给定序列中有可能有不在1…n之间的数字
参考答案：
无
解析：【喵呜刷题小喵解析】本题要求判断给定的输入序列是否可以通过栈的操作得到，并输出栈的操作过程。栈的基本操作包括进栈和出栈，每次进栈的元素可能是当前未进栈的最小元素，也可以是下一个未进栈的元素。算法的思路是，首先遍历输入序列，依次将未进栈的元素压入栈中，并输出相应的进栈操作。然后判断栈顶元素是否为当前序列的下一个元素，如果是，则弹出栈顶元素，并输出相应的出栈操作。如果栈为空，且序列已遍历完，说明可以通过栈的操作得到给定的序列。否则，说明无法通过栈的操作得到给定的序列，输出"NO"。在算法实现中，我们使用一个列表来模拟栈，列表的最后一个元素即为栈顶元素。遍历输入序列时，将未进栈的元素压入列表，并输出相应的进栈操作。然后判断列表的最后一个元素是否为当前序列的下一个元素，如果是，则弹出列表的最后一个元素，并输出相应的出栈操作。如果列表为空，且序列已遍历完，说明可以通过栈的操作得到给定的序列。否则，说明无法通过栈的操作得到给定的序列，输出"NO"。需要注意的是，由于栈的先进后出特性，我们在遍历输入序列时，需要将未进栈的元素按照从小到大的顺序压入栈中。另外，如果栈为空，且序列未遍历完，说明无法通过栈的操作得到给定的序列，直接输出"NO"。最后，我们需要注意题目中的提示，即给定序列中有可能有不在1...n之间的数字。这个提示并不影响我们的算法实现，因为我们的算法只需要判断给定的序列是否可以通过栈的操作得到，而不需要关心序列中的元素是否在1...n之间。
4、双端队列
定义一个双端队列，进队操作与普通队列一样，从队尾进入。出队操作既可以从队头，也可以从队尾。编程实现这个数据结构。
时间限制：1000
内存限制：65535
输入
第一行输入一个整数t，代表测试数据的组数。 每组数据的第一行输入一个整数n，表示操作的次数。 接着输入n行，每行对应一个操作，首先输入一个整数type。 当type=1，进队操作，接着输入一个整数x，表示进入队列的元素。 当type=2，出队操作，接着输入一个整数c，c=0代表从队头出队，c=1代表从队尾出队。 n <= 1000
输出
对于每组测试数据，输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开，按队头到队尾的顺序输出，占一行。如果队列中已经没有任何的元素，输出NULL。
样例输入
2
5
1 2
1 3
1 4
2 0
2 1
6
1 1
1 2
1 3
2 0
2 1
2 0
样例输出
3
NULL
参考答案：
无
解析：【喵呜刷题小喵解析】本题要求实现一个双端队列，其中进队操作与普通队列一样，从队尾进入。出队操作既可以从队头，也可以从队尾。我们可以使用一个列表来模拟双端队列，其中队尾为列表的末尾，队头为列表的开头。进队操作即向列表末尾添加元素，出队操作从列表开头或末尾删除元素。根据题目要求，我们需要进行如下步骤：1. 定义一个双端队列类，包含进队和出队操作。2. 读入测试数据的组数t，对于每组数据，读入操作次数n。3. 对于每个操作，读入操作类型type和对应的元素x或出队位置c。4. 根据操作类型执行对应的操作，并输出执行完所有的操作后队列中剩余的元素。在Python中，我们可以使用列表的append()方法实现进队操作，使用pop(0)方法实现从队头出队操作，使用pop()方法实现从队尾出队操作。需要注意的是，当队列为空时，从队头或队尾出队操作都应该返回"NULL"。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
