2015年-2017年 计算机技术专业 程序设计题(算法题)实战_c语言程序设计数据结构程序设计分析

2015

1.C语言算法设计部分

int total(int n)
{if(n==1) return  1;return total(n-1)+n+1;
}
//主函数测试代码已省略

2.输入某天的年月日，计算该天为当年的第几天。例如输入：1998，9，25；
输出：9月25日是1998年的第268天(提示闰年第判别方法为能被4整除却不能被100整除，或能被400整除的年份是闰年)。要求使用下面的结构体：
struct Data{int year; int month; int day};

int Func(int month,int day)
{int sum=0;switch (month-1) {case 11:sum+=30 ;case 10:sum+=31 ;case 9:sum+=30 ;case 8:sum+=31 ;case 7:sum+=31 ;case 6:sum+=30 ;case 5:sum+=31 ;case 4:sum+=30 ;case 3:sum+=31 ;case 2:sum+=28 ;case 1:sum+=31 ;}return sum+day;
}int main()
{struct Data data={1998,9,25}; //初始化结构体int num=0; //记录一共有多少天num=Func(data.month, data.day);// 判断是否是闰年，如果是则统计的天数+1，如果不是则直接结束if(data.year%4==0&&data.year%100!=0)num+1;printf("%d月%d日是%d年的第%d天\n",data.month,data.day,data.year,num);
}

3.请编写一个程序，将一字符串的第K个字符开始的全部字符赋值成为另一个字符串，要求：
(1)将复制过程单独写成一个函数，并用指针完成；
(2)在主函数中输入字符串和K的值，并在主函数中输出复制结果

