2015百度机器学习/数据挖掘工程师+自然语言处理工程师笔试题目

1.new 和 malloc 的区别。

new 返回指定类型的指针，并且可以自动计算所需要大小。
比如：

int *p; 　　
p = new int; //返回类型为int* 类型(整数型指针)，分配大小为 sizeof(int);

或：

int* parr; 　　
parr = new int [100]; //返回类型为 int* 类型(整数型指针)，分配大小为 sizeof(int) * 100;

而 malloc 则必须要由我们计算字节数，并且在返回后强行转换为实际类型的指针。

int* p; 　　
p = (int *) malloc (sizeof(int)*128);//分配128个（可根据实际需要替换该数值）整型存储单元，并将这128个连续的整型存储单元的首地址存储到指针变量p中  

double *pd=(double *) malloc (sizeof(double)*12);//分配12个double型存储单元，并将首地址存储到指针变量pd中

PS：有了malloc/free为什么还要new/delete？

malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
对于非内部数据类型的对象而言，光用maloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。
因此C++语言需要一个能完成动态内存分配和初始化工作的运算符new，以及一个能完成清理与释放内存工作的运算符delete。注意new/delete不是库函数。
我们不要企图用malloc/free来完成动态对象的内存管理，应该用new/delete。由于内部数据类型的“对象”没有构造与析构的过程，对它们而言malloc/free和new/delete是等价的。
既然new/delete的功能完全覆盖了malloc/free，为什么C++不把malloc/free淘汰出局呢？这是因为C++程序经常要调用C函数，而C程序只能用malloc/free管理动态内存。
如果用free释放“new创建的动态对象”，那么该对象因无法执行析构函数而可能导致程序出错。如果用delete释放“malloc申请的动态内存”，结果也会导致程序出错，但是该程序的可读性很差。所以new/delete必须配对使用，malloc/free也一样。

2. hash冲突是指什么?怎么解决?给两种方法，写出过程和优缺点。

1.线性再散列法
原理：线性再散列法是形式最简单的处理冲突的方法。插入元素时，如果发生冲突，算法会简单的遍历hash表，直到找到表中的下一个空槽，并将该元素放入该槽中。查找元素时，首先散列值所指向的槽，如果没有找到匹配，则继续遍历hash表，直到：（1）找到相应的元素；（2）找到一个空槽（指示查找的元素不存在）；（3）整个hash表遍历完毕（指示该元素不存在并且hash表是满的）
优点：简单直观
缺点：第一，不能从表中删除元素，因为相应的单元可能已经引起过冲突，元素绕过它存到了别处，如果我们删除了某个元素，那么其他的元素都会找不到。第二，当表被填满时性能下降明显。
2.再哈希法
原理：构造哈希函数集 $\{H_1,H_2,...,H_n\}$ ，当发生冲突时，依次使用哈希函数，直至不存在冲突为止。
优点：避免了数据聚集现象
缺点：计算时间较多，同时也不能删除元素
3.拉链法
原理：拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组 $T[0..m-1]$ 。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。
优点：拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
缺点：它需要稍微多一些的空间来实现，因为添加任何元素都需要添加指向节点的指针，并且每次探查也要花费稍微多一点的时间，因为它需要间接引用指针，而不是直接访问元素。

3. 命中的概率是 0.25，若要至少命中一次的概率不小于 0.75，则至少需要几次?

$n>log_{\frac{3}{4}}{\frac{1}{4}}$
故至少5次

4. 用C/C++写一个归并排序。数据结构为struct Node{int v; Node next};接口为 Node merge_sort(Node *);

可以参看博客http://blog.csdn.net/u013207865/article/details/50374039
只是题目给出的数据结构是链表形式，可以转换为数组。

5. 设计S型层次遍历树的算法，比如根节点是第一层，第二层从左至右遍历，第三层从右至左遍历，第四层再从左至右遍历，以此类推

核心就是广度优先。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    void getSRoad(TreeNode* root) {
        queue< TreeNode * > que;//引入队列
        stack< TreeNode *> stc;//引入栈
        bool flag=false;//true:存入队列，false：存入栈
        stc.push(root);

        while(!stc.empty()||!que.empty())
        {
            if(flag)
            {
                while(!que.empty())
                {
                    TreeNode* node=que.front();
                    que.pop();
                    cout<<node->val<<" ";
                    if(node->left!=NULL)
                        stc.push(node->left);
                    if(node->right!=NULL)
                        stc.push(node->right);
                }
                flag=~flag;

            }
            else
            {
                while(!stc.empty())
                {
                    TreeNode* node=stc.top();
                    stc.pop();
                    cout<<node->val<<" ";
                    if(node->left!=NULL)
                        que.push(node->left);
                    if(node->right!=NULL)
                        que.push(node->right);
                }
                flag=~flag;
            }
        }
    }
};

原文链接：https://blog.csdn.net/u013207865/article/details/51202438