复试上机刷题2 东华17上机真题

程序员文章站 2022-06-07 23:41:35

...

第一题改错题

给定程序modi.c中，函数fun的功能是：
用下面的公式求π的近似值，直到最后一项的绝对值小于指定的数（参数num）为止(该项不包括在结果中)：

复试上机刷题2 东华17上机真题

例如，
程序运行后，输入0.0001，
则程序输出3.1414。

请改正程序中的错误，使它能得出正确结果。
注意：不要改动main函数，不得增行或删行，也不得更改程序的结构！

modi.c文件代码如下：

#include <math.h>
#include <stdio.h>
/************下一行有错************/
fun(float num)
{ 
    int s,n;
    float t,pi;

    t=1;pi=0;n=1;s=1;
/************下一行有错************/
    while(t>=num)
    {
       pi=pi+t;
       n=n+2;
       s=-s;
/************下一行有错************/
       t=s/n;
    }
    pi=pi*4;
    return pi;
}

main()
{
	float n1,n2;
    printf("Enter a float number:");
 /************下一行有错************/
	scanf("%d",&n1);
	n2=fun(n1);
	printf("%6.4f\n",n2);
}

一眼能看出两个错误，其他的三个耗了些时间，我的修改完代码如下：

#include <math.h>
#include <stdio.h>
/************下一行有错************/
float fun(float num)
{ 
    int s,n;
    float t,pi;

    t=1;pi=0;n=1;s=1;
/************下一行有错************/
    while(t>=num||(-t)>=num)
    {
       pi=pi+t;
       n=n+2;
       s=-s;
/************下一行有错************/
       t=(float)s/(float)n;
    }
    pi=pi*4;
    return pi;
}

main()
{
	float n1,n2;
    printf("Enter a float number:");
 /************下一行有错************/
	scanf("%f",&n1);
	n2=fun(n1);
	printf("%6.4f\n",n2);
}

四处错误分别是：

return了一个浮点数，所以函数头前需要加上float表明返回值的类型
t的循环判断条件有误，其实也可以使用fabs()函数来直接处理
s和n都是int型变量，除出来的数据必然是int型，只不过赋值给t时强制转float型，所以t值小数点后均为0，需要在计算之前强制转一下s和n的类型
float型不能使用%d，改用%f

复试上机刷题2 东华17上机真题

第二题补全代码题

题目如下：
给定程序blank1.c中，函数fun的功能是：找出100至x（x≤999）之间各位上的数字之和为15的所有整数，然后输出；符合条件的整数个数作为函数值返回。
例如，当x值为500时，各位数字之和为15的整数有：
159、168、177、186、195、249、258、267、276、285、294、339、348、357、366、375、384、393、429、438、447、456、 465、474、483、492。共有26个。
所以，程序运行后，输入500，则输出 The result is: 26。
请在程序的下划线处填入正确的内容并把下划线删除，使程序得出正确的结果。注意：不得增行或删行，也不得更改程序的结构！

#include <stdio.h>
fun(int x)
{
  int n, s1, s2, s3, t;
  n = __1__;
  t = 100;
  while (t <= __2__)
  {
    s1 = t % 10;
    s2 = (t / 10) % 10;
    s3 = t / 100;
    if (s1 + s2 + s3 == 15)
    {
      printf("%d ", t);
      n++;
    }
    __3__;
  }
  return n;
}
main()
{
  int x = -1;
  while (x > 999 || x < 100)
  {
    printf("Please input(100<=x<=999): ");
    scanf("%d", &x);
  }
  printf("\nThe result is: %d\n", fun(x));
}

补全之后代码为：

#include <stdio.h>
fun(int x)
{
  int n, s1, s2, s3, t;
  n = 0;
  t = 100;
  while (t <= x)
  {
    s1 = t % 10;
    s2 = (t / 10) % 10;
    s3 = t / 100;
    if (s1 + s2 + s3 == 15)
    {
      printf("%d ", t);
      n++;
    }
    t = t+1;
  }
  return n;
}
main()
{
  int x = -1;
  while (x > 999 || x < 100)
  {
    printf("Please input(100<=x<=999): ");
    scanf("%d", &x);
  }
  printf("\nThe result is: %d\n", fun(x));
}

