百度筆試題及答案-百度筆試題及答

案

【各位讀友，本文僅供參考，望各位讀

者知悉，如若喜歡或者需要本文，可點(diǎn)

擊下載下載本文，謝謝！】祝大家工作順利】

百度java筆試題（含答案）

更多面試題，

百度面試筆試題解答答案

專家回答：

第一題

簡(jiǎn)評(píng)

百度的重要業(yè)務(wù)是搜索，搜索的基

本原理如下

1.編寫爬蟲程序到互聯(lián)網(wǎng)上抓取

網(wǎng)頁海量的網(wǎng)頁。

2.將抓取來的網(wǎng)頁通過抽取，以

一定的格式保存在能快速檢索的文獻(xiàn)系

統(tǒng)中。

3.把用戶輸入的字符串進(jìn)行拆提

成關(guān)鍵字去文獻(xiàn)系統(tǒng)中查詢并返回結(jié)

果。

由以上3點(diǎn)可見，字符串的分析,

抽取在搜索引擎中的地位是何等重要。

因此，百度的筆試面試題中，出現(xiàn)

這樣的題就變得理所當(dāng)然了。

以下是該題的java實(shí)現(xiàn)，代碼如

下：

程序代碼程序代碼

import*;

import*;

import*;

/***@authortzy*在下測(cè)試通過

*/

publicclassFileNameStat{

privateStringsrcPath;〃要記錄的文

獻(xiàn)途徑

privateMapstatMap;//用于記錄的

map

publicFileNameStat(StringsrcPath)

=srcPath;軟件開發(fā)網(wǎng)

statMap=newTreeMapO;

)

/*獲得要記錄的URL的文獻(xiàn)名*/

publicStringgetFileName(String

urlString)

