今天的CS sub回忆 zz

imongUID：140258

发信人: 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 -_-


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


[本篇全文] [回复文章] [回信给作者] [本篇作者：bitzd] [进入讨论区] [返回顶部]  2  

发信人: bitzd (5t6g), 信区: GRE
标  题: Re: 今天CS Sub回顾
发信站: BBS 水木清华站 (Sat Nov 13 17:12:06 2004), 站内


【 在 askthesky (想来越剧协会吗？) 的大作中提到: 】
: 标  题: 今天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没用了,也不对呀
: 呵呵,不知哪里题目看错了,真是年头多不考试了阿,呵呵,这种题给憋死了

这个我选的B,没有注意到D


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

B和C矛盾，必定选其中的一个吧


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

可能只有旅行商问题是NP的


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

这个我选错了，好像II可以转化成二分图匹配问题


:
: 还有个数字逻辑的, 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 -_-
:
:
: ※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.68.91]


--

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


[本篇全文] [回复文章] [回信给作者] [本篇作者：yoshimi] [进入讨论区] [返回顶部]  3  

发信人: yoshimi (无法使你高尚@sub之前戒网...), 信区: GRE
标  题: Re: 今天CS Sub回顾
发信站: BBS 水木清华站 (Sat Nov 13 18:26:24 2004), 站内

嗬嗬，我做到80多道的时候，发现前面cs的人居然只涂了20多道，结果发现你们一共也就六七十道的样子
【 在 askthesky (想来越剧协会吗？) 的大作中提到: 】
: 39题浪费了我无数时间,最终没有选
: 是给了一组程序,问out-of-order的处理下面哪个是错的,
: 类似下面的一组程序
: ...................

--

In this unique blend of spontaneously affecting music and mystical
esoterism lies the special significance of the most splendid of Bach's works.


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

pengodUID：136708

今天在北语考完！好像北语考CS的不多，202里一共28个CS的，几个English literature的，不知道在北外的多吗？

imongUID：140258

