《2019年4月自考离散数学试卷及答案解析》由会员分享，可在线阅读，更多相关《2019年4月自考离散数学试卷及答案解析（5页珍藏版）》请在金锄头文库上搜索。
1、2 0 19年4月全国自考离散数学试题及答案解析一、单选题（共4题，共8 分）1、下面四组数能构成无向图的度数列的有()。A.2,3,4,5,6,7B.1,2,2,3,4C.2,1,1,1,2D.3,3,5,6,0答案：B解析：暂无解析2、下列几个图是简单图的有()。A.G 1=(V1,E1),其中V1=a,b,c,d,e ,E1=a b,b e,e b,a e,d e B.G 2=(V2,E2)其中V2=V1,E2=,C.G=(V3,E3),其中V3=V1,E3=a b,b e,e d,c c D.G=(V4,E4),其中V4=V1,E4=（a,a）,（a,b）,（b,c）,（e,c）,（e
2、,d）。答案：B解析：暂无解析3、下列图中是欧拉图的有()。A.B.C.D.答案：B解析：暂无解析4、与命题公式P(Q R)等价的公式是()A.B.C.D.答案：B解析：暂无解析二、判断题（共10 题，共2 0 分）1/51、命题公式(A(A B)B是一个矛盾式。答案：错误解析：暂无解析2、任何循环群必定是阿贝尔群，反之亦真。答案：错误解析：暂无解析3、根树中最长路径的端点都是叶子。答案：错误解析：暂无解析4、若集合A 上的关系R是对称的，则R-1也是对称的。答案：正确解析：暂无解析5、数集合上的不等关系()可确定A 的一个划分。答案：错误解析：暂无解析6、设集合A、B、C为任意集合，若A B
3、=A C，则B=C。答案：正确解析：暂无解析7、函数的复合运算“。”满足结合律。答案：正确解析：暂无解析8、若G 是欧拉图，则其边数e 合结点数v 的奇偶性不能相反。答案：错误解析：暂无解析9、图G 为(n,m)图，G 的生成树T G 必有n 个结点。答案：正确2/5解析：暂无解析10、使命题公式P(Q R)的真值为F的真值指派的P、Q、R值分别是T、F、F。答案：正确解析：暂无解析三、填空题（共10 题，共2 0 分）1、任何(n,m)图G=(V,E),边数与顶点度数的关系是_。答案：解析：暂无解析2、当n 为_时,非平凡无向完全图K n 是欧拉图。答案：奇数解析：暂无解析3、已知一棵无向树
4、T 有三个3顶点,一个2 度顶点,其余的都是1度顶点,则T 中有_个1度顶点。答案：5解析：暂无解析4、设X 1,2,3,4,R 1,2,2,4，3,3，则r(R)=_;s(R)=_;t(R)=_。答案：解析：暂无解析5、任意两个不同小项的合取为，全体小项的析取式为_。答案：永假式(矛盾式)、永真式(重言式)解析：暂无解析6、设Q(x):x 为偶数，P(x):x 为素数，则下列命题：(1)存在唯一偶素数;(2)至多有一个偶素数;分别形式化：(1)_(2)_。答案：解析：暂无解析7、含5个结点，4条边的无向连通图(不同构)有_个，它们是_。答案：3、3/5解析：暂无解析8、设T 为根树，若_，则
5、称T 为m 元树;若_则称T 为完全m 叉树。答案：每个结点的出度都小于等于m;除叶子外，每个结点的出度都等于m。解析：暂无解析9、在代数系统(N，+)中，其单位元是0，仅有_有逆元。答案：1解析：暂无解析10、如果连通平面图G 有n 个顶点，e 条边，则G 有_个面。答案：e+2-n解析：暂无解析四、问答题（共5题，共38 分）1、若图G 中恰有两个奇数顶点，则这两个顶点是连通的。答案：证：设G 中两个奇数度结点分别为u，v。若u，v 不连通，即它们中无任何通路，则至少有两个连通分支G 1、G 2，使得u，v 分别属于G 1和G 2。于是G 1与G 2 中各含有一个奇数度结点，与握手定理矛盾
6、。因而u，v 必连通。解析：暂无解析2、证明：在6 个结点12 条边的连通平面简单图中，每个面的面度都是3。答案：证：n=6,m=12 欧拉公式n-m+f=2 知f=2-n+m=2-6-12=8。由图论基本定理知：所以必有，即每个面用3条边围成。解析：暂无解析3、某次会议有2 0 人参加，其中每人至少有10 个朋友，这2 0 人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友?(理由)答案：解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图,，2 0 人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得回路。由题已知，由判定定理，G 中存在一条汉密尔顿回
7、路。即所谈情况可能。解析：暂无解析4/54、试判断(z,)是否为格?说明理由。答案：解析：暂无解析5、设R是实数集，f:Rx RR,f(a,b)a+b，g:Rx RR,g(a,b)=a b。求证：f 和g 都是满射，但不是单射。答案：解析：暂无解析五、计算题（共10 题，共2 0 分）1、在通讯中，八进制数字出现的频率如下：0：30%、1：2 0%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码(写出求解过程)。答案：解：用 10 0 乘各频率并由小到大排列得权数(1)用H u f f m a n 算法求最优二叉树：(2)前缀码用0 0 0 0 0 传送5;0 0 0 0 1传送6;0 0 0 1传送7;10 0 传送3;10 1传送4;0 0 1传送2;11传送1;0 1传送0(频率越高传送的前缀码越短)。解析：暂无解析2、求命题公式p q r 的主合取范式与主析取范式。答案：解析：暂无解析3、无向图G 有12 条边，G 中有6 个3度结点，其余结点的度数均小于3，问G 中至少有多少个结点?答案：解析：暂无解析4、无向图G 有9个结点，每个结点的度数不是5就是6，求证：G 中至少有5个6 度结点或6 个5度结点。答案：解析：暂无解析Powered by TCPDF(www.tcpdf.org)5/5