void copy(char *str1,char *str2,int k)
{while(k--)str1++;str1--;//保证从第k位置开始while(*str2!='\0'){*str1=*str2;str1++;str2++;}*str1='\0';}int main()
{char str1[]={"month"};char str2[]={"day"};copy(str1, str2, 4);puts(str1);}

2.数据结构算法设计部分

1.

算法基本思想：遍历一遍单链表，定义两个指针一个pre指向当前结点的前一个结点，定义一个cur指针，指向当前结点，首先判断一下前两个结点的关系，明确是升序还是将序，然后开始遍历比较，不成立，直接返回，或者一直成立，直到遍历完。

代码省略，就是遍历单链表

算法基本思想：该问题的关键在于每层，所以，算法的基本思想在于二叉树的层序遍历，辅以队列这种数据结构，重点在于处理每一层，每次计算当前队列的长度，确定，每一层的长度，一次处理一层

代码省略，多次考察

3.设计算法，求出无项连通图中距离顶点V₀的最短路径长度为K的所有节点

#define INF -1    // 表示尚未访问的节点
void BFS_K(ALGraph G,VertexType v,VertexType K)
{int visit[MASVETEX];  //初始化访问数组for(int i=0;i<MASVETEX;i++)visit[i]=INF;SqQueue Q;Queue_Init(Q);Queue_En(Q, v);visit[v]=0; //顶点0到顶点0的距离为0while (!Queue_Empty(Q)) {  //假设队列不为空，开始循环Queue_De(Q, v); //从队列中弹出表头，此时弹出的元素存放在v中if (visit[v] > K) break;  //加快操作，以后的循环是没有意义的ArcNode *p=G.vertices[v].firstArc;while(p!=NULL){if(visit[p->adjvex]==INF)  //没有被访问过{visit[p->adjvex]=visit[v]+1;  //更新visit数组Queue_En(Q, p->adjvex); //将该元素加入队列中}p=p->nextArc;}}for(VertexType i=1;i<=G.vexnum;i++){if(visit[i]==K){printf("%d ",i);}}}

2016

1.C语言算法设计部分

思路如下：
第1项是 1 有一个数
第二项是23 有两个数
第三项是 3=456 有三个数
外层一个大循环从1到n，内层循环 大循环i的次数，最开始初始化一个1,每次上++它

代码略

2.某歌咏比赛中，有8个评委对20位选手进行评分，选手按1-20号进行编号，每个评委给出1-10的分数，在统计分数时要除去一个最低分和最高分，计算出其他评委给出分数的平均分作为选手的最后得分。编写程序实现以下功能：评委输入，按评分输出得分最高的三位选手的编号和分数，要求程序执行时间最短。

思路梳理:
因为要求程序执行时间最少，所以不能通过先找第一大，再找第二大，再找第三大这么循环，而是，每拿出一个选手，看看它是否是第一大，是，就依次下移，将原先的第三大挤出，以此类推，然后判断是不是第二大

3.编写程序，查找给定字符在字符串中首次出现的位置。要求:不使用有关字符串处理的库函数；
(1)主函数中键盘输入字符以及查找的字符，调用子函数；
(2)子函数完成查找任务，如果字符串中包含所查找的字符，则返回该字符串首次出现的位置，否则返回0

int first_str(char *p,char c)
{int index=1;while(*p!='\0'){if(*p==c) return index;p++;index++;}return 0;
}#define MASIZE 100
int main()
{char str[MASIZE];scanf("%s",str); //输入字符串char c;while (getchar() != '\n');scanf("%c",&c);int index=first_str(str, c);if(index!=0){printf("出现的位置为:%d\n",index);}else{printf("查找失败\n");}
}

值得积累的点:关于getchar清除缓冲区的问题

在C语言中，while (getchar() != ‘\n’); 这行代码通常用于清除输入缓冲区（input buffer）中直到下一个换行符（newline character，\n）的所有字符。这里，getchar() 是一个标准输入函数，用于从标准输入（通常是键盘）读取下一个可用的字符，并返回这个字符作为 int 类型（实际上返回的是字符的ASCII码值，但可以通过类型转换或字符比较来直接使用）。
当您使用 scanf(“%s”, str); 读取一个字符串时，scanf 会在遇到空格、制表符或换行符时停止读取。然而，换行符（用户按下回车键时产生的）仍然会留在输入缓冲区中。紧接着，当您尝试使用 scanf(“%c”, &c); 读取一个字符时，scanf 会立即从输入缓冲区中读取下一个字符，这通常是之前留在那里的换行符。

2.数据结构算法设计部分

问题1和问题2:已经出现多次了

问题3:

问题分析：本质上就是一个非连通图的遍历，将每个顶点都以它们为起始节点遍历一遍，用DFS即可实现

int visit[MaxSize]={0};void DFS_G(ALGraph G,VertexType v)
{visit[v]=1; //当前v点被访问printf("%d ",v);ArcNode *p=G.vertices[v].firstArc; //找到该点连接的第一个结点while(p!=NULL){VertexType next=p->adjvex;if(visit[next]==0)DFS_G(G, next);p=p->nextArc;}
}int traverse_G(ALGraph G)
{int sum=0;for(int i=1;i<=G.vexnum;i++){if(visit[i]==0){DFS_G(G,i);sum++;printf("\n");}}return  sum; //返回连通分量的个数
}

2017年

1. C语言算法设计部分

第一题：

void printfMultiTable()
{for(int i=1;i<=9;i++){for(int j=1;j<=i;j++){printf("%d*%d=%d ",i,j,i*j);}printf("\n");     }
}

第二题：

思路为：判断回文，通过取余将每个数存储到数组中，然后双指针判断是否为回文数。
完数电判断就是按照定义，找到每个因子加和计算即可。

不存在既是回文数又是完数的数，这道题emm，代码略

第三题：

新颖的点在于要求了动态链表存储学生成绩

struct Student
{int studentID; //学号float score;struct Student *next;
};void init_student(int ID,float score,struct Student *&head)
{struct Student *p=(struct Student *)malloc(sizeof(struct Student)); //定义一个新结点p->studentID=ID;p->score=score;p->next=head->next;head->next=p;
}void function_num(struct Student *head)  //统计结果
{struct Student *p=head->next;int s60=0;int s70=0;int s80=0;int s90=0;while(p!=NULL){if(p->score>=90&&p->score<=100){s90++;}else if(p->score>=80){s80++;}else if(p->score>=70){s70++;}else{s60++;}p=p->next;}printf("90-100分段有%d人\n",s90);printf("80-89分段有%d人\n",s80);printf("70-79分段有%d人\n",s70);printf("60-69分段有%d人\n",s60);}
int main()
{struct Student *head=NULL;head=(struct Student *)malloc(sizeof(struct Student)); //头指针的初始化while(1){int ID;float score;scanf("%d",&ID);if(ID==0) break;scanf("%f",&score);init_student(ID, score, head); }function_num(head);
}

2.数据结构算法设计部分

问题1:略

问题2:

回顾：
结点的度：指该结点的分支个数，如结点A的度为2
树的度：指树中最大的结点度数，如该树的度为3

//统计一个结点的左孩子连同左孩子的右孩子的最大数量
int getDegree(CSTree T)
{if(T==NULL) return 0;else{int maxDegree=0;int degree=0;  //根节点的度for(CSTNode *pchild=T->fristChild;pchild!=NULL;pchild=pchild->nextSibling) {degree++;  //for循环执行4次，degree最终为4int subdegree=getDegree(pchild); //subdergg本质还是degree是子函数返回的degreeif(subdegree>maxDegree)maxDegree=subdegree;}return degree>maxDegree?degree:maxDegree;}
}

问题三：

//邻接表的插入操作（头插法）
void insert(VertexType v,VertexType w,ALGraph &rG)
{ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=w;p->nextArc=rG.vertices[v].firstArc;rG.vertices[v].firstArc=p;
}void reverse(ALGraph &G,ALGraph &rG)
{// 第一步，将G的头结点，赋给rG的头结点for(int i=1;i<=G.vexnum;i++){rG.vertices[i].data=G.vertices[i].data;rG.vertices[i].firstArc=NULL;}//第二步 将v，w以w，v形式插入到rg中，以分配新的存储空间的形式插入for(int i=1;i<=G.vexnum;i++){ArcNode *p=G.vertices[i].firstArc;VertexType v=G.vertices[i].data;while(p!=NULL){VertexType w=p->adjvex;insert(w,v,rG);p=p->nextArc;}}//第三步，将点的数量，弧的数量赋值给rGrG.vexnum=G.vexnum;rG.arcnum=G.arcnum;}