中科院计算所2017推免生机试

9月18号去计算所参加推免生的机试。。。9月19号去计算所参加推免生的面试。。。9月20号堕落在北京的青旅里，不能出门。。。

首先是不得不承认，计算所的环境很好，真的很好。然后就是机试，6道题目，两个小时，没有网络。其实后来自己在看，觉得最起码有两个题目是简单到我这种人都可以做出来的，无奈自己太渣，机试就跪的哟。最后是面试，项目真的太少，以至于老师一直在问我我的社会实践。。。回来之后，一起住的去面试清华的大牛告诉我，这种事情其实都是有套路，而且之前要想一下老师会问什么，然后想一下怎么回答。大牛是真的不一样的，比如傅里叶级数，我就只会做题，大牛就会想知道这个有什么用。厉害的人就是厉害，就是会在思维方式上面不一样。嗯，会在专业上想的比较深入。这样想来，自己好像理解了会汇编的高老师说的我们没有思考的能力的意思，像一只蝼蚁一样。我一定要改，我改还不行吗。

然后就是题目了.

1.用链表表示一个整数集，实现：

a.将一个整数插入整数集；

b.从整数集中删除一个整数；

c.两个整数集的交集；

d.两个整数集的并集。

2.将一个用字符串表示的数，表示为整型数

3.A是用任意个（大于等于一个）数字和字母表示的字符串，B是用0个或多个任意数字和字母表示的字符串，请编程输出B串在A串中第一次出现的位置，或者输出不出现。

4.求圆周率，写出计算公式，并计算出时间复杂度。

5.请根据输入的点集判断这些点构成的多边形是否为凸多边形。

6.计算输入的数学表达式的值，数学表达式中包括+、-、*、/、（、）。

上面的题目全凭记忆，和原题意思一样，表述的比较有误差。

我只实现了1、2、3、4。下面是代码：

第一题：

第一题本质上感觉就是链表的实现。

set.h

#include<stdio.h>
#include<stdlib.h>


typedef struct intSet set;
typedef struct intSet* setList;

struct intSet
{
	int i;
	set* next;
};


void printList(setList s);
setList insertInt(int x, setList s);
setList deleteInt(int x, setList s);
setList extractSet(setList s1, setList s2);
setList unionSet(setList s1, setList s2);

set.cpp

#include"stdafx.h"
#include"set.h"


void printList(setList s)
{
	if (s->next == NULL)
		printf("This set is null");
	else
	{
		set* p;
		p = (struct intSet*)malloc(sizeof(struct intSet));
		p = s->next;
		while (p != NULL)
		{
			printf("%d ", p->i);
			p = p->next;
		}
		printf("\n");
	}
}


setList insertInt(int x, setList s)
{
	set* p;
	p = (struct intSet*)malloc(sizeof(struct intSet));
	if (s->next == NULL)
	{
		p->i = x;
		p->next =NULL;
		s->next = p;
	}
	else
	{
		p = s->next;
		while (p != NULL&&p->i != x)
			p = p->next;
		if (p != NULL)
			printf("The element has already existed!");
		else
		{
			p = (struct intSet*)malloc(sizeof(struct intSet));
			p->i = x;
			p->next = s->next;
			s->next = p;
		}
	}
	return s;
}


setList deleteInt(int x, setList s)
{
	set* p;
	set* pre;
	p = (struct intSet*)malloc(sizeof(struct intSet));
	pre = (struct intSet*)malloc(sizeof(struct intSet));
	if (s->next == NULL)
		printf("The set is null!\n");
	else
	{
		p = s->next;
		pre = s;
		while (p != NULL&&p->i != x)
		{
			pre = p;
			p = p->next;
		}
		if (p == NULL)
			printf("No number %d in this set!", x);
		else
		{
			pre->next = p->next;
			free(p);
		}
	}
	return s;
}


setList extractSet(setList s1, setList s2)
{
	set* tmp1;
	set* res;
	tmp1 = (struct intSet*)malloc(sizeof(struct intSet));
	res = (struct intSet*)malloc(sizeof(struct intSet));
	res->next = NULL;
	if (s1->next == NULL || s2->next == NULL)
		printf("Sets have null set;");
	else
	{
		tmp1 = s1->next;
		for (; tmp1 != NULL;tmp1=tmp1->next)
		{
			int e = tmp1->i;
			set* tmp2;
			tmp2 = (struct intSet*)malloc(sizeof(struct intSet));
			tmp2 = s2->next;
			while (tmp2 != NULL&&tmp2->i != e)
				tmp2 = tmp2->next;
			if (tmp2 != NULL)
				insertInt(e, res);
		}

	}
	return res;
}


