数据结构章节测试课后答案2024春

第一章测试

1.方法f1的时间复杂度是（ ）public int f1(int n) {int x = 0;while (n >= (x + 1) * (x + 1)) {x = x + 1;}return x;}
A:O(logn) B:O(n1/2) C:O(n) D:O(n2)
答案:B
2.方法f2的时间复杂度是（ ）public int f2(int n) {int i = 0;int sum = 0;while (sum < n) {sum += ++i;}return i;}
A:O(n1/2) B:O(n) C:O(nlogn) D:O(logn)
答案:A
3.方法f3的时间复杂度是（ ）public int f3(int n) {int x = 2;while (x < n / 2) {x = 2 * x;}return x;}
A:O(n2) B:O(logn) C:O(nlogn) D:O(n)
答案:B
4.方法f4的时间复杂度是（ ）public int f4(int n) {int count = 0;for (int k = 1; k <= n; k *= 2) {for (int j = 1; j <= n; j++) {count++;}}return count;}
A:O(nlogn) B:O(n2) C:O(n) D:O(logn)
答案:A
5.记问题的规模n=a.length，方法f5的时间复杂度是（ ）public void f5(int[] a, int x) {int j = a.length;for (int i = 0; i < a.length; i++) {if (x > a[i]) {j = i;break;}}for (int i = a.length; i > j; i--) {a[i] = a[i - 1];}a[j] = x;}
A:O(n) B:O(logn) C:O(n2) D:O(nlogn)
答案:A