English Literature的资料在这里都不多呢 :(

zhjUID：185896

我来补充点吧
印象中好像有两道以前的真题，
{set A 有 m elements set B 有 n elements,问映射有多少种的那个}
{A 为要分配的mem，B为align后分配的mem，fragment＝1－A/B，从1－2^16问fragment最接近的那个值的那道}
这次考了好几道算法的题，印象中有Strassen 's algorithm,就是两个matrix相乘分解成7次乘法的那个，考了两道题，一道是求递归方程，另一到是O(n^log7=2.81)
还有一道knapsack，具体想不起来是那种背包了，不好意思啊！
还有一道是greed求MST为什么是正确的，在clrs中看过。
还有一道是考attribute grammer,给了I，II,III,我只记得II好像是attribute grammer能用于bottom－up.
还有一道竟然是考euclid algorithm的worst case的O(n),印象中好像还没有结论啊！平均case是logb,(gcd(a,b) a>=b),记得好像当a,b是fibonacci数列中相邻两数时worst,再查查clrs吧！那位指点一下？
好像有一道是hamming distance是9，求最多表示几个值
另外上面I，II，III那个是P的那道中的III好像是给2个string，求有无length为k的common sebsequence，我当时想直接求lcs，然后和k比就行了，但不知对不对？具体想不起来了，是不是让求仅有长度为k的？不好意思啊！
那个gc中的Marked&Sweep我记得能处理环。
还有一道考AI search的，初态是：一共横着7个格，左边3个grey ball，中间有一个空格，右边3个black ball，建树，BFS，4种attempt:
1.右移一个grey ball
2.右跳一个grey ball
3.左移一个black ball
4.左跳一个black ball
问6th configration是什么?
还有是考heap操作的time O(n)，分别是Insert，delete_min，还有一个好像是改值的。
还有一道是有关找以下data structure中kth largest的值的time O(n)，1 avl or red black tree 2 heap(这个记不大清了) 3 sorted array.具体问什么想不起来了。
还有一道是solution 2048×1024 65536 colors，问要几M的显存。
还有一道是有关内存分配的，记得是next fit first。
还有一道是cache speedup ratio的，access cache 5ns,access storage 55ns,500M cpu,命中率90％。
还有一道是考relation的，问哪一个不是symmetry的但是是自反的，反对称的，传递的，I是a is substring of b,II是a,b是某段程序的其中两行，a some time run after b,III想不起来了……
还有一道是一个concurrent cpu 每个周期能做p次comparison，问在sorted array中search，要几个周期。
还有一道是有关OO的，问那个错了，好像是在class中访问了其他class中的private var。
有两道和loop invariant有关的题，一道好像是 x=0;k=1;while (k<100){x=x+2*k-1;k++},还有一道忘了。
有一道和密码学有关的题目，考的是symmretry key 和public key的对比，具体选项记不清了，我选的是private key 加解密用同一key，public用不同的key。
和function call有关的题，考的是call by value & call by reference,具体题目记不清了。
有一道考的是concurrent，记不大请了，好像如下：
produce A{
for i=1 to n
        a[i]=0;
}
produce B{
for i= n to 1
        a[i]=0;
}
main{
for i＝1 to n
        A[i]=-1;
cobegin
A();
B();
coend.
}
问什么也不记得了。
还有一道是以下3个sets中那几个中的数转换成binary是正则的，I能被5整除的，II 3^n,III 8的倍数。
还有一道考文件组织，continue，linked，index，是那种I,II,III的题目，具体记不清了，但不外乎是那种适合存那种类型的文件，比如文件的大小，多少，访问频率。
还有是一道判断postorder exp。
还有一道和编译有关，32位RISC，有R0-R7,R6中放栈顶指针，MOV offset,source,dest,MOV支持寄存器间接寻址和add & sub,给你一个语句，翻译成asm，exp记不清了，很简单的。
还有一道题不记得了，只记得I single linked list II double linked list III sorted array,问什么不记得了。
还有一道是问那个不是dynamic的algorithm，选项记不清了，但题很简单，因为其中有dijkstra，其他的看都不看了。
还有一道是考用array模拟循环队列的，让你填，head和tail的表达式，很简单的。
还有一道是考指针和二级指针的，好像是p是指针，q是二级指针，q=&p;*q=MemAllocat(T),T是language的某种type，问p&q的内容是什么？
还有一道是
E->E+T|T-E|T
T->a|b|c
问a+b-c和a-b+c各有几个grammer tree。
还有一道是给你一个diected graph的邻接matrix，找出那个选项是strang connect subgraph。
还有一道是考递归的，euclid algorithm求gcd中的
f(x,y){
if(条件忘了，好像不是y==0)
        return x;
else
        reurn f(y,x mod y);
}
让你选出最后的那个语句填什么。
还有一道是给你一段C，找那个是unreachable的和dead的。
还有一道是判断两个逻辑表达式是否是satisfiable和永真的，好像是(p->q)*(p*~q)和(q->p)+(忘了)。
还有是给你一个DFA的状态转换表，和一个串，问最终输出什么？
还有一道是给了一个BNF，问选项中那个式子无法由BNF产生。
还有一道是由关dynamic checking的，I dnamic checking run time 时做,II dynamic checking can find all type error through some sample program.III忘了
还有一道是考选项中那个时binary sreach tree 的。
operating system中有考MMT的一道题，具体忘了。
还有一道软功的题问那种测试不需要知道程序的具体的内部细节。

暂时只回忆起来怎么多了。

[[i] Last edited by zhj on 2005-9-18 at 00:41 [/i]]

imongUID：140258

最初由 zhj 发布
[B]我来补充点吧
印象中好像有两道以前的真题，
{set A 有 m elements set B 有 n elements,问映射有多少种的那个}
{A 为要分配的mem，B为align后分配的mem，fragment＝1－..

以下省略...... [/B]

Fabulous...Thanks！！