当前位置 > 职来职往 > 职业指导

程序员面试笔试宝典

供稿人:  发布时间:2015-08-19 02:35:53  浏览次数:6  字体:



1.extern的作用

  自己理解:应该需要区分extern在C语言中和C++语言中的作用,C语言中extern声明的函数和变量可以被该文件外部模块引用,C++语言中除了该作用还可以声明extern “C”声明一段代码编译连接的方法为C语言的方法。

  参考:其实extern的百度词条解释的很清楚,具体的也是跟我上面自己理解差别不是很大。

  (a) extern是C/C++语言中声明函数和全局变量作用范围(可见性)的关键字,该关键字告诉编译器,其声明的函数和变量在本模块或其他模块中使用(通常,在模块的头文件中对本模块提供给其它模块引用的函数和全局变量以关键字extern声明。)

  (b) 被extern “C”修饰的变量和函数是按照C语言的方式编译和链接的。(C语言不支持函数重载,所以函数的C++和C的编译方式不同,这一句的作用就是实现C++和C及其他语言混合编程)

  extern的使用问题

  (1)extern 变量

  在一个源文件里定义了一个数组:char a[6];在另外一个文件里用下列语句进行声明:extern char *a; 问:这样可以吗?

  答案与分析:

  不可以,程序运行时会告诉你非法访问。原因在于,指向类型 char的指针并不等价于类型char的数组。extern char *a声明的是一个指针变量而不是一个字符数组,因此,与实际的定义不同,从而造成运行时非法访问。应将声明改为 extern char a[];

  (2)单方面修改extern函数原型

  当函数提供方面单方面修改函数原型时,如果使用不知情继续沿用原来的extern声明,这样编译时编译器不会报错。但是在运行过程中,因为少输入或者是多输入参数,往往会造成系统错误,这种情况如何解决?

  答案与分析:目前业界针对这种情况的处理没有一个很完美的方案,通常的做法是提供方在自己的xxx_pub.h 中提供对外部接口的声明,然后调用方include该头文件,从而省去extern这一步。避免错误

  (3)extern ’C‘

  在C++环境下使用C函数的时候,常常会出现编译器无法找到obj模块中的C函数定义,从而导致链接失败的情况,应该如何解决这种情况呢?

  答案与分析:C++在编译的时候,为了解决函数的多态问题,会将函数名和参数联合起来生成一个中间的函数名称,而C语言则不会,因此会造成链接时找不到对应函数的情况,此时C函数就需要用extern ’C‘进行链接指定,这告诉编译器,请保持我的名称,不要给我生成用于链接的中间函数名。

  (4)extern函数声明

  常见extern放在函数前面成为函数声明的一部分,那么,C语言的关键字extern在函数的声明中起什么作用?

  答案与分析:如果函数的声明中带有关键字extern,仅仅是暗示这个函数可能在别的源文件里定义,没有其他作用。

  (5)extern和static

  A、extern表明该变量在别的地方已经定义过了,在这里要使用那个变量

  B、static表示静态的变量,分配内存的时候,存储在静态区,不存储在栈上面

  static作用范围是内部连接的关系,和extern有点相反,它和对象本身是分开存储的,extern也是分开存储的,但是extern可以被其他的对象用extern引用,而static不可以,只允许对象本身用它。具体的差别,首先static和extern不能同时修饰一个变量;其次,static修饰全局变量声明与定义同时进行;最后,static修饰全局变量的作用域只能是本身的编译单元,也就是说它的“全局”只对本编译单元有效,其他编译单元则看不到它。

  一般定义static全局变量时,都把它放在源文件中而不是头文件

  (6)extern和const

  C++中const修饰的全局常量具有跟static相同的特性,它们只能作用于本编译模块中,但是const可以与extern连用来声明该常量可以作用于其他编译模块中

  2.strstr()函数的作用

  strstr()函数的原型一般为extern char * strstr(const char *src , const char *dest) , 其作用就是判断字符串dest是否是src的子串,如果是,则返回目标字符串在源字符串中第一次出现的位置(地址,返回的是个指针)。否则,返回NULL

  3.windows线程优先级问题( 进程和线程的区别和联系 )

  参考网址【3】 进程和线程关系及区别

  (a)进程,是并发执行的程序在执行过程中分配和管理资源的基本单位,是一个动态概念。每个进程都有个自己的地址空间,即进程空间或(虚空间)。进程至少有5种基本状态,它们是:初始态、执行态、等待状态,就绪状态,终止状态。

  (b)线程,在网络或多用户环境下,一个服务器通常需要接收大量且不确定数量用户的并发请求,为每一个请求都创建一个进程显然是行不通的,――无论是从系统资源开销方面或是响应用户请求的效率方面来看。因此,操作系统中线程的概念便被引进了。线程,是进程的一部分,一个没有线程的进程可以被看作是单线程的。线程有时又被称为轻权进程或轻量级进程,也是 CPU 调度的一个基本单位。

  通常一个进程可以包含若干个线程,它们可以利用进程所拥有的资源。进程是系统进行资源分配和调度的一个独立单位,线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。线程自己基本不拥有系统资源,只拥有一些在运行中必不可少的资源(如程序计数器,一组寄存器和栈),线程可与同属于一个进程的其他线程共享进程所拥有的全部资源。

  线程和进程区别归纳:

  地址空间和其他资源:进程间互相独立,同一个进程的各线程共享。

  通信:进程间通信IPC,线程间可以直接读写进程序数据段(如全局变量)来进行通信-需要进行同步和互斥的辅助。

  调度和切换:线程上下文切换比进程上下文切换快速,高效。

  多线程的OS中,进程不是一个可执行的实体。

  4.多方法交换x与y的值

  (1)不借助第三方变量交换x和y的值 (x=x+y,y=x-y;x=x-y)

  (2)用函数实现,参数是引用 void swap( int &x,int &y )

  (3)用函数实现,参数是指针 void swap( int *x,int *y)

  5.指针的自加与引用

  假设指针指向的是一个整型数组(int a[]={1,2,3,4,5}; int *p = a;),那么,指针p的地址是数组a的首地址,而指针p++,自加之后,p所指的是a[1]的地址。

  指针的引用相当于传递的是:指针的指针,这样,指针的数值可以进行改变。

  6.前置++与后置++

  对于迭代器和其他模板对象使用前缀形式 (++i) 的自增, 自减运算符.,理由是 前置自增 (++i) 通常要比后置自增 (i++) 效率更高。

  7.inline的作用

  inline函数不像正常函数在调用时存在压栈和call的操作,它会把程序代码直接嵌入到调用代码段中,也就是说使用inline函数会增大二进制程序的体积,但是会使执行速度加快。

  同时,编译期间可以对参数进行强类型的检查,这是inline优于宏的一个方面。

  详细的解释见 关于C/C++中的inline

  8.二维数组的表示

  (1)数组的形式 int a[3][5];

  (2)指针的形式 int *p = malloc(sizeof(int )*3*5);

  9.ifndef的作用

  条件编译的语法,一般情况下,源程序中所有的行都参加编译。但是有时希望对其中一部分内容只在满足一定条件才进行编译,也就是对一部分内容指定编译的条件,这就是“条件编译”。有时,希望当满足某条件时对一组语句进行编译,而当条件不满足时则编译另一组语句。

  关于在头文件中的详细应用,看 参考网址[5] #ifndef/#define/#endif

  10.KMP算法

  字符串匹配的高级算法(具体的讲解和实现见blog 字符串匹配(KMP算法 含代码))

  11.函数调用方式

  (1)函数调用介绍

  调用函数的时候,计算机常用栈来存储传递给函数的参数。

  栈是一种先进后出的数据结构,栈有一个存储区、一个栈顶指针。栈顶指针指向堆栈中第一个可用的数据项(被称为栈顶)。用户可以在栈顶上方向栈中加入数据,这个操作称为入栈(push),压栈后,栈顶自动变成新加入数据项的位置,栈顶指针也随之修改。用户也可以从堆栈中取走栈顶,称为出栈(pop),弹出栈后,栈顶下的一个元素变成栈顶,栈顶指针随之修改。

  函数调用的时候,调用者依次把参数压栈,然后调用函数,函数被调用以后,在堆栈中取得数据,并进行计算。函数计算结束以后,或者是调用者、或者函数本身修改堆栈,使堆栈恢复原状。

  参数传递中,有两个重要的问题需要说明:

  A、当参数个数多于一个时,按照什么顺序把参数压入堆栈

  B、函数调用后,由谁来把堆栈恢复原状。

  (2)函数调用的时候主要有几种调用方法,主要分为C式,Pascal式。在C和C++中C式调用是缺省的,类的成员函数缺省调用为 _stdcall。

  __cdecl 堆栈由调用者清除 参数从右至左的顺序压入堆栈内函数名自动加前导下划线

  __stdcall 堆栈由被调用者清除 参数从右至左的顺序压入堆栈内函数名自动加前导下划线,后面紧跟着一个@,其后是参数的尺寸

  __fastcall 堆栈由被调用者清除 部分参数保存在寄存器中,然后其他的压入堆栈内函数名自动加前导下划线,后面紧跟着一个@,其后是参数的尺寸

  thiscall(非关键字) 参数从右向左压入栈。如果参数个数确定,this指针通过ecx传递给被调用者;如果参数个数不确定,this指针在所有参数亚茹栈后被压入栈。参数个数不定的,由调用者清理堆栈,否则由函数自己清理堆栈。

  12.重载函数

  函数重载是指在同一作用域内,可以有一组具有相同函数名,不同参数列表的函数,这组函数被称为重载函数。不能利用返回类型进行重载!类中函数const和非const可以进行重载,其实原理是利用this指针的类型是const和非const进行重载,其实原理就是参数类型不同,const指针or const引用调用的为const版本的函数~更多函数重载的知识。

  13.构造函数和析构函数

  在new的时候,做了三件事

  (1)调用::operator new分配所需内存

  (2)调用构造函数

  (3)返回指向新分配并构造的对象的指针

  在的时候,做了两件事

  (1)调用析构函数

  (2)调用::operator 释放内存

  C++的构造函数和析构函数

  C++中的new operator new 与placement new

  在子类和父类中,构造和析构函数的调用顺序

  析构函数的调用顺序是先基类在派生类,构造函数的调用顺序是先派生类再基类

  构造函数和析构函数 - `leisure - 博客园 http://www.cnblogs.com/chenyang920/p/5267138.html

  虚拟析构函数的使用场景是指向父类的指针实则为子类指针,调用的时候使用虚拟析构函数,防止部分内存泄露。

  构造函数不能声明为虚拟函数,因为对象的虚拟函数表的指针其实是在构造函数内编译器添加完成的代码,所以在构造函数执行之前无法访问到虚拟函数表的。

  14.合并两个有序链表

  类似归并排序,两个指针归并即可。 两个有序单链表的合并

  15.100亿条记录的文本文件,取出重复数最多的前10条

  这个问题关于海量数据的处理(具体的实现。。。)

  十道海量数据处理面试题与十个方法大总结

  360 php 面试题 - 开源中国社区 http://www.oschina.net/question/163919_61165?sort=time&#answers

  大数据处理--hash的使用 - bluesky的日志 - 网易博客 http://zhangyongbluesky.blog.163.com/blog/static/183194162012525952318/

  【程序员面试宝典】有1千万条短信,找出重复出现最多的前10条_Leora_新浪博客 http://blog.sina.com.cn/s/blog_7124c26901014zcl.html

  16.设计一个双向链表,并且提供一个可根据值删除元素的函数

  STL(Standard Template Library 标准模板库)中的list底层及为双链表实现。

  C++ List(双向链表)

  双向循环链表的实现(C)

  17.二叉树的多种遍历算法实现

  有个blog 写的非常详细,先是介绍了数与二叉树,然后写了非常详细的代码

  先中后序遍历,广度优先遍历,深度优先遍历

  [数据结构与算法]二叉树的多种遍历方式 - SAP师太 - 博客园

  http://www.cnblogs.com/jiangzhengjun/p/4289830.html

  18.有读和写的两个线程和一个队列,读线程从队列中读数据,写线程往队列中写数据

  生产者和消费者模型:

  使用信号灯和互斥量。

  19.stack,heap,memory-pool

  Stack, Heap, Pool - 推酷 http://www.tuicool.com/articles/BvQrUvz

  在C++中,有三种内存分配的方式:stack、heap、custom written pool

  Heap and Stack in programming - Paul_ss的专栏 - 博客频道 - CSDN.NET http://blog.csdn.net/paul_ss/article/details/8818368

  The memory a program uses is typically divided into four different areas:

  The code area, where the compiled program sits in memory.

  The globals area, where global variables are stored.

  The heap, where dynamically allocated variables are allocated from.

  The stack, where parameters and local variables are allocated from.

  20.TCP的流量控制和拥塞控制机制

  流量控制与拥塞控制

  网络拥塞现象是指到达通信子网中某一部分的分组数量过多,使得该部分网络来不及处理,以致引起这部分乃至整个网络性能下降的现象,严重时甚至会导致网络通信业务陷入停顿,即出现死锁现象。拥塞控制是处理网络拥塞现象的一种机制。

  流量控制。数据的传送与接收过程当中很可能出现收方来不及接收的情况,这时就需要对发方进行控制,以免数据丢失。

  流量控制用于防止在端口阻塞的情况下丢帧,这种方法是当发送或接收缓冲区开始溢出时通过将阻塞信号发送回源地址实现的。流量控制可以有效的防止由于网络中瞬间的大量数据对网络带来的冲击,保证用户网络高效而稳定的运行。

  TCP是Internet上通用的传输层协议之一,是目前应用最广泛的传输控制协议,其核心是拥塞控制机制。基于Internet的交换机的通信信道、处理速度及缓冲存储空间通常是网上所有主机共享的资源,也是网络系统潜在的瓶颈。随着信源主机数以及信源业务端业务量的不断增多,瓶颈处就有可能发生资源竞争,从而导致网络拥塞。TCP的一个重要组成部分是执行拥塞控制和拥塞恢复的算法集合。TCP拥塞控制算法的目标是最大限度利用网络带宽,同时不产生数据流传输中的拥塞现象。因此,自从上个世纪80年代出现第一次拥塞崩溃以来,TCP拥塞控制策略就在不断地进行完善和改进。

  2. 传统的TCP拥塞控制机制

  传统的TCP中的拥塞控制机制主要是基于Van Jacobson提出的"慢启动"算法、"拥塞避免"算法和一个用于估计周转RTT(round trip time)的算法。

  慢启动算法通过观察到新分组进入网络的速率应该与另一端返回确认的速率相同而进行工作。慢启动为发送方的TCP增加了另一个窗口:拥塞窗口(congestion window), 记为cwnd。当与另一个网络的主机建立TCP连接时,拥塞窗口被初始化为1个报文段(即另一端通告的报文段大小)。每收到一个ACK,拥塞窗口就增加一个报文段(cwnd以字节为单位,但是慢启动以报文段大小为单位进行增加)。发送方取拥塞窗口与通告窗口中的最小值作为发送上限。拥塞窗口是发送方使用的流量控制,而通告窗口则是接收方使用的流量控制。发送方开始时发送一个报文段,然后等待ACK。当收到该ACK时,拥塞窗口从1增加为2,即可以发送两个报文段。当收到这两个报文段的ACK时,拥塞窗口就增加为4,这是一种指数增加的关系。在某些点上可能达到了互联网的容量,于是中间路由器开始丢弃分组。拥塞避免算法是一种处理丢失分组的方法。该算法假定由于分组受到损坏引起的丢失是非常少的(远小于1%),因此分组丢失就意味着在源主机和目的主机之间的某处网络上发生了拥塞。有两种分组丢失的指示:发生超时和接收到重复的确认。拥塞避免算法和慢启动算法是两个目的不同、独立的算法。但是当拥塞发生时,我们希望降低分组进入网络的传输速率,于是可以调用慢启动来作到这一点。在实际中这两个算法通常在一起实现。1990年出现的TCP Reno版本增加了"快速重传"算法、"快速恢复"算法,避免了当网络拥塞不够严重时采用"慢启动"算法而造成过大地减小发送窗口尺寸的现象。

  3. 拥塞控制的四个阶段

  a.慢启动阶段(slow start):发送方一开始便向网络发送多个报文段,直至达到接收方通告的窗口大小为止。当发送方和接收方处于同一个局域网时,这种方式是可以的。但是如果在发送方和接收方之间存在多个路由器和速率较慢的链路时,就有可能出现一些问题。一些中间路由器必须缓存分组,并有可能耗尽存储器的空间。

  b.拥塞避免阶段(congestion avoidance):当发现超时或收到3个相同ACK确认帧时,则表示有丢包事件,此时网络已发生拥塞现象,此时要进行相应的拥塞控制。将慢启动阈值设置为当前拥塞窗口的一半;如检测到超时,拥塞窗口就被置为l。如果拥塞窗口小于或等于慢启动阈值,TCP重新进人慢启动阶段;如果拥塞窗口大于慢启动阈值,TCP执行拥塞避免算法。

  c.快速重传阶段(fast retransmit):当TCP源端收到到三个相同的ACK副本时,即认为有数据包丢失,则源端重传丢失的数据包,而不必等待RTO超时。同时将ssthresh设置为当前cwnd值的一半,并且将cwnd减为原先的一半。

  d.快速恢复阶段(fast recovery) :当"旧"数据包离开网络后,才能发送"新"数据包进入网络,即同一时刻在网络中传输的数据包数量是恒定的。如果发送方收到一个重复的ACK,则认为已经有一个数据包离开了网络,于是将拥塞窗口加1。

  TCP的流量控制就是让发送方的发送速率不要太快,让接收方来得及接收。利用滑动窗口机制可以很方便的在TCP连接上实现对发送方的流量控制。TCP的窗口单位是字节,不是报文段,发送方的发送窗口不能超过接收方给出的接收窗口的数值。

  所谓的拥塞控制为防止过多的数据注入到网络中,这样可以使网络中的路由器或链路不致过载。拥塞控制索要做的都有一个前提,就是网络能承受现有的网络负荷。流量控制往往指点对点通信量的控制,是一个端到端的问题。因特网建议标准RFC2581定义了进行拥塞控制的四种算法,即慢开始(Slow-start),拥塞避免(Congestion Avoidance)快重传(Fast Restrangsmit)和快回复(Fast Recovery)。

来源:

版权所有:Copyright© 2012 南京工程学院 通信工程学院学生工作办公室

南京市江宁区弘景大道1号·至浩苑信息楼 TEL:025-86118888 技术支持:南京友博网络科技有限公司