gesp五级-2026年3月
欢迎参加本次编程理论考试，请认真作答以下题目。
1. 您的姓名：
2. 您的部门：
叶璐
夏政
陈凯
胡慧君
一、单选题（每题2分，共30分）
3. 关于单链表、双链表和循环链表，下列说法正确的是
在单链表中，若已知任意结点的指针，则可以在O(1)时间内删除该结点
循环链表中一定不存在空指针
在循环双链表中，尾结点的next指针一定为nullptr
在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身
4. 双向循环链表中要在结点p之前插入新结点s（均非空），以下指针操作正确的是
s-＞next = p; s-＞prev = p-＞prev; p-＞prev-＞next = s; p-＞prev = s
s-＞prev = p; s-＞next = p-＞next; p-＞next-＞prev = s; p-＞next = s
s-＞next = p; s-＞prev = nullptr; p-＞prev = s
p-＞prev = s; s-＞next = p; s-＞prev = p-＞prev; p-＞prev-＞next = s
5. 下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点，横线处应填
cur = cur->next
cur->next = del->next
del->next = cur->next
cur->next = nullptr
6. 对如下代码实现的欧几里得算法（辗转相除法），执行gcd(48, 18)得到的调用序列为
gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)
gcd(48,18) -> gcd(30,18) -> gcd(12,18)
gcd(48,18) -> gcd(18,30) -> gcd(30,6)
gcd(48,18) -> gcd(12,18) -> gcd(6,12)
7. 下面代码实现了欧拉（线性）筛，横线处应填写
j <= n
j < sqrt(n)
j < primes.size()
j < i
8. 埃氏筛中将内层循环从j = i*i开始而不是j = 2*i的主要原因是
因为2*i一定不是合数
i*i一定是质数
小于i*i的i的倍数已被更小质因子筛过
这样可以把时间复杂度降为O(n)
9. 下面程序的运行结果为
2
3
4
5
10. 在升序数组中查找第一个大于等于x的位置，下面循环中横线应填
r = mid
r = mid - 1
l = mid
l = mid + 1
11. 关于递归函数调用，下列说法错误的是
递归调用层次过深时，可能会耗尽栈空间导致栈溢出
尾递归函数可以通过编译器优化来避免栈溢出
所有递归函数都可以通过循环结构来改写，从而避免栈溢出
栈溢出发生时，程序会抛出异常并可以继续执行后续代码
12. 给定n根木头，第i根长度为a[i]。要切成不少于m段等长木段，求最大可能长度，则横线上应填写
l = mid + 1; r = mid - 1
l = mid - 1; r = mid + 1
l = mid + 1; r = mid
l = mid; r = mid + 1
13. 下面代码用分治求“最大连续子段和”，其时间复杂度为
O(n)
O(n log n)
O(n^2)
O(log n)
14. 游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。A组：A={12,35,67,89}，B组：B={20,45,55,78}，下面是归并合并函数的核心循环，横线处应填入
A[i] >= B[j]
A[i] <= B[j]
i >= j
i <= j
15. 有n位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为pivot的快速排序，请问此次排序的时间复杂度是
O(n)
O(n log n)
O(n^2)
O(1)
16. 下面关于排序算法的描述中，不正确的是
冒泡排序和插入排序都是稳定的排序算法
快速排序和归并排序都是不稳定的排序算法
冒泡排序和插入排序最好时间复杂度均为O(n)
归并排序在最好、最坏和平均三种情况的时间复杂度均为O(n log n)
17. 下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用int表示，则横线处应该填写
rem /= b
rem %= b
rem = b
rem = q
二、判断题（每题2分，共20分）
18. 有一个存储了n个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是O(1)，而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是O(1)
对
错
19. 若数组a已按升序排列，则下面代码可以正确实现“在a中查找第一个大于等于x的元素的位置”
对
错
20. 快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序
对
错
21. 若某算法满足递推式T(n) = 2T(n/2) + O(n)，则其时间复杂度为O(n log n)
对
错
22. 在一个数组中，如果两个元素a[i]和a[j]满足i < j且a[i] > a[j]，则a[i]和a[j]是一个逆序对。下面代码可以正确统计数组a区间[l,r]内的逆序对总数
对
错
23. 根据唯一分解定理，如果大于1的整数n不被任何不超过其平方根的质数整除，则n是质数
对
错
24. 假设数组a的值域范围是D
，以下程序的时间复杂度是O(nlogn +nlogD)
。
对
错
25. 若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解
对
错
26. 线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过“每个合数只被其最大质因子筛去”的策略，保证每个合数恰好被标记一次，从而实现O(n)的时间复杂度
对
错
27. 任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程
对
错
关闭
更多问卷
复制此问卷