信息科學(xué)技術(shù)學(xué)院2002-2003學(xué)年第二學(xué)期生集合論與圖論期末考試試卷

1、裝- PAGE 3其他細(xì)節(jié)（2分） 5種性質(zhì)（2分）。非自反：不屬于 A。非稱(chēng)：,A但7不等于3。 |AA|2A|A|2（2分|P(A)|A2|2|A|（2分）。A 為空集：注意 A2=空關(guān)系|AA|2A|0|P(A)|A2|1。（1分A 為有限集且|AA|2A|A|2122|A|P(A)|A2|。（1分A 為有限集且|AA|2A|A|242|A|P(A)|A2|。（1分A 為有限集且|AA|2A|A|2 =982|A|P(A)|A2|。（1分A 為有限集且|AA|2A|A|22|A|P(A)|A2|。（1分A 為無(wú)限|AA|2A|A|2|A|2|A|（康托定理）|P(A)|A2|（1分）。在

2、一種計(jì)算機(jī)信息檢索的模型中，一個(gè)文件是由一些關(guān)鍵字組成的，而一個(gè)倒排文件是由含有某個(gè)關(guān)鍵字的所有文件組成的。一次查詢(xún)的輸入是一個(gè)關(guān)鍵字，輸出是這個(gè)關(guān)鍵字的倒排文件，一次查詢(xún)的開(kāi)銷(xiāo)就是包含這個(gè)關(guān)鍵字的文件個(gè)數(shù)。多次查詢(xún)就是查詢(xún)一個(gè)關(guān)鍵字序列（其中可能有重復(fù)關(guān)鍵字）中的每個(gè)關(guān)鍵字，多次查詢(xún)的開(kāi)銷(xiāo)文件集合 D=d1,d2,dn，關(guān)鍵字集合 K=k1,k2,km，倒排文件集合 K=k1,k2,km K 一一對(duì)應(yīng)。D P(K)，K包含于 P(D)，kidjdjki（4分）KP(D)的函數(shù) Q：KP(D)kQ(k)（2分）k的開(kāi)銷(xiāo)是|Q(k)|（2分）。同的 si 求|Q(si)|之和（2 分）。Edk（

3、4分）ddk的鄰域（2分）kk的度數(shù)（2分）。多次查詢(xún)就和，重復(fù)關(guān)鍵字只計(jì)算一次（2分）。證明或下列命題：“設(shè)平面上有100個(gè)點(diǎn)，其中任意兩點(diǎn)間的距離至少是 1，則最多有 300 對(duì)點(diǎn)距離恰好是 1”。距離恰好是 1（2 分）。根據(jù)握手定律（3分），所謂 n G=，其中 V= | 哪些正整數(shù)值時(shí)，G是圖，并給出證明。分情況。注意 G 的頂點(diǎn)數(shù)是 m1*m2*m3*mn所有mj都為1：G 是平凡圖，是圖（2 分）恰好有一個(gè) mj 大于 1：G 是長(zhǎng)度大于 1 的初級(jí)路徑，不是（2分）至少有兩個(gè) mj 大于 1：G 是偶圖（無(wú)奇數(shù)長(zhǎng)度回路）（2 分）。 (3a) m1*m2*m3*mn是偶數(shù)：G是圖，用歸納法構(gòu)造回路（2分）。(3b)m1*m2*m3*mn是奇數(shù)：G不是圖，偶圖兩部分頂點(diǎn)數(shù)相等，總頂點(diǎn)數(shù)是偶數(shù)（2分）。 回路的長(zhǎng)度不超過(guò)連接這些點(diǎn)的最小生成樹(shù)（不添加額外頂點(diǎn)） 小”匹配，加入匹配“邊”得到圖