PTA-学校-数据结构（排序）
2-1 直接插入排序 分数 4 作者 DS课程组 单位 临沂大学 本题要求实现直接插入排序函数，待排序列的长度1<=n<=1000。 函数接口定义： void InsertSort(SqList L); 其中L是待排序表，使排序后的数据从小到大排列。 ###类型定义： typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; 裁判测试程序样例： #include<stdio.h>#include<stdlib.h>typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length;...
PTA-学校-数据结构（图）
1-1 采用邻接矩阵表示法创建无向图 分数 4 作者 王东 单位 贵州师范学院 采用邻接矩阵表示法创建无向图G ，依次输出各顶点的度。 函数接口定义： void CreateUDN(AMGraph &G); 其中 G 是采用邻接矩阵表示的无向图。 裁判测试程序样例： #include <stdio.h>#define MVNum 100 typedef struct{ char vexs[MVNum]; int arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph;void CreateUDN(AMGraph &G);int main(){ AMGraph G; int i , j,sum=0; CreateUDN(G); for(i = 0 ; i < G.vexnum ; ++i){ sum=0; ...
PTA-学校-数据结构（树2-2以后）
2-3 有趣的最近公共祖先问题 分数 4 作者 章立晨 单位 浙大城市学院 给出一颗二叉树的后序遍历和中序遍历，你能计算出两个结点的最近公共祖先吗？ 输入格式: 第一行给出两个整数N(N<=10000)和M(M<=10000)，分别代表二叉树的结点数和我们接下来的询问数。 第二行和第三行分别给出N个整数，每个整数用空格分开，分别代表二叉树的后序遍历和中序遍历。 接下来M行，每行给出两个整数，代表我们要询问的两个结点的编号a和b。 输出格式: 对于每个我们要求的询问： 1.如果a和b中有一个或两个不在树上，输出"ERROR"。 2.否则在一行中输出一个整数，表示a和b的最近公共祖先。 输入样例: 在这里给出一组输入。例如： 3 32 3 12 1 31 22 30 3 输出样例: 在这里给出相应的输出。例如： 11ERROR 解析 #include <iostream>#include <vector>#include <unordered_map>#include <stack>#include &l...
PTA-学校-数据结构（求根结点到x结点的路径）
2-2 求根结点到x结点的路径 分数 4 作者 王东 单位 贵州师范学院 求根结点到x结点的路径（假定结点不重复）。 输入样例： 输入一行字符序列先序递归构建二叉树。每个字符对应一个结点，#表示空结点。第二行输入一个结点值x。 52#3##41##6##3 输出样例： 输出从根到结点x的路径。 5 2 3 解析 #include <iostream>#include <cstdlib> #include <queue>using namespace std;// 二叉树节点结构typedef struct BiTNode { char data; struct BiTNode* lchild, * rchild;}BiTNode, * BiTree;BiTNode* buildTree(const string& pre, int& index) { char c = pre[index]; index++; if (c == '#') { return NULL;...
PTA-学校-数据结构（玩转二叉树）
2-1 玩转二叉树 分数 6 作者 陈越 单位 浙江大学 给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。 输入格式： 输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。 输出格式： 在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。 输入样例： 71 2 3 4 5 6 74 1 3 2 6 5 7 输出样例： 4 6 1 7 5 3 2 解析 #include <iostream>#include <queue>using namespace std;// 二叉树节点结构typedef struct BiTNode { int data; struct BiTNode* lchild, * rchild;}BiTNode, * BiTree;// 独立的节点创建函数（替代构造函数，负责初始化节点）B...
PTA-学校-数据结构（最宽层次结点数、确定二叉树）
1-8 最宽层次结点数 分数 4 作者 DS课程组 单位 临沂大学 本题要求实现一个函数，返回给定的二叉树的中最宽层次的结点数，这里最宽层次指的是该层上的结点最多。 函数接口定义： int MaxWidth(BiTree T); T是二叉树树根指针，MaxWidth函数统计T中每层结点数并返回最大值，空树返回0。 其中BinTree结构定义如下： typedef char ElemType;typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild;}BiTNode, *BiTree; 裁判测试程序样例： #include <stdio.h>#include <stdlib.h>typedef char ElemType;typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;BiTree Creat...
线性方程组零解、非零解的条件总结
线性方程组零解、非零解的条件总结 线性方程组分齐次线性方程组（Ax=0，常数项全为 0）和非齐次线性方程组（Ax=b，b≠0，常数项不全为 0），两者的零解、非零解条件差异显著，核心围绕 “系数矩阵的秩 r (A)”“增广矩阵的秩 r (A,b)”“未知数个数 n” 展开。 一、齐次线性方程组（Ax=0） 齐次方程组的特点是：一定有零解（x₁=x₂=…=xₙ=0 代入方程恒成立），重点关注 “是否存在非零解”。 1. 零解的条件 无需额外条件 —— 齐次方程组必有零解。仅当 “只有零解” 时需满足：r (A) = n（系数矩阵的秩等于未知数个数）。 若 A 是 n 阶方阵（方程个数 = 未知数个数），等价于：|A| ≠ 0（系数行列式不为 0）。 2. 非零解的条件 存在非零解（即有无穷多解，含零解和无数非零解）的充要条件：r (A) ＜ n（系数矩阵的秩小于未知数个数）。 若 A 是 n 阶方阵，等价于：|A| = 0（系数行列式为 0）。 推论：当方程个数 m ＜ 未知数个数 n 时，r (A) ≤ m ＜ n，此时齐次方程组必有非零解。 二、非齐次线性方程组（Ax=...