一.单项选择题

共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) }}

• 以笔划的多少
• 以部首
• 1以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}

二、阅读程序

程序输入不超过数组或字符串定义的范围；除特殊说明外，判断题1.5分，选择题4分，共计40分

（1）

#include<iostream>
using namespace std;
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”(不含引号)。( ) {{ select(16) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• O(num)
• O(num²)
• O($\sqrt{num}$）
• O(log num)

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

• 0.45
• 0.4
• 0.5
• 0.35

（2）

#include<iostream>
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行的括号去掉，程序输出结果一定不变。( ) {{ select(22) }}

• 正确
• 错误

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

• 正确
• 错误

24. 若输入为“44”,则输出为“78”。( ) {{ select(24) }}

• 正确
• 错误

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

• 正确
• 错误

26. 若输入为“3 4”,则输出为( )。 {{ select(26) }}

• 8
• 12
• 18
• 19

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

• 0
• 2022
• 2
• 2024

（3）

#include<iostream>
using namespace std;
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。（） {{ select(28) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

31. 此程序的时间复杂度为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分。

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

#include<bits/stdc++.h>
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. v < = b. v

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

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

#include<iostream>
#include<cstring>
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(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]
• G[1][0]
• G[3][1]
• G[0][3]

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

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