一、单项选择题(共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项)

1. 关于机器翻译，下列选项中正确的是( )。{{ select(1) }}

• 常见的翻译软件只有金山词霸金山快译两种
• 机器翻译的英文全称是 Machine Translation,简称 MT
• 百度和谷歌不具有在线翻译功能
• 机器翻译是利用计算机把一种自然语言转变成另一种机器语言

2. 以补码存储的 8 位有符号整数 10100011 的十进制表示为( ) 。{{ select(2) }}

• -93
• 163
• -35
• -92

3. 关于网络协议，下面说法中正确的是( )。{{ select(3) }}

• Internet 网络协议采用 TCP/IP 协议
• 我们所说的 TCP/IP 协议就是指传输控制协议
• www 浏览器使用的应用协议是 IPX/SPX
• 没有网络协议，网络也能实现可靠地传输数据

4. 以下程序 当执行完毕后。输出的值为( )。

int f(int n)
{
    if (n==2|n==1)
        return 1;//注意递归，验证，从最小的地方推
    else
        return f(n-1)+f(n-2);
}
cout << f(9);

{{ select(4) }}

• 13
• 21
• 34
• 55

5. 下列关键字序列中,哪一项是堆( )。{{ select(5) }}

• 16,72,31,23,94,53
• 94,23,31,72,16,53
• 16,53,23,94,31,72
• 16,23,53,31,94,72

6. 对 n 个不同的排序码进行冒泡排序，在下列哪种情祝下比较的次数最多( )。{{ select(6) }}

• 从小到大排列好的
• 从大到小排列好的
• 元素无序
• 元素基本有序

7. n 为一个两位数，它的数码之和为 a，当 n 分别各乘以 3、5、7、9 以后得到 4 个乘积，如果每一个积的数码之和都为 a，那么这样的两位数 n 有( ) 个 {{ select(7) }}

• 3
• 4
• 5
• 6

8. 二叉树第 10 层的结点数的最大数目为( )。{{ select(8) }}

• 10
• 100
• 512
• 1024

9. 100 以内最大的素数是( ) 。{{ select(9) }}

• 89
• 97
• 91
• 93

10. 15 张卡片，每张卡片上写有 3 个不同的汉字，任意 2 张上的汉字不完全相同;任意 6 张中，一定有 2 张，它们上面有共同的汉字。问:这 15 张卡片上最多有多少个不同的汉字?()。{{ select(10) }}

• 30
• 45
• 35
• 180

11. 仅由数字 1,2,3 组成的七位数中，相邻数字均不相同的七位数的个数是()。{{ select(11) }}

• 128
• 252
• 343
• 192

12. 有甲、乙、丙、丁四支球队参加的足球循环赛，每两队都要赛一场，胜得 3 分，负者将 0 分，如果踢平，两队各得 1 分。现在甲、乙、丙分别得了 7 分、1 分和 6 分，已知甲和乙踢平，那么丁得( )分。{{ select(12) }}

• 1
• 3
• 4
• 7

13. 若一组记录的排序码为(46,79,56,38,40,84)则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。{{ select(13) }}

• 38,40,46,56,79,84
• 40,38,46,79,56,84
• 40,38,46,56,79,84
• 40,38,46,84,56,79

14. 一棵 6 节点二叉树的中序遍历为 ABDGECF，先序遍历为 DBACEGF，后序遍历为( )。{{ select(14) }}

• DGBEFAC
• ABGEFCD
• GBEACFD
• ABCDEFG

15. 下面哪种图不一定是树( )。{{ select(15) }}

• 无回路的连通图
• 有 n 个结点，n-1 条边的连通图
• 每对结点间都有通路的图
• 连通但删去任意一条边则不连通的图

二、阅读程序(程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分)

#include <bits/stdc++.h>
using namespace std;
const int N=2e5;        // 03 行
int a[N],s[N];
int main()
{
    int n, m;
    cin>>n>>m;
    memset (s,0, sizeof (s)) ; // 09 行
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        s[i]=a[i]+s[i-1];
    }
    int l,r;
    while(cin>>l>>r)
    {
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}

