2004年CS Sub回顾

apolloxpUID：156355

发信人: askthesky (想来越剧协会吗？), 信区: GRE
标  题: 今天CS Sub回顾
发信站: BBS 水木清华站 (Sat Nov 13 13:33:27 2004), 站内

39题浪费了我无数时间,最终没有选
是给了一组程序,问out-of-order的处理下面哪个是错的,
类似下面的一组程序
T: R0 <- R7,R8
U: R4 <- R1,R2
V: R5 <- R3,R4
W: R9 <- R0,R4
...
Z: R9 <- R0,R5
选项是 U,T,V,W,X,Y,Z 这样的形式
B里X和Y换了,但Y用到了X的输出
D里W和Z换了,它们都写R9, W本来没用了现在变成Z没用了,也不对呀
呵呵,不知哪里题目看错了,真是年头多不考试了阿,呵呵,这种题给憋死了

还有个考垃圾回收的
考mark-sweep方式,我选的是它比copy-collect方式快,很可能错了的
其它选项有
A.sweep时要看整个heap, B.能清掉所有垃圾 C.清不掉环 D.只能用整个空间的一半

最令我愤怒的是算法题都记不得了,前面又耽误了一些时间来不及现推导,没面子阿
最大流是NP的吗?(据说某年数学高考题还考网络流了)
有个貌似 bipartia..什么的图方面的词我想应该是二分图吧,二分图匹配是NP吗?

有个问I,II,III哪个是P的:
I. m个变量 n个register(n<=m), 给出冲突对集(不能占同一个寄存器的变量对),,求分配
II.一种job-shop问题吧. n个工作n台机器,给出哪个工作哪些机器能做,求能否分配开
        I可能也是求能不能分配开吧记不准了. 这个我感觉其实是指派问题
III忘了,印象中是个P问题

还有个数字逻辑的, literal指pi或非pi(i=1,...n). 3-clause是三个liternal之和
给出m个3-clause,问给定一种p1～pn,它们都为真的概率
B. (3/8)^m C. (7/8)^m E. { 3(n+1)(n+2)(n+3)/[8n(n-1)(n-2)] }^m
其它选项我印象中m越大越大,还有m*f(n)的形式[f表示我忘了-.-],我想必然不对

最ft的是第8题求8bit数中恰有4个1的个数,我居然想了好久,最后才发现就是C(8,4)=70

还有数电的,仨JK触发器连的一个乱七八糟的电路,给初态问1周期后变成啥

一分页管理的虚存系统,页大小32byte,问虚地址 0010xxxx 的实际地址
页表里页1是没在实存里的故选E page fault. 前四个分别是 1xxxx,2xxxx,3xxxx,4xxxx
一共就4个实page frame, 8个虚页

分页的还有一个记着的是..... 也是这种, 答案页号是6位的那个, 偏移是...
是2^32的虚存. 2^18的实存. 4096的页面大小好象

还有个答案16384M的回来下次回顾吧,下午还有笔试 wave -_-


--
┌  ──┬┐┌──┼─┐ ╭┼╭─┐┐┌┼┬╮┬╮                             
│      │  ┌──┴─┐ ┌┼┌─┼┐┌┴┴┐╯│ 您喜欢越剧吗？来越剧协会吧  
╰┐    │  │─╮  ┌│ ┌││  │┐╭──┐╮│  
╰┐    │  │─┴┬┴│ │├│  ┼╯│____│╭│ 详情咨询：Xiququyi板        
│      │  │──┼─│ ││└╯╰┘│    │┘│   周六晚身段班,隔周日学唱   
╰┘──┴┘└    ┘  ╯ └┴───╯└──╯─┘                             


※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.68.91]

[ Last edited by genie05 on 2005-9-10 at 09:52 ]

alexzhouusUID：2114153

这是什么时候考的,不是最近的SUB考试要等到11.12去了吗?

apolloxpUID：156355

哦。这是别人去年考后写下的回顾。
怪我标题没写清楚，这就改