题库 信息学奥赛题库 题目列表 #include <iostream> using na...
组合题
 #include <iostream>
using namespace std;
const int MAXN = 105;
int n, m, k, val[MAXN];
int temp[MAXN], cnt[MAXN];
void init() {
       cin >> n >> k;
       for (int i = 0; i < n; i++) cin >> val[i];
       int maximum = val[0];
       for (int i = 1; i < n; i++)
              if (val[i] > maximum) maximum = val[i];
       m = 1;
       while (maximum >= k) {
              maximum /= k;
              m++;
       }
}
void solve() {
       int base = 1;
       for (int i = 0; i < m; i++) {
              for (int j = 0; j < k; j++) cnt[j] = 0;
              for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
              for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
              for (int j = n - 1; j >= 0; j--) {
                     temp[cnt[val[j] / base % k] - 1] = val[j];
                     cnt[val[j] / base % k]--;
              }
              for (int j = 0; j < n; j++) val[j] = temp[j];
              base *= k;
       }
}
int main() {
       init();
       solve();
       for (int i = 0; i < n; i++) cout << val[i] << ' ';
       cout << endl;
       return 0;
}

假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在 int 表示范围内,完成下面的判断题和单选题:

第1题 判断

这是一个不稳定的排序算法。

A.
正确
B.
错误
第2题 判断

该算法的空间复杂度仅与n有关。

A.
正确
B.
错误
第3题 判断
该算法的时间复杂度为 𝑂(𝑚(𝑛+𝑘))O(m(n+k))。
A.
正确
B.
错误
第4题 单选

当输入为“5 3 98 26 91 37 46”时,程序第一次执行到第 36 行,val[]数组的内容依次为( )。

A.

91 26 46 37 98

B.

91 46 37 26 98

C.

98 26 46 91 37 

D.

91 37 46 98 26

第5题 单选
若 val[i]的最大值为 100,k 取(  )时算法运算次数最少。
A.

2

B.

3

C.

10

D.

不确

第6题 单选
当输入的 k 比 val[i]的最大值还大时,该算法退化为(  )算法。
A.

选择排序

B.

冒泡排序

C.

计数排序

D.

题目信息
阅读程序 2022年 初赛
-
正确率
0
评论
237
点击