判断题

16. 输出只能是正整数。( ) {{ select(16) }}

• 正确
• 错误

17. 将 03 行的 2e5 改为 2e10 输出结果不变。()。{{ select(17) }}

• 正确
• 错误

18. 将第 09 行删除，程序运行结果不会改变。( ) {{ select(18) }}

• 正确
• 错误

19. 只要输入 int 数据类型的数据,输出结果就是正确的。( ) {{ select(19) }}

• 正确
• 错误

选择题

20. 如输入的 5 3 1 2 3 4 5 2 4,则输出的结果为( )。 {{ select(20) }}

• 6
• 9
• 12
• 15

21. 本题涉及下列哪一项的数据范围偏小( )。 {{ select(21) }}

• a[N]
• s[N]
• m
• 以上都不对

#include <cstdio>
bool pd(long long n)
{
    if(n==1)
        return false ;
    for(long long i=2; i<n; i++)    // 06 行
        if(n%i==0) return false;
    return true ;
}
int main()
{
    long long n,i,c=0;
    int INF=1<<30;//1 左移 30 位，把 INF 初始化为较大的数    // 13 行
    scanf("%d", &n) ;
    for(i=2; i<=INF; i++)
    {
        if (pd(i))
        {
            c++;
            if(c==n)
            {
                printf ("%d",i) ;
                return 0;             // 23 行
            }
        }
    }
    printf("\n over") ;
    return 0;
}

判断题

22. 上述代码中,将第 13 行修改为 INF=1<<40,输出结果一定不变。() {{ select(22) }}

• 正确
• 错误

23. 上述代码中,将第 23 行修改为 break 或 continue 这两种情况后，相同的输入,在这两种情况,输出结果也一定相同。( ) {{ select(23) }}

• 正确
• 错误

24. 上述代码中，将第 23 行修改为 break 后，相同的输入,变量 c 的值和未修改前一定相同。( ) {{ select(24) }}

• 正确
• 错误

25. 上述代码中，将第 23 行修改为 break 后，相同的输入，输出结果也一定相同。( ) {{ select(25) }}

• 正确
• 错误

选择题

26. 当输入为:8,输出为( ) 。 {{ select(26) }}

• 17
• 19 over
• 19
• 23 over

27. 上述代码中,将第 06 行的 i < n 修改为( )后功能不变,效率更高。 {{ select(27) }}

• i*i <=n
• i < n/2
• i< n/3
• i< n/4

#include<bits/stdc++.h>
using namespace std;
int s[100001],a[100001],n,ans1, ans2;
int main()
{
    while (scanf ("%d", &a[++n])!=EOF) ;
    n--;
    for(int i=n; i>=1; i--) {
        s[i]=1;
        for (int j=i+1; j<=n; j++) {
            if(a[j]<=a[i]) {
                s[i] =max(s[i],s[j]+1);
            }
        }
        ans1 =max (ans1,s[i]);
    }
    for(int i=1; i<=n; i++) {
        s[i] =1;
        for(int j=1; j<=i; j++) {
            if(a[j]<a[i]) {
                s[i]=max(s[ i],s[j]+1);
            }
        }
        ans2 =max (ans2,s[i]) ;
    }
    printf ("%d %d", ans1,ans2) ;
    return 0;
}

判断题

28. 若输入的序列是一个单调递增序列,则 ans1 的值为 1。( ) {{ select(28) }}

• 正确
• 错误

29. 若输入的序列是一个单调递减序列，则 ans2 的值为 1。( ) {{ select(29) }}

• 正确
• 错误

30. 对输入序列数据处理中,ans1 的值越大,ans2 的值将会越小。( ) {{ select(30) }}

• 正确
• 错误

31. 输入的数值不能为负数。( ) {{ select(31) }}

• 正确
• 错误

选择题

32. 若输入 389 207 155 300 299 170 158 65，输出第一个数为( )。 {{ select(32) }}

• 3
• 4
• 5
• 6

33. 若输入 0 -1 0 -1，则输出( )。 {{ select(33) }}

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

三、完善程序(单选题，每题 3 分，共计 30 分)