(

URLurl=null;

StringfilePath=null;

StringfileName=null;

try

(

url=newURL(urlString);

filePath=();

intindex=O;

if((index=C7,,))!=-l)

(

fileName=(index+1);

else

(

fHeName='"';

catch(MalformedURLExceptione)

returnfileName;

}

/*記錄指定文獻(xiàn)名的個(gè)數(shù)*/

publicvoidstat(Stringfilename)

(

Integercount=null;

if((filename)!=null)

(

count=(Integer)(filename);

count=newInteger(()+1);

)

else

(

count=newInteger(l);

)

(filename,count);

)

/*記錄的主方法*/

publicvoidstart()throws

FileNotFoundExceptionJOException

(

BufferedReaderbfin=new

BufferedReader(newFileReader());

Stringtemp=null;

while((temp=())!=null)

(

stat(getFileName(temp));

)

)

/*輸出記錄結(jié)果*/

publicvoidresult()

(

Iteratorit=().iterator();

while(())

(

entry=()(());

((().equals("")?”空文獻(xiàn)名”:())+

“的個(gè)數(shù)是"+())；}

)

publicstaticvoidmain(Stringargs)

throwsException

FileNameStatfns=new

FileNameStat("");〃指定成待記錄文獻(xiàn)

0；

0；

)

)

第二題

簡(jiǎn)評(píng)：

這道題也與百度的業(yè)務(wù)有關(guān)，百度

現(xiàn)在除了搜索外，尚有貼吧，知道，博

客等重要產(chǎn)品。同時(shí)也在積極的探索

社區(qū)化，涉及前不久宣布進(jìn)軍電子商務(wù)

領(lǐng)域，搜索之外的這些產(chǎn)品，其重要功

能的實(shí)現(xiàn)重要是對(duì)數(shù)據(jù)庫的操作。因

此，想進(jìn)入百度，也需要對(duì)數(shù)據(jù)庫有一

定的結(jié)識(shí)。實(shí)現(xiàn)思緒及數(shù)據(jù)庫設(shè)計(jì)：

b該論壇重要有兩個(gè)實(shí)體對(duì)象，用戶和

帖子;對(duì)于帖子對(duì)象，有一個(gè)問題：回復(fù)

的帖子是否應(yīng)當(dāng)跟主題帖子存放在同一

個(gè)表里？

考慮到天天更新10萬帖子，說明

帖子數(shù)比較多，為了方便主題的呈現(xiàn)，

我一般都把主題貼和回帖分別放在不同

的表中，把主題貼和回帖分開可以提高

查詢效率（300萬的訪問量天天）。

2,按照1中的思緒，該論壇由兩

個(gè)對(duì)象（用戶和帖子）變成三個(gè)實(shí)體對(duì)象，

分別是用戶，主題帖子，回復(fù)帖子；

3,上述三個(gè)對(duì)象存在三個(gè)關(guān)系，

分別是：

用戶-主題帖，一個(gè)用戶可以發(fā)0

個(gè)或多個(gè)帖子，一個(gè)帖子相應(yīng)一個(gè)用戶

（一對(duì)多關(guān)系），

主題帖-回復(fù)帖：一個(gè)主題有。個(gè)

或多個(gè)回復(fù)帖子，一個(gè)回復(fù)帖子相應(yīng)一

個(gè)主題（一對(duì)多關(guān)系）；

用戶-回復(fù)貼：一個(gè)用戶可以回0

個(gè)或多個(gè)帖，一個(gè)帖子相應(yīng)一個(gè)用戶（一

對(duì)多關(guān)系）。

還存在對(duì)回復(fù)貼的回復(fù)，這個(gè)考慮

用fatherld來表達(dá)。

4,由于三個(gè)關(guān)系“用戶-主題帖,

主題帖-回復(fù)帖，用戶-回復(fù)貼”都是一

對(duì)多關(guān)系，根據(jù)表設(shè)計(jì)一般原則，可以

將這兩個(gè)關(guān)系獨(dú)立建立表，也可以不此

外建表而將一對(duì)多的關(guān)系體現(xiàn)在實(shí)體表

中;然而，表間的連接查詢是非常耗資源

的，所以應(yīng)盡量減少表間連接，那么對(duì)

三個(gè)關(guān)系不應(yīng)當(dāng)分別建表，而是把用戶

的id作為主題表和回帖表的外鍵，把主

題貼id作為回帖表的外鍵。

5,鑒于以上考慮，該論壇的三個(gè)

表如下所示

表名：t_user_info(用戶信息表)

字段名類型缺省值中文含

義約束備注

idInt用戶編號(hào)PRI

Auto_increment

NameVarchar(30)用戶名

EmailVarchar(50)

PhoneVarchar(30)

AddrVarchar(200)

其他字段略，根據(jù)需要添加表

名：main_content_info(主題帖信息表)

字屣名類型缺省值中文含

義約束備注

idInt貼編號(hào)PRI

Auto_increment

TitleVarchar(200)發(fā)帖標(biāo)題

ContentText發(fā)帖內(nèi)容

UserIDInt用戶編號(hào)

外鍵

其他字段略，根據(jù)需要添加

表名：sub_content_info(回復(fù)貼信

息表)

字段名類型缺省值中文含

義約束備注

idInt貼編號(hào)PRI

Auto_increment

TitleVarchar(200)發(fā)帖標(biāo)題

ContentText發(fā)帖內(nèi)容

UserIDInt用戶編號(hào)外

鍵

FatherlDInt父編號(hào)

MainlDInt主題帖編號(hào)

外鍵

其他字段略，根據(jù)需要添加

6,符合范式分析：

上述表中每個(gè)字段不可再分,一方

面滿足1NF;

然后數(shù)據(jù)庫表中的每個(gè)實(shí)例或行

都是可以被惟一地區(qū)分（id）,不存在部分

依賴，因此滿足2NF;

t_user_info（用戶信息表）和

main_content_info（主題帖信息表）不存

在任何傳遞依賴，至少屬于BCNF;

但是sub_content_info（回復(fù)貼信

息表）不滿足3NF,由于定在如下傳遞依

賴：id—>FatherID,FatherID—>MainID。

范式并不是越高越好，

sub_content_info表只滿足2NF卻更有效

率，也是當(dāng)今論壇較主流的設(shè)計(jì)。

第三題

簡(jiǎn)評(píng)：

如何對(duì)海量數(shù)據(jù)進(jìn)行快速檢索，這

是搜索引擎的必需考慮的問題。這又涉

及到數(shù)據(jù)結(jié)構(gòu)和算法。因此，要想進(jìn)

入百度，就必須熟悉一些基本的算法和

數(shù)據(jù)結(jié)構(gòu)。思緒及解決方案如下：

1：設(shè)計(jì)用TRIE樹實(shí)現(xiàn)關(guān)鍵詞到

其相應(yīng)id的快速詞典查找

TRIE樹的每一個(gè)節(jié)點(diǎn)為一個(gè)包含

256個(gè)元素的數(shù)組，同時(shí)指針指向其下一

級(jí)節(jié)點(diǎn)

節(jié)點(diǎn)定義如下：

structtrienode

(

intid;

structtrienode*child;

}TRIENODE;

假如TRIE樹的某個(gè)節(jié)點(diǎn)的指針為

NULL,說明從跟節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的途徑

構(gòu)成文獻(xiàn)B中的一個(gè)關(guān)鍵詞，

在其節(jié)點(diǎn)的id保存該關(guān)鍵詞的id;

假如指針不為NULL,則id相應(yīng)為0或

者一個(gè)無窮大的整數(shù)，標(biāo)志從根節(jié)點(diǎn)

到當(dāng)前節(jié)點(diǎn)的途徑不是一個(gè)完整

的關(guān)鍵詞。

將關(guān)鍵詞轉(zhuǎn)化為二進(jìn)制無符號(hào)

char型數(shù)組，即對(duì)于漢字等雙字節(jié)字符

視為兩個(gè)無符號(hào)char型整數(shù)，

每個(gè)元素的取值范圍在0到255

之間。

2：生成文獻(xiàn)b的TRIE樹

環(huán)節(jié)1：依次讀取文獻(xiàn)b的每一行,

對(duì)每一行執(zhí)行環(huán)節(jié)2到環(huán)節(jié)5

環(huán)節(jié)2：讀取關(guān)鍵詞id和關(guān)鍵詞,

令為key

環(huán)節(jié)3：依次讀取key的每一個(gè)字

符，對(duì)每一個(gè)字符，執(zhí)行環(huán)節(jié)4;

環(huán)節(jié)4：假如該字符相應(yīng)的指針為

NULL,則創(chuàng)建其兒子節(jié)點(diǎn)；

環(huán)節(jié)5：為當(dāng)前節(jié)點(diǎn)的相應(yīng)字符id

置為關(guān)鍵詞id

3：根據(jù)A文獻(xiàn)生成C文獻(xiàn)

環(huán)節(jié)1：依次讀取文獻(xiàn)A的每一

行，對(duì)每一行執(zhí)行環(huán)節(jié)2到環(huán)節(jié)5

環(huán)節(jié)2：分別獲取當(dāng)前行關(guān)鍵詞、

ip地址和時(shí)間

環(huán)節(jié)3：令關(guān)鍵詞key=clc2...cm,

對(duì)cl至Ucm每個(gè)字符，執(zhí)行環(huán)節(jié)4

環(huán)節(jié)4：獲取根節(jié)點(diǎn)的第cl個(gè)元

素指針，轉(zhuǎn)移到節(jié)點(diǎn)nodel,

根據(jù)nodel的第c2個(gè)元素指針，

轉(zhuǎn)移到node2...

根據(jù)nodem的第cm個(gè)元素，獲取

關(guān)鍵詞的id

環(huán)節(jié)5：往文獻(xiàn)c+寫入一行數(shù)據(jù)，

格式為關(guān)鍵詞的id、ip地址和時(shí)間

生成文獻(xiàn)B的TRIE樹過程時(shí)間復(fù)

雜度為O(n*m),其中n為文獻(xiàn)b行數(shù)，

m為文獻(xiàn)b關(guān)鍵詞的最大長(zhǎng)度。TRIE的

空間復(fù)雜度為O(n*m),n和m含義同上,

但由于實(shí)際應(yīng)用中關(guān)鍵詞之間也許會(huì)有

很多前綴相同現(xiàn)象，所以實(shí)際花費(fèi)空間

并不會(huì)很高。

生成C文獻(xiàn)的時(shí)間復(fù)雜度同樣為

O(n*m),n為文獻(xiàn)a行數(shù)，m為文獻(xiàn)a

關(guān)鍵詞的最大長(zhǎng)度，由于有了TRIE樹之

后，給定一個(gè)關(guān)鍵詞獲得其id的時(shí)間復(fù)

雜度為關(guān)鍵詞長(zhǎng)度。生成C文獻(xiàn)的過程

除了TRIE樹空間外基本不需要太多額

外的空間，空間復(fù)雜度為0(1),由于系

統(tǒng)有1G的可用內(nèi)存，TRIE占用的空間

在幾十兆到200M之間(與關(guān)鍵詞集合有

關(guān))，因此本方法完全可行。

更多面試題，百度網(wǎng)上筆試題及答

案

編程：1編程：用C語言實(shí)現(xiàn)一個(gè)

revert函數(shù)，它的功能是將輸入的字符

串在原串上倒序后返回。編程：2編

程：用C語言實(shí)現(xiàn)函數(shù)void*

memmove(void*dest,constvoid

*src,size_tn)omemmove函數(shù)的功能是

拷貝src所指的內(nèi)存內(nèi)容前n個(gè)字節(jié)

到dest所指的地址上。英文拼寫糾

錯(cuò)：3英文拼寫糾錯(cuò)：在用戶輸入英

文單詞時(shí)，經(jīng)常發(fā)生錯(cuò)誤，我們需要對(duì)

其進(jìn)行糾錯(cuò)。假設(shè)已經(jīng)有一個(gè)包含了對(duì)

的英文單詞的詞典，請(qǐng)你設(shè)計(jì)一個(gè)拼寫

糾錯(cuò)的程序。請(qǐng)描述你解決這個(gè)問題的

思緒；請(qǐng)給出重要的解決流程，算法，

以及算法的復(fù)雜度；請(qǐng)描述也許的改

善。尋找熱門查詢：4尋找熱門查詢

搜索引擎會(huì)通過日記文獻(xiàn)把用戶每次檢

索使用的所有檢索串都記錄下來，每個(gè)

查詢串的長(zhǎng)度為1-255字節(jié)。假設(shè)目前

有一千萬個(gè)記錄，這些查詢串的重復(fù)度

比較高，雖然總數(shù)是1千萬，但假如除

去反復(fù)后，不超過3百萬個(gè)。一個(gè)查

詢串的反復(fù)度越高，說明查詢它的用戶

越多，也就是越熱門。請(qǐng)你記錄最熱門

的10個(gè)查詢串，規(guī)定使用的內(nèi)存不能

超過1G。請(qǐng)描述你解決這個(gè)問題的思

緒；請(qǐng)給出重要的解決流程，算法，以

及算法的復(fù)雜度。集合合并：5集合

合并給定一個(gè)字符串的集合，格式如：

{aaabbbccc},{bbbddd},{eeefff}>

{ggg},{dddhhh}規(guī)定將其中交集不為

空的集合合并，規(guī)定合并完畢后的集合

之間無交集，例如上例應(yīng)輸出{aaabbb

cccdddhhh},{eeefff},{ggg)請(qǐng)描述

你解決這個(gè)問題的思緒；請(qǐng)給出重要的

解決流程，算法，以及算法的復(fù)雜度請(qǐng)

描述也許的改善。

///〃/////////〃//〃//〃/〃//〃/1題char

*revert(char*str){intn=strlen(str);int

i=0;charc;for(i=0;i{c=str;str=str;

str=c;}returnstr;}

////////////////////////////////〃/2題void*

memmove(void*dest,constvoid

*src,size_tn)

{assert((dest!=0)&&(src!=0));char*

temp=(char*)dest;char*ss=(char*)src;

inti=0;for(;i{*temp=*ss;}return

temp;}〃〃〃〃〃〃〃〃〃〃〃〃/〃〃〃〃〃〃〃〃〃〃/〃/

3題(1)思緒：字典以字母鍵樹組織，在

用戶輸入同時(shí)匹配(2)流程：每輸入一

個(gè)字母：沿字典樹向下一層，a)若可

以順利下行，則繼續(xù)至結(jié)束，給出結(jié)果;

b)若該處不能匹配，糾錯(cuò)解決，給出拼

寫建議，繼續(xù)至a)；

算法：1.在字典中查找單詞1.在字典

中查找單詞字典采用27叉樹組織，每

個(gè)節(jié)點(diǎn)相應(yīng)一個(gè)字母，查找就是一個(gè)字母

一個(gè)字母匹配.算法時(shí)間就是單詞的長(zhǎng)度

k.2.糾錯(cuò)算法2.糾錯(cuò)算法情況:當(dāng)輸

入的最后一個(gè)字母不能匹配時(shí)就提醒犯

錯(cuò)，簡(jiǎn)化犯錯(cuò)解決，動(dòng)態(tài)提醒也許解決

方法:⑶當(dāng)前字母前缺少了一個(gè)字母：搜

索樹上兩層到當(dāng)前的匹配作為建議；（b）

當(dāng)前字母拼寫錯(cuò)誤：當(dāng)前字母的鍵盤相

鄰作為提醒；根據(jù)分析字典特性和用戶

單詞已輸入部分選擇（a）,（b）解決復(fù)雜性

分析：影響算法的效率重要是字典的實(shí)

現(xiàn)與糾錯(cuò)解決（a）字典的實(shí)現(xiàn)已有成熟

的算法，改善不大，也不會(huì)成為瓶頸；（b）

糾錯(cuò)策略要簡(jiǎn)樸有效，如前述情況，是線

性復(fù)雜度；（3）改善（3）改善策略選擇

最是重要，可以采用記錄學(xué)習(xí)的方法改

善。/〃///〃////////〃/////////////////////〃〃〃/4題

（1）思緒（1）思緒：用哈希做思緒（2）一

方面逐次讀入查詢串，算哈希值，保存

在內(nèi)存數(shù)組中，同時(shí)記錄頻度選出前

十的頻度，取出相應(yīng)的日志串，簡(jiǎn)樸但

是了。哈希的設(shè)計(jì)是關(guān)鍵。

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII5題

思緒：先將集合按照大小排列后,優(yōu)先考

慮小的集合是否與大的集合有交思緒

集。有就合并，假如小集合與所有其他

集合都沒有交集，則獨(dú)立。獨(dú)立的集合

在下一輪的比較中不用考慮。這樣就可

以盡量減少字符串的比較次數(shù)。當(dāng)所有

集合都獨(dú)立的時(shí)候，就終止。

解決流程：解決流程：1.將集合按照

大小排序，組成集合合并待解決列表2.

選擇最小的集合，找出與之有交集的集

合，假如有，合并之；假如無，則與其

它集合是獨(dú)立集合，從待解決列表中刪

除。3.反復(fù)直到待解決列表為空算法:

算法：1。將集合按照大小從小到大排

序，組成待解決的集合列表。20取出待

解決集合列表中最小的集合，對(duì)于集合

的每個(gè)元素，依次在其他集合中搜索是

否有此元素存在：1＞若存在，則將此小

集合與大集合合并，并根據(jù)大小插入相

應(yīng)的位置。轉(zhuǎn)3o2＞若不存在，則在

該集合中取下一個(gè)元素。假如無下一個(gè)

元素，即所有元素都不存在于其他集

合。則表白此集合獨(dú)立，從待解決集合

列表中刪除。并加入結(jié)果集合列表。轉(zhuǎn)

3o3O假如待解決集合列表不為空，轉(zhuǎn)

2O假如待解決集合列表為空，成功退

出，則結(jié)果集合列表就是最終的輸出。

算法復(fù)雜度分析：算法復(fù)雜度分析：假

設(shè)集合的個(gè)數(shù)為n,最大的集合元素為

m排序的時(shí)間復(fù)雜度可以達(dá)成n*log(n)

然后對(duì)于元素在其他集合中查找，最壞

情況下為*m查找一個(gè)集合是否與其他

集合有交集的最壞情況是m*m*(n-1)

合并的時(shí)間復(fù)雜度不會(huì)超過查找集合

有交集的最壞情況。所以最終最壞時(shí)間

復(fù)雜度為O(m*m*n*n)需要說明

的是：此算法的平均時(shí)間復(fù)雜度會(huì)很

低，由于無論是查找還是合需要說明的

是并，都是處在最壞情況的概率很小，

并且排序后優(yōu)先用最小集合作為判斷是

否獨(dú)立的對(duì)象，優(yōu)先與最大的集合進(jìn)行

比較，這些都最大的回避了最壞情況。

(3)也許的改善：(3)也許的改善：也許

的改善一方面可以實(shí)現(xiàn)將每個(gè)集合里

面的字符串按照字典序進(jìn)行排列，這樣

就可以將查找以及合并的效率增高。此

外，也許采用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)也可以將

