选择题整理结果

1. 与数组相比，链表在()操作上通常具有更高的效率。

{{ select(1) }}

• 随机访问元素
• 查找指定元素
• 在已知位置插入或删除节点
• 遍历所有元素

2. 下面C++代码实现双向链表。函数is_empty()判断链表是否为空，如链表为空返回true，否则返回false。横线处不能填写()。

struct Node{
    int data;
    Node* prev;
    Node* next;
};

struct DoubleLink{
    Node* head;
    Node* tail;
    int size;

    DoubleLink(){
        head= nullptr;
        tail= nullptr;
        size= 0;
    }

    bool is_empty() const{
        ______
    }
};

{{ select(2) }}

• return head== nullptr;
• return tail== nullptr;
• return head.data== 0;
• return size== 0;

3. 基于上题代码正确的前提下，填入相应代码完善append()，用于在双向链表尾部增加新节点，横线上应填写()。

void append(int data){
    Node* newNode= new Node{data, nullptr, nullptr};
    if(is_empty()){
        head= tail= newNode;
    }else{
        ______
    }
    ++size;
}

{{ select(3) }}

• tail->next= newNode;
• newNode->prev= tail; tail= newNode;
• tail= newNode; newNode->prev= tail; tail->next= newNode;
• tail->next= newNode; newNode->prev= tail; tail= newNode;

4. 下列C++代码用循环链表解决约瑟夫问题，即假设n个人围成一圈，从第一个人开始数，每次数到第k个的人就出圈，输出最后留下的那个人的编号。横线上应填写()。

int findLastSurvival(int n, int k){
    Node* head= createCircularList(n);
    Node* p= head;
    Node* prev= nullptr;

    while(p->next!= p){
        for(int count= 1; count< k;++count){
            prev=p;
            p=p->next;
        }
        ______
    }
    cout<<"最后留下的人编号是:"<< p->data<< endl;
    delete p;
    return 0;
}

{{ select(4) }}

• prev->next= p->next; delete p; p= prev->next;
• delete p; prev->next= p->next; p= prev->next;
• delete p; p= prev->next; prev->next=p->next;
• prev->next= p->next; p= prev->next; delete p;

5. 下列C++代码判断一个正整数是否是质数，说法正确的是()。

bool is_prime(int n){
    if(n<= 1) return false;
    if(n==2|| n==3||n==5) return true;
    if(n%2==0||n%3==0||n%5==0) return false;
    
    int i=7;
    int step= 4;
    int finish_number= sqrt(n)+ 1;

    while(i<= finish_number){
        if(n% i== 0) return false;
        i+= step;
        step= 6- step;
    }
    return true;
}

{{ select(5) }}

• 代码存在错误，比如5是质数，但因为5%5余数是0返回了false
• finish_number的值应该是n/2，当前写法将导致错误
• 当前while循环正确的前提是：所有大于3的质数都符合6k±1形式
• while循环修改为for循环，其执行效果和执行时间相同

6. 下列C++代码用两种方式求解两个正整数的最大公约数，说法错误的是()。

int gcd0(int big, int small){
    if(big< small) swap(big, small);
    if(big% small== 0) return small;
    return gcd0(small, big% small);
}

int gcd1(int big, int small){
    if(big< small) swap(big, small);
    for(int i= small; i>= 1;--i){
        if(big% i== 0&& small% i== 0) return i;
    }
    return 1;
}

{{ select(6) }}

• gcd0()函数的时间复杂度为O(log n)
• gcd1()函数的时间复杂度为O(n)
• 一般说来，gcd0()的效率高于gcd1()
• gcd1()中的代码for(int i=small;i>=1;--i)应该修改为for(int i= small;i>1;--i)

7. 下面的代码用于判断整数n是否是质数，错误的说法是()。

bool is_prime(int n){
    if(n<= 1) return false;
    int finish_number= static_cast<int>(sqrt(n))+ 1;
    for(int i= 2; i< finish_number;++i){
        if(n%i==0) return false;
    }
    return true;
}

{{ select(7) }}

• 埃氏筛算法相对于上面的代码效率更高
• 线性筛算法相对于上面的代码效率更高
• 上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高
• 相对而言，埃氏筛算法比上面代码以及线性筛算法效率都高

8. 唯一分解定理描述了关于正整数的什么性质?

{{ select(8) }}

• 任何正整数都可以表示为两个素数的和
• 任何大于1的合数都可以唯一分解为有限个质数的乘积
• 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积
• 所有素数都是奇数

9. 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是()。

int find_max_recursive(const vector<int>& nums, int left, int right){
    if(left== right) return nums[left];
    int mid= left+(right- left)/ 2;
    int left_max= find_max_recursive(nums, left, mid);
    int right_max= find_max_recursive(nums, mid+ 1, right);
    return max(left_max, right_max);
}

