西安交通大学915计算机软件基础往年真题编程题答案

左手的ㄟ右手 2022-11-20 01:53 244阅读 0赞

## 06年真题编程题答案 ##

**1 编写函数，用冒泡排序法或选择排序法对输入的 100个整数按从小到大的顺序排列；**

#include <stdio.h>
    //冒泡排序算法 
    void bubblesort(int A[], int n) { //
    	bool sorted = false; //整体排序标志，首先假定尚未排序
    	int m = n;
    	while (!sorted) { 
    		sorted = true; //假定已经排序
    		for (int i = 1; i < n; i++) { //自左向右逐对检查弼前范围A[0, n)内癿各相邻元素
    			if (A[i - 1] > A[i]) { //一旦A[i - 1]不A[i]逆序，则
    				int temp = A[i - 1];
    				A[i-1] = A[i];
    				A[i] = temp;
    				
    				sorted = false; //因整体排序丌能保证，需要清除排序标志
    			}
    		}
    		n--; //至此末元素必然就位，故可以缩短待排序序列癿有效长度
    	}
    	for(int i = 0; i < m; i++){
    		printf(" %d",A[i]);
    	}
    } 
    //程序运行主函数 
    int main(){
    	int A[] = {2,9,3,6,1,17,43,21,32,5,78,54}; 
    	int n = 12;
    	bubblesort(A,n);
    }

![20201129193617900.png][]

**2、采用递归法，编写实现n!的函数；**

#include <stdio.h>
    int fun(int n)
    {
    	if(n==0)return 0;
    	if(n==1)return 1;
    	if(n==2)return 2;
    	if(n>=3)return fun(n-1)*n;
    }
    int main()
    {
    	int n,result;
    	printf("输入整数n:"); 
    	scanf("%d",&n);
    	result=fun(n);
    	printf("%d!计算结果为:%d",n,result);
    	return 0;
    }

![20201129193123654.png][]

**3、编写统计候选人得票的程序，设有十个候选人，有100个人参加投票，每次 3、编写统计候选人得票的程序，设有十个候选人，有100个人参加投票，每次输入-一个得票的候选人的名字，要最后统计输出每个候选人的得票结果。 输入-一个得票的候选人的名字，要最后统计输出每个候选人的得票结果.**

#include <stdio.h>
    #include <string.h>
    #define max 100
    struct people {
    	char name[10];//候选人姓名 
    	int count;//得票数量 
    }person[max];
    //初始化候选人信息的函数 10个候选人 
    void initVoteInfo(){
    	for(int i=0;i<10;i++){
    		printf("输入候选人姓名:");
    		//赋值
    		scanf("%s",&person[i].name); 
    		person[i].count = 0; 
    	}
    } 
    //插入投票信息的函数 n为投票人数 
    void insertVoteInfo(int n){
    	for(int i=0;i<n;i++){
    		char namestr[10];//候选人姓名 
    		printf("输入得票的候选人:");
    		//赋值
    		scanf("%s",namestr); 
    		for(int j=0;j<10;j++){
    			//判断字符串是否相等 
    			if(strcmp(person[j].name, namestr) == 0){
    				person[j].count = person[j].count + 1;
    			}
    		}
    	}
    }
    //输出每个候选人投票结果 
    void getVoteInfo(){
    	for(int i=0;i<10;i++){
    		printf("---候选人:%s得票数量为:%d\n",person[i].name,person[i].count);
    	}
    }  
    int main(){
    	//初始化
    	printf("----------------开始录入基础信息----------------\n");
    	initVoteInfo();
    	printf("----------------基础信息录入完毕----------------\n");
    	printf("------------------开始投票信息------------------\n");
    	//投票
    	int n; 
    	printf("输入投票的总人数:");  
    	scanf("%d",&n); 
    	insertVoteInfo(n);
    	printf("------------------结束投票信息------------------\n");
    	//输出结果
    	printf("------------------投票信息如下------------------\n");
    	getVoteInfo();
    	return 1;
    }

# #

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70][] ##

## 15年真题编程题答案 ##

**1.编写一个函数，该函数有三个参数，一个是二维数组,一个是二维数组的行数，最后一个是二维数组的列数，输出该二维数组两条对角线元素之和。**

