美团点评研发工程师笔试卷-2012年

1、请找出下面代码中的所有错误。

说明:以下代码是把一个字符串倒序,如“abcd”倒序后变为“dcba” 

#include"string.h"
main()
  {
   char*src="hello,world";
   char* dest=NULL;
   int len=strlen(src);
   dest=(char*)malloc(len);
    char* d=dest;
   char* s=src[len];
   while(len--!=0)
       d++=s--;
   printf("%s",dest);
   return 0;
 }
2、k链表翻转。给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,则翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6,用程序实现。

3、有一个随机数发生器,以概率P产生0,概率(1-P)产生1,请问能否利用这个随机数发生器,构造出新的发生器,以1/2的概率产生0和1。请写明结论及推理过程。

4、4个足球队打小组单循环,计分方式:胜3分平1分负0分,如果计分相同,则净胜球多的队伍排名靠前,如果净胜球还一样,则进球多的球队排名靠前。小组前两名出线。问可能出线的最低分数是多少。请说明推理过程。 备注:单循环赛是指所有参加比赛的队两两之间都比赛一次,最后按各队在全部比赛中的积分,得失分率排列名次。

5、从1到1000000的所有自然数,数字“1”一共出现了多少次?例:自然数101中,数字“1”出现了2次,自然数1011中,数字“1”出现了3次,请写明计算过程及结果。

6、以下代码功能:找出一个有序(字典序)字符串数组arr中值等于字符串v的元素的符号,如果有多个元素满足这个条件,则返回其中序号最大的。请找出下面代码中所有错误,直接在代码右侧空白处修改 。

Int bisearch(char**arr, int b, int e, char*v){
    Int minIndex = b, maxIndex = e, midIndex;
    while(minIndex<maxindex){
        midIndex=(minIndex+maxIndex)/2;
        if(strcmp(arr[midIndx],v<=0)){
            minIndex = midIndex;
        }else{
            maxIndex=minIndex;
        }
   }
        
    if(!strcmp(arr[maxIndex],v)){
        return maxIndex;
    }else{
        return -1;
    }
}
7、字符串ABCD,可以由字符串BCDA或者CDAB通过循环移位而得到。请编程实现以下检测:字符串S1是否可以由字符串S2通 过循环移位而得到。 语言不限(推荐C/C++,不推荐写伪码)


参考答案

1、如下:


  int main()
 {
  char* src = "hello,world";
  int len = strlen(src);
  char* dest = (char*)malloc(len+1);//要为\0分配一个空间
  char* d = dest;
  char* s = &src[len-1];//指向最后一个字符
  while( len-- != 0 )
  *d++=*s--;
  *d = 0;//尾部要加\0
  printf("%s\n",dest);
  free(dest);// 使用完,应当释放空间,以免造成内存汇泄露
  return 0;
 }


2、参考代码:

typedef struct node {
    struct node *next;
    int data;
} node;
void createList(node **head, int data)
{
    node *pre, *cur, *new;
    pre = NULL;
    cur = *head;
    while (cur != NULL) {
        pre = cur;
        cur = cur->next;
    }
    new = (node *)malloc(sizeof(node));
    new->data = data;
    new->next = cur;
    if (pre == NULL)
    *head = new;
    else
    pre->next = new;
}
void printLink(node *head)
{
    while (head->next != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("%dn", head->data);
}
int linkLen(node *head)
{
    int len = 0;
    while (head != NULL) {
        len ++;
        head = head->next;
    }
    return len;
}
node* reverseK(node *head, int k)
{
    int i, len, time, now;
    len = linkLen(head);
    if (len < k) {
        return head;
        } else {
        time = len / k;
    }
    node *newhead, *prev, *next, *old, *tail;
    for (now = 0, tail = NULL; now < time; now ++) {
        old = head;
        for (i = 0, prev = NULL; i < k; i ++) {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        if (now == 0) {
            newhead = prev;
        }
        old->next = head;
        if (tail != NULL) {
            tail->next = prev;
        }
        tail = old;
    }
    if (head != NULL) {
        tail->next = head;
    }
    return newhead;
}
int main(void)
{
    int i, n, k, data;
    node *head, *newhead;
    while (scanf("%d %d", &n, &k) != EOF) {
        for (i = 0, head = NULL; i < n; i ++) {
            scanf("%d", &data);
            createList(&head, data);
        }
        printLink(head);
        newhead = reverseK(head, k);
        printLink(newhead);
    }
    return 0;
}
3、这道题想等概率产生0、1,就需要找到两个独立事件,这个两个独立事件发生的概率相同,已知随机数生成器可以以p产生0,以1-p产生1,所以有下面4个独立事件,用随机数生成器产生00,01,10,11,各自的概率分别为p*p,p*(1-p),(1-p)*p,(1-p)*(1-p)可以发现生成01,10的概率相同,因此只保留这两种情况敏感词舍弃,然后将01映射为0,10映射为1,则等概率0,1随机数生成器可得到。

4、设这四个队分别为A,B,C,D,C(2,4)一共要进行6场比赛,如果A赢了3场,B和C、D3场打平,则A和B、C、D中积分最高的队一起晋级,所以最低得分为2分。0分是不可能晋级的,因为0分意味着其他3个队的积分都在3以上,1分也是不可能晋级的,因为1分意味着输了两场比赛,则必有两个对的得分在3以上。 

5、考虑六位字符000000-999999,共有字符 6位*1000 000个数=6 000 000个字符。0-9这是个字符等概率出现,因此0-9的个数都为6 000 000/10=600 000个。由于前导0不影响1-9的个数,因此自然数0-999 999中,1-9出现的次数均为6 000 000。加上1000000中的那个1,因此最终答案为600 001。 

6、如下:

int BinarySearch(char **ar,int begin,int end,char *v)
{
    int result=-1;
    while(begin <= end)
    {
        int mid=begin+(end-begin)/2;
        if(strcmp(ar[mid],v) > 0)
            end=mid-1;
        else if(strcmp(ar[mid],v) < 0)
            begin=mid+1;
        else
        {
            if(result < mid)
                result=mid;
            begin=mid+1;
        }
    }
    return result;
}
7、参考代码:
bool cmpstr(string s1,string s2) 
{ 
    if (s1.size()!=s2.size())  
        return false; 
    string s3; 
    s3=s1+s1; 
    if(s3.find_first_of(s2,0)!=string::npos) 
        return true; 
    else  
        return false; 
} 

void main(void)  
{   
    string str1="ABCDEFG",str2="CDEFGAB"; 
    if(cmpstr(str1,str2)) 
        cout<<"匹配成功"<<endl; 
    else 
    cout<<"匹配失败"<<endl;    
} 
个人资料
Bingo
等级:9
文章:694篇
访问:38.9w
排名: 1
上一篇: 美团点评湖南研发工程师笔试卷-2013年
下一篇:美团点评研发笔试卷-2013年
猜你感兴趣的圈子:
美团笔试面试圈
标签: len、dest、newhead、maxindex、mid、面试题
隐藏