1. (SPFA)给定一个有 n 个顶点(从 1 到 n 编号) ,m 条边的有向图(其中某些边权可能为负，但保证没有负环)。请你计算从 1 号点到其他点的最短路。试补全程序。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
const int inf=0x3f3f3f3f;
int h[N],e[N],ne[N],ret,w[N];
int dis[N];
bool st[N];
int n,m;
void add(int a,int b,int c) {
    e[ret]=b;
    w[ret]=c;
    ne[ret]=h[a];
    h[a]=ret++;
}
void spfa()
{
    memset (dis, inf,sizeof (dis));
    dis[1]=0;
    queue <int>q;
    q.push(1);
    st[1] = true;
    while(q.size()) {
        int t=q.front() ;
        q.pop();
        st[t]=false;
        for(int i=__(1)__;__(2)__; i=ne[i]) {
            int j=e[i];
            if (dis[j]>dis[t]+w[i])
            {
                __(3)__;
                if(!st[j]) {
                    __(4)__;
                    st[j]=true;
                }
            }
        }
    }
}
int main() {
    scanf ("%d%d", &n, &m) ;
    memset (h,-1, sizeof h) ;
    while (m--) {
        int a,b, c;
        scanf ("%d%d%d",&a, &b, &c) ;
        ___(5)___;
    }
    spfa() ;
    for (int i=2; i<=n; ++i)
        printf ("%d\n",dis[i]) ;
    return 0 ;
}

选择题

34. ⑴处应填( )。 {{ select(34) }}

• 1
• -1
• h[t]
• t

35. ⑵处应填( )。 {{ select(35) }}

• i=0
• i>0
• i!=-1
• i>-1

36. ⑶处应填( )。 {{ select(36) }}

• dis[j] =dis[t]+w[t]
• dis[j] =abs(dis[t]+w[i])
• dis[j]=dis[t]+w[i]
• dis[j]=dis[i]+w[i]

37. ⑷处应填( )。 {{ select(37) }}

• q.push(j)
• q.push(i)
• q.push(st[j])
• q.push(1)

38. ⑸处应填( )。 {{ select(38) }}

• spfa( )
• add( )
• add(a,b,c)
• spfa

2. (01 背包)在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 n、面额数组为 a[1..n]的货币系统记作(n,a)。在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i]满足 a[i]*t[i]的和为 x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9]中，金额 1,3 就无法被表示出来。两个货币系统(n,a)和(m,b)是等价的,当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表示出，要么不能被其中任何一个表示出。现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b),满足(m,b)与原来的货币系统(n,a)等价，且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务:找到最小的 m。

#include <bits/stdc++.h>
using namespace std;
int a[105],f[25005];
int main ()
{
    int T,n;
    scanf("%d", &T) ;
    while(__(1)__) {
        scanf ("%d", &n) ;
        for (int i=0; i<n; i++)
            scanf("%d",&a[i]);
        sort(a,a+n) ;
        
        int x=__(2)__;//x 代表 a[i]的最大值
        memset (f,0xcf, sizeof (f) ) ;
        f[0]=__(3)__;
        for (int i=0; i<n; i++) {
            for (int j=a[i]; j<=x; j++) {
                f[j]=max(f[j],__(4)__);
            }
        }
        int res=0;
        for(int i=0; i<n; i++) {
            if(__(5)__)
                res++;
        }
        printf ("%d\n",res);
    }
    return 0;
}

选择题

39. ⑴处应填( )。 {{ select(39) }}

• T
• T--
• 1
• 0

40. ⑵处应填( )。 {{ select(40) }}

• a[0]
• a[n-1]
• a[1]
• a[n]

41. ⑶处应填( )。 {{ select(41) }}

• -1
• 0
• 1
• n

42. ⑷处应填( )。 {{ select(42) }}

• f[j+a[i]]+1
• f[a[i]]+1
• f[j-a[i]]
• f[j-a[i]]+1

43. ⑸处应填( )。 {{ select(43) }}

• f[a[i]]==1
• f[a[i]]==0
• f[a[i]]>1
• f[a[i]]>2