计算机考试题库，免费真题

第1201题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

①处应填（）

A. a.x != b.x ? a.x < b.x : a.id < b.id B. a.x != b.x ? a.x < b.x : a.y < b.y C. equals(a,b) ? a.id < b.id : a.x < b.x D. equals(a,b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

第1202题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

②处应填（）

A. i == 0 || cmp(A[i], A[i - 1]) B. t == 0 || equals(A[i], A[t - 1]) C. i == 0 || !cmp(A[i], A[i - 1]) D. t == 0 || !equals(A[i], A[t - 1])

第1203题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

③处应填（）

A. b - (b - a) / 2 + 1 B. (a + b + 1) >> 1 C. (a + b) >> 1 D. a + (b - a + 1) / 2

第1204题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

④处应填（）

A. !cmp(A[mid], p) B. cmp(A[mid], p) C. cmp(p, A[mid]) D. !cmp(p, A[mid])

第1205题

（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

#include <stdio. h>
struct point {
    int x, y, id;
};
int equals(struct point a, struct point b) {
    return a.x == b.x && a.y == b.y;
}
int cmp(struct point a, struct point b) {
    return ①;
}
void sort(struct point A[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (cmp(A[j], A[j - 1])) {
                struct point t = A[j];
                A[j] = A[j - 1];
                A[j - 1] = t;
            }
}
int unique(struct point A[], int n) {
    int t = 0;
    for(int i = 0; i < n; i++)
        if (②)
            A[t++] = A[i];
    return t;
}
int binary_search(struct point А[], int n, int x, int y) {
    struct point p;
    p.x = x;
    р.y = y;
    p.id = n;
    int a = 0，b = n - 1;
    while (a < b) {
        int mid = ③;
        if (④)
            a = mid + 1;
        else
            b = mid;
    }
    return equals(A[a], р);
}
#define MAXN 1000
struct point A[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i].x, &A[i].y);
        A[i].id = i;
    }
    sort(A, n);
    n = unique(A, n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
                ans++;
            }
    printf("%d\n", ans);
    return 0;
}

⑤处应填（）

A. A[i].x == A[j].x B. A[i].id < A[j].id C. A[i].x == A[j].x && A[i].id < A[j].id D. A[i].x < A[j].x && A[i].y < A[j].y

第1206题

在Linux系统终端中，用于列出当前目录下所含的文件和子目录的命令为（）。

A. ls B. cd C. cp D. all

第1207题

二进制数00101010₂和00010110₂的和为（）。

A. 00111100 B. 01000000 C. 00111100 D. 01000010

第1208题

在程序运行过程中，如果递归调用的层数过多，可能会由于（）引发错误。

A. 系统分配的栈空间溢出 B. 系统分配的队列空间溢出 C. 系统分配的链表空间溢出 D. 系统分配的堆空间溢出

第1209题

以下排序方法中，（）是不稳定的。

A. 插入排序 B. 冒泡排序 C. 堆排序 D. 归并排序

第1210题

以比较为基本运算，对于2n个数，同时找到最大值和最小值，最坏情况下需要的最小的比较次数为（）。

A. 4n−2 B. 3n+1 C. 3n−2 D. 2n+1

第1211题

现有一个地址区间为0~10的哈希表，对于出现冲突情况，会往后找第一个空的地址存储（到10冲突了就从0开始往后），现在要依次存储（0,1,2,3,4,5,6,7），哈希函数为h(x)=x²mod 11。请问7存储在哈希表哪个地址中（）。

A. 5 B. 6 C. 7 D. 8

第1212题

G是一个非连通简单无向图（没有自环和重边），共有36条边，则该图至少有（）个点。

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

第1213题

令根结点的高度为1，则一棵含有2021个结点的二叉树的高度至少为（）。

A. 10 B. 11 C. 12 D. 2021

第1214题

前序遍历和中序遍历相同的二叉树为且仅为（）。

A. 只有1个点的二叉树 B. 根结点没有左子树的二叉树 C. 非叶子结点只有左子树的二叉树 D. 非叶子结点只有右子树的二叉树

第1215题

定义一种字符串操作为交换相邻两个字符。将“DACFEB”变为 “ABCDEF”最少需要（）次上述操作。

A. 7 B. 8 C. 9 D. 6

第1216题

有如下递归代码

solve(t, n)
    if t = 1 return 1
    else return 5 * solve(t - 1, n) mod n

则solve(23, 23)的结果为（）。

A. 1 B. 7 C. 12 D. 22

第1217题

斐波那契数列的定义为：F₁=1,F₂=1,F_n=F_n-1+F_n-2(n>=3)。现在用如下程序来计算斐波那契数列的第n项，其时间复杂度为（）。

F(n):
    if n <= 2 return 1
    else return F(n - 1) + F(n - 2)

A. O(n) B. O(n^2) C. O(2^n) D. O(nlogn)

第1218题

有8个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（）种方案。

A. 36 B. 48 C. 54 D. 64

第1219题

设一个三位数均为1∼9之间的整数，若以a、b、c作为三角形的三条边可以构成等腰三角形（包括等边），则这样的n有（）个。

A. 81 B. 120 C. 165 D. 216

第1220题

有如下的有向图，节点为A,B,⋯,J，其中每条边的长度都标在图中。则节点A到节点J的最短路径长度为（）。

CSP-S1提高级初赛试卷[2021]

A. 16 B. 19 C. 20 D. 22

全部知识点

知识点标签

训练

全部知识点

知识点标签