10个选择题,3个编程题,还有4个Android/iOS的附加题,附加题不记得了,记录一下选择题和编程题。

一、选择题

1.有6个不同颜色的珠子,可以串成多少种不同的手环?(旋转、翻转能变成一样的认为是一种)

A.30   B.60   C.120   D.720

2、在主线程中int i = 0,再并发同时执行A和B两个函数,函数A的内容是i++;i++;函数B的内容是i+=2;则i的结果可能为?(多选)

A.0   B.1   C.2   D.3   E.4   F.5   G.6

3、bash中不是用来处理字符串的是?

A.cut   B.awk   C.sed   D.pushd

4、【1,2,3,4,5】入栈,出栈不可能为?

A.【23415】   B.【54132】   C.【23145】   D.【15432】

5、已知一颗二叉树的先序遍历序列为GDAFEMHZ,中序遍历序列为ADEFGHMZ,则后序遍历序列为?

A.ADEFGHMZ   B.DAEFHZMG   C.AEFDHZMG   D.AFEDHMZG

6、不属于操作系统进程间实现同步的方式是?

A.临界区   B.互斥量   C.进程锁   D.事件

7、在传输层中未使用TCP协议的是?

A.SMTP   B.FTP   C.TELNET   D.DNS

8、下列哪个排序方式的平均时间复杂度不是O(nlogn)?

A.选择排序   B.快速排序   C.归并排序   D.堆排序

9、下列不是死锁产生条件的是?

A.互斥   B.请求与保持   C.竞争   D.循环等待

10、TCP的可靠传输实现不包括下列哪个选项?

A.滑动窗口   B.冗余校验   C.超时重传   D.确认机制

 

二、编程题

1.定义一个数据结构Edge

class Edge{
    private int a;
    private int b;
}

表示节点a和节点b是连接在一起的。

实现如下方法,即给定一个Edge数组Edge[]graph,以及任意两个节点p和q,返回p和q是否联通。

bool isConnected(Edge[]graph , int p , int q)

2.实现一个方法:给定股票的价格序列数组prices[n],找到在该区间内股票的最大回撤值。

(找到p1,p2两个点需满足以下条件:p1在p2左边,prices[p1]>=prices[p2],prices[p1] – prices[p2]在整个区间最大)

示例:

prices[n] = {2,3,4,1,10,8,5,1,7,2}

最大回撤:prices[4] – prices[7] = 10 – 1 = 9

prices[n] = {9,8,7,6,5}

最大回撤:prices[0] – prices[4] = 9 – 5 = 4

double getMaxDrawdown(double prices[])

 

3.已知M*N矩阵,矩阵的每行从左到右递增,每列从上到下递增,给定目标值,写程序计算给出的目标值是否存在矩阵中。

bool isExist (double  matrix[][] , double value)

RT,来自网龙笔试题,判断一个整数的二进制是否是01交替。

不知道我的答案对不对。。。负数的情况略复杂。

代码如下:

bool isZeroAndOne(int num)
{
    if(num<0){
        num = -num;
        num = num ^ 2147483647;
        num++;
    }
     if(num==1||num==0)
        {
                return false;
        }
        else {
        int last = num & 1;
        while (num)
        {
                num = num >> 1;
                int cur = num & 1;
                if ((last == 1 && cur == 1) || (last == 0 && cur == 0))
                {
                        return false;
                }
                last = cur;
        }
        return true;
        }
}

 

假设有标注了 1, 2, 3, …, n 各个数字的 n 张卡片。当第 1 张卡片的 数字为 k 时,则把前 k 张卡片逆向排序,并一直重复这个操作。举个例 子,当 n = 6 时,如果由“362154”这个序列开始,则卡片的变化情况 如下。

这种情况下,卡片顺序一共变化 8 次后就无法继续变化了。

求使卡片顺序变化次数最多的 n 张卡片的顺序以及最大的变化次数。

 

1.顺序暴力递归思路:使用C++生成n位数的全排列,按照题意暴力模拟即可。

代码:

#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n);//获得数组的全排列
int fun(int a[],int deep);//求该数组翻转多少次后第一个数为1

int tempList[99];
int maxList[99];
int maxi = 0;

void all_permutation(int arr[], int n)//获得数组的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do{
      for(int i = 0;i<n;i++){
        tempList[i] = arr[i];//临时数组存储此时的全排列
      }
      int b = fun(tempList,0);//获得该排列翻转的次数,保存给b
      if(b > maxi){//如果b大于此时最大的数
        maxi = b;//最大的翻转次数更改为b
        for(int i = 0;i<n;i++){
            maxList[i] = arr[i];//存储翻转次数最多的数组更新
        }
      }
    }while(next_permutation(arr,arr+n));//获得下一个排列
}

