數(shù)據(jù)挖掘與算法

1、部分習(xí)題與思考的答案與提示第二章習(xí)題與思考編程調(diào)用棧操作函數(shù)壓入1000000個(gè)隨機(jī)整數(shù)，再全部彈出來(lái)，打印花費(fèi)的總時(shí)間。提示：可以使用clock()函數(shù)獲取當(dāng)前時(shí)間，在壓入數(shù)據(jù)前調(diào)用一次clock()，壓入完數(shù)據(jù) 后再調(diào)用一次clock()，兩次時(shí)間差便是實(shí)際花費(fèi)的總時(shí)間。編程將100萬(wàn)個(gè)隨機(jī)整數(shù)插入到SortTble中，再調(diào)用快速排序函數(shù)排序，打印出排序 花費(fèi)的時(shí)間。提示：參考第1題的提示。編程將11000000的整數(shù)一次插入排序表里，調(diào)用二分查找函數(shù)將110000000這100 萬(wàn)個(gè)數(shù)依次查找一遍，打印出花費(fèi)的時(shí)間。提示：參考第1題的提示。編碼實(shí)現(xiàn)動(dòng)態(tài)環(huán)形隊(duì)列DeQue的彈出尾部節(jié)點(diǎn)函數(shù)

2、DeQue_PopTail()和插入頭部函數(shù) DeQue_InsertHead()函數(shù)。提示：參考 DeQue_PopHead()和 DeQue_InsertTail()的實(shí)現(xiàn)。第三章習(xí)題與思考在整塊內(nèi)存鏈表的實(shí)現(xiàn)中，考慮一下如果當(dāng)自由空間的節(jié)點(diǎn)用完時(shí)，再插入數(shù)據(jù)，申請(qǐng) 一塊大一倍的內(nèi)存，將原來(lái)內(nèi)存中數(shù)據(jù)直接拷貝過(guò)去，將多出的一半自由空間加入到自 由空間鏈表中，此時(shí)再插入數(shù)據(jù)，試問(wèn)這種實(shí)現(xiàn)方式存在什么問(wèn)題？提示：申請(qǐng)大一倍的內(nèi)存后，內(nèi)存的起始地址和原來(lái)內(nèi)存的起始地址不一樣，導(dǎo)致拷貝 完后，鏈表的鏈接指向的還是原來(lái)那塊內(nèi)存中的內(nèi)容。編碼實(shí)現(xiàn)一個(gè)整塊內(nèi)存中的鏈表插入算法，要求實(shí)現(xiàn)任意個(gè)數(shù)節(jié)點(diǎn)的插入

3、。提示：參考第1題。第四章習(xí)題與思考編碼將100萬(wàn)個(gè)隨機(jī)整數(shù)插入到哈希表中，再將這100萬(wàn)個(gè)整數(shù)全部查找一遍，看需要 花費(fèi)多長(zhǎng)時(shí)間？提示：可以使用rand()函數(shù)來(lái)生成隨機(jī)數(shù)，調(diào)用rand()函數(shù)前需要先調(diào)用srand()函數(shù)初 始化隨機(jī)數(shù)發(fā)生器。第五章習(xí)題思考：證明AVL樹(shù)中從根節(jié)點(diǎn)到任一樹(shù)梢節(jié)點(diǎn)的路徑上不存在連續(xù)三個(gè)樹(shù)梢節(jié)點(diǎn)。證明：使用反證法，假設(shè)存在三個(gè)連續(xù)的樹(shù)梢節(jié)點(diǎn)，那么這三個(gè)連續(xù)樹(shù)梢節(jié)點(diǎn)最上面的 那個(gè)節(jié)點(diǎn)的左右子樹(shù)高度差將大于等于2,與AVL樹(shù)的條件矛盾。證明紅黑樹(shù)中從根節(jié)點(diǎn)到任一樹(shù)梢節(jié)點(diǎn)的路徑上不存在連續(xù)三個(gè)樹(shù)梢節(jié)點(diǎn)。證明：使用反證法，假設(shè)存在連續(xù)三個(gè)樹(shù)梢節(jié)點(diǎn)，那么由紅黑樹(shù)的條件知

4、道從根節(jié)點(diǎn)到 任一樹(shù)梢節(jié)點(diǎn)路徑中的黑色節(jié)點(diǎn)數(shù)量相等，而從根節(jié)點(diǎn)到第2個(gè)樹(shù)梢節(jié)點(diǎn)的路徑必然要 經(jīng)過(guò)第1個(gè)樹(shù)梢節(jié)點(diǎn)，根節(jié)點(diǎn)到第3個(gè)樹(shù)梢節(jié)點(diǎn)的路徑必然經(jīng)過(guò)第2個(gè)樹(shù)梢節(jié)點(diǎn)，因此知 道三個(gè)樹(shù)梢節(jié)點(diǎn)的第2個(gè)和第3個(gè)節(jié)點(diǎn)必為紅色，但這又與紅黑樹(shù)中沒(méi)有連續(xù)兩個(gè)紅色節(jié) 點(diǎn)的條件矛盾，因此得證。使用非遞歸算法編碼實(shí)現(xiàn)二叉樹(shù)的前序遍歷函數(shù)。答案：見(jiàn)光盤(pán)源代碼編碼實(shí)現(xiàn)二叉樹(shù)的寬度遍歷函數(shù)。提示：參考樹(shù)的寬度遍歷算法使用紅黑樹(shù)替代哈希表去實(shí)現(xiàn)前面講過(guò)的Webserver Cache文件管理功能。比較一下哈希表、AVL樹(shù)、紅黑樹(shù)在各種操作效率方面的區(qū)別。估算一下對(duì)一個(gè)5000單詞的文件進(jìn)行分詞大約需要多少次詞典查詢(xún)？假設(shè)

