C++笔试题目。

1.算法的几个概念：时间复杂度，空间复杂度等等。

2.采用链地址法处理长度的时候，哈希表查找成功的平均长度与哪些因素有关？

哈希表的装填因子有关。

装填因子= 表中填入的记录数/哈希表的长度。

3.二叉树节点的计算：

  二叉树中度为1的节点有8个，度为0的节点有3个，问这颗二叉树总共有多少节点？

  对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。

  所以度为2的节点个数为3-1 = 2，那么总共的结点个数就是3+2+8 = 13。

  顺便复习一下完全二叉树的计算。

  完全二叉树有一个特点，就是度为1的节点数要么为1，要么为0。可以自己画出图来看看。

  问题：如果设一棵完全二叉树共有500个结点，则在该二叉树中有多少个叶子结点？

  设叶子节点数为n0,度为2的节点数为n0 - 1,又因为是完全二叉树，所以n1 = 1或者0

   n0 + n1 + n2 = 500，带入 2n0 - 1 + n1 = 500,故n1 = 1,n0 = 250, n2 = 249。 

5.最小生成树的问题，节点个数计算问题。

6.在序列有序的情况下，快速排序的时间复杂度是多少？

  O(n^2)。

7.网卡完成那一层的功能？

     网卡工作在物理层和数据链路层的MAC子层。

     http://leehlom.blog.163.com/blog/static/241206962008112775913541/

8.模板函数的使用。

   template <typename T>

   T add(T x, T y){

    return x + y;

}

 A.add(5,2) 

 B.add(5.2,2.2)

 C.add<float>(5.2,2)

 D.add(5.2,2)

 D是错误的，因为编译器知道要特化哪一个了。

8.构造函数可以重载么？析构函数可以重载么？

构造不重载，怎么实现多样化？

析构怎么重载，没有参数。

10.C++静态成员和非静态成员有什么区别？

   1)静态变量是属于类的,只能用classname::来调用.而非静态是属于对象的,必须通过对象

来调用.

    2)如果在函数中声明一个静态变量的话,它存储在非函数的活动区.就是它不随函数调用的

结束而释放内存空间,所以它也具有全局变量的特点.但是和全局变量相比不同在于它只能在本

文件中使用

11.空类的大小？一个含有虚函数的类大小？为什么？

  分别是1和4。

  因为，对于空类，C++编译器会制定一个char来占据位置。

  含有虚函数的类，里面会存放一个虚函数指针vptr，指向一个虚函数表。指针在32位平台上

的大小为4个字节。

12 OSI七层模型和TCP/IP 五层模型。

      

      应用层

      表示层

      会话层                 应用层

      传输层                 传输层

      网络层               互联网络层

    数据链路层             互联接口层

      物理层                 物理层

12.编程求解走楼梯问题：

  一个人一次可以上1步，2步，3步。现在有n个阶梯（1<= n <= 100W，问有方法可以上去？

）

  f(1) = 1;

  f(2) = 2;

  f(3) = 4;

  n > 3,f(n) = f(n - 1) + f(n - 2) + f(n -3)

13.人人网的朋友概念：A和B是朋友，B和C是朋友，那么A和C是二度朋友。

   找出每一个人的10度朋友。要求O(n)的算法

 

14.推荐系统的设计