#include <stdio.h>
    //计算矩阵对角线元素之和 
    int getSum(int arr[][3],int m,int n){
    	if(m!=n){
    		printf("数组函数列数不相等，不可以求对角线元素之和；\n");
    		return 0; 
    	}
    	printf("矩阵元素为：\n"); 
    	for(int i=0;i<m;i++){
    		for(int j=0;j<n;j++){
    			printf("%d ",arr[i][j]);
    		}	
    		printf("\n"); 	
    	}
        int sum = 0;
        for(int i=0;i<m;i++){
        	sum = sum + arr[i][i];
    	}
    	for(int j=0;j<n;j++){
        	sum = sum + arr[n-j-1][j];
    	}
        if(n%2 == 1){
        	//n为奇数 
        	sum = sum - arr[n/2][n/2];
    	}
    	printf("矩阵对角线元素之和为：%d",sum);
    	return 1; 
    }
     
    int main()
    {
        int a[3][4]={
       {2,5,8,7},{4,6,7,8},{3,1,5,2}};
        int b[4][4]={
       {2,5,8,7},{4,6,7,8},{3,1,5,2},{3,1,5,2}};
        int c[3][3]={
       {2,5,8},{4,6,7},{3,1,5}};
    //    getSum(a,3,4);
    //    getSum(b,4,4);
        getSum(c,3,3);
        return 1;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 2][]

**2编写一 个函数， 输入一个字符串，分别统计该字符 串中出现的数字字符个数，字母字符个数和其 他类型字符个数。**

#include<stdio.h>
    #include<string.h>
    void fun(char *s)
    {
        int i;
        //\0为结束字符 
        int num_count = 0;
        int char_count = 0;
        int else_count = 0;
        for(i=0;s[i]!='\0';i++){
            if(s[i]>='0'&& s[i]<='9'){
            	num_count++;
            }else if(s[i]>='a'&& s[i]<='z'){
            	char_count++;
            }else if(s[i]>='A'&& s[i]<='Z'){
            	char_count++;
            }else{
            	else_count++;
    		}
        }
        printf("字符串中数字数量为:%d",num_count);
        printf("字符串中字母数量为:%d",char_count);
    	printf("字符串中其它数量为:%d",else_count);
    }
    int main()
    {
        char str[100];
        printf("请输入字符串:");
        gets(str);
        fun(str);
        return 0;
    }

![20201213140700241.png][]

## 16年真题编程题答案 ##

**1、(10分)编写一个函数,功能是:将字符串s中的所有数字字符去掉，保留其余的字符，并且将形成的新字符串存储在原S的空间中。**

#include<stdio.h>
    #include<string.h>
    void fun(char *s)
    {
        int i,j=0;
        //\0为结束字符 
        for(i=0;s[i]!='\0';i++)
        {
            if(s[i]<'0'||s[i]>'9')
            {
            	//重新给S进行赋值 
                s[j++] = s[i];
            }
        }
        s[j]='\0';
        printf("删除后的为:%s",s);
    }
    int main()
    {
        char str[100];
        printf("请输入字符串:");
        gets(str);
        fun(str);
        return 0;
    }

![20201122164455848.png][]

**2、(10分)编写一个函数，功能:从一个整数m中，统计其中各位上等于n的数字数目，并返回，其中0<=n<=9，若n越界，则返回-1,并提示‘第二个参 数越界'，例如:4500201中有0共3个，编写主函数并调试。**

#include <stdio.h>
    #include <string.h>
    int fun(char *s,int n)
    {
    	if(n<0 || n>9){
    		printf("第二个参数越界");
    		return -1;
    	}
    	char p;
    	p = n +' 0';//数字转字符串 
    	int sum = 0;
        //\0为结束字符 
        for(int i=0;s[i]!='\0';i++)
        {
            if(s[i] == p)
            {
            	sum++;
            }
        }
        printf("相同个数为：%d",sum);
        return 0;
    }
    int main()
    {
    	char str[100];
    	int i,n;
    	printf("请输入整数字符串:");
    	gets(str);
    	n=strlen(str);
    	for(i=0;i<n;i++)
    	{
    		if(str[i]<'0'||str[i]>'9')
    		{
    			printf("\n输入有误，不是整数。\n");
    			break;
    		}
    	}
    	printf("请输入对比数字n:");
    	scanf("%d",&n);//接收数据
    	return fun(str,n); 	
    }

![20201122164633143.png][]

**3、(20分)建立一 个学生在某一一个课程到课情况统计程序。功能要求:**

**(1)可一次性输入所有学生的到课情况，输入学生总人数，该课程总课时，学生学号，及其到课情况，分为正常，迟到，请假，旷课；**

