西交软件915历年真题_编程题汇总与分析

     写在前面：这篇博客主要是自己复习专业课来用的，由于有一些程序设计题，我觉得还是以博客的形式把代码和个别思路写下来会好一些。本人是个蒻鸡，并且这些代码并没有提交AC,所以出错概率很大（毕竟以前比赛自己一次AC的经历也不是很多），如果发现哪里有问题，欢迎在评论区留言讨论。

==========================================================

【2014~2022历年题目】
一.西交915 2014研究生入学考试 编程题
二.西交915 2015研究生入学考试 编程题
三.西交915 2016研究生入学考试 编程题
四.西交915 2017研究生入学考试 编程题
五.西交915 2018研究生入学考试 编程题
六.西交915 2019研究生入学考试 编程题
七.西交915 2020研究生入学考试 编程题
八.西交915 2021研究生入学考试 编程题
九.西交915 2022研究生入学考试 编程题

一.西交915 2014研究生入学考试 编程题
1.进制转换：输入十进制，分别输出相应的二，八和十六进制

 思路：基本操作，但还是记录一下，对于十进制数X转N进制，
		      X%N得到是N进制的最后一位
		      X=X/N相当于将N进制最后一位去掉
	这样我们每次k=X%N 再X=X/N就可以获得N进制的每一位
1
2
3
4

代码如下：

#include 
using namespace std;

string Get(int x,int n){
	string res;
	while(x){
		int k=x%n;
		x/=n;
		if(k>10) res+='A'+k-10;
		else res+=to_string(k);
	}
	reverse(res.begin(),res.end());
	
	return res;
}

