首页 › 题库 › 信息学奥赛 › 3.1 一维数组

信息学奥赛-入门级 题库

共 65 道题 ,第 3 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 3.1 一维数组 清除
41 判断题 偏易 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

在执行完 init()后,f 数组不是单调递增的,但 g 数组是单调递增的。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
42 判断题 偏易 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

如果a数组有重复的数字,则程序运行时会发生错误。()

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
43 判断题 偏易 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

如果b数组全为0,则输出为0。()

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
44 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

插入排序


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

int n, q, a[8005], b[8005], num, x, v, ans;

int main() {
    scanf("%d%d", &n, &q);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    
    // 计算每个数在数组中的排位
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (i == j || a[j] < a[i] || a[j] == a[i]) {
                b[i]++;
            } else {
                b[j]++;
            }
        }
    }
    
    for (int i = 0; i < q; i++) {
        scanf("%d", &num);
        
        if (num == 1) {
            scanf("%d%d", &x, &v);
            
            for (int i = 1; i <= n; i++) {
                if (i == x) {
                    continue;
                }
                
                // 根据条件更新排位
                if ((a[i] < a[x] || (a[i] == a[x] && i < x)) && 
                    (a[i] > v || (a[i] == v && i > x))) {
                    b[i]++;
                    b[x]--;
                } else if ((a[i] > a[x] || (a[i] == a[x] && i > x)) && 
                           (a[i] < v || (a[i] == v && i < x))) {
                    b[i]--;
                    b[x]++;
                }
            }
            
            a[x] = v;
        }
        
        if (num == 2) {
            scanf("%d", &x);
            printf("%d\n", b[x]);
        }
    }
    
    return 0;
}


题目详情
45 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

(寻找被移除的元素)问题:原有长度为n+1公差为1等升数列,将数列输到程序的数组时移除了一个元素,导致长度为n的开序数组可能不再连续,除非被移除的是第一个或最后一个元素。需要在数组不连续时,找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>

using namespace std;

int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + __(1)__ ) {
            __(2)__ ;
        } else {
            __(3)__ ;
        }
    }
    return __(4)__ ;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++)cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == __(5)__) {
        cout << "Sequence is consecutive" << endl;
    } else {
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
46 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

奖学金

【问题描述】

某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排在前面,这样,每个学生的排序是唯一确定的。

任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前5名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分)是:

7 279

5 279

这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和),但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:

5 279

7 279

则按输出错误处理,不能得分。

【输入】

输入文件scholar.in包含n+1行:

第1行为一个正整数n,表示该校参加评选的学生人数。

第2到n+1行,每行有3个用空格隔开的数字,每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n(恰好是输入数据的行号减1)。

 所给的数据都是正确的,不必检验。

【输出】

输出文件scholar.out共有5行,每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。

【输入输出样例1】

【输入输出样例2】

【限制】

    50%的数据满足:各学生的总成绩各不相同

    100%的数据满足:6<=n<=300

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

long long a[100100];

struct student{

int a,b,c;//语文,数学,英语;

int id;

int sum; 

};

bool cmp(student da,student db){

if(da.sum!=db.sum){

return da.sum>db.sum;//总分比较。 

}else if(da.a!=db.a){

return da.a>db.a;//语文成绩比较。 

}

return da.id<db.id;//编号比较。 

}

int main() {

int n;

cin>>n;

student stu[n];

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

cin>>stu[i].a>>stu[i].b>>stu[i].c;

stu[i].id=i+1;

stu[i].sum=stu[i].a+stu[i].b+stu[i].c;//总和。 

}

stable_sort(stu,stu+n,cmp);

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

cout<<stu[i].id<<" "<<stu[i].sum<<endl;

}

return 0; 

}

题目详情
47 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

明明的随机数

【问题描述】

明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

【输入文件】

输入文件random.in 有2行,第1行为1个正整数,表示所生成的随机数的个数:

N

第2行有N个用空格隔开的正整数,为所产生的随机数。

【输出文件】

输出文件random.out 也是2行,第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。

【输入样例】

  10

  20 40 32 67 40 20 89 300 400 15

【输出样例】

  8

  15 20 32 40 67 89 300 400

答案与解析
参考答案

#include<stdio.h>

  int main(){

      int N,a[1001]={0},t,i;

      int count=0; 

     scanf("%d",&N);

      for(i=0;i<N;i++){

         scanf("%d",&t);

          if(a[t]==0){

              a[t]=t;

             count++;

        }

     }

     printf("%d\n",count);

     for(i=0;i<1001;i++){

         if(a[i]!=0)

             printf("%d ",a[i]);

     }

     return 0;

 }

题目详情
48 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

输入 n 个 0 到 100 之间的整数,由小到大排序输出,每行输出 8 个

程序清单:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
49 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

在 A,B 两个城市之间设有 N 个路站(如下图中的 S1,且 N<100),城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20,且每条路段上的距离均为一个整数)。

A,B 的一条通路是指:从 A 出发,可经过任一路段到达 S1,再从 S1 出发经过任一路段,…最后到达 B。通路上路段距离之和称为通路距离(最大距离≤ 1000)。当所有的路段距离给出之后,求出所有不同距离的通路个数(相同距离仅记一次)。

例如:下图所示是当 N=1 时的情况:

从 A 到 B 的通路条数为 6,但因其中通路 5+5=4+6,所以满足条件的不同距离的通路条数为 5。

算法说明:本题采用穷举算法。

数据结构:N:记录 A,B 间路站的个数

数组 D[I,0]记录第 I-1 到第 I 路站间路段的个数D[I,1],D[I,2],…记录每个路段距离

