cs sub的一些题目的回忆

ioiwinUID：183956

第一题大意是
function(integer k)
{
   if(k==0)
      then  return 1
   else
       return function(k-1)*2
}

what is the value of function(4)?

第五题
大意是 指令集中有20%的指令是浮点数指令，问通过硬件加速浮点机灵，最大的speedup是多少？

我选的是d 1。25    1/0。8

一个网络的传输率是2，500，000bits/s，它的一个round trip time是100milisecond，延时是是round trip time是的一般，传输协议进行一次handshaking的时间是2个rtt时间，每个包是含有1000byte，问传输1，000，000byte的时间？
我选的是3，45       1000*（8*1000/2，500，000+2。5/10，000）




某题 问 alu一个加法逻辑器件有输入a,b ，cin， cout，和输出F
F=a+b，cin=0，问该逻辑能不能进行减法？

1 A=a ，B=b的反码 cin =0 F=A+B
2 A=a ，B=b的反码 cin =1 F=A+B
3 无法进行减法

是问该逻辑能不能实现DECREASMENT 既F=A-1？
1 A=a ，B=all1‘s cin =0 F=A+B
2 A=a ，B=all1‘s cin =1 F=A+B
3 A=a ，B=0 cin =1 F=A+B
4 无法实现

31题 一个逻辑电路的输入为x, y，s，输出为F=xs+y乘s的非，
z1=c（ab+a的非乘a的非）+c的非（ab+a的非乘a的非）
z2 不太记得了

我选的是z1=a异或b异或c，z2=a，b，c中有两个1时就为1


还有一个是用x3x2x1x0来表示0到9，当它表示的数不能被4整除输出1，否则输出0。
这种输出可以由什么来表示
1 x0x1的非
2 x0x1   
3 x0+x1
4 x0x1+x2x3的非

任意的x,y，z,有 p（x,y）并且p(y,z) 蕴涵 p(y.z)
任意的x有非自反性，既非p（x,x）
问可由上面两个推出那一个或哪些？
1 任意的x,y p（x,y）或者p(y,z)
2 任意的x,y p（x,y）蕴涵  非p（x,y）
3 存在x,y p（x,y）


s 是一个集合，对s的操作有删除一个指定的元素，插入一个元素，查找某个元素。
问用什么数据结构可以是插入，删除的操作复杂度不超过logmatic n
1 排序的链表
2 平衡的2叉查找树
3 堆
还有一问是问 插入，删除，查找操作复杂度不超过logmatic n的数据结构
1 排序的链表
2 平衡的2叉查找树
3 堆

另外有个问题是问在n个数中找第根号n大的元素，问下面哪个的操作的可以使他的时间复杂度为o（n）？
1构造一个堆，删除根号n个最小的元素 我选的，其他的不太记得了


有个关于图的是问
A 是一个NP难题， B 是一个NP完全问题，问怎么确定A也是NP完全的？
1 f（x） 是一个使 A输出确定的函数，if and only if x是b的输入。


还有一个计算理论是问停机问题的具体意思。
还有一个和图中找最长路径的问题有关的。
还有一个实说背包问题是NP难的，在线性规划中有复杂度o（ns），s 是背包的size。
问这有什么明显的矛盾？
1 证明了P=NP。
2 他的输入不能用多项式时间表示什么？
3 ？？
4 ？？
5 证明了P不等于NP。

还有一个问题说最小生成树的边的权重 k和travelling sales man 中边的权的和d 的关系？不知道做？


language1 ，L1，language2，L2 下面哪些正确
1 L1并L2是正者的，那么其中至少有一个是正则的。
2 L1交L2是上下文无关的，那么其中至少有一个是？？？不记得了。



SNIFFER，可以查看网络包中的内容，是黑客常用的窃取用户密码一种手段，问下面哪些措施可以防范sniffer？
1 使用加密和动态密码
2 用smart card对网络上的用户进行验证
3 用户定期修改密码
还有一个关于网络的题是问连路 层的错误处理协议，有选择重发歇息，后退n的重发协议。


66 priority inversion（优先级反转）。 有3个优先级队列，HIGH， MIDDLE， LOW。一个 binary signal s。P（S），V（S）。问下面哪个可能发生优先极反转？
1 H ：COMPUTE
  M：P（S）；COMPUTE； V（S）
  L：P（S）； COMPUTE；V（S）
2 H：P（S）；COMPUTE； V（S）
   M：P（S）；COMPUTE； V（S）
   L：COMPUTER
3 H：P（S）；COMPUTE； V（S）
   M：COMPUTER
   L：P（S）； COMPUTE；V（S）
4  H ：COMPUTE
   M：COMPUTER
   L：P（S）； COMPUTE；V（S）
5 H：P（S）；COMPUTE； V（S）
  M：COMPUTER
  L：COMPUTER


67 full binary tree 是指，每个internal nodes都有两个子节点。s代表广度优先的enumrate和前序周游相同的所有的full binary tree的集合？
1 s is empty
2 s is finite， and the number of n nodes tree is o（n）
3 s is infinite， and the number of n nodes tree is o（1）
4 s is infinite， and the number of n nodes tree is o（n）
5 ？ 不记得了

68 仍一枚硬币，head and tail 的几率都是1/2。在某次试验中仍出3个0，或着3个1就不仍了。问仍出连续两个head 或tai的概率？l


69 问一个开hash 表有m个slots，重复的码值映射到相同的slot中时它们以链表相连。码值映射到每个slot的概率是相同的。问查找一个元素的时间复杂度？
我选的是1+n/m


70题 问在{a,b，c}中有多少中不同的equivlance  relationship？



还有一些记得不太清了。

pengodUID：136708

好记性！楼主在哪里考的？

ioiwinUID：183956

Originally posted by pengod at 2005-11-12 21:28
好记性！楼主在哪里考的？

我在武汉考的

tonychinUID：169511

楼主太强了，pfpf

ioiwinUID：183956

我就是考完有很多题不解，不确定．所以映象深刻

apolloxpUID：156355

多谢分享，祝你考出好成绩

ioiwinUID：183956

任意的x,y，z,有 p（x,y）并且p(y,z) 蕴涵 p(y.z)
任意的x有非自反性，既非p（x,x）
问可由上面两个推出那一个或哪些？
1 任意的x,y p（x,y）或者p(y,z)
2 任意的x,y p（x,y）蕴涵  非p（x,y）
3 存在x,y p（x,y）



这个题打错了。
任意的x,y，z,有 p（x,y）并且p(y,z) 蕴涵 p(y.z) 改为任意的x,y，z,有 p（x,y）并且p(y,z) 蕴涵 p(xz.z)

yuren78UID：2111432

If p(x,y) and p (y,x)  -> Then, we can get P(x,x). 不符合 Assumption 吧.