计算机相关知识题库 - 第28页

第541题

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
    if (l > r)
        return 0;
    int min = maxn, mink;
    for (int i = l; i <= r; ++i) {
        if (min > a[i]) {
            min = a[i];
            mink = i;
        }
    }
    int lres = f(l, mink - 1, depth + 1);
    int rres = f(mink + 1, r, depth + 1);
    return lres + rres + depth * b[mink];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    cout << f(0, n - 1, 1) << endl;
    return 0;
}

当 n=100 时，最好情况下，与第 12 行的比较运算执行的次数最接近的是：( )

A. 100 B. 6 C. 5000 D. 600

第542题

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
    if (l > r)
        return 0;
    int min = maxn, mink;
    for (int i = l; i <= r; ++i) {
        if (min > a[i]) {
            min = a[i];
            mink = i;
        }
    }
    int lres = f(l, mink - 1, depth + 1);
    int rres = f(mink + 1, r, depth + 1);
    return lres + rres + depth * b[mink];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    cout << f(0, n - 1, 1) << endl;
    return 0;
}

当 n=10 时，若 b 数组满足，对于任意0≤i

A. 386 B. 383 C. 384 D. 385

第543题

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
    if (l > r)
        return 0;
    int min = maxn, mink;
    for (int i = l; i <= r; ++i) {
        if (min > a[i]) {
            min = a[i];
            mink = i;
        }
    }
    int lres = f(l, mink - 1, depth + 1);
    int rres = f(mink + 1, r, depth + 1);
    return lres + rres + depth * b[mink];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    cout << f(0, n - 1, 1) << endl;
    return 0;
}

当 n=100 时，若 b 数组满足，对于任意0≤i

A. 582 B. 580 C. 579 D. 581

第544题

（矩阵变换）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：数字 0 变成矩阵，数字 1 变成矩阵。最初该矩阵只有一个元素 0，变幻 n 次后，矩阵会变成什么样？

例如，矩阵最初为：[0]；矩阵变幻一次后：；矩阵变幻 2 次后：。

输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如 (11)₂<<2=(1100)₂。

而 ^ 表示二进制异或运算符，它将两个运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0，反之为 1。

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;

int res[max_size][max_size];

void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}

int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

① 处应填（）

A. n % 2 B. 0 C. t D. 1

第545题

（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，对 n 对 10000 以内的整数，从小到大排序。

例如有三对整数（3，4）、（2，4）、（3，3），那么排序之后应该是（2，4）、（3，3）、（3，4）。

输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关键字。

数据范围≤n≤10⁷,1≤a[i],b[i]≤10⁴。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord_____ 存储第二关键字排序的结果，数组 res_____ 存储双关键字排序的结果。

试补全程序

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;

int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < maxs; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);

    return 0;
}

① 处应填（）

A. ++cnt[i] B. ++cnt[b[i]] C. ++cnt[a[i]] D. ++cnt[a[i]*maxs+b[j]]

第546题

若有定义 int a = 7, float x = 2.5, y = 4.7;，则表达式 x + a % 3 * (int) (x + y) % 2 的值是（）

A. 0.000000 B. 2.750000 C. 2.500000 D. 3.500000

第547题

下列属于图像文件格式的（）

A. WMV B. MPEG C. JPEG D. AVI

第548题

下面哪个选项是11 1011 1001 0111 和 01 0110 1110 1011进行逻辑或运算的结果( )。

A. 11 1111 1101 1111 B. 11 1111 1111 1101 C. 10 1111 1111 1111 D. 11 1111 1111 1111

第549题

编译器的作用是 ( )。

A. 将源程序重新组合 B. 将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言） C. 将低级语言翻译成高级语言 D. 将一种编程语言翻译成自然语言

第550题

设变量 x 为 float 型且已赋值，下列哪条语句能将 x 中的数值保留到小数点后两位，并将第三位四舍五入 ( )。

A. x=(x∗100+0.5)/100.0 B. x=(int)(x∗100+0.5)/100.0 C. x=(x/100+0.5)∗100.0 D. x=x∗100+0.5/100.0

第551题

由数字 1, 1, 2, 4, 8, 8组成的不同的 4 位数的个数是 ( )。

A. 104 B. 102 C. 98 D. 100

第552题

排序的算法很多，若按排序的稳定性和不稳定性分裂，下面算法中 ( ) 是不稳定排序。

A. 冒泡排序 B. 直接插入排序 C. 快速排序 D. 归并排序

第553题

G 是一个非连通无向图（没有重边和自环），共有 28 条边，则该图至少有 ( )。

A. 10 B. 9 C. 11 D. 8

第554题

一些数字可以颠倒过来看，例如 0、1、8 颠倒过来还是本身，6 颠倒过来是 9，9 颠倒过来看还是 6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如 106 颠倒过来是 901。假设某个城市的车牌只由 5 位数字组成，每一位都可以取 0 到 9。请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的 5 位数能被 3 整除 ( )。

A. 40 B. 25 C. 30 D. 20

第555题

一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，共有 4 人语文、数学都是满分，那么这个班至少有一门满分的同学有多少人 ( )。

A. 23 B. 21 C. 20 D. 22

第556题

设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，请问在归并算法中，在最坏情况下至少要做多少次比较( )。

A. n^2 B. nlogn C. 2n D. 2n−1

第557题

以下哪个结构可以用来存图 ( )。

A. 栈 B. 二叉树 C. 队列 D. 邻接矩阵

第558题

以下哪些算法不属于贪心算法 ( )。

A. Dijkstra 算法 B. Floyd 算法 C. Prim 算法 D. Kruskal 算法

第559题

有一个等比数列，共有奇数项，其中第一项和最后一项分别是 2 和 118098，中间一项是 486，请问以下那个数是可能的公比 ( )。

A. 5 B. 3 C. 4 D. 2

第560题

由正实数构成的数字三角形排列如图所示，第一行为数字 a_1,1，第二行的数从左到右依次为 a_2,1、 a_2,2，第 n 行的数为 a_n,1、a_n,2...a_n,n。从 a_1,1 开始，每一行的数a_i,j 只有两条边可以分别通向下一行的两个数 a_i+1,j 和 a_i+1,j+1。用动态规划算法找出一条从 a_1,1 向下通到 a_n,1、 a_n,2...a_n,n 中的某个路径，是的该路径上的数之和最大。

令 C[i][j]是从 a_1,1 到 a_i,j的路径上的数值，并且 C[i][0] = C[0][j] = 0，则 C[i][j] = ( )

A. max(C[i−1][j−1],C[i−1][j])+ai,j B. C[i−1][j−1]+C[i−1][j] C. max(C[i−1][j−1],C[i−1][j])+1 D. max(C[i][j−1],C[i−1][j])+ai,j

全部知识点

知识点标签

训练

全部知识点

知识点标签