查找以及合并等操作的效率得到提高。

百度n月4日網(wǎng)上筆試題及答案(僅供

參考)

百度11月4日網(wǎng)上筆試題及答案

編程：

1用C語言實(shí)現(xiàn)一個(gè)revert函數(shù)，它的

功能是將輸入的字符串在原串上倒序后

返回。

2編程：

用C語言實(shí)現(xiàn)函數(shù)void*

memmove(void*dest,constvoid

*src,size_t

n)omemmove

函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容

前n個(gè)字節(jié)

到dest所指的地址上。

3英文拼寫糾錯(cuò)：

在用戶輸入英文單詞時(shí)，經(jīng)常發(fā)生錯(cuò)

誤，我們需要對(duì)其進(jìn)行糾錯(cuò)。假設(shè)已有

一個(gè)包

含了對(duì)的英文單詞的詞典，請(qǐng)你設(shè)計(jì)一

個(gè)拼寫糾錯(cuò)

的程序。

請(qǐng)描述你解決這個(gè)問題的思緒；

請(qǐng)給出重要的解決流程，算法，以及算

法的復(fù)雜度；

請(qǐng)描述也許的改善。

4尋找熱門查詢：

搜索引擎會(huì)通過日記文獻(xiàn)把用戶每次

檢索使用的所有檢索串都記錄下來，每

