全部用英文，试卷纸，答卷纸；解答也要求用英文。
  一共4大题：
一、单选（选对1分，选错倒扣0.25，不选0分），一共26题，每题5个选项
  1，问能用8位二进制数的最小的10进制数
答：1000 0000(2)=-128(10)

1、在计算机系统中，数值一律用补码来表示（存储）。

主要原因：使用补码，可以将符号位和其它位统一处理；同时，减法也可按加法来处理。另外，两个用补

码表示的数相加时，如果最高位（符号位）有进位，则进位被舍弃。

2、补码与原码的转换过程几乎是相同的。

数值的补码表示也分两种情况：

（1）正数的补码：与原码相同。

例如，+9的补码是00001001。

（2）负数的补码：符号位为1，其余位为该数绝对值的原码按位取反；然后整个数加1。

例如，-7的补码：因为是负数，则符号位为“1”,整个为10000111；其余7位为-7的绝对值+7的原码

0000111按位取反为1111000；再加1，所以-7的补码是11111001。

已知一个数的补码，求原码的操作分两种情况：

（1）如果补码的符号位为“0”，表示是一个正数，所以补码就是该数的原码。

（2）如果补码的符号位为“1”，表示是一个负数，求原码的操作可以是：符号位为1，其余各位取

反，然后再整个数加1。

例如，已知一个补码为11111001，则原码是10000111（-7）：因为符号位为“1”，表示是一个负

数，所以该位不变，仍为“1”；其余7位1111001取反后为0000110；再加1，所以是10000111。

在“闲扯原码、反码、补码”文件中，没有提到一个很重要的概念“模”。我在这里稍微介绍一下“模”

的概念：

“模”是指一个计量系统的计数范围。如时钟等。计算机也可以看成一个计量机器，它也有一个计量范

围，即都存在一个“模”。例如：

时钟的计量范围是0～11，模=12。

表示n位的计算机计量范围是0～2(n)-1，模=2（n）。【注：n表示指数】

“模”实质上是计量器产生“溢出”的量，它的值在计量器上表示不出来，计量器上只能表示出模的

余数。任何有模的计量器，均可化减法为加法运算。

例如： 假设当前时针指向10点，而准确时间是6点，调整时间可有以下两种拨法：

一种是倒拨4小时，即：10-4=6

另一种是顺拨8小时：10+8=12+6=6

在以12模的系统中，加8和减4效果是一样的，因此凡是减4运算，都可以用加8来代替。

对“模”而言，8和4互为补数。实际上以12模的系统中，11和1，10和2，9和3，7和5，6和6都有这个特

性。共同的特点是两者相加等于模。

对于计算机，其概念和方法完全一样。n位计算机，设n=8， 所能表示的最大数是11111111，若再

加1称为100000000(9位)，但因只有8位，最高位1自然丢失。又回了00000000，所以8位二进制系统的

模为2(8)。 在这样的系统中减法问题也可以化成加法问题，只需把减数用相应的补数表示就可以

了。把补数用到计算机对数的处理上，就是补码。

另外两个概念

