【刷题小结】2012-2014年苏州大学上机复试题

2012年上机题

题目

从服务器上下载数据文件org.dat文件以二进制方式存放一系列整数，每个整数占4个字节。从第一个整数开始，第一个整数和第二个整数构成一个坐标点，依次类推，数据文件中保存了许多坐标点数据。
  问题1：
  规定处于第一象限的坐标点为有效点，请问数据文件中所有点的个数n为多少？有效点的个数k为多少？
  问题2：
  每个有效点与坐标原点构成一个的矩形，请问k个有效点与坐标原点构成的k个矩形的最小公共区域面积为多少？
  问题3：
  寻找有效点中符合下列条件的点：以该点为坐标原点，其他有效点仍然是有效点即处于第一象限（不包括坐标轴上的点）。输出这些点。
  问题4：
  对所有有效点进行分组，每个有效点有且只能属于一个分组，分组内的点符合下列规则：若对组内所有点的x坐标进行排序，点p1（x1，y1）在点p2（x2，y2）后面，即x1>x2那么y1>y2.请输出所有的分组。

分析

我看到有的代码是分题做的，这样更好给分，但是我就混在一起了，因为有些功能可以同时完成。
  我大概分成下面几个部分：
  （1）读文件，求出n和k，保存有效点。
  （2）以x的的大小由小到大进行排序。经过简单处理。可以得到最小公共面积和问题三所求的点。
  （3）分组。我就遍历了，对每个点给了一个符号位。时间复杂度比较高。

代码

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

void fileRead(FILE * fp, int num[][2], int *k, int * n);
int cmp(const void* a, const void *b);
void findMinSquare(int num[][2], int k);
int divideGroup(int num[][2], int k, int group[]);

void main()
{
	FILE * fp = fopen("org.dat", "rb");
	if (fp == NULL) {
		printf("FILE OPEN ERROR!\n");
		exit(1);
	}
	// 造数据文件，coor.txt中已经存放了一些数据
	//FILE * fp = fopen("org.dat", "wb");
	//FILE * f2 = fopen("coor.txt","r");
	//if (fp == NULL || f2==NULL) {
	//	printf("FILE OPEN ERROR!\n");
	//	exit(1);
	//}
	//int t;
	//while (fscanf(f2, "%d", &t) != EOF) {
	//	fwrite(&t, sizeof(int), 1, fp);
	//}
	//fclose(f2);

	int num[1000][2], k = 0, n = 0, groupnum;
	int group[100];
	
	fileRead(fp, num, &k, &n);

	printf("所有点的个数为：%d\n", n);
	printf("支配点的个数为：%d\n", k);

	qsort(num, k, sizeof(num[0]), cmp);
	findMinSquare(num, k);

	memset(group, -1, sizeof(group));
	groupnum = divideGroup(num, k, group);
	printf("共分为%d组，具体如下：\n", groupnum);
	for (int i = 0; i < groupnum; i++) {
		printf("第%d组点为：", groupnum);
		for (int j = 0; j < k; j++) {
			if (group[j] == i) {
				printf(" (%d, %d)", num[j][0], num[j][1]);
			}
		}
		printf("\n");
	}

	fclose(fp);

}

void fileRead(FILE * fp, int num[][2], int *k, int * n) 
{
	int x, y;
	while (fread(&x, sizeof(int), 1, fp) && fread(&y, sizeof(int), 1, fp)) {
		*n = *n + 1;
		if (x > 0 && y > 0) {
			num[*k][0] = x;
			num[*k][1] = y;
			*k = *k + 1;
		}
	}
}

int cmp(const void* a, const void *b)
{
	return ((int *)a)[0] - ((int *)b)[0];
}

void findMinSquare(int num[][2], int k)
{
	int minx, miny;
	if (k == 1) {
		printf("最小公共面积是：%d\n", num[0][0] * num[0][1]);
		printf("符合要求的点的坐标为：(%d, %d)", num[0][0], num[0][1]);
	}

	else {
		if (num[0][0] < num[1][0] && num[0][1] < num[1][1]) {
			printf("最小公共面积是：%d\n", num[0][0] * num[0][1]);
			printf("符合要求的点的坐标为：(%d, %d)\n", num[0][0], num[0][1]);
		}
		else {
			minx = num[0][0];
			miny = num[0][1];
			for (int i = 1; i < k; i++) {
				if (minx > num[i][0]) {
					minx = num[i][0];
				}
				if (miny > num[i][1]) {
					minx = num[i][1];
				}
			}
			printf("最小公共面积是：%d\n", minx * miny);
			printf("没有符合要求的点的坐标。\n");
		}
	}
}

