标签: 笔试题

一、星网锐捷 硬件笔试 1、在双向总线设计时，当总线没有输出的时候，应该将总线赋值为（） A逻辑0   B逻辑1   C高阻    D不定态 2、如果一个多接口设计电平需要支持LVCMOS33、LVCMOS25和PCI33_3的电平标准，那么在CPLD造型的时候，应该选择芯片的BANK数应该大于等于（） A2   B1    C3   D4 3、CPLD的复位信号低电平有效，那么复位信号在约束处理合理的是（） A端接上拉约束  B端接下拉约束  C端接总线保持约束，外部下拉    D端接悬浮约束，外部下拉 4、能够实现“线与”功能的门电路是（） A与非门  B或非门   C三态输出门   D集电极开路门 5、 6、 7、组合逻辑电路消除竞争冒险的方法有（） A前级加电阻  B在输出端接入滤波电容  C后级加缓冲电路  D屏蔽输入信号的尖峰干扰 8、 9、 10、设计一个四位二进制码的奇偶位发生器（假定采用偶检验码），需要几个异或门（） A 2   B3    C4   D5 11、在计算机存储体系中，缓存的作用是（） A弥补主存的存取速度不足  B缩短主存的读写周期  C减少CPU访问存储次数  D弥补主存容量不足的缺陷  12、计算机系统中的虚拟存储器的地址应是（） A逻辑地址  B物理地址  C间接访问地址  D直接访问地址 13、计算机系统中的外围设备的编址方式有（） A统一编址和独立编址  B直接编址和间接编址  C程序编址和硬件编址 D可骗址和不可编址 14、 15、所谓中断查询，查询的是（） A中断请求信号  B中断标志位  C外中断触发方式控制位  D中断允许控制位 16、负反馈放大电路中，为保证电路不产生自激，需引入补偿技术，为保证经补偿后的放大电路不的带宽不降低，需引入（） A简单电容补偿  B密勒电容补偿  C超前相位补偿 D滞后相位补偿 17、 18、在下图所示的N沟道增强型MOS管的驱动过程中，当MOS管G级与S级之间的电压VGS进入密勒平台前是驱动电压给等效电容（）充电的过程，电压VGS进入密勒平台后是驱动电压给等效（）充电的过程。 A CGS  CGD   B CGD  CGS  C CGS  CGS  D CGD CGD 19、 20、 21、 锐捷的题比较多，以后再补上。 二、海华电子  数字硬件（FPGA方向）  这个公司比较挑学校 1、在multiplier中配置生成一个常系数的乘法器，乘数为有符号型18位宽，常系数为-100，则运算结果的位宽为（） A 19  B 25   C 26  D 100 2、时钟周期为T，触发器D1的寄存器到输出时间最大为T1MAX，最小为T1MIN。组合逻辑电路最大延迟为T2MAX，最小为T2MIN。则触发器D2的建立时间应该满足什么条件（） A 大于T1MIN+T2MIN  B 大于T1MIN+T2MAX  C小于T1MAX+T2MAX  D小于T1MAX-T2MAX 3、 16分频电路要用多少个触发器（） A 3 B 4 C 5 D 6 4、在Distributed RAM G enerator 中生成一块Single Port RAM后，其管脚有addr ,data ,clk,we,q ,请分析其读写方式（） A 异步写，同步读 B 同步写，异步读 C 异步写，异步读 D 同步写，同步读 5、如何防止亚稳态（） A 降低系统频率 B 用反应更快的FF C 引入同步机制，防止亚稳态传播 D 改善时钟质量，用边沿变化快速的时钟信号 6、FPGA一般由静态存储器和三种可编程单元组成，它们分别是 ______ ______ _____ 7、时序逻辑电路通常包含______电路和_____电路，其中______ 电路是必须的。 8、数字电路中时序逻辑电路部分按照其触发器是否有统一的时钟控制分为____和___,其中______电路必须出现在时序逻辑电路中。 9、一个寻址容量为16K*8的RAM需要_____ 根地址线，____根数据线。若要扩展成32K*16的RAM,需要16K*8的RAM____块。 10、一个基本RS触发器在正常工作时，不允许输入R=S=1的信号，因此它的约束条件是_______. 简答题 11、如何将JK触发器构成T触发器，试画出逻辑框图。 12、什么是门控时钟？门控时钟的缺点是什么？ 3、简述FPGA与CPLD的内部结构区别  