setList unionSet(setList s1, setList s2)
{
	if (s1->next == NULL&&s2->next == NULL)
		printf("Both sets are null!");
	else if (s1->next == NULL)
		s1 = s2;
	else
	{
		set* tmp;
		tmp = (struct intSet*)malloc(sizeof(struct intSet));
		tmp = s1;
		while (tmp->next != NULL)
			tmp = tmp->next;
		tmp->next = s2->next;
	}
	return s1;
}

1.cpp

// 1.cpp : 定义控制台应用程序的入口

#include "stdafx.h"
#include"set.h"


int _tmain(int argc, _TCHAR* argv[])
{
	setList h1,h2,res;
	int i, j, n;
	h1 = (struct intSet*)malloc(sizeof(struct intSet));
	h2 = (struct intSet*)malloc(sizeof(struct intSet));
	res = (struct intSet*)malloc(sizeof(struct intSet));
	h1->next = NULL;
	h2->next = NULL;
	res->next = NULL;
	printf("Please input the number of the set and the set:\n");
	n = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &j);
		h1=insertInt(j, h1);
	}
	printf("Please input the number of another set and the set:\n");
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &j);
		h2=insertInt(j, h2);
	}
	printf("Please input the number you want to insert:\n");
	scanf("%d", &i);
	h1 = insertInt(i, h1);
	printf("The inserted list is:\n");
	printList(h1);
	printf("Please input the number you want to delete:\n");
	scanf("%d", &i);
	h1 = deleteInt(i, h1);
	printf("The deleted list is:\n");
	printList(h1);
	res = extractSet(h1, h2);
	printf("The extracted list is:\n");
	printList(res);
	h1 = unionSet(h1, h2);
	printf("The unioned list is:\n");
	printList(h1);
	system("pause");
	return 0;
}

第二题：

第二题目测是这里面最简单的题目了，我唯一调过的题目（一把泪）。

2.cpp

// 2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>

int _tmain(int argc, _TCHAR* argv[])
{
	int res=0;
	printf("Please input the string:\n");
	char c;
	while ((c=getchar())!='\n')
	{
		int i;
		i = 0;
		switch (c)
		{
		case'0':i = 0; break;
		case'1':i = 1; break;
		case'2':i = 2; break;
		case'3':i = 3; break;
		case'4':i = 4; break;
		case'5':i = 5; break;
		case'6':i = 6; break;
		case'7':i = 7; break;
		case'8':i = 8; break;
		case'9':i = 9; break;
		}
		res = res * 10 + i;
	}
	printf("The number is %d", res);
	system("pause");
	return 0;
}

第三题：

也不难，就是没调过。

// 3.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<stdlib.h>
#include<stdio.h>
#include<string.h>


int _tmain(int argc, _TCHAR* argv[])
{
	char s1[100];
	char s2[100];
	char *tmp0=s1;
	char *tmp1=s1;
	char *tmp2=s2;
	int i = 0;
	printf("Please input one of the string:\n");
	gets(s1);
	printf("Please input the another string:\n");
	gets(s2);
	tmp2 = s2;
	while (*tmp0 != '\0')
	{
		i++;
		if (*tmp0 == *tmp2)
		{
			tmp1 = tmp0;
			while (*tmp2 != '\0')
			{
				if (*tmp1 != *tmp2)
					break;
				else
				{
					tmp1++;
					tmp2++;
				}
			}
			if (*tmp2 == '\0')
			{
				printf("The first appeared place is %d (started from 1)", i);
				break;
			}
			else
			{
				tmp2 = s2;
				tmp0++;
			}
		}
		else 
			tmp0++;
	}
	if (*tmp0 == '\0')
		printf("The string don't appear in the string!");
	system("pause");
	return 0;
}

第四题：

第四题，我后来去网络上搜才发现第四题是一道大题啊，圆周率也是可以编程实现的。觉得程序员真是无所不能。

我的实现方法是最简单的那一种。随着循环次数的增加，圆周率也越来越精确。

// 4.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>


int _tmain(int argc, _TCHAR* argv[])
{
	double i=1.0;
	double sign=1.0;
	double res = 0.0;
	double tmp;
	for (; i < 10000000000; i += 2.0)
	{
		tmp = 1 / i;
		tmp = tmp*sign;
		res= res+tmp;
		sign *= -1;
	}
	printf("圆周率为：%lf\n",res * 4.0);
	system("pause");
	return 0;
}

在实现第一和第三题的时候，出现的错误，现在想想，觉得挺有趣的，下面附上此问题的解决方法。
http://blog.csdn.net/houmin0036/article/details/8855293

有时间要整理一篇关于字符串的博客。

原文链接：https://blog.csdn.net/hola_f/article/details/52595530

你可能也喜欢