2024西电机试算法题
时间：2025年3月16日22:26:00 start->
Problem 1
题目描述：输入两个数字m和n分别表示矩阵的行数和列数量。之后再输入m行n列的数字，表示初始矩阵。接着再对矩阵进行“归一化”操作。
归一化的操作如下：对于矩阵中每一个元素x，将元素转化为x‘=(x-min)/(max-min)。其中，max和min分别表示矩阵中所有元素的最大值和最小值。接着再对矩阵进行“镜像化”操作。“镜像化”操作即为将元素进行镜像反转。如下所示：
123 321
456 -》 654
789 987
输入格式：输入两个数字m和n，表示m行n列
输入m行n列的整数，表示矩阵。
输入数据保证1<=m，n<=10。
输出格式：输出经过处理之后的m行n列的矩阵。输出数据时，要求数据保留三位小数。
示例：输入数据：
2 2
0 2
2 0
输出：
1.000 0.000
0.000 1.000
解释：
原矩阵为
0 2
2 0
进行归一化之后，矩阵变为：
0 1
1 0
进行镜像化之后，矩阵变为：
1 0
0 1
以后输出时保证保留三位小数即可。
代码：如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<cstdio>
#include<vector>
#include<climits>
using namespace std;
int main(){
int m,n;
scanf("%d%d",&m,&n);
vector<vector<double>> nums(m,vector<double>(n,0));
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
scanf("%lf",&nums[i][j]);
}
}
double mx=INT_MIN,mn=INT_MAX;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
mx=max(mx,nums[i][j]);
mn=min(mn,nums[i][j]);
}
}
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
nums[i][j]=(nums[i][j]-mn)/(mx-mn);
}
}
for(int i=0;i<m/2;++i){
for(int j=0;j<n;++j){
swap(nums[i][j],nums[m-1-i][j]);
}
}
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
printf("%.3lf ",nums[i][j]);
}
printf("\n");
}
}
|
研梦答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<isotream>
#include<vector>
#include<iomanip>
#include<climits>
using namespace std;
int main(){
int row=0;
int column=0;
cin>>row>>column;
vector<vector<double>> matrix(row,vector<double>(column,0));
double max_value=INT_MAX;
double min_value=INT_MAX;
for(int i=0;i<row;++i){
for(int j=0;j<column;++j){
cin>>matrix[i][j];
max_value=max(max_value,matrix[i][j]);
min_value=min(min_value,matrix[i][j]);
}
}
for(int i=0;i<row;++i){
for(int j=0;j<column;++j){
matrix[i][j]=(matrix[i][j]-min_value)(max_value-min_value);
}
}
cout<<fixed<<setprecision(3);
for(int i=0;i<row;++i){
for(int j=column-1;j>=0;--j){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
|
Problem 2
题目描述：andy有m首待选择的歌曲，现在andy想要邀请一些朋友来帮自己给这些歌曲打分，所有的评委都有自己的编号，最终根据歌曲总得分一起选出n首最受欢迎的歌曲。
andy自己也是评委之一。在打分的过程中，andy也会有自己最爱的一首歌。在初步得到受欢迎的歌曲名单之后，会进行判断：
1.如果andy最喜欢的一首歌在列表之中，则将这首歌曲提到位置最靠前的位置。
2.如果andy最喜欢的一首歌不在列表之中，则将这首歌曲作为最受欢迎的歌单的最后一首。
输入格式：首先依次输入4个整数，分别是【待选择的歌曲数量】m、【最受欢迎的歌曲数量】n、【打分的评委的个数】num、【andy的编号】index。
之后输入num行，每行m+1个数字。第一个数字为整数类型，表示本评委的编号。之后的m个数字为浮点数类型，表示这个评委对每一首歌的评分。
输入保证出现的每个分数各不相同。
输出格式：输出n个数字，表示选择的是哪几首歌曲。
示例：如下
输入：
4 2 4 2
1 5.3 4.2 2.1 1.6
2 5.4 3.3 3.0 2.3
3 3.5 3.2 1.9 2.0
4 3.2 3.5 1.1 4.3
输出：
2
1
解释：一共有4首待选择的歌曲，需要选出2首最受欢迎的歌曲。一共有4位评委，andy的编号是2.
四首歌曲的总评分分别是：14.4 14.2 8.1 10.2，将所有歌曲进行初步排序，得到 14.4 14.2 10.2 8.1，andy最喜欢的歌曲是第二首歌曲，也就是总分为14.2的那个歌曲，本歌曲在歌单中，于是要将14.2放到数组的前2个位置的最前面。于是输出时，应该先输出第二首歌，再输出第一首歌。于是输出：
2
1
示例：如下
输入：
4 2 4 4
1 5.3 4.2 2.1 1.6
2 2.4 3.3 3.0 2.3
3 3.5 3.2 1.9 2.0
4 3.2 3.5 1.1 4.3
输出：
1
4
解释：
一共有4首带选择的歌曲，需要选出2首最受欢迎的歌曲。一共有4位评委，andy的编号是4.
四首歌曲的总评分分别是：14.4 14.2 8.1 10.2，将所有歌曲进行初步排序，得到：14.4 14.2 10.2 8.1。andy最喜欢的歌曲是第四首歌曲，也就是总分为10.2的那个歌曲，本歌曲不在歌单中，于是要将10.2放到数组的前2个位置的最后一个位置。于是输出时，应该先输出评分为14.4的歌曲，再输出评分为10.2的歌曲。于是输出：
1
4
代码：如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<cstdio>
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;
struct song{
int id;
double score;
};
bool cmp(song a,song b){
return a.socre>b.score;
}
int main(){
int m,n,num,index;
scanf("%d%d%d%d",&m,&n,&num,&index);
vector<song> songs(m);
for(int i=0;i<m;++i){
songs[i].id=i;
}
int andy_select;
for(int i=0;i<num;++i){
int person;
double cur;
double mx=INT_MIN;
int mx_id;
scanf("%d",&person);
for(int j=0;j<m;++j){
scanf("%lf",&cur);
songs[i]+=cur;
if(cur>mx){
mx=cur;
mx_id=j;
}
}
if(person==index){
andy_select=mx_id;
}
}
sort(songs.begin(),songs.end(),cmp);
int signal=-1;
for(int i=0;i<n;++i){
if(songs[i].id==mx_id){
signal=i;
}
}
if(signal!=-1){
swap(songs[0],songs[signal]);
for(int i=0;i<n;++i){
printf("%lf ",songs[i].score);
}
}else{
for(int i=0;i<n-1;++i){
printf("%lf ",songs[i].socre);
}
printf("lf",songs[mx_id].socre);
}
printf("\n");
return 0;
}
|
研梦答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<iostream>
#include<vector>
#include<algorithum>
#include<climits>
using namespace std;
class Song{
public:
int song_index;
double song_score;
};
class Compare{
public:
bool operator()(const Song&s1,const Song&s2) const{
return s1.song_score>s2.song_score;
}
};
// 看在songs的[left,right]区间之内能不能找到下表为target_index的歌曲
bool find(vecot<Song>&songs,int left,int right,int target){
for(int i=left;i<=right;++i){
if(songs[i].song_index==target_index){
return true;
}
}
return false;
}
int main(){
int song_num=0;
int select_song_num=0;
int person_num=0;
int andy_index=0;
cin>>song_num>>select_song_num>>person_num>>andy_index;
vector<double> score(song_num,0); // score[i] - 第i首歌曲的分数是score[i]
int favorite_index = -1; // andy最喜欢的歌曲
for(int i=;i<person_num;++i){
int index=;
cin>>index;
bool is_andy=(index==andy_index)?true:false;
int max_value=INT_MIN;
for(int j=;j<song_num;++j){
double temp_score=0;
cin>>temp_score;
score[j]+=temp_score;
if(is_andy&&temp_score>max_score){
max_score=temp_score;
favorite_index=j;
}
}
}
vector<song> songs;
for(int i=0;i<song_num;++i){
Song song;
song.song_index=i;
song.song_score=score[i];
songs.emplace_back(song);
}
sort(songs.begin(),songs.end(),Compare());
//输出
// 注意输出的时候，要输出【下标+1】，才是题目中说的【第多少首歌曲】
if(find(songs,0,select_song_num-1,favorite_index)){
//先存在于前select_song_num 首歌曲中
// 先输出最喜欢的。
cout<<facorite_index+1<<endl;
// 再输出其他的
for(int i=;i<select_song_num;++i){
if(songs[i].song_index==facotite_index){
continue;
}else{
cout<<songs[i].song_index+1<<endl;
}
}
}else{
// 不存在于前select_song_num 首歌曲中
// 先输出前select_song_num-1个
for(int i=0;i<select_song_num-1;++i){
cout<<songs[i].song_index+1<<endl;
}
// 再输出最喜欢的
cout<<favorite_index+1<<endl;
}
return 0;
}
|
Problem 3
题目描述：完成排序二叉树的创建。给定你如下的程序，补全函数的声明部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int key;
Node *left;
Node *right;
}Node,*BiTree;
void preorder(BiTree root);
int preHeight(BiTree root);
void insertNode(BiTree *root, int key);
int main(){
int n=0;
scanf("%d",&n);
Node *root=NULL;
for(int i=0;i<n;++i){
int key=0;
scanf("%d",&key);
insertNode(&root,key);
}
printf("%d\n",getHegiht(root));
preorder(root);
printf("\n");
return 0;
}
void preorder(Bitree root){
if(root==NULL){
return;
}
printf("%d ",root->key);
preorder(root->left);
preorder(root->right);
}
/*---
*/
在这里输入你的答案
/*---*/
--------
/*---*/
|
输入格式：输入一个整数类型的n表示节点数量。输入n个整数，分别表示依次插入的结点的值。
输入示例：
6
7 4 10 3 5 14
输出示例：
3
7 4 3 5 10 14
代码：如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int getHeight(BiTree root){
if(root==NULL){ // 空节点
return 0;
}
int height1=getHeight(root->left);
int height2=getHeight(root->right);
return max(heigh1,heigh2)+1;
}
void insertNode(BiTree root,int kye){
if(root==NULL){ // 根节点为空
root=new Node();
root->key=key;
return;
}
if(key<root->key){
insert((root->left),key);
}
else if(key>root->key){
insert((root->right),key);
}else{
return; // 不重复
}
}
|
Problem 4
题目描述：编写程序，完成中缀表达式到后缀表达式的转换。
输入格式：输入一个字符串，代表一个中缀表达式。表达式中没有空格。
输出格式：输出该中缀表达式的后缀表达式格式。不同符号之间，使用空格分隔。
输入示例：81+42-63*25
输出示例：81 42 + 63 25 * -
代码：如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(){
string str;
stack opStack;
stack numStack;
cin>>str;
for(int i=0;i<str.size();++i){
if(isalpha(str[i])){
char cur=str[i];
if(!opStack.empty()&&opStack.top())
}
}
}
|
研梦答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<iostream>
#include<string>
#inlcude<stack>
using namespace std;
// 将str的[left,right]部分转换为数字
int getNumber(const string&str,int left,int right){
int len=right-left+1;
return stoi(str.substr(left,len));
}
// 将str的[num_begin_pos,end_pos之间的数字]
void printNumber(const string&str,int &num_begin_pos,int end_pos){
if(num_bgin_pos!=-1){
int num=getNumber(str,num_begin_pos,end_pos);
cout<<num<<" ";
num_begin_pos=-1;
}
}
int main(){
string str;
cin>>str;
int num_begin_pos=-1; // -1表示数字还未开始
stack<char> s;
for(int i=0;i<str.size();++i){
if(str[i]=='+'||str[i]=='-'){
printNumber(str,num_begin_pos,i-1);
// 将栈中的 */+- 都出栈
while(!s.em)
}
}
}
|
