2025年中国科学技术大学计算机考研复试机试真题

2025年中国科学技术大学计算机考研复试上机真题

历年中国科学技术大学计算机考研复试上机真题

历年中国科学技术大学计算机考研复试机试真题

更多学校完整题目开源地址：https://gitcode.com/u014339447/pgcode

百度一下pgcode 即可查看，输入 “学校名称” 即可筛选该校历年机试真题，包括真题、ac代码、解题思路、视频讲解。

数字转换为十六进制数-中国科学技术大学

题目描述

给定一个整数，编写一个算法将这个数转换为 $十六进制$ 数。

对于负整数，我们通常使用 $补码运算$ 方法。

答案字符串中的所有字母都应该是小写字符，并且除了 $0$ 本身之外，答案中不应该有任何前置零。

注意: 不允许使用任何由库提供的将数字直接转换或格式化为 $十六进制$ 的方法来解决这个问题。

输入格式

输入一个数 $num$，$-2^{31}\le num\le 2^{31}-1$

输出格式

输出结果

输入样例

26

输出样例

1a

#include <stdio.h>
int main() {
    int num;
    scanf("%d", &num);
    // 直接用printf的%x占位符（题目不让用，但自己测试可以）
    printf("%x\n", num); 
    return 0;
}

岛屿数量-中国科学技术大学

题目描述

给你一个由 ${}^{\prime }{1}^{\prime }$（陆地）和 ${}^{\prime }{0}^{\prime }$（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和 $/$ 或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

输入格式

给你一个 $m\times n$ 的二维网格

$m==\text{grid.length}$

$n==\text{grid}[i].\text{length}$

$1<=m,n<=300$

$\text{grid}[i][j]$ 的值为 ${}^{\prime }{0}^{\prime }$ 或 ${}^{\prime }{1}^{\prime }$

输出格式

计算网格中岛屿的数量

输入样例

4 5
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0

输出样例

1

#include <iostream>
using namespace std;

// 最大格子数 Pre-allocated
const int MAXN = 305;

// 全局数组：0 表示未访问，1 表示已访问
int vist[MAXN][MAXN];

// 输入矩阵
int a[MAXN][MAXN];

// 实际矩阵大小
int m = 0, n = 0;

// 四个方向：上、下、左、右
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// 深度优先遍历，统计并标记一个连通分量
void dfs(int x, int y) {
    // 越界或已访问则返回
    if (x < 0 || x >= m || y < 0 || y >= n) return;
    if (vist[x][y]) return;
    // 仅对值为 1 的格子进行遍历
    if (a[x][y] != 1) return;

    // 标记已访问
    vist[x][y] = 1;

    // 向四个方向继续 DFS
    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        dfs(nx, ny);
    }
}

int main() {
    // 输入矩阵大小
    if (!(cin >> m >> n)) return 0;

    // 读取矩阵数据并初始化 vist
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
            vist[i][j] = 0;
        }
    }

    int ans = 0; // 连通分量计数

    // 遍历矩阵，遇到未访问且值为 1 的格子即开启一个 DFS
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!vist[i][j] && a[i][j] == 1) {
                dfs(i, j);
                ++ans;
            }
        }
    }

    cout << ans;
    return 0;
}

最长连续递增序列-中国科学技术大学

题目描述

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列可以由两个下标 $l$ 和 $r$ （$l<r$）确定，如果对于每个 $l\le i<r$，都有 $nums[i]<nums[i+1]$ ，那么子序列 $[nums[l],nums[l+1],...,nums[r-1],nums[r]]$ 就是连续递增子序列。

输入格式

第一行输入一个整数 $n$ 表示数组的长度

第二行输入 $n$ 个数 $nums[i]$

$1\le n\le 10^4$

$-10^9\le nums[i]\le 10^9$

输出格式

输出最长连续递增子序列长度

输入样例

5
1 3 5 4 7

输出样例

3

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i<n; i++){
        cin >> a[i];
    }
    int b[n];
    for(int i = 0; i<n; i++){
        b[i] = 1;
    }
    if(n == 1){
        cout << 1;
    }
    else{
        for(int i  = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                if(a[j]>a[j-1]){
                    b[i] = max(b[i],j-i+1);
                }
                else{
                    j = n;
                }

             }
        }    

        int m = 0;
        for(int i = 0; i<n; i++){
            if(b[i] > m){
                m = b[i];
            }
        }
        cout << m;
    }
    return 0;
}

让字符串成为回文串的最少插入次数-中国科学技术大学

题目描述

给你一个字符串 $ s $ ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 $ s $ 成为回文串的 最少操作次数 。

回文串是正读和反读都相同的字符串。

输入格式

有多组测试数据

$ 1 \leq s.length \leq 500 $

$ s $ 中所有字符都是小写字母。

输出格式

如题

输入样例

zzazz
mbadm

输出样例

0
2

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int least_insert(string str);
int LPS(vector<vector<int>>& dp,int i,int j, vector<vector<int>>& record, string& str);
int main(){
	string str;
    while(getline(cin, str)){
        cout << least_insert(str) << endl;
    }
	return 0;
}

int least_insert(string str){
	vector<vector<int>> dp(str.size(), vector<int>(str.size(), 1));
	vector<vector<int>> record(str.size(), vector<int>(str.size(), 0));
	for(int i = 0; i < str.size(); i++){
		record[i][i] = 1;
        dp[i][i] = 1;
	}for(int i = 0; i < str.size() - 1; i++){
        record[i][i + 1] = 1;
        if(str[i] == str[i + 1]){
            dp[i][i + 1] = 2;
        }else{
            dp[i][i + 1] = 1;
        }
    }return str.size() - LPS(dp, 0, str.size() - 1, record, str);
}
int LPS(vector<vector<int>>& dp,int i,int j, vector<vector<int>>& record, string& str){
	if(record[i][j] == 1){
		return dp[i][j];
	}else{
		if(str[i] == str[j]){
			record[i][j] == 1;
			return 2 + LPS(dp, i + 1, j - 1, record, str);
		}else{
			record[i][j] == 1;
			return max(LPS(dp, i + 1, j, record, str), LPS(dp, i, j - 1, record, str));
		}
	}
}