笔试题目1

4.   已知一段文本有1382个字符，使用了1382个字节存储，这段文本全部是由a、b、c、d、e字符组成，a 354次，b 483次，c 227次，d 96次，e 222次，对这5个字符使用哈夫曼编码。则以下说法正确的是？（）

A.  使用哈夫曼编码后，使用编码值来存储这段文本将花费最少的存储空间、

B.   使用哈夫曼编码后，a b c d e 这5个字符对应的编码值是唯一确定的

C.  使用哈夫曼编码后，a b c d e 这5个字符对应的编码值可以有多套，但每个字符的编码位数是确定的

D.  b这个字符的编码位数最短，d这个字符的哈夫曼编码位数应该最长

Char* getMem(void) {      Char * p = “hello world ”;
      P[5] = 0x0;
      Return p;
}
Voidtest(void) {      Char *s = 0x0;
      s = getMem();
      Printf(s);
}

19.下列哪些sql是等价的（）

A.  Select A.tname ,A.depart from teacher A joincourse B on B.tno = .A.tno

B.   Select A.tname ,A.depart from teacher A whereA.tno = course.tno

C.  Select A.tname ,A.depart from teacher wheretno in (select tno from course)

D.  Select A.tname ,A.depart from teacher where exsist (select * from course B where B.tno = A.tno);

21.将一个C类网络划分为3个子网，每个子网最少要容纳55台主机，使用的子网掩码是：（）
  A、255.255.255.248   B、255.255.255.224  C、255.255.255.224  D、255.255.255. 192

 192，保留6位计算得到的。3个子网不确定是怎么得到。

23、假设有关系模式R(A,B,C,D),其数据依赖集：F={(A,B)- >C,C->D},则关系模式R的规范化程度最高达到：（）
A.1NF
B.2NF
C.3NF
D.BCNF

这个也不太会，同学说选择应该是B。

24.以下为一段浏览器中可运行的Javascript 代码，则运行该段Javascript代码的页面弹出框中显示的结果是：（）
Var obj = { “key”:”1”,”value”:2};
Var newObj = obj;
newObj.value += obj.key;
alert(obj.value);
A、2           B、12          C、3         D、21

javascript的题目，答案是D...我还以为是考引用的...？？？

25.有足够量的2分、5分、1分硬币，如果想凑齐一元钱，可以有（）种方法
A、541    B、270   C、1024    D、128

说明：看成50个2分和20个5分构成小于一元，不够的用1分来补。当20个5分，2分0个共1种；当19个5分时，2分可能有：0,1,2共3种；。。。。。。当有2个5分时，2分可能有0,1,2...45共46种；当有一个5分时，2分可能有：0,1,2...47共48种；当有0个5分，2分可能有：0,1,2...50共51种。所以共有1+3+...+48+51=（1+48）+（3+46）+...+（23+26）+51=49*（20/2）+51=541  

29.

#include <stdio.h>
class Base
{
public:
virtual int foo(int x){return x*10;}
int foo(char x[14]){return sizeof(x)+10;}
};
class Derived:public Base
{
int foo(int x){return x*20;}
virtual int foo(char x[10]){return sizeof (x)+20;}
};
int main(void)
{
Derived  stDerived;
Base * pstBase=& stDerived;
char x[10];
printf(“%d\n”,pstBase->foo(100)+pstBase->foo(x));
return 0;
}

在32位环境下，以上程序的输出结果是（）
2014， 蛮经典的考到两点，1）虚函数，基类指着指向派生类时，如果调用的是基类已经声明过的虚函数，动态绑定，如果不是虚函数，那么基类指针将会体现裁割的性质，就是只能指向派生类对象的基类部分；2）数组在传递给函数时退化成了指针，当数组作为非引用类型的形参时，编译器不会检查数组大小，x就是指针，只有当引用传递数组才会检查传递的数组大小，传递的不再是数组的指针而是数组的引用本身

A. 珠宝商甲需要去鉴定一批41克以下的宝石（可能是41克以下不包括41克的任意重量），他只能携带一个天平和四个砝码去称重，请问他会携带那些重量的砝码？  1 3 9 27  