数组 G 记录可取到的距离

程 序 清 单 :

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
50 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

问题描述:将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:

问题求解:求出一种分法,使P为最小(若有多种方案仅记一种〉

程序说明:

数组:a[1],a[2],...A[N]存放原数

s[1],s[2],...,s[K]存放每个部分的和

b[1],b[2],...,b[N]穷举用临时空间

d[1],d[2],...,d[N]存放最佳方案

程序:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
51 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

将个0和个1,排成一圈。从任一个位置开始,每次按逆时针的方向以长度为n+1的单位进行数二进制数。

要求给出一种排法,用上面的方法产生出来的个二进制数都不相同。

例如,当n=2时, 即个0 和个1 排成如下一圈:

比如,从A位置开始,逆时针方向取三个数000,然后再从B位置上开始取三个数001,接着从C开始取三个数010,...可以得到000,001,010,101,011,111,110,100共8个二进制数且都不相同。

程序说明 

          以n=4为例,即有16个0,16个1,

          数组a用以记录32个0,1的排法,

          数组b统计二进制数是否已出现过。

程序清单

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
52 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

[问题描述]

    下面程序的功能是从键盘读取A,B数组的元素,A,B数组均已从小到大排好序(无相同元素),现将A,B合并为数组C,同样要求数组C也是从小到大排好序(有相同元素时只保留一个)。

程序中N表示数组A,B的长度,i,j,k分别表示数组A,B,C的取数或存数的指针。

[程序清单]

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
53 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

 输入一长度不超过80个字符的字符串(称为源串),该字符串由小写英文字母、空格组成,并以'.'结束。单词是由连续字母组成,两个单词之间至少有一个空格。本程序的功能为:首先找出字符串中所有单词并保留一个空格作为单词分隔,存入数组ch中。然后用键盘输入一个待查找的单词,以字符'$'结束。采用顺序查找的方法在ch中进行查找,若找到,则输出该单词在ch中出现的序号(若有多个位置出现该单词,则只输出第一个序号位置)。若不存在,则输出'NOT FOUND'。

 程序如下:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
54 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

设数组A[10..100,20..100] 以行优先的方式顺序存储,每个元素占4个字节,且已知A[10,20]的地址为1000,则A[50,90]的地址是()

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
55 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

[问题描述]  读入n个不相同且不为0的数(1<=n<=100),不用排序,求出其中第r个大的数(1≤r≤n),即有r-1个数比它大,其余的数都比它小。

例如:输入3,14,22,15,17,6,其中第3个大的数为15。

[算法说明]  以数组a[1..100]记录读入的n个数,并以0结束(0本身不是n个数中的数)。然后从第一个数开始,将它与其余的数进行比较并记录出比它大的数的个数(存于变量y中),若y=r-1时,得到所求结果:否则对下一个数进行同样的处理。

[程序清单]

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
56 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

[问题描述]  一个正整数(非素数)可表示成它的因子(1与其本身除外)的乘积。

    例如:12有因子2,3,4,6,所以可表示为:

        12=223=43=26

    给出任一个正整数N,求出它所有的因子乘积的表达式(交换律得出的不同式子算同一种)。

    [算法说明]  读入一个整数N,首先求出它的所有的因子以及每个因子可能的次数。

    例如:整数48:

    因子:2  3  4  6  8  12  16  24

    次数:4  1  2  1  1  1   1   1

将上面的结果存入数组A:ARRAY[0..20,1..2]中。其中:A[¡,1]表示因子;A[¡,2]表示次数。

然后用简单回溯的方法求出所有可能的表示。

数组B[0..20]记录取数情况;c:array[0..20]工作单元。

[程序清单]

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
57 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

阅读下列程序段,写出程序运行后数组元素A1,A2,…,A11中的值。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
58 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

有N×N个数据组成如下方阵:

现将…存储在一维数组A[1],A[2],…A[(N*(N+1))/2] 中。

试问:任给i,j怎样求出K来,使得A[K]的值正好是请写出由i,j计算K值的表达式。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
59 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

设有N个不同整数的数列:例如N=4时,有4个不同整数的数列为17,4,16,5。数列中的第1个数17,比它后面的三个数都大,则称数17的逆数为3。数列中的第2个数4比它后面的数都小,则称数4的逆数为0。同时记数列中全部逆数的和称为数列的逆数。上例中,数列17,4,16,5的逆数:为3+0+1+0=4。


[程序要求]  当给出N个不同整数的数列后,求出此数列的逆数。   

[算法描述]  为求得上面问题的解,设置数组A:array[1..N] of Integer 和逆数计数器5,然后用一个二重循环求出数列的逆数。

[程    序]

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
60 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 3.1 一维数组

装球:设有n个盒子(n足够大,可装入任何数量的球),分别编号1,2,……。同时有k个小球(k>0),今将k 个小球装入到盒子中去。

装入规则如下:

(1)第一个盒子不能为空。

(2)装入必须严格按递增顺序进行。

     例如,当k=8,n=6时,装入方法有1,2,5或1,3,4

(3)在满足上面的两个条件下,要求有球的盒子尽可能多。

(4)装完后,相邻盒子中球个数差的绝对值之和最小(未装的盒子不计)。

如上例中:

  装入法1,2,5,则差的绝对值之和为2-1+5-2=4

  装入法1,3,4,则差的绝对值之和为3-1+4-3=3


[程序要求]  给出k(k表示小球的个数)之后,求出满足上述四个条件的装入方法。

[算法描述]  设计一个数组A用数组元素代表盒子,然后依次装入小球。

[程序清单]

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情