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

1. 文件型病毒传染的主要对象是（ ）{{ select(1-1) }}

• 文本文件
• 系统文件
• 可执行文件
• .EXE 和 .COM 文件

2. 24 针打印机的分辨率约为 180dpi。dpi 数越大，打印精度越高。其中单位 dpi 是指（ ）{{ select(1-2) }}

• 印点/厘米
• 印点/毫米
• 印点/英寸
• 印点/寸

3. 内存地址的最重要特点是（ ）{{ select(1-3) }}

• 随机性
• 唯一性
• 顺序性
• 连续性

4. 多媒体计算机是指（ ）{{ select(1-4) }}

• 具有多种功能的计算机
• 具有多种外设的计算机
• 能处理多种媒体的计算机
• 能借助多种媒体操作的计算机

5. 最早的计算机的用途是用于（ ）{{ select(1-5) }}

• 科学计算
• 自动控制
• 系统仿真
• 辅助设计

6. CPU 中（ ）机构相当于运算器中的一个存储单元，它的存取速度比存储器要快得多。（ ）{{ select(1-6) }}

• 存放器
• 辅存
• 主存
• 寄存器

7. 计算机软件我们一般指的是（ ）{{ select(1-7) }}

• 系统软件和实用软件
• 实用软件和自由软件
• 培训软件和管理软件
• 编辑软件和科学计算软件

8. 操作系统在第几代计算机开始应用（ ）{{ select(1-8) }}

• 第一代
• 第二代
• 第三代
• 第四代

9. 计算机中的数有浮点与定点两种，其中用浮点表示的数，通常由哪两部分组成（ ）{{ select(1-9) }}

• 指数与基数
• 尾数与小数
• 阶码与尾数
• 整数与小数

10. 如果用一个字节来表示整数，最高位用作符号位，其他位表示数值。例如：00000001 表示＋1，10000001 表示－1，试问这样表示法的整数 A 的范围应该是（ ）{{ select(1-10) }}

• -127<=A<=127
• -128<=A<=128
• -128<=A<128
• -128

11. 下列叙述中，正确的是（ ）{{ select(1-11) }}

• 线性表的线性存储结构优于链表存储结构
• 队列的操作方式是先进后出
• 栈的操作方式是先进先出
• 二维数组是指它的每个数据元素为一个线性表的线性表

12. 用某种排序方法对线性表 25,84,21,47,15,27,68,35,20 进行排序，结点变化如下：
(1)25,84,21,47,15,27,68,35,20；
(2)20,15,21,25,47,27,68,35,84；
(3)15,20,21,25,35,27,47,68,84；
(4)15,20,21,25,27,35,47,68,84.
那么，排序方法是（ ）{{ select(1-12) }}

• 选择排序
• 希尔排序
• 合并排序
• 快速排序

13. 如果某二叉树的前序为 STUWV，中序为 UWTVS，那么该二叉树的后序是（ ）{{ select(1-13) }}

• WUVTS
• UWVTS
• VWUTS
• WUTSV

14. 下面关于数据结构的叙述中，正确的叙述是（ ）{{ select(1-14) }}

• 顺序存储方式的优点是存储密度大，且插入、删除运算效率高
• 链表中的每一个结点都包含一个指针
• 包含 n 个结点的二叉排序树的最大检索长度为 log2(n)
• 将一棵树转换为二叉树后，根结点没有右子树

15. 表达式 (1+34)*5-56/7 的后缀表达式为（ ）{{ select(1-15) }}

• 1 34+5 56 7-*/
• -*+1 34 5/56 7
• 1 34+5*56 7/-
• 1 34 5*+56 7/

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

（一）（汉诺塔问题）

汉诺塔问题：古代有一个梵塔，塔内有三个座 A,B,C，A 座上有 n 个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这 n 个盘子从 A 座移到 B 座，但每次只能允许移动一个盘子，并且在移动过程中，3 个座上的盘子始终保持大盘在下，小盘在上，程序如下：

