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

1. 不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢排列的是（ ）{{ select(1-1) }}

• 快存/辅存/主存
• 外存/主存/辅存
• 快存/主存/辅存
• 主存/辅存/外存

2. RAM 中的信息是（ ）{{ select(1-2) }}

• 生产厂家预先写入的
• 计算机工作时随机写入的
• 防止计算机病毒侵入所使用的
• 专门用于计算机开机时自检用的

3. 在 24*24 点阵的字库中，汉字"一"与"编"的字模占用字节数分别是（ ）{{ select(1-3) }}

• 72、72
• 32、32
• 32、72
• 72、32

4. 计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。已知 64 位的奔腾处理器一次能处理 64 个信息，相当于（ ）字节。（ ）{{ select(1-4) }}

• 8 个
• 1 个
• 16 个
• 2 个

5. 在计算机领域中，通常用英文单词"BYTE"来表示（ ）{{ select(1-5) }}

• 字
• 字长
• 二进制位
• 字节

6. GB2312-80 规定了一级汉字 3755 个，二级汉字 3008 个，其中二级汉字字库中的汉字是以（ ）为序排列的。（ ）{{ select(1-6) }}

• 以笔画的多少
• 以部首
• 以 ASCII 码
• 以机内码

7. 设栈 S 的初始状态为空，现有 5 个元素组成的序列{1,2,3,4,5}，对该序列在 S 栈上依次进行如下操作（从序列中的 1 开始，出栈后不再进栈）:进栈、进栈、进栈、出栈、进栈、出栈、进栈。试问出栈的元素序列是（ ）{{ select(1-7) }}

• {5,4,3,2,1}
• {2,1}
• {2,3}
• {3,4}

8. 设循环队列中数组的下标范围是 n，其中头尾指针分别是 f 和 r，则其元素个数是（ ）{{ select(1-8) }}

• r-f
• r-f+1
• (r-f) MOD n+1
• (r-f+n) MOD n