复试上机刷题2 东华17上机真题这个就很简单了，没什么好解释的了

第三题补全代码题

题目如下：
给定程序blank2.c中，函数fun的功能是将a和b所指的两个字符串转换成面值相同的整数，并进行相加作为函数值返回，规定字符串中只包含数字字符。

例如：
主函数main中输入字符串：
32486和12345
在主函数中输出的函数值为：
44831

请在程序的下划线处填入正确的内容并把下划线删除，使程序得出正确的结果。注意：不得增行或删行，也不得更改程序的结构！

blank2.c代码如下：

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

int  strToNumber( char  s[] )
{
    int  d=0;
    int i=0;
    while(s[i]!='\0')
        if(isdigit( s[i]))
        {
            d=d*10+s[i]-__1__;
            __2__;
        }
    return  d;
}
int  add( char  a[], char  b[] )
{
    return  __3__;
}
main()
{
    char  s1[10],s2[10];
    printf("Input  string  s1 : ");
    gets(s1);
    printf("Input  string  s2 : ");
    gets(s2);
    printf("The result is:  %ld\n", add(s1,s2) );
}

修改之后的代码如下：

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

int  strToNumber( char  s[] )
{
    int  d=0;
    int i=0;
    while(s[i]!='\0')
        if(isdigit( s[i]))
        {
            d=d*10+s[i]-48;
            i++;
        }
    return  d;
}
int  add( char  a[], char  b[] )
{
    return  strToNumber(a)+strToNumber(b);
}
main()
{
    char  s1[10],s2[10];

    printf("Input  string  s1 : ");
    gets(s1);
    printf("Input  string  s2 : ");
    gets(s2);
    printf("The result is:  %ld\n", add(s1,s2) );
}

这题先看main函数，发现直接调用add，add中只有return，故add函数必然调用了strToNumber函数；看名字就知道这是一个将字符串转int的函数，所以空3可以确定了；空2很容易确定，空1思考了一会，其实使用printf打印一下d就明白了，char类型的1做加法会变成49

复试上机刷题2 东华17上机真题

第四题编程题

题目如下：
有n（n很大）个范围为0~32767数字，其中有大量重复的数，在main函数中已读入到data 数组中，请编写函数fun，计算剔除重复数字之后，还剩下几个数。

fun函数的功能是：传入两个形参，一个是数组data，一个是n的值，经过计算，返回剔除重复数字后剩下的数字的个数。
比如，
程序运行时输入： 5 1 1 3 1 3
则程序输出：2
要求：请衡量时间复杂度和空间复杂度，尽量设计高效算法。请在prog1.c最前面的注释部分介绍自己的算法。

注意：部分源程序存在文件prog1.c中。
请勿改动主函数main和其他函数中的任何内容，仅在函数fun的花括号中填入你编写的若干语句

prog1.c如下：

#include <stdio.h>
NONO();
/*
请在此解释自己的算法，并说明时间复杂度及空间复杂度
*/
int fun(int array[],int n)
{


}
int main()
{
    int data[200000];//数组长度不超过200000
	int n,count,i;
    scanf("%d", &n);
    for(i=0; i<n; i++)  //data数组实际存放n个元素
        scanf("%d", &data[i]);
    count=fun(data,n);
    printf("%d\n", count);
    NONO();
	return 0;
}
NONO()
{//本函数用于辅助教师判卷，不需要阅读其中代码，也请不要改动其中代码。
    FILE *rf,*wf ;
    int a[1000], i, j, p, n ;
    rf = fopen("bc2.in", "r") ;
    wf = fopen("p1.out", "w") ;
    for(i = 0 ; i < 6 ; i++)
    {
        fscanf(rf, "%d", &n) ;
        for(j = 0 ; j < n ; j++) fscanf(rf, "%d", &a[j]) ;
        p=fun(a, n) ;
        fprintf(wf, "%d\n", p) ;
    }
    fclose(rf) ;
    fclose(wf) ;
}

使用flag数组做标志位，初始赋值为0，只要array数组中有这个数x就将flag[x]自增；
最后计算flag标志位不为0的个数，即为去重后剩余的个数