個(gè)查詢串

的長(zhǎng)度為1-255字節(jié)。假設(shè)目前有一千

萬個(gè)記錄，

這些查詢串的反復(fù)度比較高，雖然總數(shù)

是1千萬，但假如除去反復(fù)后，不超過3

百萬個(gè)

O一個(gè)查詢串的反復(fù)度越高，說明查詢

它的用戶越多，

也就是越熱門。請(qǐng)你記錄最熱門的10

個(gè)查詢串，規(guī)定使用的內(nèi)存不能超過

IGo

請(qǐng)描述你解決這個(gè)問題的思緒；

請(qǐng)給出重要的解決流程，算法，以及算

法的復(fù)雜度。

5集合合并：

給定一個(gè)字符串的集合，格式如：

{aaabbbccc},{bbbddd},{eeefff},

{ggg},{dddhhh)

規(guī)定將其中交集不為空的集合合并,規(guī)

定合并完畢后的集合之間無交集，例如

上例應(yīng)

輸出

{aaabbbcccdddhhh},{eeefff},{ggg}

請(qǐng)描述你解決這個(gè)問題的思緒；

請(qǐng)給出重要的解決流程，算法，以及算

法的復(fù)雜度

請(qǐng)描述也許的改善。

〃〃〃〃〃〃〃/〃〃〃〃〃〃〃〃/1

