外观
中兴
约 741 字大约 2 分钟
2025-02-27
中兴
单选题：2+3+2 应该是 多选题：2+3 编程题：2道
第一题：选择排序
题目描述
简单选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
现在需要得到序列第 i 趟排序后的结果（本题中采用每轮选取选出最小值的方式）。比如给定趟数 3 和序列 (45 88 48 40 21 73) 。根据选择排序的算法： 第一趟：21 88 48 40 45 73
第二趟：21 40 48 88 45 73
第三趟：21 40 45 88 48 73
由此可以得到第三趟的输出为 (21 40 45 88 48 73)。
输入描述：
输入包含多组，每组由两行组成：
第一行为正整数i，代表需要做的简单排序的趟数；
第二行为正整数序列，包含用空格隔开的多个值（i<=序列长度，序列长度最大为100）。 输出描述：
输出描述：
输出经过第i趟排序后的正整数序列（用空格分隔元素）。
代码实现
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
// 读取第一个输入：趟数 i
String line1 = scanner.nextLine();
if (line1 == null || line1.trim().isEmpty()) {
break;
}
int passes = Integer.parseInt(line1.trim());
// 读取第二个输入：待排序的序列
if (!scanner.hasNextLine()) {
break;
}
String line2 = scanner.nextLine();
if (line2 == null || line2.trim().isEmpty()) {
break;
}
String[] tokens = line2.trim().split("\\s+");
int[] arr = new int[tokens.length];
for (int i = 0; i < tokens.length; i++) {
arr[i] = Integer.parseInt(tokens[i]);
}
// 对序列进行选择排序的前 passes 趟
int n = arr.length;
for (int i = 0; i < passes && i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换当前元素和最小元素
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
// 输出第 i 趟排序后的序列
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i != arr.length - 1) {
System.out.print(" ");
}
}
System.out.println();
}
scanner.close();
}
}第二题：二叉树
题目描述
由数字 1~N 顺序构成的完全二叉树中，其中 1 是根结点。
求从根结点到指定数字对应结点的路径上的数字组成的数字字符串。
输入描述：
整数N，1 <= N <= 1000
输出描述：
从根结点到输入数字的路径结点上的数字组成的数字字符串，数字之间由单个空格间隔。
示例： 输入：5 输出：1 2 5
代码
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入的整数 N
int N = scanner.nextInt();
scanner.close();
// 用于存储路径上的节点
ArrayList<Integer> path = new ArrayList<>();
int current = N;
// 构建从目标节点到根节点的路径
while (current >= 1) {
path.add(current);
current /= 2;
}
// 逆序输出路径（从根节点到目标节点）
Collections.reverse(path);
for (int i = 0; i < path.size(); i++) {
System.out.print(path.get(i));
if (i != path.size() - 1) {
System.out.print(" ");
}
}
}
}