1.判断题
（1）对（2）对（3）对（4）对（5）错（6）错（7）错
2.选择题
1~5 DDADA 6 C
3.填空题
1)自反性对称性传递性
2)gcd（a，m）=1
3)子域扩域
4)保密系统的通信理论
5)冗余度和唯一解距离
6)1
7)时间复杂度和空间复杂度
4.简答题及计算题
（1）
#include<stdio.h>
unsigned int Gcd( unsigned int M, unsigned int N ) {
unsigned int Rem;
while( N > 0 )
{
Rem = M % N;
M = N;
N = Rem;
}
return M;
}
void main()
{
int temp;
int a,b;
scanf("%d",&a);
scanf("%d",&b);
printf("the greatest common factor of %d and %d is ",a,b); printf("%d\n",Gcd(a,b));
}
（2）
1024=888*1+136 gcd（888，136）
888=136*6+72 gcd（136，72）
136=72*1+64 gcd（72，64）
72=64*1+8 gcd（64，8）
64=8*8+0 gcd（8，0）
gcd（1024，888）=8
gcd（2，99）=1
φ(99)=φ(9*11)=φ(32*11)=9*（1-1/3）*11=66 1000000=16666*60+40
21000 000 mod99≡216666*60+40 mod99≡240 mod99≡10244 mod99≡344mod99≡672mod99≡34
（4）
x5+2≡2x(2x4+2)+(2x+2)
2x4+2≡(x3+2x2+x+2)(2x+2)+1
1≡2x4+2-(x3+2x2+x+2)(2x+2)
≡2x4+2-(x3+2x2+x+2)[(x5+2)-2x(2x4+2)]
≡(2x4+4x3+2x2+4x+1)(2x4+2)+(2x3+x2+2x+1)(x5+2 )
≡(2x4+x3+2x2+x+1)(2x4+2)+(2x3+x2+2x+1)(x5+2) 所以，g(x)=1，s(x)=2x4+x3+2x2+x+1，t(x)=2x3+x2+2x+1。

x≡1mod5
x≡5mod6
x≡4mod7
x≡10mod11
m1 =5, m2 =6,m3 =7,m4 =11
a1 =1, a2 =5,a3 =4,a4 =10
M=5*6*7*11=2310
M1 =6*7*11=462, M2 =5*7*11=385, M3 =5*6*11=330,M4 =5*6*7=210
Mb≡1modm
462b1≡1mod5 b1≡3mod5
385b2≡1mod6 b2≡1mod6
330b3≡1mod7 b3≡1mod7
210b4≡1mod11 b4≡1mod11
1*3*462+5*1*385+4*1*330+1*10*210≡2111mod2310 兵数2111mod2310。

（6）
证明：
封闭性
∵a,b∈Z+
∴a+b+a.b∈Z+
∴a。

b∈Z+
∴（Z+，。

）满足封闭性
结合律
（a。

b）。

c=(a+b+a.b)。

c=(a+b+a.b)+c+(a+b+a.b)*c=a+b+c+ac+bc+ab+abc a。

(b。

c)=a。

(b+c+b.c)=a+b+c+b.c+a*(b+c+b.c)=a+b+c+ac+bc+ab +abc
∴（a。

b）。

c=a。

(b。

c)
（7）
H(x)=-∑p(xi)log(p(xi)) (i=1,2,3,4)
=-（2*（1/4log1/4）+1/8log1/8+2*（3/16log3/16））=23/8-3/8log3
（8）
旅行商问题（TSP Travelling Salesman Problem）该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。

可以用回溯法和贪心算法解决。

还有子集和问题，Hamilton回路，最大团问题等。