当前没有测试数据。

全国青少年信息学奥林匹克联赛初赛模拟考试（四） （ 普及组 C++ 语言 两小时完成 ） ●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●● 一、单项选择题（共 15 题，每题 2 分，共计 30 分。每题有且仅有一个正确选项。） 1、补码（10011001）2的原码是（） A、10011001 B、01100110 C、11100110 D、11100111 2、计算机中，决定计算机寻址大小的是（） A、内存 B、寄存器 C、数据总线 D、地址总线 3、在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。 A．系统分配的栈空间溢出 B．系统分配的堆空间溢出 C．系统分配的队列空间溢出 D．系统分配的链表空间溢出 4、从 ENIAC 到当前最先进的计算机，冯·诺依曼体系结构始终占有重要的地位。冯·诺依曼体系结构的核心内容是（ ）。 A、采用开关电路 B、采用半导体器件 C、采用存储程序和程序控制原理 D、采用键盘输入 5、在 C++程序中,表达式 23|2^5 的值是( ) A. 23 B. 1 C.32 D.18 6、已知7个结点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号,以下同),中根遍历 是4 2 6 5 1 7 3,则该二叉树的后根遍历是( ) A. 4 6 5 2 7 3 1 B. 4 6 5 2 1 3 7 C. 4 2 3 1 5 4 7 D. 4 6 5 3 1 7 2 7、一颗完全二叉树可以使用数组表示，现在标记根为0（即数组第0个元素为二叉树的根），已知一个节点的下标为i，则该节点的父节点下标为（）。 A、（i＋1）／2 B、i－2 C、（i－1）／2 D、i／2 8、已知一个栈的空间大小为3，元素 a b c d e 顺序入栈，那么下面不能的出栈顺序是（） A、a b c d e B、b c d e a C、d c b a e D、c d e b a 9、（ ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。 A．动态规划 B．贪心 C．分治 D．搜索 10、与十进制数28.5625相等的四进制数是（） A、130.5625 B、13.21 C、130.21 D、130.5 11、已知x=（0.1011010）2 ，则[X/2]补=（ ）2 A、0.1011101 B、11110110 C、0.0101101 D、0.100110 12、地面上有标号为A、B、C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3……，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在C柱上，从下到上的编号为（ ）。 A．2 4 3 6 5 7 B．2 4 1 2 5 7
C．2 4 3 1 7 6 D．2 4 3 6 7 5 13、完全二叉树的节点个数为11，则它的最后一层叶结点个数为（ ）。 A.4 B.3 C.5 D.2 14、对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的。 A、a B、b C、c D、d 15、现在有5个字母 A、B、C、D、E出现的频率分别为10，2，3，5，8，问由这些字母构成的哈夫曼树最长的编码长度为（ ）。 A、1 B、2 C、3 D、4 二、阅读程序写结果（共 4 题，每题 8 分，共计 32 分） 1、

1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 void my_strip(char* str){
5	int len = strlen(str);
6	if( 0 == len )
7		return;
8   for( int i = 0; i < len; ++i )
9		if( isalpha(str[i]) )
10			str[i] |= 32;
11		else if( str[i] == ' ')
12			str[i] = ':';	
13 }
14 int main(){
15	char str[64];
16	gets(str);
17	my_strip(str);
18	cout << str;
19	return 0;
20 }

判断题 1、第10行str[i] |=32换成str[i]+=32效果相同（） 2、 函数my_strip参数在64位系统下占8个字节（） 3、 若没有6 7两行，程序也能正常运行（） 4、 16行gets输入可能会读入超过64个字符（） 选择题 5、输入数据 Are you ok，那么输出的结果为（） A．Are you ok B. Are You Ok C. are:you:ok D.ARE:YOU:OK 6、若输入5个连续空格，那么输出结果为（） A．无输出 B.： C.5: D.:::::

2、

1 #include <iostream>
2 using namespace std;
3 #define COUNT 6
4 int cocktail_sort(int* a,int size){
5	int times = 0;
6	for(int i = 0; i < size/2; ++i){
7		bool bchanged = false;
8		for(int j = 0; j< size-i; ++j){
9			if( j+1 < size && a[j] > a[j+1]){
10				bchanged = true;
11				swap(a[j],a[j+1]);
12			}
13		}
14		if( !bchanged )
15			break;
16		for(int k = size-i-1; k > 0; --k){
17			if( k >= 1 && a[k] < a[k-1] )
18				swap(a[k],a[k-1]);
19		}
20		times++;
21	}
22	return times;
23 }
24 int main(){
25	int a[COUNT];
26	for( int i = 0; i < COUNT; ++i)
27		cin >> a[i];
28	cout << cocktail_sort(a,COUNT) << endl;
29 }

