#CS410. 阅读程序-数论

阅读程序-数论

阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第10节：数论

第1题【NOIP】2012

#include <iostream>
using namespace std;
int n,i,ans;
int main(){
    cin>>n;
    ans=0;
7   for(i=1;i<=n;i++)
        if(n%i==0) ans++;
    cout<<ans<<endl;
    return 0;    
}

●判断题

(1)该程序可能输出负数。

{{ select(1-1) }}

  • 正确
  • 错误

(2)可以将第7行的i初始值赋为0。

{{ select(1-2) }}

  • 正确
  • 错误

(3)输入18.输出结果为6。

{{ select(1-3) }}

  • 正确
  • 错误

(4)该程序可以正常运行。

{{ select(1-4) }}

  • 正确
  • 错误

●选择题

(5)如果将第8行的ans++改成ans--,那么输人18,输出结果为()

{{ select(1-5) }}

  • 6
  • -6
  • man
  • ans

(6)该算法的时间复杂度为( )。

{{ select(1-6) }}

  • O(n)
  • O(1)
  • O(n2n^2)
  • O(nlogn)

第2题【NOIP】2013

#include <iostream>
using namespace std;
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<<num<<endl;
	return 0;
}

●判断题

(1)u可以为0

{{ select(2-1) }}

  • 正确
  • 错误

(2)b-a一定不小于num。

{{ select(2-2) }}

  • 正确
  • 错误

(3)输入1 9 2,输出4。

{{ select(2-3) }}

  • 正确
  • 错误

(4)该程序时间复杂度与u有关。

{{ select(2-4) }}

  • 正确
  • 错误

●选择题

(10)输出结果为10,输入数据可能为

{{ select(2-5) }}

  • 10 27 2
  • 20 30 10
  • 5 99 3
  • 41 83 4

(6)输人151 981 7,输出结果为()。

{{ select(2-6) }}

  • 117
  • 118
  • 120
  • 119

第3题【NOIP】2016

#include <iostream>
using namespace std;
int main(){
    int i = 100, x = 0, y = 0;
    while (i > 0){
        i--;
        x = i % 8;
        if (x == 1)
            y++;
    }
    cout << y << endl;
    return 0;
}

●判断题

(1)程序输出12

{{ select(3-1) }}

  • 正确
  • 错误

(2)若将第6行替换为“i++”,删程序无法在1s之内结束。

{{ select(3-2) }}

  • 正确
  • 错误

(3)若将第4行的“i=100”替换为“i=10”,则输出1.2

{{ select(3-3) }}

  • 正确
  • 错误

(4)若将第6行的“i--”后加上一个“i++,则程序会死循环。

{{ select(3-4) }}

  • 正确
  • 错误

●选择题

(5)若将第8行去掉，则程序输出

{{ select(3-5) }}

  • 98
  • 99
  • 100
  • 101

(6)若将第9行去掉“,”替换成“;”,则程序输出()

{{ select(3-6) }}

  • 0
  • 1
  • 2
  • 3

第4题【NOIP】2009

#include <iostream>
using namespace std;
int a,b;
int work(int a,int b){
	if (a%b)return work(b,a%b);
	return b;
}

int main(){
	cin >> a >> b;
	cout << work(a,b) << endl;
	return 0;
}

●判断题

(1)在第2行下面添加#define int long long程序可以正常运行。

{{ select(4-1) }}

  • 正确
  • 错误

(2)将第3行的int改成double结果不会改变。

{{ select(4-2) }}

  • 正确
  • 错误

(3)不能输入0 0。

{{ select(4-3) }}

  • 正确
  • 错误

(4)输人20 12结果输出4。

{{ select(4-4) }}

  • 正确
  • 错误

●选择题

(5)输入2012 13,输出()

{{ select(4-5) }}

  • 2012
  • 2013
  • 13
  • 1

(6)该算法的时间复杂度级别为

{{ select(4-6) }}

  • 线性时间
  • 对数时间
  • 平方时间
  • 常数时间

第5题【NOIP】2012

#include <iostream>
using namespace std;
int n, i, ans;
int gcd(int a, int b)
{
    if (a % b == 0) return b;
    else
        return gcd(b, a%b);
}
int main()
{
12  cin>>n;
    ans = 0;
    for (i = 1; i <= n; i++)
        if (gcd(n,i) == i)
            ans++;
    cout<<ans<<endl;
}

●判断题

（1)将n定义为double类型，程序的输出结果不变。

{{ select(5-1) }}

  • 正确
  • 错误

(2)输入一个正整数，输出结果不可能不大于1

{{ select(5-2) }}

  • 正确
  • 错误

(3)输人100000000000,输出结果为144。

{{ select(5-3) }}

  • 正确
  • 错误

(4)第12行可改为scanf(“%d”,&n);

