万卷网 > 题目详情
题型:组合题
#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]++; 30         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).

当输入为“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

(2).

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

A.正确 B.错误
(3).

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

A.正确 B.错误
(4).

当输入的 k 比 val[i]的最大值还大时,该算法退化为( )算法。

A.

选择排序

B.

冒泡排序

C.

计数排序

D.

桶排序

(5).

若 val[i]的最大值为 100,k 取( )时算法运算次数最少。

A.

2

B.

3

C.

10

D.

不确定

(6).

该算法的时间复杂度为 O(m(n + k))。( )

A.正确 B.错误
更新时间:2022-12-06 14:30:10 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级

相似题推荐

简答题

T4员工招聘

2026-04-17
简答题

T1社团招新

2026-04-17
简答题

T2道路修复

2026-04-17
简答题

T3谐音替换

2026-04-16
单选题

对一个大小为16(下标0-15)的数组构建满线段树,查询区间[3,11]时,最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)?

A.

7

B.

8

C.

9

D.

10

2025-10-17
公众号
客服 反馈
顶部