一.单项选择题

共15题,每题2分,共30分;每题有且仅有一个正确选项。

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

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

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

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

3. 内存地址的最重要特点是( )。

{{ select(3) }}

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

4. 多媒体计算机是指( )。

{{ select(4) }}

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

5. 最早的计算机的用途是用于( )。

{{ select(5) }}

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

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

{{ select(6) }}

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

7. 计算机软件我们一般指的是( )。 {{ select(7) }}

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

8. 操作系统在第几代计算机开始应用( )。

{{ select(8) }}

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

9. 计算机中的数有浮点与定点两种，其中用浮点表示的数，通常由哪两部分组成( )。

{{ select(9) }}

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

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

    {{ select(10) }}

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

11. 下列叙述中,正确的是( )。 {{ select(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(12) }}

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

13. 如果某二叉树的前序为STUWV,中序为UWTVS,那么该二叉树的后序是( )。

{{ select(13) }}

• WUVTS
• UWVTS
• VWUTS
• WUTSV

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

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

15. 表达式(1+34)*5-56/7的后缀表达式为( )。 {{ select(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分

（1） 汉诺塔问题：古代有一个梵塔，塔内有三个座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时,程序不会出现死循环。( ) {{ select(16) }}

• 正确
• 错误

17. 输出共有2ⁿ行。( ) {{ select(17) }}

• 正确
• 错误

18. 当n>0时,将第4行的“==”改为“<=”,程序输出结果必定不变。( ) {{ select(18) }}

• 正确
• 错误

19. 将第5行的“n”改为“1”,程序输出结果必定不变。( ) {{ select(19) }}

• 正确
• 错误

20. 此程序的时间复杂度是( )。 {{ select(20) }}

• O(n)
• O(n²)
• O(n³)
• O(2ⁿ)

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

• 0
• 4
• 5
• 6

（2）

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

22. 程序输出的是5ⁿ的值。( ) {{ select(22) }}

• 正确
• 错误

23. 程序执行到第27行时,i的值为1。( ) {{ select(23) }}

• 正确
• 错误

24. 对于任意1<=i<=al,都有0<=num<=9。( ) {{ select(24) }}

• 正确
• 错误

25. 程序输出的是一个小数，且小数末尾可能有多余的0。( ) {{ select(25) }}

• 正确
• 错误

26. 此程序的时间复杂度是( )。 {{ select(26) }}

• O( n)
• O(n²)
• O(n³)
• O(nlogn)

27. 若n=3,则输出为( ) {{ select(27) }}

• 8
• 0.125
• 0.8
• 125

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

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

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

接下来N行，每行一个整数，第i行的整数ai表示第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>>>>>n>>m;
    for(int  i=1;i< =n;i++)
        cin>>a[i] ;
    a[n+1] =1;
    int  fl=0, fr=1;
    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”,程序输出结果必定不变。( ) {{ select(28) }}

• 正确
• 错误

29. 程序执行到第26行时,必有fl>fr。( ) {{ select(29) }}

• 正确
• 错误

30. .若第23行执行的check(mid)==1,则最终的ans小于或等于此时的mid。( ) {{ select(30) }}

• 正确
• 错误

31. 程序执行到第10行时， count的值表示：如果最短跳跃距离恰好为dis，那么最少需要移走几块岩石。( ) {{ select(31) }}

• 正确
• 错误

32.此程序的时间复杂度是( )。

{{ select(32) }}

• O(n²)
• O(nl)
• O(nlogl)
• O(nlogn)

33. 若输入为:

25 5 2
2
11
14
17
21

则输出为( )。 {{ select(33) }}

• 3
• 4
• 5
• 6

三、完善程序

单选题，除特殊说明外，每小题3分，共计30分。

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

#include<bits/stdc++.h>
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 pointl,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=   ④   ;
                    u=j;
                }
            }
        	flag[u]=1 ;
            for(int v=1;v<=points;v++)
            {//找出离源点最近的点后更新dis里面的源点到各个点的值是否最小
                if(edg[u][v]
                {
                    if(dis[v]>dis[u]+edg[u][v])
                    {
                        dis[v]=   ⑤      ;
                    }
                }
          	}
    	}
        for ( i=1;i<=points;i++)
        {
            cout<<dis[i]<<" ";
        }
        cout<<endl;
}

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

• infinity
• dis[j]
• 0
• 1

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

• infinity
• dis[j]
• 0
• 1

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

• quanzhi
• 0
• inf
• 1

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

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

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

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

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

#include<iostream>
#include<cstring>
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(39) }}

• 0
• 5
• 10
• 15

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

• 5
• 6
• 10
• 15

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

• 5
• 6
• 10
• 15

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

• 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(43) }}

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