T5T5

以比较为基本运算,对于 2n2n 个数,同时找到最大值和最小值,最坏情况下需要的最小的比 较次数为( )。

A. 4n-2

B. 3n+1

C. 3n-2

D. 2n+1

原因:先把前两个数做一次比较,然后把剩下的数两两相比,所有大的和前两个数中大的比,所有小的和前面两个数中小的比,找到最大值和最小值。一共用 1+3(n-1)=3n-3+1=3n-2 次。

错因:没有想到这一点,选的A。

T11T11

有如下递归代码

solve(t, n):
  if t=1 return 1
  else return 5*solve(t-1,n) mod n

则 solve(23,23) 的结果为( )。

A. 1

B. 7

C. 12

D. 22

原因:代码的意思是求 5t1modn5^{t-1} \mod n 的值。

错因:没看出来,蒙的C。