二、阅读程序(程序输人不超过数组或字符串定义的范围; 除特殊说明外，判断题1.5分，选择题4分，共计40分)

阅读程序1：

#include<bits/stdc++.h>
using namespace std;
const int Maxn=10005;
int n,b[Maxn];
inline void mergesort(int*a,int l,int r) {
    if (l==r) return;
    int mid=l+r>>1;
    mergesort(a,l,mid),mergesort(a,mid+1,r);
    int i=l,j=mid+1,cnt=0;
    while (i<=mid && j<=r) {
        if (a[i]<=a[j]) b[++cnt]=a[i++];
        else b[++cnt]=a[j++];
    }
    while (i<=mid) b[++cnt]=a[i++];
    while (j<=r) b[++cnt]=a[j++];
    for (i=l;i<=r;i++) a[i]=b[i-l+1];
}
int a[Maxn];
int main(void) {
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    mergesort(a,1,n);
    for (int i=1;i<=n;i++) cout<<a[i]<<(i==n ? '\n' : ' ');
    return 0;
}

16. (1分)该算法中"int *a"没有传值。 {{ select(16) }}

• 正确
• 错误

17. (1分)该算法会换行。 {{ select(17) }}

• 正确
• 错误

18. 该算法中mergesort函数时间复杂度为O(n log n)。 {{ select(18) }}

• 正确
• 错误

19. 如果输入为"5 4 3 9 7 8"则输出为3 4 7 8 9\n。 {{ select(19) }}

• 正确
• 错误

20. 下面哪句与i==n?'\n':' '相同（）。 {{ select(20) }}

• i!=1?'\n':' '
• "\n"[i==n]
• "\n"[i!=n]
• ' '

21. 该算法的最劣复杂度与哪个排序算法相同（）。 {{ select(21) }}

• 快速排序
• 选择排序
• 计数排序
• 堆排序

阅读程序2：

#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,f[10010],p1,p2,p3;
int find(int k){
    if(f[k]==k) return k;
    return f[k]=find(f[k]);
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++) f[i]=i;
    for(i=1;i<=m;i++){
        cin>>p1>>p2>>p3;
        if(p1==1)
            f[find(p2)]=find(p3);
        if(p1==2)
            if(find(p2)==find(p3))
                printf("Y\n");
            else
                printf("N\n");
    }
    return 0;
}

22. (1分)该算法中p1的作用是确定操作类型。 {{ select(22) }}

• 正确
• 错误

23. (1分)去掉for(i=1;i<=n;i++) f[i]=i;对该算法没有影响。 {{ select(23) }}

• 正确
• 错误

24. 输入2 2 1 1 2 2 1 2输出为Y。 {{ select(24) }}

• 正确
• 错误

25. 输入2 1 2 1 2输出为N。 {{ select(25) }}

• 正确
• 错误

26. 该算法时间复杂度为（）。 {{ select(26) }}

• O(m log n)
• O(nm)
• O(n+m)
• O(nm²)

27. 把return f[k]=find(f[k]);改成return find(f[k]);最差时间复杂度为（）。 {{ select(27) }}

• O(m log n)
• O(nm)
• O(n+m)
• O(nm²)

阅读程序3：

int t,x[100],a[100];
void work(int d,int i,int n){
    int k;
    if(n==1)
    {
        for(k=0;k<d;k++)
            printf("%3d",a[k]);
        printf("\n");
    }
    else
        for(k=i;k<t;k++)
            if(n%x[k]==0)
            {
                a[d]=x[k];
                work(d+1,k,n/x[k]);
            }
}
int main(){
    int i,k,n;
    cin>>n;
    for(i=n;i>1;i--)  if(n%i==0)   x[t++]=i;
    work(0,0,n);
}

28. for(i=n;i>1;i--) if(n%i==0) x[t++]=i;的作用是求出n的所有因数。 {{ select(28) }}

• 正确
• 错误

29. 该程序的作用是对n进行质因数分解。 {{ select(29) }}

• 正确
• 错误

30. printf("%3d",a[k]);中去掉3对程序没有影响。 {{ select(30) }}

• 正确
• 错误

31. 去掉if(n%x[k]==0)对程序有影响。 {{ select(31) }}

• 正确
• 错误

32. 如果输入为2，那么输出为（）。 {{ select(32) }}

• 2
• 2 1
• 1 2
• 2 2

33. 如果输入为72，那么输出的非回车字符有多少行（）。 {{ select(33) }}

• 14
• 15
• 16
• 17