一、深圳国微，国企，感觉不错   数字电路工程师笔试 1、分析电路回答问题，电路如下：    （1）A、B、C三点的电压，及VOUT=？ （2）分析两个PMOS管和反相器的作用。 2、更改下面的电路，使其功耗最低，并说明更改后，为何功耗更低      3、原题记不住了，大意是分析三段不同风格的Verilog代码，那些会产生latch，为什么会产生latch. 4、给出了一个全加器电路，（电路图记不住了），输出端由一个CFG信号控制MUX，CFG=0时，S,C0直接输出给C1,C2，CFG=1时，S,C0由D触发器打一拍再送给C1,C2。 （1）分析电路功能； （2）用verilog代码实现电路功能。 5、（1）设计一个带异步复位的D触发器电路； （2）结合D触发器的波形图，分析说明step time 和hold time.(D触发器波形图，记不住了），   还有两题忘了。这个公司，来得比较晚，去听宣讲会的人很少，只有几个人。做完卷子，当场就面试。这个卷子，他们大概看一下，主要问一些你做的项目和一些基础知识。  二、TI应用工程师笔试  信号链试题 题都记不住了。主要考查方面有:放大器、模数/数模转换器、时钟、接口。 题都比较偏具体的器件应用。如放大器带宽、ADC/DAC的信噪比怎么计算，怎么设计滤波电路，时钟考的是PLL的组成部分。接口主要考的是I2C、SPI两种。给出几个波形图，分析其具体是什么操作，读/写的数据是什么。 三、中兴移动笔试 也是题都记不住了。主要考查内容有：OTG，USBOTG是什么？有什么用。差分信号。放大电路的截止频率，定义及计算。用BJT实现和个简单的逻辑门，如与非、或非等。 星形电路与三角电路的转换，计算电路网络的电流电压。还有一个是充电电路。大多数都不会。 四、宇龙酷派 基带笔试 主要考查内容有：锁相环组成部分；功率放大器的三种工作状态；理想运放参数的特征；什么是肖特基二极管；TTL驱动CMOS,及CMOS驱动TTL时，需不需要加上拉电阻，为什么；共模抑制比的概念及计算公式；给出一个buck电路，分析其工作原理；用74LS138实现一个逻辑函数。

有些题不完整，是做完题出来回忆记下来的。特别简单的题可以没记，部分题只记了考点。 一、汇顶科技，这个公司在深圳，待遇不错。 1、有源、无源滤波器的区别及各自的优缺点，并画出电路图，写出其传递函数，还要画出幅频响应、相频响应波特图。 2、一个单相桥式整流电路，分析其工作原理。 3、填空题，一个表达式求最后结果，主要考逻辑运算符的优先级。 4、BJT单管放大电路，求其输入输出电阻。（什么组态，忘了） 5、给出一个运算电路图，求输出表达式。(比较简单） 以上是部分题，前面的题都还比较简单，最后一题不好做。 6、设计题：设计一个信号源响应测试仪。已有信号源1Hz------20MHz，幅值1V正弦信号。输入到二端口网络，信号源扫频输入，在输出口测相应频率信号的幅值和相位。要求：幅值、相位精度分别为正负1%、正负10.可选的器件有：12V DC电源、电阻、电容、电感、二极管、三极管、运放、稳压芯片10bitDAC、12bitADC. (1)\画出测量仪的系统模块框图，并说明每个模块的作用，连接关系。 （2）、画出幅值和相位检测电路，并说明各元件参数选择说明。 二、和利时，硬件笔试 1、电源模块设计中，电源调整率的定义及其计算公式。 2、24MHz的晶振，其温漂为正负100PPM，其正常工作温度为0到75摄氏度，设常温为25摄氏度，计算晶振输出频率范围。 3、RS485如何防护高频干扰，若通信速度较高，选择防护器件时，应注意什么参数。 4、现场总线技术的特点，种类、应用领域。 5、场效应管的特点。 三、烽火通信，硬件笔试 1、原题记不住了，大意是，在端到端时延和数据发送率一定的情况下，帧长，信道利用率和吞吐量的关系。 2、IP地址192.168.1.1属于______类IP地址。 3、UDP协议属于哪个层次的协议。 4、IPV6中，源地址或目的地址的长度为_________。 5、STM-1的信号速率为________Mbit/S。 6、拉曼光放大器中，被放大信号，波长为1550nm ，则泵浦光波长为 ______。 7、传输数字信号需要的带宽比模拟信号_______。 8、三网融合是指：_______________. 9、光纤通信发展的两个方向__________。 10、G652光纤在1310nm~~~~衰减系数________.(这个题记不清了，没学过光通信方面的，所以一点都不懂) 简答题 11、某网络的IP地址为180.6.0.0 子网掩码为255.255.252.0求（1）、子网地址、主机地址各占多少位（2）些网络最多能容纳主机总数（设子网和主机的全0、全1均不用）。 12、阐述交换机和路由器的区别。（当时在考试时，用手机上网抄了一点，结果面试的时候又被问了） 13、无源和有源滤波器的区别。 14、原题记不住了，给出了一个电容三点式谐振回路，计算其谐振频率。 这些题，有的是没学过，完全不会，有的是学过，但忘了或者一直没弄明白、没重视，还有一些非常简单的题没记下来。上面这些题，现在还有好多不会做，大家可以一起讨论。  

  一、单项选择题   1.下列说法不正确的是：（B）   　　A.SATA硬盘的速度速度大约为500Mbps/s   　　B.读取18XDVD光盘数据的速度为1Gbps   　　C.前兆以太网的数据读取速度为1Gpbs   　　D.读取DDR3内存数据的速度为100Gbps   解析：有说B的，有说D的，B肯定是不对的吧。   　　关于B选项：   　　理论上讲：DVD的1倍速是1350KB/s，CD是150KB/s，DVD的1倍速等于CD的9倍速。   　　因为CD容量是700MB左右，DVD单面单层（DVD-5）是4.7GB（实际为4.37GB），DVD单面单层的容量是CD的6.4倍左右，所以，1倍速的播放器在80分钟内把一张700MB的CD读取出来（700MB*1024/150KB/s/60=79.6min），1倍速的播放器在60分钟内把一张4.7GB的DVD读出来（4.37GB*1024*1024、1350KB/s/60=56.6min）   　　DVD的倍速:   　　1x：（1倍速）基本传输速率为1350KB/s。   　　2x：（2倍速）基本传输速率为2700KB/s。   　　4x：（4倍速）基本传输速率为5400KB/s。   　　18x：（18倍速）基本传输速率为24300KB/s=23M。   　　CD的倍速:   　　1x（1倍速）基本传输速率为150KB/s。   　　2x（2倍速）基本传输速率为300KB/s   　　4x（4倍速）基本传输速率为600KB/s。   　　8x（8倍速）基本传输速率为1200KB/s。       2.（D）不能用于Linux中的进程通信   　　A.共享内存   　　B.命名管道   　　C.信号量   　　D.临界区(每个进程访问临界资源的那段代码称为临界区；临界资源就是每次只允许一个进程访问的共享资源)   解析：   　　Linux进程间通信的几种主要手段简介：   　　（1）管道及有名管道：管道可用于具有亲缘关系的进程间通信；有名管道克服了管道没有名字的限制，因此，除了具有管道所具有的功能外，它还允许无亲缘关系进程间通信；   　　（2）信号：信号是比较复杂的通信方式，用于通知接收有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；linux除了支持Unix早期信号语义函数signal外，还支持语义符合Posix标准的信号函数sigaction（实际上，该函数是基于BSD的，BSD为了实现可靠信号机制，又能够统一对外接口，用sigaction函数重新实现了signal函数）；   　　（3）消息队列：消息队列是消息的链接表，包括Posix消息队列和system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列客服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点；   　　（4）共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其他通信机制，如信息量结合使用，来达到进程间的同步及互斥；   　　（5）信息量：主要作为进程间以及同一进程不同线程之间的同步手段；   　　（6）套接口：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。   　　Linux线程间通信几种主要通信手段简介：   　　（1）锁机制：包括互斥锁、条件变量、读写锁，互斥锁提供了以排他方式防止数据结构被并发修改的方法，使用条件变量可以以原子的方式阻塞线程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的，条件变量始终与互斥锁一起使用。读写锁运行多个线程同时读共享数据，而对写操作是互斥的；   　　（2）信号量机制：包括无名线程信号量和命名线程信号量；   　　（3）信号机制：类似于进程间的信号处理；   　　进程与线程的区别：   　　进程概念：   　　进程是表示资源分配的基本单位，又是调度运行的基本单位。例如，用户运行自己的程序，系统就创建一个进程，并为它分配资源。然后，把该进程放入进程的就绪队列。进程调度程序选中它，为它分配CPU以及其他有关子亚U年，该进程才真正运行。所以，进程是系统中并发执行的单位。   　　线程的概念：   　　线程是进程中执行运算的最小单位，亦即执行处理机调度的基本单位。如果把进程理解为在逻辑上操作系统所完成的任务，那么线程表示完成该任务的许多子任务之一。线程可以在处理器上独立调度执行，这样，在多处理器环境下就允许几个线程各自在单独处理器上进行。   　　引入线程的好处：   　　（1）易于调度。    　　（2）提高并发性。通过线程可方便有效地实现并发性。进程可创建多个线程来执行同一程序的不同部分。    　　（3）开销少。创建线程比创建进程要快，所需开销很少。   　　（4）利于充分发挥多处理器的功能。通过创建多线程进程（即一个进程可具有两个或更多个线程），每个线程在一个处理器上运行，从而实现应用程序的并发性，使每个处理器都得到充分运行。    　　进程和线程的关系：    　　（1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。    　　（2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。    　　（3）处理机分给线程，即真正在处理机上运行的是线程。    　　（4）线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。       3.设在内存中有P1,P2,P3三道程序，并按照P1,P2,P3的优先级次序运行，其中内部计算和IO操作时间由下表给出（CPU计算和IO资源都只能同时由一个程序占用）：   P1:计算60ms---》IO 80ms---》计算20ms   P2:计算120ms---》IO 40ms---》计算40ms   P3:计算40ms---》IO 80ms---》计算40ms   完成三道程序比单道运行节省的时间是（C）   　　A.80ms 　　　　B.120ms 　　　　C.160ms 　　　　D.200ms   解析：   　　单道运行的总时间为：60+80+20+120+40+40+40+80+40=520ms       4.两个等价线程并发的执行下列程序，a为全局变量，初始为0，假设printf、++、--操作都是原子性的，则输出不肯哪个是（A）      1 void foo() {  2   3     if (a = 0) {  4   5         a++;  6   7     }  8   9     else { 10  11         a--; 12  13     } 14  15     printf( "%d" , a); 16  17 }   　　A.01 　　　　B.10 　　　　C.12 　　　　D.22   解析：   　　对于B选项：P1执行程序，输入1，P2执行程序，输出0；   　　对于C选项：初始为0，P1执行完判断语句，决定要执行a++，中断，P2进行判断，此时a仍然等于0，执行判断语句，并执行输入，得到1，P1然后继续执行，此时它该执行a++，这时a=1，执行并输出，结果为2；   　　对于D答案：初始为0，P1执行完判断语句，决定要执行a++，中断，P2进行判断，此时a仍然等于0，执行a++，得到a=1，中断，P1继续执行a++，a=2，P1输出，得到2，P1结束，P2继续执行输出语句，得到2；       5.给定fun函数如下，那么fun(10)的输出结果是（C）   int fun(int x)    {       return (x==1) ? 1 : (x + fun(x-1));   }   　　A.0 　　　　B.10 　　　　C.55 　　　　D.3628800       6.在c++程序中，如果一个整型变量频繁使用，最好将他定义为（D）   　　A.auto 　　　　B.extern 　　　　C.static 　　　　D.register   解析：   　　C语言提供了四种类型修饰符：auto、register、extern、static。   　　auto修饰仅在语句块内使用，初始化可为任何表达式，其特定是当执行流程进入该语句块的时候执行初始化操作，没有默认值；   　　使用register修饰符修饰变量，将暗示编译程序相应的变量被频繁地使用，如果可能的话，应将其保存到CPU的寄存器，以加快其存储速度；   　　static静态变量声明符。在声明它的语句块、子程序块或函数内部有效，值保持，在整个程序期间分配存储器空间，编译器默认值为0,。是C/C++中很常用的修饰符，它被用来控制变量的存储方式和可见性。Static被引入以告知编译器，将变量存储在程序的静态存储区而非栈上空间。   　　extern可以置于变量或者函数前，以表示变量或者函数的定义在别的文件中，提示编译器遇到此变量或函数时，在其他模块中寻找其定义。另外，extern也可用来进行链接指定。       7.长为n的字符串中匹配长度为m的子串的复杂度为（B）   　　A.O(N) 　　　　B.O(M+N) 　　　　C.O(N+LOGM) 　　　　D.O(M+LOGN)   解析：有选B的，也有选C的。   　　这道题目首先想到的是KMP算法，时间复杂度为O(m+n)。但是还有的选择C选项，貌似是Sunday算法。       8.判断一包含n个整数a + a = a 的时间复杂度为（B）   　　A.O(n)    B.O(n^2)     C.O(nlog(n))    D.O(n^2log(n))   解析：   　　对于B选项，可以这样实现。   　　（1）先对数组进行排序，时间为O(nlogn)，然后从大往小取a ，n次   　　然后在0到k-1之间夹出i，j来...每次K操作...若存在负数，则需要在0到n-1之间夹出i,j；   　　（2）先对数组进行排序，时间为O(nlogn)，然后两次for循环嵌套，进行hash查找；   　　对于D选项，可以这样实现。   　　（1）先对数组进行排序，时间为O(nlogn)，然后两个for循环嵌套，二分查找a +a 是否在数组中；   　　   9.三次射击能中一次的概率是0.95，请问一次射击能中的概率是多少？（C） 　　A.0.32 　　　　B.0.5 　　　　C.0.63 　　　　D.0.85   解析：   　　公式很简单，1-（1-p)^3=0.95。接下来需要有一定的估算技巧。A选项可以看作1/3，C选项可以看作2/3，D选项可以看作4/5.       10.下列序排算法中最坏复杂度不是n(n-1)/2的是（D）   　　A.快速序排     B.冒泡序排   C.直接插入序排   D.堆序排   解析：   　　各种排序算法的时间复杂度：   　　插入排序思想：   　　将n个元素的数列分为已有序和无序两个部分，每次处理就是讲无序数列中的第一个元素与有序数列的元素从后往前逐个进行比较，找到插入位置，将该元素插入到有序数列的合适位置。   　　希尔排序思想：   　　希尔排序，也称为递减增量排序算法，是插入排序的一种高速而稳定的改进版本。   　　希尔排序是基于插入排序的以下两点性质而提出改进方法的：   　　（1）插入排序在对几乎已经排好序的数据操作时，效率高，即可达到线性排序的效率；   　　（2）但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；    　　选择排序思想：   　　首先在未排序的序列中找到最大（小）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最大（小）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。       二、不定向选择题   1.以下哪些进程状态转换是正确的(ABCE)   　　A.就绪到运行    B.运行到就绪    C.运行到阻塞    D.阻塞到运行    E.阻塞到就绪   解析：   　　进程调度：   　　四种进程间的状态转换： 　　    　　就绪—执行 执行—阻塞 阻塞—就绪  执行—就绪   　　1）进程的三种基本状态        进程在运行中不断地改变其运行状态。通常，一个进程必须具有以下三种基本状态：   　　就绪状态：   　　当进程已分配到除CPU以外的所有必要的资源，只要获得处理机便可立即执行，这时的进程状态就称为就绪状态；   　　执行状态：   　　当进程已获得处理机，其程序正在处理机上执行，此时的进程状态称为执行状态；   　　阻塞状态：   　　正在执行的进程，由于等待某个事件发生而无法执行时，便放弃处理机而进入阻塞状态。引起进程阻塞的事件有很多种，例如，等待I/O完成、申请缓冲区不能满足、等待信号等。   　　2）进程三种状态间的转换   　　一个进程在运行期间，不断地从一种状态转换到另一种状态，它可以多次处于就绪状态和执行状态，也可以多次处于阻塞状态。   　　A. 就绪—执行   　　处于就绪状态的进程，当进程调度程序为之分配好了处理机后，该进程便由就绪状态转换为执行状态；   　　B. 执行—就绪   　　处于执行状态的进程在其执行过程中，因分配给它的一个时间片已经用完而不得不让出处理机，于是进程从执行状态转换为就绪状态；   　　C. 执行—阻塞   　　正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态；   　　D. 阻塞—就绪   　　处于阻塞状态的进程，若其等待的事件已经发生，于是进程便从阻塞状态转变为就绪状态。       4.A和B晚上无聊就开始数星星。每次只能数K个（20=k=30）A和B轮流数。最后谁把星星数完谁就获胜，那么当星星数量为多少时候A必胜？（）   　　A、2013   B、2888   C、4062  D、***    E、****   解析：不懂   　　对于上述答案，A有必胜的策略，A、B、C、D、E都应该选择。首先，A选取，使剩余的星星为50的倍数。然后数星星的顺序为B、A、B、A......。B数k个星星，则A就数50-k个，使剩余星星始终剩余为50的倍数，最后，一定是A数最后的星星。A必胜。       三、填空问答题   1.给你一个整型数组A ，完成一个小程序代码（20行之内），使得A 逆向，即原数组为1，2，3，4，逆向之后为4，3，2，1。        3.有个苦逼的上班族，他每天忘记定闹钟的概率为0.2，上班堵车的概率为0.5，如果他既没定闹钟上班又堵车那他迟到的概率为1.0，如果他定了闹钟但是上班堵车那他迟到的概率为0.9，如果他没定闹钟但是上班不堵车他迟到的概率为0.8，如果他既定了闹钟上班又不堵车那他迟到的概率为0.0，那么求出他在60天里上班迟到的期望。   解析：概率为0.51       4.战报交流：战场上不同的位置有N个战士（n4），每个战士知道当前的一些战况，现在需要这n个战士通过通话交流，互相传达自己知道的战况信息，每次通话，可以让通话的双方知道对方的所有情报，设计算法，使用最少的通话次数，是的战场上的n个士兵知道所有的战况信息，不需要写程序代码，得出最少的通话次数。   解析：   　　笔试的时候是这样想的：N-1个人围成一个环，将知道的消息都告诉第N个人，需要N-1次，同时第N-1个人与第N个人交流时，两人互相交流消息，这样子第N-1个人与第N个人都知道了所有人的信息，接下来第N-1人沿着环将消息传递下去，需要N-2次，所以需要N-1+(N-2)=2N-3。   　　但是实际上这个问题有着更优的解法。   　　扩展的一类问题：   　　题目：假如我们班有n个MM，每一个MM都有一个独家的八卦消息。两个MM可以通过电话联系，一通电话将使得双方都获知对方目前已经知道的全部消息。要想所有n个MM都知道所有n条八卦消息，最少需要多少通电话？请给出通话方案。   　　来自：http://www.matrix67.com/blog/archives/1078   解答：   　　（1）分析情况   　　当n很小时我们很容易通过枚举的方法找出最佳通话方案：   　　A1=0 A2=1 A3=3 A4=4 A5=6 A6=8   　　（2）基于中间消息传递人的思想建模   　　可以先把所有消息集中于一个或几个人，然后再由这些消息汇总人把消息传给所有人。设n个MM中有m个消息汇总人，她们共享所有消息需要打An通电话。   　　通话方案如下：   　　第一、剩下的n-m个MM每个人从m个消息汇总人中随机选择一个通话。这样一来m个消息汇总人就掌握所有n条八卦消息，并且她们每个人所掌握的消息互不重叠，是互补的；   　　第二、m个消息汇总人通过打电话共享所有八卦消息；   　　第三、作为消息汇总人的m个MM再通过电话将自己新得到八卦新闻告知最开始打电话给自己的MM，使得她们也掌握所有n条消息；   　　模型如下：  　　       　　（3）模型分析   　　按照上面的通话方案，第一步需要n-m通电话，第二步需要Am通电话，第三步需要n-m通电话，故有An=2*（n-m）+Am，进一步化简得   　　An=2*n - （2*m - Am）   　　即当MM的个数为n时，共享所有八卦消息共需要2*n - （2*m - Am）通电话。若要使得通话次数最小，就要求（2*m - Am）最大。因此，取多少个MM作为消息汇总人使得（2*m - Am）最大成为了解决这个问题的关键，它反映了MM们之间通话的效率。记Em=（2*m - Am）。   　　当有一个消息汇总人即m=1时，E1=2*1 - A1=2；   　　当有两个消息汇总人即m=2时，E2=2*2 - A2=3；             　 m=3时，E3=2*3 - A3=3；                 m=4时，E4=2*4 - A4=4；                 m=5时，E5=2*5 - A5=4；                 m=6时，E6=2*6 - A6=4；                           .......   　　由归纳法可知，当m=4时，Em有最大值4，An有最小值2*n - 4，即当有大于或等于4个消息汇总人时可通过上述通话方案使得n个MM通过最小的电话数共享所有八卦消息。此时共需要2*n - 4次电话。   　　（4）模型证明         http://blog.csdn.net/linygood/article/details/8898844   　　（5）模型结果  　　   　　题目中如果告诉n大于4，那么结果就是2n-4。       5.有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。   解答：   　　这个问题等价于找未知序列数中的最小数，我们将reg这个函数等价为以下过程：如果i认识j，记作i大于等于j,同样j不一定大于等于i,满足要求，i不认识j记作i  　　       　　另外一种思路：    　　       四、综合题   有一个淘宝商户，在某城市有n个仓库，每个仓库的储货量不同，现在要通过货物运输，将每次仓库的储货量变成一致的，n个仓库之间的运输线路围城一个圈，即1-2-3-4-...-n-1-...，货物只能通过连接的仓库运输，设计最小的运送成本（运货量*路程）达到淘宝商户的要求，并写出代码。   解答：   　　这个题目类似的题目有：   　　题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1045 　　有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1，求使所有人获得均等糖果的最小代价。 分析： 　　假设a1分给an的糖果数为k，则可以得到以下的信息：       　　　　a1       a2          a3　　　　　　an-1 　　　　　an 　　当前数目：a1-k      a2　　　　　　　 a3　　　　　  an-1 　　　　　an+k 　　所需代价：|a1-k-ave| |a1+a2-k-2*ave| |a1+a2+a3-k-3*ave||a1+..+a(n-1)-k-(n-1)*ave|   |k| 　　以sum 表示从a1加到ai减掉i*ave的和值，这以上可以化简为 　　总代价 = |s1-k|+|s2-k|+...+|s(n-1)-k|+|k| 　　不难看出：当k为s1...s(n-1)中的中位数的时候，所需的代价最小  　　   ，对明星k,他不认识所有人，则k是其中最小的数，且满足其余的人都认识他，也就是其余的人都大于等于k.这样问题就被转换了。就拿n=5来说，首先有数组s ={a,b,c,d,e}这5个变量，里边存放着随机数，求是否存在唯一最小数，如果存在位置在s中的哪里。（楼主这里是这个意思，按我的理解题中这个最小数一定是存在且唯一的）。