内存限制：128 MB时间限制：1.000 S
评测方式：文本比较命题人：2011014323
提交：3365解决：1604
题目描述
根据一个递增的整数序列构造有序单链表，删除其中的重复元素
本题是附加代码模式，主函数main和打印链表的代码会自动附加在同学们提交的代码后面，请同学们在提交的时候注释附加代码。
附加代码如下：
void PrintList(const List &list){
Node *p = list->next;
if(p == NULL){
cout<<"list is empty"<<endl;
}else{
while(p != NULL){
cout << p->data << " ";
p = p->next;
}
}
cout << endl;
}
int main(){
int n;
while(cin >> n){
if( n ==0) {
cout<<"list is empty"<<endl;
continue;
}
List list;
InitList(list); // 初始化单链表
for(int i=0;i<n;i++){
int v;
cin >> v;
AddNode(list,v); // 在单链表的末尾增加节点
}
PrintList(list); // 输出链表
RemoveDuplicate(list); // 删除重复元素
PrintList(list); // 再次输出链表
DestroyList(list); // 销毁单链表
}
return 0;
}
输入
输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开
输出
针对每组测试数据，输出包括两行，分别是删除前和删除后的链表元素，用空格隔开 如果链表为空，则只输出一行，list is empty
样例输入 复制
5 1 2 3 4 5
5 1 1 2 2 3
0样例输出 复制
1 2 3 4 5
1 2 3 4 5
1 1 2 2 3
1 2 3
list is empty提示
单链表的结构体定义和相应的操作函数如下图所示：
#include <iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
typedef Node* List;
int InitList(List &list){
return 0;
}
int DestroyList(List &list){
return 0;
}
int AddNode(List &list, int data){
return 0;
}
void RemoveDuplicate(List &list){
}
内存限制：128 MB时间限制：1.000 S
评测方式：文本比较命题人：admin
提交：1714解决：766
题目描述
给定一个顺序存储的线性表，删除线性表中所有小于r且大于l的元素。删除后剩余元素保持顺序存储，相对位置不变。
输入
第一行元素个数n、区间l、r。1<=n<=1e6,0<=l<=r<=1e8.
第二行n个整数，对应顺序表的各元素。对于每个元素Ai满足0<=Ai<=1e8
输出
第一行输出删除后元素的个数
第二行输出删除后顺序表中的元素，没有元素直接换行
样例输入 复制
10 0 4
4 -8 2 12 1 5 9 3 3 10样例输出 复制
6
4 -8 12 5 9 10内存限制：128 MB时间限制：1.000 S
评测方式：文本比较命题人：admin
提交：1168解决：578
题目描述
给定一个顺序存储的线性表，设计算法查找该线性表中最长的连续递增子序列。例如（1,9,2,5,7,3,4,6,8,0）中最长的递增子序列为（3,4,6,8）.
输入
序列长度 n （1<=n<=1e6）
序列元素（整数）a1，a2.....an (1<=ai<=1e9)
输出
最长连续递增子序列（若有多个等长最长连续递增子序列，输出位置靠前的）。
样例输入 复制
15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10样例输出 复制
3 4 6 8题目描述
给你一个链表，链表长度为n，链表内各元素为a1，a2....an，给你一个数m，求链表倒数第m个数是多少。
本题是附加代码模式，主函数main的代码会自动附加在同学们提交的代码后面，请同学们在提交的时候注释掉自己的main函数。
main函数代码如下：
输入
第一行：链表长度n（1<=n<=1e4）
第二行：n个数字，为链表元素从头到尾依次排列
第三行：数字m
输出
输出倒数第m个元素的值并输出换行
样例输入 复制
5
1 2 3 4 5
5 样例输出 复制
1提示
单链表的结构体定义和相应的操作函数如下图所示：
#include <iostream>
#include <cstdio>
using namespace std;
struct Node{
int data;
Node *next;
};
typedef Node* List;
int InitList(List& list){
return 0;
}
int DestroyList(List& list){
return 0;
}
int AddNode(List& list,int v){
return 0;
}
void PrintList(const List& list){
}
// 查找倒数第m个节点
Node* FindMthNode(const List& list, int m){
}
内存限制：128 MB时间限制：1.000 S
评测方式：文本比较命题人：admin
提交：1116解决：621
题目描述
将两个链表表示的递增整数序列合并为一个非递减的整数序列
本题是附加代码模式，以下代码会自动附加在同学们提交的代码后面，请同学们在提交的时候注释掉自己的main函数和链表输出函数。
附加代码如下：
void PrintList(const List &list)
{
List p=list;
while(p->next!=NULL){
p=p->next;
cout << p->data << " ";
}
cout << endl;
}
int main(){
int m,n;
cin >> m >> n;
List listA, listB;
InitList(listA); // 初始化单链表
InitList(listB); // 初始化单链表
for(int i=0;i<m;i++){
int v;cin >> v;
AddNode(listA,v); // 在单链表的末尾增加节点
}
for(int i=0;i<n;i++){
int v; cin >> v;
AddNode(listB, v);
}
List listC = MergeList(listA,listB); //合并两个单链表
PrintList(listC); // 输出单链表
DestroyList(listA); // 销毁单链表
DestroyList(listB); // 销毁单链表
DestroyList(listC); // 销毁单链表
return 0;
}
输入
输入三行，第一行代表两个链表长度，第二三行分别表示两个链表表示的递增序列
输出
输出合并后的序列
样例输入 复制
3 5
1 3 5
2 4 6 8 10样例输出 复制
1 2 3 4 5 6 8 10提示
单链表的结构体定义和相应的操作函数如下所示：
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
};
typedef Node* List;
void InitList(List &list)
{
}
void DestroyList(List &list)
{
}
void AddNode(List &list,int data)
{
}
List MergeList(List &listA,List &listB)
{
List listC;
return listC;
}
内存限制：128 MB时间限制：1.000 S
评测方式：文本比较命题人：admin
提交：744解决：445
题目描述
给你两个一元多项式，输出这两个一元多项式的乘积。
输入
输入包含两行，每行一个一元多项式。
每行开头一个数字n,表示该多项式非零项项数，后面有n组数字，每组数字包含两个数字，按顺序分别为该项的系数和指数。
输出
输出包含一行，按指数从大到小的顺序输出乘积的非0项的系数与指数，以空格分隔开。
如果最终结果为0，直接输出0 0。
样例输入 复制
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1样例输出 复制
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1内存限制：128 MB时间限制：1.000 S
评测方式：文本比较命题人：admin
提交：1149解决：582
题目描述
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。
本题是附加代码模式，主函数main和打印链表的代码会自动附加在同学们提交的代码后面，请同学们在提交的时候注释掉附加代码。
附加代码如下：
void PrintList(const List &list){
Node *p = list->next;
if(p == NULL){
cout<<"NULL"<<endl;
}else{
while(p != NULL){
cout << p->data << " ";
p = p->next;
}
}
cout << endl;
}
int main(){
List listA, listB;
InitList(listA); // 初始化单链表
InitList(listB); // 初始化单链表
int v;
while(cin >> v && v != -1){
AddNode(listA,v); // 在单链表的末尾增加节点
}
while(cin >> v && v != -1){
AddNode(listB,v); // 在单链表的末尾增加节点
}
List listC = GetIntersection(listA,listB); //合并两个单链表
PrintList(listC); // 输出单链表
DestroyList(listA); // 销毁单链表
DestroyList(listB); // 销毁单链表
DestroyList(listC); // 销毁单链表
return 0;
}
输入
输入分为两行，分别在每行给出由若干个正整数构成的非降序序列，用-1表示序列的结尾（-1不属于这个序列）。数字用空格间隔。
输出
在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出“NULL”（不带引号）。
样例输入 复制
1 2 5 -1
2 4 5 8 10 -1样例输出 复制
2 5提示
单链表的结构体定义和相应的操作函数如下图所示：
#include <iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
typedef Node* List;
int InitList(List &list){
return 0;
}
int DestroyList(List &list){
return 0;
}
int AddNode(List &list, int data){
return 0;
}
List GetIntersection(const List &listA, const List &listB){
List listC;
return listC;
}
内存限制：512 MB时间限制：1.000 S
评测方式：文本比较命题人：2011014323
提交：2613解决：1472
题目描述
复习考研累了的时候看看一集二十分钟左右的《生活大爆炸》也不失为一种乐趣。在剧中Sheldon可以说是一个极品，真不知Leonard是如何忍受这位极品室友成天的唠叨。
你知道么？Sheldon有一个神秘的小本本，记录了所有他从小开始讨厌的人名。Stuart这位漫画店老板就是小本本的一员哦，谁叫他常常毫不客气地挤兑Sheldon，曾多次赌赢过Sheldon呢。
Penny是一个漂亮的女孩，好奇心也很强。为了满足她的好奇心，我当回编剧让她意外知道了Sheldon的那个小本本放在了哪里。于是她几乎每天都去看，看看上面有哪些人。但是那个小本本上的人名实在太多。要知道她可是没上过大学在饭店里面当服务员啊。请聪明的你帮帮她处理处理那个小本本吧。
图1：《生活大爆炸》里的角色
Sheldon每天都会在小本本里记录些人名，当然有时也会与他们和好就会从小本本中将这个人名删除。我们假设Sheldon会在一个空的小本本上插入、删除、查询某个人。
要帮助Penny，你需要知道一个顺序表是怎么初始化、插入、删除以及查找的。下面我就将这些算法列举在下方。
图2：线性表的动态分配顺序存储结构以及初始化
图3：线性表的插入算法
图4：线性表的删除算法
图5：线性表的查找算法
输入
输入数据只有一组，有很多行。每行的格式可能是下列一种：
insert a name
delete name
show
search name
其中 a 是一个整数，代表在第a个名字前插入名字。name是一个姓名，只包含英文字母的大小写，每个名字不超过30个字符。
输入保证不会插入列表中已经存在的姓名，不会删除列表中不存在的姓名，也不会搜索列表中不存在的姓名。
输出
起始时，列表是空的。只输出show和search name 的结果。show将列表中的姓名全部输出，search只输出找到该名字的序号（从1开始）。每次输出占一行，姓名间用空格隔开。如果列表中没有名字了，show时也要输出一个空行。
样例输入 复制
insert 1 Stuart
insert 2 Bernadette
show
search Stuart
delete Stuart
show
insert 2 Stuart
show
insert 1 Amy
insert 2 Leslie
insert 3 Stephanie
show
delete Leslie
show
search Stuart样例输出 复制
Stuart Bernadette
1
Bernadette
Bernadette Stuart
Amy Leslie Stephanie Bernadette Stuart
Amy Stephanie Bernadette Stuart
4提示
提示：
1、名字是不含空格的，指令也是一定的，所以可以用scanf("%s", str)来读取。
2、上述代码有些函数头中变量类型与变量之间有个&，这个表示该变量是引用类型的，是C++特性。在C语言中存在值传递与指针传递，值传递中形参不可以改变实参的值，需要通过指针来修改。而引用变量实际上就是实参的另一个名字，这种类型的形参改变会影响实参的值。
3、使用题目中的代码需要自己定义其中缺失的类型和变量，例如Status、OK以及Error等。
4、ElemType类型中可以只有一个字符数组用来存储姓名。
5、LocateElem_Sq函数在调用时需要传递一个函数指针，可以这样定义： Status cmp(ElemType e1, ElemType e2); 注意这个函数用来判断e1和e2是否相等，如果相等则返回非零值，否则返回0。因此可以在这个函数里直接返回 !strcmp(...)但最好需要改变返回类型。
6、内存分配以及字符串操作需要的头文件分别是stdlib.h和string.h需要被包含进来。
7、题目要求每个输出占一行，所以要注意换行。
总结：
1、实际上，题目中几乎将主要代码都写出来了。解决这道题使用上面的代码是可能复杂了点，但将各个功能独立出来是个不错的思路。以后修改就方便了，特别适用于代码量较大的程序。
2、C语言中参数的传递分为值传递和指针传递，而C++中多了一个引用传递。值传递和指针传递都不可以改变传递进来的值，但指针可以改变其所指向的值。在C语言中，调用函数时传入的参数叫做“实参”，而在函数声明或定义中在函数头中的参数叫做“形参”。值传递与指针传递中，形参的改变是不影响实参的。C++中，引用传递，形参与实参实际上是同一个内容的不同名字，因而形参的变化会改变实参。引用传递是C++中一个很重要也很方便的特性，比如在可能会产生不必要的复制时，采用引用传递是一个很不错的解决方案。
内存限制：128 MB时间限制：1.000 S
评测方式：文本比较命题人：2011014323
提交：3398解决：1681
题目描述
根据一个整数序列构造一个单链表，然后将其反转。
例如：原单链表为 2 3 4 5 ，反转之后为5 4 3 2
本题是附加代码模式，主函数main和打印链表的代码会自动附加在同学们提交的代码后面，请同学们在提交的时候注释掉附加代码。
附加代码如下：
void PrintList(const List &list){
Node *p = list->next;
if(p == NULL){
cout<<"list is empty"<<endl;
}else{
while(p != NULL){
cout << p->data << " ";
p = p->next;
}
}
cout << endl;
}
int main(){
int n;
while(cin >> n){
if( n ==0) {
cout<<"list is empty"<<endl;
continue;
}
List list;
InitList(list); // 初始化单链表
for(int i=0;i<n;i++){
int v;
cin >> v;
AddNode(list,v); // 在单链表的末尾增加节点
}
PrintList(list); // 输出链表
ReverseList(list); // 反转链表
PrintList(list); // 再次输出链表
DestroyList(list); // 销毁单链表
}
return 0;
}
输入
输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开
输出
针对每组测试数据，输出包括两行，分别是反转前和反转后的链表元素，用空格隔开 如果链表为空，则只输出一行，list is empty
样例输入 复制
5 1 2 3 4 5
0样例输出 复制
1 2 3 4 5
5 4 3 2 1
list is empty提示
单链表的结构体定义和相应的操作函数如下图所示：
#include <iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
typedef Node* List;
int InitList(List &list){
return 0;
}
int DestroyList(List &list){
return 0;
}
int AddNode(List &list, int data){
return 0;
}
void ReverseList(List &list){
}
内存限制：128 MB时间限制：1.000 S
评测方式：文本比较命题人：外部导入
提交：1479解决：645
题目描述
N个人围成一圈，从第一个人开始报数，数到M的人出圈；再由下一个人开始报数，数到M的人出圈；……输出依次出圈的人的编号。N，M由键盘输入。
输入
一行，包含两个正整数N，M。1<=N,M<=100。
输出
先输出一个空行，再依次出圈的人的编号。每个编号后都有一个空格。
样例输入 复制
8 5
样例输出 复制
5 2 8 7 1 4 6 3