普加搜索引擎與數(shù)據(jù)挖掘部筆試題答案

1、一、基本問答題：1.冒泡和插入排序哪個快？快多少？一樣快（如果插入排序指的是直接插入排序的話）一樣快（如果插入排序指的是折半插入排序的話）一樣快（如果插入排序指的是二路插入排序的話）一樣快（如果插入排序指的是表插入排序的話）插入排序快（如果插入排序指的是希爾插入排序的話）理論上快O（n2） O（n1.3）。2.請說明冒泡排序和插入排序的序列應用何種數(shù)據(jù)結構儲存更好？分別對應著STL中哪個Tempelate?冒泡排序用數(shù)組比較好，對應著template中的vector；插入排序用鏈表比較好，對應著template中的deque。3.在只有命令行的條件下，你喜歡怎樣調(diào)試程序？在linux平臺下下用

2、gcc進行編譯，在windows平臺下用cl.exe進行編譯，用make工具根據(jù)目標文件上一次編譯的時間和所依賴的源文件的更新時間自動判斷應當編譯哪些源文件，提高程序調(diào)試的效率。 4.數(shù)據(jù)的邏輯存儲結構（如數(shù)組，隊列，樹等）對于軟件開發(fā)具有十分重要的影響，試對你所了解的各種存儲結構從運行速度、存儲效率和適用場合等方面進行簡要地分析。 運行速度存儲效率適用場合數(shù)組 快高比較適合進行查找操作，還有像類似于矩陣等的操作鏈表較快較高比較適合增刪改頻繁操作，動態(tài)的分配內(nèi)存隊列較快較高比較適合進行任務類等的調(diào)度棧一般較高比較適合遞歸類程序的改寫 二叉樹（樹）較快一般一切具有層次關系的問題都可用樹來描述圖一

3、般一般除了像最小生成樹、最短路徑、拓撲排序等經(jīng)典用途。還被用于像神經(jīng)網(wǎng)絡等人工智能領域等等。 5.什么是分布式數(shù)據(jù)庫？ 分布式數(shù)據(jù)庫系統(tǒng)是在集中式數(shù)據(jù)庫系統(tǒng)成熟技術的基礎上發(fā)展起來的，但不是簡單地把集中式數(shù)據(jù)庫分散地實現(xiàn)，它具有自己的性質(zhì)和特征。集中式數(shù)據(jù)庫系統(tǒng)的許多概念和技術，如數(shù)據(jù)獨立性、數(shù)據(jù)共享和減少冗余度、并發(fā)控制、完整性、安全性和恢復等在分布式數(shù)據(jù)庫系統(tǒng)中都有了不同的、更加豐富的內(nèi)容。 6.寫一段代碼判斷一個單向鏈表中是否有環(huán)。給出如下結構struct nodestruct*next;typedef stuct node Node；算法說明：初始化兩個指針，一個每次后移1個，一個后移

4、2個。當?shù)谝粋€指針追上第二個指針時候就說明有環(huán)！ int find_circle(Node* sll) list fast = sll; list slow = sll; if (NULL = fast) return -1; while (fast & fast-next) fast = fast-next-next; slow = slow-next; if (fast = slow) return 1; return 0; 7.談談HashMap和Hashtable的區(qū)別?（1）HashTable的方法是同步的，HashMap未經(jīng)同步，所以在多線程場合要手動同步HashMap這個區(qū)別就像

5、Vector和ArrayList一樣。（2）HashTable不允許null值(key和value都不可以),HashMap允許null值(key和value都可以)。（3）HashTable有一個contains(Object value)，功能和containsValue(Object value)功能一樣。（4）HashTable使用Enumeration，HashMap使用Iterator。（5）HashTable中hash數(shù)組默認大小是11，增加的方式是 old*2+1。HashMap中hash數(shù)組的默認大小是16，而且一定是2的指數(shù)。（6）哈希值的使用不同，HashTable直接使

6、用對象的hashCode。8.#include和#include“filename.h”有什么區(qū)別？用 #include 格式來引用標準庫的頭文件（編譯器將從標準庫目錄開始搜索）。 用 #include “filename.h” 格式來引用非標準庫的頭文件（編譯器將從用戶的工作目錄開始搜索）。 二、進階問答題：1.有以下兩個文件，請寫出一個你覺得比較標準的Makefile文件:CHello.cpp#includeusing namespace std;class CHellopublic:void printHello()coutHello Worldendl;Main.cpp #includ

7、eCHello.cppint main()CHello hello;hello.printHello();return 0;main: Main.o CHello.ogcc o testHello Main.o CHello.oCHello.o: CHello.cpp Main.o: Main.cppgcc c o Main.o Main.cppclean:rm rf CHello.o Main.o testHello2.Hadoop的一般性MapReduce計算有幾個步驟，哪個步驟最花費時間？（1）input（2）map tasks（3）reduce tasks（4）output步驟（2）最花費時間 個人看法3.簡述奇異值分解(Singular Value Decomposition)在文本聚類中的作用。消減了詞和文本之間語義關系的模糊度，從而更有利于文本聚類。 三、繪圖題現(xiàn)在起太陽熄滅，請繪制地球人口隨時間的變化圖，并說明為何這樣繪制？說明：一階段：當太陽熄滅之后，氣候、石油等資源變化的還不是很快，人后還在緩慢的增長。二階段：當不可回收的資源利用的差不多的時候，人們將會瀕臨崩潰，所以這時人口銳減。三階段：當人們已經(jīng)適應之后，慢慢的人后達到平衡狀態(tài)。四階段：這時人們利用自己的智慧再次的發(fā)展起來，但由于資源沒有以前那么的好，所以相比會發(fā)展的緩