devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

王道计算机考研机试指南刷题笔记-自用4_计算机复试机试刷题

作者：小惠珠哦 | 2024-07-06 10:37:59

赞

踩

计算机复试机试刷题

目录

第三章 排序与查找

3.1 排序

例题3.1 排序（华科复试上机题）

①直接插入排序

②折半插入排序

③希尔排序

④冒泡排序

⑤快速排序

例题3.2 成绩排序（清华复试上机题）

例题3.3 成绩排序（清华复试上机题）

习题3.1 特殊排序（华科复试上机题）

习题3.2 整数奇偶排序（北大复试上机题）

习题3.3 小白鼠排队（北大复试上机题）

第三章 排序与查找

3.1 排序

例题3.1 排序（华科复试上机题）

排序_牛客题霸_牛客网 (nowcoder.com)

1、思路

  • 排序这一块儿挺重要的，初试结束之后就没再看过了，经典排序算法的实现忘得差不多了，用这一题重新捡起来。
  • C++ algorithm 库中的sort函数：sort(first,last,comp) // first和last为待排序序列的起始地址arr和结束地址arr+n,comp为排序方式，默认升序。如果要降序排列或自定义排列，可以编写比较函数来实现。
  • 去年备考的笔记还在，翻出来复习一遍之后再用不同的排序方法都实现一遍。

2、解答

①直接插入排序

  1. // 1.直接插入排序
  2. void insertSort(int a[], int n) {
  3.     int i, j;
  4.     // 将第2~n个元素依次插入已排好序的队列中
  5.     for ( i = 1 ; i < n ; i++ ) {
  6.         int temp;
  7.         // 只有a[i]<a[i-1]（已排序好的最后一个元素）时才需要移动
  8.         if ( a[i] < a[i - 1] ) {
  9.             // temp暂存待排序的a[i]
  10.             temp = a[i];
  11.             // 所有大于temp的元素都后移一位
  12.             for ( j = i - 1 ; a[j] > temp ; --j ) {
  13.                 a[j + 1] = a[j];
  14.             }
  15.             // 将待排序元素插入最终位置
  16.             a [j + 1] = temp;
  17.         }
  18.     }
  19. }

②折半插入排序

  1. //2.折半插入排序
  2. void insertSort2(int a[], int n) {
  3.     int i, j, low, high, mid,temp;
  4.     // 将第2~n个元素依次插入已排好序的队列中
  5.     for ( i = 2; i <= n ; i++ ) {
  6.         temp = a[i];
  7.         // 折半查找的两个端点值
  8.         low = 1, high = i-1;
  9.         // while循环条件：low<=high
  10.         while ( low <= high ) {
  11.             mid = (low + high) / 2;
  12.             if ( temp < a[mid] )
  13.                 high = mid-1; // 查找左半子表
  14.             else
  15.                 low = mid+1; // 查找右半子表
  16.         }
  17.         for ( j = i - 1 ; j >= high + 1 ; --j ) {
  18.             a[j + 1] = a[j];
  19.         }
  20.         // 将待排序元素插入最终位置
  21.         a [high + 1] = temp;
  22.     }
  23. }

       

③希尔排序

  1. //3.希尔排序
  2. void shellSort(int a[], int n) {
  3.     int i, j, dk;
  4.     for ( dk = n / 2 ; dk >= 1 ; dk = dk / 2 ) { // 步长变化
  5.         for ( i = dk + 1 ; i <= n ; i++ ) {
  6.             // 将a[i]插入有序增量序列
  7.             if ( a[i] < a[i - dk] ) {
  8.                 a[0] = a[i];
  9.                 // 注意循环条件
  10.                 for ( j = i - dk ; j > 0 && a[j] > a[0] ; j -= dk ) {
  11.                     a[j + dk] = a[j];
  12.                 }
  13.                 a[j + dk] = a[0];
  14.             }
  15.         }
  16.     }
  17. }

        

