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=...
PTA-学校-数据结构（二叉树的非递归遍历）
1-7 二叉树的非递归遍历 分数 5 作者 陈越 单位 浙江大学 本题要求用非递归的方法实现对给定二叉树的 3 种遍历。 函数接口定义： void InorderTraversal( BinTree BT );void PreorderTraversal( BinTree BT );void PostorderTraversal( BinTree BT ); 其中BinTree结构定义如下： typedef struct TNode *Position;typedef Position BinTree;struct TNode{ ElementType Data; BinTree Left; BinTree Right; int flag;}; 要求 3 个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。 此外，裁判程序中给出了堆栈的全套操作，可以直接调用。 裁判测试程序样例： #include <stdio.h>#include <stdlib.h>typedef enum { fa...
2025-2026-1《数据结构》测验1（线性结构）总结
2025-2026-1《数据结构》测验1（线性结构）总结 一、关于数据结构的说法，正确的是 ( )。 题干：以下关于数据结构的说法中，正确的是 ( )。 A. 数据的逻辑结构独立于其存储结构 B. 数据的存储结构独立于其逻辑结构 C. 数据的逻辑结构唯一决定了其存储结构 D. 数据结构仅由其逻辑结构和存储结构决定 答案：A 解析： 数据的逻辑结构是指数据元素之间的逻辑关系（如线性、树、图等），是抽象的概念，与存储方式无关； 数据的存储结构是逻辑结构在计算机中的物理实现（如顺序存储、链式存储等），依赖于逻辑结构但不被其唯一决定（同一逻辑结构可对应多种存储结构）； 数据结构由逻辑结构、存储结构和运算三部分组成，并非仅前两者。 因此，只有 A 选项正确。 二、下列程序段的时间复杂度是（ ）。 题干： int sum = 0;for(int i = 1; i < n; i *= 2) for(int j = 0; j < i; j++) sum++; A. O(logn) B. O(nlogn) C. O(n) D. O(n²) 答案：C 解析： 外...
PTA-学校-数据结构（二叉树求深度和叶子数、先序输出叶结点、层次遍历）
1-4 二叉树求深度和叶子数 分数 3 作者 鲁法明 单位 浙江大学 编写函数计算二叉树的深度以及叶子节点数。二叉树采用二叉链表存储结构 函数接口定义： int GetDepthOfBiTree ( BiTree T);int LeafCount(BiTree T); 其中 T是用户传入的参数，表示二叉树根节点的地址。函数须返回二叉树的深度（也称为高度）。 裁判测试程序样例： //头文件包含#include<stdlib.h>#include<stdio.h>#include<malloc.h>//函数状态码定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INFEASIBLE -2#define NULL 0typedef int Status;//二叉链表存储结构定义typedef int TElemType;typedef struct BiTNode{ ...