这种思路来源于以前acm我遇见的质数题

#include <stdio.h>
NONO();
/*
使用flag数组做标志位，初始赋值为0，只要array数组中有这个数x就将flag[x]自增；
最后计算flag标志位不为0的个数，即为去重后剩余的个数
*/
int fun(int array[],int n)
{
	int flag[32770] = {0};
	for(int i =0;i<n;i++){
		flag[array[i]]++;
	}
	int sum = 0;
	for(int i = 0;i<=32767;i++){
		if(flag[i]!=0){
			sum++;
		}
	}
	return sum;
	/*也可以稍微优化一下，如下：
	int flag[32770] = {0};
	int sum = 0;
	for(int i =0;i<n;i++){
		if(flag[array[i]]==0){
			sum++;
		}
		flag[array[i]]++;
	}
	return sum;
	*/
}
int main()
{
    int data[200000];//数组长度不超过200000
	int n,count,i;
    scanf("%d", &n);
    for(i=0; i<n; i++)  //data数组实际存放n个元素
        scanf("%d", &data[i]);
    count=fun(data,n);
    printf("%d\n", count);
    NONO();
	return 0;
}
NONO()
{//本函数用于辅助教师判卷，不需要阅读其中代码，也请不要改动其中代码。
    FILE *rf,*wf ;
    int a[1000], i, j, p, n ;
    rf = fopen("bc2.in", "r") ;
    wf = fopen("p1.out", "w") ;
    for(i = 0 ; i < 6 ; i++)
    {
        fscanf(rf, "%d", &n) ;
        for(j = 0 ; j < n ; j++) fscanf(rf, "%d", &a[j]) ;
        p=fun(a, n) ;
        fprintf(wf, "%d\n", p) ;
    }
    fclose(rf) ;
    fclose(wf) ;
}

其实如果数据比较大不是6w多的话，可以先排序，然后从小往大数就可以了

第五题编程题

题目内容如下：

计算所需要最少拦截系统的数目：
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能达到前一发的高度。某天，雷达捕捉到敌国的导弹来袭，如果系统数量太少，将导致有可能不能拦截所有的导弹。所以，根据雷达捕捉到的导弹高度（导弹总数目不超过 1000），需要预先准备相应数量的拦截系统。

比如导弹的高度依次为：
5 3 4 2 4 1
则一个拦截系统的第一发炮弹必须打到高度 5 的地方，第二发炮弹打到高度 3 的地方。但第三发炮弹打不到高度 4 的地方（因为每一发炮弹不能达到前一发的高度），所以要使用第二套拦截系统。
第二套拦截系统发射的炮弹高度打到 4 和 2 的高度(实际上,要拦截高度为 2 的炮弹,使用第一套拦截系统或者第二套都可以)。
第三套拦截系统发射的炮弹高度打到 4 和 1 的高度(实际上,要拦截高度为 1 的炮弹,三套拦截系统都可以)。因此，总共需要三套拦截系统。
再比如导弹的高度依次为： 5 3 4 2 3 1 则一个拦截系统的第一发炮弹必须打到高度 5 的地方，第二发炮弹打到高度 3 的地方。但第三发炮弹打不到高度 4 的地方（因为每一发炮弹不能达到前一发的高度），所以要使用第二套拦截系统。
第二套拦截系统发射的炮弹高度打到 4 的高度。再要拦截高度为 2 的炮弹,使用第一套拦截系统或者第二套都可以，但考虑到后面还需要拦截炮弹，我们这里使用第一套拦截系统（为什么不能用第二套，自己想啦）。
再要拦截高度为 3 的炮弹,我们使用第二套拦截系统。再拦截高度为 1 的炮弹，第一套和第二套系统都可以，我们使用第一套。
因此，总共仅需要两套拦截系统，第一套拦截的是 5 3 2 1，第二套拦截的是 4 3。

请根据给定的高度数据，帮助计算一下最少需要多少套拦截系统。

在main函数中，首先输入n，表示共有n个导弹，然后读入导弹的高度到数组a中。 fun函数接受a数组和n两个参数，计算需要的拦截系统的数目，并返回该结果。请完成fun 函数。
比如，程序运行时输入：

