数据结构——平衡二叉树PTA习题(很多不会的,求大佬帮忙写题解)

简介: 数据结构——平衡二叉树PTA习题(很多不会的,求大佬帮忙写题解)

单选题


image.png

image.png

image.png

image.png


选择题题解


2、如图所示



3、转的过程:


  • 插入48之后属于右左双旋转的情况,按照图示的方法先做右单旋转,再做左单旋转


  • 右单旋转:以37为轴,53顺时针旋转(向下),原本是37左孩子的48成为53的左孩子


  • 24的右孩子由53变为37


  • 左单旋转:仍然以37为轴,24逆时针旋转(向下),成为37的左孩子


24的左子树高度为1,右字数高度为3,属于RL型,RL型的变化就这么做的,具体RL型解释如下



具体的RL型的旋转规则,大佬说记住就可以了,哎拼命记吧。


从第四题之后都暂时不会,望各位大佬留言赐教,补充题解


编程题


7-3 插入排序还是堆排序 (25分) 不会


根据维基百科的定义:


插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。


堆排序也是将输入分为有序和无序两部分,迭代地从无序部分找出最大元素放入有序部分。它利用了大根堆的堆顶元素最大这一特征,使得在当前无序区中选取最大元素变得简单。


现给定原始序列和由某排序算法产生的中间序列,请你判断该算法究竟是哪种排序算法?


输入格式:


输入在第一行给出正整数 N (≤100);随后一行给出原始序列的 N 个整数;最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。


输出格式:


首先在第 1 行中输出Insertion Sort表示插入排序、或Heap Sort表示堆排序;然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔,且行首尾不得有多余空格。


输入样例 1:


10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0


输出样例 1:


Insertion Sort
1 2 3 5 7 8 9 4 6 0


输入样例 2:


10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9


输出样例 2:


Heap Sort
5 4 3 1 0 2 6 7 8 9


代码


#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = 2e4+100;
int a[maxn];
int b[maxn];
void cal(int l,int r){
    int i=l,j=i*2;
    while(j<=r){
        if(j+1<=r&&b[j]<b[j+1])
            j++;
        if(b[j]>b[i]){
            swap(b[i],b[j]);
            i=j;
            j=i*2;
        }
        else
            break;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&b[i]);
    }
    int flag=-1;
    int i;
    for( i=1; i<=n; i++)
    {
        if(i==1)
            continue;
        else if(b[i]>=b[i-1])
            continue;
        else
        {
            flag=i;
            break;
        }
    }
    if(flag!=2)
    {
        sort(b+1,b+flag+1);
        printf("Insertion Sort\n");
        for(int i=1; i<=n; i++)
        {
            if(i==1)
                printf("%d",b[i]);
            else
                printf(" %d",b[i]);
        }
        printf("\n");
    }
    else
    {
        printf("Heap Sort\n");
        int pos=n;
        while(pos>=2&&b[pos]>b[pos-1])
            pos--;
            swap(b[1],b[pos]);
        cal(1,pos-1);
        for(int i=1; i<=n; i++)
        {
            if(i==1)
                printf("%d",b[i]);
            else
                printf(" %d",b[i]);
        }
        printf("\n");
    }
    return 0;
}


7-4 愿天下有情人都是失散多年的兄妹 (25分)


呵呵。大家都知道五服以内不得通婚,即两个人最近的共同祖先如果在五代以内(即本人、父母、祖父母、曾祖父母、高祖父母)则不可通婚。本题就请你帮助一对有情人判断一下,他们究竟是否可以成婚?


输入格式:


输入第一行给出一个正整数N(2 ≤ N ≤104 ),随后N行,每行按以下格式给出一个人的信息:


本人ID 性别 父亲ID 母亲ID


其中ID是5位数字,每人不同;性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考,则相应的ID位置上标记为-1。


接下来给出一个正整数K,随后K行,每行给出一对有情人的ID,其间以空格分隔。


注意:题目保证两个人是同辈,每人只有一个性别,并且血缘关系网中没有乱伦或隔辈成婚的情况。


输出格式:


对每一对有情人,判断他们的关系是否可以通婚:如果两人是同性,输出Never Mind;如果是异性并且关系出了五服,输出Yes;如果异性关系未出五服,输出No。


输入样例:


24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011


输出样例:


Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No


代码


#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int Inf = 1e5 + 5;
vector<int> vec[Inf];   // 存关系图 
bool vis[Inf];        // 标记五服以内的亲属 
char sex[Inf];        // 记录性别 
bool flag;          // 标记情侣是否为近亲 
void Dfs(int x, int num)  // num表示第几代,从0开始 
{
  if (num >= 4)     // 超过五代直接退出 
    return;
  for (int i = 0; i < vec[x].size(); i++)
  {
    if (!vis[vec[x][i]])
    {
      vis[vec[x][i]] = 1; // 标记出现的人 
      Dfs(vec[x][i], num + 1);
    }
    else
      flag = 1;   //五服之内出现一样的人 
  }
}
int main()
{
  int T;
  cin >> T;
  while (T--)
  {
    int t, fa, ma;
    char ch;
    scanf("%d ", &t);
    sex[t] = getchar();
    scanf(" %d %d", &fa, &ma);
    if (fa != -1)   // -1不用保存,避免数据处理不当导致数组越界 
    {
      vec[t].push_back(fa); // 保存双亲 
      sex[fa] = 'M';  // 记录父亲性别 
    }
    if (ma != -1)
    {
      vec[t].push_back(ma);
      sex[ma] = 'F';
    }
  }
  cin >> T;
  while (T--)
  {
    int x, y;
    scanf("%d %d", &x, &y);
    if (sex[x] == sex[y]) // 同性 
      cout << "Never Mind" << endl;
    else
    {
      memset(vis, 0, sizeof(vis));  // 每次都初始化一下,每个人的五服亲戚不一样
      vis[x] = 1;
      vis[y] = 1;
      flag = 0;
      Dfs(x, 0);
      Dfs(y, 0);
      if (flag) // 被标记过说明这两人为近亲 
        cout << "No" << endl;
      else
        cout << "Yes" << endl;
    }
  }
  return 0;
}
相关文章
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
2月前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
36 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
3月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
6月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
43 2
|
6月前
|
存储 算法 测试技术
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
79 1
|
6月前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
48 1
|
6月前
|
机器学习/深度学习
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
42 1
|
6月前
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
80 1
|
6月前
|
算法
数据结构和算法学习记录——平衡二叉树(基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度)
数据结构和算法学习记录——平衡二叉树(基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度)
67 0