2015年同等學力計算機綜合模擬3

2. 在一種計算機信息檢索的模型中，一個文件是由一些關鍵字組成的，而一個倒排文件是由含有某個關鍵字的所有文件組成的。一次查詢的輸入是一個關鍵字，輸出是這　　個關鍵字的倒排文件，一次查詢的開銷就是包含這個關鍵字的文件個數。多次查詢就是查詢一個關鍵字序列(其中可能有重復關鍵字)中的每個關鍵字，多次查 詢的開銷是 　　各次查詢的開銷之和，其中重復查詢同一個關鍵字的開銷之只計算一次。假設關鍵字和文件的個數都是有限的，試用集合論或圖論的術語來描述這個模型，并給出上述斜體字　　概念的形式化定義。

解答與評分標準：

集合論：

文件集合 D={d1,d2,…,dn}，關鍵字集合K={k1,k2,…,km}，倒排文件集合

K’={k1’,k2’,…,km’ }與關鍵字集合K 一一對應。D 包含于P(K)，K’包含于

P(D)，ki 屬于dj 當且僅當dj 屬于ki’(4 分)。查詢是從K 到P(D)的函數

Q：K→P(D)，查詢k 是求Q(k)(2 分)，查詢k 的開銷是|Q(k)|(2 分)。

多次查詢(s1,s2,…,st)就是求(Q(s1),Q(s2),…,Q(st))，多次查詢的開銷是對不

同的si 求|Q(si)|之和(2 分)。

圖論：

二部圖 G=，D 為文件集合，K 為關鍵字集合，E 為邊集合，(d,k)是E 中的邊當且僅當文件d 含有關鍵字k(4 分)。文件d 的內容就是d的相鄰頂點集合(鄰域)，倒排文　　件k 的內容就是k 的鄰域，查詢k 就是求k 的鄰域(2 分)，查詢k 的開銷就是k 的度數(2 分)。多次查詢就是求一組關鍵字的鄰域，多次查詢的開銷就是這組關鍵字頂　　點的度數之和，重復關鍵字只計算一次(2 分)。

更多關注：

同等學歷報考指南  同等學歷考試用書 同等學歷考試模擬試題

（責任編輯：中大編輯）

共2頁,當前第1頁  第一頁  前一頁  下一頁