{{ select(5-4) }}

  • 正确
  • 错误

●选择题

（5）输人120.输出为()

{{ select(5-5) }}

  • 15
  • 16
  • 18
  • 14

(6)该算法时间复杂度为()

{{ select(5-6) }}

  • O(n）
  • O(nlogn）
  • O(n)(\sqrt{n})
  • O(n2n^2)

第6题【NOIP】2014

#include <iostream>
using namespace std;
int main(){
04  int a, b, i, tot, c1, c2;
    scanf( "%d%d", &a, &b );
06  tot = 0;
    for ( i = a; i <= b; i++ ){
08      c1    = i / 10;
        c2    = i % 10;
        if ( (c1 + c2) % 3 == 0 )tot++;
    }
    printf( "%d", tot );
    return(0);
}

●判断题

(1)将第6行去掉会导致运行错误。

{{ select(6-1) }}

  • 正确
  • 错误

(2)将第4行去掉会导致编译错误

{{ select(6-2) }}

  • 正确
  • 错误

(3)若a,b都是99以内的整数，将第8行替换为“c1=i/10”没有影响。

{{ select(6-3) }}

  • 正确
  • 错误

4)若a,b都是99以内的整数，则答案为区间[a,b]中3的倍数的数量。

{{ select(6-4) }}

  • 正确
  • 错误

●选择题

(5)输入1100,则输出()

{{ select(6-5) }}

  • 31
  • 32
  • 33
  • 24

(6)输人110000,则输出()

{{ select(6-6) }}

  • 3333
  • 3400
  • 258
  • 1950

第7题【NOIP】2017

#include<iostream>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	int x = 1;
	int y = 1;
	int dx = 1;
	int dy = 1;
	int cnt = 0;
	while (cnt != 2) {
		cnt = 0;
		x = x + dx;
		y = y + dy;
		if (x == 1 || x == n) {
16			++cnt;
17			dx = -dx;
		}
		if (y == 1 || y == m) {
20			++cnt;
21			dy = -dy;
		}
	}
	cout << x << " " << y << endl;
	return 0;
}

●判断题

①)若将16、20行去掉，则程序会出现死循环

{{ select(7-1) }}

  • 正确
  • 错误

2)若将第一行的iostream改为cstdio,则程序会出现编译错误

{{ select(7-2) }}

  • 正确
  • 错误

(3)若将17、21行去掉，则程序会出现死循环

{{ select(7-3) }}

  • 正确
  • 错误

(4)记L=min(n,m),则时间复杂度为O(L2L^2)

{{ select(7-4) }}

  • 正确
  • 错误

●选择题

(5)输人2 3 1 1,则输出()

{{ select(7-5) }}

  • 1 1
  • 2 2
  • 1 3
  • 3 1

(6)输入2 2 1 1,则输出()

{{ select(7-6) }}

  • 1 I
  • 1 2
  • 2 1
  • 2 2

第8题【NOIP】2014

#include <iostream>
using namespace std;
const int SIZE = 100;
int main()
{
    int    p[SIZE];
    int    n, tot, i, cn;
    tot = 0;
    cin >> n;
    for ( i = 1; i <= n; i++ )
        p[i] = 1;
    for ( i = 2; i <= n; i++ )
    {
        if ( p[i] == 1 )
            tot++;
16      cn = i * 2;
        while ( cn <= n )
        {
            p[cn] = 0;
            cn += i;
        }
    }
    cout << tot << endl;
    return(0);
}

●判断题

(1)n的值为100时程序不会运行错误

{{ select(8-1) }}

  • 正确
  • 错误

(2)被程序的时间复杂度为O(n)

{{ select(8-2) }}

  • 正确
  • 错误

(3)将第16行的cn=i*2改为cn=i,程序输出结果不变

{{ select(8-3) }}

  • 正确
  • 错误

(4)输入30，输出结果为10

{{ select(8-4) }}

  • 正确
  • 错误

●选择题

(5)本程序的功能为

{{ select(8-5) }}

  • 求n以内的质数
  • 求n以内与n互质的数
  • 求n的约数
  • 求n以内与n不互质的数

(6)输人100,输出结果为()

{{ select(8-6) }}

  • 24
  • 22
  • 25
  • 23

第9题【NOIP】2012

#include <iostream>
using namespace std;
const int SIZE = 20;
int data[SIZE];
int n, i, h, ans;
void merge()
{
    data[h-1] = data[h-1] + data[h];
    h--;
    ans++;
}
int main()
{
    cin>>n;
    h = 1;
    data[h] = 1;
17  ans = 0;
    for (i = 2; i <= n; i++)
    {
        h++;
        data[h] = 1;
22      while (h > 1 && data[h] == data[h-1])
            merge();
    }
    cout<<ans<<endl;
}