④冒泡排序

  1. //4.冒泡排序
  2. void bubbleSort(int a[],int n){
  3.     int i,j;
  4.     bool flag;
  5.     for ( i = 0 ; i < n ; i++ ) {
  6.         // 标志本趟冒泡是否发生交换
  7.         flag = false;
  8.         for ( j = n-1 ; j > i ; j-- ) {
  9.             int temp;
  10.             if ( a[j] < a[j-1] ) {
  11.                 temp = a[j];
  12.                 a[j] = a[j-1];
  13.                 a[j-1] = temp;
  14.                 flag = true;
  15.              }
  16.         }
  17.         // 本次冒泡没有发生交换，说明已有序
  18.         if (!flag)
  19.             return;
  20.     }
  21. }

⑤快速排序

        一个大坑：写的时候把pivot写成了a[pivot]，结果怎么都不对，自己来回对了几遍也没发现问题……

  1. //5.快速排序
  2. int Partition(int a[], int low, int high) {
  3.     // 选取第一个元素作为枢轴元素
  4.     int pivot = a[low];
  5.     while (low < high) {
  6.         // high所指向的元素大于等于枢轴元素，--high
  7.         while (low < high && a[high] >= pivot ) --high;
  8.         // 比枢轴元素小的移到左边
  9.         a[low] = a[high];
  10.         // low所指向的元素小于等于枢轴元素，++low
  11.         while (low < high && a[low] <= pivot ) ++low;
  12.         // 比枢轴元素大的移到右边
  13.         a[high] = a[low];
  14.     }
  15.     // 跳出循环时low=high，枢轴元素存在到a[high]
  16.     a[low] = pivot;
  17.     return low;
  18. }
  19.  
  20. void quickSort(int a[], int low, int high) {
  21.     if ( low < high ) {
  22.         int pivotpos = Partition(a, low, high);
  23.         quickSort(a, low, pivotpos - 1);
  24.         quickSort(a, pivotpos + 1, high);
  25.     }
  26. }

例题3.2 成绩排序（清华大学复试上机题）

成绩排序_牛客题霸_牛客网 (nowcoder.com)

1、思路

  • 处理多个学生学号和成绩的时候，发现直接输入不行。看了解析发现这里是对结构体进行排序，需要先将学生抽象为一个结构体，用C++更方便。
  • 排序的要求：
  • 成绩相等：比较学号，从小到大排序
  • 成绩不等：比较成绩，从小到大排序
  • 排序利用C++ alogrithm库中的sort函数可以实现，只需要编写自定义排序函数comp，特别注意comp函数的写法。

2、源代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. // 定义学生结构体
  7. struct Student {
  8.     int id;
  9.     int score;
  10. };
  11.  
  12. // 自定义比较函数
  13. bool comp (Student a, Student b) {
  14.     // 成绩相等比较学号
  15.     if (a.score == b.score) 
  16.         return a.id < b.id;
  17.     else 
  18.         // 成绩不等比较成绩
  19.         return a.score < b.score;
  20. }
  21.  
  22. int main() {
  23.     int n;
  24.     scanf("%d\n", &n);
  25.     Student arr[n];
  26.     for (int i = 0 ; i < n ; i++) {
  27.         scanf("%d %d\n", &arr[i].id, &arr[i].score);
  28.     }
  29.     sort(arr, arr + n, comp);
  30.     for (int i = 0 ; i < n ; i++) {
  31.         printf("%d %d\n", arr[i].id, arr[i].score);
  32.     }
  33.     return 0;
  34. }

例题3.3 成绩排序（清华大学复试上机题）

成绩排序_牛客题霸_牛客网 (nowcoder.com)

1、思路

  • 按照上一题一样的思路哐哐写，写了两个自定义排序函数，用户输入0调用降序，输入1调用升序。
  • 不出意外没通过，看了其他人解法的评论区发现sort排序是不稳定排序，而题目要求相同成绩按照先录入者排序在前的规则处理。
  • stable_sort(first,last,cmp) 函数可以实现稳定排序。
  • 由于学生信息中包含姓名，所以输入输出选用C++ 的cin和cout会更方便。