9. 电线上停着两种鸟(A,B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类:一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知:电线上两个顶点上正好停着相同的小鸟，则两端为不同小鸟的线段数目一定是（ ）{{ select(1-9) }}

• 奇数
• 偶数
• 可奇可偶
• 数目固定

10. 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为（ ）{{ select(1-10) }}

• 插入排序
• 归并排序
• 选择排序
• 快速排序

11. 对一个满二叉树，m 个树叶，l 个分支结点，n 个结点，则（ ）{{ select(1-11) }}

• n=l+m
• l+m=2n
• m=l-1
• n=2l-1

12. 以下不是操作系统名字的是（ ）{{ select(1-12) }}

• WindowsXP
• Arch/Info
• Linux
• OS/2

13. 以下不是个人计算机的硬件组成部分的是（ ）{{ select(1-13) }}

• 主板
• 虚拟内存
• 总线
• 硬盘

14. 已知元素(8,25,14,87,51,90,6,19,20)，这些元素以怎样的顺序进入栈，才能使出栈的顺序满足:8 在 51 前面；90 在 87 的后面；20 在 14 的后面；25 在 6 的前面；19 在 90 的后面？（ ）{{ select(1-14) }}

• 20,6,8,51,90,25,14,19,87
• 51,6,19,20,14,8,87,90,25
• 19,20,90,8,6,25,51,14,87
• 6,25,51,8,20,19,90,87,14

15. 假设我们用 d=(a1,a2,…,a5)，表示无向图 G 的 5 个顶点的度数，下面给出的哪组 d 值合理？（ ）{{ select(1-15) }}

• {2,2,2,2,2}
• {1,2,2,1,1}
• {3,3,3,2,2}
• {5,4,3,2,1}

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确的填√，错误的填×；除特殊说明外，判断题每题 1.5 分，选择题每题 4 分，共计 40 分）

（一）

# include<iostream>
using namespace std;
# include<cmath>

bool IsPrime(int num)
{
    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num%i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int num = 0;
    cin >> num;
    if (IsPrime(num))
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    system("pause");
    return 0;
}

判断题

16. 第 19 行输入 97 时，输出为"NO"(不含引号)。（ ）{{ dropdown(2-1)[√, ×] }}（1 分）

17. 第 19 行输入 119 时，输出为"YES"(不含引号)。（ ）{{ dropdown(2-2)[√, ×] }}（1 分）

18. 若将第 7 行的 <= 改成 <，程序输出的结果一定不会改变。（ ）{{ dropdown(2-3)[√, ×] }}

19. 当程序执行第 14 行时，i 的值为 sqrt(num)。（ ）{{ dropdown(2-4)[√, ×] }}

选择题

20. 最坏情况下，此程序的时间复杂度是（ ）{{ select(2-5) }}（3 分）

• O(num)
• O(num²)
• O(√num)
• O(lognum)

21. 若输入的 num 为 20 以内的正整数，则输出为"YES"的概率是（ ）{{ select(2-6) }}

• 0.45
• 0.4
• 0.5
• 0.35

（二）

# include<bits/stdc++.h>
using namespace std;
const int mod=2048;
long long c,n;
long long kasumi(long long x,long long mi){
    long long res=1;
    while(mi){
        if(mi&1){
            res=(res * x)%mod;
        }
        x=(x * x)%mod;
        mi>>=1;
    }
    return res;
}
int main(){
    cin>>n>>c;
    if(n==3){
        printf("%lld",c * (c-1));
        return 0;
    }
    long long ans = ((kasumi (c - 1, n) + (c - 1)* kasumi (- 1, n))% mod + mod)%mod;
    cout<<ans;
    return 0;
}

判断题

22. 将第 9 行和第 11 行的括号去掉，程序输出结果一定不变。（ ）{{ dropdown(2-7)[√, ×] }}（1 分）

23. 将第 12 行的 mi>>=1 改为 mi * =0.5，程序输出结果一定不变。（ ）{{ dropdown(2-8)[√, ×] }}（1 分）

24. 若输入为"4 4"，则输出为"78"。（ ）{{ dropdown(2-9)[√, ×] }}

25. 此程序的时间复杂度为 O(logn)。（ ）{{ dropdown(2-10)[√, ×] }}

选择题

26. 若输入为"3 4"，则输出为（ ）{{ select(2-11) }}

• 8
• 12
• 18
• 19

27. kasumi(2046,13) 的返回值为（ ）{{ select(2-12) }}

• 0
• 2022
• 2
• 2024

（三）

# include<cstdio>
int n,r,num[10000];
bool mark[10000];
void print(　　)
{
    for(int i=1;i<=r;i++)
        printf("%d ",num[i]);
    printf("\n");
}
void search(int x)
{
    for(int i=1;i<=n;i++)
        if(! mark[i])
        {
            num[x]=i;
            mark[i]=true;
            if(x==r) print(　);
            search(x+1);
            mark[i]=false;
        }
}
int main(　)
{
    scanf("%d%d",&n,&r);
    search(1);
}

判断题

28. 程序结束时，对任意 1<=i<=n，mark[i]=0。（ ）{{ dropdown(2-13)[√, ×] }}（1 分）

29. 若 n<r，则程序无输出。（ ）{{ dropdown(2-14)[√, ×] }}（2 分）

30. 若输入为"4 3"，则输出中数字 1 和 2 的个数不同。（ ）{{ dropdown(2-15)[√, ×] }}（2 分）

31. 此程序的时间复杂度为 O(n)。（ ）{{ dropdown(2-16)[√, ×] }}（2 分）

选择题

32. 若输入为"6 3"，则函数 print 的执行次数为（ ）{{ select(2-17) }}

• 60
• 120
• 6
• 720

33. 若输入为"7 4"，则输出的最后一行为（ ）{{ select(2-18) }}

• 4 5 6 7
• 7 6 5 4
• 4 3 2 1
• 1 2 3 4

三、完善程序（单选题，每小题 3 分，共计 30 分）

（一）（克鲁斯卡尔求最小生成树）

克鲁斯卡尔求最小生成树思想:首先将 n 个点看作 n 个独立的集合，将所有边快排（从小到大）。然后，按排好的顺序枚举每一条边，判断这条边连接的两个点是否属于一个集合。若是，则将这条边加入最小生成树，并将两个点所在的集合合并为一个集合。若否，则跳过。直到找到 n-1 条边为止。

# include<iostream>
# include<algorithm>
using namespace std;
struct point{
    int x;
    int y;
    int v;
};
point a[10000];

int cmp(const point &a,const point &b){
    if( ① ) return 1;
    else return 0;
}

int fat[101];
int father(int x){
    if(fat[x]！=x) return fat[x]= ② ；
    else return fat[x];
}

void unionn(int x,int y){
    int fa=father(x);
    int fb=father(y);
    if(fa！=fb) fat[fa]=fb;
}

int main(){
    int i,j,n,m,k=0,ans=0,cnt=0;
    cin>>n;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        cin>>m;
        if(m！=0){
            k++;
            a[k].x=i;
            a[k].y=j;
            a[k].v=m;
        }
    }
    sort(a+1,a+1+k, ③ )；

    for(i=1;i<=n;i++){
        fat[i]=i;
    }

    for(i=1;i<=k;i++){
        if(father(a[i].x)！= ④ ){
            ans+=a[i].v;
            unionn(a[i].x,a[i].y);
            cnt++;
        }
        if( ⑤ ) break;
    }

    cout<<ans;
    return 0;

}