一的补码(one's complement) 指的是正数=原码,负数=反码

而二的补码(two's complement) 指的就是通常所指的补码。

这里补充补码的代数解释：

任何一个数都可以表示为-a=2^(n-1)-2^(n-1)-a;

这个假设a为正数，那么-a就是负数。而根据二进制转十进制数的方法，我们可以把a表示为：a=k0*2^0+k1*2^1+k2*2^2+……+k(n-2)*2^(n-2)

这里k0,k1,k2,k(n-2)是1或者0，而且这里设a的二进制位数为n位，即其模为2^(n-1),而2^(n-1)其二项展开是:1+2^0+2^1+2^2+……+2^(n-2)，而式子：-a=2^(n-1)-2^(n-1)-a中，2^(n-1)-a代入a=k0*2^0+k1*2^1+k2*2^2+……+k(n-2)*2^(n-2)和2^(n-1)=1+2^0+2^1+2^2+……+2^(n-2)两式，2^(n-1)-a＝(1-k(n-2))*2^(n-2)+(1-k(n-3))*2^(n-3)+……+(1-k2)*2^2+(1-k1)*2^1+(1-k0)*2^0+1,而这步转化正是取反再加1的规则的代数原理所在。因为这里k0,k1,k2,k3……不是0就是1，所以1－k0,1-k1,1-k2的运算就是二进制下的取反，而为什么要加1，追溯起来就是2^(n-1)的二项展开式最后还有一项1的缘故。而-a=2^(n-1)-2^(n-1)-a中，还有-2^(n-1)这项未解释，这项就是补码里首位的1，首位1在转化为十进制时要乘上2^(n-1)，这正是n位二进制的模。

不能贴公式，所以看起来很麻烦，如果写成代数式子看起来是很方便的。

注：n位二进制，最高位为符号位，因此表示的数值范围-2^(n-1) ——2^(n-1) -1,所以模为2^(n-1)。上面提到的8位二进制模为2^8是因为最高位非符号位，表示的数值范围为0——2^8-1。

;

    2，10101010101写成10进制和16进制分别是多少
答：1365(10) 555(16)

    3，数列题，16进制，0x64,0x190,0x384,0x640,0x9C4
答：100，400，900，1600，2500，（3600）

    4，数列题，16进制，0x1,0x8,0x1B,0x40,0x7D
答：1,8,27,64,125,(216)

    5，因式分解，9x^2-49
答：9(x+3)(x-3)

    6，7 概率题，说3个人，每人一个口袋，里面4个球，1red，3blue
  然后就是拿球的概率，超简单，都是乘法定律。
答：要复习下概率论了。

    8，问int **a[10]; 的意思
答：a是一个指向数组的指针的指针

    9，问int *(*a)[10];
答：

答：a是一个指向数组的指针，数组的每个元素是一个函数。

    11－13 问的是replace算法，给出了5个进程，和他们的loaded，last accessed的时间
问下列算法，会替换哪个进程

答：复习下进程的替换策略吧，参考“操作系统：设计与实现”
最优算法（OPT）; 最久未使用算法（ LRU least recently used）; 先进先出算法（FIFO）; 第二次机会算法（Second Chance）; 时钟算法（Clock）; 最近未使用算法（ NRU Not recently used）

    14，6个driver，n个process，每个process需要2个driver，问which n, deadlock

  选项记不清了，好像n＝3，n<=3, n<6, n = 6，none of above
答：进程死锁问题，好像有个公式

答：16

    16 问N个noodles，每次找两个ends，连起来，直到no ends，问expacted number of

答：把单根的N个绳子打结，共要个N结。

    17 一段C程序，主要考察const char*, const
答：const在c中表示“只读”，即不能更改

输出：bsdf
说明const constchar与constchar const 是一样的，都是一个指向char的常指针

    18 一大段话，选True or False，进程调度，有关priority inversion（逆置）
答：

答：

大多数商用实时操作系统(RTOS)均采用基于优先级的抢先调度器，这些系统为每个任务分配唯一的优先等级。调度器可以保证在所有等待运行的任务中，真正运行的总是具有最高优先级的任务。为了满足上述目标，调度器需要在执行中抢先优先级较低的任务。
由 于多个任务共享资源，调度器控制范围以外的事件可以在必要的情况下阻止具有最高优先级的准备就绪任务运行。如果出现这种情形，将有可能使任务错过临界期限 (critical deadline)，从而导致系统崩溃。优先级倒置就是当具有最高优先级的准备就绪任务在应该运行却无法执行时所采用的一项应急措施。

优先级倒置研究获得了两种解决方案。第一种方案称为优先级继承(priority inheritance)，该技术强令低优先级的任务继承与之共享资源并被挂起的任意高优先级任务的优先等级。一旦高优先级任务开始挂起，即可实施优先级 继承，直到资源释放。这需要得到操作系统的大力支持。

第二种解决方案称为优先级顶置(priority ceiling)，该方案为每种资源都分配优先级；调度器将该优先级传送至任何存取资源的任务，而分配给资源的优先级则为最高优先级用户的优先级。一旦任务完成对该资源的操作，其优先级恢复正常。
优先级顶置的一大特色就在于任务可以共享资源，并且只需简单地改变资源的优先级，因此就不再需要信号量。

    20 很简单的C程序，问result
  21 还是C程序，主要问sizeof()
答：sizeof是C语言的一种单目操作符，用于计算所占字节大小。

在vc上结果是24，在gcc上是20

  22 C程序，问常量定义和函数调用中的print("%d",__LINE__);
答：__LINE__是个用于调试的宏，表示代码所在的行数。

    23，24 C程序，考察 N1 >>= 1 和 N2  = (n1 & 1)

    25, 26 也是很简单的C程序，选择题

    二、information question,两道选择，EMC的R&D center at Beijing and Shanghai，
  1，你首选工作地点：（ft，－Shanghai）

  三、Bonus question，下个C/C  的函数
  从单链表中找到一个cycle
答：程序员面试宝典177页。设置两个步长不等的游标，一个步长为1，一个为2，两个游标同时出发，若能再次相遇则是循环链表。

    四、简答，in English
  starvtion 和 deadlock 的异同
答：
异：饥饿是指进程因优先级抢占等原因分配不到处理器资源，死锁是指进程分配到了处理器资源，而无法继续进行。
同：无论何种原因，该进程都因得不到想要的处理器资源而无法运行

时间是两个小时，从两点到四点。题目全英文，分三部分，第一部分是29道五选一，第二部分两个信息问题，第三部分三道编程题。其中第二部分的信息题一个问你工作地点首选北京还是上海，第二题问你备选城市有哪些。

    第一部部分的选择题既有智力题也有计算机基础知识题还有编程语言题。

    1.7×(1/7) = 1是什么率？
答：交换律？结合律

    2.What's database view?
答：视图，也可以理解为虚表。A database view displays one or more database records on the same page. A view can display some or all of the database fields.

    3.4*(3*2) = (4*3)*2是什么率？
答：结合律。

    4.ABCDEF六城市两两相连，问从A到B经过其他城市有且只有一次的路径有多少个？
答：

    9.对代码中syntax进行分析用到的什么文法？
答：编译的知识，语法分析---上下文无关的文法(context-free grammars)

    10.问要进行stable的sorting，会避免使用哪种算法？
答：稳定算法：基数排序 归并 简单排序(O(n^2))如冒泡、插入
    不稳定算法：快速排序，堆排序，希尔排序、选择

  17.0.15625写成二进制是什么 0.000101
答：
（1）二进制转换为十进制

将每个二进制数按权展开后求和即可。请看例题：

把二进制数（101.101）2=1*2^2+0*2^1+1*2^0+1*2^-1+0*2^-2+1*2^-3=（5.625）10

（2）十进制转换为二进制

一般需要将十进制数的整数部分与小数部分分开处理。

整数部分计算方法：除2取余法 请看例题：

十进制数（53）10的二进制值为（110101）2

小数部分计算方法：乘2取整法，即每一步将十进制小数部分乘以2，所得积的小数点左边的数字（0或1）作为二进制表示法中的数字，第一次乘法所得的整数部分为最高位。请看例题：

将（0.5125）10转换成二进制。（0.5125）10=（0.101）2

  18.问1,2,3,5,8,13...这个数列，第58个除以第57个得多少？1.618 F数列最后接近黄金分割

  19.问关于fopen(“w”)的问题（主要是覆盖而不是追加）

    20.问一连串cat和sort命令后输出

  22.问RAID0的作用
答：RAID 0又称为Stripe或Striping，它代表了所有RAID级别中最高的存储性能。RAID 0提高存储性能的原理是把连续的数据分散到多个磁盘上存取，这样，系统有数据请求就可以被多个磁盘并行的执行，每个磁盘执行属于它自己的那部分数据请求。 这种数据上的并行操作可以充分利用总线的带宽，显著提高磁盘整体存取性能。

把连续的数据分散到多个磁盘上存取，RAID 0 并不是真正的RAID结构, 没有数据冗余

    23.火星上到处是硬币，随便拿起一个，如果是头朝上的就翻成字朝上的，如果是字朝上的就抛出，落地后有各一半的机会头朝上或字朝上。再随便拿起包括刚才那个在内的所有硬币中的一个，重复前述步骤。问，很多很多次后字朝上和头朝上的硬币比例？2:1

    24.问RAID5的作用
答：RAID 5不对存储的数据进行备份，而是把数据和相对应的奇偶校验信息存储到组成RAID5的各个磁盘上，并且奇偶校验信息和相对应的数据分别存储于不同的磁盘上

    25.麦当劳有6块9块20块鸡的袋子，问大于等于N块的鸡都能正好用前述袋子装走的最小N是多少？
答：44

    26.问又要考虑安全又要充分利用带宽的网络中，是先加密后压缩，还是先压缩后加密?
答：先压缩，后加密

    27.问要使一群人存在2人同月出生概率不低于50％的最小人数是多少？
答：5

    28.c++中不可重载的运算符是？
答：.   .*  ::  ?:  .->     

    29.TCP/IP不存在那个层？（secure layer）

    主要体会是，一些基础知识平时要注意积累，特别是面向对象、RAIN、网络，很多笔试都有考到，智力题的话注意积累经验。

    第三部分是三道程序题。要求至少答两道，有时间也可以答三道。

    1.写一个画圆的函数

  要求：要让圆看起来连续圆滑，要画多余4×radius个点。

    画点使用int drawPoint(int x,int y)函数

    2.写出一段c++程序的输出。主要考察重载、多态、继承

  3.函数声明如下

  其中i <= N，功能输出i递增到N再递减到i的整数，每行输出一个数。比如func(1,5)就是

  要求是只用一条语句（函数体就一个分号）完成功能。要求：

    不能有逗号，不能有新变量声明，不能用?:，不能用循环，不能用char int 什么什么的保留字符

前两天EMC笔试中碰到的一道比较有意思的题目：碗里有n根面条，现在一次在碗中取任意两头（未必是同一根面条的）连在一起，直到没有面条的“头”剩下为止，问平均可以在碗里形成多少个圈？
答案参考全文阅读

【全文】
设n根面条得到的结果是f(n)，做一次“粘头”的操作其实可以分成两种情况：
1. 被粘的两头是同一根面条上的
这种情况的发生的概率是1/(2n-1)，此时平均圈数为1+f(n-1)
2. 被粘的两头是不同两根面条上的
这种情况的发生的概率是(2n-2)/(2n-1)，此时平均圈数为f(n-1)
于是有：

而f(1)=1
于是f(n)=sum(1/(2*i-1), i=1..n)

----------------------------------------------------------------------------------------------------

1. 有一个村庄，村庄里各户人家直到生出女孩来就不再生小孩了，而生男孩女孩的概率各是1/2。请问这个村庄男孩女孩的比例是多少

c这个题目迷惑性很大，可以从这个思路解答：第一胎男女比例为1：1，同理第2到n胎比例都为1：1，所以总的比例是1：1

2. 有一家人，老公、老婆、儿子还有老公的妈妈，其中有一个是律师，一个是医生
  如果医生比律师年轻，则医生与律师没有血缘关系
  如果医生的女的，那么医生和律师有血缘关系
  如果律师是男的，医生也是男的
请问我们能确定这家人里的那一个人
    a. 老公是医生
    b. 老婆是医生
    c. 儿子是医生
    d. 老公的妈妈是医生
    e. 以上都不对

3. 实验室里有1000个一模一样的瓶子，但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话，会在一个星期的时候死去，其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药

    e. 以上都不对
b每个瓶子用10位的二进制表示，白鼠编号为0-9，瓶子的某位为1表示给这个编号的白鼠喝这个瓶子的药

4. 有ABCDEF六个城市，每一个城市都和其他所有城市直接相连，问从A——B有多少种连接方式。路径不允许在两个城市之间往返。（这题的选项可能有的数记错了）

    e. 以上都不对

P为组合
然 后说一下读程序题。就程序本身来说都是很简单的程序，基本学过C语言的话，读懂语句应该没有问题的。有好几道都是算数列的，还有几道是 char 型数组，还有算循环次数的题目。只有两道题记得比较清楚，题目都是以程序形式给出的，我就把程序的大概意思按照我的理解写出来，可能有错，所以仅供参考。

1. 菲波那契数列 1,1,2,3,5,8,13……的第40位除以第39位得多少？即，N40/N39=？

    d. 以上都不对
b. Fabonacci数列连续两项之余好像是黄金分割点

2. 数列 0,1,3,6,10,15,21……从a0加到a10000得多少？

    e. 以上都不对

计算机基础知识的题目也不少，主要考点有B-tree，冒泡排序，堆栈，dual-link和单向link，小数点后的数十进制到二进制的转 化，ox进制，按位异或，C 和C++ 的 struct有什么区别，什么样的排序算法效率高，什么样的排序算法节省空间，还有一些网络存储磁盘阵列的很基础的题目。都不难，只可惜没学过什么，或者 说学了都忘了，所以就凭感觉了，看那个选项顺眼就选那个。

第二部分的编程题是要把N5 ->N4 ->N3 ->N2 ->N1的序列用一种自己熟悉的编程语言转化成N1 ->N2 ->N3 ->N4 ->N5。看起来是要用到指针的，由于我都忘干净了，所以啥也没写。

标 题: 今天下午的EMC笔经，智力题部分
            发信站: 水木社区 (Sat Sep 9 23:36:49 2006), 站内
            今天下午笔了EMC的intern笔试，我忘记我投的什么职位了，好像只有developer?
            写写智力题吧，基本上，英文能看懂就ok，可惜我英文太滥了，
            自己也是连猜带蒙。有理解不对的，其他同学纠正下吧！

     1。经过最少多少次比较能找出1000个元素中second smallest的一个

            2。六个城市两两相连，现在从A城市出发，连接每个城市一次且不重复的路径有多少条
            3。个位是8且是square of an integer的2-digit number有几个

            4。假设你要做一个practical building，which shape has the largest ratio of
            volume to surface area?体积除表面积最大
            A.Tetrahedron四面体
            B.4-side pyramid4面椎
            C.Cube立方体
           D.Sphere球
            E.Hemisphere半球
D感觉
            这题我记住你了！选项一个都不认识！我饮恨！找到一道不需要大学知识的我容易吗……
            5。10个口袋每个有100个金币，其中一个口袋每个金币9grams，其余正常的金币都是10grams。有个天平，问最少几次可以找出那个口袋
            6。四个人过*，分别10、5、2、1分钟，晚上只