5、平均每句有10個(gè)單詞，那么有500句，每句大約耗費(fèi)10X9/2=45次詞典查詢(xún)，因 此總共需要大約500X45 = 22500次詞典查詢(xún)。一個(gè)企業(yè)想建一個(gè)內(nèi)部搜索引擎，假設(shè)總共有十萬(wàn)個(gè)關(guān)鍵詞，十萬(wàn)個(gè)網(wǎng)頁(yè)文件，估算一 下搜索關(guān)鍵詞詞典大約要占多少內(nèi)存空間？答：假設(shè)平均每個(gè)網(wǎng)頁(yè)有500個(gè)不重復(fù)的單詞，那么在關(guān)鍵詞詞典中，每個(gè)網(wǎng)頁(yè)出現(xiàn)的 平均次數(shù)為500次；所有網(wǎng)頁(yè)在關(guān)鍵詞詞典中出現(xiàn)總次數(shù)為：500X10萬(wàn)次。每個(gè)關(guān)鍵詞所對(duì)應(yīng)的網(wǎng)頁(yè)文件平均個(gè)數(shù)為：500X10萬(wàn)/10萬(wàn)= 500個(gè)。如果給網(wǎng)頁(yè)文件名編號(hào)的話，編號(hào)需要消耗4字節(jié)，那么一個(gè)關(guān)鍵詞對(duì)應(yīng)的網(wǎng)頁(yè)文件列 表就需要消耗：4字節(jié)X500 = 200

6、0字節(jié)。10萬(wàn)個(gè)關(guān)鍵詞的詞典總共需要消耗：10萬(wàn)X2000字節(jié)= 200M字節(jié)。假設(shè)每個(gè)網(wǎng)頁(yè)文件名需要消耗32字節(jié)空間，那么網(wǎng)頁(yè)文件名和編號(hào)表消耗的空間為：10萬(wàn)X(32+4)=3.6M字節(jié)總共需要消耗203.6M字節(jié)的空間考慮一下如何在搜索引擎的關(guān)鍵詞詞典中搜索包含某個(gè)關(guān)鍵詞但不包含另外一個(gè)關(guān)鍵 詞的結(jié)果。答：先按書(shū)中5.6.3中介紹的方法求出同時(shí)包含兩個(gè)關(guān)鍵詞的交集，再將包含第1個(gè)關(guān) 鍵詞的集合中減去交集便得到了所需的結(jié)果。編碼實(shí)現(xiàn)一個(gè)簡(jiǎn)易的搜索引擎功能。要求對(duì)給定目錄下的網(wǎng)頁(yè)文件輸出關(guān)鍵詞詞典， 對(duì)給定的關(guān)鍵詞要求能輸出包含這個(gè)關(guān)鍵詞的所有文件。提示：搜索給定目錄下的網(wǎng)頁(yè)文件可以使用操作

7、系統(tǒng)提供的文件搜索函數(shù)。第六章習(xí)題與思考編碼使用哈希AVL樹(shù)去替代哈希表實(shí)現(xiàn)前面哈希表那章中的Webserver CACHE文件 管理。編碼調(diào)用哈希紅黑樹(shù)去實(shí)現(xiàn)一個(gè)英文詞典的管理功能。將哈希紅黑樹(shù)、哈希AVL樹(shù)和前面幾章講過(guò)的各種數(shù)據(jù)結(jié)構(gòu)作一個(gè)插入、刪除、查找、 有序性、時(shí)間效率、空間效率等方面的綜合比較。第七章習(xí)題與思考畫(huà)出寬度優(yōu)先搜索算法的流程圖。編程實(shí)現(xiàn)無(wú)環(huán)有向圖的分層算法。編程實(shí)現(xiàn)哈密頓圈算法。第八章習(xí)題與思考實(shí)現(xiàn)多個(gè)任務(wù)可以同時(shí)遍歷操作的多任務(wù)鏈表。將前面第4章中的Webserver CACHE文件管理改寫(xiě)成支持多任務(wù)的。編碼：創(chuàng)建多個(gè)任務(wù)，一些任務(wù)不停地向消息隊(duì)列中發(fā)送數(shù)據(jù)，一些任

8、務(wù)不停地從消息 隊(duì)列接收數(shù)據(jù)，然后還有一個(gè)任務(wù)不停地遍歷消息隊(duì)列里的數(shù)據(jù)。將本章的消息隊(duì)列代碼改寫(xiě)成當(dāng)隊(duì)列滿時(shí)，發(fā)送操作會(huì)阻塞在那里。提示：增加一個(gè)計(jì)數(shù)信號(hào)量，當(dāng)計(jì)數(shù)為0時(shí)表示消息隊(duì)列滿，在發(fā)送操作中要先判斷計(jì) 數(shù)是否為0,為0則需要等待；在接收操作中則需要將計(jì)數(shù)加1。編碼實(shí)現(xiàn)一個(gè)支持多任務(wù)操作的哈希AVL樹(shù)。第九章習(xí)題與思考：將932節(jié)中的Efree(void *p, size_t size)函數(shù)的第2個(gè)參數(shù)去掉的話，如何修改代碼來(lái) 實(shí)現(xiàn)它。提示：需要在內(nèi)存的頭部或尾部保存內(nèi)存的size信息。如何將本章講的內(nèi)存泄漏檢查和內(nèi)存越界檢查結(jié)合起來(lái)一起使用？提示：在內(nèi)存泄漏檢查的基礎(chǔ)上對(duì)分配的內(nèi)存尾部