[数据结构与算法] NOIP-2016-J1-真题解析

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> NOIP-2016-J1-真题解析 -> 正文阅读

[数据结构与算法]NOIP-2016-J1-真题解析

一、选择题

1、D，基础题，考察常用应用软件常识，A,B,C均属于Microsoft Office办公软件里的产品，是微软公司的软件产品，Acrobat Reader是Adobe公司的产品
2、C，基础题，考察二进制，n位二进制能表示的数值范围是 $0-2^{n-1}$ ，总共 $2^n$ 个数， $2^8=256$ ，所以最少8位刚好能满足题目要求
3、D，基础题，考察计算机网络基础知识，A,B,C均属于无线通信技术范畴，以太网是一种计算机局域网技术，属于有线通信技术范畴
4、C，基础题，考察计算机常识，A,B是著名的CPU产商，IBM的产品非常广泛，从PC到大型机，软件，硬件都有，也生产CPU，特别是大型机的CPU，Microsoft则是典型的系统软件产商，代表产品是Window操作系统，Office办公软件等。
5、D，基础题，考察计算机硬件系统，A,B,C均是外存储设备，D鼠标是输入设备
6、C，数学题，屏幕上输出的字符串是ASDasdASDasd…，反复输出ASDasd这6个字符，第n个字符只需对6求余即可，81%6=3，所以是第3个字符D
7、B，基础题，考察二进制运算
8、B，基础题，考察进制转换，二进制小数0.1转八进制，乘以4即可，即0.4
9、C，基础题，考察计算机硬件系统，32位和64位指的是总线宽度，即寻址空间，32位机器理论上可以寻址4GB的内存空间，即最大支持4GB内存，64位则可以寻址256TB空间。
10、A，基础题，考察字符串基础知识，字符串是一种特殊的线性表，即字符数组，串的长度可以为0，即空串，空格字符组成的串不是空串，空格字符也是字符元素。
11、D，数据结构题，考察二叉树的存储结构，二叉树采用顺序存储结构，节点下标按照满二叉树的顺序编号，从根节点开始依次数过来，最后一个节点的下标最大，为15
12、B，编程题，考察for语句的应用，s初值为a，循环c次，每次给s累加1，最终s=a+c
13、D，编程题，考察while循环语句和continue关键字，注意区别continue和break的区别，前者是跳过本轮循环后续的语句，继续下一轮循环，后者是直接退出当前循环。
打表依次列出n和k的变化情况可得答案D

14、A，算法题，考察二分查找，查找时，判断当前元素若刚好是峰顶，则直接返回，对应第1空c，否则如果落在峰顶左侧，则表示峰顶在右侧，需要在右边区间继续查找峰顶，对应第2空a，否则就是落在峰顶右侧了，需要在左边边区间继续查找，对应第3空b
15、D，数据结构题，考察无向图的边和度的关系，图G有n个顶点，则所有顶点的度数和=边数的2倍， $2 n = 2 ? 16$ ，所以n=16
16、B，数学题，考察组合数学，球和盒子经典问题，球和盒子均相同，可以为空的情况，可以直接用公式计算， $P_1^7+P_2^7+P_3^7=1+3+P_1^4+P_2^4+P_3^4=1+3+1+2+1=8$
也可以直接枚举，因为题目给的数量很小，分别枚举空盘子的数量，
0个空盘，(1,1,5),(1,2,4),(1,3,3),(2,2,3)，1个空盘，(1,6),(2,5),(3,4)，2个空盘，(8)，
总共也是4+3+1=8
17、A
18、A，数据结构题，考察图的应用，根据题意，Lucia分享照片给其朋友，不想让Jacob看到，则其分享的朋友不能与Jacob是朋友，即不能与Jacob直接有连线，排除法可以快速排除B,C,D
19、C，数学题，考察统筹方法的应用，如上图流水线所示，最短需要50分钟完成3道菜

20、C，竞赛常识题，考察竞赛规则，U盘属于存储设备，是禁止带入考察，ABC可以带入考场

二、问题求解

1、组合数学题，采用排除法，任选两个方格的方法总数减去所有两个方格在同一行或同一列的的方法。
$c_{16}^2-c_4^2*4-c_4^2*4=72$
2、数据结构题，考察二叉树结点，当树是单枝树的时候，叶子结点最少为1，当树是一个完全二叉树的时候，高度最小。根的高度为1，高度为h的完全二叉树结点最多是 $2^h-1$ ，最少是 $2^{h-1}$ ，2016介于1024和2047之间，h为11

