阿里巴巴笔试记

阿里巴巴笔试记

考点（不分先后次序）：

C++：1.关于DOM的描述；2.网络蜘蛛系统；3.UTF-8；4.数据库检索：查准率和查全率；5.索引压缩；6.设计cralwer；7.Trie树查询；8.HTML&HTTP协议；9.信息检索模型；10.分布式通信协议；11.分布式搜索引擎；12.双向循环链表；13.快速排序；14.32位系统。

关于DOM的描述:

javascrip里面的dom（文档对象模型）它是一种模型，将格式化文档对象化处理。在xml和html 的处理中广泛应用。//dom是定义超文本结构的对象及方法，分层次的，有容器类的对象，也有基本元素对象，而这些对象，都包含有相应的属性和对应的操作方法（接口）。

//一般而言，DOM结构准确地反映了HTML文档所包含的内容，也就是说，每个HTML标记表现为一个标记节点（tag node），每个文本项内容表现为一个文本项节点（text node）。//是W3C组织推荐的处理可扩展置标语言的标准编程接口。

2. 网络蜘蛛系统

网络蜘蛛即Web Spider，是一个很形象的名字。把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。

对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的问题，

在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先（如下图所示）。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比较容易。两种策略的区别，下图的说明会更加明确。

在网络蜘蛛机器人系统里面，真正起指挥作用的是人工管理系统制定的规则和检索索引数据库。它可以决定什么样的网站抓的勤一点，或者干脆不抓.

3. UTF-8

使用UTF-8编码唯一的好处是，国外的用户如果使用Windows XP英文版，浏览UTF-8编码的任何网页，无论是中文、还是日文、韩文、阿拉伯文，都可以正常显示，UTF-8是世界通用的语言编码，UTF-8的推广要归功于Google的应用，以及Blog开发者。而如果用Windows XP英文版的IE6.0浏览gb2312语言编码的网页，则会提示是否安装语言包。因此，可能会失去很多的国外浏览者。 使用gb2312编码的好处是，因为程序产生的网页文本使用ANSI编码格式，会比UTF-8文本编码节省一些体积，访问速度会稍微快一点点，大约是30:38的比例，也就是30K的ANSI编码，转为UTF-8编码是38K，当然，这个比例并不准确，是会随Unicode字符集区域的不同而变化的。

UTF-8（8 位元 Universal Character Set/Unicode Transformation Format）是针对Unicode 的一种可变长度字符编码。它可以用来表示 Unicode 标准中的任何字符，而且其编码中的第一个字节仍与 ASCII 相容，使得原来处理 ASCII 字符的软件无需或只作少部份修改后，便可继续使用。因此，它逐渐成为电子邮件、网页及其他储存或传送文字的应用中，优先采用的编码。UTF-8 编码提供了一种简便而向后兼容的方法, 使得那种完全围绕 ASCII 设计的操作系统, 比如 Unix, 也可以使用 Unicode. UTF-8. UTF_8字符集

　　UTF-8是UNICODE的一种变长字符编码，由Ken Thompson于1992年创建。现在已经标准化为RFC 3629。UTF-8用1到6个字节编码UNICODE字符。如果UNICODE字符由2个字节表示，则编码成UTF-8很可能需要3个字节，而如果UNICODE字符由4个字节表示，则编码成UTF-8可能需要6个字节。用4个或6个字节去编码一个UNICODE字符可能太多了，但很少会遇到那样的UNICODE字符

4.数据库检索：查准率和查全率；

查全率与查准率是评价检索效果的两项重要指标。

查全率是指系统在进行某一检索时，检出的相关文献量与系统文献库中相关文献总量的比率，它反映该系统文献库中实有的相关文献量在多大程度上被检索出来。

查全率=[检出相关文献量/文献库内相关文献总量]×100%

查准率是指系统在进行某一检索时，检出的相关文献量与检出文献总量的比率，它反映每次从该系统文献库中实际检出的全部文献中有多少是相关的。

查准率=[检出相关文献量/检出文献总量]×100%

通过对查准率和查全率的概念分析,得到了定性的结论:查全率依赖于查准率,查准率的提高有利于查全率的提高。通过对两者间关系的数学推导,得到了查准率和查全率之间一般性的定量关系。

5.索引压缩