说明：我第一反应有两种思路。1、由上往下尝试，假设需要40/2=20，转化为有3个发吗解决1-20的问题，发现走不通；2、然后尝试由下往上，首先以2倍为步长，明显不行，再以3倍为步长1,3,9,27，短暂尝试发现确实可以经过加减构造出任意1-40.  

阿里

8.char str[] = "hello";
sizeof(str)             //6
char *p = str;
sizeof(p)               //4
sizeof(*p)              //1

设N为总的节点数！总的入度=20*4+10*3+1*2+10*1=122=N-1，所以N=123。而N又=20+10+1+10+n（n为度为0的点，即叶子）即n=82

2^100=2^99*2=8^33*2=(7+1)^33*2=(7^33+33*7^32+……+33*7+1)*2=2*7^33+2*33*7^32+……+2*33*7+2
前面的项都是7的倍数
最后是2
所以余数是2

停时是一个随机变量。你给定一个条件，让这个过程在某个时刻停下。这个停下的时间就是停时。
比如我要在时间t=5时停下，那么这个停时就永远是5。从概率论的角度来讲这个停时就是一个定义在trivial sigma algebra上的随机变量。
比如我要在这个过程达到10的时候停下，那么因为这个过程是随机的，所以这个停时也是个随机变量。因为这个过程在什么时候达到10是随机的。
但是要注意一个停时只能定义在在这个停时之前的时间所关联的sigma域上。比如你可以让一个过程在它第一次达到10的时候停下，这个时间是一个停时。但是你不能让一个过程在它最后一次达到10的时候停下。因为你永远不知道这一次停下是不是最后一次。因此它就不是一个停时。

停时定理就是说如果一个鞅满足特定条件（这些条件基本就是要求停时和过程本身almost surely bounded）那么这个鞅在任何停时的期望值等于它在零时刻的期望值

22.下面关于二叉搜索树的正确说法包括——

A、待删除结点有左子树和右子树时，只能使用左子树的最大值结点替换待删除结点。

B、给定一棵二叉搜索树的前序和后序结果，无法确定这棵二叉树

C、给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的

D、给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树

A,C

23.被称为中国雨人的周玮，仅仅使用1分钟的时间就可以对16位数字开14次方。那么，以下数字钟，不可能成为其候选答案的是——

A、11.0 B、12.0C、13.0D、14.0E、15.0

参考答案ADE。最小数字1000000000000000开14次方，得到11.7，最大数字9999999999999999开14次方，得到13.8。

25.某电子眼睛分辨率640*360；（省略一段废话）。蓝牙4.0最大带宽24Mbps，请问能否通过该技术将每秒50帧真彩（24bit）画面传输至它的屏幕。如果是，请说明原因，如果否，说明理论上大约多久才能传送一帧。

参考答案：不能，640*360*24*50=2.76*10^8>24*1024*1024=2.5*10^7。

26.将N条长度为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为——M*logN

26题：不是M*N？26题当然是堆排序啊.

归并问题？两两归并，先1 2归并，3 4归并，在重复就可以了，时间复杂度是NMlog（N）。总共logN次归并，每次NM，为NMlog(N)。

也可以用堆来做，结果一样，将N个链表头放入堆中，每次取出顶端节点插入，NM个元素都要进入堆，堆排序复杂度是log(n)、而后取出堆中元素。入堆的是链表，不是每个元素。我的思路是,一般的堆排序,一般是每个元素是一个数字,这里是每个元素一个链表。当前的值是链表头。每次选出来一个值是log(N)，一共N*M个数，故是M*NlogN。只是不同的做法而已...结果一样很正常啊。

我觉得可以理解成两两归并，两两归并，复杂度容易算。我觉得用堆要好理解些 ，更直接。

