@dantangfan
2015-01-21T17:14:04.000000Z
字数 15769
阅读 1805
里面大多数问题都是从学习过程中从书上或者网上收集的内容，但是并没有说明出处，麻烦不要散播。谢谢。
int i=1;main(){int i=i;}//能通过编译，但是i是一个未定义值。
main(){int arr[]={6,7,8,9};int *ptr=arr;*(ptr++) += 123;printf(“%d,%d”,*ptr,*(ptr++));}
第三句等价与*ptr += 123;prt++;这个时候ptr指向7,printf中从右往左先计算ptr++。所以最后答案是输出8，8.
sizeof和strlen的区别
（1）sizeof是运算符，strlen是函数
（2）sizeof可以用类型做参数，strlen只能用char*做参数并且以'\0'结尾
（3）数组作为sizeof参数不退化，但作为strlen参数退成指针
（4）sizeof在编译阶段就计算，strlen在运行时候计算
指针和引用的区别
#include <iostream>using namespace std;class A{public:int a;A():a(1){}void print(){cout<<a;}};class B:public A{public:int a;B():a(2){}};int main(int argc, const char *argv[]){B b;b.print();cout<<b.a;return 0;}
B类的a覆盖了A类的a，但是在构造的时候要先构造A类的a，所以输出是12。重点需要说明的是构造函数从最初开始构造，各个类的同名变量没有形成覆盖，都是独立的变量。所以在b.print的时候，b中没有print函数，只有从A中找，找到了print就使用A中的a。
16. 什么是多态
一个接口，多种实现。在运行的过程中才决定调用的函数。允许将父对象设置称为和他的一个或更多的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给他的子对象的特性以不同的方式运作。简单的说就是允许将子类的指针赋值给父类指针。多态是由虚函数实现的。
17. 共有继承和私有继承
c++中继承只能继承public和protected中的属性和方法。如果是私有继承，那么继承下来的属性或者方法都只能在类的内部使用，是子类的private方法或者属性。
公有继承：对派生类来说，基类的public都被继承下来并且是public的，protected也被继承下来，但是是private的。
私有继承：对派生类来说，基类的public和protected都被继承下来，但是是private的。
受保护继承：对派生类来说，基类的public和protected都被继承下来，但是都是protected的
多态的作用：
a隐藏实现细节，使得代码模块化；扩展代码模块，实现代码重用
b接口重用：为了类在继承和派生的时候，保证使用家族中任一类的实例的某一属性的正确调用
代码输出
main(){printf(“%f”,5);printf(“%d”,5.0);}
首先5是int型的，在stack中分配4个字节存放，%f是double（printf中float会自动转换成double），因此在stack中读取8个字节，所以内存访问越界了，会发生什么情况不可预测。而第二个5.0占8字节，由于小段规则，%d只能读取低4字节。就输出0.
值得注意的是，现代编译器gcc等都不会通过编译。
A a;a.func(10);//将会被编译成A::func(&a,10);
看起来和静态函数没有差别，不过，还是有区别的。编译器通常会对this指针做一些优化，因此this指针的传递效率比较高
- this指针并不占用对象的空间。this相当于非静态函数的一个隐匿参数，不占用对象空间。他跟对象之间没有包含关系，只是当前调用函数的对象被它指向而已。所有成员函数的参数，不管是不是隐含的，都不会占用对象空间，只是会占用参数传递时的栈空间或者直接占用一个寄存器。
- this指针是什么时候创建的。this在成员函数的开始前构造，执行结束之后清除。
- this指针存放在何处。他会因编译器的不同而放在不同的地方，可能是堆，栈或者寄存器。
- 我们只有获得一个对象后，才能通过对象获得this指针。this指针只有在成员函数中才有定义，因此你获得一个对象后也不能通过对象使用this指针。所以我们无法知道一个对象的this指针的位置。当然，在成员函数里是可以知道的，直接&this
静态路由和动态路由
静态路由是管理员手动配置的，当网络拓扑结构发生变化的时候需要手动修改信息。在缺省状态下是私有的，不会传播给其他路由器。一般适用于比较简单的网络环境，这种环境中，网络管理员易清楚了解拓扑结构，便于设置。
动态路由是指路由器能自动的建立路由表，并且能根据实际情况自动调整。主要依赖于对路由表的维护和路由器之间的信息交换，适用于大网络
策略路由可以说是一种高级的静态路由，但是又与静态路由不同。普通的静态路由（也包括动态路由）是按照数据包的目的地址来进行路由，而策略路由是按照数据包的源地址来进行路由。在同一台路由器上如果配置了策略、静态、动态三种路由，路由器接口首先对入站的数据包源地址进行判断有没有匹配在此接口上配置的策略路由的数据流，如果有，则按照策略路由的配置转发数据包。如果没有，则按普通数据包情况路由。具体是静态路由协议优先还是动态路由协议优先（去往同一个目的地址根据路由协议的不同有多条路径），要看你在此路由器上定义的管理具体大小，管理距离越小则此种路由协议的可信度越高，则优先选用该种路由协议。而管理距离的默认值又根据各厂家路由器的不同而不同。
网络层和数据链路层
网络层传输的是IP包， 数据链路层传输的是帧。
数据链路层值负责传输数据，不理会格式、内容、编码等。保证传输的可靠性
网络层要负责内容，格式和编码
网络层就像秘书，而链路层就像邮递员。
交换机工作在链路层，路由器工作在网络层，集线器工作在物理层，路由器设备=路由器+交换机
ip地址分类
IP被分为5类(A,B,C)还有D,E他们是留给IAB委员使用的就不说了.
A的范围1.0.0.0~126.255.255.555
B的范围128.1.0.0~191.254.255.255
C的范围192.0.1.0~233.255.254.0
Class Singleton{private:Singleton(){}static Singleton *instance;public:static Singleton *getInstance(){if(instance==NULL)instance = new Singleton;return instance;}};Singleton *S = Singleton::getInstance();
factory（工厂模式）：
看不懂，不看了
10. 数据库范式
1NF：字段不可分
2NF：有主键，非主键字段依赖主键
3NF：非主键字段不能相互依赖
例题：
设有关系模式R（U，F），其中： U={A，B，C，D，E}，F={A→D，E→D，D→B，BC→D，DC→A } （1） 出R的候选关键字 （2） 判断R最高为几级范式？ （3） 若R不是3NF，将R分解为3NF
a在F中我们不难看出C,E没有谁决定它，所以CE一定是候选关键字，可见CE就能决定ABD了，所以主键就是CE
b首先肯定是1NF，简单理解就是F中ABCDE都有；其次也是2NF因为F中不存在部分依赖，也就是没有AB->C,B->C这种形式出现；但是不是3NF，因为F中存在传递依赖。
11. 编译原理和正则表达式
（1）词法分析：词法分析器根据词法规则识别出源程序中各个记号token，每个token代表一类单词lexeme。源程序中常见的记号可分为几类:关键字、标识符、字面量、特殊符号。词法分析输入的是源程序，输出的是识别的记号流。词法分析的任务是把源文件的字符流转换成记号流。
（2）语法分析：根据词法分析识别出记号流中的结构（短语、句子），并构造一颗能反映该结构的语法树。
（3）语义分析：根据语义规则对语法分析树中的语法单元进行静态语义检查，类型检查和转换等。其目的在于保证语法正确的的结构在语义上也是合法的。
（4）中间代码生成：根据语义分析的输出生成中间代码。可以有若干形式，他们的共同特征是与具体机器无关。最常用的就是三地址码，它的一种实现方式是四元式。优点是便于阅读，便于优化
（5）中间代码优化：由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间上都有极大的浪费。
（6）目标代码生成：是编译器的最后一个阶段，需要考虑以下几个问题:计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。目标代码可以有多种形式:汇编语言、二进制代码、内存形式
（7）符号表管理：符号表的作用是源程序中符号的必要信息，并加以合理组织，从而在编译器的各个阶段能对他们进行快速准确的查找和操作。
（8）出错处理：可以分为静态错误和动态错误。所谓动态错误，是指源程序中的逻辑错误，往往发生在运行时，也被称作动态语义错误，如被除数为0，下标越界等。静态错误分为语法错误和静态语义错误。语法错误是指有关语言结构上的错误，如单词拼写、表达式缺少操作数、begin和end不匹配。静态语义错误是指分析源程序时可发现的语义上的错误，如加法的两个变量一个是整数、一个是数组。
抢占式调度和轮询调度
linux僵尸进程如何产生，有何危害，如何避免
一个进程在调用exit结束自己生命的时候其实并没有真正销毁，而是留下一个称为僵尸进程的数据结构，在linux进程状态中，僵尸进程是特殊的一种，它放弃了所有的内存空间，没有代码也不能调度，只在进程列表中保存一个位置。它需要父进程来为他收尸，如果父进程没有使用wait等函数等待子进程结束，它就会一直保存僵尸状态，如果父进程结束，init进程会自动接手这个进程，还是可以为它收尸的。如果父进程是一个不会结束的循环，那子进程就会一直僵尸。我们可以用wait等函数等待子进程返回来避免僵尸
面向对象的三个基本要素和五种主要的设计原则
基本要素：继承、封装、多态
基本原则：
简述DNS解析过程
首先，客户端发出DNS请求翻译ip地址或者主机名，DNS收到请求后：
对三次握手和四次挥手的理解
Epoll机制相关概念(Epoll与Select机制区别)，这个概念许多面试官都会问起. epoll模型及优缺点？
主要有3点，对应于select的3个缺点：1连接数受限 2 查找配对速度慢 3数据由内核拷贝到用户态。
后台开发没能必考！！
各种STL容器的实现方式
vector的容量增长的题目，vector a; push_back八次对象，求总共调用多少次拷贝构造函数。另外问到vecter和set的底层实现
vector初始大小是0,之后可能按照2倍数增长g++/gun下测试，但实际上可能不是这样的，v.capacity()
vector是动态数组，在堆上分配内存，元素连续存放，有保留内存，如果大小减小后，内存不会自动释放。
list双向链表，用链表节点实现
deque双向队列=vector+list
map平衡二叉树/红黑树实现
set红黑树实现，为什么不用hash？首先set不像map的key-value对，它的key和value是相同的。关于set有两种说法，一个是STL中的set用红黑树实现，一个是hash_set用hash table实现。红黑树和hash table最大的不同是树是有结构的。如果单单判断set中的元素是否存在，那么当然hash table显然更合适，因为查找时间是log1。但是STL中的set被强调成集合，涉及到了集合的并set_intersection()，交set_union()，差set_difference()等操作，都需要进行大量的操作，于是树有优势
虚函数问题，析构函数为什么经常被声明为虚函数？析构函数里面能调用虚函数么？
答：为了防止通过父类指针析构子类对象时能正确的调用虚函数。析构函数调用虚函数语法上是没有问题的，但是标准应该是不建议的
tcp状态变迁图
艹，记不住
tcp怎么实现流控制和拥塞控制机制
ack=1代表确认字段。链接建立的时候接收方会告诉发送方接收窗口大小，协商好窗口大小后，发送符合尺寸的字节流并等待对方回应，发送方根据回应信息改变窗口尺寸大小，增加或者减小发送未得到确认的字节流的字节数。调整过程包括：如果发生拥塞，发送窗口缩小为原来的一半（慢启动），同时将超时重传的时间变为原来的两倍。tcp的窗口机制保证了数据传输的可靠性和流量控制。
差错控制：校验和（跟udp一样），确认（ack报文不需要确认，当收到一个序列号比期望要大时马上发ack让发送端重传，收到重复的序列号马上ack解决ack丢失问题，丢失的报文到达的时候马上ack表示已经收到丢失的），重传（超时、发送端收到连续的三个ACK）。
16进制字串转10进制字符串
先把16进制转换成2进制，再把2进制转换成10进制（需要不能2进制反转）。
16转2很简单，2进制转10
//思路是每次向右一位的时候先整体乘以2,在看这一位是不是1.a[n]={0},b[4*n]=”0011111111111111111111111111101”;len=1;int j,i;for(i=0;i<n;i++){for(j=0;j<len;j++);a[j]*=2;j=0;while(a[j]!=0||j<len){if(a[j]>=10){a[j] = a[j]/10;a[j+1]+=1;}j++;}len = j;if(b[i]==1)a[0]+=1;}//得到的a是倒序的，个位是a0
template<class T>class vector{pirvate:T *array;int size;int capacity;public:vector();vector(vector &);~vector();bool push_back(T);bool pop_back();bool empty();T & operate[](T);};template<class T>vector<T>::vector(const vector<T> v);class string{private:char *data;public:string():data(new char[1]){}string(const char *str):data(new char[strlen(str)+1]){strcpy(data,str);}string(const string &str):data(new char[str.length()+1]){strcpy(data,str.c_str());}~string(){delete [] data;}string &operate=(const string &src){swap(src);return *this;}size_t size(){return strlen(data);}const char *c_str(){return data;}void swap(string &str){std::swap(data,str.data);}char & operate[](int i){return data[i];}};
几个要点:
a。只在构造函数中用new，析构函数中用delete
b。每个函数都只有一两行代码， 没有条件判断
c。析构函数不必建厂data是否是NULL
e。拷贝构造函数没有检查str的合法性。这里在初始化列表中就用了str，因此在函数内部用assert没有意义
const int a=1;int *b = (int *)&a;*b = 3;printf(“%d,%d”,a,*b);
使用gcc的时候输出3,3；使用g++的时候输出1,3；
区别在于：c语言把const int当成只读的变量，既然是变量，那么在内存中就会有储存空间，并且可以通过指针改变他的值。而c++当成常量，编译器会使用常数直接替换掉他比如cout<
如何提高cache的命中率
智能指针的设计（垃圾回收机制）
首先new和delete要成对出现，而且delete要自动调用，那么就只能考class中的构造函数和析构函数
但是多个指针可以指向同一个数据，于是我们就使用引用计数的方式来解决多个指针指向同一数据的问题。
定义一个类来解决引用指针的问题（这个数据是要被多个smart指针共享的数据），所以需要设置成友员,由于不会有除了智能指针之外的其他调用，所以他的所有成员和方法都可以是私有的。
class _counter{template<class T> friend class SmartPointer;_counter(int u):use(u){}~_counter(){};int use;};在smartpointer类中保留counter的指针template<class T>class SmartPointer{private:T *pt;_counter *pc;public:SmartPointer(T *t):pc(new _count(1)),pt(t){};SmartPointer(SmartPointer<T> &rhs){pc = rhs->pc;pt = rhs->pt;pc->use +=1;}~SmartPointer(){pc->use -=1;if(pc->use==0){delete pc;delete pt;}}SmartPointer & operator=(SmartPointer<T> &rhs){if(rhs==*this)return *this;pc = rhs.pc;pt = rhs.pt;pc->use += 1;return *this;}T &operator *(){return *pt;}T *operator ->(){return pt;}}//比如说我们有一个有指针的类class HasPtr{int *p;public:HasPtr(int n):p(new int[n]){}~HasPtr(){delete []p;}};//使用的时候SmartPointer<HasPtr> psp(new HasPtr(3));SmartPointer<HasPtr> npsp(p);//就可以得到如下内存结构
内存池
template<class T>class CmemoryPool{public:CmemoryPool(unsigned int nIterCount = 32){ExpandFreeList(nIterCount);}~CmemoryPool(){CmemoryPool<T> *pNesxt = NULLfor(pNext = m_pFreeList;pNext!=NULL;pNext = m_pFreeList){m_pFreeList = m_pFreeList->next;delete [](char *)pNext;}}void *Alloc(){if(m_pFreeList==NULL)ExpendFreeList();//从空表头获取空间CmemoryPool<T> *pHead = m_pFreeList;m_pFreeList = m_pFreeList->next;return pHead;}void Free(void *p){CmemoryPool<T> *pHead = static_cast<CmemoryPool<T>*>(p);pHead->m_pFreeList = m_pFreeList;m_pFreeList = pHead;}protected://分配内存到list中void ExpandFreeList(unsigned nItemCount = EXPANSION_SIZE){unsigned int nSize = sizeof(T) > sizeof(CMemoryPool<T>*) ? sizeof(T) :sizeof(CMemoryPool<T>*);CMemoryPool<T>* pLastItem = static_cast<CMemoryPool<T>*>(static_cast<void*>(newchar[nSize]));m_pFreeList = pLastItem;for(int i=0; i<nItemCount-1; ++i){pLastItem->m_pFreeList = static_cast<CMemoryPool<T>*>(static_cast<void*>(newchar[nSize]));pLastItem = pLastItem->m_pFreeList;}pLastItem->m_pFreeList = NULL;}private:CMemoryPool<T>* m_pFreeList;};
Struct Node{int data;Node *left;Node *right;};Node * ArrayToAVL(int arr[], int n){return helper(arr,0,n-1);}Node *helper(int arr[], int start, int end){if(start>end) return NULL;int mid=start+(end-start)/2;Node *node = new Node(arr[mid]);node->left=helper(arr,start,mid-1);node->right=helper(arr,mid+1,end);return node;}
实现线程安全的队列
旋转数组二分查找。方法一：第一次二分找到关键值，第二次再二分。方法二，判断出数组的单调性，根据第一个和最后一个元素大小判断要查找的数在那个部分，直接从中间二分。
快排最坏情况优化到nlogn
memcpy实现
int memcmp(const void *s, const void *t, unsigned int count){assert((s!=NULL)&&(t!=NULL));while( *(char *)s && *(char *)t &&*(char *)s==*(char *)t&&count--){s = (char *)s +1;t = (char *)t+1;}return (*(char *)s-*(char*)t);}void *memcpy(void *dest, const void *src, unsigned int count){assert((s!=NULL)&&(t!=NULL));void *addr = dest;while(count--){*(char *)dest = *(char *)src;dest = (char *)dest +1;src = (char *)src+1;}return addr;}
i++和++i哪个效率搞，怎么实现
在内置数据类型的情况下都一样，在自定义数据的情况下++i效率高。
自定义数据类型的情况下，++i返回对象的引用，i++总是要创建一个临时对象，在退出的时候还要销毁它，而且返回临时对象还要调用其拷贝构造函数
malloc的实现机制
它将一个可用的内存块连接成一个长长的列表所谓空闲链表。调用malloc函数的时候，它沿着链接表找到一个大到足以满足用户请求的内存块。然后将内存块一分为二（其中一块与用户请求的大小相同，另一块就是剩下的）。接下来将内存传给用户，并将剩下的（如果有的话）返回到链表上。调用free的时候他将用户释放的内存连接到空闲链表上。最后，链表会被切成很多的小内存碎片，如果用户申请一个较大的内存，那么可能没有能满足要求的片段。于是malloc函数请求延时，并开始在空闲链表上翻箱倒柜查各内存片，对他们进行整理，将相邻的小空闲快合并成较大的。