今天的CS sub回忆 zz

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]]