167 lines
3.8 KiB
Markdown
167 lines
3.8 KiB
Markdown
``` html
|
||
A 单链表基本操作
|
||
分数 10
|
||
作者 朱允刚
|
||
单位 吉林大学
|
||
请编写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列，输出实施上述操作后的链表。单链表数据域值为整数。
|
||
|
||
输入格式:
|
||
输入第1行为1个正整数n，表示当前单链表长度；第2行为n个空格间隔的整数，为该链表n个元素的数据域值。第3行为1个正整数m，表示对该链表施加的操作数量；接下来m行，每行表示一个操作，为2个或3个整数，格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个数据域值为d的结点，若k=0则表示表头插入。1 k表示删除链表中第k个结点，此时k不能为0。注：操作序列中若含有不合法的操作（如在长度为5的链表中删除第8个结点、删除第0个结点等），则忽略该操作。n和m不超过100000。
|
||
|
||
输出格式:
|
||
输出为一行整数，表示实施上述m个操作后的链表，每个整数后一个空格。输入数据保证结果链表不空。
|
||
|
||
输入样例:
|
||
5
|
||
1 2 3 4 5
|
||
5
|
||
0 2 8
|
||
0 9 6
|
||
0 0 7
|
||
1 0
|
||
1 6
|
||
|
||
输出样例:
|
||
7 1 2 8 3 5
|
||
|
||
代码长度限制
|
||
16 KB
|
||
Python (python3)
|
||
时间限制
|
||
1000 ms
|
||
内存限制
|
||
256 MB
|
||
Java (javac)
|
||
时间限制
|
||
5000 ms
|
||
内存限制
|
||
256 MB
|
||
其他编译器
|
||
时间限制
|
||
100 ms
|
||
内存限制
|
||
10 MB
|
||
栈限制
|
||
8192 KB
|
||
|
||
---
|
||
|
||
B 栈的实现及基本操作
|
||
分数 10
|
||
作者 朱允刚
|
||
单位 吉林大学
|
||
给定一个初始为空的栈和一系列压栈、弹栈操作，请编写程序输出每次弹栈的元素。栈的元素值均为整数。本题不允许使用stack、queue、vector等STL容器。
|
||
|
||
输入格式:
|
||
输入第1行为1个正整数n，表示操作个数；接下来n行，每行表示一个操作，格式为1 d或0。1 d表示将整数d压栈，0表示弹栈。n不超过20000。
|
||
|
||
输出格式:
|
||
按顺序输出每次弹栈的元素，每个元素一行。若某弹栈操作不合法（如在栈空时弹栈），则对该操作输出invalid。
|
||
|
||
输入样例:
|
||
7
|
||
1 1
|
||
1 2
|
||
0
|
||
0
|
||
0
|
||
1 3
|
||
0
|
||
|
||
输出样例:
|
||
2
|
||
1
|
||
invalid
|
||
3
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
10 MB
|
||
栈限制
|
||
131000 KB
|
||
|
||
---
|
||
|
||
C 队列的实现及基本操作
|
||
分数 10
|
||
作者 朱允刚
|
||
单位 吉林大学
|
||
给定一个初始为空的队列和一系列入队、出队操作，请编写程序输出每次出队的元素。队列的元素值均为整数。
|
||
备注：本题不允许使用stack、queue、vector等STL容器。
|
||
|
||
输入格式:
|
||
输入第1行为1个正整数n，表示操作个数；接下来n行，每行表示一个操作，格式为1 d或0。1 d表示将整数d入队，0表示出队。n不超过20000。
|
||
|
||
输出格式:
|
||
按顺序输出每次出队的元素，每个元素一行。若某出队操作不合法（如在队列空时出队），则对该操作输出invalid。
|
||
|
||
输入样例:
|
||
7
|
||
1 1
|
||
1 2
|
||
0
|
||
0
|
||
0
|
||
1 3
|
||
0
|
||
|
||
输出样例:
|
||
1
|
||
2
|
||
invalid
|
||
3
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
20 MB
|
||
栈限制
|
||
8192 KB
|
||
|
||
---
|
||
|
||
D KMP模式匹配算法
|
||
分数 10
|
||
作者 朱允刚
|
||
单位 吉林大学
|
||
给定目标串s和模式串p，编写程序使用KMP算法进行模式匹配，计算p在s中首次出现的位置，若p不在s中则输出−1。字符串下标从0开始。
|
||
|
||
输入格式:
|
||
输入为2行，第1行为主串s，第2行为模式串p。主串和模式串长度不超过10
|
||
5
|
||
。
|
||
|
||
输出格式:
|
||
输出为2行，第1行为3个整数，表示分别在模式串p的p
|
||
m/4
|
||
|
||
,p
|
||
2m/4
|
||
|
||
,p
|
||
3m/4
|
||
|
||
处失配后，模式串下一次匹配的位置（即next[j]或f[j−1]+1的值，j=m/4,2m/4,3m/4），每个整数后一个空格，m表示模式串p的长度；第2行为一个整数，表示p在s中首次出现的位置，若p不在s中则输出−1。
|
||
|
||
输入样例:
|
||
qwerababcabcabcabcdaabcabhlk
|
||
abcabcabcabc
|
||
|
||
输出样例:
|
||
0 3 6
|
||
6
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
20 ms
|
||
内存限制
|
||
10 MB
|
||
栈限制
|
||
8192 KB
|
||
|
||
``` |