首页 分类 维基 链接 关于
SITEMAP订阅

百度笔试面试.

1.char a=255;
sizeof(++a)=?（1）
a=?（-1）

2.删除掉cpp文件中的所有注释

//删除掉src中的注释，保存到dst，dst长度为len
    //未考虑字符串中有特殊字符的情况
    void DeleteComment(const char *src,char *dst,int len)
    {
        char *s=(char *)src;
        int i=0;
        while (*s)
        {
            //printf("%c\n",*s);
            if(*(s+1) && *s=='/'  && *(s+1)=='/')
            {
                printf("注释1()\n");
                s+=2;
                printf("掠过");
                while (*s && *s!='\n')
                {
                    printf("%c",*s);
                    s++;
                }
                printf("\n");
                if(!*s)
                    return;
                //s++;
            }
            else if(*(s+1) && *s=='/'  && *(s+1)=='*')
            {
                printf("注释2()\n");
                s+=2;
                printf("掠过");
                while (*s && *(s+1) && !(*s=='*'  && *(s+1)=='/'))
                {
                    printf("%c",*s);
                    s++;
                }
                printf("\n");
                if(!*s || !*(s+1))
                    return;
                s++;
            }
            else if(i<len)
                dst[i++]=*s;
            s++;
        }
        dst[i++]=0;
    }

    void Test()
    {
        int len=0;
        char *src=0;
        char *dst=0;
        FILE *fp=fopen("1.cpp","r");

        CHECK(fp);
        fseek(fp,0,2);
        len=ftell(fp);
        printf("文件长度:%d\n",len);
        printf("文件内容:\n");
        src=new char[len+1];
        fseek(fp,0,0);
        fread(src,len,1,fp);
        src[len]=0;
        printf(src);

        dst=new char[len+1];
        DeleteComment(src,dst,len);
        printf("\n======================================\n");
        Trace(dst);

        delete []src;
        delete []dst;
    }

 

 3.用脚本（bash）统计
两个文本文件的相同的行，
？？
第一文件有而第二文件无的行
？？，
两个文件的补集。
 cat file1 file2 | sort | uniq > 1.txt
4.设计一个简化的bbs系统：多用户，可发表主题，回复，同主题阅读，分不同的版面，为每一用户判断某一文章是否已读，等。
5.

面试：
1.判断一个链表是否存在回路?
给指针加一个标志域，如访问过则置1.当遍历到标志为1的项说明有了回路。

定义2个指针，一快(fast)一慢(slow)，即：从头向后遍历过程中，每循环一次，快指针一次向后移动2个元素，慢指针移动一个元素，每次判断(   fast==slow   ||   slow==fast->nest   ),如果成立，说明慢指针赶上了快指针，则为循环链表，否则，如果有一个指针到达NULL，则为单链表。

重新做一个链表，用于存放所有原链表中的节点，插入节点时按按地址顺序插入，  
  如果出现相同的地址就说明是死链，结束查询....

2.两个单向链表，有可能交叉，请设计算法判断是否交叉，如果交叉，返回交叉点！算法复杂度o(n)
两个链表最后是合并成一个 而不是交叉 所以：
（1）先找到p1，p2的最后一个节点，同时记录节点数量a，b；
（2）判断最后一个节点是否相同，

如果不相同则没相交。
如果相同 则从第一个节点和|a-b|+1个节点开始比较 看是否相等 不相等都寻找下一个节点
直到找到交叉点
3.硬盘文件系统设计，及磁盘整理算法
4.Hash表
5.php+MySQL
6.问参加过ACM/数学建模没有
7.多边形标记问题：
判断点是否在多边形内的问题？
我知道有两种方法：  
  1。累计角度法  
      过此点连接多边形的每一顶点，各相邻边角度之和为360度，则此点在多边形内。  
  否则为0度，在多边形外部。  
   
  2。射线法  
      过此点向任意角度发一条射线，若与多边形的各条边交点个数之和为偶数，则此点在  
  多边形之外，否则在多边形之内。  
      若有交点为多边形顶点则要另选一条射线重算。  
   
   
  请问哪种方法好一点（时间复杂度）？  
方法一对凹多边形可能会出现问题吧。
8.多线程

同步互斥的概念
同步：只有a做完才能做b。  
  互斥：a和b只是在一个时间做一个。  
   
  可用p,v操作来实现。

相交进程之间的关系主要有两种，同步与互斥。所谓互斥，是指散步在不同进程之间的若干程序片断，当某个进程运行其中一个程序片段时，其它进程就不能运行它们之中的任一程序片段，只能等到该进程运行完这个程序片段后才可以运行。所谓同步，是指散步在不同进程之间的若干程序片断，它们的运行必须严格按照规定的某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。  
   
  显然，同步是一种更为复杂的互斥，而互斥是一种特殊的同步。