●判断题

(1)去掉第17行，程序输出结果不变

{{ select(9-1) }}

  • 正确
  • 错误

(2)输入5，输出结果为3。

{{ select(9-2) }}

  • 正确
  • 错误

(3)将第22行的“==“改为“>=”,程序输出结果会改变。

{{ select(9-3) }}

  • 正确
  • 错误

(4)输入2147483647,程序一定正常运行。

{{ select(9-4) }}

  • 正确
  • 错误

●选择题

(5)输人2012,输出结果为

{{ select(9-5) }}

  • 2004
  • 2015
  • 2018
  • 2006

(6)ans的上界为

{{ select(9-6) }}

  • n
  • n\sqrt{n}
  • logn
  • nn\sqrt{n}

第10题【NOIP】2011

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v){
    int ans,i;
    ans=0;
    for(i=1;i<=n;i++)
12     if( a[u][i]!=a[v][i])
           ans++;
    return ans;
}
int main(){
    int sum,i,j;
    cin>>n;
    memset(a,0,sizeof(a));
    m=1;
21  while(1)
    {
        i=1;
        while( (i<=n) && (a[m][i]==1) )
            i++;
        if(i>n)
           break;
        m++;
        a[m][i]=1;
        for(j=i+1;j<=n;j++)
           a[m][j]=a[m-1][j];
    }
    sum=0;
    for(i=1;i<=m;i++)
       for(j=1;j<=m;j++)
          sum+=h(i,j);
    cout<<sum<<endl;
    return 0;
}

●判断题

(1)第21行至多执行n次。

{{ select(10-1) }}

  • 正确
  • 错误

(2)将第12行的!=改成==,结果不影响。

{{ select(10-2) }}

  • 正确
  • 错误

(3)输入的n为11,不会数组越界。

{{ select(10-3) }}

  • 正确
  • 错误

(4)该程序可以正常运行。

{{ select(10-4) }}

  • 正确
  • 错误

●选择题

(5)输入7,输出结果为()。

{{ select(10-5) }}

  • 7
  • 6
  • 57344
  • 114514

(6)该算法的时间复杂度为()。

{{ select(10-6) }}

  • O(1)
  • O(n)
  • O(n2n^2)
  • O(22n2^{2n})

第11题【NOIP】2013

#include <iostream>
using namespace std;
int main() {
	int a, b, u, i, num;
	cin>>a>>b>>u;
06	num = 0;
	for (i = a; i <= b; i++)
08		if ((i % u) == 0)
			num++;
	cout<<num<<endl;
	return 0;
}

●判断题

(1)u*v可以为0。

{{ select(11-1) }}

  • 正确
  • 错误

(2)去掉第06行，程序输出结果会发生改变。

{{ select(11-2) }}

  • 正确
  • 错误

(3)将第08行的“||”改为“&.&”,程序输出结果不会发生改变。

{{ select(11-3) }}

  • 正确
  • 错误

(4)输入1 9 3 4,输出结果为4。

{{ select(11-4) }}

  • 正确
  • 错误

●选择题

D.16

(5)输入51 82 3 6,输出结果为()。

{{ select(11-5) }}

  • 15
  • 11
  • 5
  • 16

(6)输入97 207 4 6,输出结果为()。

{{ select(11-6) }}

  • 125
  • 50
  • 36
  • 75

第12题【NOIP】2018

#include <iostream>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];
bool isSmall() {
    for (int i = 1; i <= n; ++i)
        if (a[i] != b[i]) return a[i] < b[i];
    return false;
}
bool getPermutation(int pos) {
    if (pos > n) {
        return isSmall();
    }
    for (int i = 1; i <= n; ++i) {
        if (!isUse[i]) {
            b[pos] = i; isUse[i] = true;
            if (getPermutation(pos + 1)) {
                return true;
            }
            isUse[i] = false;
        }
    }
    return false;
}
void getNext() {
    for (int i = 1; i <= n; ++i) {
        isUse[i] = false;
    }
    getPermutation(1);
32  for (int i = 1; i <= n; ++i) {
33       a[i] = b[i];
34  }
}
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= t; ++i) {
        getNext();
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d", a[i]);
46      if (i == n) putchar('\n'); else putchar(' ');
    }
    return 0;
}

●判断题

1)若t=0,则输入的排列与输出的排列相同。

{{ select(12-1) }}

  • 正确
  • 错误

(2)此程序的功能是求出给定的排列的上t个排列。

{{ select(12-2) }}

  • 正确
  • 错误

(3)若将46行去掉，则输出效果不变。

{{ select(12-3) }}

  • 正确
  • 错误

(4)将32～34行去掉，则输出效果不变。

{{ select(12-4) }}

  • 正确
  • 错误

●选择题

(5)该程序的时间复杂度为()。