判断题 1、 COUNT是一个变量（） 2、 如果将数组a放在全局，那么cocktail_sort可以不传参数（） 3、 若将第14 15行注释掉，程序效果相同（） 4、若输入数据全部相同，最后将输出1（） 选择题 5、若输入数据 10 1 2 3 4 5，那么输出的结果为（） A．1 B.2 C.3 D.4 6、若输入数据 10 5 3 2 4 1，那么输出结果为（） A．1 B.2 C.3 D.4

3、

1 #include<iostream>
2 using namespace std;
3 void foo(int a, int b, int c){
4	if(a > b) 
5		foo(c, a, b);
6	else
7		cout<<a<<','<<b<<','<<c<<endl;
8 }
9 int main(){
10	int a, b, c;
11	cin >> a >> b >> c;
12	foo(a, b, c);
13	return 0;
	14 }

判断题 1、第四行为递归的终止条件（） 2、foo函数没有返回值（） 选择题 3、若输入数据7 6 5，那么结果为（）。 A．7,6,5 B.5,7,6 C.5,6,7 D.7,5,6 4、若输入数据3 1 2，则结果为（）。 A．3,1,2 B.1,2,3 C.2,3,1 D.2,1,3 5、如果第4行修改为if (a>b && c > b),那么第三题的结果为（）。 A．7,6,5 B.5,7,6 C.5,6,7 D.7,5,6 6、(4分)在最坏的情况下，foo将会被调用几次（） A．1 B.2 C.3 D.4

三、完善程序（每小题3分，总共30分） 1、快速排序为常用的排序，请完善下面程序。

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
void quick_sort(int a[],int left,int right)
{
	if( left >= right )
		return ;
	int pivot = a[(left+right)>>1];
	int i = left;
	int j = right;
	while(   ①   )
	{
		while( a[j] > pivot )
			  ②  ；
		while( a[i] < pivot )
			++i;
		if( i <= j )
		{
			  ③  ;
			--j;++i;
		}
	}
	  ④  ;
	quick_sort(a,i,right);
}

int main()
{
	int n;
	scanf("%d",&n);
	int a[n];
	for( int i = 0; i < n; i++)
		scanf("%d",&a[i]) ;
	  ⑤  ;
	for(int i = 0; i < n; i++)
		printf("%d ",a[i]);
	printf("\n");
	return 0;
}

1）①处应填（） A．i <= j B. i < j C. i == j D. i >= j 2) ②处应填（） A．j++ B. j-- C. i++ D. i— 3) ③处应填（） A．swap(a[i-1],a[j]) B. swap(a[i],a[j]) C. swap(a[i],a[j-1]) D. swap(a[i+1],a[j+1]) 4) ④处应填（） A．quick_sort(a,right,j) B. quick_sort(a,left,i) C. quick_sort(a,left,i+1) D. quick_sort(a,left,i-1) 5) ⑤处应填（） A．quick_sort(a,0,n) B. quick_sort(a,1,n) C. quick_sort(a,0,n-1) D. quick_sort(a,0,n)

2、 （坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。

#include <iostream>
using namespace std;
const int SIZE =100;
int x[SIZE],y[SIZE],f[SIZE];
int n,i,j,max_f,ans;
int main()
{
	cin>>n;
	for(i=1;i<=n;i++) cin>>x[i]>>y[i];
	max_f=0;
	for(i=1;i<=n;i++)
	{
		f[i]=   ①   ;
		for(j=1;j<=n;j++)
		{
			if(x[j]<x[i] &&   ②    )
			      ③       ;
		}
		if(      ④       )
		{
			max_f=f[i];
			    ⑤    ;	
		}
	}
	for(i=1;i<=n;i++) cout<<f[i]<<endl;
	cout<<ans<<endl;
	return 0;	
}

1）①处应填（） A．1 B. n C. i+1 D. 0 2) ②处应填（） A．y[j]>y[i] B. y[j]<y[i] C. y[j]>=y[i] D. y[j]<=y[i] 3) ③处应填（） A．f[i]+1 B. f[j]+1 C. f[i]++ D.f[j]++ 4) ④处应填（） A．f[i]>max_f B. f[i]>=max_f C. f[j]>=max_f D. f[j]>max_f 5) ⑤处应填（） A．ans = i B. ans = i++ C. ans = j D. ans = f[i]