• Contest2850 - 【在线编程平台】2022年计算机类数据结构作业12.20221201-1206

    目录

    问题 A: 二叉排序树 - 文本输出

    问题 B: 销售排行榜 

    问题 C: 二叉排序树-平衡因子 

    问题 D: 案例 1-1.1 二分查找

    问题 E: 进阶实验 1-3.1：两个有序序列的中位数

    问题 A: 二叉排序树 - 文本输出

    题目描述

    给定一个序列，使用该序列生成二叉排序树（也叫二叉搜索树，BST），然后以本题规定方法输出该二叉排序树。
    例：
    给定一个序列：43 25 29 67 17 88 54 47 35 62
    以第一个数字（43）为根节点，然后将后面的数字依输入次序逐个添加至该树中，得到一个二叉排序树，如下图所示。


    然后先序遍历上面这个树，并按行输出数字。
    其中每个子节点的输出前，需要相较于其父节点前多四个普通空格。
    当某个节点为叶子节点（即无子节点），则该节点的左右叶子节点均不用输出。
    而当某个节点仅有左叶子节点或右叶子节点时，另一个空缺的子节点用#占位。


    以该图为例，其最终输出结果为：
    43
        25
            17
            29
                #
                35
        67
            54
                47
                62
            88

    输入格式

    第一行为正整数n，表示接下来将输入的节点数量。（n<500）
    第二行为n个正整数，每个数字以空格分隔（以第一个数字为根节点）

    输出格式

    以题目描述中的方法输出得到的二叉排序树。
    以第一个数字为根节点，然后将后面的数字依输入次序逐个添加至该树中，得到一个二叉排序树。
    然后先序遍历该树，并按行输出数字。
    其中每个子节点的输出前，需要相较于其父节点前多四个普通空格。
    当某个节点为叶子节点（即无子节点），则该节点的左右叶子节点均不用输出。
    而当某个节点仅有左叶子节点或右叶子节点时，另一个空缺的子节点用#占位。
     

    输入样例 复制

    1. 10
    2. 43 25 29 67 17 88 54 47 35 62

    输出样例 复制

    1. 43
    2.     25
    3.         17
    4.         29
    5.             #
    6.             35
    7.     67
    8.         54
    9.             47
    10.             62
    11.         88
    1. #include
    2. using namespace std;
    3.  
    4. typedef struct node{
    5.     int data;
    6.     node *rchild;
    7.     node *lchild;
    8. }Node,*Tree;
    9.  
    10.  
    11. void creat(Tree &tree,int num)
    12. {
    13.     Tree node = new Node;
    14.     node->data=num;
    15.     node->lchild=NULL;
    16.     node->rchild=NULL;
    17.     if(tree==NULL)
    18.     {
    19.         tree=node;
    20.     }
    21.     else if(num>tree->data)
    22.     {
    23.         creat(tree->rchild,num);
    24.     }
    25.     else
    26.     {
    27.         creat(tree->lchild,num);
    28.     }
    29. }
    30.  
    31.  
    32. void print(Tree tree,int i)
    33. {
    34.     if(tree==NULL)
    35.     return;
    36.     for(int j=0;j
    37.     cout<<"    ";
    38.     cout<data<
    39.     i++;
    40.     if(tree->lchild==NULL&&tree->rchild!=NULL)
    41.     {
    42.         for(int j=0;j
    43.         cout<<"    ";
    44.         cout<<"#"<
    45.     }
    46.     print(tree->lchild,i);
    47.     print(tree->rchild,i);
    48.     if(tree->lchild!=NULL&&tree->rchild==NULL)
    49.     {
    50.         for(int j=0;j
    51.         cout<<"    ";
    52.         cout<<"#"<
    53.     }
    54. }
    55.  
    56. int main()
    57. {
    58.     int n;
    59.     cin>>n;
    60.     int a[505];
    61.     Tree tree;
    62.     tree=new Node;
    63.     tree=NULL;
    64.     for(int i=0;i
    65.     {
    66.         cin>>a[i];
    67.     }
    68.     for(int i=0;i
    69.     {
    70.         creat(tree,a[i]);
    71.     }
    72.     print(tree,0);
    73.     return 0;
    74. }

    问题 B: 销售排行榜 

    题目描述

    你的任务是帮助淘宝网店店长整理销售数据，根据累计的销售记录，将所有商品按销售数量降序排列。

    输入格式

    输入包括多行数据(行数小于100000)，每行数据包括4个信息，分别是商品名称、销售数量、单价、成交日期

    商品名称由小写字母组成，且不超过100个字符，销售数量和单价都是正整数，且小于10000

    输出格式

    输出包括多行数据，将所有在输入中出现的商品按销售数量降序排列，每行数据包括3个信息，分别是商品名称、销售数量、销售额,如果两种商品销售数量一样，则按商品的字母顺序升序排列

    输入样例 复制

    1. apple 1 20 2014-4-2 
    2. basketball 1 20 2014-4-2
    3. computer 1 20 2014-4-2
    4. shoe 1 20 2014-4-2
    5. tv 1 20 2014-4-2
    6. apple 1 18 2014-4-3

    输出样例 复制

    1. apple 2 38
    2. basketball 1 20
    3. computer 1 20
    4. shoe 1 20
    5. tv 1 20
    1. #include
    2. using namespace std;
    3. struct info{
    4.     string name;
    5.     int num;
    6.     int price;
    7.     int flag=1;
    8.     int all=0;
    9. }a[100005];
    10.  
    11. bool mysort1(struct info c,struct info d)
    12. {
    13.     return c.name
    14. }
    15.  
    16. bool mysort2(struct info c,struct info d)
    17. {
    18.     if(c.num==d.num)
    19.     return c.name
    20.     else
    21.     return c.num>d.num;
    22. }
    23.  
    24. int main()
    25. {
    26.     string name;
    27.     int num;
    28.     int price;
    29.     string date;
    30.     int index=0;
    31.     while(cin>>name>>num>>price>>date)
    32.     {
    33.         a[index].price=price;
    34.         a[index].name=name;
    35.         a[index].num=num;
    36.         a[index].all=num*price;
    37.         index++;
    38.         // if(index==6)
    39.         // break;
    40.     }
    41.     sort(a,a+index,mysort1);
    42.     for(int i=1;i
    43.     {
    44.         if(a[i].name==a[i-1].name)
    45.         {
    46.             a[i-1].flag=0;
    47.             a[i].num+=a[i-1].num;
    48.             a[i].all+=a[i-1].all;
    49.         }
    50.     }
    51.     sort(a,a+index,mysort2);
    52.     for(int i=0;i
    53.     {
    54.         if(a[i].flag==1)
    55.         cout<" "<" "<
    56.     }
    57. }

    问题 C: 二叉排序树-平衡因子 

    题目描述

    给定一个序列，使用该序列生成二叉排序树，然后以本题规定方法输出该二叉排序树。
    例：
    给定一个序列：43 25 29 67 17 88 54 47 35 62
    以第一个数字（43）为根节点，然后将后面的数字依输入次序逐个添加至该树中，得到一个二叉排序树

    然后先序遍历上面这个树，并按行输出数字。
    其中每个子节点的输出前，需要相较于其父节点前多四个普通空格。
    当某个节点为叶子节点（即无子节点），则该节点的左右叶子节点均不用输出。
    而当某个节点仅有左叶子节点或右叶子节点时，另一个空缺的子节点用#占位。
    对于非空的节点，求出其平衡因子，并用括号括起来输出在结果中
    以该图为例，其最终输出结果为：
    43(0)
        25(-1)
            17(0)
            29(-1)
                #
                35(0)
        67(1)
            54(0)
                47(0)
                62(0)
            88(0)

    输入样例 复制

    1. 10
    2. 43 25 29 67 17 88 54 47 35 62

    输出样例 复制

    1. 43(0)​
    2.     25(-1)
    3.         17(0)
    4.         29(-1)
    5.             #
    6.             35(0)
    7.     67(1)
    8.         54(0)
    9.             47(0)
    10.             62(0)
    11.         88(0)
    1. #include
    2. using namespace std;
    3.  
    4. typedef struct node{
    5.     int data;
    6.     int height=0;
    7.     node *rchild;
    8.     node *lchild;
    9. }Node,*Tree;
    10.  
    11. int depth=0;
    12.  
    13. int height(Tree &t)
    14. {
    15.     if(t==NULL)
    16.     return 0;
    17.     t->height=max(height(t->lchild),height(t->rchild))+1;
    18.     return t->height;
    19. }
    20.  
    21.  
    22.  
    23. void creat(Tree &tree,int num)
    24. {
    25.     Tree node = new Node;
    26.     node->data=num;
    27.     node->lchild=NULL;
    28.     node->rchild=NULL;
    29.     if(tree==NULL)
    30.     {
    31.         tree=node;
    32.     }
    33.     else if(num>tree->data)
    34.     {
    35.         creat(tree->rchild,num);
    36.     }
    37.     else
    38.     {
    39.         creat(tree->lchild,num);
    40.     }
    41. }
    42.  
    43.  
    44. void print(Tree tree,int i)
    45. {
    46.     if(tree==NULL)
    47.     return;
    48.     for(int j=0;j
    49.     cout<<"    ";
    50.     cout<data;
    51.     if(tree->lchild==NULL&&tree->rchild==NULL)
    52.     cout<<"("<<0<<")"<
    53.     else if(tree->lchild==NULL&&tree->rchild!=NULL)
    54.     cout<<"("<rchild->height*-1<<")"<
    55.     else if(tree->lchild!=NULL&&tree->rchild==NULL)
    56.     cout<<"("<lchild->height<<")"<
    57.     else
    58.     cout<<"("<lchild->height-tree->rchild->height<<")"<
    59.     i++;
    60.     if(tree->lchild==NULL&&tree->rchild!=NULL)
    61.     {
    62.         for(int j=0;j
    63.         cout<<"    ";
    64.         cout<<"#"<
    65.     }
    66.     print(tree->lchild,i);
    67.     print(tree->rchild,i);
    68.     if(tree->lchild!=NULL&&tree->rchild==NULL)
    69.     {
    70.         for(int j=0;j
    71.         cout<<"    ";
    72.         cout<<"#"<
    73.     }
    74. }
    75.  
    76. int main()
    77. {
    78.     int n;
    79.     cin>>n;
    80.     int a[505];
    81.     Tree tree;
    82.     tree=new Node;
    83.     tree=NULL;
    84.     for(int i=0;i
    85.     {
    86.         cin>>a[i];
    87.     }
    88.     for(int i=0;i
    89.     {
    90.         creat(tree,a[i]);
    91.     }
    92.     height(tree);
    93.     print(tree,0);
    94.     return 0;
    95. }

    问题 D: 案例 1-1.1 二分查找

    题目描述

      给定大小为N(0

    输入格式

    第一行 数组大小 N
    第二行 数组A[]
    第三行 带查找的整数X

    输出格式

    如找到X，则输出第一次出现的位置。如未找到，则输出-1。

    输入样例 复制

    1. 5
    2. 1 2 4 4 5 
    3. 4

    输出样例 复制

    3
    1. #include
    2. using namespace std;
    3. int a[1005];
    4.  
    5. int main()
    6. {
    7.     int n;
    8.     cin>>n;
    9.     int t;
    10.     for(int i=0;i
    11.     {
    12.         cin>>a[i];
    13.     }
    14.     cin>>t;
    15.      for(int i=0;i
    16.      {
    17.         if(a[i]==t)
    18.         {
    19.             cout<1;
    20.             return 0;
    21.         }
    22.      }
    23.      cout<<-1;
    24. }

    问题 E: 进阶实验 1-3.1：两个有序序列的中位数

    题目描述

        已知有两个等长非降序序列S1，S2。先将S1，S2合并为S3，求S3的中位数。长度为N的非降序序列SN的中位数为第X个数，Ｘ＝不超过（N+１）／２的最大整数。

    输入格式

    第一行，序列S１，S２的长度Ｎ
    第二行，序列S１的N个整数
    第三行，序列S２的N个整数

    输出格式

    输出两个序列合并后序列S３的中位数

    输入样例 复制

    1. 5
    2. 1 3 5 7 9
    3. 2 3 4 5 6

    输出样例 复制

    4
    1. //这里耍了个小聪明，没有合并，不要学我
    2. #include
    3. using namespace std;
    4. int a[10005];
    5. int b[10005];
    6.  
    7. int main()
    8. {
    9.     int n;
    10.     int index=0;
    11.     cin>>n;
    12.     for(int i=0;i
    13.     cin>>a[i];
    14.     for(int i=0;i
    15.     cin>>b[i];
    16.     int i=0,j=0;
    17.     while(1)
    18.     {
    19.         int temp=0;
    20.         if(a[i]<=b[j])
    21.         {
    22.             temp=a[i];
    23.             i++;
    24.         }
    25.         else
    26.         {
    27.             temp=b[j];
    28.             j++;
    29.         }
    30.         index++;
    31.         if(index==n)
    32.         {
    33.             cout<
    34.             return 0;
    35.         }
    36.     }
    37.     return 0;
    38. }

  • 相关阅读:
    超详细Docker部署SpringBoot+Vue项目（三更博客项目部署）
    Spring Boot 整合Redis实现消息发布与订阅
    csp-202206
    Java 7 生命周期结束
    腾讯地图开发填坑总结
    Java后端小伙两周斩获字节2-2offer 面经总结
    pandas学习（三） grouping
    基于Doris构建亿级数据实时数据分析系统
    Spring Cloud Feign实战
    GIS之深度学习03：Anaconda无法正常启动问题汇总（更新）
  • 原文地址：https://blog.csdn.net/weixin_61133168/article/details/128196134