int fun(int a[],int deep){
    if(a[0]==1){
        return deep;//如果第一个数是1的时候,返回结果
    }
   else{
    reverse(a,a+a[0]);//翻转数组的前a[0]个数
    fun(a,deep+1);//调用递归且deep+1,deep是我们的翻转次数
   }
}

int main(){
    int t;
     while(scanf("%d",&t)){
     if(t>=2 && t < 10){
     maxi = 0;
     int a[t+10];
     for(int i = 0;i<t;i++){
        a[i] = i+1;
     }
      all_permutation(a,t);
      printf("array is :");
      for(int i = 0;i<t;i++){
        printf("%d ",maxList[i]);
      }
      printf("\n");
      printf("max count = %d\n",maxi);
     }
     else{
        printf("please input number of 2~9!\n");
     }
     }
}

 

2.倒推优化递归思路:首先,数组的全排列需要第一个数是1,其次当一个数组中第i个数字是i的时候,这个数组一定有递推的上一步,否则这个数组就是最初情况。

代码:


#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n);//获得数组的全排列
void fun(int a[],int n,int deep);//递归函数

int tempList[99];//存储临时数组
int maxList[99];//存储变化次数最多的数组结果
int maxi = 0;//存储变化的最大次数

void all_permutation(int arr[], int n)//获得数组的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do
    {
        if(arr[0] == 1)
        {
            for(int i = 0; i<n; i++)
            {
                tempList[i] = arr[i];
            }
            fun(tempList,n,0);
        }
    }
    while(next_permutation(arr,arr+n));
}

void fun(int a[],int n,int deep)//递归函数
{
    if(deep > maxi){//获得最大翻转次数且存储此时的数组
        maxi = deep;
        for(int i = 0;i<n;i++){
            maxList[i] = a[i];
        }
    }
    for(int i = 1;i<n;i++){
        if(a[i]==i+1){//如果数组的第i个数等于i+1(因为数组从0开始)
            reverse(a,a+i+1);//翻转前i个数
            fun(a,n,deep+1);//开始递归,deep+1
            reverse(a,a+i+1);//翻转回去
        }
    }
}

int main()
{
    int t;
    while(scanf("%d",&t))
    {
        if(t>=2 && t < 10)
        {
            maxi = 0;
            int a[t+10];
            for(int i = 0; i<t; i++)
            {
                a[i] = i+1;
            }
            all_permutation(a,t);
            printf("array is :");
            for(int i = 0; i<t; i++)
            {
                printf("%d ",maxList[i]);
            }
            printf("\n");
            printf("max count = %d\n",maxi);
        }
        else
        {
            printf("please input number of 2~9!\n");
        }
    }
}

 

 

题目描述:

n条恶龙闯入了王国的领土,为了拯救王国的危机,国王任命你前往冒险者工会雇佣勇者前去讨伐恶龙。每条恶龙的战斗力为ai。每个勇者的战斗力为bi,雇佣他的花费为ci。只有当勇者的战斗力大于等于恶龙的战斗力时,勇者才能击败恶龙。因为勇者都是骄傲的,所以勇者们拒绝互相组队(即每个勇者只能独自一人去讨伐恶龙)。勇者们都具有凝聚空气中魔力的能力,因此可以无限次出战。王国需要金币去灾后重建,需要你计算打败所有恶龙的最小花费。

输入:

第一行输入一个整数T,表示数据的组数。1≤T≤10。 第一行输入n,m,表示龙的数量和冒险者的数量。0<n,m≤10000。 接下来n行,每行一个数字ai表示龙的战斗力。 接下来m行,每行分别为bi和ci,表示冒险者的战斗力和雇佣他的花费。0<=ai,bi,ci≤100000。

输出:

如果能击退恶龙们,请输出最小的花费,如果不能,请输出”Kingdom fall”

样例输入:

2

1 1

6

10 3

3 2

10

14

15

9 10

6 7

样例输出:

3 Kingdom fall

 

先对每个骑士和龙的能力进行sort排序,然后遍历骑士和龙,用最小的代价将龙一条一条击退就好啦~
AC代码:

#include<iostream>
#include<limits.h>
#include<algorithm>
using namespace std;

struct maoxianjia
{
    double att;
    double mesos;
};