# include<iostream>
using namespace std;
void hanoi(int n,char a,char b,char c) {
    if(n==1)
        cout<<n<<" "<<a<<" "<<c<<endl;
    else {
        hanoi(n-1,a,c,b);
        cout<<n<<"."<<a<<" "<<c<<endl;
        hanoi(n-1,b,a,c);
    }
}
int main() {
    int n;
    cin>>n;
    hanoi(n,'A','B','C');
    return 0;
}

判断题

16. 当 n>=0 时，程序不会出现死循环。（ ）{{ dropdown(2-1)[√, ×] }}（1 分）

17. 输出共有 2^n 行。（ ）{{ dropdown(2-2)[√, ×] }}（1 分）

18. 当 n>0 时，将第 4 行的 == 改为 <=，程序输出结果必定不变。（ ）{{ dropdown(2-3)[√, ×] }}

19. 将第 5 行的 n 改为 1，程序输出结果必定不变。（ ）{{ dropdown(2-4)[√, ×] }}

选择题

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

• O(n)
• O(n^2)
• O(n^3)
• O(2^n)

21. 若要求输出不超过 15 行，则下列哪个 n 的值是合法的？（ ）{{ select(2-6) }}

• 0
• 4
• 5
• 6

（二）

# include <cstdio>
# define N 1005

using namespace std;
int num[N];

int main() {
    int a1 = 1, n, x;
    scanf("%d", &n);
    num[1] = 1;
    for (int i = 1; i <= n; ++i) {
        x = 0;
        for (int j = 1; j <= a1; ++j) {
            num[j] = num[j] * 5 + x;
            x = num[j] / 10;
            num[j] %= 10;
        }
        if (x > 0) num[++a1] = x;
    }
    printf("0.");
    for (int i = a1; i < n; ++i) {
        putchar('0');
    }
    for (int i = a1; i >= 1; i--) {
        printf("%d", num[i]);
    }
    putchar('\n');
    return 0;
}

判断题

22. 程序输出的是 5^n 的值。（ ）{{ dropdown(2-7)[√, ×] }}（1 分）

23. 程序执行到第 27 行时，i 的值为 1。（ ）{{ dropdown(2-8)[√, ×] }}（1 分）

24. 对于任意 1<=i<=a1，都有 0<=num<=9。（ ）{{ dropdown(2-9)[√, ×] }}

25. 程序输出的是一个小数，且小数末尾可能有多余的 0。（ ）{{ dropdown(2-10)[√, ×] }}

选择题

26. 此程序的时间复杂度是（ ）{{ select(2-11) }}

• O(n)
• O(n^2)
• O(n^3)
• O(nlogn)

27. 若 n=3，则输出为（ ）{{ select(2-12) }}

• 8
• 0.125
• 0.8
• 125

（三）

在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

输入文件第一行包含三个正整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。

接下来 N 行，每行一个整数，第 i 行的整数 a[i](0<a[i]<L)表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出文件只包含一个整数，即最短跳跃距离的最大值。

# include <iostream>
using namespace std;
int l,n,m,a[50005],ans;
bool check(int dis)
{
    int count=0,last=0;
    for(int i=1;i<=n;i++)
        if(a[i]-last<dis)count++;
            else last=a[i];
    if(count>m)return 0;return 1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    a[n+1]=l;
    int fl=0,fr=l;
    while(fl<=fr)
    {
        int mid=(fl+fr)/2;
        if(check(mid))fl=mid+1,ans=mid;
            else fr=mid-1;
    }
    cout<<ans;
    return 0;
}

判断题

28. 将第 19 行的 fl=0 改为 fl=1，程序输出结果必定不变。（ ）{{ dropdown(2-13)[√, ×] }}（1 分）

29. 程序执行到第 26 行时，必有 fl>fr。（ ）{{ dropdown(2-14)[√, ×] }}（2 分）

