面试群:17178382,17177936(如果群满,请加入下一群)
下面的题目还在不断勘误与增加中.
有的题目本身就是不可能完成的,只要证明这种不可能性就OK了.
有的题目是在现阶段没有普通解法的,只需要作出合理讨论就OK了.
请对自己感兴趣的部分进行作答,有了解就发到vczh@163.com,注明昵称和qq号码,根据回答情况,
进入不同的群.
*************************************************************************************
*数据结构与算法
*************************************************************************************
1.(vczh)用非递归的方法,不使用其他数据结构,求出在中序遍历中这个节点的下一个节点.
2.(vczh)已知链表A的节点的集合SetA,链表B节点的集合SetB,求算法判断
a.SetA交SetB非空
b.交集中『前一个节点不在此交集中』的节点
3.(飞雪)试计算含有n(n>=0)个结点的二叉树的形状的个数.
4.(飞雪)已知二叉树的结点的定义如下
struct node
{
node* LeftChild, * RightChild;
int data;
};
请写出非递归无其它数据结构的前序遍历算法和后序遍历算法.
5.(飞雪)请给出AVL(平衡树)插入以及删除指定key的结点的非递归算法.
6.(飞雪)请写出给一颗二叉树穿线的算法.
7.(飞雪)生成n个不同元素的全排列,非递归.
8.(飞雪)已知序列a[0...n]满足a[j] > s[j-1](j>0),其中s[j] = a[0] + a[1] +...+a[j]
对于已知的数x,写出在a[i]在找出若干个数使其和等于x的算法.
9.(飞雪)请写出用遗传算法解方程f(x) = 0的C或C++代码(假设在区间(a, b)内有一个解).
10.(飞雪)从100万个数中找出最大的50个数.
11.(飞雪)已知100000个元素中有一个元素至少出现50001次,试找出这个元素.
12.(飞雪)将KMP算法推广到二维情况.
13.(飞雪)已知平面上有若干点,求将这些点覆盖的最小的圆.
14.(飞雪)现有n个自然数构成的序列,交换两个元素的代价为这两个自然数的和,试计算通过交换
使这个序列有序需要付出的最小代价.
15.(飞雪)在一个0,1均匀分布的随机数产生器的基础上构造一个标准正态分布的随机数产生器并
论述在均匀分布的随机数产生器的基础上构造任意分布的随机数产生器的可能性.
16.(飞雪)已知元素为整数的矩阵mat[0...m-1,0...n-1],从第一行走到最后一行,然后回到第一行,
向最后一行走的时候,得分加上所走的元素的值,回来的时候,得分减去所走的元素的值,可以朝列指
标差不超过1的列前进,在向最后一行走的时候,行指标必须增加1,返回的时候必须减少.起始分为0,
如何走使最后的得分最高.
17.(飞雪)现有一个以0,1,2为元素的m*n矩阵,0为可访问,1不为可访问,2为可得分点(可访问),任给
一点为起始点,最多可以访问多少个得分点.
*************************************************************************************
*C++程序设计语言
*************************************************************************************
1.(飞雪)试利用模板偏特化写一个输入九九表的程序.
2.(飞雪)试利用模板偏特化写一个输出10的阶乘的程序.
3.(飞雪)最佳参数类型选择
BestTypeSelect<T>::ResultType
当T为指定类型的时候为T
其它情况下为const T&
4.(飞雪)泛型转发
写一个泛型转发函数f,f要将它的参数原封不动地转发给g(不管g的参数类型是什么):
template<typename T>
void f(T& t)
{
g(t);
}
分析上面的做法,给出自己的做法
5.(飞雪)已知有一个全局数组int g_arr[100];在程序运行时访问越界,而这个数组被大量引用,
请添加和修改适当的代码定位出访越界的地方.
6.(飞雪)写一个类A,在代码 A a; a = 1,2,3;cout << a << endl;运行后能输出1 2 3.
7.(飞雪)一个模板需要3个参数,对最后一个参数进行特化,特化版本中从来不用到第二个参数,
在模板递归中,刚好在特化时,特化版本的第二个参数(int)溢出,是否能特化成功呢?
*************************************************************************************
*计算与语言理论
*************************************************************************************
1.(飞雪)已知有如下的语法:
T :
x
Lx.T
T T
其中:
Lx.T尽可能右扩展
T T具有左结合性
请画出Lx.Ly.x y x的语法树.
2.(飞雪)写出识别四则运算表达式的正则式.
3.(飞雪)已知类型A B C D其中A是B的子类型,C是D的子类型,
请写出类型C->B的子类型
4.(飞雪)论不用运行时解释去实现动态语言的实现.
*************************************************************************************
*windows操作系统
*************************************************************************************
1.(飞雪)在用户态下写物理内存(Windows5.1以上).
2.(飞雪)避开IceSword的侦测隐藏进程.
3.(飞雪)写程序导出指定QQ群的成员列表.
*************************************************************************************
*设计与模式
*************************************************************************************
1.(飞雪)一个应用程序有多个窗口,在窗口比较靠近的时候,窗口靠在一起(参考千千静听).描述你
的解决方案,如果能用UML描述更好.
2.(飞雪)设计一个生产者消费者模型或者消息驱动的应用程序的框架.
*************************************************************************************
*其它
*************************************************************************************
1.(飞雪)写一个程序,使CPU使用率呈锯齿状.
2.(飞雪)写一个程序,输入C程序的代码,输出这个C程序的复杂度.