一、单选题（共20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项）

1.  微型计算机中，控制器的基本功能是（ ）。
2.  设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（ ）。
3.  在下列关于图灵奖的说法中，不正确的是（ ）。
4.  计算机在工作过程中，若突然停电，（ ）中的信息不会丢失。
5.  完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。
6.  在以下各项中，（ ）不是操作系统软件。
7.  设栈S的初始状态为空， 元素a，b，c，d，e，f依次入栈S， 出栈的序列为b，d，f，e，c，a， 则栈S的容量至少应该是（ ）。
8.  与十进制数28.5625相等的四进制数是（）。
9.  设字符串S=”Olympic”，S的非空子串的数目是（ ）。
10.  Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（）是典型的Web2.0应用。
11.  递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。
12.  (2008)10 + (5B)16的结果是（ ）。
13.  二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。
14.  将数组{8,23,4,16,77,-5,53,100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。
15.  对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，成功查找元素19的查找长度（比较次数）是（）。
16.  面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的是（）。
17.  在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（ ）。
18.  设T是一棵有n个顶点的树，下列说法不正确的是（ ）。
19.  下列不属于NOIP竞赛推荐使用的语言环境的是（）。
20.  在C++程序中，表达式200|10的值是（ ）

二、问题求解 （共2 题，每题 5 分，共计 10 分；每题全部答对得5 分，没有部分分）

1.  书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有种。 满足 A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有种摆法。
2.  有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为 。
城市1城市2城市3城市4城市5城市6
城市102311215
城市22025312
城市3320365
城市4153079
城市51236702
城市615125920

三、阅读程序写结果（共4 题，每题 8 分，共计 32 分）

1.  
#include <iostream>
using namespace std;
int main()
{
    int i, a, b, c, d, f[4];
    for(i = 0; i < 4; i++) cin >> f[i];
    a = f[0] + f[1] + f[2] + f[3];
    a = a / f[0];
    b = f[0] + f[2] + f[3];
    b = b / a;
    c = (b * f[1] + a) / f[2];
    d = f[(b / c ) % 4];
    if(f[(a + b + c + d) % 4] > f[2])
        cout << a + b<< endl;
    else 
        cout << c + d << endl;
    return 0;
}
输入：9 19 29 39
输出：
2.  
#include <iostream>
using namespace std;
void foo(int a, int b, int c)
{
    if(a > b) 
        foo(c, a, b);
    else
        cout<<a<<','<<b<<','<< c<<endl;
}

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    foo(a, b, c);
    return 0;
}
输入：3 1 2
输出：
3.  
#include < iostream>
using namespace std;
void func(int ary[], int n )
{
    int i=0, j, x;
    j=n-1;
    while(i<j)
    {
        while (i<j&&ary[i]>0) i++;
        while (i<j&&ary[j]<0) j--;
        if (i<j)
        {
            x=ary[i];
            ary[i++]=ary[j];
            ary[j--]=x;
        }
    }
}

int main()
{
    int a[20], i, m;
    m=10;
    for(i=0; i<m; i++)
    {
        cin>>a[i];
    }
    func(a, m);
    for (i=0; i<m; i++)
        cout<<a[i]<<" ";
    cout<< endl;
    return 0;
}
输入：5 4 -6 -11 6 -59 22 -6 1 10
输出：
4.  
#include<iostream>
#include<cstring>
using namespace std;
#define MAX 100
void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m)
{
    int i, root_m;
    if(spos_f > epos_f)
        return;
    for(i = spos_m; i <= epos_m; i++)
        if(first[spos_f] == mid[i])
        {
            root_m = i;
            break;
        }
    solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);
    solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);
    cout << first[spos_f];
}

int main()
{
    char first[MAX], mid[MAX];
    int len;
    cin >> len;
    cin >> first >> mid;
    solve(first, 0, len - 1, mid , 0, len - 1);	
    cout << endl;
    return 0;
}
输入：
7
ABDCEGF
BDAGECF
输出：

四、完善程序（共2 题，每题 14 分，共计 28 分）

1.  （字符串替换）
给定一个字符串S（S仅包含大小写字母），下面的程序将S中的每个字母用规定的字母替换，并输出S经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串S，第二个字符串S’由26个字母组成，它是a-z的任一排列，大小写不定，S’规定了每个字母对应的替换字母：S’中的第一个字母是字母A和a的替换字母，即S中的A用该字母的大写替换，S中的a用该字母的小写替换；S’中的第二个字母是字母B和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换；…… 以此类推。 
#include <iostream>
#include <string.h>
char change[26], str[5000];
using namespace std;
void CheckChangeRule()
{
    int i;
    for (i = 0;i < 26;i ++)
    {
        if ()
            change[i] -= 'A' - 'a';
    }
}
	
void ChangeString()
{
    int i;
    for (i = 0;i <strlen(str);i ++)
    {
        if()
            str[i] = change[str[i] - 'A'] -'a' + 'A';
        else
            ;
    }
}
	
int main()
{
    int i;
    cin >> str ;
    cin >> change;
    CheckChangeRule();
    ;
    cout << str << endl;
    return 0;
}
2.  （找第k大的数）
给定一个长度为1,000,000的无序正整数序列, 以及另一个数n (1<=n<=1000000), 然后以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）。 
#include <iostream>
using namespace std;
	
int a[1000001],n,ans = -1;
void swap(int &a,int &b)
{
    int c;
    c = a; a = b; b = c;
}
	
int FindKth(int left, int right, int n)
{
    int tmp,value,i,j;
    if (left == right) return left;
    tmp = rand()% (right - left) + left;
    swap(a[tmp],a[left]);
    value = ;
    i = left;
    j = right;
    while (i < j)
    {
        while (i < j &&  ) j--;
        if (i < j) {a[i] = a[j]; i++;} else break;
        while (i < j && ) i++;
        if (i < j) {a[j] = a[i]; j--;} else break;
    }
    ;
    if(i < n) return FindKth();
    if(i > n) return ;
    return i;
}
	
int main()
{
    int i;
    int m = 1000000;
    for (i = 1;i <= m;i ++)
        cin >> a[i];
    cin >> n;
    ans = FindKth(1,m,n);
    cout << a[ans];
    return 0;
}