CS 11/04 SUB题目讨论帖！！

yt_MayUID：209423

还有一题也是关于谓词表达式的，说到了contigent，问怎样描述三个表达式，是在always true, always fault和contigent中选。答案忘了，肯定是乱选的...

一道是讲换页策略，采用LRU，我选的是10次缺页；

一道是讲分页和分段的比较，我选的是A，分页产生内部碎片，分段产生外部碎片

一道是讲语言L为regular
I.{w|w的长度为偶数}；
II.{w|w的长度为质数}；
III.忘了
反正II不对，忘了选的是I还是I，III了。

还有一个也是关于NPC语言的题，我选的是一个是对的，一个是错的，另一个还不知道是否错误。

[ 本帖最后由 yt_May 于 2006-11-4 20:43 编辑 ]

phoenixinterUID：2161191

我来了我来了，哈哈哈哈哈哈

那个谓词表达式，应该选择Always True, Contingent, Contingent
第一个逻辑表达式是这样的
对任意x(S(b)->S(x)) 大概是这样的

第三个肯定是contingent的
因为如果全称谓词的universe是。。。
倒。。好像应该是always false...当x=b的时候肯定是错的....

数理逻辑错真是太丢人了。。。

分页和分段那个我也是A

regular那个应该选I，三是context-free的

最后一个题目：第一个对，第二个错，第三个等价P＝NP，不知对错

phoenixinterUID：2161191

倒。。。
两个人讨论这个讨论了好久。。。
不是求biconnected component
是求strongly connected component (强连通分量)
定义如下：如果一个图中，x~>y, y~>x，那么x和y强连通
这个题目是选A
4有条边在B中连到了{1,3,6}所以是错的。。。

phoenixinterUID：2161191

这个没有问题 4，ceil(1000/256) = 4
那个工作流的概率是5/6
LRU是10次page fault，这个也没有问题

惊闻Java我选对了@_@...

phoenixinterUID：2161191

CSMA/CA那个题目我选的是3L，原因如下
他说了ABCDE五个节点排在一行，无线通信，每相邻两个节点都会干扰，但是每间隔的节点都不会干扰，采用CSMA/CA协议，所以我觉得ACE都可以同时传输，那么是3L。

nearest & farthest neighbor那个题目肯定是O(nlogn),O(n)
原因如下：
无论是quicksort / mergesort都可以借助比较操作和交换操作实现，因此没有问题。
排序后直接线性扫描即O(nlogn)，我当时这个题目在考场上手写伪代码-_- 确定了下来

排序算法那个题目复杂度是O(2^n)

顺便说一句T(n)=T(n/2)+T(n/4)+cn的复杂度是O(n)，千万不要选O(nlogn)，自己动手画一个递归树就出来了，我差点选错。

下一题是shell-sort k-ordered sorted把它用插入排序所需要的comparison次数的asymptotic analysis，我如果没有搞错的话应该是O(kn)。

church-turing thesis和neutron machine那个我选的是E，停机问题明显不可计算，pi的十进制展开式是否有7个连续7这个虽然不可判定但是是直觉可计算的。

software requirement specification的问题那个我选的是I和II，这个我讲不清楚-_- 反正软件工程看来大家都不懂...

knapsack肯定是29, no optimal, 最优是30，wutherings is right

phoenixinterUID：2161191

第一题是求一个算法的复杂度，明显是O(logn)的
第二题是求一个堆弹出最大元素后的数组表示，我如果没有记错
原来的堆是这样的
         9
       /   \
      7    6
     /    /  \
    4   1   2
大家看着弹吧，这个没什么问题
第三题是那个n -> n/8的题目，是O(1)的操作，因为只需要删掉前几个节点。
第四题和第五题是两个编译原理的题目，都很简单，
似乎第四题是C x*x(x+y)yy*y
第五题是A
第六题是一个简单的程序语言题求最后result的值，应该是8。
第七题还确实忘了

有一题是按照什么key的插入顺序可以插入出一个给定的二叉树

有一个题目考semispace garbage collection的特性，这个不会..@_@

还有一个题目是考一个数据库self-join操作最后可能出来多少个tuple
我选的是218
第一个是[1,2] 6 第二个[3,8] 30 第三个是[9,10] 10
采用histogram进行estimate

我再想想....

phoenixinterUID：2161191

还有一个题目是这样的
M0,M1,M2,M3...Mn是所有图灵机的一个集合
I 能否判定给定一个n,Mn在n步之内halt
II Mn恰在n步halt
III Mn至少n步halt

我选[I,II], III明显是halting problem

phoenixinterUID：2161191

啊，又想起来一个
问一个mst中
I. 是否一定要包含最短边？
II. 一定要包含次短边？
III. 一定不能包含最长边？

我选I...这个应该没有问题吧
不过突然想到mst可能是很多的
是否有什么mst不包含最短边..
疑惑中
II III明显全错

phoenixinterUID：2161191

我仿佛可以回忆一个out-of-order的题目
那个题目我选A还是B来着。。。CDE被我拓扑排序排除了-_-
好像最后选A，大家选什么

phoenixinterUID：2161191

。。。我再努力回忆回忆吧~~过了昨天这个最好的时间有点回忆不起来了-_-

后来所有不确定的题目我都选了C....
反正数学期望是0~~又不是负分...

对了，
有一个题目
大概是一个算法，每次找前一半的最大，后一半的最大
问你63能出现在最后的两个元素的概率是多少
这个题目选32/63 ... 31/63? 忘了，反正大概是这一个

还有一个题目
就是五个球放在四个盒子中
A和B两个盒子中球数的期望和
这个是2.5

yt_MayUID：209423

原帖由 phoenixinter 于 2006-11-5 06:55 发表
CSMA/CA那个题目我选的是3L，原因如下
他说了ABCDE五个节点排在一行，无线通信，每相邻两个节点都会干扰，但是每间隔的节点都不会干扰，采用CSMA/CA协议，所以我觉得ACE都可以同时传输，那么是3L。

nearest & ...

ACE同时传怎么传？这道题必然是两个邻居之间才会有传输，一个节点传输必然会影响左右两个节点，所以我认为只能是A-B和D-E，所以是2L的带宽。

yt_MayUID：209423

原帖由 phoenixinter 于 2006-11-5 07:09 发表
我仿佛可以回忆一个out-of-order的题目
那个题目我选A还是B来着。。。CDE被我拓扑排序排除了-_-
好像最后选A，大家选什么

这是个指令乱序执行的问题，我觉得A是错的，里面的V和X被交换顺序了。原序中两者存在WAR或者RAW依赖。我选的是E。

yt_MayUID：209423

semispace garbage collection那道题，I是可以消除循环引用，II忘了，III是可以解决堆栈碎片问题。我道题我选的是I和III。

第五题给了一张NFA的图，让你写出它的grammar，其实就是按图转化一下就行了。我的答案和phoenixinter的不同，我好像选的是D。我觉得A有明显错误，有一个产生式的右部含有表示终态的变量V，这样肯定不对。

[ 本帖最后由 yt_May 于 2006-11-5 07:55 编辑 ]

yt_MayUID：209423

两道in-order流水线的题目也说一下吧：

一道是三条指令，问在ID阶段需要检测的hazard是多少个？我选的是2个。

另一道是问stall cycle就是气泡的个数，我选的是3个。