阿里巴巴筆試記

阿里巴巴筆試記

考點（不分先后次序）：

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年創建�，F在已經標準化為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：<xs:choic>&<xs:sequence>；12.領域模型；13.Servlet生命周期。

還有綜合類的，就有點類似公務員考試的題目，還有一些關于計算機的題目，例如考點：

軟件測試的對象；2.用戶進程的跟蹤信息存在于什么目錄；3.how使普通用戶可執行超級用戶文件；4.向有限空間輸入超長字符串是什么攻擊，等等。大題就兩道：1.隱馬爾科夫模型（HMM）的3個基本問題；2.（寫函數的）。其實看到這些題目，我就蒙了，有些根本就沒見過。但是別怕，是否做出這些題目，并不是他們是否選擇你的標準（我覺得），都是摸一下底而已。我相信，大部分的人都是做不出來的，里面涉及的知識點，也不是全能從課本學來，靠的是積累。當然，這些也只是我個人的看法，因為我也沒過這個筆試，不過我覺得我還是有收獲的。這是我第一個參加的筆試，重在過程，所以我列下了這兩個方向的考點，可能還是有點參考價值吧！

隱馬爾科夫模型(hidden Markov model,縮寫為HMM)的提出最初是在語音處理領域。HMM是在Markov鏈的基礎上發展起來的一種統計模型。由于實際問題比Markov鏈模型所描述的更為復雜，因此在HMM中觀察到的事件與狀態并不是一一對應，而是與每個狀態的一組概率分布相聯系。它是一個雙重隨機過程，其中之一是Markov鏈，描述狀態的轉移；另一個描述每個狀態和觀察值之間的統計對應關系。這樣，HMM以概率模型描述觀察值序列，具有很好的數學結構，能夠比較完整地表達觀察值序列的特征。

【阿里巴巴筆試記】相關文章：

阿里巴巴筆試題08-10

阿里巴巴筆試題07-17

阿里巴巴筆試題201508-01

2015年阿里巴巴筆試題08-05

2013阿里巴巴筆試試題09-23

阿里巴巴公司DBA筆試題07-31

阿里巴巴2010年DBA筆試題07-26

阿里巴巴校招筆試題，試題分享08-10

2015年阿里巴巴校園招聘筆試題08-04