**(2)可统计某-个学生的到课情况的上课率(包括正常，迟到。旷课率，并输出。**

**(3)可统计所有学生的上课率，旷课率，并输出。**

#include <stdio.h>
    #include <string.h>
    #define max 128
    struct student {
    	char studentcode[10];
    	int normalcount;//正常次数 
    	int latecount;//迟到次数 
    	int leavecount;//请假次数 
    	int absentcount;//旷课次数 
    }person[max];
    //插入学生信息的函数 
    void insertStudentInfo(int n){
    	for(int i=0;i<n;i++){
    		printf("输入学生的学号 正常上课次数 迟到次数 请假次数 旷课次数：%s%d%d%d%d\n");
    		//赋值
    		scanf("%s%d%d%d%d",&person[i].studentcode,
    		&person[i].normalcount,&person[i].latecount,
    		&person[i].leavecount,&person[i].absentcount); 
    	}
    }
    //根据学号获取某个学生的相关信息 
    void getStudentInfo(int n,int sum,char *s){
    	for(int i=0;i<n;i++){
    		//判断字符是否相等 
    		if(strcmp(person[i].studentcode, s) == 0){
    			printf("学号为%s的学生上课情况如下：\n",person[i].studentcode);
    			printf("    上课率为：%2f,旷课率：%2f\n",
    			(float)(person[i].normalcount+person[i].latecount)/sum,
    			(float)person[i].absentcount/sum);
    		}	
    	}
    } 
    //获取所有学生的相关信息 
    void getAllStudentInfo(int n,int sum){
    	int allincount = 0;
    	int allabsentcount = 0;
    	for(int i=0;i<n;i++){
    		allincount = allincount + person[i].normalcount+person[i].latecount;
    		allabsentcount = allabsentcount + person[i].absentcount;
    	}
    	printf("所有学生上课情况如下：\n");
    	printf("    上课率为：%2f,旷课率：%2f\n",
    	(float)allincount/(sum*n),
    	(float)allabsentcount/(sum*n));
    }
    int main(){
    	int n,sum;
    	printf("----------------开始录入基础信息----------------\n");
    	printf("输入学生的总人数：");  
    	scanf("%d",&n);
    	printf("输入总上课次数：");  
    	scanf("%d",&sum);
    	printf("----------------基础信息录入完毕----------------\n");
    	printf("----------------开始录入学生信息----------------\n");
    	insertStudentInfo(n);
    	printf("----------------学生信息录入完毕----------------\n");
    	char str[10];
    	printf("请输入要查询的学生学号:");
    	scanf("%s",&str);
    	getStudentInfo(n,sum,str); 
    	getAllStudentInfo(n,sum); 
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 3][]

## 17年编程题答案 ##

**应用题第八题**

![20201206094426420.png][]

![20201206094339293.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 5][]

**1、已知一个带有表头结点的单链表，结点结构为**

![20201206092136781.png][]

**假设该链表只给出了头指针list.在不改变链表的前提下，请设计一个尽可能高效算法、查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点点的data域的值，并返回1;否则，只返回0。要求:   
1)描述算法的基本设计思想。   
2)描述算法的详细实现步骤。   
3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C、C++或Java语言实现)，关键之处请给出简要注释。 **

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 6][]

struct LinkNode{
    	int data;
    	LinkNode *link;
    } *LinkList;
    int Search_k(LinkList list,int k){
    	//查找链表list倒数第k个结点，并输出该结点data域的值
    	LinkList p=list->link;//指针p,q指向链表的第一个结点 
    	LinkList q=list->link;
    	int count=0;//计数器初始化为0 
    	while(p!=NULL){//指针p依次遍历链表直至最后一个结点 
    		if(count<k)
    		count++;
    		else
    		q=q->link;
    		p=p->link;
    	} //while
    	/*
    	上面这几行是这个算法的核心思想，我来解释一下
    	首先算法开始运行时，p在动，而q不动
    	直到p向右移动了k次，此时k和count相等，这时候p和q一起向右移动
    	如果k小于链表的长度，则返回q指针指向的数据域 
    	*/
    	if(count<k)//若k值大于链表的长度，则找不到该结点，返回0 
    	return 0;
    	else{
    		//找到该结点则返回该结点的数据域 
    		ptintf("该节点数据域为：%d"q->data,);
    		return 1;
    	} 
    }

**2、写一个折半查找函数；**

#include <stdio.h>
    //折半查找 
    void halfSearch(int A[],int n){
    	int low=0,high=9,mid;//high = A的长度 
    	bool flag = false;
    	//折半查找
    	while(low<=high){
    		mid = (low+high)/2;
    		if(A[mid] == n){
    			printf("---%d所在位置为:%d",n,(mid+1));
    			flag = true;
    		}
    		if(A[mid]>n)
    			high = mid - 1;
    		else low = mid + 1;
    	} 
    	if(!flag){
    		printf("---未找到所查元素");
    	}
    } 
    
    int main(){
    	int A[9] = {0,13,27,38,49,49,65,76,97}; 
    	halfSearch(A,38);
    	return 0;
    }

![202011292029225.png][]

