NOIP2013第十九届普及组初赛题目C++和答案-

由天下分享时间：2024/12/26 5:04:42 加入收藏我要投稿点赞

int main() { int a, b, u, i, num;

cin>>a>>b>>u; num = 0; for (i = a; i <= b; i++) if ((i % u) == 0) num++;

cout<

} 输入：1 100 15 输出：

_________

3. #include using

namespace std;

int main() { const int SIZE = 100;

int n, f, i, left, right, middle, a[SIZE]; cin>>n>>f; for (i = 1; i <= n; i++) cin>>a[i]; left = 1; right = n; do {

middle = (left + right) / 2; if (f <= a[middle]) right = middle; else

left = middle + 1; } while (left < right); cout<

2 4 6 9 11 15 17 18 19 20 21 25 输出：_________

CCF NOIP2013 初赛普及组 C++语言试题第

6 页，共 10 页

4. #include using

namespace std; int main() {

const int SIZE = 100; int height[SIZE], num[SIZE], n, ans; cin>>n;

for (int i = 0; i < n; i++) { cin>>height[i]; num[i] = 1; for (int j = 0; j < i; j++) {

if ((height[j] < height[i]) && (num[j] >= num[i])) num[i] = num[j]+1; } } ans = 0;

for (int i = 0; i < n; i++) {

if (num[i] > ans) ans = num[i]; }

cout<

2 5 3 11 12 4 输出：_________

四、完善程序（共 2 题，每题 14 分，共计 28 分）

1. （序列重排）全局数组变量 a 定义如下： const

int SIZE = 100; int a[SIZE], n; 它记录着一个长度为 n 的序列 a[1], a[2], …, a[n]。

现在需要一个函数，以整数 p (1 ≤ p ≤ n)为参数，实现如下功能：将序列 a 的前 p 个数与后 n – p 个数对调，且不改变这 p 个数（或 n – p 个数）之间的相对位置。例如，长度为 5 的序列 1, 2, 3, 4, 5，当 p = 2 时重排结果为 3, 4, 5, 1, 2。

CCF NOIP2013 初赛普及组 C++语言试题第

7 页，共 10 页

有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n)、空间复杂度为 O(n)：

void swap1(int p) {

int i, j, b[SIZE];

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

b[ (1) ] = a[i]; for (i = p + 1; i <= n; i++) b[i - p] = (2) ;

for (i = 1; i <= (3) ; i++) a[i] = b[i]; }

我们也可以用时间换空间，使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法：

void swap2(int p) {

int i, j, temp;

for (i = p + 1; i <= n; i++) { temp = a[i]; for (j = i; j >= (4) ; j--) //（3 分） a[j] = a[j - 1];

//（3 分） //（3 分） //（2 分）

(5) = temp; } }

//（3 分）

2. （二叉查找树）二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的

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

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

CCF NOIP2013 初赛普及组 C++语言试题第

8 页，共 10 页

#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) ) && //（3 分） (is_bst(a[root].left_child, lower_bound, cur) == 1) &&

(is_bst( (2) , (3) , (4) ) == 1))

//（3 分，3 分，3 分）

return 1; return 0; } int main()