重复查询同一个关键字的开销之只计算一次。假设关键字和文件的个数都 是有限的,试用集合论或图论的术语来描述这个模型,并给出上述斜体字 概念的形式化定义 解答与评分标准 集合论 文件集合D={dhdh2,dn},关键字集合K={k1,k2km},倒排文件集合 K={k1k2,km}与关键字集合K一一对应。D包含于P(K,K包含于 PD),k属于d当且仅当d属于k(4分)。查询是从K到P(D)的函数 Q:K→P(D),查询k是求Q(k)(2分),查询k的开销是Qk川(2分) 多次查询(s12S)就是求(Q(s1)Q(2),(s),多次查询的开销是对不 同的s求(Q(s之和(2分) 图论: 部图G=<DK,E>,D为文件集合,K为关键字集合,E为边集合,(d,k) 是E中的边当且仅当文件d含有关键字k(4分)。文件d的内容就是d 的相邻顶点集合(邻域),倒排文件k的内容就是k的邻域,查询k就是 求k的邻域(2分),查询k的开销就是k的度数(2分)。多次查询就 是求一组关键字的邻域,多次查询的开销就是这组关键字顶点的度数之 和,重复关键字只计算一次(2分)。 6.证明或推翻下列命题:“设平面上有100个点,其中任意两点间的距离至 少是1,则最多有300对点距离恰好是1” 解答与评分标准 命题成立(2分)。 无向图G=<V,E>,V是平面上的这100个点,两个点相邻当且仅当这两点 距离恰好是1(2分)。 每个顶点的度数不超过6(3分) 根据握手定律(3分), 2E顶点度数之和≤100*6,所以这个图的边数不超过300(2分) 7.所谓n维网格就是一个无向图G=<VE,其中{<12…,>|1s≤m lssm},E={(v,n2)v1和n2恰好只在一个坐标上相差1}。讨论当m和n 哪些正整数值时,G是哈密顿图,并给出证明。 解答与评分标准 分情况讨论。注意G的顶点数是m1*m2*m3*,*mn (1)所有m都为1:G是平凡图,是哈密顿图(2分) (2)恰好有一个m大于1:G是长度大于1的初级路径,不是哈密顿图 (2分)。- 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) 是 E 中的边当且仅当文件 d 含有关键字 k（4 分）。文件 d 的内容就是 d 的相邻顶点集合（邻域），倒排文件 k 的内容就是 k 的邻域，查询 k 就是 求 k 的邻域（2 分），查询 k 的开销就是 k 的度数（2 分）。多次查询就 是求一组关键字的邻域，多次查询的开销就是这组关键字顶点的度数之 和，重复关键字只计算一次（2 分）。 6． 证明或推翻下列命题：“设平面上有 100 个点，其中任意两点间的距离至 少是 1，则最多有 300 对点距离恰好是 1”。 解答与评分标准： 命题成立（2 分）。 无向图 G=<V,E>，V 是平面上的这 100 个点，两个点相邻当且仅当这两点 距离恰好是 1（2 分）。 每个顶点的度数不超过 6（3 分）。 根据握手定律（3 分）， 2|E|=顶点度数之和 ≤100*6, 所以这个图的边数不超过 300（2 分）。 7． 所谓 n 维网格就是一个无向图 G=<V,E>，其中 V={<i1,i2,…,in> | 1≤ij≤mj, 1≤j≤n}，E={(v1,v2)| v1和 v2恰好只在一个坐标上相差 1}。讨论当 mj和 n 取 哪些正整数值时，G 是哈密顿图，并给出证明。 解答与评分标准： 分情况讨论。注意 G 的顶点数是 m1*m2*m3*…*mn。 (1) 所有 mj都为 1：G 是平凡图，是哈密顿图（2 分）。 (2) 恰好有一个 mj大于 1：G 是长度大于 1 的初级路径，不是哈密顿图 （2 分）