全国第二十一届青少年信息学奥林匹克竞赛分区联赛初赛试题 [2015年]

1. 1MB等于（ ）。

2. 在PC机中，PENTIUM、奔腾、酷睿、赛扬等是指（ ）。

3. 操作系统的作用是（ ）。

4. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以（ ）形式进行的。

5. 下列说法正确的是（ ）。

6. 二进制数00100100和00010100的和是（ ）。

7. 与二进制小数0.1相等的十六进制数是（ ）。

8. 所谓的“中断”是指（ ）。

9. 计算机病毒是（ ）。

10. FTP可以用于（ ）。

11. 下面哪种软件不属于即时通信软件（ ）。

12. 6个顶点的连通图的最小生成树，其边数为（ ）。

13. 链表不具备的特点是（ ）。

14. 线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。

15. 今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为（ ）

16. 前序遍历序列与中序遍历序列相同的二叉树为（ ）。

17. 如果根的高度为1，具有61个结点的完全二叉树的高度为（ ）。

18. 下列选项中不属于视频文件格式的是（ ）。

19. 设某算法的计算时间表示为递推关系式T(n) = T(n - 1) + n （n为正整数）及T(0) = 1，则该算法的时间复杂度为（ ）。

20. 在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选手自带的是（ ）。

1. 重新排列1234使得每一个数字都不在原来的位置上，一共有_________种排法。
答案：9

2. 一棵结点数为2015的二叉树最多有_________个叶子结点。
答案：1008

1.

#include <iostream> 
using namespace std; 
int main() { 
    int a, b, c; 
    a = 1; 
    b = 2; 
    c = 3;
	if (a > b) { 
        if (a > c) 
            cout << a << ' '; 
        else 
            cout << b << ' '; 
    } 
    cout << c << endl; 
    return 0; 
} 
输出：3

2.

#include <iostream> 
using namespace std; 
struct point { 
    int x; 
    int y; 
}; 
int main() { 
    struct EX { 
        int a; 
        int b; 
        point c; 
    } e; 
    e.a = 1; 
    e.b = 2; 
    e.c.x = e.a + e.b; 
    e.c.y = e.a * e.b; 
    cout << e.c.x << ',' << e.c.y << endl;
    return 0; 
} 
输出：3,2

3.

#include <iostream> 
#include <string> 
using namespace std; 
int main() { 
    string str; 
    int i; 
    int count; 
    count = 0; 
    getline(cin, str); 
    for (i = 0; i < str.length(); i++) { 
        if(str[i] >= 'a' && str[i] <= 'z') 
            count++; 
    } 
    cout << "It has " << count << " lowercases" << endl; 
    return 0; 
} 

输入：NOI2016 will be held in Mian Yang. 
 
输出：It has 18 lowercases

4.

#include <iostream> 
using namespace std; 
void fun(char *a, char *b) { 
    a = b; 
    (*a)++; 
} 
int main() { 
    char c1, c2, *p1, *p2; 
    c1 = 'A'; 
    c2 = 'a'; 
    p1 = &c1; 
    p2 = &c2; 
    fun(p1, p2); 
    cout << c1 << c2 << endl; 
    return 0; 
}
输出：Ab

1. （打印月历）输入月份m（1 ≤ m ≤ 12）按一定格式打印2015年第m月的月历。（第三、四空2.5分其余3分）
例如，2015年1月的月历打印效果如下（第一列为周日）
S M T W T F S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

#include <iostream> 
using namespace std;  
const int dayNum[]={-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 
int m, offset, i; 
int main() { 
    cin >> m; 
    cout << "S\tM\tT\tW\tT\tF\tS" << endl; // '\t'为TAB制表符 
        offset=4    ; 
    for (i = 1; i < m; i++) 
        offset =    (offset+dayNum[i])%7    ; 
    for (i = 0; i < offset; i++) 
	cout << '\t'; 
    for (i = 1; i <=     dayNum[m]    ; i++) { 
        cout <<     i    ; 
        if (i == dayNum[m]||   (offset+i)%7   == 0) 
            cout << endl; 
        else 
            cout << '\t'; 
    } 
    return 0; 
} 

2. （中位数）给定n（n为奇数且小于1000）个整数，整数的范围在0~m（0 < m < 2^31）之间，请使用二分法求这n个整数的中位数。所谓中位数，是指将这n个数排序之后，排在正中间的数。（第五空2分，其余3分）

#include <iostream>
using namespace std;  

const int MAXN = 1000;  

int n, i, lbound, rbound, mid, m, count; 
int x[MAXN];  

int main() { 
 cin >> n >> m; 
    for (i = 0; i < n; i++) 
        cin >> x[i]; 
    lbound = 0; 
    rbound = m; 
    while (    rbound>lbound    ) { 
        mid = (lbound + rbound) / 2; 
             count=0     ; 
        for (i = 0; i < n; i++) 
            if (     mid<x[i]     ) 
                     count++     ; 
        if (count > n / 2) 
            lbound = mid + 1; 
        else 
                 rbound=mid     ; 
    } 
    cout << rbound << endl; 
    return 0; 
}