Dotcpp > 试卷列表 > （笛卡尔树）对于一个给定的两两不等的正整数序列，

（笛卡尔树）对于一个给定的两两不等的正整数序列，

"NOIP真题" 试卷中 NOIP第十七届全国青少年信息学奥林匹克联赛初赛试题[2011提高组] 中有题目如下：

（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树。首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父结点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列 7、2 、12 、1、10 、5、15 、3 ，下图就是一棵对应的笛卡尔树。现输入序列的规模 n（1<=n<100 ）和序列的 n 个元素，试求对应的笛卡尔树的深度 d（根节点深度为 1），以及有多少个叶节点的深度为 d 。

QQ截图20210120141530.png

【程序清单】

#include <iostream>
using namespace std;
const int SIZE = 100+5;
const int INFINITY = 1000000;
int n, a[SIZE], maxDeep, num;
void solve(int left, int right, int deep){
    int i, j, min;
    if (deep > maxDeep) {
        maxDeep = deep;
        num = 1;
    }else if (deep == maxDeep)
        ①;
    min = INFINITY;
    for (i = left; i <= right; i++)
        if (min > a[i]) {
            min = a[i];
            ②;
        }
    if(left < j)③;
    if(j < right)④;
}
int main(){
    int i;
    cin>>n;
    for (i = 1; i <= n; i++)
        cin>>a[i];
    maxDeep = 0;
    solve(1, n, 1);
    cout<<maxDeep<<' '<<num<<endl;
    return 0;
}

共 12 分　

所属试卷：NOIP第十七届全国青少年信息学奥林匹克联赛初赛试题[2011提高组]

其它题目

有如下程序，若程序的输出结果是123，则程序中下划线处

下列程序逆序打印所输入正整数的各位数字，例如输入134

程序流程图中带有箭头的线段表示的是（）。

有以下程序：程序运行后的输出结果是。

有以下程序程序运行后的输出结果是。

已知x=[1，2，3，2，3]，执行语句x.remov

在循环语句中，_______语句的作用是提前进入下一次

def f1:a, b=1,2return b,

IP地址能够唯一地确定Internet上每台计算机与每

在/home目录中查找所有的用户目录的命令是_____

下面给出了一个SHELL程序，试对其行后有#（n）形式

在客户/服务器结构中，DBMS运行在。

下述哪一条是顺序存储结构的优点？

一组记录的关键码为（46，79，56，38，40，84

强连通图的各顶点间均可达。

关系数据库中，主键是( )

在视图上不能完成的操作是( )

当a=3，b=2，c=1时，执行以下程序段后a=___

则z的值为_____。

结构体是不同数据类型的数据集合，作为数据类型，必须先说

函数fun的功能是：从三个形参a，b，c中找出中间的那

有以下程序程序的运行结果是

给定程序中，函数fun的功能是根据形参i的值返回某个函

下面属于系统软件的是

程序运行后的输出结果是

如右图所示，共有 13个格子。对任何一个格子进行一次操

一棵结点数为2015 的二叉树最多有（）个叶子结点。

（笛卡尔树）对于一个给定的两两不等的正整数序列，

有 6 个城市，任何两个城市之间都有一条道路连接， 6

冗余数据是指可以由其他数据导出的数据，例如，数据库中已

更多选择题

更多填空题

题量:	0 道
总分:	分

（笛卡尔树）对于一个给定的两两不等的正整数序列，

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

（笛卡尔树 ）对于一个给定的两两不等的正整数序列，

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

（笛卡尔树）对于一个给定的两两不等的正整数序列，