1.
唯⼀分解定理描述的内容是 ( ) ?
2.
贪⼼算法的核⼼思想是 ( ) ?
3.
下⾯的 C++代码⽚段⽤于计算阶乘 。请在横线处填⼊（ ） ，实现正确的阶乘计算。
1 int factorial(int n) {
2 if (n == 0 || n == 1) {
3 return 1;
4 } else {
5 // 在此处填入代码
6 }
7 }
4.
下⾯的代码⽚段⽤于在双向链表中删除⼀个节点 。请在横线处填⼊（ ） ，使其能正确实现相应功能。
1 void deleteNode(DoublyListNode*& head, int value) {
2 DoublyListNode* current = head;
3 while (current != nullptr && current->val != value) {
4 current = current->next;
5 }
6 if (current != nullptr) {
7 if (current->prev != nullptr) {
8 ____________________________________ // 在此处填入代码
9 } else {
10 head = current->next;
11 }
12 if (current->next != nullptr) {
13 current->next->prev = current->prev;
14 }
15 delete current;
16 }
17 }
5.
辗转相除法也被称为 ( )
6.
下⾯的代码⽚段⽤于计算斐波那契数列 。该代码的时间复杂度是 ( ) ?
1 Int fibonacci(int n) {
2 if (n <= 1) {
3 return n;
4 } else {
5 return fibonacci(n - 1) + fibonacci(n - 2);
6 }
7 }
7.
下⾯的代码⽚段⽤于将两个⾼精度整数进⾏相加 。请在横线处填⼊（ ） ，使其能正确实现相应功能。
1 string add(string num1, string num2) {
2 string result;
3 int carry = 0;
4 int i = num1.size() - 1, j = num2.size() - 1;
5 while (i >= 0 || j >= 0 || carry) {
6 int x = (i >= 0) ? num1[i--] - '0 ' : 0;
7 int y = (j >= 0) ? num2[j--] - '0 ' : 0;
8 int sum = x + y + carry;
9 carry = sum / 10;
10
11 }
12 return result;
13 }
8.
给定序列：1 ，3 ，6 ，9， 17 ，31 ，39 ，52 ，61 ，79 ，81 ，90 ，96 。使⽤以下代码进⾏⼆分查找查找元素82时 ，需要循环多少次， 即最后输出的times值为（ ） 。
1 int binarySearch(const std::vector<int>& arr, int target) {
2 int left = 0;
3 int right = arr.size() - 1;
4 int times = 0;
5 while (left <= right) {
6 times ++;
7 int mid = left + (right - left) / 2;
8 if (arr[mid] == target) {
9 cout << times << endl;
10 return mid;
11 } else if (arr[mid] < target) {
12 left = mid + 1;
13 } else {
14 right = mid - 1;
15 }
16 }
17 cout << times << endl;
18 return -1;
19 }
9.
下⾯的代码⽚段⽤于判断⼀个正整数是否为素数 。请对以下代码进⾏修改 ，使其能正确实现相应功能 。 ( )
1 bool isPrime(int num) {
2 if (num < 2) {
3 return false;
4 }
5 for (int i = 2; i * i < num; ++i) {
6 if (num % i == 0) {
7 return false;
8 }
9 }
10 return true;
11 }
10.
在埃拉托斯特尼筛法中 ，要筛选出不⼤于n的所有素数 ，最外层循环应该遍历什么范围 ( ) ?
1 vector<int> sieveOf Eratosthenes(int n) {
2 std::vector<bool> isPrime(n + 1, true);
3 std::vector<int> primes;
4 {
5 if (isPrime[i]) {
6 primes.push_back(i);
7 for (int j = i * i; j <= n; j += i) {
8 isPrime[j] = false;
9 }
10 }
11 }
12 for (int i = sqrt(n) + 1; i <= n; ++i) {
13 if (isPrime[i]) {
14 primes.push_back(i);
15 }
16 }
17 return primes;
18 }
11.
素数的线性筛法时间复杂度为（ ） 。
12.
归并排序的基本思想是（ ） 。
13.
在快速排序中 ，选择的主元素（pivot）会影响算法的（ ） 。
14.
递归函数在调⽤⾃⾝时 ，必须满⾜（ ） ， 以避免⽆限递归？
15.
假设给定链表为: 1→3→5→7→nullptr ，若调⽤searchValue(head, 5) ，函数返回值为（ ） 。
1 int searchValue(ListNode* head, int target) {
2 while (head != nullptr) {
3 if (head->val == target) {
4 return 1;
5 }
6 head = head->next;
7 }
8 return 0;
9 }
1.
辗转相除法⽤于求两个整数的最⼤公约数。
2.
插⼊排序的时间复杂度是O（NlogN） 。
3.
⼆分查找要求被搜索的序列是有序的 ，否则⽆法保证正确性。
4.
使⽤贪⼼算法解决问题时 ，每⼀步的局部最优解⼀定会导致全局最优解。
5.
分治算法的核⼼思想是将⼀个⼤问题分解成多个相同或相似的⼦问题进⾏解决 ，最后合并得到原问题的解。
6.
分治算法的典型应⽤之⼀是归并排序 ，其时间复杂度为O（NlogN） 。
7.
素数表的埃⽒筛法和线性筛法的时间复杂度都是O（NloglogN） 。
8.
贪⼼算法是⼀种可以应⽤于所有问题的通⽤解决⽅案。
9.
单链表和双链表都可以在常数时间内实现在链表头部插⼊或删除节点的操作。
10.
在C语⾔中 ，递归的实现⽅式通常会占⽤更多的栈空间 ，可能导致栈溢出。
1.
试题名称：成绩排序
3.1.1 问题描述
有N名同学，每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序：
1. 比较总分，高者靠前；
2. 如果总分相同，则比较语文和数学两科总分，高者靠前；
3. 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
4. 如果仍相同，则二人并列。
你需要输出每位同学的排名，如遇x人并列，则他们排名相同，并留空后面的x-1个名次。例如，有3名同学并列第1，则后一名同学自动成为第4名。
3.1.2 输入描述
第一行一个整数N，表示同学的人数。
接下来N行，每行三个非负整数ci,mi,ei分别表示该名同学的语文、数学、英语成绩。
保证o≤ci,mi,ei≤150 。
3.1.3 输出描述
输出N行，按输入同学的顺序，输出他们的排名。
注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名
3.1.4 特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
3.1.5 样例输入 1
3.1.6 样例输出 1
3.1.7 数据规模
对于30的测试点，保证N≤100 ，且所有同学的总分各不相同。
对于所有测试点，保证2≤N≤104 。
2.
试题名称： B-smooth 数
3.2.1 题面描述
小杨同学想寻找一种名为 B-smooth 数的正整数。
如果一个正整数的最大质因子不超过B，则该正整数为 B-smooth 数。
小杨同学想知道，对于给定的n和B，有多少个不超过n的B-smooth 数。
3.2.2 输入格式
第一行包含两个正整数n, B，含义如题面所示。
3.2.3 输出格式
输出一个非负整数，表示不超过n的B-smooth 数的数量。
3.2.4 样例1
3.2.5 样例解释
在不超过10的正整数中，3-smooth 数有{1,2,3,4,6,8,9} ，共7个。
3.2.6 数据范围
对于全部数据，保证有1≤n≤106 ，1≤B≤106 。