三、阅读程序

1、

#include <iostream>
using namespace std;
int main()
{
    int max, min, sum, count = 0;
    int tmp;
    cin >> tmp;
    if (tmp == 0)
        return 0;
    max = min = sum = tmp;
    count++;
    while (tmp != 0)
    {
        cin >> tmp;
        if (tmp != 0)
        {
            sum += tmp;
            count++;
            if (tmp > max)
                max = tmp;
            if (tmp < min)
                min = tmp;
        }
    }
    cout << max << "," << min << "," << sum / count << endl;
    return 0;
}

输入: 1 2 3 4 5 6 0 7
简单编程题，考察while循环语句，仔细打表，列出每次循环各个变量的值即可，最后tmp输入0的时候，程序结束，此时max=6，min=1，sum=21, count=6，输出结果是6, 1, 3
在这里插入图片描述

2、

#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;
}

简单编程题，考察while循环语句，i从100开始倒序遍历，每发现一个模8余1的数累加1，所以就是求1-100之间有多少个模8余1的整数，依次枚举可得1，9，17，25，33，41，49，57，75，73，81，89，97，总共13个，所以输出结果是13

3、

#include <iostream>
using namespace std;

int main(){
    int a[6] = {1, 2, 3, 4, 5, 6};
    int pi = 0;
    int pj = 5;
    int t, i;
    while (pi < pj)
    {
        t = a[pi];
        a[pi] = a[pj];
        a[pj] = t;
        pi++;
        pj--;
    }
    for (i = 0; i < 6; i++)
        cout << a[i] << ",";
    cout << endl;
    return 0;
}

简单编程题，考察while循环语句和数组遍历，pi，pj分别是数组的首尾下标，pi向后，pj向前，逐个逐个对调，直到pi和pj相遇，数组初值是{1,2,3,4,5,6}，首尾对调后，输出结果是{6,5,4,3,2,1}

4、

#include <iostream>
using namespace std;
int main()
{
    int i, length1, length2;
    string s1, s2;
    s1 = "I have a dream.";
    s2 = "I Have A Dream.";
    length1 = s1.size();
    length2 = s2.size();
    for (i = 0; i < length1; i++)
        if (s1[i] >= 'a' && s1[i] <= 'z')
            s1[i] -= 'a' - 'A';
    for (i = 0; i < length2; i++)
        if (s2[i] >= 'a' && s2[i] <= 'z')
            s2[i] -= 'a' - 'A';
    if (s1 == s2)
        cout << "=" << endl;
    else if (s1 > s2)
        cout << ">" << endl;
    else
        cout << "<" << endl;
    return 0;
}

简单编程题，考察数组和字符串处理，遍历两个字符串的字符，若是小写字母，则将其转换为小写字母，所以s1和s2经过转换之后，都变成小写字母格式的"i have a dream."，所以是相等的，结果输出=

四、完善程序

1、（读入整数）请完善下面的程序，使得程序能够读入两个 int 范围内的整数，并将这两个整数分别输出，每行一个。（第一、五空 2.5 分，其余 3 分）输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。

例如：
输入：
123 -789
输出： 123
-789

#include <iostream>
using namespace std;

int readint(){
    int num = 0;          // 存储读取到的整数
    int negative = 0;    // 负数标识
    char c;                  // 存储当前读取到的字符
    c = cin.get();
    while ((c < '0' || c > '9') && c != '-')
        c = ①;
    if (c == '-')
        negative = 1;
    else
        ②;
    c = cin.get();
    while (③){
        ④;
        c = cin.get();
    }
    if (negative == 1)
        ⑤;
    return num;
}
int main()
{
    int a, b;
    a = readint();
    b = readint();
    cout << a << endl
         << b << endl;
    return 0;
}

简单编程题，首先获取第一个输入的字符，然后判断其如果不是数字也不是负号就继续输入，直到输入数字或负号，①是cin。get()或getchar()，如果是输入负号，则将负数标记negative置为1，否则将字符转换为数字存入num中，②是num=c-‘0’，然后接着输入后面的数字，每输入一个合法的0-9的数字字符，就将其转换累加到num中，③是判断当前输入字符是否0-9，c>=‘0’&&c<=‘9’，④是累加，num=num*10+c-‘0’，输入完后，输出结果，若前面设置过负数标记，则转换为负数，⑤是num=-num

