时间：２０１２年１０月２１日下午４点

１.填空题：设x可以用n个5和m个7相加表示，x=5n+7m。求x的最小值，即大于等于x的数都可以用5和7表示。
我觉得是２５.
假设５ｎ＋７ｍ＝ｘ；５ｎ＇＋７ｍ＇＝ｘ＋１；１＋５ｎ＋７ｍ ＝５ｎ＇＋７ｍ＇ ；找出最小满足条件的ｎ＝ｍ＝２，此时ｘ＝２５,之后的２６＝２１＋５,２７＝２０＋７；２８＝２８；２９＝１４＋１５,；３０；３１＝２１＋１０；３２＝２５＋７；３３＝２８＋５；３４＝１４＋２０；３５……等等。个位数为从０——９都可以用５和７的倍数表示，因此最小的ｘ是２５。

２.填空题：从坐标原点（0.0）出发，360°都可以行走，每次行走距离为1，求行走两步后离坐标原点距离的期望。邓家超写的是１，走两步，最近走回原点，最远走到距离为２的圆周长上，转变为求这个小圆周上所有点到坐标原点距离的期望，取他们的圆心离坐标原点的值，即为１.

３.填空题：unix操作系统中进程间通讯的四种机制
管道＼消息＼共享存储区＼信号＼ 信号量
主要的四个是前４个：
（１）信号是用于通知发生一个进程同步事件的软件机制。信号类似于硬件中断，但没有优先级，即内核平等地对待所有的信号。对于同时发生的信号，一次只给进程一个信号，而没有特别的次序。进程间可以互相发送信号，内核也可以在内部发送信号。信号的传递是通过修改信号要发送到的进程所对应的进程表中的一个域来完成的。由于每个信号只保存为一位，因此不能对给定类型的信号进行排队。只有在进程被唤醒继续运行时，或者进程准备从系统调用中返回时，才处理信号。ｕｎｉｘ　ＳＶＲ４中定义的信号有：ｓｉｇｈｕｐ（阻塞；当内核设想该进程的用户正在做无用工作时发送给进程）ｓｉｇｉｎｔ（中断）ｓｉｇｂｕｓ（总线错误）等。
（２）管道是一个环形缓冲区，允许两个进程以生产者／消费者的模型进行通信。先进先出队列，由一个进程写，另一个进程读。创建一个管道后，它的大小是固定的字节数。当一个进程试图往管道中写时，如果有足够的空间，则写请求被立即执行；否则该进程被阻塞。类似的，如果一个进程试图读取多于当前管道中的字节数时，它也被阻塞，否则读请求被立即执行。操作系统强制实施互斥，即一次只能有一个进程可以访问管道。管道分有名管道和无名管道。只有“血缘“关系的进程才可以共享无名管道，而不相关的进程只能共享有名管道。
（３） 消息是有类型的一段文本。ＵＮＩＸ为参与消息传递的进程提供ｍｓｇｓｎｄ和ｍｓｇｒｃｖ系统调用。每个进程都有一个与之相关联的消息队列，其功能类似于信箱。消息发送者指定发送的每个消息的类型，类型可以被接收者用做选择的依据。当进程试图给一个满队列发送消息时，它将被阻塞；当进程试图从一个空队列读取时也被阻塞；如果一个进程试图读取某一特定类型的消息，但由于现在还么有这种类型的消息而失败时，该进程不会阻塞。
（４）共享存储区：ＵＮＩＸ提供的进程间通信速度最快的形式是共享存储区。这是被多个进程所共享的虚存中的一个公共内存块。进程读写共享存储区所使用的机器指令与读写虚存的其他空间所使用的指令相同。每个进程有一个只读或读写的权限。互斥约束不属于共享存储区机制的一部分，但必须由使用共享存储区的进程提供。
（５）信号量ｓｅｍＷａｉｔ和ｓｅｍＳｉｇｎａｌ原语的基础上进行推广。一个信号量包含以下元素：信号量的当前值＼在信号量上操作的最后一个进程的进程ＩＤ＼等待该信号量的值大于当前值的进程数＼等待该信号量的值为０的进程数。与信号量相关联的是在该信号量上阻塞的进程队列。信号量实际上是以集合的形式创建的，一个信号量集合有一个或多个信号量 。

４编程题：给定扑克牌中的序列（123456789TJQKA），1代表1，T代表10（十进制）A代表14（十进制），求相应十进制表示的字符串序列。我理解的就是14进制转换为10进制，其中数都是用字符串表示，且14进制给定的数序列中没有0.

5.编程题： 图G用邻接矩阵表示，求图G的联通子图
广度或者深度遍历图，当遇到栈空或者队列为空时，一个联通子图找到，再找图中没有遍历过的点，继续。

６.算法题：给定一个单词，在字典中求其兄弟单词，数据结构和算法。若单词改成汉语短语（长度小于５）该如何求解，需要哪些改变？