int divideGroup(int num[][2], int k, int group[])
{
	int groupnum = 0;
	int tx, ty;
	for (int i = 0; i < k; i++)
	{
		if (group[i] == -1) {
			group[i] = groupnum;
			
			tx = num[i][0];
			ty = num[i][1];
			for (int j = i + 1; j < k; j++) {
				if (group[j] == -1 && num[j][0] > tx && num[j][1] > ty) {
					group[j] = groupnum;
					tx = num[j][0];
					ty = num[j][1];
				}
			}
			groupnum++;;
		}
	}
	return groupnum;
}

2013年上机题

题目

二进制数据文件1.bin中存放了100000个样本点，每个样本点由4个属性构成，属性均为整型。
  定义： 如a点的k个属性不比b点的对应属性差（属性值越小越好），
  且a点至少有一个属性比b点的对应属性好，则称a点k-支配b点。
  要求： 求出不被任何点k-支配的样本点的个数。
  在试卷上填写求出的样本点个数和所用时间（Elapsed Time）。

分析

这道题看上去不难，但是倒是花费了我不少的时间，其中有许多大大小小的bug。先简单介绍一下程序的几个部分：
  （1）计时（这个已经写好了）
  （2）读取文件中的数据并保存。
  （3）遍历数组，寻找不被控制的数据。
  我原来打算直接开一个$100000*4$的数组来保存数据，但是报了stack overflow的错，我查了下，说是栈的默认大小是1M，这明显超过了。我就决定用结构体+手动分配内存，但是没想到保存结构体指针的数组也超过了内存限制（原谅我没算）。后来发现只要开成全局变量就好了。
  考虑到数据有100000个，昨天丁大佬说10000个数据的话复杂度为$n^2$就有些大了，我就考虑到能不能减少时间复杂度。着就想到了链表。最开始的构想是两层遍历，去掉被控制的点。后来想到为了减少比较的次数，可以设置标志位。既然说到了标志位，就想到不如直接用链表删掉被控制的点就好了。这个算法的时间复杂度我没有求，但是最好情况是$O(n)$，最坏情况是$O(n^2)$。

代码

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

#define MAXSIZE 100000

void run(void);

int main()
{
	LARGE_INTEGER m_nFreq;
	LARGE_INTEGER m_nBeginTime;
	LARGE_INTEGER m_nEndTime;

	QueryPerformanceFrequency(&m_nFreq);
	QueryPerformanceCounter(&m_nBeginTime);

	run();

	QueryPerformanceCounter(&m_nEndTime);
	printf("\nElapsed Time = %lf sec\n",(double)(m_nEndTime.QuadPart-m_nBeginTime.QuadPart)/m_nFreq.QuadPart);
	return 0;
}

struct Dot
{
	int pos[4];
	Dot * next;
};


int dataRead(FILE * fp, Dot * head);
void eraseControlDot(Dot * head, int * count);
void freeSpace(Dot * head);

void run(void)
{
	FILE * fp = fopen("1.bin", "rb");
	if (fp == NULL) {
		printf("FILE OPEN ERROR!\n");
		exit(0);
	}

	Dot * head = (Dot *)malloc(sizeof(Dot));
	head->next = NULL;

	int count = dataRead(fp, head);
	eraseControlDot(head, &count);
	printf("%d", count);
	
   freeSpace(head);
   
	fclose(fp);
}

int dataRead(FILE * fp, Dot * head)
{
	int count = 0;
	int a, b, c, d;
	Dot * node, *p = head;

	while (fread(&a, sizeof(int), 1, fp) && fread(&b, sizeof(int), 1, fp) && fread(&c, sizeof(int), 1, fp) &&
    fread(&d, sizeof(int), 1, fp ) && count < MAXSIZE) {
		node = (Dot *)malloc(sizeof(Dot));
		node->pos[0] = a;
		node->pos[1] = b;
		node->pos[2] = c;
		node->pos[3] = d;
		node->next = NULL;
		p->next = node;
		p = node;
		count++;
	}
	return count;
}

