危盛的一套比试题,请大家一起来锻炼一下脑子!
反正一共是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）和—x,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
[解决办法]
[解决办法]
题目5
高中生物课本里的放回抽样的方法，大学软件工程里面也有这样的方法。
[解决办法]
怎么没有人做第八题？我来试一下：
如果两条线段有至少一条与坐标轴平行，都比较简单，现在考虑两条线段都不与坐标轴平行的情况
1.先求出AB所在的直线方程y=f1(x);
2.再求出CD所在的直线方程y=f2(x);
(求上述两个方程不用解方程组求交点，直接用高中解析几何的两点式公式即可)
3.两条线段相交的充分必要是：(f1(Cx)-Cy)*(f1(Dx)-Dy)<=0&&(f2(Ax)-Ay)*(f2(Bx)-By)<=0;
解释一下：
(f1(Cx)-Cy)*(f1(Dx)-Dy)<=0 说明CD两点在直线y=f1(x)的两侧，但是线段CD跟线段AB并不一定相交,同理(f2(Ax)-Ay)*(f2(Bx)-By)<=0 说明AB两点在直线y=f2(x)的两侧，但是线段AB跟线段CD并不一定相交,但是如果两条件同时满足则两线段一定相交。
代码略。
[解决办法]
第7个百度了以后看懂了 http://blog.csdn.net/yy_msdn/archive/2007/07/22/1702289.aspx
长见识了
[解决办法]
题目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
//绳子折两次，从两头烧，就可以算出15分钟，既然能算出15分钟，就可以算出22.5=（30+15）/2
题目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
// 1.灌满6升
2.倒进10升
3.再灌满6升
4.再倒进10升 剩余2升
5.把大桶倒空
6.倒进剩余2升
7.再灌满6升
8.道进大桶
题目4：In which system(进制) expression 13*16=244 is true?
A 5 B 7 C 9 D 11
// 5进制 23*31 最后一位为3 错
7进制 16*22 最后一位为12-7=5 错
9进制 14*17 最后一位为28-3*9=1 错
11进制 21*15 最后一位为5 错
所以，我认为没有一个正确的
题目5：一个鱼塘，养鱼若干，请想一个办法尽量准确的估算其中有多少条鱼。
//算出每平方米的鱼，再乘于鱼塘的总面积
题目6：int FindMiddle(int a ,int b,int c)和int CalMiddle(int a ,int b,int c)分别为两个C函数，他们都号称能返回三个输入int 中中间大小的那个int.。你无法看到他们的源代码，你如何判断哪个函数的质量好？
//我认为int FindMiddle(int a ,int b,int c)比较好，因为名字比较明确，就是找中间那一个数，让人一看就明白
[解决办法]
题四：B
(x+3)(x+6) = 2*x*x + 4 * x + 4
x > 6
则x = 7
题一正解：39 第一题就是找规律，第1、2、4象限相加，减去第3象限
题二正解：c（very good）
15min：
0时刻：A点燃两头，B点燃一头，A烧完是30min时刻
此时用B同时点两头可以测量15min
22.5min:
0时刻：A点燃两头，B点燃一头，A烧完是30min时刻
30min时刻：B点燃两头，C点燃一头，B烧完是45min时刻，此时C只点燃了15min，熄灭C
此时，同时点燃C的两头可以测量22.5min
题三正解：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
不知道大家看过少年包青天第三部没有，里面就有一个类似的例子。
题四 我觉得应该选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是否有必然联系呢，高手快来啊...
[解决办法]