建立索引是搜索引擎核心技术之一，建立索引的目的是能够快速的响应用户的查询。搜索引擎最常用的索引数据结构是倒排文档，倒排文档的原理其实相当简单。为什么要进行索引压缩？对索引进行压缩有很多好处：比如可以减少索引占用的磁盘空间和内存；比如可以减少I/O读写量； 比如可以查询响应速度加快；为了能够增加压缩效果，一般在进行压缩前先改写索引内容，首先把倒排索引的数值按照大小排序，然后用差值而非实际值表示（d-gap)；这个是每个压缩算法开展前要做的工作；目前的压缩方法可以分为固定长度的和变长压缩。

具体说是将索引编码（落实到机器中应该是MD5哈希值）以一种压缩的方式来表示，既利于节省存储空间，又可以提高检索速度。其实，我觉得这个东西最大的好处还是节约“缓存空间”，提高访问速度。采用索引压缩能够带来很多好处，所以实用的搜索引擎都会采用索引压缩技术，但是对索引进行压缩也会带来问题，就是比不压缩需要更多的计算量.

6.设计cralwer

搜索引擎的工作整体上可分为三个部分，在第一阶段，Crawler开始“爬行”页面，获取最原始信息，Crawler是一段小程序，它通过初始地址，访问页面，分析出页面内部包括的链接，将链接传送给Crawler控制模块，Crawler控制模块判断哪些链接对应的页面是下一步需要访问的，哪一些是已经被访问过的，从而指示Crawler进行下一步“爬行”；另一方面，Crawler将获取到的Web页面传送到页面数据存储库（Page Repository）中，临时存储起来。第二阶段，索引器将库中存储的`页面进行解析，根据索引构建原则创建索引，并将索引存储到索引库中，另外，在一些基于页面链接对页面进行排名的搜索引擎系统中，链接分析与页面排名的确定也在这个阶段完成。第三阶段，检索引擎处理用户的搜索请求，找出相关页面文档，并根据页面排名高低，按顺序将结果返回给用户。三个阶段并行协同工作，维持搜索引擎的正常运转

爬行器技术 ：爬行器（Crawler，Spider）又叫“爬虫”、“蜘蛛”，工作在搜索引擎的最前端，是搜索引擎中最关键的部分之一，它的性能好坏直接影响到搜索引擎对于页面信息的采集与更新。 Internet上的网页可以通过链接进行互访，这使得Crawler可以从初始URL出发，沿着链接导向，遍历Internet上整体网页构成的连通图。即使整体页面构成的图不是完全连通的，也可以将Internet上的页面集合看成是一个个连通的子图构成的，多个Crawler选择合理的起点，顺着页面链接进行爬行，也能遍历完整个图。考虑到网络上Web页面的数量非常庞大，设计一个性能良好的爬行器需要考虑以下4个问题[10]： 1．应下载哪些页面？ 在多数情况下，Crawler并不下载Web上的所有页面，即使是最复杂的搜索引擎，其索引库中能检索到的页面也只占整个Web总页面的一小部分。所以，Crawler优先选择最“重要”的页面进行下载非常重要，以保证下载的部分更有价值。 2．如何更新页面？一旦Crawler下载了大量的页面，它会周期性的访问原始页面地址，看其是否是更新过的。Web上的页面内容可能变化非常快，Crawler必须决定以不同的频率访问不同的页面。

3．如何降低被爬行站点的负载？当Crawler获取页面时，需要消耗部分被访问服务器的资源，同时也占用网络带宽，增加了网络负担。Cralwer应使用相应的策略降低这些消耗，否则相应站点将禁止Cralwer去访问其页面。 4．如何并行化爬行过程？ 由于要爬行的页面数量非常大，一个Crawler在一定时间内，通常不能胜任爬行所有页面的能力，必须使用多个Crawler来完成这一工作。因此，Crawler之间的并行协同工作显得非常重要。

针对Crawler工作任务的重要性及其工作量的巨大，许多搜索引擎采用了分布式Crawler技术，但是如何将巨大的爬行任务均衡地分配给各个Crawler是分布式WebCrawler的关键问题之一。目前许多Crawler系统都采用了集中式的任务分割策略

7.Trie树查询

基于三数组Trie索引树原理的汉语词典查询机制,并用递归算法实现构词状态表的自动构建.

Trie树是搜索树的一种，来自英文单词"Retrieval"的简写，可以建立有效的数据检索组织结构，是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机（DFA），每个节点代表自动机的一个状态。在词典中这此状态包括＂词前缀＂，＂已成词＂等。Trie树就是字典树，其核心思想就是空间换时间.字典树有如下简单的性质：

(1) 根节点不包含字符信息；

(3) 一棵m度的Trie或者为空，或者由m棵m度的Trie组成。

搜索字典项目的方法为：

(1) 从根结点开始一次搜索；(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树，转到该子树继续进行检索；

(3) 在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。

4) 迭代过程……

(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

双数组Trie（Double-Array Trie）是trie树的一个简单而有效的实现，由两个整数数组构成，一个是base[]，另一个是check[]。设数组下标为i ,如果base,check均为0,表示该位置为空。如果base为负值，表示该状态为词语。Check表示该状态的前一状态，t=base+a, check[t]=i 。

8.HTML&HTTP协议

HTML（Hyper Text Mark-up Language ）即超文本标记语言，是 WWW 的描述语言，由 Tim Berners-lee提出。设计 HTML 语言的目的是为了能把存放在一台电脑中的文本或图形与另一台电脑中的文本或图形方便地联系在一起，形成有机的整体，人们不用考虑具体信息是在当前电脑上还是在网络的其它电脑上。这样，你只要使用鼠标在某一文档中点取一个图标，Internet就会马上转到与此图标相关的内容上去，而这些信息可能存放在网络的另一台电脑中。HTML文本是由 HTML命令组成的描述性文本，HTML 命令可以说明文字、 图形、动画、声音、表格、链接等。 HTML的结构包括头部 (Head)、主体 (Body) 两大部分。头部描述浏览器所需的信息，主体包含所要说明的具体内容。

HTTP协议(Hypertext　Transfer　Protocol，超文本传输协议)是用于从WWW服务器传输超文本到本地浏览器的传送协议。它可以使浏览器更加高效，使网络传输减少。它不仅保证计算机正确快速地传输超文本文档，还确定传输文档中的哪一部分，以及哪部分内容首先显示(如文本先于图形)等。超文本传输协议（HTTP）是一种为分布式，合作式，多媒体信息系统服务，面向应用层的协议。它是一种通用的，不分状态（stateless)的协议，除了诸如名称服务和分布对象管理系统之类的超文本用途外，还可以通过扩展它的请求方式，错误代码和报头[47]来完成许多任务。HTTP的一个特点是数据表示方式的典型性和可协商性允许独立于传输数据而建立系统。

9.信息检索模型；

信息检索的数学模型　2.1 信息检索系统的形式化表示　2.2 集合论检索模型　2.2.1 布尔检索模型　2.2.2 模糊集合模型　2.2.3 扩展布尔模型2.3 代数论检索模型　2.3.1 向量空间模型　2.3.2 潜在语义索引模型　2.3.3 神经网络模型　2.4 概率论检索模型　2.4.1 经典概率模型　2.4.2 基于Bayesian网络的检索模型　2.5 其他信息检索模型与数学理论　2.5.1 结构化检索模型　2.5.2 浏览模型　2.5.3 其他新型数学理论提出了一种基于本体语义模型的信息检索方法。该方法充分利用领域本体提供的概念之间的语义相关性，从语义模型扩展、概念相似度、相关度计算，并以用户反馈等角度探讨了基于语义模型的自动推理方法在信息检索中的应用，文章介绍了系统实现框架. 包括布尔检索模型、向量空间模型和概率检索模型在内的信息检索数学模型.

10.分布式通信协议；

分布式虚拟环境（DVE）中高速运动实体的状态更新数据量很大，对实时性要求高，现有的通讯协议不支持消息废除，因而不能很好地支持新的状态更新消息覆盖过时消息。文章提出了一种可更新队列的概念模型，在此基础上提出了一种新的协议方案，它支持过时消息的丢弃，更好地满足了实时交互的需要。分布式实时数据库系统必须能够处理具有时间限制的应用，而这些应用所涉及的某些数据又不在应用本地，所以不可避免地要与网络上的其它结点进行通讯，传送数据或消息．在分布式实时数据库系统中，不仅要求数据值正确，而且具有时间限制，即在规定的时间内，值正确的数据才是有效的．所以，实时通讯中，不仅要求数据或消息传送正确，而且要尽可能保证或必须保证数据或消息在应用可允许的时间范围内完成传送．

11.分布式搜索引擎

分布式搜索引擎是根据地域、主题、IP地址及其它的划分标准将全网分成若干个自治区域，在每个自治区域内设立一个检索服务器，而每个检索服务器由信息搜索机器人、索引搜索软件数据库和代理三部分组成。信息搜索机器人负责本自治区域内的信息搜索，并建立索引信息存入索引数据库。代理负责向用户提供查询接口，并与其它代理进行互换，实现检索服务器之间的信息交换，且查询可以重定向，即如果一个索引数据库没有满足查询要求，它可以将查询请求发送到其它检索服务器上。

它与集中式搜索引擎相比有以下优点：各检索服务器之间相互共享资源，站点只向本自治区域内的信息搜索机器人提供信息，减轻了网络及各站点的负载。各代理之间的相互协作及查询重定向使得提供的服务更完善。 与Web本身的分布式特性相适应，具有良好的可扩充性，便于维护。索引信息划分到各自的索引数据库中，使得各索引数据库相对较小，查询的响应时间相对较短。部分检索服务器发生故障时，其它部分能正常工作。Web服务器集群是一种典型的分布式处理系统。所谓Web集群就是采用高速网络，将原来独立的若干个服务器联结起来，作为一个整体提供服务，把到达的请求分配到集群中的各个后台服务器上，让它们分摊负载及I/O，通过并行处理提高性能。此时涉及到请求分配器及负载平衡的技术问题。开发垂直门户的分布式搜索引擎系统时，发现有四种不同应用的分布式搜索引擎： 1. 分布式元搜索: 2. 散列分布搜索引擎 3. Peer 2 peer 搜索引擎 4. 局部遍历型搜索引擎.分布式元搜索:

14.32位系统

32位系统指机内 数据长度，指令长度，地址长度是二进制32位。 64位系统指机内 数据长度，指令长度，地址长度是二进制64位。 64位系统速度快。32位系统系统要寻高于32位的地址就要用到复杂一点的运算，用两个32位单元组合成（好几步才能到位）。64位系统直接寻址（一步到位）。

JAVA：1.Servlet中怎样控制页面在客户端的缓存策略；2.执行存储过程；3.JSP；4.Thread.wait()可否设置超时；5.注释XML内容：CDATA；6.IOC；7.Open-Closed原则含义；8.JUnit TestCase基类中的代码；9.javax.servle.http.HttpServlet；10.JDBC连接池&功能；11.XML Schema：&；12.领域模型；13.Servlet生命周期。

还有综合类的，就有点类似公务员考试的题目，还有一些关于计算机的题目，例如考点：

软件测试的对象；2.用户进程的跟踪信息存在于什么目录；3.how使普通用户可执行超级用户文件；4.向有限空间输入超长字符串是什么攻击，等等。大题就两道：1.隐马尔科夫模型（HMM）的3个基本问题；2.（写函数的）。其实看到这些题目，我就蒙了，有些根本就没见过。但是别怕，是否做出这些题目，并不是他们是否选择你的标准（我觉得），都是摸一下底而已。我相信，大部分的人都是做不出来的，里面涉及的知识点，也不是全能从课本学来，靠的是积累。当然，这些也只是我个人的看法，因为我也没过这个笔试，不过我觉得我还是有收获的。这是我第一个参加的笔试，重在过程，所以我列下了这两个方向的考点，可能还是有点参考价值吧！

隐马尔科夫模型(hidden Markov model,缩写为HMM)的提出最初是在语音处理领域。HMM是在Markov链的基础上发展起来的一种统计模型。由于实际问题比Markov链模型所描述的更为复杂，因此在HMM中观察到的事件与状态并不是一一对应，而是与每个状态的一组概率分布相联系。它是一个双重随机过程，其中之一是Markov链，描述状态的转移；另一个描述每个状态和观察值之间的统计对应关系。这样，HMM以概率模型描述观察值序列，具有很好的数学结构，能够比较完整地表达观察值序列的特征。