1. 比較下列集合的基數(shù)大小并給出證明:A×A,P(A),2→A,A→2.
解答與評(píng)分標(biāo)準(zhǔn):
|A×A| = |2→A| = |A|2(2 分),
|P(A)| = |A→2| = 2|A|(2 分)。
分情況討論:
(1) A 為空集:注意A→2={空關(guān)系},
|A×A| = |2→A| = 0 < |P(A)| = |A→2| = 1。(1 分)
(2) A 為有限集且|A|=1:
|A×A| = |2→A| = |A|2 = 1 < 2 = 2|A| = |P(A)| = |A→2| 。(1 分)
(3) A 為有限集且|A|=2:
|A×A| = |2→A| = |A|2 = 4 = 2|A| = |P(A)| = |A→2| 。(1 分)
(4) A 為有限集且|A|=3:
|A×A| = |2→A| = |A|2 =9 > 8 = 2|A| = |P(A)| = | A→2| 。(1 分)
(5) A 為有限集且|A|>4:
|A×A| = |2→A| = |A|2 < 2|A| = |P(A)| = |A→2| 。(1 分)
(6) A 為無(wú)限集:
|A×A| = |2→A| = |A|2 = |A| < 2|A|(康托定理)= |P(A)| = | A→2| (1 分)。
注(1)(2)(5)(6)結(jié)果相同,可合并。
2. 在一種計(jì)算機(jī)信息檢索的模型中,一個(gè)文件是由一些關(guān)鍵字組成的,而一個(gè)倒排文件是由含有某個(gè)關(guān)鍵字的所有文件組成的。一次查詢的輸入是一個(gè)關(guān)鍵字,輸出是這 個(gè)關(guān)鍵字的倒排文件,一次查詢的開(kāi)銷就是包含這個(gè)關(guān)鍵字的文件個(gè)數(shù)。多次查詢就是查詢一個(gè)關(guān)鍵字序列(其中可能有重復(fù)關(guān)鍵字)中的每個(gè)關(guān)鍵字,多次查 詢的開(kāi)銷是 各次查詢的開(kāi)銷之和,其中重復(fù)查詢同一個(gè)關(guān)鍵字的開(kāi)銷之只計(jì)算一次。假設(shè)關(guān)鍵字和文件的個(gè)數(shù)都是有限的,試用集合論或圖論的術(shù)語(yǔ)來(lái)描述這個(gè)模型,并給出上述斜體字 概念的形式化定義。
解答與評(píng)分標(biāo)準(zhǔn):
集合論:
文件集合 D={d1,d2,…,dn},關(guān)鍵字集合K={k1,k2,…,km},倒排文件集合
K’={k1’,k2’,…,km’ }與關(guān)鍵字集合K 一一對(duì)應(yīng)。D 包含于P(K),K’包含于
P(D),ki 屬于dj 當(dāng)且僅當(dāng)dj 屬于ki’(4 分)。查詢是從K 到P(D)的函數(shù)
Q:K→P(D),查詢k 是求Q(k)(2 分),查詢k 的開(kāi)銷是|Q(k)|(2 分)。
多次查詢(s1,s2,…,st)就是求(Q(s1),Q(s2),…,Q(st)),多次查詢的開(kāi)銷是對(duì)不
同的si 求|Q(si)|之和(2 分)。
圖論:
二部圖 G=,D 為文件集合,K 為關(guān)鍵字集合,E 為邊集合,(d,k)是E 中的邊當(dāng)且僅當(dāng)文件d 含有關(guān)鍵字k(4 分)。文件d 的內(nèi)容就是d的相鄰頂點(diǎn)集合(鄰域),倒排文 件k 的內(nèi)容就是k 的鄰域,查詢k 就是求k 的鄰域(2 分),查詢k 的開(kāi)銷就是k 的度數(shù)(2 分)。多次查詢就是求一組關(guān)鍵字的鄰域,多次查詢的開(kāi)銷就是這組關(guān)鍵字頂 點(diǎn)的度數(shù)之和,重復(fù)關(guān)鍵字只計(jì)算一次(2 分)。
編輯推薦:
2015年同等學(xué)力計(jì)算機(jī)綜合模擬試題
2015年同等學(xué)力申碩英語(yǔ)寫作常用句子匯總
(責(zé)任編輯:lqh)