{{ select(9) }}

• 该算法采用分治算法
• 该算法是递归实现
• 该算法采用贪心算法
• 该算法不是递推算法

10. 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是()。

int find_max(const vector<int>& nums){
    if(nums.empty()) throw invalid_argument("输入数组不能为空");
    int max_value= nums[0];
    for(int num: nums){
        if(num> max_value) max_value= num;
    }
    return max_value;
}

{{ select(10) }}

• 本题find_max()函数采用的是迭代算法
• 本题find_max()函数的时间复杂度为O(n)
• 和上一题的find_max()相比，因为没有递归，所以没有栈的创建和销毁开销
• 本题find_max()函数和上一题的find_max()时间复杂度相同

11. 下面的C++代码用于在升序数组1st中查找目标值target最后一次出现的位置。相关说法，正确的是()。

int binary_search_last_occurrence(const vector<int>& lst, int target){
    if(lst.empty()) return -1;
    int low= 0, high= lst.size()- 1;
    while(low< high){
        int mid=(low+ high+ 1)/ 2;
        if(lst[mid]<= target){
            low= mid;
        } else{
            high= mid-1;
        }
    }
    if(lst[low]== target) return low;
    else return -1;
}

{{ select(11) }}

• 当lst中存在重复的target时，该函数总能返回最后一个target的位置，即便lst全由相同元素组成
• 当target小于lst中所有元素时，该函数会返回0
• 循环条件改为while(low<=high)程序执行效果相同，且能提高准确性
• 将代码中(low+ high+1)/2修改为(low+ high)/2效果相同

12. 有关下面C++代码的说法，错误的是()。

double sqrt_binary(long long n, double epsilon= 1e-10){
    if(n< 0) throw invalid_argument("输入必须为非负整数");
    if(n==0||n==1) return n;

    //阶段1
    long long low= 1, high= n;
    long long k=0;
    while(low<= high){
        long long mid=(low+ high)/ 2;
        long long mid_sq= mid* mid;
        if(mid_sq==n) return mid;
        else if(mid_sq< n){
            k= mid;
            low= mid+1;
        } else{
            high= mid-1;
        }
    }

    //阶段2
    double low_d= (double) k;
    double high_d= (double) (k+1);
    double mid;
    while(high_d- low_d>= epsilon){
        mid= (low_d+ high_d)/ 2;
        double mid_sq= mid* mid;
        if(mid_sq< n) low_d= mid;
        else high_d= mid;
    }
    return (low_d+ high_d)/ 2;
}

{{ select(12) }}

• "阶段1"的目标是寻找正整数n可能的正完全平方根
• "阶段2"的目标是如果正整数n没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根
• 代码check_int=(longlong)(result+0.5)是检查因浮点误差是否为正完全平方根
• 阶段2的二分法中high_d-low_d>=epsilon不能用于浮点数比较，会进入死循环

13. 硬币找零问题中要求找给客户最少的硬币。coins存储可用硬币规格，单位为角，假设规格都小于10角，且一定有1角规格。amount为要找零的金额，约定必须为1角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为0。下面是其实现代码，相关说法正确的是()。

int find_coins(const vector<int>& coins, int amount){
    sort(coins.begin(), coins.end(), greater<int>());
    int n= coins.size();
    for(int i= 0; i< n;++i){
        int coin= coins[i];
        int num= amount/ coin;
        result[i]= num;
        amount-= num* coin;
        if(amount== 0) break;
    }
    cout<<"找零方案如下:"<<endl;
    for(int i= 0; i< n;++i){
        cout<< sorted_coins[i]<<"角需要"<< result[i]<<"枚"<<endl;
    }
    return 0;
}

{{ select(13) }}

• 上述代码采用贪心算法实现
• 针对本题具体要求，上述代码总能找到最优解
• 上述代码采用枚举算法
• 上述代码采用分治算法

14. 关于下述C++代码的快速排序算法，说法错误的是()。

int randomPartition(std::vector<int>& arr, int low, int high){
    int random= low+ rand()%(high- low+ 1);
    std::swap(arr[random],arr[high]);
    int pivot= arr[high];
    int i= low-1;
    for(int j= low; j< high; j++){
        if(arr[j]<= pivot){
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i+1], arr[high]);
    return i+1;
}

