2027年408真题数据结构篇

一、单项选择题

第01~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

01.

设 $n$n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。

x = 2;
while (x < n / 2) 
    x = 2 * x;

A. $O(\log ?n)$O(\log n)

B. $O\left(n\right)$O(n)

C. $O(n\log ?n)$O(n\log n)

D. $O\left(n^2\right)$O(n^2)

解答：

方法一：精确计算法

该过程主要代价为while循环，其中核心代码 $x=2?x$x=2*x 的代价为 $O\left(1\right)$O(1) ，需要计算while循环的迭代次数。

初始时有 $x=2=2^1$x = 2=2^1 ；

while循环第 1 次迭代后有 $x=2?2=2^{1+1}$x=2\cdot2=2^{1+1} ；

归纳得while循环第 $i$i 次迭代后有 $x=2^{i+1}$x=2^{i+1} ；

假设第 $k$k 次迭代后，恰有 $x=2^{k+1}$

如需高考志愿指导，可联系网站客服获取！助你成功率提升90%！

学员评价