int comp(const maoxianjia &a,const maoxianjia &b)
{
    if(a.att == b.att)
    {
        return a.mesos<b.mesos;
    }
    else
        return a.att>b.att;
}

int main()
{
    int t = 0;
    int n = 0;
    int m = 0;
    int sum = 0;
    int mini;
    cin>>t;
    while(t--)
    {
        sum = 0;
        cin>>n>>m;
        int a[n+1];
        for(int i = 0; i < n; i++)
        {
            cin>>a[i];
        }
        maoxianjia b[m+1];
        for(int i = 0; i < m ; i++)
        {
            cin>>b[i].att>>b[i].mesos;
        }
        sort(a,a+n);
        sort(b,b+m,comp);
        if(b[0].att<a[n-1])
        {
            cout<<"Kingdom fall"<<endl;
            continue;
        }
        else
        {
            mini = INT_MAX;
            for(int i = 0; i <n ; i++)
            {
                for(int j = 0; j<m ; j++)
                {
                    if(a[i] > b[j].att)
                    {
                        break;
                    }
                    if(mini > b[j].mesos)
                    {
                        mini = b[j].mesos;
                    }
                }
                sum = sum + mini;
                mini = INT_MAX;
            }
        }
        cout<<sum<<endl;
    }
}

问题描述
  体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排,学号小的排在前面,然后进行多次调整。一次调整小明可能让一位同学出队,向前或者向后移动一段距离后再插入队列。
例如,下面给出了一组移动的例子,例子中学生的人数为8人。
0)初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8;
1)第一次调整,命令为“3号同学向后移动2”,表示3号同学出队,向后移动2名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8;
2)第二次调整,命令为“8号同学向前移动3”,表示8号同学出队,向前移动3名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7;
3)第三次调整,命令为“3号同学向前移动2”,表示3号同学出队,向前移动2名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
小明记录了所有调整的过程,请问,最终从前向后所有学生的学号依次是多少?
请特别注意,上述移动过程中所涉及的号码指的是学号,而不是在队伍中的位置。在向后移动时,移动的距离不超过对应同学后面的人数,如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时,移动的距离不超过对应同学前面的人数,如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。
输入格式
  输入的第一行包含一个整数n,表示学生的数量,学生的学号由1到n编号。
第二行包含一个整数m,表示调整的次数。
接下来m行,每行两个整数p, q,如果q为正,表示学号为p的同学向后移动q,如果q为负,表示学号为p的同学向前移动-q。
输出格式
  输出一行,包含n个整数,相邻两个整数之间由一个空格分隔,表示最终从前向后所有学生的学号。
样例输入
8
3
3 2
8 -3
3 -2
样例输出
1 2 4 3 5 8 6 7
评测用例规模与约定
  对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 1000,所有移动均合法。
AC代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int n,m;
    vector<int> a;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    a.push_back(i);
    for(int cas=0;cas<m;cas++)
    {
        int x,y;
        cin>>x>>y;
        vector<int>::iterator it;
        for(it=a.begin();it!=a.end();it++)
            if(*it==x)
            break;
        a.erase(it);
        a.insert(it+y,x);

    }
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;

}

 

问题描述
  请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。
假设一节车厢有20排、每一排5个座位。为方便起见,我们用1到100来给所有的座位编号,第一排是1到5号,第二排是6到10号,依次类推,第20排是96到100号。
购票时,一个人可能购一张或多张票,最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位,则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中(不考虑是否相邻)。
假设初始时车票全部未被购买,现在给了一些购票指令,请你处理这些指令。
输入格式
  输入的第一行包含一个整数n,表示购票指令的数量。
第二行包含n个整数,每个整数p在1到5之间,表示要购入的票数,相邻的两个数之间使用一个空格分隔。
输出格式
  输出n行,每行对应一条指令的处理结果。
对于购票指令p,输出p张车票的编号,按从小到大排序。
样例输入
4
2 5 4 2
样例输出
1 2
6 7 8 9 10
11 12 13 14
3 4
样例说明
  1) 购2张票,得到座位1、2。
2) 购5张票,得到座位6至10。
3) 购4张票,得到座位11至14。
4) 购2张票,得到座位3、4。
评测用例规模与约定
  对于所有评测用例,1 ≤ n ≤ 100,所有购票数量之和不超过100。