**3、设有两个栈S1、S2都采用顺序栈方式， 并且共享一个个存储区\[0, ......，maxsize-1\].为了尽量使用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式请设计S1、S2栈的出栈、进栈操作算法。要求:利用空间策略;算法数据结构;写出算法步骤;**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 8][]

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define STACKSIZE 100
    typedef int ElemType;
    typedef struct
    {
    	ElemType stack[STACKSIZE];
    	int top[2];
    }SSeqStack;
    void InitStack(SSeqStack *S)//初始换栈
    {
    	S->top[0] = 0;
    	S->top[1] = STACKSIZE-1;
    }
     
    int StackEmpty(SSeqStack S,int flag)//判断栈是否为空
    {
    	switch(flag)
    	{
    	case 0:
    		if(S.top[0] == 0)
    		{
    			return 1;
    		}
    		break;
    	case 1:
    		if(S.top[1] == STACKSIZE-1)
    		{
    			return 1;
    		}
    		break;
    	default:
    		return 0;
    	}
    	return 0;
    }
     
    int GetTop(SSeqStack S,ElemType *e,int flag)//取栈顶元素
    {
    	switch(flag)
    	{
    	case 0:
    		if(S.top[0] == 0)
    		{
    			return 0;
    		}
    		*e = S.stack[S.top[0]-1];
    		break;
    	case 1:
    		if(S.top[1] == STACKSIZE-1)
    		{
    			return 0;
    		}
    		*e = S.stack[S.top[1]+1];
    		break;
    	default:
    		return 0;
    	}
    	return 1;
    }
     
    int PushStack(SSeqStack *S,ElemType e,int flag)//入栈
    {
    	if(S->top[0] == S->top[1])
    	{
    		return 0;
    	}
    	switch(flag)
    	{
    	case 0:
    		S->stack[S->top[0]] = e;
    		S->top[0]++;
    		break;
    	case 1:
    		S->stack[S->top[1]] = e;
    		S->top[1]--;
    		break;
    	default:
    		return 0;
    	}
    	return 1;
    }
     
    int PopStack(SSeqStack *S,ElemType *e,int flag)//出栈
    {
    	switch(flag)
    	{
    		if(S->top[0] == 0 )
    		{
    			return 0;
    		}
    	case 0:
    		S->top[0]--;
    		*e = S->stack[S->top[0]];
    		break;
    	case 1:
    		if(S->top[1] == STACKSIZE-1)
    		{
    			return 0;
    		}
    		S->top[1]++;
    		*e = S->stack[S->top[1]];
    		break;
    	default:
    		return 0;
    	}
    	return 1;
    }
     
    int StackLength(SSeqStack S)//求栈长度
    {
    	return S.top[0]+S.top[1];
    }
     
    void ClearStack(SSeqStack *S)//清空栈
    {
    	S->top[0] = 0;
    	S->top[1] = STACKSIZE-1;
    }
    //设有两个栈S1和S2都采用顺序栈的方式存储，并且共享一个存储区。
    int main(void)
    {
    	SSeqStack S;
    	int i;
    	ElemType a[] = {'a','b','c','d','e'};
    	ElemType b[] = {'x','y','z','r'};
    	ElemType e1,e2;
    	InitStack(&S);
    	for(i = 0;i < sizeof(a)/sizeof(a[0]);i++)
    	{
    		if(PushStack(&S,a[i],0) == 0)
    		{
    			printf("栈已满，不能进栈！");
    			return 0;
    		}
    	}
    	for(i = 0;i < sizeof(b)/sizeof(b[0]);i++)
    	{
    		if(PushStack(&S,b[i],1) == 0)
    		{
    			printf("栈已满，不能进栈！");
    			return 0;
    		}
    	}
    	if(GetTop(S,&e1,0) == 0)
    	{
    		printf("栈已空！");
    		return 0;
    	}
    	if(GetTop(S,&e2,1) == 0)
    	{
    		printf("栈已空！");
    		return 0;
    	}
    	printf("左端栈栈顶元素是：%c,右端栈栈顶元素是：%c\n",e1,e2);
    	printf("左端栈元素的出栈顺序是：");
    	while(!StackEmpty(S,0))
    	{
    		PopStack(&S,&e1,0);
    		printf("%4c",e1);
    	}
    	printf("\n");
    	printf("右端栈元素的出栈顺序是：");
    	while(!StackEmpty(S,1))
    	{
    		PopStack(&S,&e2,1);
    		printf("%4c",e2);
    	}
    	printf("\n");
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 9][]

**4、假设有n个作业，m台机器设备，每个作业i可选择一台设备加工， 加工时间为 Ti,每次一台设备只加工1个作业，基于贪心策略写程序，实现作业调度，使n个作业等待时间的和最小。**

**要求:写出贪心算法作业调度策略描述作业调度算法;写出算法数据结构:算法步骤；**