例:  
      ...  
      s=1;  
      i=0;  
      cobegin  
          p1();  
          p2();  
      endbegin  
   
      p1(){  
          while(未完成){  
              p(s);  
              i++;  
              printf("%d",i)；  
              v(s);  
            }  
        }  
       
        p2(){  
            while(未完成){  
                  p(s);  
                  i--;  
                  printf("%d",i)；  
                  v(s);  
              }  
      }  
  p1(),p2()是两个进程。i++和i--分别是两个程序片断。在没有执行完p1（）是不允许执行p2()的。这里的p1()和p2()并不是指一个完整的进程，只是两进程的公共资源（临界资源）.

  当程序1调用程序2时，程序1就停下不动，直到程序2完成回到程序1来，程序1才继续下去，这就是所谓的“synchronous”,即同步。如果程序1调用程序2后，径自继续自己的下一个动作，那么两者之间就是所谓“asynchronous”，即异步。Win32   API中的SendMessage()就是同步行为，而PostMessage()就是异步行为。   
  同步机制有critical   sections(关键区域、临界区域），mutex(互斥器），semaphore(信号量），event(事件）。   
  在同步机制中，critical   sections是指一小块“用来处理一份被共享之资源”的程序代码，这里所指的资源，并不是指来自.RES(资源文件）的Windows资源，而是广义的指一块内存，一个数据结构，一个文件，或任何其他具有“使用之排他性”的东西。也就是说，资源每一次（同一时间）只能被一个线程处理。  
  mutex的用途和critical   sections非常类似，但是它牺牲速度已增加弹性。   
  其它两个我就不再说了，这些在《Win32多线程程序设计》中第四章同步机制中有详细的讨论和例子。


  “临界”   该段代码属于原子操作   
  “同步”   一般是双方协调，如一方等待  
  “互斥”   不能一起执行

  “临界状态”   处于临界状态的代码段一个时间段只允许一个进程访问   
  “同步”   多个进程之间协调对某些临界资源的访问顺序  
  “互斥”   当某个线程访问某个临界资源的时候，不允许别的线程同时访问此资源  
怎样才能实现线程的同步与互斥？ 

EnterCriticalSection     LeaveCriticalSection  
  CreateSemaphore   ReleaseSemaphore   WaitForSingleObject  
  SetEvent   WaitForSingleObject   Mutex...
CSyncObject是MFC中解决互斥同步问题的基础类  
常用4种  
  关键代码段——单进程内  
  互斥量——互斥  
  信号灯——充许设定一个以上共享资源  
  事件内核对象——灵活  

以下面试题不是此次百度的
1.全局变量和局部变量有什么区别？实怎么实现的？操作系统和编译器是怎么知道的？
2.请问交换机和路由器分别的实现原理是什么？分别在哪个层次上面实现的？
3.请你详细的解释一下IP协议的定义，在哪个层上面，主要有什么作用？ TCP与UDP呢？
4.以下代码有什么问题？
struct Test
{
Test( int ) {}
Test() {}
void fun() {}
};
void main( void )
{
Test a(1);
a.fun();
Test b();
b.fun();
}
5.写一个函数，将其中的t都转换成4个空格。

都是华为的老题

1、全局变量是整个程序都可访问的变量，谁都可以访问，生存期在整个程序从运行到结束(在程序结束时所占内存释放)，而局部变量存在于模块(子程序，函数)中，只有所在模块可以访问，其他模块不可直接访问，模块结束(函数调用完毕)，局部变量消失，所占据的内存释放。
全局变量分配在全局数据段并且在程序开始运行的时候被加载. 局部变量则分配在堆栈里面。

2、交换机用在局域网中，交换机通过纪录局域网内各节点机器的MAC地质(物理地址)就可以实现传递报文,无需看报文中的IP地质。路由器识别不同网络的方法是通过识别不同网络的网络ID号(IP地址的高端部分)进行的，所以为了保证路由成功，每个网络都必须有一个唯一的网络编号。路由器通过察看报文中IP地址，来决定路径，向那个子网(下一跳)路由，也就是说交换机工作在数据链路层看MAC地址，路由器工作在网际层看IP地质
但是由于现在网络设备的发展，很多设备既有交换机的功能有由路由器的功能(交换试路由器)使得两者界限越来越模糊。
3、IP协议是网络层的协议，它实现了Internet中自动路由的功能，即寻径的功能，TCP协议是一个传输性的协议它向下屏蔽了IP协议不可靠传输的特性，向上提供一个可靠的点到点的传输，UDP提供的是一种无连接的服务,主要考虑到很多应用不需要可靠的连接，但需要快速的传输
4、
Test b();//定义了一个函数

 

Published on Sep 14, 2007 in categories

Powered by Jekyll and Theme by solid

本站总访问量次