算法分析期末试题集答案(6套)1

《算法分析与设计》

一、

解答题 1. 机器调度问题。

问题描述：现在有n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为s i ，完成时间为f i ，s i

问题实例：若任务占用的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）

画出工作在对应的机器上的分配情况。

2. 已知非齐次递归方程：f (n)bf (n 1)g(n)f (0)c =-+??=?

，其中，b 、c 是常数，g(n)

是n 的某一个函数。则f(n)的非递归表达式为：n

n

n i i 1

f (n)cb b g(i)-==+∑。

现有Hanoi 塔问题的递归方程为：h(n)2h(n 1)1

h(1)1=-+??=?

，求h(n)的非递归表

达式。

解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n 递推到1，有：

n 1

n 1

n 1i i 1

n 1n 22n h(n)cb

b g(i)

22 (22121)

----=--=+=+++++=-∑

3. 单源最短路径的求解。

问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V 中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

解法：现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。

4. 请写出用回溯法解装载问题的函数。

装载问题：有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船，

其中集装箱i 的重量为wi ，且

1

2

1

n

i i w c

c =≤+∑。装载问题要求确定是否有一个合理

的装载方案可将这n 个集装箱装上这2艘轮船。如果有，找出一种装载方案。

解：void backtrack (int i)

{// 搜索第i 层结点

if (i > n) // 到达叶结点

更新最优解bestx,bestw;return; r -= w[i];

if (cw + w[i] <= c) {// 搜索左子树

4

3 2 1 100 30 maxint

10 - {1} 初始 dist[5] dist[4] dist[3] dist[2] u S 迭代

x[i] = 1;

cw += w[i];

backtrack(i + 1);

cw -= w[i]; }

if (cw + r > bestw) {

x[i] = 0; // 搜索右子树

backtrack(i + 1); }

r += w[i];

}

5. 用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。

解答：斜线标识的部分完成的功能为：提前更新bestw值；

这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。

为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。

7. 最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，

Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj

的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立

递归关系如下：

00,0 [][][1][1]1,0;

max{[][1],[1][]},0;

i j

i j

i j

c i j c i j i j x y

c i j c i j i j x y

?==

?

=--+>=

?

?-->≠

?

在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。

（2）函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填写程序中的空格，以使函数LCS完成构造最长公共子序列的功能（请

将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。

8.对下面的递归算法，写出调用f(4)的执行结果。

二、复杂性分析

1、 MERGESORT(low ，high) if low

endif

end MERGESORT

答: 1、 递归方程

设n=2k

解递归方程：

2、 procedure S1(P ，W ，M ，X ，n) i ←1; a ←

???>+==1)2/(21)(n cn n T n a

n T n

cn an kcn

T cn

n T cn cn n T n T k log )1(22)4/(4)2/)4/(2(2)(+=+=+=++=

while i≤ n do

if W(i)>M then return endif

a←a+i

i←i+1 ;

repeat

end

解： i←1 ;s←0 时间为：O(1)

while i≤ n do 循环n次

循环体内所用时间为 O(1)

所以总时间为:

T(n)=O(1)+ nO(1)= O(n)

3.procedure PARTITION(m,p)

Integer m,p,i;global A(m:p-1)

v←A(m);i←m

loop

loop i←i+1 until A(i) ≥v repeat

loop p←p-1 until A(p) ≤v repeat

if i

then call INTERCHANGE(A(i),A(p))

else exit

endif

repeat

A(m) ←A(p);A(p) ←v

End PARTITION

解：最多的查找次数是p-m+1次

4.procedure F1(n)

if n<2 then return(1)

else return(F2(2,n,1,1))

endif

end F1

procedure F2(i,n,x,y)

if i≤n

then call F2(i+1,n,y,x+y)

endif

return(y)

end F2

解：F2（2，n,1,1）的时间复杂度为：

T(n)=O(n-2); 因为i≤n时要递归调用F2，一共是n-2次

当n＝1时F1(n)的时间为 O(1)

当n>1时F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为 O(n) 5.procedure MAX(A,n,j)

xmax←A(1);j←1

for i←2 to n do

if A(i)>xmax then xmax←A(i); j←i;endif

repeat

end MAX

解：xmax←A(1);j←1 时间为：O(1)

for i←2 to n do 循环最多n-1次

所以总时间为:

T(n)=O(1)+ (n-1)O(1)= O(n)

6.procedure BINSRCH(A,n,x,j)

integer low,high,mid,j,n;

low←1;high←n

while low≤high do

mid←|_(low+high)/2_|

case

:x

:x>A(mid):low←mid+1

:else:j←mid; return

endcase

repeat

j←0

end BINSRCH

解：log2n+1

三、算法理解

1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。

各边的代价如下：

C(1,2)=3， C(1,3)=5 ，C(1,4)=2

C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1

C(5,8)=4， C(6,8)=5 ，C(7,8)=6

解：Cost(4,8)=0

Cost(3,7)= C(7,8)+0=6 ，D[5]=8

Cost(3,6)= C(6，8)+0=5, D[6]=8

Cost(3,5)= C(5，8)+0=4 D[7]=8

Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)}

= min{1+ 5, 2+4}=6 D[4]=6

Cost(2,3)= min{C(3，6)+ Cost(3,6) }

= min{4+5}=9 D[3]=5

Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)}

= min{8+5, 4+6}=10 D[2]=7

Cost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)}

= min{3+10, 5+9,2+6}= 8

D[1]=4

1→4→6→8

2、写出maxmin算法对下列实例中找最大数和最小数的过程。

数组 A=(48,12,61,3,5,19,32,7)

解：写出maxmin算法对下列实例中找最大数和最小数的过程。

数组 A=()

1、 48,12,61,3, 5,19,32,7

2、48,12 61,3 5,19 32,7

3、 48～61, 12～3 19～32，5～7

4、 61～32 3～5

5、 61 3

3、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。

A=(65,70,75,80,85,55,50,2)

解：第一个分割元素为65

(1) (2) (3) (4) (5) (6) (7) (8) i p

65 70 75 80 85 55 50 2 2 8

65 2 75 80 85 55 50 70 3 7

65 2 50 80 85 55 75 70 4 6

65 2 50 55 85 80 75 70 4 6

55 70 75 80 85 65 50 2

4、归并排序算法对下列实例排序，写出算法执行过程。

A=(48,12,61,3,5,19,32,7)

解： 48,12,61,3 5,19,32,7

48,12 61,3 5,19 32,7

12,48 3,61 5,19 7,32

3, 12, 48, 61 5, 7, 19，32

3,5, 7,12，19，32，48,61

5、写出图着色问题的回溯算法的判断X[k]是否合理的过程。

解：i←0

while i

if G[k,i]=1 and X[k]= X[i] then

return false

i←i+1

repeat

if i= k then return true

6、对于下图，写出图着色算法得出一种着色方案的过程。

解：K←1

X[1] ←1 , 返回 true

X[2]←1,返回false; X[2]←X[2]+1=2, 返回 true

X[3]←1 ,返回false; X[3]←X[3]+1=2, 返回false;X[3]←X[3]+1=3, 返回 true X[4]←1, 返回false; X[4]←X[4]+1=2, 返回false;X[4]←X[4]+1=3, 返回 true 找到一个解（1，2，3，3）

7、写出第7题的状态空间树。

解：

8、写出归并排序算法对下列实例排序的过程。

(6,2,9,3,5,1,8,7)

解：调用第一层次 6,2,9,3 5,1,8,7 分成两个子问题调用第二层次 6,2 9,3 5,1 8,7 分成四个子问题

