868历年真题算法设计题+程序设计题

11.5	2013年真题*4

一天四道太顶了，11.6-11.15先且两天四道题，先把数学二轮+三轮结束！

如果程序设计题写不了核心算法，但是把思路写上去，只将核心函数空出来也能拿些分！！
DFS大概率不会和stack同时出现，一般是使用stack来模拟DFS；

【2013 1】一个用邻接矩阵存储的有向图，请用实现该图的深度优先算法。
算法：DFS，矩阵+有向图，可递归
一般：邻接链表的有向图，如果碰到了则开始DFS，如果读不到则顺延往后递归

//数据结构
#define maxsize 100
typedef int VexType;
typedef int EdgeType;
typedef struct{VexType vex[maxsize];EdgeType edge[maxsize][maxsize];int vexnum,edgenum;
}MGraph;

int visit[maxsize];
void Visit(int n);
void DFS(MGraph g , int n = 0){//从n开始遍历Visit(n);visit[n] = 1;for(int i = n ; i < g.vexnum ;i++){for(int j = 0; j < g.vexnum; j++){if(g.edge[i][j] == 1 && visit[j] == 0)DFS(g , j);}}	
}

问题：不需要双重循环，使用了递归！！若是非递归是双循环【我用的GPT检查的代码，再对答案】

//修改
int visit[maxsize];
void Visit(int n);
void DFS(MGraph g , int n = 0){//从0开始遍历Visit(n);visit[n] = 1;for(int j = 0; j < g.vexnum; j++){if(g.edge[n][j] == 1 && visit[j] == 0)DFS(g , j);}	
}