AC代码
#include <iostream>
#include<list>
#include<math.h>
using namespace std;
  int main(){
  int n,m,temp,Count;
  int a[200];
  int b[30];

  for(int i=0;i<20;i++){
    b[i]=5;
  }
  for(int i=0;i<100;i++){
    a[i]=1;
  }

  cin>>n;
  while(n--){
    cin>>m;
    Count =m;
    for(int i=0;i<20;i++)
  {
      temp = i;
     if(b[i]>=m){
        break;
     }
     else temp++;
  }
   if(temp==20){
    for(int i=0;i<100;i++)
    if((a[i]==1)&&(Count!=0)){
        cout<<i+1<<" ";
        Count--;
        a[i]=0;
    }



   }
   else{
    for(int j=temp*5;j<temp*5+5;j++){
        if((a[j]==1)&&(Count!=0)){
            a[j]=0;
            cout<<j+1<<" ";
            Count--;
        }
    }
      b[temp] = b[temp] - m;
    cout<<endl;
   }
  }
  }

 

问题描述
  有一个学校的老师共用N个教室,按照规定,所有的钥匙都必须放在公共钥匙盒里,老师不能带钥匙回家。每次老师上课前,都从公共钥匙盒里找到自己上课的教室的钥匙去开门,上完课后,再将钥匙放回到钥匙盒中。
钥匙盒一共有N个挂钩,从左到右排成一排,用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置,但钥匙上有标识,所以老师们不会弄混钥匙。
每次取钥匙的时候,老师们都会找到自己所需要的钥匙将其取走,而不会移动其他钥匙。每次还钥匙的时候,还钥匙的老师会找到最左边的空的挂钩,将钥匙挂在这个挂钩上。如果有多位老师还钥匙,则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙,则老师们会先将钥匙全还回去再取出。
今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课,给出每位老师所需要的钥匙、开始上课的时间和上课的时长,假设下课时间就是还钥匙时间,请问最终钥匙盒里面钥匙的顺序是怎样的?
输入格式
  输入的第一行包含两个整数NK
接下来K行,每行三个整数wsc,分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙,但是老师使用钥匙的时间不会重叠。
保证输入数据满足输入格式,你不用检查数据合法性。
输出格式
  输出一行,包含N个整数,相邻整数间用一个空格分隔,依次表示每个挂钩上挂的钥匙编号。
样例输入
5 2
4 3 3
2 2 7
样例输出
1 4 3 2 5
样例说明
  第一位老师从时刻3开始使用4号教室的钥匙,使用3单位时间,所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙,使用7单位时间,所以在时刻9还钥匙。
每个关键时刻后的钥匙状态如下(X表示空):
时刻2后为1X345;
时刻3后为1X3X5;
时刻6后为143X5;
时刻9后为14325。
样例输入
5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9
样例输出
1 2 3 5 4
评测用例规模与约定
  对于30%的评测用例,1 ≤ NK ≤ 10, 1 ≤ w ≤ N, 1 ≤ sc ≤ 30;
对于60%的评测用例,1 ≤ NK ≤ 50,1 ≤ w ≤ N,1 ≤ s ≤ 300,1 ≤ c ≤ 50;
对于所有评测用例,1 ≤ NK ≤ 1000,1 ≤ w ≤ N,1 ≤ s ≤ 10000,1 ≤ c ≤ 100。
AC代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, k, w, s, c, key[1001];


struct Teacher//定义教师结构体
{
    int key;//钥匙编号
    int time;//使用钥匙时间
    int flag;//设置标识符
};

bool cmp(Teacher t1,Teacher t2){
    if(t1.time !=t2.time){
        return t1.time<t2.time;
    }
    else if(t1.flag !=t2.flag){
        return t1.flag >t2.flag;
    }
    else{
        return t1.key < t2.key;
    }
}
int main(){
std::ios::sync_with_stdio(false);
 vector<Teacher> v;//定义结构体向量
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        key[i] = i;
    }
    for(int i=0;i<k;i++)
    {
        cin>>w>>s>>c;
        Teacher t;
        t.key = w;
        t.time = s;
        t.flag = 0;//借
        v.push_back(t);
        t.key = w;
        t.time = s+c;
        t.flag = 1;//归还
        v.push_back(t);
    }
   sort(v.begin(),v.end(),cmp);

   for(int i=0;i<v.size();i++){
    Teacher t = v[i];
    if(t.flag==0)//借钥匙
    {
       for(int j = 1;j<=n;j++){
        if(key[j]==t.key){
            key[j]=0;
            break;
        }
       }

    }
   else {//还钥匙
      for(int j=1;j<=n;j++){
        if(key[j]==0){
            key[j]=t.key;
            break;
        }
      }
   }
   }
   for (int i=1;i<=n;i++){
    cout<<key[i]<<" ";
   }
   cout<<endl;
   return 0;
}