11月12日SUB考试cs(计算机)讨论专帖

so猫UID: 148633

11月12日SUB考试cs(计算机)讨论专帖

大家有什么疑问可以在这里讨论
不要再新开帖子咯~~~
谢谢
:)

so猫UID: 148633

题目回忆也请放在这里哦
方便我们日后整理哦
谢谢大家啦~

P.S.: 代替giter斑斑发帖 他出去玩去啦 嘿嘿~

alexzhouusUID: 2114153

考到最后,只觉得体力不支

tonychinUID: 169511

2.AbirdsVflies 即所有的鸟都能飞，我选的答案是E(>birdsVflies)即存在不是鸟的也能飞。

3.   /+*WX*YZ-Y-ZX
求后序遍历吧？

6.  用x3x2x1x0表示0~9，表示的数不能被4整除输出1，否则输出0。问如何表示，A x0x1的非
B x0x1   
C x0+x1
D x0x1+x2x3的非
我的答案是A

7~8  一段程序
n=9;
for (i=0;i<n;i++)
{
    a[i]=i mod 3;
}
tempmax=a[0];
for (j=1;j<n;j++)
{
    if a[j]<=tempmax then tempmax=a[j]
}
7.问tempmax被赋值几次，8.问a[j]<=tempmax换成a[j]<tempmax的话tempmax被赋值几次。

9.是关于relationship database的什么key的问题

10.是关于RISC的题目

11.是关于LRU的题目

12.是个状态图，很容易

13~14是关于scope的题目
var
  x,y,z:integer;
begin
  x=7;y=5;z=4;
  procedure B;
  var
    x,y:integer;
  begin
    x=6;y=4;
    C;
  end;
  procedure C;
  var z:integer;
  begin
    z=3;
    write(x+y+z);
  end;
  B;
end

    C;
13.问静态作用域下输出结果是多少
14.动态

15.是关于array sezrch的题目

16. S-〉aAa|E   A-bS
A.aba
B.abba
C.ababa
问哪些可以推导出来

17.关于local variable,parameter,return address的题目

18.给了一个图，求depth-first遍历

19.就是那道RTT的问题，我的答案也是3.45

20~21.关于平衡二叉树和堆排序的问题

24.一段汇编程序，题目里面解释得很详细，也有过类似的题目，很容易

26.给了一段程序，关于堆栈操作，看懂就能做对，也很容易

27.终于考到了正则语言的交集和补集的封闭性

31.给了一个逻辑电路图，应该是一个乘法器。答案我选的z1=abc之间相互异或，z2=abc中至少有两个是1则等于1，否则等于0

34.一个程序
a[1..9]=[1,2,3,1,2,3,1,2,3]
n=9;
for i=n to 0 step -1
{
  a[i]=a[n-i+1]
}
问程序运行的结果是多少
我的答案是[1,2,3,1,2,1,3,2,1]

由于时间非常紧张，加上中午考完就和同学去happy了，直接导致忘掉了不少题目，请大家多多指正，感激不尽。
-------------------------------酷酷的分割线-----------------------------------------------------
下面是ioiwin兄台回忆的题目，巨强无比，pfpf。


第一题大意是
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？



还有一些记得不太清了。

graspeverysecUID: 2130798

正则那道我怎么觉得交集和补集的说法都不对！！