6
5 3 4 2 3 1 
则程序输出：“The number is: 2”

题目给的源码如下：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
NONO();
int  fun(int  height[], int  n)
{
    

}
int main ()
{
    int n , a[1000];
    int i, k, total;
    scanf ( "%d", &n );
    for ( i=0; i < n; i++ )
    {
        scanf ( "%d", &a[i] );
    }
    total = fun(a, n);
    printf("The number is: %d", total);
    NONO();
    return 0;
}
NONO()
{//本函数用于辅助教师判卷，不需要阅读其中代码，也请不要改动其中代码。
    FILE *rf,*wf ;
    int a[1000], i, j, p, n ;
    rf = fopen("bc.in", "r") ;
    wf = fopen("p2.out", "w") ;
    for(i = 0 ; i < 6 ; i++)
    {
        fscanf(rf, "%d", &n) ;
        for(j = 0 ; j < n ; j++) fscanf(rf, "%d", &a[j]) ;
        p=fun(a, n) ;
        fprintf(wf, "%d\n", p) ;
    }
    fclose(rf) ;
    fclose(wf) ;
}

修改之后的代码如下：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
NONO();
int  fun(int  height[], int  n)
{
    int point[1000]={0};
	int k = 0;
	for(int i =0;i <n;i++){
		for(int j=0;j<n;j++){
			if(point[j]>height[i]){
				point[j] = height[i];
				break;
			}
			else if(point[j]==0){
				point[j] = height[i];
				k++;
				break;
			}
		}
	}
	
	return k;
}
int main ()
{
    int n , a[1000];
    int i, k, total;
    scanf ( "%d", &n );
    for ( i=0; i < n; i++ )
    {
        scanf ( "%d", &a[i] );
    }
    total = fun(a, n);
    printf("The number is: %d", total);
    NONO();
    return 0;
}

NONO()
{//本函数用于辅助教师判卷，不需要阅读其中代码，也请不要改动其中代码。
    FILE *rf,*wf ;
    int a[1000], i, j, p, n ;
    rf = fopen("bc.in", "r") ;
    wf = fopen("p2.out", "w") ;
    for(i = 0 ; i < 6 ; i++)
    {
        fscanf(rf, "%d", &n) ;
        for(j = 0 ; j < n ; j++) fscanf(rf, "%d", &a[j]) ;
        p=fun(a, n) ;
        fprintf(wf, "%d\n", p) ;
    }
    fclose(rf) ;
    fclose(wf) ;
}

这里唯一需要注意的是数组批量赋初值只能0，之前我赋初值-1，结果只有第一个是-1。调试截图如下：
复试上机刷题2 东华17上机真题

第六题编程题

题目如下：
从数据结构中树的定义可知，除根结点外，树中的每个结点都有唯一的一个双亲结点。根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各结点。树中的结点除保存结点本身的信息之外，还要保存其双亲结点在数组中的位置（即在数组中的下标。双亲的信息为-1 则表示该结点为根结点），树的这种表示法称为双亲表示法。

树的每个结点的数据类型定义如下：

struct PTNode {
char data; //结点数据域 
int parent; //结点双亲在数组中的位置
};

树的数据类型定义如下：

#define MAX_TREE_SIZE 100
struct PTree {
struct PTNode nodes[MAX_TREE_SIZE]; //存储树中所有结点
int n; //树*有 n 个结点，n 不超过 100
}

则下图 1 所示的树，按照双亲表示法存储结构，存储为图 2 所示形式（n 为 10）。

复试上机刷题2 东华17上机真题已知一棵树已存储为以上形式，请编写函数 GetNearestCommonGrand，查找给定的两个
（不相同的）结点最近的共同祖先。GetNearestCommonGrand 的函数原型为： char GetNearestCommonGrand(struct PTree T, char nodeData1, char nodeData2)
函数形参：
T：保存了树中结点数目及图 2 所示的结点数组
nodeData1,nodeData2：给定的两个结点的数据（输入时保证这两个结点存在）。
函数返回值：两个结点最近的共同祖先。
比如，nodeData1 为’G’，nodeData2 为’H’，则函数返回’A’。
说明：输入保证 nodeData1 和 nodeData2 在树中能找到。

