- 相關推薦
阿里巴巴筆試記
考點（不分先后次序）：
C++：1.關于DOM的描述；2.網(wǎng)絡蜘蛛系統(tǒng)；3.UTF-8；4.數(shù)據(jù)庫檢索：查準率和查全率；5.索引壓縮；6.設計cralwer；7.Trie樹查詢；8.HTML&HTTP協(xié)議；9.信息檢索模型；10.分布式通信協(xié)議；11.分布式搜索引擎；12.雙向循環(huán)鏈表；13.快速排序；14.32位系統(tǒng)。
關于DOM的描述:
javascrip里面的dom（文檔對象模型）它是一種模型，將格式化文檔對象化處理。在xml和html 的處理中廣泛應用。 //dom是定義超文本結構的對象及方法，分層次的，有容器類的對象，也有基本元素對象，而這些對象，都包含有相應的屬性和對應的操作方法（接口）。
//一般而言，DOM結構準確地反映了HTML文檔所包含的內(nèi)容，也就是說，每個HTML標記表現(xiàn)為一個標記節(jié)點（tag node），每個文本項內(nèi)容表現(xiàn)為一個文本項節(jié)點（text node）。//是W3C組織推薦的處理可擴展置標語言的標準編程接口。
2. 網(wǎng)絡蜘蛛系統(tǒng)
網(wǎng)絡蜘蛛即Web Spider，是一個很形象的名字。把互聯(lián)網(wǎng)比喻成一個蜘蛛網(wǎng)，那么Spider就是在網(wǎng)上爬來爬去的蜘蛛。網(wǎng)絡蜘蛛是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁，從網(wǎng)站某一個頁面（通常是首頁）開始，讀取網(wǎng)頁的內(nèi)容，找到在網(wǎng)頁中的其它鏈接地址，然后通過這些鏈接地址尋找下一個網(wǎng)頁，這樣一直循環(huán)下去，直到把這個網(wǎng)站所有的網(wǎng)頁都抓取完為止。如果把整個互聯(lián)網(wǎng)當成一個網(wǎng)站，那么網(wǎng)絡蜘蛛就可以用這個原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都抓取下來。
對于搜索引擎來說，要抓取互聯(lián)網(wǎng)上所有的網(wǎng)頁幾乎是不可能的，從目前公布的數(shù)據(jù)來看，容量最大的搜索引擎也不過是抓取了整個網(wǎng)頁數(shù)量的百分之四十左右。這其中的原因一方面是抓取技術的瓶頸，無法遍歷所有的網(wǎng)頁，有許多網(wǎng)頁無法從其它網(wǎng)頁的鏈接中找到；另一個原因是存儲技術和處理技術的問題，
在抓取網(wǎng)頁的時候，網(wǎng)絡蜘蛛一般有兩種策略：廣度優(yōu)先和深度優(yōu)先（如下圖所示）。廣度優(yōu)先是指網(wǎng)絡蜘蛛會先抓取起始網(wǎng)頁中鏈接的所有網(wǎng)頁，然后再選擇其中的一個鏈接網(wǎng)頁，繼續(xù)抓取在此網(wǎng)頁中鏈接的所有網(wǎng)頁。這是最常用的方式，因為這個方法可以讓網(wǎng)絡蜘蛛并行處理，提高其抓取速度。深度優(yōu)先是指網(wǎng)絡蜘蛛會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路之后再轉入下一個起始頁，繼續(xù)跟蹤鏈接。這個方法有個優(yōu)點是網(wǎng)絡蜘蛛在設計的時候比較容易。兩種策略的區(qū)別，下圖的說明會更加明確。
在網(wǎng)絡蜘蛛機器人系統(tǒng)里面，真正起指揮作用的是人工管理系統(tǒng)制定的規(guī)則和檢索索引數(shù)據(jù)庫。它可以決定什么樣的網(wǎng)站抓的勤一點，或者干脆不抓.
3. UTF-8
使用UTF-8編碼唯一的好處是，國外的用戶如果使用Windows XP英文版，瀏覽UTF-8編碼的任何網(wǎng)頁，無論是中文、還是日文、韓文、阿拉伯文，都可以正常顯示，UTF-8是世界通用的語言編碼，UTF-8的推廣要歸功于Google的應用，以及Blog開發(fā)者。而如果用Windows XP英文版的IE6.0瀏覽gb2312語言編碼的網(wǎng)頁，則會提示是否安裝語言包。因此，可能會失去很多的國外瀏覽者。 使用gb2312編碼的好處是，因為程序產(chǎn)生的網(wǎng)頁文本使用ANSI編碼格式，會比UTF-8文本編碼節(jié)省一些體積，訪問速度會稍微快一點點，大約是30:38的比例，也就是30K的ANSI編碼，轉為UTF-8編碼是38K，當然，這個比例并不準確，是會隨Unicode字符集區(qū)域的不同而變化的。
UTF-8（8 位元 Universal Character Set/Unicode Transformation Format）是針對Unicode 的一種可變長度字符編碼。它可以用來表示 Unicode 標準中的任何字符，而且其編碼中的第一個字節(jié)仍與 ASCII 相容，使得原來處理 ASCII 字符的軟件無需或只作少部份修改后，便可繼續(xù)使用。因此，它逐漸成為電子郵件、網(wǎng)頁及其他儲存或傳送文字的應用中，優(yōu)先采用的編碼。 UTF-8 編碼提供了一種簡便而向后兼容的方法, 使得那種完全圍繞 ASCII 設計的操作系統(tǒng), 比如 Unix, 也可以使用 Unicode. UTF-8. UTF_8字符集
UTF-8是UNICODE的一種變長字符編碼，由Ken Thompson于1992年創(chuàng)建�，F(xiàn)在已經(jīng)標準化為RFC 3629。UTF-8用1到6個字節(jié)編碼UNICODE字符。如果UNICODE字符由2個字節(jié)表示，則編碼成UTF-8很可能需要3個字節(jié)，而如果UNICODE字符由4個字節(jié)表示，則編碼成UTF-8可能需要6個字節(jié)。用4個或6個字節(jié)去編碼一個UNICODE字符可能太多了，但很少會遇到那樣的UNICODE字符
4.數(shù)據(jù)庫檢索：查準率和查全率；
查全率與查準率是評價檢索效果的兩項重要指標。
查全率是指系統(tǒng)在進行某一檢索時，檢出的相關文獻量與系統(tǒng)文獻庫中相關文獻總量的比率，它反映該系統(tǒng)文獻庫中實有的相關文獻量在多大程度上被檢索出來。
查全率=[檢出相關文獻量/文獻庫內(nèi)相關文獻總量]×100%
查準率是指系統(tǒng)在進行某一檢索時，檢出的相關文獻量與檢出文獻總量的比率，它反映每次從該系統(tǒng)文獻庫中實際檢出的全部文獻中有多少是相關的。
查準率=[檢出相關文獻量/檢出文獻總量]×100%
通過對查準率和查全率的概念分析,得到了定性的結論:查全率依賴于查準率,查準率的提高有利于查全率的提高。通過對兩者間關系的數(shù)學推導,得到了查準率和查全率之間一般性的定量關系。
5.索引壓縮
建立索引是搜索引擎核心技術之一，建立索引的目的是能夠快速的響應用戶的查詢。搜索引擎最常用的索引數(shù)據(jù)結構是倒排文檔，倒排文檔的原理其實相當簡單。為什么要進行索引壓縮？對索引進行壓縮有很多好處：比如可以減少索引占用的磁盤空間和內(nèi)存；比如可以減少I/O讀寫量； 比如可以查詢響應速度加快；為了能夠增加壓縮效果，一般在進行壓縮前先改寫索引內(nèi)容，首先把倒排索引的數(shù)值按照大小排序，然后用差值而非實際值表示（d-gap)；這個是每個壓縮算法開展前要做的工作；目前的壓縮方法可以分為固定長度的和變長壓縮。
具體說是將索引編碼（落實到機器中應該是MD5哈希值）以一種壓縮的方式來表示，既利于節(jié)省存儲空間，又可以提高檢索速度。其實，我覺得這個東西最大的好處還是節(jié)約“緩存空間”，提高訪問速度。采用索引壓縮能夠帶來很多好處，所以實用的搜索引擎都會采用索引壓縮技術，但是對索引進行壓縮也會帶來問題，就是比不壓縮需要更多的計算量.
6.設計cralwer
搜索引擎的工作整體上可分為三個部分，在第一階段，Crawler開始“爬行”頁面，獲取最原始信息，Crawler是一段小程序，它通過初始地址，訪問頁面，分析出頁面內(nèi)部包括的鏈接，將鏈接傳送給Crawler控制模塊，Crawler控制模塊判斷哪些鏈接對應的頁面是下一步需要訪問的，哪一些是已經(jīng)被訪問過的，從而指示Crawler進行下一步“爬行”；另一方面，Crawler將獲取到的Web頁面?zhèn)魉偷巾撁鏀?shù)據(jù)存儲庫（Page Repository）中，臨時存儲起來。第二階段，索引器將庫中存儲的頁面進行解析，根據(jù)索引構建原則創(chuàng)建索引，并將索引存儲到索引庫中，另外，在一些基于頁面鏈接對頁面進行排名的搜索引擎系統(tǒng)中，鏈接分析與頁面排名的確定也在這個階段完成。第三階段，檢索引擎處理用戶的搜索請求，找出相關頁面文檔，并根據(jù)頁面排名高低，按順序將結果返回給用戶。三個階段并行協(xié)同工作，維持搜索引擎的正常運轉
爬行器技術 ：爬行器（Crawler，Spider）又叫“爬蟲”、“蜘蛛”，工作在搜索引擎的最前端，是搜索引擎中最關鍵的部分之一，它的性能好壞直接影響到搜索引擎對于頁面信息的采集與更新。 Internet上的網(wǎng)頁可以通過鏈接進行互訪，這使得Crawler可以從初始URL出發(fā)，沿著鏈接導向，遍歷Internet上整體網(wǎng)頁構成的連通圖。即使整體頁面構成的圖不是完全連通的，也可以將Internet上的頁面集合看成是一個個連通的子圖構成的，多個Crawler選擇合理的起點，順著頁面鏈接進行爬行，也能遍歷完整個圖�？紤]到網(wǎng)絡上Web頁面的數(shù)量非常龐大，設計一個性能良好的爬行器需要考慮以下4個問題[10]： 1．應下載哪些頁面？ 在多數(shù)情況下，Crawler并不下載Web上的所有頁面，即使是最復雜的搜索引擎，其索引庫中能檢索到的頁面也只占整個Web總頁面的一小部分。所以，Crawler優(yōu)先選擇最“重要”的頁面進行下載非常重要，以保證下載的部分更有價值。 2．如何更新頁面？一旦Crawler下載了大量的頁面，它會周期性的訪問原始頁面地址，看其是否是更新過的。Web上的頁面內(nèi)容可能變化非�？�，Crawler必須決定以不同的頻率訪問不同的頁面。
3．如何降低被爬行站點的負載？當Crawler獲取頁面時，需要消耗部分被訪問服務器的資源，同時也占用網(wǎng)絡帶寬，增加了網(wǎng)絡負擔。Cralwer應使用相應的策略降低這些消耗，否則相應站點將禁止Cralwer去訪問其頁面。 4．如何并行化爬行過程？ 由于要爬行的頁面數(shù)量非常大，一個Crawler在一定時間內(nèi)，通常不能勝任爬行所有頁面的能力，必須使用多個Crawler來完成這一工作。因此，Crawler之間的并行協(xié)同工作顯得非常重要。
針對Crawler工作任務的重要性及其工作量的巨大，許多搜索引擎采用了分布式Crawler技術，但是如何將巨大的爬行任務均衡地分配給各個Crawler是分布式WebCrawler的關鍵問題之一。目前許多Crawler系統(tǒng)都采用了集中式的任務分割策略
7.Trie樹查詢
基于三數(shù)組Trie索引樹原理的漢語詞典查詢機制,并用遞歸算法實現(xiàn)構詞狀態(tài)表的自動構建.
Trie樹是搜索樹的一種，來自英文單詞"Retrieval"的簡寫，可以建立有效的數(shù)據(jù)檢索組織結構，是中文匹配分詞算法中詞典的一種常見實現(xiàn)。它本質上是一個確定的有限狀態(tài)自動機（DFA），每個節(jié)點代表自動機的一個狀態(tài)。在詞典中這此狀態(tài)包括＂詞前綴＂，＂已成詞＂等。Trie樹就是字典樹，其核心思想就是空間換時間.字典樹有如下簡單的性質：
(1) 根節(jié)點不包含字符信息；
(3) 一棵m度的Trie或者為空，或者由m棵m度的Trie組成。
搜索字典項目的方法為：
(1) 從根結點開始一次搜索；(2) 取得要查找關鍵詞的第一個字母，并根據(jù)該字母選擇對應的子樹，轉到該子樹繼續(xù)進行檢索；
(3) 在相應的子樹上，取得要查找關鍵詞的第二個字母，并進一步選擇對應的子樹進行檢索。
4) 迭代過程……
(5) 在某個結點處，關鍵詞的所有字母已被取出，則讀取附在該結點上的信息，即完成查找。
雙數(shù)組Trie（Double-Array Trie）是trie樹的一個簡單而有效的實現(xiàn)，由兩個整數(shù)數(shù)組構成，一個是base[]，另一個是check[]。設數(shù)組下標為i ,如果base,check均為0,表示該位置為空。如果base為負值，表示該狀態(tài)為詞語。Check表示該狀態(tài)的前一狀態(tài)，t=base+a, check[t]=i 。
8.HTML&HTTP協(xié)議
HTML（Hyper Text Mark-up Language ）即超文本標記語言，是 WWW 的描述語言，由 Tim Berners-lee提出。設計 HTML 語言的目的是為了能把存放在一臺電腦中的文本或圖形與另一臺電腦中的文本或圖形方便地聯(lián)系在一起，形成有機的整體，人們不用考慮具體信息是在當前電腦上還是在網(wǎng)絡的其它電腦上。這樣，你只要使用鼠標在某一文檔中點取一個圖標，Internet就會馬上轉到與此圖標相關的內(nèi)容上去，而這些信息可能存放在網(wǎng)絡的另一臺電腦中。HTML文本是由 HTML命令組成的描述性文本，HTML 命令可以說明文字、 圖形、動畫、聲音、表格、鏈接等。 HTML的結構包括頭部 (Head)、主體 (Body) 兩大部分。頭部描述瀏覽器所需的信息，主體包含所要說明的具體內(nèi)容。
HTTP協(xié)議(Hypertext Transfer Protocol，超文本傳輸協(xié)議)是用于從WWW服務器傳輸超文本到本地瀏覽器的傳送協(xié)議。它可以使瀏覽器更加高效，使網(wǎng)絡傳輸減少。它不僅保證計算機正確快速地傳輸超文本文檔，還確定傳輸文檔中的哪一部分，以及哪部分內(nèi)容首先顯示(如文本先于圖形)等。超文本傳輸協(xié)議（HTTP）是一種為分布式，合作式，多媒體信息系統(tǒng)服務，面向應用層的協(xié)議。它是一種通用的，不分狀態(tài)（stateless)的協(xié)議，除了諸如名稱服務和分布對象管理系統(tǒng)之類的超文本用途外，還可以通過擴展它的請求方式，錯誤代碼和報頭[47]來完成許多任務。HTTP的一個特點是數(shù)據(jù)表示方式的典型性和可協(xié)商性允許獨立于傳輸數(shù)據(jù)而建立系統(tǒng)。
9.信息檢索模型；
信息檢索的數(shù)學模型 2.1 信息檢索系統(tǒng)的形式化表示 2.2 集合論檢索模型 2.2.1 布爾檢索模型 2.2.2 模糊集合模型 2.2.3 擴展布爾模型2.3 代數(shù)論檢索模型 2.3.1 向量空間模型 2.3.2 潛在語義索引模型 2.3.3 神經(jīng)網(wǎng)絡模型 2.4 概率論檢索模型 2.4.1 經(jīng)典概率模型 2.4.2 基于Bayesian網(wǎng)絡的檢索模型 2.5 其他信息檢索模型與數(shù)學理論 2.5.1 結構化檢索模型 2.5.2 瀏覽模型 2.5.3 其他新型數(shù)學理論提出了一種基于本體語義模型的信息檢索方法。該方法充分利用領域本體提供的概念之間的語義相關性，從語義模型擴展、概念相似度、相關度計算，并以用戶反饋等角度探討了基于語義模型的自動推理方法在信息檢索中的應用，文章介紹了系統(tǒng)實現(xiàn)框架. 包括布爾檢索模型、向量空間模型和概率檢索模型在內(nèi)的信息檢索數(shù)學模型.
10.分布式通信協(xié)議；
分布式虛擬環(huán)境（DVE）中高速運動實體的狀態(tài)更新數(shù)據(jù)量很大，對實時性要求高，現(xiàn)有的通訊協(xié)議不支持消息廢除，因而不能很好地支持新的狀態(tài)更新消息覆蓋過時消息。文章提出了一種可更新隊列的概念模型，在此基礎上提出了一種新的協(xié)議方案，它支持過時消息的丟棄，更好地滿足了實時交互的需要。分布式實時數(shù)據(jù)庫系統(tǒng)必須能夠處理具有時間限制的應用，而這些應用所涉及的某些數(shù)據(jù)又不在應用本地，所以不可避免地要與網(wǎng)絡上的其它結點進行通訊，傳送數(shù)據(jù)或消息．在分布式實時數(shù)據(jù)庫系統(tǒng)中，不僅要求數(shù)據(jù)值正確，而且具有時間限制，即在規(guī)定的時間內(nèi)，值正確的數(shù)據(jù)才是有效的．所以，實時通訊中，不僅要求數(shù)據(jù)或消息傳送正確，而且要盡可能保證或必須保證數(shù)據(jù)或消息在應用可允許的時間范圍內(nèi)完成傳送．
11.分布式搜索引擎
分布式搜索引擎是根據(jù)地域、主題、IP地址及其它的劃分標準將全網(wǎng)分成若干個自治區(qū)域，在每個自治區(qū)域內(nèi)設立一個檢索服務器，而每個檢索服務器由信息搜索機器人、索引搜索軟件數(shù)據(jù)庫和代理三部分組成。信息搜索機器人負責本自治區(qū)域內(nèi)的信息搜索，并建立索引信息存入索引數(shù)據(jù)庫。代理負責向用戶提供查詢接口，并與其它代理進行互換，實現(xiàn)檢索服務器之間的信息交換，且查詢可以重定向，即如果一個索引數(shù)據(jù)庫沒有滿足查詢要求，它可以將查詢請求發(fā)送到其它檢索服務器上。
它與集中式搜索引擎相比有以下優(yōu)點：各檢索服務器之間相互共享資源，站點只向本自治區(qū)域內(nèi)的信息搜索機器人提供信息，減輕了網(wǎng)絡及各站點的負載。各代理之間的相互協(xié)作及查詢重定向使得提供的服務更完善。 與Web本身的分布式特性相適應，具有良好的可擴充性，便于維護。索引信息劃分到各自的索引數(shù)據(jù)庫中，使得各索引數(shù)據(jù)庫相對較小，查詢的響應時間相對較短。部分檢索服務器發(fā)生故障時，其它部分能正常工作。Web服務器集群是一種典型的分布式處理系統(tǒng)。所謂Web集群就是采用高速網(wǎng)絡，將原來獨立的若干個服務器聯(lián)結起來，作為一個整體提供服務，把到達的請求分配到集群中的各個后臺服務器上，讓它們分攤負載及I/O，通過并行處理提高性能。此時涉及到請求分配器及負載平衡的技術問題。開發(fā)垂直門戶的分布式搜索引擎系統(tǒng)時，發(fā)現(xiàn)有四種不同應用的分布式搜索引擎： 1. 分布式元搜索: 2. 散列分布搜索引擎 3. Peer 2 peer 搜索引擎 4. 局部遍歷型搜索引擎.分布式元搜索:
14.32位系統(tǒng)
32位系統(tǒng)指機內(nèi) 數(shù)據(jù)長度，指令長度，地址長度是二進制32位。 64位系統(tǒng)指機內(nèi) 數(shù)據(jù)長度，指令長度，地址長度是二進制64位。 64位系統(tǒng)速度快。32位系統(tǒng)系統(tǒng)要尋高于32位的地址就要用到復雜一點的運算，用兩個32位單元組合成（好幾步才能到位）。64位系統(tǒng)直接尋址（一步到位）。
JAVA：1.Servlet中怎樣控制頁面在客戶端的緩存策略；2.執(zhí)行存儲過程；3.JSP；4.Thread.wait()可否設置超時；5.注釋XML內(nèi)容：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使普通用戶可執(zhí)行超級用戶文件；4.向有限空間輸入超長字符串是什么攻擊，等等。大題就兩道：1.隱馬爾科夫模型（HMM）的3個基本問題；2.（寫函數(shù)的）。其實看到這些題目，我就蒙了，有些根本就沒見過。但是別怕，是否做出這些題目，并不是他們是否選擇你的標準（我覺得），都是摸一下底而已。我相信，大部分的人都是做不出來的，里面涉及的知識點，也不是全能從課本學來，靠的是積累。當然，這些也只是我個人的看法，因為我也沒過這個筆試，不過我覺得我還是有收獲的。這是我第一個參加的筆試，重在過程，所以我列下了這兩個方向的考點，可能還是有點參考價值吧！
隱馬爾科夫模型(hidden Markov model,縮寫為HMM)的提出最初是在語音處理領域。HMM是在Markov鏈的基礎上發(fā)展起來的一種統(tǒng)計模型。由于實際問題比Markov鏈模型所描述的更為復雜，因此在HMM中觀察到的事件與狀態(tài)并不是一一對應，而是與每個狀態(tài)的一組概率分布相聯(lián)系。它是一個雙重隨機過程，其中之一是Markov鏈，描述狀態(tài)的轉移；另一個描述每個狀態(tài)和觀察值之間的統(tǒng)計對應關系。這樣，HMM以概率模型描述觀察值序列，具有很好的數(shù)學結構，能夠比較完整地表達觀察值序列的特征。
【阿里巴巴筆試記】相關文章：
阿里巴巴筆試題08-10
阿里巴巴筆試題07-17
阿里巴巴筆試題201508-01
2015年阿里巴巴筆試題08-05
2013阿里巴巴筆試試題09-23
阿里巴巴公司DBA筆試題07-31
阿里巴巴2010年DBA筆試題07-26
阿里巴巴校招筆試題，試題分享08-10
2015年阿里巴巴校園招聘筆試題08-04