2、总结

  • 书上给的解法是在学生结构体中多定义了一个int型id属性，输入学生信息时依次id赋值，比较成绩时相同成绩再继续比较id，id小的即先录入的，符合题目要求。
  • 也可以自己编写稳定的排序算法（比如冒泡排序）来实现。

3、源代码

  1. // version 1 : stable_sort()实现
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. // 定义学生结构体
  8. struct Student {
  9.     string name;
  10.     int score;
  11. };
  12.  
  13. // 升序或降序
  14. int flag;
  15.  
  16. // 自定义排序函数
  17. bool cmp(Student a, Student b) {
  18.     if (flag == 0) {
  19.         return a.score > b.score;
  20.     } else
  21.         return a.score < b.score;
  22. }
  23.  
  24.  
  25. int main() {
  26.     int n;
  27.     while ( cin >> n ) {
  28.         cin >> flag;
  29.         Student s[n];
  30.         for ( int i = 0 ; i < n ; i++) {
  31.             cin >> s[i].name >> s[i].score;
  32.         }
  33.         stable_sort(s, s + n, cmp);
  34.         for ( int i = 0 ; i < n ; i++) {
  35.             cout << s[i].name << " " << s[i].score << endl;
  36.         }
  37.     }
  38. }
  1. // version 2 : 给Student结构体添加id属性实现稳定排序
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. // 定义学生结构体
  8. struct Student {
  9.     string name;
  10.     int score;
  11.     int id;  // 标识录入的先后顺序
  12. };
  13.  
  14. // 升序或降序
  15. int flag;
  16.  
  17. // 自定义排序函数
  18. bool cmp(Student a, Student b) {
  19.     if (flag == 0) {
  20.         // 分数相等，id小的在前
  21.         if (a.score == b.score) {
  22.             return a.id < b.id;
  23.         } else {
  24.             // 分数不等，按分数降序排列
  25.             return a.score > b.score;
  26.         }
  27.     } else {
  28.         if (a.score == b.score) {
  29.             return a.id < b.id;
  30.         } else {
  31.             // 分数不等，按分数升序排列
  32.             return a.score < b.score;
  33.         }
  34.     }
  35. }
  36.  
  37.  
  38. int main() {
  39.     int n;
  40.     while ( cin >> n ) {
  41.         cin >> flag;
  42.         Student s[n];
  43.         for ( int i = 0 ; i < n ; i++) {
  44.             cin >> s[i].name >> s[i].score;
  45.             s[i].id=i; // 给id赋值
  46.         }
  47.         stable_sort(s, s + n, cmp);
  48.         for ( int i = 0 ; i < n ; i++) {
  49.             cout << s[i].name << " " << s[i].score << endl;
  50.         }
  51.     }
  52. }

习题3.1 特殊排序（华科复试上机题）

特殊排序_牛客题霸_牛客网 (nowcoder.com)

1、思路

  • sort函数对输入的数进行排序，先输出排序后的最后一个元素（即最大值），再依次输出前n个元素。
  • 我想复杂了，我想的是先找到最大值，再把最大值从数组中删掉，对剩下的元素用一次sort函数。

2、源代码

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. #define N 1010
  6.  
  7. int a[N];
  8.  
  9. int main() {
  10.     int n;
  11.     int i;
  12.     cin >> n;
  13.     for (i = 0 ; i < n ; i++) {
  14.         cin >> a[i];
  15.     }
  16.     // 对数组a升序排列
  17.     sort(a,a+n);
  18.     // 输出最后一个元素（即最大值）
  19.     cout << a[n-1] << endl;
  20.     // 判断是否有剩下的数
  21.     if( n==1 ) {
  22.         cout << "-1" << endl;
  23.     } else {
  24.         for (i = 0 ; i < n-1 ; i++) {
  25.             cout << a[i] << " "; // 依次输入前n-1个有序元素
  26.         }
  27.         cout << endl;
  28.     }
  29.  
  30. }

习题3.2 整数奇偶排序（北大复试上机题）

整数奇偶排序_牛客题霸_牛客网 (nowcoder.com)