**参考博客：**[https://blog.csdn.net/iteye\_6233/article/details/82338737][https_blog.csdn.net_iteye_6233_article_details_82338737]

## 18年真题编程题答案 ##

**1、输入字符串，字符串以“\#”结尾，判断每个字符串中0-9数字各有多少个?如输入: “9jss7h21H326tu2sw37\*\#\*”输出0:0,1:1,2:3,4:0,5:0,6:1,7:2, 8:0,9:1”，输出格式不限制。**

#include <stdio.h>
    int main(){
    	int x;
    	int a[10] = {0}, i;
    	printf("请输入数字字符串,以#结尾：");
    	while((x=getchar()) != '#')
    	if(x >= '0' && x <= '9') a[x-'0'] += 1;//x-'0'转变为数字 
    	for(i=0;i<10;i++)
    	printf("%d个数:%d ,",i,a[i]);
    	printf("\n");
    	return 0;
    }

![20201206100209414.png][]  
**2.输入几个学生的姓名和成绩，要求分数相同时顺序相对输入时不变(即要求稳定排序)，进行排序后输出。  
如输入4个学生的成绩表如下:   
Jack 70  
Petter 96  
Joy 70  
Lili 89  
输出结果为:  
Petter 96  
Lili 89  
Jack 70  
Joy 70**

#include <stdio.h>
    #include <string.h>
    #define max 128
    struct student {
    	char studentname[10];
    	int score;//学生得分 
    }person[max];
    //插入学生信息的函数 
    void insertStudentInfo(int n){
    	for(int i=0;i<n;i++){
    		printf("输入学生的姓名 分数: \n");
    		//赋值
    		scanf("%s%d",&person[i].studentname,
    		&person[i].score); 
    	}
    }
    //稳定排序  选择冒泡 
    void scoreSort(int n){
    	for(int i=0;i<n-1;i++){
    		for(int j=n-1;j>i;j--){
    			if(person[j-1].score<person[j].score){
    				//交换 
    				char studentname_temp[10];
    				//C语言中字符串复制 strcpy(目标,源) 
    				strcpy(studentname_temp,person[j].studentname);
    				int score_temp = person[j].score;
    				person[j].score = person[j-1].score;
    				strcpy(person[j].studentname,person[j-1].studentname);
    				person[j-1].score = score_temp;
    				strcpy(person[j-1].studentname,studentname_temp);
    			}
    		} 
    	}
    	//输出
    	printf("排序结果如下：\n");
    	for(int i=0;i<n;i++){
    		printf("%s %d\n",person[i].studentname,person[i].score);
    	}
    } 
    int main(){
    	int n,sum;
    	printf("----------------开始录入基础信息----------------\n");
    	printf("输入学生的总人数：");  
    	scanf("%d",&n);
    	printf("----------------基础信息录入完毕----------------\n");
    	printf("----------------开始录入学生信息----------------\n");
    	insertStudentInfo(n);
    	printf("----------------学生信息录入完毕----------------\n");
    	//排序 
    	scoreSort(n); 
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 10][]  
**3、输入年月日，计算该天是本年的第N天(1<=年<=3000 1<=月<=12. 1<=日<=31)。如输入数据为y=2017, m=12, d=24,三个参数，输出结果为“N=358” 。**

#include <stdio.h>
    #include <stdlib.h>//system("pause")
    
    int main()
    {
    	//total总天数,leap用于闰年的2月天数
    	int year,month,day,total,leap;
    	printf("请输入年月日(按顺序,中间用空格隔开)：");
    	scanf("%d%d%d",&year,&month,&day);
    	if((year%4==0&&year%100!=0)||year%400==0)//判断是否闰年，闰年2月多一天，所以闰年leap为1，平年为leap为0。
    	{
    		leap=1;
    	}else
    	{ 
    		leap=0;
    	}
    	//根据月份计算对应的最终天数。
    	switch(month)
    	{
    		case 1:total=day;break;
    		case 2:total=31*1+day;break;
    		case 3:total=31*1+28+leap+day;break;
    		case 4:total=31*2+28+leap+day;break;
    		case 5:total=31*2+28+leap+30*1+day;break;
    		case 6:total=31*3+28+leap+30*1+day;break;
    		case 7:total=31*3+28+leap+30*2+day;break;
    		case 8:total=31*4+28+leap+30*2+day;break;
    		case 9:total=31*5+28+leap+30*2+day;break;
    		case 10:total=31*5+28+leap+30*3+day;break;
    		case 11:total=31*6+28+leap+30*3+day;break;
    		case 12:total=31*6+28+leap+30*4+day;break;
    		//12月之前的11个月中有6个31天，4个30天，2月为28天+leap。
    	}
    	if(year>=1&&year<=3000&&month>=1&&month<=12&&day>=1&&day<=31)//判断输入是否正解，年份最大为9999，可自行更改。
    	{
    		printf("%d月%d日止，%d年已过去%d天。\n",month,day,year,total);
    		system("pause");//按任意键继续...
    	}else{
    		printf("错误\n");
    		system("pause");//按任意键继续...
    	}
        return 0;
    }

![20201206110605339.png][]  
**4、M个相同的小球，放入N个相同的箱子，允许有的箱子空，求共有多少种分配的方法。循子不区分先后顺序，如有6个球，1.2.3和3.2.1是同一种放法)。**

