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{ ...
PTA-学校-数据结构（统计度为1的结点数、二叉树求结点数、求二叉树的高度）
1-1 统计度为1的结点数 分数 3 作者 黄龙军 单位 绍兴文理学院 要求实现函数，统计并返回二叉树中的度为1的结点数。二叉树采用二叉链表存储，结点结构如下： struct BiTNode { // 结点结构 char data; // 结点数据域 BiTNode *lchild, *rchild; // 左、右孩子指针}; 函数接口定义： int CountSingle(BiTNode *T); 其中参数 T是指向二叉树根结点的指针。 裁判测试程序样例： #include<iostream>#include<string>using namespace std;struct BiTNode { char data; BiTNode *lchild, *rchild;};int CountSingle(BiTNode *T); // 统计并返回度为1的结点数BiTNode *CreateBiTree(string ...
PTA-学校-数据结构（顺序队列的3个操作、链式队列的3个操作）
2-11 顺序队列的3个操作 分数 6 作者 陈越 单位 浙江大学 请编写程序，将 n+1 个整数顺序压入容量为 n 的队列，随后执行 n+1 次取队首并出队的操作。 输入格式： 输入首先在第一行给出正整数 n（≤104）；随后一行给出 n+1 个 int 范围内的整数，数字间以空格分隔。 输出格式： 将输入的n+1 个整数顺序压入容量为 n 的队列，随后执行 n+1 次取队首并出队的操作，输出取出的元素的值，每行一个。 注意：当队列已满时，入队操作应该不执行，并在一行中输出错误信息 错误：队列已满。；当队列为空时，取队首和出队操作应该不执行，并在一行中输出错误信息 错误：队列为空。。空队列取队首应返回 -1。 输入样例： 51 2 3 4 5 6 输出样例： 错误：队列已满。12345错误：队列为空。-1错误：队列为空。 解析（直接用queue库） #include <iostream>#include <queue>using namespace std;int main() { int n; cin >> n; int i = ...