网易2013校园招聘-测试：笔试题目（1）（含答案）

第一部分（必做）：计算机科学基础 

1、长为N的字符串中匹配长度为M的子串的算法复杂度是（）

 A.  O(N)  B. O(M+N)   C. O(N+logM)  D. O(M+logN) 

答：B 

2、以下排序算法中，哪些是稳定的排序算法（多选）

（） A.冒泡 B.插入 C.合并 D.希尔 E.快速排序 答：ABC 3、以下是一颗平衡二叉树，请画出插入键值3以后的这颗平衡二叉树。分析：考察平衡二叉树的基本操作，插入3变成不平衡，需要节点5右旋一次，节点2左旋一次。   

4、给定两个整数集合A和B，每个集合都包含20亿个不同整数，请给出快速计算A∩B的算法，算法可使用外存，但是要求占用内存不能超过4GB。 

答： 将集合A是的整数，根据n%10不同，分别装入10个文件中，依次命名为a0,a1……,a9。同理，将集合B分别装入10个文件中，依次命名为 b0,b1,……,b9。那么A和B编号不同的文件中，一定不会有相同的整数。只需分另求出a0与b0中共有的元素、a1与b1中共有的元素……利用bitmap，将bitmap清0，读入文件ai，依次处理每个数，即将bitmap的第（n/10）位置1。然后读入文件bi，依次处理每个数，即：若bitmap第（n/10）位为1，则这个数属于A∩B

 5、请给出从N个无序的整数中计算机最小的K个整数的算法，并给出时间复杂度，其中K<<N，要求时间复杂度尽可能的低，不要求K个整数排序。

 答：堆排序。将N个数中的前K个建立一个小顶堆。每读入一个新的整数，就把它插入到堆中，调整堆，但是每次调整都只调整前K个元素。从第K+1个位置开始的元素都忽略。时间为NlogK 

6、假设一个有8个1024字页面的逻辑地址空间,映射到一个有32帧的物理内存结构中，逻辑地址有多少位？ 

答：13

逻辑地址 = 逻辑页号 + 页内偏移 逻辑页面数为8，因此逻辑页号长度为3，页面的大小为1024，因此页面偏移的长度为10.如果求物理地址多少位，则是15
解：因为页面数为8=2^3，故需要3位二进制数表示。每页有1024个字节，1024=2^10，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=2^5）。
（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表。
（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。 

7、关于网络ISO各层协议的问题，把左右相对应。 应用层 网卡 表示层 路由IP 会话层 交换机 网络层   TCP/UDP 传输层    HTTP/DNS 数据链路层    ASCII 物理层      PRC，SQL

 答：连线题。
（1）网卡的作用就是把数据进行串并转换（串连数据是比特流形式的，存在与本计算机内部，而计算机与计算机之间是通过帧形式的数据来进行数据传输 的），MAC子层规定了如何在物理线路上传输的frame,LLC的作用是识别不同协议类型然后进行encapsulation(封包), 所以精确的说,网卡工作在数据链路层的MAC子层.

（2）路由IP属于网络层

（3）ISO的术语称之为中继（relay）系统

根据中继系统所在的层次，可以有以下五种中继系统：
1.物理层（即常说的第一层、层L1）中继系统，即转发器（repeater）。
2.数据链路层（即第二层，层L2），即网桥或桥接器（bridge）。
3.网络层（第三层，层L3）中继系统，即路由器（router）。
4.网桥和路由器的混合物桥路器（brouter）兼有网桥和路由器的功能。
5.在网络层以上的中继系统，即网关（gateway）.我们经常说到的以太网交换机实际是一个基于网桥技术的多端口第二层网络设备，即数据链路层

（4）TCP/UDP属于传输层

（5）HTTP/DNS属于应用层

（6） 表示层位于OSI分层结构的第六层，它的主要作用之一是为异种机通信提供一种公共语言，以便能进行互操作。这种类型的服务之所以需要，是因为不同的计算机 体系结构使用的数据表示法不同。例如，IBM主机使用EBCDIC编码，而大部分PC机使用的是ASCII码。在这种情况下，便需要会话层来完成这种转 换。ASCII属于表示层

（7）PRC，SQL属于哪一层呢？

 8、关于Bridge模式，Observer模式，Strategy模式，Mediator模式，以上哪种模式可以使得算法的使用者忽视算法的具体实现？ 答：Bride模式
（1）Bridge模式 的用意是"将抽象化(Abstraction)与实现化(Implementation)脱耦，使得二者可以独立地变化"。

（2）Observer模式定义对象间的一对多的依赖关系,当一个对象的状态发生改变时, 所有依赖于它的对象都得到通知并被自动更新。

（3）Strategy模式 定义一系列算法，把他们封装起来，并使他们可以互相替换。 将策略加以封装为一个物件，而不是将策略写死在某个类中，如此一来，策略可以独立于客户端，随时增加变化、增加或减少策略，即使是修改每个策略的内容，也不会对客户端程式造成影响。

（4）Mediator模式 用一个中介对象来封装一系列关于对象交互行为。

 9、数据库系统提供两种不同类型的语言，分别是自含式语言和嵌入式语言，来供数据库管理员及开发者管理，查询和更新。 

10、数据库理论中取出右侧关系中所有与左侧关系的任一元组都不匹配的元组，用空值填充所有来自左侧关系的属性，再把产生的元组加到自然连接的结果上，这种连接运算称为？ 

答：左外连接