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{ ...