2、（郊游活动）有 n 名同学参加学校组织的郊游活动，已知学校给这 n 名同学的郊游总经费为 A 元，与此同时第 i 位同学自己携带了 Mi 元。为了方便郊游，活动地点提供 B(≥n)辆自行车供人租用，租用第 j 辆自行车的价格为 Cj 元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。（第四、五空 2.5 分，其余 3 分）本题采用二分法。对于区间[l, r]，我们取中间点 mid 并判断租用到自行车的人数能否达到 mid。判断的过程是利用贪心算法实现的。

#include <iostream>
using namespace std;
#define MAXN 1000000

int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;

bool check(int nn) {
    int count = 0, i, j;
    i = ①;
    j = 1;
    while (i <= n) {
        if(②)
            count += C[j] - M[i];
        i++;
        j++;
    }
    return ③;
}

void sort(int a[], int l, int r) {
    int i = l, j = r, x = a[(l + r) / 2], y;
    while (i <= j) {
        while (a[i] < x) i++;
        while (a[j] > x) j--;
        if (i <= j) {
            y = a[i]; a[i] = a[j]; a[j] = y;
            i++; j--;
        }
    }
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}

int main() {
    int i;
    cin >> n >> B >> A;
    for (i = 1; i <= n; i++)
        cin >> M[i];
    for (i = 1; i <= B; i++)
        cin >> C[i];
    sort(M, 1, n);
    sort(C, 1, B);
    l = 0;
    r = n;
    while (l <= r) {
        mid = (l + r) / 2;
        if(④){
            ans = mid;
            l = mid + 1;
        }else
            r = ⑤;
    }
    cout << ans << endl;
    return 0;
}

算法题，考察了二分法和贪心法的综合应用，跟题目提示，采用二分法进行查找，最多能租到自行车的同学数范围必然是在0-n之间，通过二分查找，每取一个人数时，用贪心算法求得此刻所需用到的最小经费，然后判断其是否不超过A，若是，则表示还可能有更多的人能借到自行车，继续往右边进行二分查找，否则往左边进行二分查找，直到找到最多的刚好满足消耗经费不超过A的租到自行车的人数。
从main函数开始，首先是两个排序，分别对学生的零钱，自行车的租金进行排序，这个是便于贪心法计算最小经费。然后就是标准的二分查找了，若当前查找值满足，则更新ans为mid，然后往右查找可能的更大的值，否则往左查找，⑤mid-1

void sort(int a[], int l, int r) {
    int i = l, j = r, x = a[(l + r) / 2], y;
    while (i <= j) {
        while (a[i] < x) i++;
        while (a[j] > x) j--;
        if (i <= j) {
            y = a[i]; a[i] = a[j]; a[j] = y;
            i++; j--;
        }
    }
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}

接着观察sort函数，这里是典型的快速排序，熟悉快速排序的应该能快速判断出来这里是升序排序，对应于主函数里的就是将n个同学的自带零钱进行升序排序，将B辆自行车按租金升序排序。
然后看check函数：

bool check(int nn) {
    int count = 0, i, j;
    i = ①;
    j = 1;
    while (i <= n) {
        if(②)
            count += C[j] - M[i];
        i++;
        j++;
    }
    return ③;
}

check函数就是根据贪心算法，计算nn个同学租到自行车时，所需的最小经费，如何使消耗经费更小，因为学生自带零钱只能自己用，按贪心思想，则应尽量先用零钱解决，需要尽可能先让零钱多的学生租到自行车，并且要尽量租租金便宜的自信车，对排好序的学生，显然只有排在最后的nn个同学租到自行车时，消耗经费最小，并且这nn个同学依次租的是前nn辆租金最便宜的自行车。

check函数这里，i和j分别是学生和自行车的下标，i从n-nn+1开始，j从1开始，①是n-nn+1，然后开始遍历，对每个学生i，如果其零钱不够支付对应的第j辆自信车租金，则需要使用经费，②是M[i]<C[j]，count是统计所消耗的经费，最后返回的是count是否不超过总经费A，③是count<=A，再结合main函数里的第4空，就是判断当前mid个学生是否能借到自行车，所以④是check(mid)