当前位置： 首页 > article >正文

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

article 2024/11/5 23:24:33
11.52013年真题*4

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

  1. 如果程序设计题写不了 核心算法 ，但是把思路写上去，只将核心函数空出来也能拿些分！！
  2. 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;
		else
			res += 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;
	else
		cout << "晒网" <<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;
        else
            res += 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;
    else
        cout << "晒网" << 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;}
			else
				row = 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;}
			else
				col = i;
		}
	}
	if(row > 0 && col > 0) 									   //问题：【细节】这里应该是 >= !
		cout << "ErrorIn(" << row << "," << col << ")" << endl;//问题：【细节】这里应该是 row+1 和col+1!!
	else
		cout << "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;
}

http://www.kler.cn/a/380765.html

相关文章：

  • 计算机网络：网络层 —— 网络地址转换 NAT
  • 一二三应用开发平台自定义查询设计与实现系列3——通用化重构
  • DCN网络进行新冠肺炎影像分类
  • Python毕业设计选题：基于django+vue的4S店客户管理系统
  • RV1126-SDK学习之OSD实现原理
  • 为什么要使用Docker？
  • leetcode-3-无重复字符的最长子串
  • Pr 视频效果：过渡
  • 使用Python Flask实战构建Web应用
  • 告别传统营销，HubSpot AI分析工具带你玩转新潮流
  • BERT预训练的MLM和NSP任务的损失函数都是什么？
  • 一文快速预览经典深度学习模型（一）——CNN、RNN、LSTM、Transformer、ViT
  • 架构师之路-学渣到学霸历程-43
  • 只允许指定ip远程连接ssh
  • 【3】流程控制
  • HarmonyOS鸿蒙开发入门，常用ArkUI组件学习（一）
  • Spring cloud
  • QT下载安装
  • 为什么要使用Docker？
  • c# 值类型
  • 青少年编程与数学 02-003 Go语言网络编程 02课题、网络分层模型
  • RHCE selinux 和 防火墙（fireword|iptable）
  • 【里程计在激光雷达SLAM中的作用】【gmapping算法hector_mapping算法】
  • 基于 LR(1) 和 LALR 的 Parser Generator
  • （九）JavaWeb后端开发——Servlet
  • 关于read/write 网络IO、硬盘IO的区别