//【15 代码回顾】
//非递归使用栈进行递归模拟
//外层循环遍历图中每个结点，保证每个连通分量的所有结点都被访问到
//每个未被访问的节点i，为起点开始一个新的DFS遍历，未被访问的节点被压入栈
//出栈后，进行访问
int visit[maxsize];
void Visit(int n);
void DFS_UnRecursion(MGraph g){stack<int> st;for(int i = 0 ; i < g.vexnum ; i++){//外层循环if(visit[i] == 0)st.push(i);//DFS-出栈访问、未被访问入栈while(!st.empty()){int w = st.top();st.pop();if(visit[w] == 0){Visit(w);visit[w] = 1;//入栈for(int v = g.vexnum - 1 ; v >= 0; v-- ){if(g.edge[w][v] == 1 && visit[v] == 0)st.push(v);}}}}
}

【2013 2】一个人从2000年1月1日开始，三天打鱼，两天晒网。写一个程序，计算他在以后的某年某月某日是打鱼还是晒网。终止日期从键盘输入。（假设从2000年1月1日开始到2012年11月18日结束。）
要写出月+日的二重数组，输入是年月日，所以代码应该先计算是多少天，再计算是打鱼还是筛网，一组是5天，所以先days%5得到余数，如果是1 2 3则是打鱼 4 0则是晒网
重点是计算有多少天，年注意有闰年和平年的区分

#include<iostream>
using namespace std;
int st_year = 2000 ,st_month = 1 , st_day = 1;
int day_mon[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
int countDay(int year ,int month ,int day){int res = 0;//前几年for(int i = st_year ; i < year ;i++){if(i % 4 == 0)res += 366;elseres += 365；}//该年的月for(int i = 0 ; i < month-1 ; i++){res += day_mon[i];if(i == 1 && (year%4 == 0) )res++;}//该月的天res += day;return res;
}
void main(){int year , month , day;cin >> year >> month >> day >> endl;int num = countDay(year ,month ,day);int judge = num%5;if(judge == 1 || judge == 2 ||judge == 3)cout << "打鱼" <<endl;elsecout << "晒网" <<endl;
}

在这里插入图片描述

#include <iostream>
using namespace std;int st_year = 2000, st_month = 1, st_day = 1;
int day_mon[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 闰年判断
bool isLeapYear(int year) {return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}// 计算从起始日期到给定日期的天数
int countDay(int year, int month, int day) {int res = 0;// 前几年for (int i = st_year; i < year; i++) {if (isLeapYear(i))res += 366;elseres += 365;}// 该年的前几个月for (int i = 0; i < month - 1; i++) {res += day_mon[i];if (i == 1 && isLeapYear(year))  // 如果是闰年的2月，多加1天res++;}// 加上该月的天数res += day - 1;  // 不包含起始日return res;
}int main() {int year, month, day;cout << "请输入年月日（格式：年 月 日）：";cin >> year >> month >> day;int num = countDay(year, month, day);int judge = num % 5;if (judge == 1 || judge == 2 || judge == 3)cout << "打鱼" << endl;elsecout << "晒网" << endl;return 0;
}

【2013 1】交叉奇偶校验检验规则：行和列的1的个数为偶数时，表示正确。例：
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
所有行中1的个数为2，0，4，2 所有列中1的个数为2，2，2，2 请编写一个程序，对给定规模的矩阵(n*n ,> n<1000)进行交叉奇偶校验。若校验正确，则输出“OK”；若不正确且仅有一处错误，则输出“ErrorIn(2,3)”，(2,3)表示第二行第三列出现错误；若不正确且有多出错误，则输出为"Error"。

#include<iostream>
#define maxsize 100
int Count(int vec[] , int n){int num = 0;//记录1的个数for(int i = 0 ; i < n ; i++ ){if(vec[i] == 1)num++;}return num;
}
int main(int matrix[][],int n){								   //问题：【细节】输入学习下方代码int error = 0;//用于判断错误个数int row = -1 , col = -1;//行的判断for(int i = 0 ; i < n ; i++){int num = Count(matrix[i] , n);if(num % 2 == 1){if(row > 0){									   //问题：【细节】这里应该是 >= !cout << "Error" << endl;return 0;}elserow = i;}}//列的判断for(int i = 0 ; i < n ; i++){//第i列int vec[maxsize];for(int j = 0 ; j < n ; j++){vec[j] = matrix[j][i];//vec存储第i列}int num = Count(vec , n);if(num % 2 == 1){if(col > 0){									   //问题：【细节】这里应该是 >= !cout << "Error" << endl;return 0;}elsecol = i;}}if(row > 0 && col > 0) 									   //问题：【细节】这里应该是 >= !cout << "ErrorIn(" << row << "," << col << ")" << endl;//问题：【细节】这里应该是 row+1 和col+1!!elsecout << "OK" << endl;return 0;
}

总结：代码思路实现都不难，还是【细节】出问题！！

#include<iostream>
#include<vector>
using namespace std;int Count(int vec[], int n) {int num = 0;for (int i = 0; i < n; i++) {if (vec[i] == 1)num++;}return num;
}int main() {int n;cin >> n;  // 读取矩阵的大小vector<vector<int>> matrix(n, vector<int>(n));  // 使用动态数组int error = 0;int row = -1, col = -1;// 读取矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> matrix[i][j];}}// 行的判断for (int i = 0; i < n; i++) {int num = Count(matrix[i].data(), n);if (num % 2 == 1) {  // 行错误if (row >= 0) {cout << "Error" << endl;return 0;} else {row = i;}}}// 列的判断for (int i = 0; i < n; i++) {int vec[maxsize];for (int j = 0; j < n; j++) {vec[j] = matrix[j][i];  // vec存储第i列}int num = Count(vec, n);if (num % 2 == 1) {  // 列错误if (col >= 0) {cout << "Error" << endl;return 0;} else {col = i;}}}if (row >= 0 && col >= 0) {cout << "ErrorIn(" << row + 1 << "," << col + 1 << ")" << endl;} else {cout << "OK" << endl;}return 0;
}

【2013 2】二叉树T的先序遍历序列为：DBACEGF，中序遍历序列为：ABCDEFG。

求出其后序遍历的结果。回答：后序遍历为ACBFGED
编写程序，读入先序遍历与中序遍历的结果存入字符数组，并求出后序遍历结果输出。

程序：先读入先序和中序存入字符数组推后序遍历
思路：先还原树，再看后续
不会了，只能写这么多

//数据结构
typedef struct TNode{char data;struct TNode *left ,*right;
}TNode;

#include<iostream>
#define maxsize 100
using namespace std;char preOrder[maxsize];
char inOrder[maxsize];void StructTree(TNode *&t , int root){//递归的底if(preOrder[])//新建节点TNode newNode = (TNode*)malloc(sizeof(TNode));newNode->data = preOrder[root];newNode->left = StructTree(t , root+1);newNode->right = StructTree(t , i+1);}
void PostOrder(TNode *t){if(t == NULL)return;PostOrder(t->left);PostOrder(t->right);cout << t->data;
}
int main(){cin >> "请输入先序遍历序列:";for(int i = 0 ; i < maxsize ; i++)cin >> preOrder[i];cin >> "请输入中序遍历序列:";for(int i = 0 ; i < maxsize ; i++)cin >> inOrder[i];//还原树TNode *t;StructTree(t,0);//确认后序遍历序列PostOrder(T);cout << endl; return 0;
}

在这里插入图片描述

TNode* StructTree(int& preIndex ,int inStart ,int inEnd){if(inStart > intEnd)return nullptr;//先序遍历的根结点char rootData = preOrder[preIndex++];TNode* root = (TNode*)malloc(sizeof(TNode));root->data = rootData;root->left = nullptr;root->right = nullptr;//在中序遍历中找到根结点的位置int rootIndex = inStart;while(inOrder[rootIndex] != rootData)rootIndex++;//构建左子树和右子树root->left = StructTree(preIndex , inStart , rootIndex - 1);root->right = StructTree(preIndex , rootIndex + 1, inEnd);
}// 后序遍历
void PostOrder(TNode* root) {if (root == nullptr)return;PostOrder(root->left);PostOrder(root->right);cout << root->data;
}int main(){
// 输入先序和中序遍历cout << "请输入先序遍历序列:";string preStr;cin >> preStr;for (int i = 0; i < preStr.length(); i++) {preOrder[i] = preStr[i];}cout << "请输入中序遍历序列:";string inStr;cin >> inStr;for (int i = 0; i < inStr.length(); i++) {inOrder[i] = inStr[i];}// 变量初始化int preIndex = 0;int n = preStr.length();  // 先序和中序长度相同// 还原二叉树TNode* root = StructTree(preIndex, 0, n - 1);// 输出后序遍历cout << "后序遍历序列为: ";PostOrder(root);cout << endl;return 0;
}