阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第9节：树和图

第6题【NOIP】2010

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool  map[SIZE][SIZE],found;
bool successful(){
    int i;
    for(i=1;i<=n;i++)
        if(!map[r[i]][r[i%n+1]])
           return false;
    return true;
}
14 void swap(int *a,int *b)
{
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
void perm(int left,int right)
{
    int i;
    if(found)
       return ;
    if(left>right){
        if(successful()){
            for(i=1;i<=n;i++)
                cout<<r[i]<<' ';
            found=true;
        }
        return ;
    }
    for(i=left;i<=right;i++){
        swap(r+left,r+i);
        perm(left+1,right);
        swap(r+left,r+i);
    }
}
int main()
{
    int x,y,i;
    cin>>n>>m;
44  memset(map,false,sizeof(map));
    for(i=1;i<=m;i++){
        cin>>x>>y;
        map[x][y]=true;
48      map[y][x]=true;
    }
    for(i=1;i<=n;i++)
       r[i]=i;
    found=false;
    perm(1,n);
    if(!found)
        cout<<"No solution!"<<endl;
    return 0;
}

●判断题

(1)在44行前加一个左斜杠，程序能正常运行，结果不变。

{{ select(6-1) }}

• 正确
• 错误

(2)去掉14行的*,运行结果不变。

{{ select(6-2) }}

• 正确
• 错误

(3)将48行删去不影响输出结果

{{ select(6-3) }}

• 正确
• 错误

(4)将map类型改为int不会影响运行结果。

{{ select(6-4) }}

• 正确
• 错误

●选择题

(5)该程序时间复杂度为()

{{ select(6-5) }}

• $O(n^{mlogn}×m^{nlogm})$
• O(n * m)
• O(m! * n)
• O(n! * n)

(6)输入：9 12 1 2 2 3 3 4 4 5 5 6 6 1 1 7 2 7 3 8 4 8 5 9 6 9输出()

{{ select(6-6) }}

• 1 2 3 4 5 6 7 8 9
• 9 8 7 2 4 3 5 1 6
• 3 2 7 1 6 9 5 4 8
• 1 6 9 5 4 8 3 2 7