危盛的一套比试题,请大家一起来锻炼一下脑子!
反正一共是10道题 要做三个小时， 把我做得累的 最后危胜还是没要我 今年工作真难找 郁闷阿~~~
题目1:下面图问号处该填什么？(不好意思 图咋都贴不上去 只好给个链接~ 谁能帮忙贴下图)
http://album.hi.csdn.net/app_uploads/jinder22/20081201/100422452.p.jpg?d=20081201100453467
题目2：There is a kind of cord which is NOT uniform. It will cost one hour to burn such a cord from one top to another top. Now assume you can use three such cords. Then which time you can not measure precisely?（有一条不均匀的绳子，从一端烧到另一端需要1小时，假设你有3根这样的绳子，下面哪个时间你不能精确得到）
A 15min B 22.5min C 35min D both of ABC
题目3：There are two buckets. The capacity are six kilolitre and ten kilolitre. All these two buckets are NOT uniform(均匀). Now assume you have these 2 buckets and a pool with unlimited water. And we define either of such three operations as one step（两个不均匀的桶，一个6升另一个10升，如果池塘有无限的水，那么下面步骤）:
1> Pour water from the pool to one bucket untill this bucket is full;（用水把其中一个桶灌满）
2> Pour water from A to bucket B until bucket A is empty or bucket B is full;（把其中一个桶的水灌入另一桶直到一个桶空一个桶满）
3> Pour away water from one bucket to the pool untill this bucket is empty;（八其中一个桶到光）
If you could get eight kilolitre of water in the larger bucket precisely, you should execute at least ______ steps?（如果你想在10升大桶中得到8升水，那你至少要执行几步操作）
A 6 B 8 C 10 D 12
题目4：In which system(进制) expression 13*16=244 is true?
A 5 B 7 C 9 D 11
题目5：一个鱼塘，养鱼若干，请想一个办法尽量准确的估算其中有多少条鱼。
题目6：int FindMiddle(int a ,int b,int c)和int CalMiddle(int a ,int b,int c)分别为两个C函数，他们都号称能返回三个输入int 中中间大小的那个int.。你无法看到他们的源代码，你如何判断哪个函数的质量好？
题目7：请于都下面这段C++代码，说明Fun1和Fun2的功能，并解释他们的优缺点。
int Fun1(unsingned int x)
x=(x & 0x55555555)+((x>>1) & 0x55555555);
x=(x & 0x33333333)+((x>>2) & 0x33333333);
注：第7题题目不全，请看62楼的修正。
题目8：判断二维平面上两条线段是否规范相交（有且只有一个非端点的交点）；输入四个点的坐标（Ax，Ay），（Bx,By）,（Cx,Cy）和（Dx,Dy），分别表示第一条线段AB的两个端点，和第二条线段CD的两个端点。输出1表示相交，0表示不相交。设计的算法中，不允许计算直线间的交点坐标，因为求方程的解设计到浮点除法，这将丢失很多精度，但是浮点的乘法是允许的。请阐述算法思想，并用C++代码实现。
题目9：问1:
叙述如何用双链表结构描述下面的一个稀疏矩阵？假定在该结构中，非零元的记录从最左列遍历到最右列，每一列从上至下遍历。并用C++代码实现（在该问题给出的矩阵中，记录信息的顺序是｛a11,a21,a41,a22,a52……,a45,a55｝。）
a11 0 a13 0 0
a21 a22 0 a24 0
0 0 a33 0 0
a41 0 0 a44 a45
0 a52 0 0 a55
问2：
请给出你所能想到的其他更好的描述稀疏矩阵的数据结构。并说明好在哪里，比如矩阵乘法，加法，行列式运算，方程求解等方面的运算效率，存储器空间的使用效率等等。
题目10Please give a description of the algorithm to renmove the dead code in a program (That is,”dead code elimination ”),(An instruction and a variable are dead if it computes values which are not used on any executable path to the procedure’s exit.)For example, in below program,（请给出一个算法，实现移除死代码的功能）
b=a+c
d=c+f
d=d*a
d=d*c
return d;
Instruction “b=a+c”is dead since b has no effect to the final output d.(比如说上面的代码中b=a+c 就对最后结果d一点用处都没有)
We need an algorithm to find out such dead code and remove them from the final program.
如何请写出算法，和解题思路。
[解决办法]
10. 我想到的就是按语句逆序来扩充一个引用集，对每一句，当且仅当左值在引用集中，把表达式的变量集加入到引用集中
初始引用集R为空，空语句为D
return d R={d}
d=d*c d belongs to R => R={d,c}
d=d*a d belongs to R => R={d,c,a}
d=c+f d belongs to R => R={d,c,a,f}
b=a+c b not belongs to R => R={d,c,a,f}不变， D ={ b=a+c }
这个集合用一个hashset就再完美不过了...
[解决办法]
题一：39
vm = v1 + v2 - v3 + v4 =>39
题二: C
1 一根绳子可以计1小时和30min(两头烧)
A 15 min(将一根绳子割掉，四头同时点) 故A可计，D排除
B 22.5min(先计时15分，再计时7.5分（一根绳子割4断，同时烧）)
题三：A
s1 6 empty 10 full
s2 10-6 6 full 10 4L
s3 6 empty 10 4L
s4 6 4L 10 empty
s5 6 4L 10 full
s6 6 full 10 8L
题四：B
(x+3)(x+6) = 2*x*x + 4 * x + 4
x > 6
则x = 7
[解决办法]
s3 6 empty 10 4L
s4 6 4L 10 empty
s5 6 4L 10 full
s6 6 full 10 8L
不知道大家看过少年包青天第三部没有，里面就有一个类似的例子。
题四 我觉得应该选d，看大家好像都选b，我的理由是：假设为10十进制，13×16=208，而结果为244，要使是结果大于208
则必大于十进制，这样排除a，b，c选d了。
题五 答案等高手来吧，只能是推测了
题六 题目6：int FindMiddle(int a ,int b,int c)和int CalMiddle(int a ,int b,int c)分别为两个C函数，他们都号称能返回三个输入int 中中间大小的那个int.。你无法看到他们的源代码，你如何判断哪个函数的质量好？
我想这道题应该是考大家分析情况的能力，比如一些特殊情况要特殊处理，例如：先测试0 0 0 看他们的测试结果，在测0 0 1
（我想这个比较能反映问题），在随便输入一些不是数字的数，测一下他们的排错功能，呵呵. 如果前面俩种情况他们的结果一
样，那就这能测他们的算法效率啦....
题七：题目7：请于都下面这段C++代码，说明Fun1和Fun2的功能，并解释他们的优缺点。
int Fun1(unsingned int x)
x=(x & 0x55555555)+((x>>1) & 0x55555555);
x=(x & 0x33333333)+((x>>2) & 0x33333333);
只是分析了5和3的二进制，发现为0101和0011，和x>>1与x>>2是否有必然联系呢，高手快来啊...
[解决办法]
