一、单项选择题（共15题，每题2分，共计30分）

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

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

2. RAM中的信息是()。 {{ select(2) }}

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

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

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

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

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

5. 在计算机领域中,通常用英文单词"BYTE"来表示()。 {{ select(5) }}

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

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

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

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

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

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

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

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

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

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

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

11. 对一个满二叉树,m个树叶,l个分支结点,n个结点,则( )。 {{ select(11) }}

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

12. 以下不是操作系统名字的是()。 {{ select(12) }}

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

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

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

14. 已知元素(8,25,14,87,51,90,6,19,20),这些元素以怎样的顺序进入栈,才能使出栈的顺序满足:8在51前面;90在87的后面;20在14的后面;25在6的前面;19在90的后面?()。 {{ select(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(15) }}

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

二、阅读程序（共计40分；标注分值的按标注计，未标注判断题每题1.5分，选择题每题4分）

（一）素数判断

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

判断题 16. (1分)第19行输入97时,输出为"NO"(不含引号)。() {{ select(16) }}

• 正确
• 错误

17. (1分)第19行输入119时,输出为"YES"(不含引号)。() {{ select(17) }}

• 正确
• 错误

18. 若将第7行的"<="改成"<",程序输出的结果一定不会改变。() {{ select(18) }}

• 正确
• 错误

19. 当程序执行第14行时,i的值为sqrt(num)。() {{ select(19) }}

• 正确
• 错误

选择题 20. (3分)最坏情况下,此程序的时间复杂度是( )。 {{ select(20) }}

• O(num)
• O(num^2)
• O(sqrt(num))
• O(log num)

21. 若输入的num为20以内的正整数,则输出为"YES"的概率是()。 {{ select(21) }}

• 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. (1分)将第9行和第11行的括号去掉,程序输出结果一定不变。() {{ select(22) }}

• 正确
• 错误

23. (1分)将第12行的"mi>>=1"改为 "mi *=0.5",程序输出结果一定不变。() {{ select(23) }}

• 正确
• 错误

24. 若输入为"4 4",则输出为"78"。() {{ select(24) }}

• 正确
• 错误

25. 此程序的时间复杂度为O(log n)。() {{ select(25) }}

• 正确
• 错误

选择题 26. 若输入为"3 4",则输出为( )。 {{ select(26) }}

• 8
• 12
• 18
• 19

27. kasumi(2046,13)的返回值为()。 {{ select(27) }}

• 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分)程序结束时,对任意 1<=i<=n ,mark[i]=0。() {{ select(28) }}

• 正确
• 错误

29. (2分)若n<r,则程序无输出。() {{ select(29) }}

• 正确
• 错误

30. (2分)若输入为"4 3",则输出中数字1和2的个数不同。() {{ select(30) }}

• 正确
• 错误

31. (2分)此程序的时间复杂度为O(n)。() {{ select(31) }}

• 正确
• 错误

选择题 32. 若输入为"6 3",则函数print的执行次数为()。 {{ select(32) }}

• 60
• 120
• 6
• 720

33. 若输入为"7 4",则输出的最后一行为()。 {{ select(33) }}

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

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

（一）Kruskal最小生成树

克鲁斯卡尔求最小生成树思想:首先将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(34) }}

• a.v<b.v
• a.v>b.v
• a.v>=b.v
• a.y<=b.y

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

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

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

• algorithm
• point
• cmp
• sizeof(a)

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

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

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

• 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的初始化代码省略
    euler(1);
    return 0;
}

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

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

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

• 1
• 0
• u
• v

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

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

42. 若为七桥问题对应的图，以下边初始化正确的是()。 {{ select(42) }}

• G[0][1]=1; G[1][0]=1;
• G[1][0]=1; G[0][1]=1;
• G[3][1]=1; G[1][3]=1;
• G[0][3]=1; G[3][0]=1;

43. 若为七桥问题对应的图，以下边初始化正确的是()。 {{ select(43) }}

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