编号
题目
答案
题型
分值
大纲
难度
11
设集合A={a，b，c，d}上的关系Rb总001={<a , b > ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。 
答:
  ，
t (R)={<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > }
简答题
8
3
如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 
答: 用Kruskal算法求产生的最优树。算法略。结果如图：
树权C(T)=23+1+4+9+3+17=57即为总造价。
简答题
8
3
设<Z6,+6>是一个，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出<Z6,+6>的所有子。
答: 子有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>
简答题
8
3
权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。
答:
简答题
8
3
集合X={<1,2>, <3,4>, <5,6>,
… }，R={<<x1,y1>,<x2,y2>>|x1+y2 = x2+y1} 。
1）说明R是X上的等价关系。 （6分）
2）求出X关于R的商集。（2分）
答: 1）、
1、自反性：
2、对称性：
3、传递性：
即
由（1）（2）（3）知：R是X上的先等价关系。
2）、X/R=
简答题
8
3
设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}
要求 1）、写出R的关系矩阵和关系图。（4分） 2）、用矩阵运算求出R的传递闭包。（4分）
答:
1、；        关系图
2、
    t (R)={<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > }。
简答题
8
;
4
利用主析取范式，判断公式的类型。
答:
它无成真赋值，所以为矛盾式。
简答题
8
3
在二叉树中:1)求带权为2，3，5，7，8的最优二叉树T。（4分）2)求T对应的二元前缀码。（4分）
答: （1）由Huffman方法,得最佳二叉树为：
（2）最佳前缀码为：000，001，01，10，11
简答题
8
3
下图所示带权图中最优投递路线并求出投递路线长度（邮局在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。
简答题
8
5
设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 24}，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?
答: (1)≤={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>}
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。
简答题
8
4
设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？
答: 公式A涵义为：对任意的实数x,y,z，如果x<y  则  (x-z) < (y-z)
  A的真值为： 真（T）。
简答题
8
3
给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：的真值。
答: P，Q是真命题，R是假命题。
简答题
8
3
给定解释I：D={2，3}，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式的真值。
答:
简答题
8
;
3
将化为与其等价的前束范式。
答:
简答题
8
3
简述关系的性质有哪些？
自反性，对称性，传递性，反自反性，反对称性
简答题
8
1
假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。
答:解：传输它们的最佳前缀码如上图所示，happy new year的编码信息为：
10 011 0101 0101 001 110 111 0100 001 111 011 000
附：最优二叉树求解过程如下：
简答题
8
3
用washall方法求图的可达矩阵，并判断图的连通性。
答:
    1：A[2，1]=1，；  2： A[4，2]=1，
3： A[1，3]=A[2，3]=A[4，3]=1，
4： A[k，4]=1，k=1，2，3，4，
p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。
简答题
8
3
设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？
答:
用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为
此图中的Hamilton回路即是圆桌安排座位的顺序。
Hamilton回路为a b d f g e c a。
简答题
8
3
用 Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。若传递a ，b， c， d ，e， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。（
答:
（1）用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e
传输它们的最优前缀码为{0000，0001，001，01，10，11} 。
简答题
8
3