第 1 题 文件型病毒传染的主要对象是（）

第 2 题 24 针打印机的分辨率约为180dpi. Dpi 数越大，打印精度越高。其中单位dpi是指（）

第 3 题 内存地址的最重要特点是（）

第 4 题 多媒体计算机是指（）

第 5 题 最早的计算机的用途是用于（）

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

第 7 题 计算机软件我们一般指的是（）

第 8 题 操作系统在第几代计算机开始应用（）

第 9 题 计算机中的数有浮点与定点两种，其中用浮点表示的数，通常由( )这两部分组成（）

第 10 题 如果用一个字节来表示整数，最高位用作符号位，其他位表示数值。例如: 0000001 表示+1，1000001 表示-1，试问这样表示法的整数A的范围应该是（）

第 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.那么，排序方法是（）

第 13 题 如果某二叉树的前序为STUWV， 中序为UWTVS，那么该二叉树的后序是（）

第 14 题 下面关于数据结构的叙述中，正确的叙述是（）

第 15 题 表达式(1+34)*5-56/7的后缀表达式为（）

二、判断题（每题 2 分，共 20 分）

第 16 题 汉诺塔问题:古代有一个梵塔，塔内有三个座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 题 (1分)当n≥0时，程序不会出现死循环。

第 17 题 (1分)输出共有 2^n 行。

第 18 题 当n>0时，将第4行的“==” 改为“<=”，程序输出结果必定不变。

第 19 题 将第5行的“n”改为“1”，程序输出结果必定不变。

第 20 题 (3分)此程序的时间复杂度是（）。

第 21 题 若要求输出不超过15行，则下列哪个n的值是合法的（） 。

第 23 题

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

第 23 题 (1分)程序输出的是5^n的值。

第 24 题 (1分)程序执行到第27行时，i的值为1。

第 25 题 对于任意1≤i≤al，都有0≤num≤9。

第 26 题 程序输出的是一个小数，且小数末尾可能有多余的0。

第 27 题 此程序的时间复杂度是（）。

第 28 题 若n=3，则输出为（）。

第 30 题 在起点和终点之间，有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;
}

第 30 题 (1分)将第19行的“fl=0”改为“f1=l”，程序输出结果必定不变。

第 31 题 (2分)程序执行到第26行时，必有fl>fr。

第 32 题 (2分)若第23行执行的check(mid)==l, 则最终的ans≤此时的mid。

第 33 题 (2分)程序执行到第10行时，count 的值表示:如果最短跳跃距离恰好为dis，那么最少需要移走几块岩石。

第 34 题 此程序的时间复杂度是（）。

第 35 题 若输入为:25 5 2 2 11 14 17 21 则输出为（）。

三、编程题（每题 25 分，共 50 分）

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

#include<iostream>
using namespace std;
int main()
{
	int edgs;
	int points ;
	int dis[10];
	int flag[10];
	int infinity=999999;
	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]=___(1)___;
			}
			else
			{
				edg[i][j]=___(2)___;
			}
		}
	}
	int point1 , point2 , quanzhi ;
	for (i=1; i<=edgs; i++)
	{
		cin>>point1>>point2>>quanzhi ;
		edg[point1][point2]= ___(3)___ ;
	}
	for (i=1; i<=points; i++)
	{
		dis[i]=edg[1][i];
	}
	for (i=1; i<=points; 1++)
	{
		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 (f1ag[j]==0&&dis[j]<min)
			{//核心思想:依次比较出离源点最近的点
				min=___(4)___;
				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]=___(5)___;
				}
			}
		}		
	}
	for (i=1; i<=points; i++)
	{
		cout<<dis[i]<" ";
	}
	cout<<endl;
}

第 37 题 ①处应填( )

第 38 题 ②处应填( )

第 39 题 ③处应填( )

第 40 题 ④处应填( )

第 41 题 ⑤处应填( )

第 43 题 完全背包问题 容量为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]= { ___(1)___ };
	
	for(int i=1; i<=___(2)___; i++)
		for(int j=w[i]; j<=___(3)___; j++)
			dp[j] =___(4)___;
	cout <<___(5)___<< endl;
	return 0;
}

第 43 题 ①处应填( )

第 44 题 ②处应填( )

第 45 题 ③处应填( )

第 46 题 ④处应填( )

第 47 题 ⑤处应填( )