调用第三层次 6 2 9 3 5 1 8 7 分成八个子问题

调用第四层次只有一个元素返回上一层

第三层归并 2 ,6 3, 9 1,5 7,8 返回上一层

第二层归并 2 ,3,6, 9 1,5,7,8 返回上一层

第一层归并 1, 2 ,3, 5 ,6, 7, 8,9 排序结束，返回主函数

9、写出用背包问题贪心算法解决下列实例的过程。

P=(18,12,4,1)

W=(12,10,8,3)

M=25

解:实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。

CU←25,X←0

W[1]< CU: x[1]←1; CU←CU-W[1]=13;

W[2]< CU: x[2]←1; CU←CU-W[2]=3;

W[3]>CU: x[3]←CU/ W[3]=3/8;

实例的解为：（1，1，3/8，0）

11、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。

解：有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。

一共要要执行四次才能找到值为82的数。

12、使用prim算法构造出如下图G的一棵最小生成树。

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;

dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6

解：使用普里姆算法构造出如下图G的一棵最小生成树。

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;

dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6

13、有如下函数说明 int f(int x,int y) {

f=x Mod y +1; }

已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k 的值是多少并写出详细过程。 解：有如下函数说明 int f(int x,int y) {

f=x Mod y +1; }

已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k 的值是多少并写出详细过程。 }

K 的值是5

14、McCathy 函数定义如下： 当x>100时 m(x)=x-10;

当x<=100时 m(x)=m(m(x+11));

编写一个递归函数计算给定x 的m(x)值。 解：McCathy 函数定义如下： 当x>100时 m(x)=x-10;

当x<=100时 m(x)=m(m(x+11));

编写一个递归函数计算给定x 的m(x)值。 int m(int x) {

int y;

if(x>100) return(x-100);

else

{

y=m(x+11);

return (m(y));

}

}

15、设计一个算法在一个向量A中找出最大数和最小数的元素。

解：设计一个算法在一个向量A中找出最大数和最小数的元素。

Void maxmin(A,n)

Vector A;

int n;

{

int max,min,i;

max=A[1];min=A[1];

for(i=2;i<=n;i++)

if(A[i]>max)max=A[i];

else if(A[i]

printf(“max=%d,min=%d\n”,max,min);

}

四、设计算法

1.设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为t i。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。

多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。

解：对于处理机j，用S[j] 表示处理机j已有的作业数，用P[j,k]表示处理机j的第k个作业的序号。

1）将作业按照t[1]≥t[2]≥……≥t[n]排序

2）S[1:m]清零 j←0 //从第一个处理机开始安排

3) for i←1 to n do //安排n个作业

j←j mod m +1 //选下一个处理机

S[j]←S[j]+1;

P[j,S[j]]←i ；

Repeat

2. 设有n种面值为:

d1≥d2≥……≥d n的钱币，需要找零钱M，如何选择钱币d k，的数目X k，满足d1×X i＋……d n×X n M ，使得

X i＋……X n 最小

请选择贪心策略，并设计贪心算法。

解：贪心原则：每次选择最大面值硬币。

CU←M;i←1;X←0 // X为解向量

While CU≠0 do

X[i]←CU div d[i] // X[i]为第i中硬币数

CU←CU-d[i]*X[i]

i←i+1;

repeat

3.有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。

解：定义结构体数组G，将物品编号、利润、重量作为一个结构体：例如G[k]={1,10,2} 求最优解，按利润/重量的递减序，有

{5,6,1,6} {1,10,2,5}{6,18,4,9/2} {3,15,5,3} {7,3,1,3}{2,5,3,5/3} {4,7,7,1} 算法

procedure KNAPSACK(P，W，M，X，n)

//P(1：n)和W(1；n)分别含有按

P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值

和重量。M是背包的容量大小，而x(1：n)是解向量//

real P(1：n)，W(1：n)，X(1：n)，M，cu；

integer i，n；

X←0 //将解向量初始化为零//

cu←M //cu是背包剩余容量//

for i←1 to n do

if W(i)>cu then exit endif

X(i) ←1

cu←cu-W(i)

repeat

end GREEDY-KNAPSACK

根据算法得出的解：

X=（1,1,1,1,1,0,0）获利润52，而解

（1,1,1,1, 0, 1,0）可获利润54

因此贪心法不一定获得最优解。

4. 设计只求一个哈密顿环的回溯算法。

解：Hamiltonian(n)

{k←1; x[k] ←0;

While k>0 do

x[k] ← x[k]+1;

while B(k)=false and x[k]≤n do

x[k] ← x[k]+1; repeat

If x[k]≤n then

if k=n then {print x; return}

else {k← k+1; x[k]←0;} endif

else k← k-1

endif

repeat

end

procedure B(k)

{ G[x[k-1],x[k] ]≠1 then return false; for i ←1 to k-1 do

if x[i]=x[k] then return false;endif repeat

return true; }

5．利用对称性设计算法，求n 为偶数的皇后问题所有解。 解：利用对称性设计算法，求n 为偶数的皇后问题所有解。 procedure NQUEENS1(n)

a ←0 //计数器清零

X(1)←0；k ←1 //k 是当前行；X(k)是当前列// While k>0 do //对所有的行执行以下语句// 1) { X(k)←X(k)+1 //移到下一列// While X(k)≤n and not PLACE(k) do 2) X(k)←X(k)十l if X(k)≤n then if k=n / then

{print (X)，a ←a+1 //找到一个解计数器a 加1//

if a=n/2 then return // 找到n/2个解算法结束 3) else {k ←k+1；X(k)←0；} 4) else k ←k －1 //回溯// }

end NQUEENS

1、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或))(()(n g n f Ω=或

))(()(n g n f θ=，并简述理由。

（12分） (1) ;5log )(;log )(2+==n n g n n f

(2) ;100)(;2)(2n n g n f n == (3) ;3)(;2)(n n n g n f ==

解：简答如下：

（1）)5(log log 2

+=n n θ，（2）)100(22

n n

Ω=，（3）)3(2n

n

ο=

2、试用分治法实现有重复元素的排列问题：设),...,,{21n r r r R =是要进行排列的n 个元素，其中元素n r r r ,...,,21可能相同，试计算R 的所有不同排列。（13分）

解：解答如下：

Template

void Perm(Type list[],int k,int m) {

if(k= =m){

for(int i=0;i<=m;i++) cout<

}

else for(int i=k;i<=m;i++)

if(ok(list,k,i)){

swap(list[k],list[i]);

Perm(list,k+1,m);

swap(list[k],list[i]); ……………………………..（8分）

};

}

其中ok用于判别重复元素。

Template

int ok(Type list[],int k,int i)

{

if(i>k)

for(int t=k;t

if(list[t]= =list[i]) return 0;

return 1;

}……………………………..（13分）

3、试用分治法对一个有序表实现二分搜索算法。（12分）

解：解答如下：

Template

int BinarySearch(Type a[],const Type& x,int n)

{//假定数组a[]已按非递减有序排列，本算法找到x后返回其在数组a[]中的位置，//否则返回-1

int left=0,right=n-1;

while(left<=right){

int middle=(left+right)/2;……………………………..（4分）

if(x= =a[middle]) return middle+1;

if(x>a[middle]) left=middle+1;……………………………..（8分）

else right=middle-1;

}

return -1;

}……………………………..（12分）

4、试用动态规划算法实现0-1闭包问题。（15分）

解：解答如下：

Template

void Knapsack(Type v,int w,int c,int n,Type **m)

{

Int jMax=min(w[n]-1,c);

for(int j=0;j<=jMax;j++) m[n][j]=0;

for(int j=w[n];j<=c;j++) m[n][j]=v[n]; ……………………………..（5分）

for(int i=n-1;i>1;i--){

jMax=min(w[i]-1,c);

for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];

for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); …………..（8分）};

m[1][c]=m[2][c];

if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); …………..（10分）

}

