第 23 题

# include <iostream>
using namespace std;
const int maxn=100005;
int n;
int a[maxn];
int b[maxn];
void solve(int l, int r)
{
	if (l==r) return ;
	int mid=(l+r)/2;
	solve(l, mid); solve(mid+1,r);
	int i=1,j=mid+1,k=1;
	while(i<=mid &&j<=r)
	{
		if (a[i]<=a[j]) b[k++]=a[i++];
		else b[k++]=a[j++]; 
	}
	while(i<=mid) b[k++]=a[i++];
	while(j<=r) b[k++]=a[j++];
	for (int i=l; i<=r; i++) a[i]=b[i]; 
}
int main(){
	cin>>n;
	for (int i=1; i<=n; i++) cin>>a[i];
	solve(1,n);
	int ans=0;
	for (int i=1; i<=n; i++) ans=ans+a[i]*i;
	cout<<ans<<endl;
	return 0;
}

第 23 题 即使a中有重复的数字，该程序仍能正常运行并输出正确答案。( )

第 24 题 当运行完25行后，a数组单调不增。( )

第 25 题 当输入如下时，n 1 2 3.....n 输出答案为( )。

第 26 题 该程序最坏情况下的时间复杂度为( )。

第 27 题 当输入如下时，5 50 60 30 40 50,输出为( )。

第 28 题 列各组输入获得的答案最大的是( )。

第 30 题

#include <stdio.h>
char c[200][200];
int s[200], m, n;
void numara() {
	int i,j, cod, nr;
	for(j=0; j<n; j++) {
		nr=0; cod=1;
		for(i=0; i<m; i++) {
			if(c[i][j]=='1') {
				if(!cod) {cod=1;s[nr]++;nr=0;}
			}
			else {
				if (cod) {nr=1;cod=0;} 
				else nr++;
			}
		}
		if(!cod) s[nr]++;
	}
}
int main() {
	int i,j;
	scanf("%d %d\n", &m, &n);
	for(i= 0; i<m; i++) gets(c[i]);
	numara();
	for(i=1; i<=m; i++)
		if(s[i]!= 0) printf("%d %d",i, s[i]);
	return 0;
}

输入保证是正整数m和n以及一个m*n的01矩阵，且相邻元素之间没有空格。如 下例: 2 4 0101 1000

第 30 题 若将第21行的“int i,j;”改为“int i;”,则程序会出现编译错误。()

第 31 题 程序最少输出0个数,最多输出2*m个数。()

第 32 题 s[i]表示矩阵中有s[i]个列有i个0。( )

第 33 题 若把第10行的“cod=1;”和第13行的“cod=0;”全部换成“cod^=1;”，则程序运行结果不变。( )

第 34 题 若m=100,n=100,则s[1]的最大值是( )。

第 35 题 若m=95,n=95,则s[5]的最大值是( )。

三、编程题（每题 25 分，共 50 分）

第 37 题 (YY的树)题目给出m颗非空有根(根节点编号为1)区分左右儿子的二叉树。 将某一棵给出二叉树的叶子节点换成任意一棵二叉树称为一次变换，即给出的二叉树变换到新二叉树。 同一棵二叉树进行多次变换是指在每次变换后得到的新二叉树上继续进行变换。 若任意一棵大小超过1的二叉树都可以由给出的某一棵给出的二叉树通过有限次变换得到，则输出“Almost Complete”，否则输出“No”。 题目第一行首先读入一个数m，表示二叉树的棵数。 接下来进行m次这样的操作。 读入一个数n，接下来n行每行2个数li和ri分别表示这棵二叉树第i个点的左右儿子编号，若没有左儿子，则li=0，若没有右儿子，则ri=0。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n, m, tot;
vector <int> t;
int lc[N], rc[N];
inline bool isleaf(int u) { ___(1)___;}
inline bool solve(vector <int> t) {
	if (t.empty()) return false;
	for (auto o : t) if (isleaf(o)) return true;
	vector<int> t1,t2,t3,t4;
	for (auto o : t) {
		if(!lc[o]) t2.push_back(rc[o]);
		if(!rc[o]) t1.push_back(lc[o]);
		if( ___(2)___ ) {
			if (isleaf(lc[o])) t3.push_back(rc[o]);
			if (isleaf(rc[o])) t4.push_back(lc[o]);
		}
	}
	___(3)___;
}
int main() {
	scanf("%d", &m);
	for (int i=1; i<=m; ++i) {
		int n;	scanf("%d" ,&n);___(4)___;
		for (int j=1; j<=n; ++j) {
			scanf("%d", &lc[tot+j]); if (lc[tot+j]) lc[tot+j] += tot;
			scanf("%d", &rc[tot+j]); if (rc[tot+j]) rc[tot+j] += tot;
		}
		___(5)___;
	}
	if (solve(t)) printf("Almost Complete\n");
	else printf("No\n");
	return 0;
}

第 37 题 ⑴处应填( )。

第 38 题 ⑵处应填( )。

第 39 题 ⑶处应填( )。

第 40 题 ⑷处应填( )。

第 41 题 ⑸处应填( )。

第 43 题 逻辑游戏 题目描述: 一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。 对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。 输入: 输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。 输入的第一行是n（0#include <stdio.h> #include <math.h> int orig, n, ns, a [102][102], bun; int d[]= {1,0,-1,0,0,1,___(1)___}; void plimba(int x, int y) { int i,xx, yy; a[x][y]=-a[x][y] ; if(abs(a[x-1][y]) !=orig&&( ___(2)___ !=a[x-1][y]||abs(a[x][y-1]) !=orig)) ns++; if(abs(a[x+1][y]) !=orig&& (a[x+1][y-1]!=a[x+1][y]||abs(a[x][y-1]) !=orig)) ns++; if(abs(a[x][y-1]) !=orig&&( ___(3)___ !=a[x][y-1]||abs(a[x-1][y]) !=orig)) ns++; if(abs(a[x][y+1]) !=orig&&(a[x-1][y+1] !=a[x][y+1]||abs(a[x-1][y]) !=orig)) ns++; for(i=0; i<4 ; i++) { xx=x+d[2*i]; yy=y+___(4)___; if(xx>=1&&xx<=n&&yy>=1&&yy<=n&& ___(5)___ )plimba(xx,yy); } } int main () { int i,j; bun=1; scanf("%d",&n); for (i=0; i<=n+1; i++) for (j=0; j<=n+1; j++) a[i][j]=0; a[0][0]=-1; a[n+1][0]=-1; a[0][n+1]=-1; a[n+1][n+1]=-1; for (i=1; i<=n; i++) for (j=1; j<=n; j++) scanf("%d",&a[i][j]); for (i=1; i<=n ; i++) for(j=1; j<=n; j++) { if(a[i][j]>-1) { ns=0; ___(6)___; plimba (i,j); if(ns%2==1) bun=0; } } if (bun)printf("YES\n");else printf("NO\n"); return 0; }

第 43 题 ⑴处应填( )。

第 44 题 ⑵处应填( )。

第 45 题 ⑶处应填( )。

第 46 题 ⑷处应填( )。

第 47 题 ⑸处应填( )。

第 48 题 ⑹处应填( )。