29.跳跃链表：(MIT麻省理工-算法导论公开课-12讲：跳跃表http://v.163.com/movie/2010/12/7/S/M6UTT5U0I_M6V2TTJ7S.html)

设当前在第i层第j列那个节点上。
i)如果第j列恰好只有i层（对应插入这个元素时第i次调用随机化模块时所产生的B决策，概率为1-p），则当前这个位置必然是从左方的某个节点向右跳过来的。
ii)如果第j列的层数大于i（对应插入这个元素时第i次调用随机化模块时所产生的A决策，概率为p），则当前这个位置必然是从上方跳下来的。（不可能从左方来，否则在以前就已经跳到当前节点上方的节点了，不会跳到当前节点左方的节点）
设C(k)为向上跳k层的期望步数（包括横向跳跃）
有：
C(0) = 0
C(k) = (1-p)(1+向左跳跃之后的步数)+p(1+向上跳跃之后的步数)
     = (1-p)(1+C(k)) + p(1+C(k-1))
C(k) = 1/p + C(k-1)
C(k) = k/p
    而跳跃表的高度又是logn级别的，故查找的复杂度也为logn级别

微软

1.死锁的条件：

1.互斥资源 2.不可剥夺 3.环路等待 4.请求与保持

1.mutual exclusion, 2.No preemption,4.hold and wait

2.TCP avoid congestion collapse:

A.Slow-start 

B.sliding window

C.fast retransmit

D.fast recovery

慢开始，拥塞窗口，快重传，快恢复

5. 20^13 mod 7 = 20^12*20 = (21-1)^12*20 , 6

7.28.5625 -》四进制 

每次将小数部分乘以对应的进制，相应的整数部分就是对应的数字
小数部分一直乘以4，直到小数部分为0结束
比如此例，整数部分就不说了，小数部分是：
0.5625 * 4 = 2.25                // (0.2)4            // 整数部分为2，第一位小数就是2
0.25 * 4 = 1                         // (0.21)4          // 整数部分为1，第二位小数就是1

(0.5625)10 = (0.21)4

总结：   实际工作中，对系统的了解越多越好。目前大多数的测试人员都是做黑盒测试，很少有做白盒测试的。 因为白盒测试对软件测试人员的要求非常高，需要有很多编程经验。做.NET程序的白盒测试你要能看得懂.NET代码。做JAVA程序的测试，需要你能看懂JAVA的代码。 如果你都能看懂了，你还会做测试么

A.memory mapped file

B.Socket

C.semaphore

D.file

E.signal

C？？

1   文件映射
　　文件映射(Memory-Mapped Files)能使进程把文件内容当作进程地址区间一块内存那样来对待。因此，进程不必使用文件I/O操作，只需简单的指针操作就可读取和修改文件的内容。文件映射是在多个进程间共享数据的非常有效方法，有较好的安全性。但文件映射只能用于本地机器的进程之间，不能用于网络中，而开发者还必须控制进程间的同步。

2  共享内存
　　Win32 API中共享内存(Shared Memory)实际就是文件映射的一种特殊情况。进程在创建文件映射对象时用0xFFFFFFFF来代替文件句柄(HANDLE)，就表示了对应的文件映射对象是从操作系统页面文件访问内存，其它进程打开该文件映射对象就可以访问该内存块。由于共享内存是用文件映射实现的，所以它也有较好的安全性，也只能运行于同一计算机上的进程之间。

3  匿名管道
　　管道(Pipe)是一种具有两个端点的通信通道：有一端句柄的进程可以和有另一端句柄的进程通信。管道可以是单向－一端是只读的，另一端点是只写的；也可以是双向的一管道的两端点既可读也可写。
　　匿名管道(Anonymous Pipe)是 在父进程和子进程之间，或同一父进程的两个子进程之间传输数据的无名字的单向管道。通常由父进程创建管道，然后由要通信的子进程继承通道的读端点句柄或写 端点句柄，然后实现通信。父进程还可以建立两个或更多个继承匿名管道读和写句柄的子进程。这些子进程可以使用管道直接通信，不需要通过父进程。
　　匿名管道是单机上实现子进程标准I/O重定向的有效方法，它不能在网上使用，也不能用于两个不相关的进程之间。
4  命名管道
　　命名管道(Named Pipe)是服务器进程和一个或多个客户进程之间通信的单向或双向管道。不同于匿名管道的是命名管道可以在不相关的进程之间和不同计算机之间使用，服务器建立命名管道时给它指定一个名字，任何进程都可以通过该名字打开管道的另一端，根据给定的权限和服务器进程通信。
　　命名管道提供了相对简单的编程接口，使通过网络传输数据并不比同一计算机上两进程之间通信更困难，不过如果要同时和多个进程通信它就力不从心了。