{{ select(12-5) }}

  • O(nlogt)
  • O(nt)
  • O(nt2nt^2)
  • O(n2tn^{2t}

(6)若输入3 1 1 2 3,则输出()。

{{ select(12-6) }}

  • 1 2 3
  • 1 3 2
  • 2 1 3
  • 3 2 1

第13题【NOIP】2009

#include <iostream>
using namespace std;
const int maxn=50;
const int y=2009;
int main()
{
    int n,c[maxn][maxn],i,j,s=0;
    cin >> n;
    c[0][0]=1;
    for(i=1;i<=n;i++)
    {
        c[i][0]=1;
        for(j=1;j<i;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
        c[i][i]=1;
    }
    for(i=0;i<=n;i++)
        s=(s+c[n][i])%y;
    cout << s << endl;
    return 0;
}

●判断题

(1)该程序的第03行需要加分号才能正常运行。

{{ select(13-1) }}

  • 正确
  • 错误

(2)该程序可能输出2009。

{{ select(13-2) }}

  • 正确
  • 错误

(3)第05行的s可以不用赋初值。

{{ select(13-3) }}

  • 正确
  • 错误

(4)输入17,输出486。

{{ select(13-4) }}

  • 正确
  • 错误

●选择题

(5)该程序的实质是()。

{{ select(13-5) }}

  • 快速排序
  • 区间最大和
  • 区间前缀和
  • 杨辉三角

(6)该算法的时间复杂度级别为()。

{{ select(13-6) }}

  • 线性时间
  • 对数时间
  • 平方时间
  • 常数时间

第14题【NOIP】2013

#include <iostream>
using namespace std;
int main() {
04	const int SIZE = 100;
	int n, f, i, left, right, middle, a[SIZE];
	cin>>n>>f;
07	for (i = 1; i <= n; i++)
08		cin>>a[i];
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=i; j++)
11			if(a[i]>=a[j]) {
				t=a[i];
				a[j]=a[i];
				a[i]=t;
			}
	}
	left = 1;
	right = n;
	do {
		middle = (left + right) / 2;
		if (f <= a[middle])
			right = middle;
		else
			left = middle + 1;
	} while (left < right);
	cout<<left<<endl;
	return 0;
}

●判断题

(1)将第04行的程序移动到02、03行的中间，程序能够正常运行。

{{ select(14-1) }}

  • 正确
  • 错误

(2)将第11行的“=”删除，运行结果会改变。

{{ select(14-2) }}

  • 正确
  • 错误

(3)将第07行的“i=1;i<=n;”改为“i=0;i<n;”运行结果不会改变。

{{ select(14-3) }}

  • 正确
  • 错误

(4)若第08行输入n个相同的数字，程序最后输出的left值为1。

{{ select(14-4) }}

  • 正确
  • 错误

（5）当n=5,f=7,a={8,4,7,5,6}时，则结果为（）。

{{ select(14-5) }}

  • 3
  • 4
  • 5
  • 7

(6)输人仍是第(5),将第11行的“>="改为"<=",则结果为（）

{{ select(14-6) }}

  • 3
  • 4
  • 5
  • 7

第15题【NOIP】2009

#include <iostream>
using namespace std;
int main()
{
    int n,m,i,j,p,k;
    int a[100],b[100];
    cin >> n >> m;
    a[0]=n;i=0;p=0;k=0;
    do{
        for (j=0;j<i;j++)
            if (a[i]==a[j])
            {
                p=1;k=j;break;
            }
        if (p)break;
        b[i]=a[i]/m;
        a[i+1]=a[i]%m*10;
        i++;
    }while (a[i]!=0);
    cout << b[0] << ".";
21  for (j=1; j<k; j++)cout << b[j];
22  if (p)cout << "(";
23  for (j=k;j<i;j++)cout << b[j];
24  if (p)cout << ")";
25  cout << endl;
26  return 0;
}

●判断题

(1)输人的m可以为任意自然数

{{ select(15-1) }}

  • 正确
  • 错误

(2)输入-1 2,会输出-0.5

{{ select(15-2) }}

  • 正确
  • 错误

(3)输人1 2时，程序会输出0.(5)

{{ select(15-3) }}

  • 正确
  • 错误

(4)输入0 1时，程序会输出0。

{{ select(15-4) }}

  • 正确
  • 错误

●选择题

(5)输入5 13,输出为 （ )。

{{ select(15-5) }}

  • 0.(384615)
  • 0
  • 18
  • 8

(8)删去下列哪一行后，用(5)中的输人运行代码后输出结果发生改变?()

{{ select(15-6) }}

  • 25
  • 26
  • 21
  • 24
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. 粤ICP备2022142345号-1
  4. Worker 0, 21ms
  5. Powered by Hydro v4.14.1 Community