34. ① 处应填（ ）{{ select(3-1) }}

• a.v＜b.v
• a.v＞b.v
• a.v＞= b.v
• a.v＜= b.v

35. ② 处应填（ ）{{ select(3-2) }}

• father(x)
• father(fat[x])
• fat(father[x])
• x

36. ③ 处应填（ ）{{ select(3-3) }}

• algorithm
• point
• cmp
• sizeof(a)

37. ④ 处应填（ ）{{ select(3-4) }}

• a[i].y
• father(a[i].y)
• fat[a[i].y]
• a[i].x

38. ⑤ 处应填（ ）{{ select(3-5) }}

• cnt＞0
• i == 1
• ans == n-1
• cnt == n-1

（二）（欧拉回路）

欧拉回路问题由七桥问题而来，其基本问题是是否能一次性不重复地走遍这七座桥，转换为数学问题中的图论就是指的是从图中的一个顶点出发，是否能够一次性不回头地走遍所有的边，算法代码如下

# include <iostream>
# include <ctime>
using namespace std;

int G[5][5];
int visited[5][5];
int n = 5;
void euler(int u) {
    for (int v = 0; v < n; v++) {
        if (G[u][v] &&. ① ) {
            cout << u << "->" << v << endl;
            visited[u][v] = visited[v][u] = ② ；
                            ③
        }
    }
}

int main() {
    G[1][2] = G[2][1] = G[1][3] = ④ = 1;
    G[2][4] = G[4][2] = G[3][4] = ⑤ = 1;
    euler(1);
    return 0;
}

39. ① 处应填（ ）{{ select(3-6) }}

• G[v][u]
• ! visited[u][v]
• visited[u][v]
• visited[v][u]

40. ② 处应填（ ）{{ select(3-7) }}

• 1
• 0
• u
• v

41. ③ 处应填（ ）{{ select(3-8) }}

• euler(v);
• euler(u);
• G[u][v] = 0;
• G[v][u] = 0;

42. ④ 处应填（ ）{{ select(3-9) }}

• G[0][1]
• G[1][0]
• G[3][1]
• G[0][3]

43. ⑤ 处应填（ ）{{ select(3-10) }}

• G[0][2]
• G[2][0]
• G[2][1]
• G[4][3]