#G115. GESP level5 初等数论

GESP level5 初等数论

GESP level5 - 初等数论

  1. 唯一分解定理描述的内容是( )? {{ select(1) }}
  • 任意整数都可以分解为素数的乘积
  • 每个合数都可以唯一分解为一系列素数的乘积
  • 两个不同的整数可以分解为相同的素数乘积
  • 以上都不对
  1. 辗转相除法也被称为( ) {{ select(2) }}
  • 高斯消元法
  • 费马定理
  • 欧几里得算法
  • 牛顿迭代法
  1. 下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改,使其能正确实现相应功能。
bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i * i < num; ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return false;
    return true;
}

{{ select(3) }}

  • num < 2 应该改为 num <= 2
  • 循环条件 i * i < num 应该改为 i * i <= num
  • 循环条件应该是 i <= num
  • 循环体中应该是 if (num % i != 0)
  1. 在埃拉托斯特尼筛法中,要筛选出不大于n的所有素数,最外层循环应该遍历什么范围( )?
vector sieveOfEratosthenes(int n) {
    std::vector isPrime(n + 1, true);
    std::vector primes;
    { 
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

{{ select(4) }}

  • for (int i = 2; i <= n; ++i)
  • for (int i = 1; i < n; ++i)
  • for (int i = 2; i <= sqrt(n); ++i)
  • for (int i = 1; i <= sqrt(n); ++i)
  1. 素数的线性筛法时间复杂度为( )。 {{ select(5) }}
  • O(n)
  • O(n log n)
  • O(n log log n)
  • O(n²)
  1. 辗转相除法用于求两个整数的最大公约数。( ) {{ select(6) }}
  • 对
  • 错
  1. 二分查找要求被搜索的序列是有序的,否则无法保证正确性。( ) {{ select(7) }}
  • 对
  • 错
  1. 分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决,最后合并得到原问题的解。( ) {{ select(8) }}
  • 对
  • 错
  1. 分治算法的典型应用之一是归并排序,其时间复杂度为O(n log n)。( ) {{ select(9) }}
  • 对
  • 错
  1. 素数表的埃氏筛法和线性筛法的时间复杂度都是O(n log log n)。( ) {{ select(10) }}
  • 对
  • 错
  1. 下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。下面有关说法错误的是( )。
int fiboA(int N)
{
    if(N ==1||N==2)
        return 1;
    return fiboA(N-1)+fiboA(N-2);
}
int fiboB(int N)
{
    if (N ==1||N==2)
        return 1;
    int last2=1,last1=1;
    int nowVal=0;
    for(inti=2;i<N;i++)
    {
        nowVal=last1+last2;
        last2=last1;
        last1 =nowVal;
    }
    return nowVal;
}

{{ select(11) }}

  • fiboA( ) 用递归方式,fiboB() 循环方式
  • fiboA( ) 更加符合斐波那契数列的数学定义,直观易于理解,而fiboB() 需要将数学定义转换为计算机程序实现
  • fiboA( ) 不仅仅更加符合数学定义,直观易于理解,且因代码量较少执行效率更高
  • fiboB( ) 虽然代码量有所增加,但其执行效率更高
  1. 有关下面C++代码说法正确的是( )。
int rc;
int foo(int x,int y)
{
    int r;
    if(y ==0)
        r=x;
    else
        r=foo(y,x%y);
    rc++;
    return r;
}

{{ select(12) }}

  • 如果x 小于10, rc 值也不会超过20
  • foo 可能无限递归
  • foo 可以求出 x 和 y 的最大公共质因子
  • foo 能够求出 x 和 y 的最小公倍数
  1. 下面C++代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数N是否素数,有关其时间复杂度的正确说法是( )。
bool isPrimeA(int N)
{
    if(N<2)
        return false;
    for(inti=2;i<=N/2;i++)
        if(N%i==0)
            return false;
    return true;
}
bool isPrimeB(int N)
{
    if(N<2)
        return false;
    for (int i=2;i<=sqrt(N);i++)
        if(N%i==0)
            return false;
    return true;
}

{{ select(13) }}

  • isPrimeA( ) 的最坏时间复杂度是O(n/2),isPrimeB( ) 的最坏时间复杂度是O(logN),isPrimeA() 优于isPrimeB()
  • isPrimeA() 的最坏时间复杂度是O(n),isPrimeB( ) 的最坏时间复杂度是O(n½),isPrimeB() 绝大多数情况下优于isPrimeA()
  • isPrimeA() 的最坏时间复杂度是O(n½),isPrimeB( ) 的最坏时间复杂度是O(n),isPrimeA( ) 优于isPrimeB( )
  • isPrimeA() 的最坏时间复杂度是O(logN) ,isPrimeB( ) 的最坏时间复杂度是O(n),isPrimeA() 优于isPrimeB( )
  1. 小杨想编写一个判断任意输入的整数N是否为素数的程序,下面哪个方法不合适?( ) {{ select(14) }}
  • 埃氏筛法
  • 线性筛法
  • 二分答案
  • 枚举法
  1. 小杨设计了一个拆数程序,它能够将任意的非质数自然数N转换成若干个质数的乘积,这个程序是可以设计出来的。( ) {{ select(15) }}
  • 对
  • 错
  1. 插入排序有时比快速排序时间复杂度更低。( ) {{ select(16) }}
  • 对
  • 错
  1. 小杨想写一个程序来算出正整数N有多少个因数,经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。( ) {{ select(17) }}
  • 对
  • 错
  1. 下面C++代码以递归方式实现字符串反序,横线处应填上代码是( )。
//字符串反序
#include 
#include 
using namespace std;
string sReverse(string sIn){
    if(sIn.length()>sIn;
        cout<<sReverse(sIn)<<end1;
        return 0;
    }

{{ select(18) }}

  • sIn[sIn.length() - 1] + sReverse(sIn.substr(0, sIn.length() - 1));
  • sIn[0] + sReverse(sIn.substr(1, sIn.length() - 1));
  • sReverse(sIn.substr(0, sIn.length() - 1)) + sIn[sIn.length() - 1];
  • sReverse(sIn.substr(1, sIn.length() - 1)) + sIn[sIn.length() - 1];
  1. 下面代码中的isPrimeA() 和isPrimeB() 都用于判断参数N是否素数,有关其时间复杂度的正确说法是( )。
#include 
#include
using namespace std;

bool isPrimeA(int N){
    if(N<2)
        return false;
    for(inti=2;i<N;i++)
        if(N%i==0)
            return false;
    return true;
}
bool isPrimeB(int N){
    if(N<2)
        return false;
    int endNum=int(sqrt(N));
    for(inti=2;i<=endNum;i++)
        if(N%i==0)
            return false;
    return true;
}

int main(){
    cout<<boolalpha;
    cout<<isPrimeA(13)<<" "<<isPrimeB(13)<<end1;
    return 0;
}

{{ select(19) }}

  • isPrimeA() 的最坏时间复杂度是O(N),isPrimeB() 的最坏时间复杂度是O(log N),isPrimeB() 优于isPrimeA()。
  • isPrimeA() 的最坏时间复杂度是O(N),isPrimeB() 的最坏时间复杂度是O(N½),isPrimeB() 优于isPrimeA()。
  • isPrimeA() 的最坏时间复杂度是O(N½),isPrimeB() 的最坏时间复杂度是O(N),isPrimeA() 优于isPrimeB()。
  • isPrimeA() 的最坏时间复杂度是O(log N),isPrimeB() 的最坏时间复杂度是O(N),isPrimeA() 优于isPrimeB()。
  1. 找出自然数N以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中埃氏筛法效率更高。( ) {{ select(20) }}
  • 对
  • 错
  1. 唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积,即质因数分解是唯一的。( ) {{ select(21) }}
  • 对
  • 错
  1. 根据唯一分解定理,下面整数的唯一分解是正确的()。 {{ select(22) }}
  • 18=3×6
  • 28=4×7
  • 36=2×3×6
  • 30=2×3×5
  1. 下述代码实现素数表的线性筛法,筛选出所有小于等于n的素数,横线上应填的最佳代码是()。
vector sieve_1inear(int n){
    vector is_prime(n +1,true);
    vectorprimes;
    if(n<2)return primes;
    
    is_prime[0]=is_prime[1]= false;
    for(inti=2;i<=n/2;i++){
        if(is_prime[i]) primes.push_back(i);
        
        for(intj=0; ;j++){ //在此处填入代码
            is_prime[i*primes[j]]= false;
            if(i%primes[j]==0)
                break;
        }
    }
    for(inti=n/2 +1;i<=n; i++){
        if(is_prime[i]) primes.push_back(i);
    }
    return primes;
}

{{ select(23) }}

  • j<primes.size()
  • i * primes[j] <= n
  • j < primes.size() && i * primes[j] <= n
  • j <= n
  1. 线性筛相对于埃拉托斯特尼筛法,每个合数只会被它的最小质因子筛去一次,因此效率更高。( ) {{ select(24) }}
  • 对
  • 错