2024年3月25日发(作者：三升四衔接数学试卷)
-- -
编
号
1
题目
1 设集合A={a，b，c，d}上的关系
答:
R={ ,< b , a > ,< b, c > , < c ,
0
d >}用矩阵运算求出R的传递闭包
1
t (R)。
M
R
0
0
答案
题分
型 值
大纲
难
度
3
100
10
010
01
MMM
，
RR
R
2
00001
00000
0
1
M
R
0
0
101
010
000
000
1
1
0
0
111
111
001
000
10
01
00
00
1
0
M
R
0
0
010
101
000
000
简8 4.3
答
题
M
R
3
M
R
2
M
R
4
M
R
3
M
t(R)
M
R
M
R
2
M
R
3
M
R
4
t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }
2
如下图所示的赋权图表示某七个
城市
v
1
,v
2
,,v
7
及预先算出它
们之间的一些直接通信线路造
价，试给出一个设计方案，使得
各城市之间能够通信而且总造价
树权C(T)=23+1+4+9+3+17=57即为总造价。
- - 优质资料
答: 用Kruskal算法求产生的最优树。算法略。结果如图：
简8 7.2
答
题
3
-- -
最小。
3
设 6 ,+ 6 >是一个群，这里+ 6 是模6 加法，Z 6 ={[0 ]，[1]，[2]，[3]，[4]， [5]}，试求出 6 ,+ 6 >的所有子群。 4 权数1，4，9，16，25，36，49，答: 64，81，100构造一棵最优二叉树。 简8 7.2 答 题 3 答: 子群有<{[0]},+ 6 >；<{[0],[3]},+ 6 >；<{[0],[2],[4]},+ 6 >；<{Z 6 },+ 6 > 简8 8.3 答 题 3 - - 优质资料 -- - 5 集合X={<1,2>, <3,4>, <5,6>, …}，R={< 1 ,y 1 >, 2 ,y 2 >>|x 1 +y 2 x 2 +y 1 } 。 1） 说明R是X上的等价关系。（ 6 分） 2） 求出X关于R的商集。（2分） = 答: 1）、 1、 自反性： x,yX,由于xyxy 简8 4.4 答 题 3 x,y,x,yR 2、 R自反 对称性： x 1 , y 1 X , x 2 , y 2 X 当x 1 ,y 1 ,x 2 ,y 2 R时即x 1 y 2 x 2 y 1 也即x 2 y 1 x 1 y 2 故x 2 ,y 2 ,x 1 ,y 1 RR有对称性 3、 传递性： x 1 , y 1 X , x 2 , y 2 Xx 3 , y 3 X 当x 1 ,y 1 ,x 2 ,y 2 R且x 2 ,y 2 ,x 3 ,y 3 R时 x 1 y 2 x 2 y 1 即 x 2 y 3 x 3 y 2 (1)(2) (1) (2) x 1 y 2 x 2 y 3 x 2 y 1 x 3 y 2 即 x 1 y 3 x 3 y 1 故x 1 ,y 1 ,x 3 ,y 3 RR有传递性 由（1）（2）（3）知：R是X上的先等价关系。 2）、X/R= {[ 1,2 ] R } 6 设集合A={ a ,b , c , d }上关系R={< 答: 简8 4.1;4.3 答 4 - - 优质资料 -- - a, b > , < b , a > , < b , c > , < c , d >} 要求 1）、写出R的关系矩阵和关 系图。（4分） 2）、用矩阵运算求 出R的传递闭包。（4分） 题 0 1 1、 M R 0 0 100 010 ； 关系图 001 000 010 101 000 000 2、 M R 2 1 0 M R M R 0 0 0 1 M R 0 0 1 0 M R 0 0 M R 3 M R 2 101 010 000 000 010 101 M R 2 M R 5 M R 3 ,M R 6 M R 4 , 000 000 1 1 0 0 111 111 001 000 M R 4 M R 3 M t(R) M R M R 2 M R 3 M R 4 t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }。 - - 优质资料 -- - 7 利用主析取X式，判断公式 (PQ)QR 的类型。 8 (PQ)QR(PQ)(QR) 答: (PQ)(QR)PQQRF 它无成真赋值，所以为矛盾式。 简8 2.3 答 题 简8 7.2 答 题 3 在二叉树中:1)求带权为2，3，5，答: （1）由Huffman方法,得最佳二叉树为： 7，8的最优二叉树T。（4分）2) 求T对应的二元前缀码。（4分） 3 （2）最佳前缀码为：000，001，01，10，11 9 下图所示带权图中最优投递路线 并求出投递路线长度（邮局在D 点）。 答: 图中奇数点为E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF 道路EG、GF，得图G，则G是欧拉图。 由D开始找一条欧拉回路：DEGFGEBACBDCFD。 道路长度为： 35+8+20+20+8+40+30+50+19+6+12+10+23=281。 10 设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 答: (1)≤={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>， 简8 4.4 答 题 4 ‘‘ 复制 简8 7.2 答 题 5 24}，“ ”为S上整除关系，问： <2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>} I S - - 优质资料 -- - （1）偏序集 S , 的Hass图 如何？（2）偏序集 {S ,} 的极小 元、最小元、极大元、最大元是 什么? covS={<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,<6,12> ,<8,24>,<12,24>} Hass图为 （2）极小元、最小元是1，极大元、最大元是 24。 11 设解释R如下：D R 是实数集，D R 中特定元素a=0，D R 中特定函数 答: 公式A涵义为：对任意的实数x,y,z，如果x A的真值为： 真（T）。 简8 3.2 答 题 3 f(x,y)xy ，特定谓词 F(x,y):xy ，问公式 Axyz(F(x,y) 的涵义 F(f(x,z),f(y,z))) 如何？真值如何？ 12 给定3个命题：P：比XX人口多； Q：2大于1；R：15是素数。 求 复合命题： 答: P，Q是真命题，R是假命题。 (QR)(PR)(10)(11)010 简8 2.2 答 题 3 - - 优质资料 -- - (QR)(PR) 的真值。 简8 3.1;3.2 答 题 3 13 给定解释I：D={2，3}，L（x,y）为 yxL(x,y)y(L(2,y)L(3,y))(L(2,2)L(3,2))(L(2,3)L(3,3)) L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) 答: (10)(01)000 = L (3 , 2 )=0 ,求谓词合式公式 yxL(x,y) 的真值。 14 wff 将 x((yP(x,y)) 化为 (zQ(z)R(x))) 答: 与其等价的前束X式。 15 简述关系的性质有哪些？ x(y(P(x,y))((zQ(z))R(x)))x((y(P(x,y)((zQ(z))R(x))) x(y(P(x,y)z(Q(z))R(x)))xyz(P(x,y)Q(z)R(x)) 自反性，对称性，传递性，反自反性，反对称性 简8 3.2 答 题 3 简8 4.3 答 题 简8 7.2 答 题 1 16 假设英文字母，a，e，h，n，p，r，答:解：传输它们的最佳前缀码如上图所示，happy new year的编码信息为： w，y出现的频率分别为12%，8%， 10 011 0101 0101 001 110 111 0100 001 111 011 000 15%，7%，6%，10%，5%，10%， 最优二叉树求解过程如 求传输它们的最佳前缀码，并给 附： 出happy new year的编码信息。 下： 3 - - 优质资料 -- - 17 用washall方法求图的可达矩阵， 并判断图的连通性。 0 1 答: A(G) 0 0 011 010 001 100 011 0 011 1 A ； 2： A[4，2]=1， i 0 001 1 100 011 011 001 111 111 111 111 111 011 011 001 111 简8 6.3 答 题 3 0 1 i 1：A[2，1]=1， A 0 0 0 1 i 3： A[1，3]=A[2，3]=A[4，3]=1， A 0 1 1 1 A 4： A[k，4]=1，k=1，2，3，4， i 1 1 18 设有a、b、c、d、e、f、g七个人， 他们分别会讲的语言如下：a：英， b：汉、英，c：英、西班牙、俄， d：日、汉，e：德、西班牙，f： 法、日、俄，g：法、德，能否将 这七个人的座位安排在圆桌旁， 使得每个人均能与他旁边的人交 谈？ 答: p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。 简8 6.4 答 题 3 用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无 向边连结，所得无向图为 此图中的Hamilton回路即是圆桌安排座位的顺序。 Hamilton回路为a b d f g e c a。 - - 优质资料 -- - 19 用 Huffman算法求出带权为2，3， 答: 5，7，8，9的最优二叉树T，并 求W（T）。若传递a ，b， c， d ， e， f 的频率分别为2%， 3% ， 5 %， 7% ，8% ，9%求传输它 的最佳前缀码。（ 简8 7.2 答 题 3 W(T)24345392728283 （1） 用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e 传输它们的最优前缀码为{0000，0001，001，01，10，11} 。 20 构造一个结点v与边数e奇偶性相 反的欧拉图。 简8 6.4 答 题 5 答: 21 设A={1，2，3，4}，S={{1}，{2， 3}，{4}}，为A的一个分划，求由S 导出的等价关系。 答: R={< 1 , 1 > , < 2 , 2> , < 2, 3 > , < 3 , 2 > , < 3 , 3 > < 4 , 4 > } 简8 4.4 答 题 3 - - 优质资料 -- - 22 设 A { x 1 , x 2 , x 3 , x 4 , x 5 } ，偏序 集 A,R 的Hass图为 求 ①A中最小元与最大元；② 答: ①A中最大元为 x 1 ，最小元不存在； ② { x 3 , x 4 , x 5 } 上界 x 1 , x 3 ，上确界 x 1 ；下界无，下确界无。 简8 4.4 答 题 3 {x 3 ,x 4 ,x 5 } 的上界和上确界，下 界和下确界。 23 用Warshall算法，对集合A={1，2， 3，4，5}上二元关系 R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>} 求t（R）。 答: 简8 4.1;4.3 答 题 4 1 0 M R 0 0 0 1000 0010 0001 1000 0000 i 1时， M R [1,1]=1, A = M R i 2时，M[1,2]=M[4,2]=1 1 0 A= 0 0 0 1010 0010 0001 1010 0000 - - 优质资料 -- - i 3时，A的第三列全为0，故A不变 i 4时，M[1,4]=M[2,4]=M[4,4]=1 1 0 A= 0 0 0 1 0 A= 0 0 0 24 将谓词公式 1010 1010 0001 i 5时，M[3,5]=1 ，这时 1010 0000 1010 1010 0001 1010 0000 简8 2.1;3.1; 答3.2 题 3 所以t (R)={<1,1>, <1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>} 。 ((x)(P(x)(yQ(y))(y)R(y) ((xP(x)(yQ(y))(y)R(y) ((x)P(x)(y)(Q(y))(y)R(y) ((x)P(x)(yQ(y))(y)R(y) 答: ((x)P(x)(yQ(y))(z)R(z) ((x)P(x) (y)Q(y))(y)R(y) 化为前束析取X式与前束合取X 式。 (x)(y)(z)((P(x)Q(y))R(z)) 前束析取范式 (x)(y)(z)((P(x)R(z))(Q(y)R(z)) 前束合取范式 25 １)、画一个有一条欧拉回路和一 条汉密尔顿回路的图。 答: 简8 6.4 答 题 3 - - 优质资料
更多推荐
前束,矩阵,求出,析取
发布评论