部分代码在 prog3.c 中，请仅在 GetNearestCommonGrand 函数中填入内容，完成程序。要求：尽量优化算法的时间复杂度与空间复杂度，并在GetNearestCommonGrand函数前的注释部分简要介绍自己的算法，同时指出该算法具有什么样的时间复杂度与空间复杂度。
请勿改动主函数main和其它已有函数中的任何内容，可以在函数 GetNearestCommonGrand的花括号中填入你编写的若干语句，允许增加自定义函数。

prog3.c 中，struct PTree CreateTree()函数用于从键盘输入树的双亲表示法的信息，创建一棵树。输入的第一个数 n 表示树中结点数，此后有 n 行输入，每行表示一个结点的信息，其中第一个信息为结点的数据，第二个信息为结点的双亲结点在数组中的位置。在 main 函数中还需要输入两个结点的字符数据，查询这两个结点的最近共同祖先.

如输入（第一行为 n，表示共有 10 个结点，后面 10 行，为 10 个结点的信息，最后一行为 g 和 h，表示查询结点 g 和结点 h 的最近共同祖先）：
10
a -1
b 0
c 0
d 0
e 1
f 1
g 1
h 2
i 3
j 3
g h
则将创建图 b 所对应的树。输出结果为’a’

如输入：
8
a -1
b 0
e 1
h 6
c 0
d 0
f 5
g 5
g h
输出结果为’d’

prog3.c 源码如下：

#include <stdio.h>
#define MAX_TREE_SIZE 100
void NONO();
struct PTNode /*树的一个结点*/
{
    char data;
    int parent; /* 双亲位置域 */
};
struct PTree
{
    struct PTNode nodes[MAX_TREE_SIZE];
    int n; /* 结点数 */
};
/*
请在此介绍自己的算法，并解释算法的时间复杂度与空间复杂度
*/
char GetNearestCommonGrand(struct PTree T, char nodeData1, char nodeData2)
{


}
struct PTree CreateTree()
{
    int i,n;
    int parentId;
    char ch;
    struct PTree newTree;
    scanf("%d", &n);
    newTree.n=n;
    for (i = 0; i < n; i++)
    {
        scanf(" %c%d", &ch, &parentId);
        newTree.nodes[i].data=ch;
        newTree.nodes[i].parent=parentId;
    }
    return newTree;
}
int main()
{
    struct PTree aTree;
    char node1, node2, nodeGrand;
    aTree = CreateTree();
    scanf(" %c %c", &node1, &node2);
    nodeGrand= GetNearestCommonGrand (aTree, node1, node2);
    printf("%c\n", nodeGrand);
    NONO();
    return 0;
}
void NONO()
{//本函数用于辅助教师判卷，不需要阅读其中代码，也请不要改动其中代码。
    FILE *fp, *wf ;
	int i,j,n;
	char ch;
	int parentId;
    char node1, node2, nodeGrand;
	struct PTree newTree;
    fp = fopen("p3.in","r");
    wf = fopen("p3.out","w");
    for(i = 0 ; i < 6 ; i++)
	{
		fscanf(fp, "%d", &n);
		newTree.n=n;
		for (j = 0; j < n; j++)
		{
			fscanf(fp," %c%d", &ch, &parentId);
			newTree.nodes[j].data=ch;
			newTree.nodes[j].parent=parentId;
		}
    fscanf(fp," %c %c", &node1, &node2);
    nodeGrand= GetNearestCommonGrand (newTree, node1, node2);
		fprintf(wf, "%c\n", nodeGrand);
	}
    fclose(fp);
    fclose(wf);
}

改过之后的代码如下：