Template

Void Traceback(Type **m,int w,int c,int n,int x)

{

for(int i=1;i

if(m[i][c]= =m[i+1][c]) x[i]=0; …………..（12分）

else { x[i]=1,c-=w[i];};

x[n]=(m[n][c])?1:0;

}……………………………..（15分）

5、试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。（15分）

解：解答如下：

void dicomp(int n,int a[])

{

k=1;

if(n<3){ a[1]=0;return;};

if(n<5){ a[k]=1;a[++k]=n-1;return;}; ……………………………..（5分）

a[1]=2;n-=2;

while(n>a[k]){

k++;

a[k]=a[k-1]+1;

n-=a[k];

};……………………………..（10分）

if(n= =a[k]){ a[k]++;n--;};

for(int i=0;i

}……………………………..（15分）

m 矩阵A的一个子矩阵，使6、试用动态规划算法实现最大子矩阵和问题：求n

其各元素之各为最大。（15分）

解：解答如下：

int MaxSum2(int m,int n,int **a)

{

int sum=0;

int *b=new int[n+1];

for(int i=1;i<=m;i++){

for(int k=1;k<=n;k++) b[k]=0;……………………………..（5分）

for(int j=i;j<=m;j++){

for(int k=1;k<=n;k++) b[k]+=a[j][k];

int max=MaxSum(n,b);

if(max>sum) sum=max;

} }

return sum; ……………………………..（10分） }

int MaxSum(int n,int *a)

{

int sum=0,b=0;

for(int i=1;i<=n;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; }

Return sum; ……………………………..（15分） }

7、试用回溯法解决下列整数变换问题：关于整数i 的变换f 和g 定义如下：??2/)(;3)(i i g i i f ==。对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。（18分）

解：解答如下：

void compute() { k=1;

while(!search(1,n)){ k++;

if(k>maxdep) break; init();

};……………………………..（6分） if(found) output();

else cout<<”No Solution!”<

bool search(int dep,int n) {

If(dep>k) return false; for(int i=0;i<2;i++){

int n1=f(n,i);t[dep]=i; ……………………………..（12分） if(n1= =m||search(dep+1,n1)){ Found=true; Out();

return true; }

return false; ……………………………..（18分） }

一、排序和查找是经常遇到的问题。按照要求完成以下各题：（20分）

（1） 对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成

递减序。

（2） 请描述递减数组进行二分搜索的基本思想，并给出非递归算法。 （3） 给出上述算法的递归算法。

（4） 使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，

135。

答案：（1）第一步：15 29 135 18 32 1 27 25 5 第二步：29 135 18 32 27 25 15 1 5 【1分】

第三步：135 32 29 18 27 25 15 5 1 【1分】 第四步：135 32 29 27 25 18 15 5 1 【1分】

（2）基本思想：首先将待搜索元素v 与数组的中间元素2n A ??????进行比较，如果2n v A ??

>????，

则在前半部分元素中搜索v ；若2n v A ??

=????，则搜索成功；否则在后半部分数组中搜索v 。【2

分】

非递归算法：

输入：递减数组A[left:right]，待搜索元素v 。【1分】 输出：v 在A 中的位置pos ，或者不在A 中的消息（-1）。【1分】 步骤：【3分】

int BinarySearch(int A[],int left,int right,int v) { int mid; while (left<=right) { mid=int((left+right)/2); if (v==A[mid]) return mid; else if (v>A[mid]) right=mid-1; else left=mid+1; } return -1; }

（3）递归算法：

输入：递减数组A[left:right]，待搜索元素v 。【1分】 输出：v 在A 中的位置pos ，或者不在A 中的消息（-1）。【1分】 步骤：【3分】

int BinarySearch(int A[],int left,int right,int v) { int mid;

if (left<=right)

{

mid=int((left+right)/2);

if (v==A[mid]) return mid;

else if (v>A[mid]) return BinarySearch(A,left,mid-1,v);

else return BinarySearch(A,mid+1,right,v);

}

else

return -1;

}

（4）搜索18：首先与27比较，18<27，在后半部分搜索；再次与18比较，搜索到，返回5。【1分】

搜索31：首先与27比较，31>27，在前半部分搜索；再次32比较，31<32，在后半部分搜索，与29比较，31>29，此时只有一个元素，未找到，返回-1。【2分】搜索135：首先与27比较，135>27，在前半部分搜索；再次32比较，135>32，在前半部分搜索；与135比较，相同，返回0。【2分】

二、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。（20分）。

答案：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。【1分】

步骤V1V2E1E2

1.{a} {b} {} {ab}

2.{a,b} {d} {ab} {bd}

3.{a,b,d} {c,f} {ab,bd} {dc,df}

4.{a,b,d,c} {f} {ab,bd} {df}

5.{a,b,c,d,f} {e} {ab,bd,dc,df} {fe}

6.{a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg}

7.{a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh}

8.{a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 【以上每步2分】

结果：从a到h的最短路径为a b d f e g h

→→→→→→，权值为18。【1分】三·假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。

答案：求所有顶点对之间的最短路径可以使用Dijkstra 算法，使其起始节点从a 循环

到h ，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】 三、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】

5x =6x =7x =17分，每个节点1

分】

a ．1501154040305035190.62540

-++++?= 7(1,1,1,1,,0,0)8

b. 1501154040305030177.560

-++++?=7(1,1,1,1,0,,0)12

c ．4040305010170++++=

(1,1,1,1,0,0,1)

d. 1501054040303530167.560

-++++?= 3(1,1,1,0,1,,0)4

e. 150130404050353017560

-++++?=

1

(1,1,0,1,1,,0)3

f. 1501304040503510170.7135

-++++?=

4(1,1,0,1,1,0,)7

g. 40405030160+++=

(1,1,0,1,0,1,0)

h. 1501404040353010146.8535-++++?= 2(1,1,0,0,1,1,)7

i.1501254030503530167.560-++++?=5(1,0,1,1,1,,0)12 j. 150145

4030503530157.560-++++?

=1(0,1,1,1,1,,0)12

在Q 1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F 、

海洋地质学概论复习题及答案

海洋地质学概论 CH1 绪论 1、海洋地质学的定义 以传统的地质学理论和板块构造理论为基础，以海洋高新探测和处理技术为依托，在地球系统科学理论的指导下，研究大洋岩石圈地质过程及其与地球相关圈层（尤其是大气、水圈和地幔）间相互作用，为人类开发资源、维护海洋权益和保护环境服务的科学。 2、海洋地质学结构 1）海洋地貌学； 研究海底形态、空间分布及成因为主要内容。大洋地貌的研究对于板块构造学说的建立做出过重要贡献。 2）海洋地球物理学； 是地球物理学的重要分支，是支撑海洋地质发展的重要技术手段。包括海洋重力、海底地磁场、海底地震学、海洋地电学和海洋地热学等。 3）海底构造地质学 是20世纪海洋地质学发展中最辉煌的领域，板块构造模式不只是海洋构造，而且建立了全球构造体系。 4）海洋沉积学； 研究海洋沉积物的特征、时空分布及形成和演变机制为主要内容。海洋沉积学的发展极大地丰富了沉积学的内容并革新了传统沉积学的理论。海洋沉积学已发展成为一个涵盖很广的学科领域，例如海洋沉积矿物学、海洋沉积地球化学、海洋沉积动力学、碳酸盐沉积学、构造沉积学等。 5）海洋地层学； 是地质学的重要理论基础，重建地质历史和解释历史是它的主要任务。由于现代技术的广泛应用及深海钻探计划和浅海钻探的开展，在岩石地层划分、生物地层划分和年代地层划分方面取得了长足的进展。 6）古海洋学； 它是深海钻探计划(DSDP)的产物，以探索海洋环境和海水物理学、化学特征演变历史及研究海洋生产力和海洋生物的宏观演化为目的，它的主要研究材料是海洋沉积物，发展了从沉积物中提取高分辨地质信息的一切现代手段。古海洋学已成为大洋钻探计划(ODP)、全球变化研究等重大国际研究计划的重要内容，是20世纪末地球科学中发展最快的分支学科，也是21世纪通过气圈／水圈／地圈探索地球历史的重要领域。 7）海底矿产地质学 它是研究赋存于海底的矿物资源和有机物矿产的形成、富集规律及矿产资源的赋存状态和开采条件的科学。海洋石油、天然气；滨海及浅海固体砂矿；大洋多金属结核、结壳、磷块岩、块状硫化物矿和多金属软泥等热液矿产及天然气水合物等。

中国近现代史纲要试题及答案

中国近现代史纲要试题及答案 一、单项选择题(本大题共30小题，每小题1分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.鸦片战争前中国封建社会的主要矛盾是( ) A.地主阶级和农民阶级的矛盾 B.帝国主义和中华民族的矛盾 C.资产阶级和工人阶级的矛盾 D.封建主义和资本主义的矛盾 正确答案是：A 2.中国封建社会产生过诸多“盛世”，出现在清代的是( ) A.文景之治 B.贞观之治 C.开元之治 D.康乾盛世 正确答案是：D 3.将中国领土台湾割让给日本的不平等条约是( ) A.《南京条约》 B.《北京条约》 C.《马关条约》 D.《瑗珲条约》 正确答案是：C 4.西方列强对中国的侵略，首先和主要的是( ) A.政治控制 B.军事侵略 C.经济掠夺 D.文化渗透 正确答案是：B 5.1839年组织编写成《四洲志》，向中国人介绍西方情况的是( ) A.林则徐 B.魏源

C.马建忠 D.郑观应 正确答案是：A 6.19世纪末，在帝国主义列强瓜分中国的狂潮中提出“门户开放”政策的国家是( ) A.俄国 B.日本 C.美国 D.德国 正确答案是：C 7.太平天国农民起义爆发的时间是( ) A.1851年 B.1853年 C.1856年 D.1864年 正确答案是：A 8.太平天国由盛而衰的转折点是( ) A.永安建制 B.北伐失利 C.天京事变 D.洪秀全病逝 正确答案是：C 9.最早对兴办洋务的指导思想作出完整表述的人是( ) A.冯桂芬 B.马建忠 C.王韬 D.郑观应 正确答案是：A 10.洋务运动时期最早创办的翻译学堂是( ) A.同文馆 B.广方言馆 C.译书局 D.译书馆 正确答案是：A

《微机原理与接口技术》模拟试题6参考答案及评分细则

《微机原理与接口技术》模拟试题六参考答案及评分细则 一、判断并陈述理由题（不陈述理由不计分）（1分×10=10分）: 1．（×）8086CPU的最大模式是为实现多处理器系统而设计的。 2．（√）在8086CPU构成的微机系统中的数据可以存放在几个不连续的段中。3．（×）DMA方式可以实现内存与接口之间数据的直接交换。 4．（×）8086 的可屏蔽中断受到IF标志位的影响，并且需要从数据线上读取中断类型码。 5．（×）构成一个最小8086 CPU的微机系统除了8086、8282、8286至少还需要8284时钟发生器。 6．（√）8086CPU的Ready信号是由外部硬件产生的。 7．（√）8086复位时，（CS）＝FFFFH，（IP）=0000H，所以8086在复位后重新启动时，便从内存的FFFF0H单元开始执行指令，使得系统在启动时自动进入系统程序。 8．（×）中断类型码乘以4,就可以得到中断向量的存放地址。 9．（√）多个外设可以通过8259A中断控制器用一条中断请求线向CPU发中断请求。 10．（×）8251是可编程串行通信接口芯片而8255是可编程并行通信接口芯片。 二、选择题（1分×10=10分） 1 2 3 4 5 6 7 8 9 10 B B C B A A B A D D 三、填空（每空1分×20=20分）： 1．操作码操作数 2．CS DS ES SS 3．00020H 00023H 4．（1）ADD DX，BX （2）ADD [BX]0B2H，CX （3）ADD AL，[BX][SI] （4）ADD WORD PTR [0524H]，2A59H 5．数据信息控制信息状态信息 6．程序控制的输入输出方式中断传送方式DMA工作方式 7．工作方式控制字置位/复位控制字 四．简答如下基本概念题：（5分×5＝25分） 1．I/O接口电路采用统一编址时对微处理器无特殊要求,只需将I/O接口电路当作存储对于一样对待即可；而独立编址时则对微处理器有特殊要求，需要CPU 的指令系统中包含有访内指令和访外指令以及专门的访内操作和访外操作的控制逻辑。 2．INTR是由可屏蔽中断请求引脚INTR引入的外部硬件中断；而INT n是由软中断指令产生软件中断？ 3．因为动态存储器所存的信息是放在芯片内部的电容上的，由于电容的缓慢放电，时间久了会造成数据的丢失。为了保证数据不丢失，必须及时将数据信息读

机械设计模拟试题集及答案

机械设计（2）模拟试卷及参考答案 一、是非题（对的用“√”表示，错的用“×”表示，每小题1分，共10分） 1.在链传动设计中，链节数一般选奇数为宜。（×） 2.在蜗杆传动中，当量摩擦系数随齿面相对滑动速度的增大而增大。 (×) 3.单万向联轴器的从动轴角速度不均匀，改用双万向联轴器后，从动轴的角速度即可变为均匀。(×) 4.为了提高轴的刚度，轴的材料可以采用合金钢来代替碳素钢。（×) 5.在蜗杆传动中，蜗杆头数越多，则蜗杆传动的效率就越高。 (√) 6.齿式联轴器是一种无弹性元件的挠性联轴器，它对轴的安装精度要求不高，允许有一定的偏移量。（√） 7.滚动轴承的静强度安全系数S0只能大于1。（×） 8.动压滑动轴承热平衡计算时，若进油温度t i<35℃，则说明轴承发热不严重。（×) 9.滚动轴承轴向预紧的主要目的是为了提高轴承的承载能力。 (×) 10.在滑动轴承设计中，适当选用较大的宽径比会提高承载能力。（√） 11.在带、链两级传动中，宜将带传动放在高速级。（√） 12.在链传动中，张紧轮宜安装在靠近主动轮的松边外侧上。 (√) 13.在蜗杆传动中，中心距a = (d2+d1)/2 = m(z1+z2)/2。(×) 14.在工作时只承受弯矩而不承受转矩的轴，其工作应力一定是对称循环变应力。（×) 15.选择联轴器规格型号时的主要依据之一是：T ca＜[T]。 (√) 16.在不完全液体润滑滑动轴承设计中，限制pv值的主要目的是限制轴承的温升。（√） 17.滚动球轴承在工作时滚动体上某一点的载荷及应力均呈周期性的不稳定变化。（√） 18.毡圈密封装置的毡圈及轴承盖上的装毡圈槽都是矩形截面，目的是为了得到较好密封效(×) 19.刚性联轴器在安装时要求两轴严格对中，而挠性联轴器在安装时可以不考虑对中问题。（×） 20.为了增加油膜压力，液体动力润滑的向心滑动轴承中，一般油槽应开在承载区。（×） 21.在链传动中，当主动链轮匀速转动时，链速是变化的。（√） 22.蜗杆传动中传动平稳的原因在于其同时啮合的齿对数较多。（√） 23.滚动轴承的润滑方式通常可根据轴承的转速n来选择。（×） 24.使用十字滑块联轴器时对轴和轴承都会产生附加动载荷。（√） 25.相同系列和尺寸的球轴承与滚子轴承相比时，滚子轴承的承载能力比球轴承高，而极限转速低。（√） 26.在蜗杆、链两级传动中，宜将链传动布置在高速级。（×） 27.滑动轴承的润滑油膜的平均温度越低，其粘度 越小。（×） 28.齿式联轴器的外齿齿顶是制成凹弧面的。（×） 29.提高轴的表面质量有利于提高轴的疲劳强度。（√） 30.链传动中，当一根链的节数为偶数时，接头形式需采用过渡链节。（×） 31.在链传动中，当主动链轮匀速转动时，链速是变化的。（√） 32.当液体动力润滑滑动轴承所受载荷较大时，则应选用较大的轴承间隙。（×） 33.滑动轴承轴瓦上的油沟应开在非承载区。（√） 34.单个万向联轴器在使用时会产生附加动载荷，为改善这种情况，常成对使用之。（√） 35.滚动轴承的公称接触角越大，承受轴向载荷的能力就越大。（√） 36.滚动轴承中，滚子轴承的承载能力要比球轴承高而极限转速则比球轴承低。（√） 37.为了大幅提高轴的刚度，可把轴的材料从碳钢改为合金钢。（×） 38.对轴的表面进行强化处理，不能提高轴的疲劳强度。（×） 39.在蜗杆传动中，蜗杆头数越少，自锁性越好。 ( √ ) 40.在蜗杆传动中，当量摩擦系数随齿面相对滑动速度的增大而增大。（×） 41.设计链传动时，链长（节数）最好取链轮齿数的整数倍。（×）

2020年智慧树知道网课《沉积学》课后章节测试满分答案

第一章测试 1 【单选题】(1分) 关于沉积岩的分类，以下说法正确的是: A. 海绿石石英砂岩为碎屑岩的一种。 B. 灰绿色块状凝灰岩是一种碳酸盐岩。 C. 碳酸岩是一种沉积岩。 D. 砾屑灰岩属于碎屑岩类。 2 【单选题】(1分) 沉积岩的形成包括（）等三个阶段： A. 原始物质形成阶段、沉积物搬运和沉积作用阶段、沉积后作用阶段 B. 原始物质形成阶段、沉积物搬运阶段、沉积阶段 C. 沉积物形成阶段、沉积物搬运阶段、沉积阶段 D. 沉积物搬运阶段、沉积阶段、沉积后阶段

3 【判断题】(1分) 与岩浆岩相比，沉积岩在地表分布面积更广，体积更大 A. 对 B. 错 4 【判断题】(1分) 因为沉积岩与火山岩均形成于地壳表层，所以二者的形成条件相同 A. 错 B. 对 5 【多选题】(1分) 同岩浆岩相比，沉积物具有（）的特点 A. 高温矿物罕见 B. 存在大量有机质

C. 低温矿物富集 D. FeO高于Fe2O3 E. 特有的自生矿物 6 【多选题】(1分) 关于沉积岩的结构特征，下列说法正确的是： A. 沉积岩具有结晶结构和碎屑结构 B. 沉积岩具有碎屑结构而无结晶结构 C. 沉积岩与岩浆岩均具有结晶结构 D. 沉积岩与岩浆岩均具有玻璃结构 7 【多选题】(1分) 关于沉积岩形成的地壳表层条件（沉积圈），以下说法正确的是： A. 沉积圈环境特征与岩浆岩形成条件相似 B.

沉积物沉积时的压力最大可达1100atm C. 沉积物沉积时的温度最高可达摄氏650度 D. 同岩浆岩与变质岩相比，沉积岩形成于常温常压环境 8 【单选题】(1分) 按照原始物质来源，沉积岩可以分为（）。 A. 砾岩、砂岩、粉砂岩、粘土岩 B. 碎屑岩、化学岩、生物岩、火山碎屑岩 C. 碎屑岩、碳酸盐岩、生物岩、火山碎屑岩 D. 碎屑岩、化学岩、火山碎屑岩、碳酸盐岩 9 【判断题】(1分) 沉积物沉积后一般会先后经历表生期、同生期、后生期和成岩期等阶段的变化。 A. 错 B. 对

中国近代史纲要试题(含答案)

中国近代史纲要试题（含答案） 一、单项选择题 1．在甲午战争后，严复翻译的《天演论》所宣传的重要思想是（D）。A．师夷长技以制夷B．中学为体，西学为用C．天下兴亡，匹夫有责D．物竞天择，适者生存 2．戊戌政变后，新政中被保留下来的只有（B）。A．农工商总局B．京师大学堂C．译书局D．铁路矿务局 3．中国近代第一次思想解放潮流的是（B）。A．洋务派与顽固派的论战B．维新派与顽固派的论战C．革命派与保皇派的论战D．问题\与\主义\的论战\ 4．洋务派创办的第一个规模较大的近代军事工业是(AA．江南制造总局B．马尾船政局C．天津机器局D．湖北枪炮厂 5．下列关于洋务运动表述,不正确的是（B）。A．内忧外患,清政府内部产生洋务派B．师夷长技,洋务派选择资本主义强国C．自强求富,办军工兴民用采用机器生产D．只师长技,破产结局不可避免6．洋务派认为清王朝的“心腹之害”是（D）。A．英国B．俄国C．日本D．太平天国和捻军。) 7．在我国近代最早出现的近代企业是（C）。A．洋务派创办的企业B．民族资本主义企业C．外商企业D．官僚资本主义企业8．近代中国第一个领导资产阶级革命的全国性政党是（D）A、兴中会B、科学补习所C、华兴会D、中国同盟会

9．新文化运动中对封建礼教进行揭露控拆的《狂人日记》的作者是（B） A.胡适 B.鲁迅C.李大钊 D.陈独秀 10．1895年，日本强迫清政府签订《马关条约》，割去中国（B）全岛及所有附属岛屿和澎湖列岛。A．香港B．台湾C．澳门D．崇明 11．19世纪80－90年代签订的中外不平等条约，与19世纪40－50年代相比，最根本的不同是（D）。A．割取中国领土的面积最大B．索取的赔款数额不断加大 C.规定开放更多的通商口岸 D.列强获得在华投放资本的特权 12．提出了“师夷长技以制夷”的思想的是（C）。A．龚自珍B．林则徐C．魏源D．郑观应 13．1839年组织编写成《四洲志》，向中中国人介绍西方情况的是（A）。A．林则徐B．魏源C．马建忠 D．郑观应 14．五四运动的中心由北京转移到上海后，运动的新特点是(C) A.商人罢市B.学生大规模罢课 C.工人阶级登上政治舞台 D.运动取得初步胜利 15．遵义会议是中国共产党从幼稚走向成熟的标志，主要由于它（B）A．结束了“左”倾错误在中央的统治 B．在军事上确定了以毛泽东为核心的新的党中央的正确领导C．在生死关头妥协地处理了党内当时最主要的问题D．保证了长征转移的胜利

管理信息系统模拟题及答案(模拟六)

2010 自考《管理信息系统》模拟试题及答案（2）（考试时间 150 分钟）点击查看 >> 参考答案第一部分选择题 一、单项选择题（本大题共 20 小题，每小题 1分，共 20 分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1. 下面属于数据的是（） A. 数字 B. 声音 C. 视频 D. 以上均正确 2. 反映企业日常生产和经营管理活动的信息是（） A. 战略信息 B. 战术信息 C. 作业信息 D. 决策信息 3. ___________________________ 电子会议系统通过卫星把不同城市的会议室联结起来，出席会议的人可能在屏幕上显示，互相自由交谈，是由提供的功能。（） A. 业务处理系统 B .过程 控制系统 C. 办公自动化系统 D. 管理信息系统 4. 下列属于战术级管理的是（） A. 高层管理 B .中层管理来源：考试大 C. 基层管理 D. 作业层管理 5. 关于企业流程再造说法错误的是（） A. 要点在于简化和优化任务之间的联系，减少冗余过程 B. 信息技术使信息流动最佳化 C. 信息技术是业务流程优化和重组的技术基础 D. 是在原有基础上进行的修补，有利于提高效率 6.下列属于应用软件的是（） A. 数据库管理系统 B.系统维护软件 C.图像处理软件 D. 操作系统 7. OSI 参考模型中，第四层是（） A. 应用层 B. 传输层 C.数据链路层 D. 会话层 8.网络中，打印输出设备属于（） A. 网络服务器 B. 工作站 C. 共享设备 D. 用户终端

9. 数据库的功能中，包括数据字典、用户数据、存取路径等的是 ( ) A. 数据库操纵功能 B .数据库运行管理 C. 数据库的建立和维护功能 D. 数据组织、存储和管理功能 10. 下列关于Access说法错误的是() A. 是 Microsoft Office 附带的一个组件 B. 支持超级链接 C .能够在查询过程中进行统计汇总等 D. 操作界面不同于 Word、 Excel 11. Access中，可实现随机查询要求，提高查询灵活性的查询方式是() A. 交叉表查询 B. 参数查询 C. 操作查询 D. SQL 查询 12. U/C 矩阵中， C 代表 ( ) A. 使用 B. 完成 C. 功能 D. 创建 13. CASE 法严格的讲只是一种开发 ( ) A. 过程 B. 步骤 C. 环境 D. 方法 14. 可行性分析的最后成果是( ) A. 项目开发的初步方案 B .可行性分析报告 C. 确定新项目开发有无必要和可能 D. 提供当前现有信息系统的概括 15. 数据字典中，数据结构任选项的表示形式为( ) A. ( ) B. [ ] C. { } D. ( ) 16. 将 2007 年 3月 1 日表示为 20070301，这种编码类型属于 ( ) A. 顺序码 B. 区间码 C. 特征码 D. 十进制码 17. 系统每秒钟执行的作业数是指( ) A. 响应时间 B. 可靠性 C. 吞吐量 D. 处理方式 18. -般适合于比较大的系统的转换方式的是（）

离散数学模拟题一套及答案

离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())

下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。

沉积学套题目和答案

《沉积学》模拟试题A 一、名词解释(每题2分,共20分) 1.沉积岩 2.机械沉积分异作用 3.杂基 4.结构成熟度 5.沉积后作用 6.叠层石构造 7.沃尔索相律 8.河流的“二元结构” 9.沉积相10.重力流 二、填空题(每题1分,共20分) 1.沉积岩的形成过程大致可分成如下阶段：、、。 2.按有无页理发育，可将粘土岩分为页岩和。 3.狭义火山碎屑岩的主要岩石类型有：、、。 4.碳酸盐岩主要由、、、、五种结构组分组成。 5.冲积扇的沉积类型包括、、和四种类型。 6.根据地貌特点、水动力状况、沉积物特征，无障壁海岸沉积相由陆向海依次为、、和四个亚相。 三、简答题(每题6分,共30分) 1.简述三级分类命名原则并对具体岩石命名。 简述三级分类命名原则（4分），并给具体岩石命名（2分）：一碎屑岩，粒度在0.5-0.25mm的碎屑占60%，0.1-0.25mm的占27%，0.01～0.1mm的占11%，<0.01mm的占2%。2.试画出并简单描述3种不同类型的层理构造（每个图示和描述各1分）。 3.白云石有哪些成因机理？ 4.简述典型浊积岩的垂向序列（鲍玛序列）特征。 5.简述欧文的陆表海能量带模式。 四、论述题(共40分) 1.试从碎屑岩的原始物质来源、搬运和沉积作用、沉积后作用等方面阐述碎屑岩的形成过程。（25分） 2.何谓建设性三角洲？试述建设性三角洲的鉴定特征、主要亚相、微相类型，并分析与油气的关系。 （15分） 《沉积学》模拟试题A参考答案 一、名词解释（每题2分，共20分） 1.沉积岩 沉积岩是组成岩石圈的三大类岩石（岩浆岩、变质岩、沉积岩）之一，是它在地壳表层条件下，由母岩的风化产物、火山物质、有机物质等沉积岩的原始物质成分，经过搬运作用、沉积作用以及沉积后作用而形成的一类岩石。

中国近现代史试题汇总(含全答案)

10.中共确定建立抗日民族统一战线的方针的会议是（ C ） A.八七会议 B.遵义会议 C.瓦窑堡会议 D.洛川会议 20.中华民国南京临时政府的局限性表现为（ ABC ） A.承认清政府与列强所订的一切不平等条约有效 B.没有提出任何可以满足农民土地要求的政策和措施 C.维护封建土地制度 22.毛泽东在《论持久战》一文中科学地预测中国持久抗战将经历三个阶段,即（ ABC ） A.战略防御阶段 B.战略相持阶段 C.战略反攻阶段 D.战略进攻阶段 E.战略决战阶段 35.简述鸦片战争后中国社会发生的两个根本性变化。 答：一，独立的中国逐步变成半殖民地的中国；二，封建的中国逐步变成半封建的中国。 37.简述抗日战争胜利的原因。 ①正义性的反侵略战争：这是中国民族革命与世界反法西斯战争两重性质的进步的和正义的战争，因此得道多助，具有广泛的社会基础。 ②全民族抗战：抗日战争是以国共合作为基础的全民族抗战，体现了中华民族的觉醒和民族的凝聚力。从敌后战场到正面战场，从国统区到论陷区。从国内社会各阶层到国外华侨，从汉族到少数民族都充分体现了全民抗战的特点。 ③中共的中流砥柱作用：从抗日民族统一战线的倡导和建立，到全面抗战路线的制定；从敌后根据地的建立和抗日游击战争的开展，到毛泽东《论持久战》指明抗战前途；从坚持斗争求团结巩固统一战线，到抓住国际国内有利时机及时反攻胜利，都突出了中共在抗战胜利中的关键作用。 ④两大战场相互依存，相互配合，坚持到抗战胜利，成为中国抗日战争的突出特点。 ⑤世界反法西斯战争的相互配合；世界反法西斯统一战线的形成和作战的相互协调是二战胜利的根本原因,苏美对日作战是中国抗战决胜的有力配合. 38.简述新民主主义革命时期中国存在的三种政治力量及其建国方案。 三种政治力量： (1)地主阶级和买办性的大资产阶级（后官僚资产阶级）。他们是反动势力、民主革命的对象。其政治代表现时北洋政府，以后主要是国民党统治集团。 (2)民族资产阶级。他们是中间势力，民主革命的力量之一。其政治代表是民主党派的某些领导人物和若干无党派民主人士。 (3)工人阶级、农民阶级和城市小资产阶级。他们是进步势力，民主革命的主要力量。其政治代表是中国共产党。 三种建国方案： (1)地主阶级和买办性的大资产阶级的方案。主张继续实行地主阶级、买办的大资产阶级的军事独裁统治，使中国继续走半殖民地半封建社会的道路。 (2)民族资产阶级民族资产阶级的建国方案。他们是要建立一个名副其实的资产阶级共和国，以便是资本主义得到自由和充分的发展，使中国成为一个独立的资本主义社会。 (3)工人阶级和其他进步势力的方案。他们主张在工人阶级及其政党的领导下，首先进行一场彻底的反帝反封建的新式资产阶级民主革命，即新民主主义革命，以便建立一个工人阶级领导的人民共和国，即人民民主专政的国家；并经过这个人民共和国，逐步达到社会主义和共产主义。

《编译原理》模拟期末试题汇总 6套,含答案

《编译原理》模拟试题一 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√) 6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×) 10．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。