30. 若第 23 行执行的 check(mid)==1，则最终的 ans 小于或等于此时的 mid。（ ）{{ dropdown(2-15)[√, ×] }}（2 分）

31. 程序执行到第 10 行时，count 的值表示:如果最短跳跃距离恰好为 dis，那么最少需要移走几块岩石。（ ）{{ dropdown(2-16)[√, ×] }}（2 分）

选择题

32. 此程序的时间复杂度是（ ）{{ select(2-17) }}

• O(n^2)
• O(nl)
• O(nlogl)
• O(nlogn)

33. 若输入为：

25 5 2
2
11
14
17
21

则输出为（ ）{{ select(2-18) }}

• 3
• 4
• 5
• 6

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

（一）（迪杰斯特拉算法）

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于 1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

# include<iostream>
using namespace std;
int main()
{
    int edgs;
    int points;
    int dis[10];
    int flag[10];
    int infinity=9999999;
    cin>>points>>edgs;
    int edg[10][10];
    for (int i=1;i<=points;i++) //初始化
    {
            for (int j=1;j<=points;j++)
            {
                    if (i==j)
                    {
                        edg[i][j]= ① ；
                    }
                    else
                    {
                        edg[i][j]= ② ；
                    }
            }
    }
    int point1,point2,quanzhi;
    for (i=1;i<=edgs;i++)
    {
            cin>>point1>>point2>>quanzhi;
            edg[point1][point2]= ③ ；
    }
    for (i=1;i<=points;i++)
    {
            dis[i]=edg[1][i];
    }
    for (i=1;i<=points;i++)
    {
            flag[i]=0;
    }
    flag[1]=1;
    int min,u;
    for (i=1;i<=points-1;i++)
    { //源点到源点不用比较，因次总的次数少一次
            min=infinity;
            for (int j=1;j<points;j++)
            {
                if (flag[j]==0&&dis[j]<min)
                {//核心思想:依次比较出离源点最近的点
                    min= ④ ；
                    u=j;
                }
            }
            flag[u]=1;
            for (int v=1;v<=points;v++)
            {//找出离源点最近的点后更新 dis 里面的源点到各个点的值是否最小
                if (edg[u][v]<infinity)
                {
                    if (dis[v]>dis[u]+edg[u][v])
                    {
                        dis[v]= ⑤ ；
                    }
                }
        }
    }
    for (i=1;i<=points;i++)
    {
        cout<<dis[i]<<" ";
    }
    cout<<endl;
}

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

• infinity
• dis[j]
• 0
• 1

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

• infinity
• dis[j]
• 0
• 1

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

• quanzhi
• 0
• inf
• 1

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

• j
• dis[j]
• flag[j]
• i

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

• dis[u]
• edg[u][v]
• dis[u]+edg[u][v]
• infinity

（二）（完全背包问题）

完全背包问题。容量为 10 的背包，有 5 种物品，每种物品数量无限，其重量分别为 5,4,3,2,1，其价值分别为 1,2,3,4,5。设计算法，实现背包内物品价值最大。代码如下(输出 50)：

# include <iostream>
# include<algorithm>

using namespace std;

int main()
{
    int total_weight = 10;
    int w[6] = {0,5,4,3,2,1};
    int v[6] = {0,1,2,3,4,5};
    int dp[11] = {  ①  };

    for (int i = 1; i <=  ②  ; i++)
        for (int j = w[i]; j <=  ③  ;j++)
            dp[j] =  ④  ;

    cout <<  ⑤  << endl;
    return 0;
}

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

• 0
• 5
• 10
• 15

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

• 5
• 6
• 10
• 15

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

• 5
• 6
• 10
• 15

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

• dp[j]+v[i]
• dp[j－w[i]]＋v[i]
• min(dp[j],dp[j－w[i]]+v[i])
• max(dp[j],dp[j－w[i]]+v[i])

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

• v[10]
• dp[10]
• w[10]
• total_weight