**详情可查看**：[https://blog.csdn.net/komonder/article/details/81879550][https_blog.csdn.net_komonder_article_details_81879550]

#include <stdio.h>
    //具体做法就是穷举，也就是把所有情况穷举出来，就是用for循环
    //所有情况下的一个是把指定 M个球放到N个箱里，
    //也就是说N个箱每个箱都最少有一个球，这个功能由int fun(int m,int n);完成
    //把 1个 ，2个， ·····n个的情况相加
    int f(int m,int n)
    {
        int sum = 0;
        int i=1;
        if(n>m) n=m;
        if((m==1)||(n==1)) return 1;
        for(i=1;i<=n;++i)
            sum+=fun(m,i);
        return sum;
    }
    //也就是说N个箱每个箱都最少有一个球
    //也就是说把M个球必须放到N个箱里
    //第一步就是把M个球拿出N个放到N个箱里，每一个箱子一个
    //第二部是把剩下的M-N个 随机放到N个箱子里
    int fun(int m,int n)
    {
        if((n==1)||(n==m))return 1;
        
        return  f(m-n,n);
    }
    int main(){
        printf("分配方法数目  = %d",f(7,7));
        return 0;
    }

## 19年真题编程题答案 ##

**应用题第二题使用队列模拟栈的进栈和出栈**

**参考**：[https://www.cnblogs.com/TimLiuDream/p/10088115.html][https_www.cnblogs.com_TimLiuDream_p_10088115.html]

**应用题第五题第四问：**

**若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。**

//二叉链表类型定义
    typedef struct BiTNode {
        TElemType data;
        BiTNode  *lchild, *rchild;
    } BiTNode, *BiTree;
    //实现函数
    Status Similar(BiTree t1, BiTree t2)
    /* 判断两棵二叉树是否相似的递归算法 */
    {
        if(!t1 && !t2)//同为空时，两树相似
            return TRUE;
        else if(t1 && t1){
            if(Similar(t1 -> lchild,t2 -> lchild) && Similar(t1 -> rchild,t2 -> rchild))
                //两树都不为空时，判断左右子树是否相似
                return TRUE;
            else
                return FALSE;
        }else//以上两种情况都不符合，就直接返回FALSE
            return FALSE;
    }

**1、输入若干个点的坐标(x,y),xy都是正整数，当输入(0, 0)时表示输入结束、现要求输入完毕以后，输出一个长方形左下角和右上角的坐标。要求长方形区域覆盖所有输入点坐标。(若只输入了一个点的坐标则可以只输出1个点)**

**要求:写出基本设计思想;具体实现步骤;写出程序的代码**

#include <stdio.h>
    #define max 128
    struct point {
    	int x_point;//x坐标值 
    	int y_point;//y坐标值 
    }location[max];
    /**
    问题分析:
    	长方形左下角坐标为x最小值 y最小值 
    	右上角坐标为x最大值 y最大值 
    */ 
    //插入坐标 
    void insertPoint(int i,int x_point,int y_point){
    	location[i].x_point = x_point;
    	location[i].y_point = y_point;
    }
    //横坐标从小到大排  纵坐标从小到大排 
    void sort_fun(int n){
    	for(int i=0;i<n-1;i++){
    		for(int j=n-1;j>i;j--){
    			if(location[j-1].x_point>location[j].x_point){
    				//交换 x 
    				int x_point_temp = location[j].x_point;
    				location[j].x_point = location[j-1].x_point;
    				location[j-1].x_point = x_point_temp;
    			}
    			if(location[j-1].y_point>location[j].y_point){
    				//交换 y 
    				int y_point_temp = location[j].y_point;
    				location[j].y_point = location[j-1].y_point;
    				location[j-1].y_point = y_point_temp;
    			}
    		} 
    	}
    } 
    int main(){
    	int i = 0;
    	printf("---------------开始输入坐标信息--------------\n");
    	bool flag = true;//结束标识
    	while(flag){
    		int x_point,y_point;
    		printf("输入坐标,以空格隔开,输入0 0 表示结束:");
    		scanf("%d%d",&x_point,&y_point); 
    		if(x_point !=0 && y_point !=0){
    			insertPoint(i,x_point,y_point);
    			i=i+1;
    		}else{
    			flag = false;
    		} 
    	} 
    	printf("---------------结束输入坐标信息--------------\n");
    	sort_fun(i);
    	printf("长方形左下角坐标为:(%d,%d)",location[0].x_point,location[0].y_point);
    	printf("长方形右上角坐标为:(%d,%d)",location[i-1].x_point,location[i-1].y_point);
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 11][]

**2、回文串可以被定义为形如abccba,也可以是a bc c b a(含空格)**

**(1)使用递归思想，实现一个可以检测回文串的函数。  
(2)不使用递归，使用栈来实现检测回文子串的功能。  
要求:写出算法基本设过思想，具体实现步骤和代码。**

#include <stdio.h>
    #include <string.h>
    //非递归算法 
    void noRecursion(char *str){
    	int len,i;
    	len=strlen(str);
    	for(i=0;i<len/2;i++){
    		if(str[i]!=str[len-1-i]) 
    			break;
    	}
    	printf("非递归算法检测如下：");
    	if(i==(len/2)){
    		printf("%s是回文串\n",str);
    	}else{
    		printf("%s不是回文串\n",str);
    	}
    }
    //递归算法 
    bool ispal(char *s,int x,int y){
        if(y-x<=1) return true;
        return s[x]==s[y-1] && ispal(s,x+1,y-1);
    }
    int main()
    {
    	char str[100];
    	printf("字符串:");
    	gets(str);
    	//非递归算法 
    	noRecursion(str);
    	int length = strlen(str);
    	//递归算法
    	bool flag = ispal(str,0,length);
    	printf("递归算法检测如下：");
    	if(flag){
    		printf("%s是回文串\n",str);
    	}else{
    		printf("%s不是回文串\n",str);
    	}
    	return 0; 	
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 12][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 13][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 14][]

**3、从一个无序列找出共中的逆序对。要求时间复杂度为O(nlogn)。如果不能实现上述时间复杂度，请分析出自己所写程序的时间复杂度。  
样例：对于一个包含N个非负整数的数组A\[1...n\].如果有i<j且>A\[j\].则称(A\[i\],A\[j\])为1个逆序对。例如输入数组\[3,1,4,5,2\]则输出逆序对为(3,1), (3,2)，(4,2)，(5,2)共4个。  
要求:利用空间策略;算法数据结构;写出算法步骤和代码。**

#include <stdio.h>
    /**
    	归并排序求逆对数 时间复杂度为O(nlogn)
    	temp为辅助数组 
    */ 
    void merge(int arr[],int start,int mid,int end,int temp[],long long *count){
        int index = 0,index1 = 0,index2 = 0;
        index = 0; index1 = start; index2 = mid+1;
    
        while((index1<=mid) && (index2<=end)){
            if(arr[index1] <= arr[index2]){
                temp[index++] = arr[index1++];
            }else{
                temp[index++] = arr[index2++];
                //ans+=e1-p1+1;
                (*count) = (*count) + mid - index1 + 1;
                for(int m =start;m<index2-1;m++){
                	if(arr[index2-1]<arr[m]){
                		printf("(%d,%d) ",arr[m],arr[index2-1]);
    				}	
    			} 
            }
        }
        //第一个表未检测完  复制 
        while(index1<=mid)
            temp[index++] = arr[index1++];
        //第二个表未检测完  复制 
        while(index2<=end)
            temp[index++] = arr[index2++];
    
        for(int i=0;i<index;i++){
            // 复制也是递归进行的，所以并不是从start开始到end
            arr[start+i] = temp[i];
        }
    }
    
    void mergeSort(int arr[],int start,int end,int temp[],long long *count){
        if(start<end){ // 递归出口
            int mid = 0;
            mid = (start+end)/2;//从中间划分两个子序列 
            mergeSort(arr,start,mid,temp,count);//左侧递归归并 
            mergeSort(arr,mid+1,end,temp,count);//右侧递归归并 
            merge(arr,start,mid,end,temp,count);//归并 
        }
    }
    int main() 
    { 
        long long count = 0;
            int m = 5;
            int *a = new int[m];
            printf("输入五个数以空格隔开:");
            for(int i=0;i<m;i++){
                scanf("%d",&a[i]); 
            }
     		printf("逆对数如下:\n");
            int *temp = new int[m];
            mergeSort(a,0,m-1,temp,&count);
            delete []a;
            delete []temp;
        	printf("逆对数有%d对",count); 
            return 0;
    }

![20201206214255347.png][]

## 20年编程题答案 ##

**1.a、b、c、d四个0-9的数字，输出所有使得abcd+cadb=9102的abcd数字(15分)。**

#include <stdio.h>
    /**
    a、b、c、d四个0-9的数字，输出所有使得abcd+cadb=9102的abcd数字
    */
    void findFunction(){
    	int num_1,num_2;
    	int i=0;
    	int a,b,c,d;
    	printf("所有使得abcd+cadb=9102的abcd数字如下：\n");
    	for(a=0;a<9;a++){
    		for(b=0;b<9;b++){
    			for(c=0;c<9;c++){
    				for(d=0;d<9;d++){
    					num_1 = a*1000+b*100+c*10+d;
    					num_2 = c*1000+a*100+d*10+b;
    					if((num_1+num_2) == 9102){
    						printf("-----------第%d组------\n",(i+1));
    						printf("---%d:",a);
    						printf("---%d:",b);
    						printf("---%d:",c);
    						printf("---%d:",d);
    						i++;
    					}
    				}
    			}
    		}		
    	}
    	printf("------程序运行结束,共有%d个.\n",i);
    }
    int main(){
    	findFunction();
    	return 1;
    }

**2、反序数指整数各位取反之后的数。如321 的反序是123，147 的反序是741，现输入n组a,b(ab均大于0且小于10000)，如果a、b反转的和等于和的反转，则输出a、b.  
例如: a=123, b=456, 那么a+b的和= 123+456=579.**

#include <stdio.h>
    //取反函数 
    int reverse(int x)
    {
        int s = 0;
        if(x<0)
        {
            printf("数字不可以为负数；\n");
    		return 0; 
        }
        while(x>0)
        {
           s = s*10+x%10;
           x = x/10; 
        }
       return s ;
    }
     
    int main()
    {
        int a,b;
        printf("输入a和b，以空格隔开：");
        scanf("%d%d",&a,&b);
    	int a_reverse = reverse(a);
    	int b_reverse = reverse(b);
    	int sum = a+b;
    	int sum_reverse = reverse(sum);
    	if(sum_reverse == (a_reverse+b_reverse)){
    		printf("%d,%d可以使反的和等于和的反",a,b);
    	}
        return 0;
    }

![20201213131827892.png][]

**3、公司发礼品，有n件商品价值为al, a... .an的不同商品(0<an<=40)、 其价值各不相同。某员工有总价值200元的商品可以选，问总共有多少种搭配?**

[20201129193617900.png]: /images/20221120/4b079376962a48d6aa7e6e5a7f60a590.png
[20201129193123654.png]: /images/20221120/e7da781866604d4ba5cbea8f48f97e28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70]: /images/20221120/8c607ab8e01f4a35b1ebefcee0e17355.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 1]: /images/20221120/71becddc87a643d4928c283c76a327ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 2]: /images/20221120/664c391674064e6db1164736ce8ec1d9.png
[20201213140700241.png]: /images/20221120/3e30963785534363bf15989048b6cad5.png
[20201122164455848.png]: /images/20221120/587cea74475a4a3196a444095a3f9019.png
[20201122164633143.png]: /images/20221120/cded3d8d58f24382917b1352dc2d477b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 3]: /images/20221120/f62fcc4f6555489b9c04ac1141b5b363.png
[20201206094426420.png]: /images/20221120/f632cf5e2f384bb1ba0dd04c35eb15ed.png
[20201206094339293.png]: /images/20221120/3f2fd87fdcec48489e34de0653789c56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 4]: /images/20221120/5eff7e24723f407c8c1b7c28415dca27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 5]: /images/20221120/b459b12e727342c1bc578c408f8dc076.png
[20201206092136781.png]: /images/20221120/3da66d6216b0490487789fe151d3cd8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 6]: /images/20221120/1c7c0090772f43debd7a8193d2b912fd.png
[202011292029225.png]: /images/20221120/7549c988b60942d18c8da69f338dc348.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 7]: /images/20221120/dc11a150b18f4824853e4b7407bad9b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 8]: /images/20221120/43d05dcb1f4742008667d192d1c349c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 9]: /images/20221120/3b8a24073a1c490a9c19c0bb1b0a209f.png
[https_blog.csdn.net_iteye_6233_article_details_82338737]: https://blog.csdn.net/iteye_6233/article/details/82338737
[20201206100209414.png]: /images/20221120/9654b6d92e1e4d2799189dc55aff5701.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 10]: /images/20221120/b80da6498f56424aaa3c30887c583684.png
[20201206110605339.png]: /images/20221120/60052feb67a44bd7869e764ca8fbfcfb.png
[https_blog.csdn.net_komonder_article_details_81879550]: https://blog.csdn.net/komonder/article/details/81879550
[https_www.cnblogs.com_TimLiuDream_p_10088115.html]: https://www.cnblogs.com/TimLiuDream/p/10088115.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 11]: /images/20221120/83d7b1843bb6445aafe283c477557313.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 12]: /images/20221120/1767388b7d644119b582e36364050c38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20201206184139928.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20201206184200839.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4,size_16,color_FFFFFF,t_70
[20201206214255347.png]: https://img-blog.csdnimg.cn/20201206214255347.png
[20201213131827892.png]: https://img-blog.csdnimg.cn/20201213131827892.png