试题页表4.(简答题)

第1页共7页序号试题内容1用真值表法判断下列公式的类型.（1）（PQ）（PQ）（2）（PQ）R（3）（P（PQ））R（4）（PQ）Q4求下列公式的主析取和合取范式。（1）(┐PQ)∧(PR)（2）(PQ)∨(P∧R)（3）P∧Q∨R10设A={a,b,{a,b}}，B={a,b}，试求B－A，AB11对60个学生参加课外活动的情况进行调查。结果发现，25人参加物理小组，26人参加化学小组，26人参加生物小组。9人既参加物理小组又参加生物小组，11人既参加物理小组又参加化学小组，8人既参加化学小组又参加生物小组。8人什么小组也没参加，回答下列各问题：（1）有多少人参加了3个小组？（2）只参加一个小组的有多少人？12在20名青年有10名是公司职员,12名是学生,其中5名既是职员又是学生,问有几名既不是职员,又不是学生。13求1到500之间能被2,3,7任一数整除的整数个数。14设A={1，2，3，4}，R，S都是A上的二元关系，其中：R={1,2，2,1，2,3，3,2，4,4},S={1,1，4,4}(1)给出R的关系矩阵和关系图；(2)求dom(RS)，ran(RS),fld(R-S)，RoS，R2，R-115设A={1,2,3,4,5,6,7,8,9,10}，R是A上的二元关系，R={x,y|x,y∈A∧x+y=10}说明R具有哪些性质。16设A={a,b,c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性(要求画出R的关系图)。第2页共7页序号试题内容17将集合3,2,1A上的下述二元关系：R=｛〈1，1〉，〈1，2〉〈1，3〉〈3，3〉｝T=｛〈1，1〉，〈1，2〉〈2，1〉〈2，2〉，〈3，3〉｝S=｛〈1，1〉，〈1，2〉〈2，2〉〈2，3〉｝φA×A分别画出R、S、T、φ、A×A的关系图，并按自反性、对称性、反对称性和传递性分类（10分）18设集合A={1，2，3，4，5}，试求A上的模2同余关系R的关系式。19设A={a,b,c},A上的二元关系R的关系图如下图所示,（1）写出二元关系R的关系式和关系矩阵M；（2）求r(R),s(R),t(R)。cba20设cbaA,,，A上的二元关系bccbbaaaR,,,,,,,，求r(R)，s(R)，t(R)。21设集合A={a，b，c，d}，R1，R2都是A上的二元关系，R1={a，b，b，c，c，a}，R2=，试求R1和R2的自反闭包，对称闭包和传递闭包。22设A={a,b,c,d},A上的二元关系R={a,b,b,a,b,c,c,d,d,b},求R的自反闭包r(R)，对称闭包s(R)和传递闭包t(R)。23设集合A={a，b，c}，A上的二元关系R={a,b，b,b，b,c},试给出R，r(R)，s(R),t(R)的关系图。24设A={a,b,c},写出集合A上的所有不同的划分和等价关系第3页共7页序号试题内容25设A={a,b,c,d,e,f},A上的等价关系R=AI∪{a,b,b,a,e,f,f,e}，求：（1）a的等价类[]na；(2)求c的等价类[]nc(3)求商集A/R26分别画出下列各偏序集A，R的哈斯图，并求A的极大元、极小元，最大元、最小元。(1)edcbaA,,,,，A上的二元关系R为：,,,,,,,,,,,,ARabacadaebecedeI(2)A={1，2，3，4，6，9，24，54}，R是A上的整除关系。27下图给出了一个偏序关系R的哈斯图。abcdef(1)写出二元关系R的关系式。(2)求子集｛b，c，d｝上的最大元、最小元、极大元、极小元、上界、上确界、下界、下确界。28设A={a,b,c,d,e}，A上的偏序关系R＝{c,a，c,b，d,a，d,b，e,a，e,b，e,c，e,d}IA，求：(1)画出偏序集A，R的哈斯图；(2)求子集B={c,d,e}的极大元，极小元，最大元，最小元，上确界，下确界。第4页共7页序号试题内容30设A={a,b,c,d,e},给定如下：1={{a,b,c},{d,e}},2={{a,b},{c},{d,e}},3={{a,b,c},{c,d,e}},4={{a},{d,e}},5={φ,{a,b,c},{d,e}},6={{a,{b},c},{d,e}},问：哪些是A的划分？33已知无向图G有11条边，2度与3度顶点各2个，其余都是4度顶点，求G中共有几个顶点。（写出过程）34下面的无向图G1和G2同构吗？为什么？G2G1agbcfed567423135下面的有向图G1和G2同构吗？说明理由（4分）G1G223541dceba36有向图G如图所示。用矩阵法求：（8分）（1）G中长度为2的通路有几条？（2）G中长度为3的回路有几条？（3）G的可达矩阵P。V1V4V3V2第5页共7页序号试题内容37有向图G如下所示。求：（1）图G的邻接矩阵A（G）；（2）从1V到4V长度为2和4的通路各有几条？（3）经过4V的长度不大于4的回路共有几条？（4）图G的可达矩阵P（G）V2V3V4V138设有向图G=(V，E)如下图所示，(1)试用邻接矩阵方法求长度为3的路的总数和回路总数；(2)求图G的可达矩阵.V1V4V2V342有向图PERT图如下所示：（1）求图中各顶点的最早完成时间；（2）求图中各顶点的最晚完成时间；（3）求图中的关键路径。1213441602344cghfbdea第6页共7页序号试题内容43有向图PERT图如下所示：（1）求图中各顶点的最早完成时间；（2）求图中各顶点的最晚完成时间；（3）求图中的关键路径。3333222111V1V2V5V3V4V647求下图G的一棵最小生成树，并求它的权W（T）（5分）123445677848设无向图G如下所示：求最小生成树T。123455574549用克鲁斯卡尔算法求带权图的最小生成树，并求权W(T)3333222134445555第7页共7页序号试题内容50利用KrusKal算法求出下面各加权图的最小生成树及其边权之和W(T)。344423331432151利用KrusKal算法求出下面各加权图的最小生成树及其边权之和W(T)。873533653641521153252在具有n个顶点的完全图Kn中删去多少条边才能得到树？53一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个度数为1的结点？54(1)在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？(2)画出两棵非同构的满足(1)中顶点度数的无向树12TT和。（6分）55求一棵带权为1，1，1，2，2，3，4，5的最优二元树T，并计算它的权W(T)。(6分)56给定权1，2，4，6，6，8，10，10，15，22，36构造一棵最优二元树，并计算它的权W（T）。57设7个字母在通信中出现的频率如下：（8分）a：35%b：20%c：15%d：10%e：10%f：5%g：5%。用最优二元树构造一个表示它们的最佳前缀码，使得用较短的符号串表示频率较大的字母。