void quickSort(std::vector<int>& arr, int low, int high){
    if(low< high){
        int pi= randomPartition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

{{ select(14) }}

• 在randomPartition函数中，变量i的作用是记录大于基准值的元素的边界
• randomPartition函数随机选择基准值，可以避免输入数据特定模式导致的最坏情况下时间复杂度O(n^2)
• 快速排序平均时间复杂度是O(n log n)
• 快速排序是稳定排序算法

15. 小杨编写了一个如下的高精度除法函数，则横线上应填写的代码为()。

pair<BigInt, BigInt> div(BigInt a, BigInt b){
    BigInt q,r;
    if(compare(a,b)<0){
        q.len=1; q.d[0]=0; r=a;
        return make_pair(q,r);
    }
    r.len= b.len;
    for(int i= a.len-1; i>= a.len-b.len; i--){
        r.d[i-(a.len-b.len)]= a.d[i];
    }
    for(int i= a.len-b.len; i>=0; i--){
        if(r.len>1|| r.d[0]!=0){
            for(int j= r.len; j>0; j--){
                r.d[j]= r.d[j-1];
            }
        } else{
            ______
        }
        while(compare(r,b)>=0){
            r= sub(r,b);
            q.d[i]++;
        }
    }
    return make_pair(q,r);
}

{{ select(15) }}

• r.d[0]= a.d[i]; r.len++;
• r.d[i]= a.d[i]; r.len++;
• r.d[i]= a.d[i]; r.len=1;
• r.d[0]= a.d[i]; r.len=1;

判断题整理结果（共10题）

1. 下面C++代码是用欧几里得算法(辗转相除法)求两个正整数的最大公约数，a大于b还是小于b都适用。

int gcd(int a,int b){
    while(b){
        int temp= b;
        b=a%b;
        a= temp;
    }
    return a;
}

{{ select(16) }}

• √
• ×

2. 下面的C++代码用于输出每个数对应的质因数列表，输出形如:{5:[5], 6:[2,3], 7:[7],8:[2,2,2]}。

int main(){
    int n, m;
    cin>>n>>m;
    if(n>m) swap(n,m);
    map<int, vector<int>> prime_factor;
    for(int i=n; i<=m;++i){
        int j=2,k=i;
        while(k!=1){
            if(k%j==0){
                prime_factor[i].push_back(j);
                k/=j;
            } else{
                ++j;
            }
        }
    }
    for(auto& p: prime_factor){
        cout<<p.first<<":";
        for(int v: p.second) cout<<v<<" ";
        cout<<endl;
    }
    return 0;
}

{{ select(17) }}

• √
• ×

3. 下面的C++代码实现归并排序。代码在执行时，将输出一次HERE字符串，因为merge()函数仅被调用一次。

void merge(std::vector<int>& arr, int left, int mid, int right){
    std::vector<int> temp(right-left+1);
    int i=left, j=mid+1, k=0;
    while(i<=mid && j<=right){
        if(arr[i]<=arr[j]) temp[k++]=arr[i++];
        else temp[k++]=arr[j++];
    }
    while(i<=mid) temp[k++]=arr[i++];
    while(j<=right) temp[k++]=arr[j++];
    for(int p=0; p<k; ++p) arr[left+p]=temp[p];
}

{{ select(18) }}

• √
• ×

4. 归并排序的最好、最坏和平均时间复杂度均为O(n log n)。

{{ select(19) }}

• √
• ×

5. 查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为g的单词，他首先翻到字典约一半的页数，发现该页的首字母是m，由于字母表中g位于m之前，所以排除字典后半部分，查找范围缩小到前半部分;不断重复上述步骤，直至找到首字母为g的页码。这种查字典的一系列操作可看作二分查找。

{{ select(20) }}

• √
• ×

6. 求解下图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图(如距离不能为负值)单源最短路径的算法。从该算法的描述可以看出，Dijkstra算法是贪心算法。

{{ select(21) }}

• √
• ×

7. 分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。

{{ select(22) }}

• √
• ×

8. 函数puzzle定义如下，则调用puzzle(7)程序会无限递归。

{{ select(23) }}

• √
• ×

9. 如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为O(n)。

vector<int> linear_sieve(int n){
    vector<int> primes;
    vector<bool> is_prime(n+1, true);
    for(int i=2; i<=n; ++i){
        if(is_prime[i]) primes.push_back(i);
        for(int j=0; j<primes.size() && i*primes[j]<=n; ++j){
            is_prime[i*primes[j]]=false;
            if(i%primes[j]==0) break;
        }
    }
    return primes;
}

{{ select(24) }}

• √
• ×

10. 下面C++代码实现将Hello写入data.txt。

ofstream out("data.txt");
out<<"Hello";
out.close();

{{ select(25) }}

• √
• ×

注：根据原始文档，选择题共15题，判断题共10题，合计25题。所有题目内容、代码格式和选项顺序均保持与原始文档完全一致，仅删除了选项前的ABCD字母标识。