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

单选
设模式串的长度为m,目标串的长度为n,当n≈m且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省()
A. 对
B. 错

单选
串是一种特殊的线性表,其特殊性体现在()
A. 数据元素是一个字符
B. 可以顺序存储
C. 数据元素可以是多个字符
D. 可以链接存储

单选
解析XML时，需要校验节点是否闭合，如必须有与之对应，用（）数据结构实现比较好
A. 链表
B. 树
C. 队列
D. 栈

单选
已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()
A. head(tail(LS))
B. tail(head(LS))
C. head(tail(head(tail(LS)))
D. head(tail(tail(head(LS))))

单选
下面关于求关键路径的说法不正确的是()
A. 求关键路径是以拓扑排序为基础的
B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D. 关键活动一定位于关键路径上

单选
所有人口中，某癌症的患病率为0.008。对有癌症的病人，医院的化验测试有2%的可能错判其无癌症。对无癌症的病人，有3%的可能错判其有癌症。问：现有一新病人，化验测试表明其有癌症，该病人实际患有癌症的概率是多少？（计算过程四舍五入保留4位小数）
A. 0.0078
B. 0.0298
C. 0.2074
D. 0.98

单选
你有100个球，红的50个，蓝的也是50个,你需要把它们（所有的球）放在两个罐子中（随便怎么放），请问怎样放使你从中拿出红球（拿一次）的机率最大？
A. 一个罐子50个红球 ，另一个罐子50个篮球
B. 一个罐子不放球 ，另一个罐子放100个球
C. 一个罐子1个红球 ，另一个罐子49个红球，50个篮球
D. 一个罐子1个红球，50个篮球 ，另一个罐子49个红球

单选
6×9的的方格中，起点的左下角，终点在右上角，从起点到终点，只能从下向上，从左向右走，问一共有多少种不同的走法。
A. 4200
B. 5005
C. 1005
D. 以上都不正确

问答
二分查找是常用的编程方法，请用完整代码实现该函数（不许调用库函数）
void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));

问答
长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的swap，请设计并实现排序。

问答
汉诺塔一共为2*N，2个一样大小，有编号顺序每次只能移动一个大的不能叠在小得上面移动完之后，相同大小的编号必须和原来一样问最小要移动多少次？如A1 A2 B1 B2 C1 C2……这样叠，A<B<C ….B不能放在A上面，C不能放BA上面，移动到另外一个柱子后，还必须是A1 A2 B1 B2 C1 C2….

问答
有一副牌编号0~51，请把这副牌尽可能随机的发到4个人手里
注1：已经有rand()函数可以调用，但是rand()函数开销较大，请尽量少调用
a,b,c,d分别是13个元素的1维数组
函数原型 void deal( int[] a, int[] b, int[] c, int[] d );

问答
如何随机选取1000个关键字。给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

问答
请完成二分查找的非递归算法：
Int binsearch(ElemType A[], int n, KeyType K) {
    int low = 0;
    int high = n - 1;
    while (low <= high)
    {
        int mid = _____ ;
        if (K = = A[mid].key) return mid;
        else if (K < [mid].key) _____ ;
        else _____ ;
    } return -1;
}
问答
求一个正整数N的开方，要求不能用库函数sqrt()，结果的精度在0.001
问答
一个圆，被分成N个部分，用K中颜色给每个部分上色，要求相邻区域颜色不能相同。有多少种上色方案？
问答
给定两个整数集合A和B，每个集合都包含20亿个不同整数，请给出快速计算A∩B的算法，算法可使用外存，但是要求占用内存不能超过4GB。
问答
每个整数0-9这10个数组成，如223有2个2 ，和1个3，输入m和n（0<m<n<10^20< span="">） </m<n<10^20<>
求出m到n之间所有整数共包含了多少个0，1。。。。9
实现函数void foo(const char*m, const char * n, char * result, size_t len )
result为输出缓冲，len为result的长度。
要求写出思路、程序程序效率，计算时间复杂度和空间复杂度
问答
有一个环形的珠子串，数量为m。其中包含颜色种类为n(n<10) 截取一串要包含这n种颜色，且越短越好。并分析时间复杂度与空间复杂度。
问答
在排序数组中，找出给定数字的出现次数。比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。