(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式 三、填空题(每空1分，共10分)

注册税务师考试《税法一》模拟试题及答案6套

税务师考试《税法一》模拟试题及答案第一套 一、单项选择题 1、自2015年5月10日起，我国对卷烟在批发环节征收的消费税，税率由原来的5%变为11%加0.005元/支，假设在2015年12月，甲卷烟批发企业被税务机关查出其2014年隐瞒卷烟不含税销售额50万元，对消费税税率的判定不得适用新法，只能沿用旧法，这体现了（）。 A、新法优于旧法原则 B、法律不溯及既往原则 C、实体从旧，程序从新原则 D、程序优于实体原则 2、下列关于税法解释的表述，错误的是（）。 A、按照解释的尺度不同，税法解释可以分为字面解释、限制解释与扩充解释 B、按照文义解释原则，必须严格依税法条文的字面含义进行解释，既不扩大也不缩小，这是所谓字面解释 C、限制解释是税法解释的基本方法，税法解释首先应当坚持限制解释 D、税法的扩充解释是指为了更好地体现立法精神，对税法条文所进行的大于其字面含义的解释 3、下列关于税法与刑法、国际法关系的表述，不正确的是（）。 A、税法与刑法是从不同的角度规范人们的社会行为，但两者的联系十分密切 B、税法与刑法在调整对象上有衔接和交叉 C、税法与国际法是相互影响、相互补充、相互配合的 D、税法属于权利性法规，刑法属于禁止性法规 4、下列关于税收实体法要素中税率的说法，正确的是（）。 A、在累进税率的前提下，边际税率等于平均税率 B、边际税率与平均税率是分析纳税人负担时常用的概念 C、零税率是以零表示的税率，是免税的一种方式 D、边际税率的提高不会带动平均税率的上升

5、下列关于税收征收程序和税务稽查程序的表述，错误的是（）。 A、税务登记是整个征收管理的首要环节 B、纳税申报是税收管理信息的主要来源和重要的税务管理制度 C、稽查局查处税收违法案件时，实行选案、检查、审理、执行分工制约原则 D、检查应当自实施检查之日起30日内完成，确需延长检查时间的，应当经稽查局局长批准 6、在我国现行税法体系中，属于全国人民代表大会通过的税收法律的是（）。 A、《中华人民共和国企业所得税法》 B、《增值税暂行条例实施细则》 C、《税收代理试行办法》 D、《税收征收管理法实施细则》 7、下列关于税收执法的相关表述，不正确的是（）。 A、税收执法的实质是税收执法主体将深藏在税法规范、法条中的国家意志贯彻落实到社会经济生活与税收活动之中 B、税收执法具有被动性 C、税收执法监督的主体是税务机关 D、税收执法监督的内容是税务机关及其工作人员的行政执法行为 8、下列各项中，不符合税收刑事司法规定的是（）。 A、税收刑事司法是以《刑法》和《刑事诉讼法》为法律依据的 B、税收刑事责任是实施税务刑事处罚的基础，而税务刑事处罚是税收刑事责任的实现方式 C、在税收刑事程序中有税务机关、公安机关、检察院和法院四个国家机关参与，经历案件移送、立案侦查、提起公诉和司法裁判四个阶段 D、税收刑事案件的公诉是税收刑事程序的枢纽环节 9、下列关于小规模纳税人管理的说法，错误的是（）。 A、年应税销售额超过小规模纳税人标准的其他个人，按一般纳税人纳税 B、自2018年5月1日起，增值税小规模纳税人标准为年应征增值税销售额500万元及以下

中国近代史试题(含答案)

中国近代史 一、单项选择题(本大题共15个小题，每小题2分，共30分；在每小题给出的四个选项中，只有一项符合题意) 1．“列强的炮声惊醒了古老中华帝国的美梦，中华民族的屈辱史——中国近代史开始了。”这里“列强的炮声”指的是( ) A．鸦片战争 B．第二次鸦片战争 C．甲午中日战争 D．八国联军侵华战争 2．下列图片中的历史人物在近代反侵略斗争中作出了重大的贡献，其中收复新疆的是( ) 3．列强对近代中国发动多次侵略战争，其中19世纪九十年代与19世纪四十年代的战争相比，最主要的区别是( ) A．列强获得了对华资本输出的特权 B．侵犯到中国渤海地区 C．允许列强在华设立使馆界 D．割占中国的领土面积扩大 4．在近代中国，有这样一批机器工业：企业实行雇佣制，经费由政府拨给，产品分配给军队。下列企业中属于这批工业的有( ) A．福州船政局 B．轮船招商局 C．滦州煤矿公司 D．沈阳飞机制造厂 5．19世纪末，随着民族危机加重，康有为、梁启超等维新派掀起了

一场救亡图存的政治变革。有关这场变革的说法不正确的是( ) A．光绪帝颁布诏书标志着变革的开始 B．在变革中建立了近代中国第一所体制完备的高等学府 C．此次变革得到湖南巡抚陈宝箴的支持 D．这是一场以光绪帝为首的封建统治者的自救运动 6．在一次历史研究性学习活动中，同学们搜集了某一时期陈独秀、李大钊、胡适、鲁迅等人的资料和文章。你认为这一学习活动的主题应是( ) A．“自强”“求富” B．“实业救国” C．“三民主义” D．“民主”和“科学” 7．在中国近代化探索的历程中，不同阶层、不同派别的力量进行了不同尝试。下列内容出现的先后顺序是( ) ①蔡元培倡导学术上“兼容并包”②公车上书③兴中会成立④北洋海军的建立 A．②③①④ B．④③②① C．①④③② D．③②④①8．马克思主义是中国共产党的行动指南，马克思主义成为近代中国新思潮的主流始于( ) A．新文化运动前期 B．十月革命爆发后 C．五四运动后 D．中国共产党成立后 9．1924年5月，孙中山在黄埔军校开学典礼上说：“要从今天起，重新做革命的基础，另外成立一种理想上的革命军。一生一世，都不存升官发财的心理，只知道做救国救民的事业。”两年后，该校师生

英语模拟试卷6及答案

福建省专升本入学考试 英语模拟试卷6 II. Vocabulary and Structure (20 points) Directions: There are 20 incomplete sentences in this section. For each sentence there are four choices marked A, B, C and D. Choose one answer that best completes the sentence and blacken the corresponding letter on the Answer Sheet. 11. Neither her parents nor Jill _______ seen this movie before; all of them want to see it tomorrow. A. has B. have C. having D. had 12. I have to _____ myself for a while. I’ve got something urgent to deal with. A. forgive B. excuse C. spare D. entertain 13. I was told that ______ 10:15 flight would get us to Shanghai in time to reach ______ Fudan University. A. the; / B. /; the C. a; the D. the; the 14. They said they would ______ their plan until it was finished. A. change B. stick to C. stay at D. go on 15. I don’t like this hat. Please show me _______. A. another B. the other C. others D. both 16. When I applied for my passport to be renewed, I had to send a _____ photograph. A. fresh B. fashionable C. late D. recent 17. We will _______ be in a hurry if we want to catch the 12:00 train. A. must B. need C. necessary D. have to 18. The businessman demanded that all his money _______ without any delay. A. to pay B. paid C. be paid D. be paying 19. You ought to take every ________ to improve your English. A. case B. chance C. thing D. time 20. _______ from outside, the house seemed to be very shabby but its interior was luxurious. A. Seen B. Seeing C. To see D. Saw 21. I’ve been working on my vocabulary actively, and one way to _____ it is to see films in English on TV. A. go down B. go up C. improve D. decrease 22. He did not do it in the way________ I would have done it myself. A. in that B. which C. as D. / 23. The girl is ______ young _______. A. so; to work B. too; to work C. too; to working D. so; working 24. Without air, there would be no atmosphere to protect us ________ the sun’s deadly rays. A. from B. under C. to D. in 25. Your box is _______ mine. A. four times as big as B. four times as bigger as C. as four times big D. as big as four times 26. Every means _______ been tried since then. A. has B. have C. are D. is 27. She likes hearing her own voice. She never stops ________. A. talking B. telling C. to talking D. to tell 28. The policeman looked me ________ several times and obviously disliked what he saw. A. up and down B. over and over again C. to and fro D. round and round 29. Talking to foreigners is fun if you _______ the right time and place. A. locate B. consider C. choose D. decide 30. Not only _______ us light，but it gives us heat.

中国近代史试卷答案

常州轻工职业技术学院成人高等教育2015学年期末考试拟题纸 课程名称卷种（A/B）考核形式闭卷使用班级总份数出卷人审核人班级学号姓名成绩第1页共2页 一、单项选择题（每题1分，共20分） 题号12345678910 答案D A A B C C C B C D 题号11121314151617181920 答案B A B C D D B A C A 二、多项选择题（每题2分，共20分） 题号12345 答案AC ABC AB AB ABD 题号678910 答案AB ABC ABC ABCD ABCD 三、简答题（每小题10分，共40分）（根据学生答案情况酌情评分） 1、近代中国进行的反侵略战争具有什么意义？ 第一，近代中国人民进行的反侵略战争，沉重打击了帝国主义侵华的野心，粉碎了他们瓜分中国和把中国变成完全殖民地的图谋。 帝国主义列强一次次对中国发动侵略战争，为了掠夺和扩大殖民地，为了他们自身的殖民扩张利益，正是中国人民的英勇斗争，表现了中国人民不屈不挠的爱国主义精神，也给外国侵略者以沉重打击和深刻教训，使他们越来越清楚地认识到，中国是一个很难征服的国家，不得不放弃了瓜分中国的政策。 第二，近代中国人民进行的反侵略战争，教育了中国人民，振奋了中华民族的民族精神，鼓舞了人民反帝反封建的斗志，大大提高了中国人民的民族觉醒意识。甲午战争以后，中华民族面临生死存亡之际，帝国主义的瓜分狂潮和民族危机的刺激，全民族开始有了普遍的民族意识的觉醒，救亡图存的思想日益高涨。正是这种亡国灭种的危机感，增强了中华民族整体民族利益休戚与共的民族认同感和凝聚力，成为中华民族自立自强并永远立于世界民族之林的根本所在。 2、为什么说孙中山领导的辛亥革命引起了近代中国的历史性巨大变化？ 辛亥革命是资产阶级领导的以反对君主专制制度、建立资产阶级共和国为目的的革命，是一次比较完全意义上的资产民主革命。在近代历史上，辛亥革命是中国人民救亡图存、振兴中华而奋起革命的一个里程碑，它使中国发生了历史性巨变。 第一，辛亥革命推翻了封建势力的政治代表、帝国主义在中国的代理人——清王朝的统治，沉重的打击了中外反动势力，使中国反动统治者在政治上乱了阵脚。 第二，辛亥革命结束了统治中国两千多年的封建君主专制制度，建立了中国历史上第一个资产阶级共和政府。 第三，辛亥革命给人们带来一次思想上的解放。 第四，辛亥革命促使社会经济、思想习惯和社会风俗等方面发生了新的积极变化。 第五，辛亥革命在一定程度上打击了帝国主义的侵略势力，推动了亚洲各国民族解放运动的高涨。 3、为什么说中国人民抗日战争是弱国战胜强国的范例？其基本经验是什么？ 第一、从实力对比来看，抗日战争是弱国对强国的战争。中国是半殖民地半封建社会，政治、军事、经济、文化等各方面综合实力都很落后，是弱国。而日本是世界上一等强国，军事、经济实力和政治组织力量都很强大。 第二，从战略对比来看，抗日战争是大国对小国的战争。 第三，从战争性质上看，抗战是中国抵御日本侵略的正义战争。中国是正义的、进步的反侵略战争，是得道的；日本是非正义的、野蛮的、侵略战争，是失道的。 第四，从战争结果上看，中国人民的抗日战争取得了近代以来的第一次反侵略战争的完全胜利。中国人民彻底打败了日本侵略者，使中华民族避免遭受殖民奴役的厄运。 基本经验： 第一，全国各族人民的大团结是中国人民战胜一切艰难困苦、实现奋斗目标的力量源泉。没有全国各民族人民的大团结，就没有抗日战争的伟大胜利。 第二，以爱国主义为核心的伟大民族精神是中国人民团结奋进的精神动力。以爱国主义为核心的中华民族精神是抗日战争得以坚持和胜利的重要思想保证。 第三，提高综合国力是中华民族自立于世界民族之林的基本保证。一个国家只有首先自强，才能在世界上自立。 第四，中国人民热爱和平，反对侵略战争，同时又不惧怕战争。 第五，只有坚持中国共产党的领导，中华民族才能捍卫自己的生存和发展的权利，才能创造美好的未来。 4、怎样认识建立独立的、比较完整的工业体系和国民经济体系的重大意义？ 独立的比较完整的工业体系和国民经济体系的建立，是了不起的巨大成就，是中国人民在中国共产党领导下英勇奋斗的伟大成果，是社会主义制度优越性的生动体现，具有极其重要的战略意义，它为我们继续推进社会主义建设开拓了可以依靠的阵地，为实现现代化的伟大事业奠定了初步的物质基础。 随着独立的比较完整的工业体系的形成，工业在国民经济中的主导地位门益明显，发挥着越来越重要的作用。工业部门不仅为改善人民生活提供了大量的日用消费品，为国民经济其他部门和国防建设提供了大批燃料、动力、原材料和技术装备，而且还为出口提供了相当数量的产品，它