int main(){
	int x;
	cin>>x;
	cout<<Get(x,2)<<" "<<Get(x,8)<<" "<<Get(x,16)<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.输入字符串，以回车结束，判断其是否为回文串。
代码：

#include 
using namespace std;
const int N=1e6+5;
char ch[N];
int cnt=0;

bool Judge(char ch[]){
	int cnt=strlen(ch);
	for(int i=0,j=cnt-1;i<=j;i++,j--){
		if(ch[i]!=ch[j]) return false;
	}
	return true;
}

int main(){
	
	//读入回文串 
	gets(ch);
	
	//判断 是回文串输出YES，否者输出NO 
	if(Judge(ch))cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.结构体排序。em…由于题面太长这里就不贴题面了。PS:这里提以前前几年的题都比较简单，我买的真题BD都是用C语言写的，但是最近的题目越来越难，给出的答案都是C++，也就是说我们是可以直接使用STL的。（应该？）
代码：

#include 
using namespace std;
const int N=1e6+5;
struct Book{
	string name;//书名
	int num_save;//库存量 
	int num_sale;//销售量 
	double price;//单价 
};

Book books[31];

bool cmp(Book book1,Book book2){
	return book1.num_sale>book2.num_sale;
}

int main(){
	//输入书籍信息；
	for(int i=0;i<30;i++)cin>>books[i].name>>books[i].num_sale>>books[i].num_save>>books[i].price;
	 
	
	for(int i=1;i<=100;i++){
		string name;
		cin>>name;
		
		for(int j=0;j<30;j++){
			if(books[i].name==name){
				books[i].num_sale++;
				books[i].num_save--;
			}
		}
	}
	
	sort(books,books+30,cmp);
	
	for(int i=0;i<30;i++)cout<<books[i].name<<" "<<books[i].num_sale<<" "<<books[i].num_save<<endl;
} 
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

二.西交915 2015研究生入学考试 编程题
（前几年过于简单的题这里就不写了，感觉没那个必要…）
1.编写函数：分别输出一个矩阵的主对角线元素和和副对角线元素和。（略）
2.编写函数，分别统计各字符串字符出现次数。（略）
3.输入m次字符串，输出出现过的字符串出现次数。（略）
4.链表题，写一个函数输出链表中节点值为x的个数。

虽然这本题也过于简单 ，但是鉴于这题说明了西交曾经考过链表题，而有些链表题也可以出的很复杂，所以这里贴一下代码。
平日复习注意链表题的练习，很多基本操作如反转链表，循环链表，合并链表等代码实现要熟练掌握

代码：

int caortx(structLNode *HL,int x){
	int res=0;
	for(auto t=HL;t;t=t->next){
		if(t->val==x)res++;
	}
	return res;
}
1
2
3
4
5
6
7
8
9

三.西交915 2016研究生入学考试 编程题
1.编写函数，将字符串s中的所有数字字符去掉，保留其余字符，并将新的字符串存储再原来s的空间中。

本题其实暗含了空间限制，所以考虑纯C语言，然后用双指针写。

void deleteNumber(char s[]){
	int len=strlen(s);
	for(int i=0,j=0;i<len;i++){
		if(s[i]>='0'&&s[i]<='9'){
			s[i]='\0';
			continue;
		}
		s[j]=s[i],j++;
	}
}
1
2
3
4
5
6
7
8
9
10

2.编写函数，统计一个整数里面有多少位等于数字n(n若不是个位数直接返回-1)（略）
3.结构体，类似2014，写出数据结构，写出算法描述（其实啥算法都没有，直接模拟），写出源程序。（略，但是多提一句，这题看答案解析上写的竟然是整张试卷的压轴题，并说因为这道题所以没人满分…这题虽然没有任何的思维难度，但是考场上都是在纸上手写代码，本题的代码量相对较大，这也是答案给出的本题难点所在，在备考过程中，尤其临近考试一两个月时请务必多多练习手写大量的代码，提高代码手写速度，同时注意代码规范）

四.西交915 2017研究生入学考试 编程题
ps:915的2017年的题目与之前变化相对较大，原本40分的程序设计改为了40的算法设计（有区别，但是个人感觉区别不大，一般是写算法思想，写代码实现），不过18年后17年的40分的算法设计又变回了之前的40分的程序设计。注意，17年开始，915的题目开始变难了。

1.写出折半查找的算法的基本思想和代码实现。

算法基本思想：折半查找其实就是二分查找。在一个有序表中，我们先取出当前有序表中的中间值，如果要查找的值小于该值则在当前区间的前半部分进行折半查找；如果要查找的值大于中间值，则在当前区间的后半部分进行折半查找了；否则就是中间值的位置的元素我们要找的元素，算法结束。

代码实现：

//长度为n的有序表a,有序表中的元素下标从1开始
//折半查找有序表中为值为k的元素的位置 
int binarySearch(int a[],int n,int k){
	int l=1,r=n;
	while(l<r){
		int mid=(l+r+1)/2;
		if(k>a[mid])l=mid+1;
		if(k<a[mid])r=mid-1;
		if(k==a[mid]) return mid;
	}  
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.链表题，输出单链表倒数第k个节点的值，写出基本思想，实现步骤，代码实现。

基本思想：假设该链表一共有n个节点，则倒数第k个节点即为正数n-k+1个节点，所以从头节点开始遍历到第n-k+1个节点后输入该点的值即可。

实现步骤：
（1）用一个指针变量t从头节点开始遍历，统计节点个数，直到该指针变量指向null。
（2）判断，若k>n，则查找失败返回0。
（3）用一个指针变量从头节点开始遍历，遍历时统计当前已经遍历到哪一个点，遍历到第n-k+1个节点时直接返回该点的data值

代码实现：

//题目中给出的link即next
int find(linklist *list,int k){
	int cnt=0;
	for(auto t=list;t;t=t->link)cnt++;
	
	if(k>cnt)return 0;
	for(auto t=list,i=1;t;t->link,i++){
		if(i==n-k+1) return t->data; 	
	}	
}
1
2
3
4
5
6
7
8
9
10

3.两个栈s0和s1共享一片连续的存储区域elem[1~maxsize-1]，设计共享栈以及有关出栈和入栈的操作。写出基本思想和代码实现。

基本思想：将elem[0],elem[maxsize-1]定义为s0和s1的栈底（记为top0和top1）；若s0入栈elem[++top0]=x,出栈elem[top–]=-1(在合法的情况下)，若s1入栈elem[–top1]=x,s1出栈elem[top1++]=-1;

代码实现：

//默认初始所有元素为-1 
typedef struct Stack{
	int elem[maxsize];
	int top[0]:0;
	int top[1]:maxsize-1;
}s;
 
void pop(int id){
	int top=s.top[id];
	
	if(id==0){
		if(elem[top]!=-1){
			elem[top]=-1;
			top--;
		}
	}	
	
	if(id==1){
		if(elem[top]!=-1){
			elem[top]=-1;
			top++;
		}
	}
}

void push(int id,int x){
	int top=s.top[id];
	
	if(id==0){
		if(top+1<=maxsize-1&&elem[top+1]==-1){
			elem[top+1]=x;
			top++;
		}
	}
	
	if(id==1){
		if(top-1>=0&&elem[top-1]==-1){
			elem[top-1]=x;
			top--;
		}
	}
		
}
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

4.贪心区间问题：求最大不相交区间的数量。（em…这题是17年的压轴题，可以看出17年的题已经相比前几年变难了，至少开始出现思维题和除了暴力和模拟以外的算法题了）

基本思想：有关贪心区间的问题，一般要么以左端点排序，要么以右端点排序（比较经典的几个模型都是的）。具体证明一般都是反证法。这里就不在赘述了。

代码实现：

#include 
using namespace std;
int n;
struct node{
	int l,r;
	bool operator<(const node&t){
		return r<t.r;
	}
};
main(){
	cin>>n;
	
	vector<node>q;
	for(int i=0;i<n;i++){
		int l,r;
		cin>>l>>r;
		q.push_back({l,r});
	}
	
	sort(q.begin(),q.end());
	
	int res=1,ed=q[0].r;
	for(int i=0;i<n;i++){
		if(ed<=q[i].l){
			res++;
			ed=q[i].r;
		}
	}
	
	cout<<res<<endl;
} 
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

PS：
1.注意排序算法的复习：915曾经考察过二分的思想和代码实现，其他排序算法比如快排，归并的算法思想和实现复习时要留意复习，没准还考。
2.注意链表专题的复习：915在15和17年均考察了链表题，虽然17年的链表题依然很简单，但是可以看出来，难度比15年已经有所提高了。
3.注意经典问题的复习：这里主要是是指以前比赛中见过的各种经典问题，比如17年考过的这种贪心区间问题，以前自己也写过一篇总结此类问题的博客ACM五大贪心区间问题总结，另外听上岸的学长说最近几年还考过多权值最短路，DP滚动数组优化这些，坦白的说，虽然这些东西在ACM里面并不算不难，从考研的角度来说还是要认真准备，毕竟915是手写代码并且完全闭卷不能带板子的。

五.西交915 2018研究生入学考试 编程题<先鸽几天，未完续待>