1、思路

  • 定义两个奇偶数组，输入时判断奇偶性，存入对应数组
  • 对奇数组降序排列，偶数组升序排列，一次AC。
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. bool cmp(int a,int b) {
  6.     return a > b;
  7. }
  8.  
  9. int main() {
  10.     int a[10];
  11.     int even[10],odd[10];
  12.     int i,j=0,k=0;
  13.     for (i = 0 ; i < 10 ; i++) {
  14.         cin >> a[i];
  15.         if (a[i]%2 == 0) {
  16.             even[j++] = a[i]; // a[i]是偶数，存入even
  17.         } else {
  18.             odd[k++] = a[i]; // a[i]是奇数，存入odd
  19.         }
  20.     }
  21.     sort(odd,odd+k,cmp); // 对奇数降序排列
  22.     for(i = 0 ; i < k ; i++) {
  23.         cout << odd[i] << " ";
  24.     }
  25.     sort(even,even+j);  // 对偶数升序排列
  26.     for(i = 0 ; i < j ; i++) {
  27.         cout << even[i] << " ";
  28.     }
  29.     cout << endl;    
  30. }

2、其他方法

  ① 先把所有的按从小到大排序，然后遍历两次数组。第一遍从后往前，遇到奇数就输出；第二遍从前往后，遇到偶数就输出。（很巧妙，通过从后往前遍历实现奇数的降序排列） 

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int main() {
  6.     int a[10];
  7.     while(cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]>>a[7]>>a[8]>>a[9]) {
  8.         // 对数组a升序排序
  9.         sort(a,a+10);
  10.         // 从后往前遍历排序好的a数组，遇到奇数就输出
  11.         for(int i = 9 ; i >= 0 ; --i) {
  12.             if (a[i]%2 == 1) 
  13.                 cout << a[i]<< " ";
  14.         }
  15.         // 从前往后遍历排序好的a数组，遇到偶数就输出
  16.         for(int i = 0 ; i < 10 ; ++i) {
  17.             if (a[i]%2 == 0) 
  18.                 cout << a[i]<< " ";
  19.         }
  20.         cout << endl;
  21.     }
  22. }

  ② 在cmp函数中书写比较逻辑：传入两个整型参数a，b

  • a、b都是奇数：降序排列
  • a、b都是偶数：升序排列
  • a、b一个奇数一个偶数：奇数排在偶数前面（最后一个return没看懂，私信了原作者，等一个回复orz）
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. bool cmp (int a,int b) {
  6.     if ( a%2==1 && b%2==1 ) // a、b都是奇数，降序排列
  7.         return a > b;
  8.     else if ( a%2==0 && b%2==0 )  // a、b都是偶数，升序排列
  9.         return a < b ;
  10.     else 
  11.         return a%2 > b%2;  // 这里没看懂orz
  12. }
  13.  
  14. int main() {
  15.     int a[10];
  16.     for (int i = 0 ; i < 10 ; i++) {
  17.         cin >> a[i];
  18.     }
  19.     sort(a,a+10,cmp);
  20.     for (int i = 0 ; i < 10 ; i++) {
  21.         cout << a[i] << " ";
  22.     }
  23.     cout << endl;
  24. }

习题3.3 小白鼠排队（北大复试上机题）

小白鼠排队_牛客题霸_牛客网 (nowcoder.com)

1、思路

  • 与例题3.2类似，定义老鼠结构体，存储重量和帽子颜色两个属性。
  • 编写自定义比较函数cmp，按重量降序排列。比较简单

2、源代码

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct Mouse { // 定义老鼠结构体
  6.     int weight;
  7.     string color;
  8. };
  9.  
  10. bool cmp(Mouse a, Mouse b) { // 定义cmp比较函数，按重量降序排列
  11.     return a.weight > b.weight;
  12. }
  13.  
  14. int main() {
  15.     int n;
  16.     cin >> n;
  17.     Mouse m[n];
  18.     for (int i = 0 ; i < n ; i++) {
  19.         cin >> m[i].weight >> m[i].color;
  20.     }
  21.     sort(m, m + n, cmp);
  22.     for (int i = 0 ; i < n ; i++ ) {
  23.         cout << m[i].color << endl;
  24.     }
  25. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/792621
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号