CS(计算机) 2007考场知识点回忆+某些题目回忆

emil167UID：2277371

前言：（本部分纯属扯淡，时间紧迫的老大们请自行跳跃致正文部分）
    标题之所以那样叫是觉得可能会给后来的同志们带来搜索上的快感。之所以鄙视ets的邪恶保密要求上来写这个是觉得cs sub的回忆帖太少了，practice book上面的东西
对复习也没啥实际意义。
    那些什么“水平有限，如有错误请指正”之类的和谐废话我就不说了，看完之后有什么反应都是正常，俺挺得住。
    考过的老大们发现问题一定要说！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！不然我就成罪人了……

----------------------------------------------------正------------文------------由------------此------------开------------始------------------------------------------------------------------------------------

1.图论中涉及最小生成树的内容：
    包括加权和不加权的无向图的最小生成树算法，以及算法的时间复杂性（平均、最坏），可判定性（哪些生成树的问题是可判定的，哪些是np的，哪些是np完全的），
给出一个具体的图，能够手工找出最小生成树。这次考试出了9道左右spanning tree 的问题，所以份量很重，需要格外注意。
    有向图的算法似乎比无向图的简单？这次虽然没有出，但是看看应该没坏处吧。
2.组成原理中cache结构的内容：
    cache似乎是这次唯一和组成原理有关的东西吧，出的东西都比较的细节。一共不超过3道。比如：一个32位的系统，有若干M那么大的cache，cache是用4路组相联的方式组织的，还有
若干条件，之后问：给cache编地址需要多少多少位的二进制数。再比如：给了一个cache的实例（一堆条件描述）和相关的cache调度算法，然后给了一个访存序列，问
这个序列每次访存时是命中还是不命中。
    总之cache的东西不是很难，但是凑巧某些点没看过就抓瞎了，所以看的时候每个点都要看到。
3.网络协议
    TCP的相关内容都看看吧，这次的2道都是计算题，就是给了很详细的一堆数，然后根据tcp协议规定的行为算出一个实际运行时的数。
4.数字逻辑
    先来个回忆题：一个逻辑器件的集合A被称为是XXX的，如果只用A中的器件就能够实现所有的布尔函数表达式。我们有一个逻辑器件L，它有三个输入，一个输出。当L的
三个输入中有至多一个“1”时，L输出“1”；当L的三个输入中有两个或两个以上的“1”时，L输出“0”。问：下列哪些器件的集合是XXX的：
{与非门}、{L，非门}、{与门、或门}
    再来个回忆题：给了一个逻辑图（P、Q、R、x是输入，剩下的部分是与非门等简单的逻辑门），对应的布尔表达式还算容易。然后问：PQR分别取什么输入的时候这个电路的
输出不是常数。（也就是x变化的时候输出也要变化）。
    数字逻辑应该就这两个。
5.java
    java这几年非常火啊，这次出了好几个，没学过，所以很多都不会。其中有一个是给了一个java类的定义，然后问这段代码编译的时候会发生什么现象（比如运行时错误什么的）。
6.其他的一些回忆题：
    a.有这样一段程序：
int main()
{
    int i；
    for ( i=0 ; i < 4 ; i = i+1 )
      {
          output( i );
          fork( );
       }
}
说明：output（i）函数负责把i 的值输出到屏幕上。fork（）建立一个新的进程，并且这个子进程和父进程是identical的包括变量的名字和值，以及代码结构。我们不知道系统的
进程调度策略是什么。
问：这个函数编译运行之后屏幕上面的输出内容会有多少种？（选项有1，3，4，10，10以上）

      b.有这样一段程序：
int main()
{
    int x，y；
    一堆代码
    while ( x!=y )
      {
          x=x-1;
          y=y-2;
       }
}
说明：不考虑整型变量的下溢和上溢。
问：   在进入while函数的时候x和y分别需要满足什么条件，才能够保证一定会从while中退出。
选项： (x>=y, x is odd, y is even)
           (x>=y, x is even, y is odd)
           (x<=y, x is odd, y is even)
           (x<=y, x is even, y is odd)
           (剩下一个肯定不对的记不清了)
    c.这个有人写过了，在此致以敬意，重写一下就算转载了吧。
      有一个骰子不是均匀的，1到5点出现的概率是相同的，为描述方便，记为p，6点出现的概率是3p。问：投两次骰子，所得的点数之和是11的概率有多大。
    d.这个也有人写过了，重写转载下下，嗯。
      7的10次方除以11的余数是几。
      我的办法：7^10=49^5=(44+5)^5=f，易知，f按照二项式定理展开之后只有一项不被11整除，就是5^5。这样就得到了一个简化的问题版本：5^5除以11
余数是多少。一直这样处理，很快就得到结果了。
    e.哪个数据结构是只用n个单元这么长的一个array就装得下的：链表，堆，B tree，？，？


----------------------------------------------------正------------文------------暂------------时------------结------------束------------------------------------------------------------------------------------

    忽然发现很多有印象的题只剩下印象了，所以没有发出来，将来什么时候说不定会来补充两句。那个，面向对象只考了一个，题目都没看懂。
    很令人欣慰的是今年竟然已经有计算机回忆帖了，很好，明年的筒子们有福气了^_^。
    最后罗嗦一句：为啥sub分类的时候没有计算机这一项啊？搞的发帖子的时候还要选“未归类”……

NETEMUID：2283160

看不懂 帮顶

xfdeng2008UID：2424797

thanks ，helpful

poler2005UID：2196213

其实 7的10次 模11
可以用费马定理   直接等于1