西工大计算机考研机试题练习（2019年-2014年）

nwpu复试上机题练习

2019年

1.排序@@

#include "iostream"
#include "set"
using namespace std;
int main(int argc, char* argv[])
{
   
	set<int> st;
	int n;
	cin>>n;
	while(n--){
   
		for(int i = 0;i < 8;i++){
   
			int num;
			cin>>num;
			st.insert(num);
		}
		for(auto num : st){
   
			cout<<num<<" ";
		}
		cout<<endl;
	}
	return 0;
}

手动排序如下：

#include <bits/stdc++.h>
using namespace std;
ostream &operator<<(ostream &c, const vector<int> v)
{
   
    for (auto i : v)
    {
   
        c << i << " ";
    }
    c << endl;
    return c;
}
void insert_sort(vector<int> &v)
{
   //找到合适的位置 插入选中的元素
    if (!v.size())
        return;
    for (int i = 1; i < v.size(); i++)
    {
   
        int k = i - 1, key = v[i];
        while (k >= 0 and key < v[k])
        {
   
            v[k + 1] = v[k];
            k--;
        }
        v[k + 1] = key;
    }
    return;
}
void select_sort(vector<int> &v)
{
   
    if (!v.size())
        return;
    for (int i = 0; i < v.size() - 1; i++)
    {
   //每轮选出最大的元素，放在已排序队列最右边
        int min = i;
        for (int j = i + 1; j < v.size(); j++)
        {
   
            if (v[j] < v[min])
                min = j;
        }
        swap(v[min], v[i]);
    }
}
void bubble_sort(vector<int> &v)
{
    //把最大的元素放在最后面
    for (int i = 0; i < v.size() - 1; i++)
    {
   
        for (int j = 0; j < v.size() - 1 - i; j++)
        {
   
            if (v[j] > v[j + 1])
                swap(v[j], v[j + 1]);
        }
    }
    return;
}
void quick_sort(vector<int> &s, int l, int r)
{
   
    if (l < r)
    {
   
        int i = l, j = r, x = s[l];
        while (i < j)
        {
   
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;  
            if(i < j) 
                s[i++] = s[j];
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用 
        quick_sort(s, i + 1, r);
    }
}
int main()
{
   
    vector<int> v({
   3, 4, 1, 2, 5});
    bubble_sort(v);
    cout << v;
    cin.get();
}

2.求三角形面积

#include "iostream"
#include <iomanip>
#include "math.h"
using namespace std;
int main(int argc, char* argv[])
{
   
	int n;
	cin>>n;
	while(n--){
   
        double a,b,c;
        cin>>a>>b>>c;
        if(a+b>c && a+c>b && b+c>a){
   
            double p = (a+b+c)/2;
            cout<<fixed<<setprecision(2)<<sqrt(p*(p-a)*(p-b)*(p-c))<<endl;
        }else{
   
            cout<<"NaN"<<endl;
        }
	}
	return 0;
}

3.判断IP地址是否有效

#include "iostream"
#include "stdio.h"
using namespace std;
bool check(int num){
   
    return num>=0&&num<=255 ? 1 : 0;
}
int main(int argc, char* argv[])
{
   
	int n;
	cin>>n;
	while(n--){
   
        int a,b,c,d;
        scanf("%d.%d.%d.%d",&a,&b,&c,&d);
        if(check(a)&&check(b)&&check(c)&&check(d)){
   
            cout<<"Yes"<<endl;
        }else{
   
            cout<<"No"<<endl;
        }
	}
	return 0;
}

4.求质数@

#include "iostream"
#include "math.h"
using namespace std;
bool isPrime(int n){
   
    if(n <= 1) return 0;
    if(n == 2) return 1;
    for(int i = 2;i<=sqrt(n);i++){
   
        if(n%i == 0) return 0;
    }
    return 1;
}
int main(int argc, char* argv[])
{
   
    int m,n;
    cin>>m>>n;
    while(n){
   
        if(isPrime(m)) {
   
            cout<<m<<endl;
            n--;
        }
        m++;
    }
	return 0;
}

5.一天中的任意两天差值

#include "iostream"
using namespace std;
int main(int argc, char* argv[])
{
   
    int n;
    cin>>n;
    while(n--){
   
        int year1,month1,day1,year2,month2,day2;
        scanf("%d %d %d %d %d %d",&year1,&month1,&day1,&year2,&month2,&day2);
        cout<<(month2-month1)*30+day2-day1+1<<endl;
    }
	return 0;
}

6.四则运算@@

思路：

• 首先设定符号的优先级，例如乘除法优先级高于加法高于减法。
• 再设定符号栈s和数字栈n，定义“调整”：弹出数字栈顶两个元素与符号栈顶一个运算符，进行运算，将运算结果压入数字栈。其实就是优先计算一个最基本的式子。
• 开始从左向右依次匹配：
  • 遇到数字，首先完整解析出数字（如32.13），再压入数字栈n
  • 遇到字符，如果符号栈顶字符优先级高且，调整符号栈；否则压入该字符
  • 遇到左括号，找到对应的右括号，将递归调用自身处理它们包裹的字符串，得到对应的数值。将数值压入数字栈。指针指向刚才的右括号下一个元素，继续匹配。
• 匹配结束后符号栈如果不空，则进行调整直到栈空。最后数字栈必剩下一个数值，即为结果

#include <iostream>
#include <stack>
#include <iomanip>
#include <string>
using namespace std;
int prios(char c)
{
   
    switch (c)
    {
   
    case '*':
        return 3;
    case '/':
        return 2;
    case '+':
        return 1;
    case '-':
        return 0;
    default:
        return 0;
    }
}
double matchNum(string s, int &p)
{
   
    //匹配数字 并且移动p
    string num = "";
    while (isdigit(s[p]) or s[p] == '.')
    {
   
        num += s[p];
        p++;
    }
    return stod(num);
}
void adjust(stack<char> &c, stack<double> &n)
{
   
    double n1 = n.top();
    n.pop();
    double n2 = n.top();
    n.pop();
    double n3;
    switch (c.top())
    {
   
    case '+':
        n3 = n1 + n2;
        break;
    case '-':
        n3 = n2 - n1;
        break;
    case '*':
        n3 = n2 * n1;
        break;
    case '/':
        n3 = n2 / n1;
        break;
    }
    n.push(n3);
    c.pop();
}
int findRight(int p, string s)
{
   
    stack<char> st;
    while (p <= s.size())
    {
   
        if (s[p] == '(')
            st.push('(');
        else if (s[p] == ')')
            st.pop();
        if (st.empty())
            return p;
        p++;
    }
    return -1;
}
double sum(string s)
{
   
    stack<char> c;
    stack<double> n;
    int p = 0; //pos
    while (p < s.size())
    {
   
        char ch = s[p];
        if (isdigit(ch))
        {
   
            n.push(matchNum(s, p));
        }
        else if (ch == '*' or ch == '/' or ch == '+' or ch == '-')
        {
   
            if (!c.empty() and prios(ch) <= prios(c.top()))
            {
   
                adjust(c, n);
            }
            c.push(ch);
            p++;
        }
        else if (ch == '(')
        {
   
            int index = findRight(p, s);
            n.push(sum(s.substr(p + 1, index - p - 1)));
            p = index + 1;
        }
    }
    while (!c.empty())
    {
   
        adjust(c, n);
    }
    return n.top();
}
int main()
{
   
    int n;
    cin >> n;
    cin.get();
    while (n--)
    {
   
        string s;
        getline(cin,s);
        double ans = sum(s);
        if(ans - (int)ans ==0){
   
            cout<<(int)ans<<endl;
        }else{
   
            cout<<fixed<<setprecision(2)<<ans<<endl;
        }
    }
    return 0;

重难点：

• 整体思路，特别是设定运算符优先级，规定两个栈的调整规则
• 23.123字符转数字的实现：stod字符串转double

if (isdigit(s[p])) //如果首字母是数字，就与后续数字拼成一个数
       {
   
           string num_s;
           while (isdigit(s[p]) or s[p] == '.')
           {
   
               num_s += s[p++];
           }
           n.push(stod(num_s)); //223.221由string转为double
       }

• 找到右括号并正确分隔字符串：string.substr方法，注意其第一个参数是起始位置，第二个参数是要分割的长度而不是结束位置。

   else if (s[p] == '(')
        {
   
            int pos = findRight(p,s);
            //pos这时候指向正确的对应右括号
            string u(s);
            n.push(sum(s.substr(p + 1, pos - p - 1)));
            s = u;//字符串s已被破坏
            p = pos +