9 动态连接库
　　Win32动态连接库(DLL)中的全局数据可以被调用DLL的所有进程共享，这就又给进程间通信开辟了一条新的途径，当然访问时要注意同步问题。
　　虽然可以通过DLL进行进程间数据共享，但从数据安全的角度考虑，我们并不提倡这种方法，使用带有访问权限控制的共享内存的方法更好一些。

12 Sockets
　　Windows Sockets规范是以U.C.Berkeley大学BSD UNIX中流行的Socket接口为范例定义的一套Windows下的网络编程接口。除了Berkeley Socket原有的库函数以外，还扩展了一组针对Windows的函数，使程序员可以充分利用Windows的消息机制进行编程。
　　现在通过Sockets实现进程通信的网络应用越来越多，这主要的原因是Sockets的跨平台性要比其它IPC机制好得多，另外WinSock 2.0不仅支持TCP/IP协议，而且还支持其它协议(如IPX)。Sockets的唯一缺点是它支持的是底层通信操作，这使得在单机的进程间进行简单数据传递不太方便，这时使用下面将介绍的WM_COPYDATA消息将更合适些。

Linux下的进程间通信机制大致包括：管道、信号（在Windows上成为消息）、信号队列（实际是消息链表）、共享内存、信号量、套接字。

共同点

 由上面的分析可以看出两个操作系统共有的且用的较多的进程间通信机制有：管道、消息、共享内存和套接字。简介如下：

  管道（Pipe）及有名管道（named pipe）：管道可用于具有亲缘关系进程间的通信，有名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。

   信号或者消息（Signal）：信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身。

   共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。

   套接口（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。

临界区，互斥量，信号量，事件的区别
===================================
四种进程或线程同步互斥的控制方法
1、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
2、互斥量:为协调共同对一个共享资源的单独访问而设计的。
3、信号量:为控制一个具有有限数量用户资源而设计。
4、事 件:用来通知线程有一些事件已发生，从而启动后继任务的开始。




临界区(Critical Section)(同一个进程内，实现互斥)
===================================
保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。




互斥量(Mutex)(可以跨进程，实现互斥)
===================================
互斥量跟临界区很相似，只有拥有互斥对象的线程才具有访问资源的权限，由于互斥对象只有一个，因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出，以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。
互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。




信号量(Semaphores)(主要是实现同步，可以跨进程)
===================================
信号量对象对线程的同步方式与前面几种方法不同，信号允许多个线程同时使用共享资源，这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。一般是将当前可用资源计数设置为最大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就会减1，只要当前可用资源计数是大于0的，就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目，不能在允许其他线程的进入，此时的信号量信号将无法发出




事件(Event)(实现同步，可以跨进程)
===================================
事件对象也可以通过通知操作的方式来保持线程的同步。并且可以实现不同进程中的线程同步操作。

11.数据库外键

12.编译器从源文件产生可执行二进制文件的过程

C语言编译全过程


    编译的概念：编译程序读取源程序（字符流），对之进行词法和语法的分析，将高级语言指令转换为功能等效的汇编代码，再由汇编程序转换为机器语言，并且按照操作系统对可执行文件格式的要求链接生成可执行程序。
    编译的完整过程：C源程序－－>预编译处理(.c)－－>编译、优化程序（.s、.asm）－－>汇编程序(.obj、.o、.a、.ko)－－>链接程序（.exe、.elf、.axf等）

14.c++的构造函数

注意点：

首先都是基于cross join(笛卡尔乘积），然后是inner join，在笛卡尔乘积的结果集中去掉不符合连接条件的行。
left outer join 是在inner join的结果集上加上左表中没被选上的行，行的右表部分每个字段都用NUll填充。
right outer join 是在inner join的结果集上加上右表中没被选上的行，行的左表部分全用NULL填充。