void eraseControlDot(Dot * head, int * count)
{
	Dot *p, *q, *current;
	if (*count > 0) {
		current = head->next;
		while(current != NULL) {
			q = head;
			p = head->next;
			while (p != NULL) {
				if (p->pos[0] >= current->pos[0] && p->pos[1] >= current->pos[1] && 
                p->pos[2] >= current->pos[2]&& p->pos[3] >= current->pos[3] 
                &&(p->pos[0] > current->pos[0] || p->pos[1] > current->pos[1] 
                || p->pos[2] > current->pos[2] || p->pos[3] > current->pos[3])) {
					q->next = p->next;
					free(p);
					p = q->next;
					*count = *count - 1;
				}
				else {
					p = p->next;
					q = q->next;
				}			
			}
			current = current->next;
		}
	}
}

void freeSpace(Dot * head)
{
	Dot *p, *q;
	p = head->next;
	q = head;
	while (p != NULL) {
		free(q);
		q = p;
		p = p->next;
	}
	free(p);
}

2014年上机题

题目

input.bin中有10000组数据，每组数据有4个属性，都为整型。定义邻近点为拥有k个距离小于等于d的点的点，$d=\sqrt{(b_1-a_1)*(b_1-a_1)+(b_2-a_2)*(b_2-a_2)+(b_3-a_3)*(b_3-a_3)+(b_4-a_4)*(b_4-a_4)}$;现定义k=10，d=7500，显示出符合点的编号及其各个属性。

分析

这道题就是两次循环求解，不难，但是数据量比较大，时间比较长。

代码

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

#define ARRAYSIZE 10000
#define _CRT_SECURE_NO_WARNINGS

struct Dot {
	int pos[4];
	int ngb;
	void initDot() {
		ngb = 0;
	}
}points[ARRAYSIZE];

int fileRead(FILE *fp);
void countNeighbour(int count, double distance);
void showResult(int count, int k);

void main()
{
	LARGE_INTEGER m_nFreq;
	LARGE_INTEGER m_nBeginTime;
	LARGE_INTEGER m_nEndTime;

	QueryPerformanceFrequency(&m_nFreq);
	QueryPerformanceCounter(&m_nBeginTime);

	FILE * fp = fopen("1.bin", "rb");
	if (fp == NULL) {
		printf("FILE OPEN ERROR!\n");
		exit(1);
	}
	
	int k=10;
	double distance=7500;
	//printf("请输入k和距离：");
	//scanf("%d%lf", &k, &distance);

	int count = fileRead(fp);
	countNeighbour(count, distance);
	showResult(count, k);

	fclose(fp);

	QueryPerformanceCounter(&m_nEndTime);
	printf("\nElapsed Time=%lf sec\n",(double)(m_nEndTime.QuadPart-m_nBeginTime.QuadPart)/m_nFreq.QuadPart);
}

int fileRead(FILE *fp)
{
	int num[4];
	int count = 0;
	while (fread(num, sizeof(int), 4, fp) && count < ARRAYSIZE) {
		points[count].initDot();
		for (int i = 0; i < 4; i++) {
			points[count].pos[i] = num[i];
		}
		count++;
	}
	return count;
}

void countNeighbour(int count, double distance)
{
	for (int i = 0; i < count - 1; i++) {
		for (int j = i + 1; j < count; j++) {
			if (sqrt((double)((points[i].pos[0]-points[j].pos[0])*(points[i].pos[0]-points[j].pos[0])
            +(points[i].pos[1] - points[j].pos[1])*(points[i].pos[1] - points[j].pos[1]) 
            +(points[i].pos[2] - points[j].pos[2])*(points[i].pos[2] - points[j].pos[2]) + 
            (points[i].pos[3] - points[j].pos[3])*(points[i].pos[3] - points[j].pos[3]))) < distance) 
        {
				points[i].ngb++;
				points[j].ngb++;
			}
		}
	}
}

void showResult(int count, int k)
{
	bool flag = true;
	for (int i = 0; i < count; i++) {
		if (points[i].ngb == k) {
			printf("第%d个点:(%d,%d,%d,%d)\n",i,points[i].pos[0], points[i].pos[1], points[i].pos[2], 
            points[i].pos[3]);
			flag = false;
		}
	}
	if (flag) {
		printf("没有符合要求的点。\n");
	}
}