#include <stdio.h>
#define MAX_TREE_SIZE 100
void NONO();
struct PTNode /*树的一个结点*/
{
    char data;
    int parent; /* 双亲位置域 */
};
struct PTree
{
    struct PTNode nodes[MAX_TREE_SIZE];
    int n; /* 结点数 */
};
/*
 将两个节点的双亲节点直到根节点全部存入数组，再从根节点开始对比，
 直至找到不一样的节点，此处回退一个即为最近共同祖先
时间复杂度为o(n),空间复杂度o(logn)
*/
char GetNearestCommonGrand(struct PTree T, char nodeData1, char nodeData2)
{
	int tree1[100],tree2[100];
	int i,j,m,n,flag1,flag2;
	for(i =0;i<T.n;i++){
		if(T.nodes[i].data == nodeData1){
			flag1 = i;
		}
		else if(T.nodes[i].data == nodeData2){
			flag2 = i;
		}
	}
	i = 0;
	tree2[i] = flag1;
	i++;
	j = flag1;
	while(T.nodes[j].parent!=-1){
		tree1[i]= T.nodes[j].parent;
		i++;
		j = T.nodes[j].parent;;
	}
	m = i-1;
	i = 0;
	tree2[i] = flag2;
	i++;
	j = flag2;
	while(T.nodes[j].parent!=-1){
		tree2[i]= T.nodes[j].parent;
		i++;
		j = T.nodes[j].parent;
	}
	n = i-1;
	while(tree1[m]==tree2[n]){
		m--;
		n--;
	}
	return T.nodes[tree2[n+1]].data;

}
struct PTree CreateTree()
{
    int i,n;
    int parentId;
    char ch;
    struct PTree newTree;
    scanf("%d", &n);
    newTree.n=n;
    for (i = 0; i < n; i++)
    {
        scanf(" %c%d", &ch, &parentId);
        newTree.nodes[i].data=ch;
        newTree.nodes[i].parent=parentId;
    }
    return newTree;
}
int main()
{
    struct PTree aTree;
    char node1, node2, nodeGrand;
    aTree = CreateTree();
    scanf(" %c %c", &node1, &node2);
    nodeGrand= GetNearestCommonGrand (aTree, node1, node2);
    printf("%c\n", nodeGrand);
    NONO();
    return 0;
}
void NONO()
{//本函数用于辅助教师判卷，不需要阅读其中代码，也请不要改动其中代码。
    FILE *fp, *wf ;
	int i,j,n;
	char ch;
	int parentId;
    char node1, node2, nodeGrand;
	struct PTree newTree;
    fp = fopen("p3.in","r");
    wf = fopen("p3.out","w");
    for(i = 0 ; i < 6 ; i++)
	{
		fscanf(fp, "%d", &n);
		newTree.n=n;
		for (j = 0; j < n; j++)
		{
			fscanf(fp," %c%d", &ch, &parentId);
			newTree.nodes[j].data=ch;
			newTree.nodes[j].parent=parentId;
		}
    fscanf(fp," %c %c", &node1, &node2);
    nodeGrand= GetNearestCommonGrand (newTree, node1, node2);
		fprintf(wf, "%c\n", nodeGrand);
	}
    fclose(fp);
    fclose(wf);
}

思路说明都写在注释那里了~
复试上机刷题2 东华17上机真题

总结

刷完17年的真题，做个总结吧：

总体难度来说，中下难度
调试的时候NONO函数这种先注释掉，调试完再恢复
vc++不怎么会用，摸索了半天，这里需要注意的是一个报错，fatal error C1010: unexpected end of file while looking for precompiled head

问题详细解释：致命错误C1010，在寻找预编译指示头文件时，文件未预期结束。就是没有找到预编译指示信息的问文件。

顾名思义就是预编译因为缺少了预编译文件而失败。解决方法显然可以取消预编译，或者帮助编译器找到预编译文件。

故解法：

1.右键单击项目工程中的cpp文件，在菜单Project->Settings->C/C++->Precompile Header，设置为第一项：Not using precompile headers。
复试上机刷题2 东华17上机真题
2.在.c文件开头添加包含文件stdafx.h。

#include"stdafx.h"

上一篇： 51Nod-1476-括号序列的最小代价

下一篇：网站怎么优化才能有效降低网站跳出率?

复试上机刷题2 东华17上机真题

第一题改错题

第二题补全代码题

第三题补全代码题

第四题编程题

第五题编程题

第六题编程题

总结

东华复试上机备考踩坑记-15年第四题