在线预览（题目节选）
1
选择
考虑如下 C 语言代码段，假设 n 为正整数且远大于 1。请分析该算法的时间复杂度，并选出正确的选项。
void func(int n) {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
printf(".");
}
}
}
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(2^n)
2
选择
某数据结构课程中，老师展示了两种不同的存储方案。方案一采用顺序存储结构，将数据元素依次存放在地址连续的内存单元中；方案二采用链式存储结构，通过指针链接离散分布的节点。已知该数据结构的逻辑结构为树形结构（如二叉树）。关于这两种方案与逻辑结构的关系，下列叙述正确的是：
A. 只有方案一能正确表示树形逻辑结构，因为顺序存储天然具备层次性
B. 只有方案二能正确表示树形逻辑结构，因为链式存储可以灵活指向任意子节点
C. 两种方案均可实现树形逻辑结构，且逻辑结构的定义不依赖于具体的存储方式
D. 方案一无法实现非线性逻辑结构，必须转换为线性序列后才能存储
3
选择
考虑如下 C 语言代码段，假设 n 为正整数且远大于 1。请分析该算法的时间复杂度，并选出正确的选项。
void func(int n) {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n / i; j++) {
printf("*");
}
}
}
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
4
选择
考虑如下 C 语言代码段，假设 n 为正整数且远大于 1。请分析该算法中内层语句 `count++` 的总执行次数 T(n) 的渐近阶（Big-O），并选出正确选项。
void func(int n) {
int i, j;
int count = 0;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j = j * 2) {
count++;
}
}
}
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
5
填空
某数据集合的逻辑结构被描述为一个完全二叉树。若采用顺序存储结构（即数组）实现该逻辑结构，设根节点存储在数组索引为1的位置，则对于任意非叶节点 i（i≥1），其左子节点的存储位置可由公式 ______ 确定。
6
填空
考虑如下 C 语言代码段，假设 n 为正整数且远大于 1。请分析该算法中内层语句 `count++` 的总执行次数 T(n) 的渐近阶（Big-O），并填空。
void func(int n) {
int i, j, count = 0;
for (i = 1; i <= n; i = i * 2) {
for (j = 1; j <= i; j++) {
count++;
}
}
}
该算法的时间复杂度为 O(____)。
7
填空
考虑如下 C 语言代码段，假设 n 为正整数且远大于 1。请分析该算法中语句 `sum += i * j;` 的总执行次数 T(n) 的渐近阶（Big-O），并填空。
void calc(int n) {
int sum = 0;
for (int i = 2; i <= n; i *= 2) {
for (int j = 1; j <= i; j++) {
sum += i * j;
}
}
}
该算法的时间复杂度为 O(____)。
8
选择
考虑如下 C 语言代码段，假设 n 为正整数且远大于 1。请分析该算法中内层语句 `x = x + 1;` 的总执行次数 T(n) 的渐近阶（Big-O），并选出正确选项。
void calc(int n) {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j < i; j = j * 2) {
x = x + 1;
}
}
}
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
9
选择
考虑如下 C 语言代码段，假设 n 为正整数且远大于 1。请分析该算法中内层语句 `count++;` 的总执行次数 T(n) 的渐近阶（Big-O），并选出正确的选项。
void calc(int n) {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n / i; j++) {
count++;
}
}
}
A. O(n)
B. O(n log n)
C. O(n^(3/2))
D. O(n^2)
10
计算
设 n 为正整数且远大于 1。考虑如下 C 语言代码段：
int T(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
count++;
}
}
return count;
}
请计算该算法中语句 `count++` 的总执行次数 T(n) 的精确数学表达式（使用求和符号表示），并据此判断其渐近时间复杂度 Big-O。
完整版式、参考答案与解析请下载 PDF 查看。