1題

char*revert(char*str)

(

intn=strlen(str);

inti=0;

charc;

for(i=0;i{

c=str;

str=str;

str=c;

)

returnstr;

)

〃〃〃//〃〃〃〃〃〃〃〃〃〃〃/〃〃

2題

void*memmove(void*dest,constvoid

*src,size_tn)

(

assert((dest!=O)&&(src!=O));

chartemp=(char*)dest;

char*ss=(char*)src;

inti=0;

for(;i{

*temp++=*ss++;

)

returntemp;

〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃/〃〃〃〃〃〃〃

3題

(D思緒：

字典以字母鍵樹組織，在用戶輸入同時(shí)

匹配

⑵

流程：

每輸入一個(gè)字母：

沿字典樹向下一層，

a)若可以順利下行，則繼續(xù)至結(jié)束，

給出結(jié)果；

b)若該處不能匹配，糾錯(cuò)解決，給出拼

寫建議，繼續(xù)至a)；

算法：

1.在字典中查找單詞

字典采用27叉樹組織，每個(gè)節(jié)點(diǎn)相應(yīng)一

個(gè)字母，查找就是一個(gè)字母

一個(gè)字母匹配.算法時(shí)間就是單詞的長(zhǎng)

度k.

2.糾錯(cuò)算法

情況:當(dāng)輸入的最后一個(gè)字母不能匹配

時(shí)就提醒犯錯(cuò)，簡(jiǎn)化犯錯(cuò)解決，動(dòng)態(tài)提醒

也許解決方法：

(a)當(dāng)前字母前缺少了一個(gè)字母：搜索

樹上兩層到當(dāng)前的匹配作為建議；

(b)當(dāng)前字母拼寫錯(cuò)誤：當(dāng)前字母的鍵

盤相鄰作為提醒；

根據(jù)分析字典特性和用戶單詞已輸入

部分選擇⑶,(b)解決

復(fù)雜性分析:影響算法的效率重要是字

典的實(shí)現(xiàn)與糾錯(cuò)解決

字典的實(shí)現(xiàn)已有成熟的算法，改善不

大，也不會(huì)成為瓶頸；

(b)糾錯(cuò)策略要簡(jiǎn)樸有效，如前述情況,

是線性復(fù)雜度；

⑶改善

策略立擇最是重要，可以采用

記錄學(xué)習(xí)的方法改善。

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

4題

⑴思緒：

用哈希做

(2)

一方面逐次讀入查詢串，算哈希值，保

存在內(nèi)存數(shù)組中，同時(shí)記錄頻度

選出前十的頻度，取出