优酷【算法类】：笔试题目3（最全）

问答
设计一个算法，找出二叉树上任意两个结点的最近共同父结点。 复杂度如果是O(n2)则不得分。

问答
二叉树节点最大距离，需要分析算法复杂性。

问答
什么是社会网络研究？它的主要观点是什么？有哪些应用？

问答
从100万个数里面找出10个最大的数。写出代码并分析复杂度。

问答
10个房间里放着随机数量的金币。每个房间只能进入一次，并只能在一个房间中拿金币。 一个人采取如下策略：前四个房间只看不拿。随后的房间只要看到比前四个房间都多的金币数， 就拿。否则就拿最后一个房间的金币。编程计算这种策略拿到最多金币的概率。

问答
一景区需要门票5元，售票员没有零钱，假设这一天会来2N个人，其中N个人会给5元钱，N个人给10元，问所有人都不需要等待的概率是多少？

问答
使用堆栈（Stack）来模拟队列（FIFO）功能，要求数据必须存储在堆栈内部。需要实现enqueue（入队），dequeue（出对），isEmpty（判空）三个功能，并给出单元测试。

问答
一串首尾相连的珠子（m个），有N种颜色（N《=10），设计一个算法，取出其中一段，
要求包含所有N种颜色，并使长度最短。并分析时间复杂度与空间复杂度。
首先把珠子确定一个起始位置（随机），然后对所有珠子进行编号，从M+1到M+M，然后
构建N个数组，每个数组中存放每种颜色珠子在链子中的位置（按照从小到大顺序），但是因为第1个珠子和最后一个珠子的句子是1，而不是M-1，所以我们假设有三个项链，首位项链，这样每个珠子就有三个位置，把所有这些位置都放到M个数组中去。

找出N个数组中最短的一个数组，穷举所有出现的位置（从M+1到M+M）范围内的，当确定一个位置k时，从其他N-1个数组中用二分查找的方法找出一个和他距离最近的珠子，当然这前提是假设这个颜色的珠子在第一个位置上。
时间复杂度为，M(位置数)*log(M)(查找)*10（分别假设以每种颜色珠子作为起始位置）
3）设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，则中国人民人民中国都有效。要求：

1）系统每秒的查询数量可能上千次；
2）词语的数量级为10W；
3）每个词至多可以与1W个词搭配

问答
请写出贝叶斯公式，请描述朴素贝叶斯分类方法的原理和步骤。

问答
用户在输入英文单词时经常出错，现对其进行就错。给定一个正确的英文词典，考虑纠错实现。
1)指出思路。
2)流程、算法难易程度及可能的改进策略。
我们需要在淘宝的商品中提取一批优质商品（有特色、质量好、服务好等），比如需要提取100万件，准确率要求是95%。我们有n个不同的方法可以提取这些商品，但每个方法在保持准确率满足要求的情况下都不能做到提取完整的100万件商品。因此可以把这n个方法得到的满足要求的商品集按如下方法合并起来：如果一个商品被k个方法选为优质商品，则将它的分数设为k；按照k从大到小排序选取前100万件。但实际中发现这样选出的100万件商品不符合精度要求，请解释可能的原因。还可以向哪个方向努力？

问答
关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell的排序法，则一趟扫描的结果是( )；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是( )。

问答
int Recurse(int a, int b) {
    if(a >= b)
    {
        if(a == b)
       return a;
        else
       return 0;
    }
    else
    {
        return Recurse(a + 1, b - 1) + a + b;
    } }
假设a=8，b=2012，Recurse()函数的返回值是( )
问答
12个元素的排序数组进行二分查找，每个元素被查找的概率是相等的，平均比较次数为( )。
问答
下列给定程序中，函数fun的功能是：把形参a所指数组中的最大值放在a[0]中，接着求出a所指数组中的最小值放在a[1]中，再把a所指数组元素中的次大值放在a[2]中，把a数组元素中的次小值放在a[3]中，依此类推。
例如，若a所指数组中的数据最初排列为：1、4、2、3、9、6、5、8、7，按规则移动后，数据排列为：9、1、8、2、7、3、6、4、5.形参n中存放a所指数组中数据的个数。
请在程序的下画线处填入正确的内容并将下画线删除，使程序得出正确的结果。 试题程序：
#define N 9
/**********found**********/
void fun(int( ), int n)
{
    int i, j, max, min, px, pn, t;
    /**********found**********/
    for (i = 0;
i < n - 1;
i +=( ))
    {
        max = min = a[i];
        px = pn = i;
        for (j =( );
j < n - 1 ;
j ++)
        {
            if (max < a[j])
            {
                max = a[j];
                px = j;
            }
            if (min > a[j])
            {
                min = a[j];
                pn = j;
            }
        }
        if (px != i)
        {
            t = a[i];
a[i] = max;
a[px] = t;
            if (pn == i) pn = px;
        }
        if (pn != i + 1)
        {
            t = a[i + 1];
            a[i + 1] = min;
            a[pn] = t;
        }
    }
}

问答
在一个容量为25的循环队列中，若头指针front=18，尾指针rear=9，则该循环队列中共有( )个元素。
问答
一个具有3个节点的二叉树可以有( )种形态。
问答
若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则后序序列是( )？
问答
有一个数组（53,83,18,59,38,35），依次将其存储在hash表中，其中哈希函数为h(k)=k%7,如采用线性探测（每次向后查找1位）的方式解决冲突，则该hash表上查找38,35,53访问hash表的表项次数分别为( )，( )，( )。
问答
设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线 上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与 A[0][0]之间有( )个数据元素（即不算A[i][j]和A[0][0]）。
有 11 盆花，围成一圈，要求每次组合时，每盆花相邻的两盆花与上次不同，请问有( )种排列方法？
问答
7个相同的球放到4个不同的盒子里的，每个盒子至少放一个，方法有( )种。