NOIP2013初赛普及组C++题目及答案

值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。

输入的第一行包含一个整数 n，表示这棵树有 n 个顶点， 编号分别为 1, 2, ? , n，其 中编号为 1 的为根结点。之后的第 i 行有三个数 value, left_child , right_child ，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用 0 代替。输出 1 表示这棵树是二叉查找树，输出0 则表示不是。

#include using namespace std;const int SIZE = 100; const int INFINITE = 1000000; struct node {

int left_child, right_child, value; };node a[SIZE];

int is_bst(int root, int lower_bound, int upper_bound) {

int cur;

if (root == 0)

return 1;

cur = a[root].value;

if ((cur > lower_bound) && ( (1) ) && (is_bst(a[root].left_child, lower_bound, cur) == 1) && (is_bst( (2) , (3) , (4) ) == 1))

return 1; return 0; }

int main() {

int i, n; cin>>n;

for (i = 1; i <= n; i++)

cin>>a[i].value>>a[i].left_child>>a[i].right_child; cout<

6

第十九届全国青少年信息学奥林匹克联赛初赛

普及组参考答案

一、单项选择题（共20 题，每题1.5分，共计30分） 1 A 11 A

2 A 12 A 3 B 13 D 4 C 14 A 5 D 15 C 6 B 16 C 7 B 17 A 8 C 18 D 9 A 19 A 10 C 20 B

二、问题求解（共2 题，每题 5 分，共计 10 分；每题全部答对得5 分，没有部分分） 1. 14

2. s1 = 0，s2 = 1，s3 = 1，s4 = 1

三、阅读程序写结果（共 4 题，每题 8 分，共计 32 分） 1. 2. 3. 4.

3+5=8 6 7 4

四、完善程序（共计 28 分，以下各程序填空可能还有一些等价的写法，由各省赛区组织本省专家审定及上机验证，可以不上报CCF NOI 科学委员会复核） 1. (1) n –p + i (2) a[i] (3) n (4) i –p + 1 (5) a[i–p]

2. (1) cur < upper_bound (2) a[root].right_child (3) cur (4) upper_bound (5) 1

7