2023年7月19日发(作者：)
设p：他用功；q：他成绩好.命题u：“只要他用功，他成绩才好”可以符号化为（d）
A. u: p→q B. u: p∨q C. u: ﹁p∨﹁q D. u: q→p
设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（ b）
A． P∧ Q B． P∨ Q C．（PQ） D．（ P∨ Q）
设A(x)：x是实数，B(x)：x是有理数，命题“有的实数是有理数”符号化为（c）
A.
∃ x(A(x) →B(x)) B. ∃ x(A(x) ∨B(x)) C. ∃ x(A(x) ∧B(x)) D. ﹁(∀ x)(A(x) ∧﹁B(x))
下列由邻接矩阵表示的有向图中，为欧拉图的是（）
2017-2018学年《离散数学》模拟试题
By烟台大学计-165
一、 单项选择题（10*2=20）
1. 下列语句是命题的是（）
A.全体起立!
C.我在说谎
B.x=0
D.张三生于1886年的春天
2. 下列由关联矩阵表示的无向图中，为欧拉图的是（） 3. 下列公式中，永真式是（）
A. (p∧﹁p)
↔q
C. p∨(﹁p∧q)
B. (p→﹁q)∨p
D.
﹁(p∨q) ∨q
4. 设命题函数R(x)：x是实数；L(x,y)：x＜y；则语句“没有最小的实数”可以符号化为（）
A.
∀ x( R(x)
→
∃ y( R(y)
∧ L(x, y) ) )
B.
∃ x( R(x)
→
∀ y( R(y)
∧ L(x, y) ) )
C.
∀ x( R(x)
→
∃ y( R(y)
∧ L(y, x) ) )
D.
∃ x( R(x)
→
∀ y( R(y)
∧ L(y, x) ) )
5. 下面的符号集中不是前缀码的是（）
A. C1={0,10,110,1111}
B. C2={1,01,001,000}
C. C3={1,11,101,001,0011}
D. C4={b,c,dd,dc,aba,abb,abc}
6. 某有向图G1的邻接矩阵第i行中1的个数表示第i个点的（）
A.出度 B.入度 C.前驱 D.后继
7. 设p：他怕困难；q：他获得成功.命题u：“只要他怕困难，他就不会获得成功”可以符号化为（）
A. u: p→q B. u: q→p C. u: ﹁p→q D. u: q→﹁p
8. 集合E=N+,x={1,2,3,{1,2,3},4,5},y={{1,2,3},3,4},z={1,2,3}，下列说法错误的是（）
A. (x-y)-z=(x-z)-y B. ∪x={1,2,3,4,5}
C. y∩z={{1,2,3}} D. ∩y=∅
9. 下列关于图论的说法，正确的是（）
A. 不含平行边或环的图称为简单图
B. 含平行边和环的图称为多重图
C. 无向完全图K4是欧拉图
D. 仅有一个孤立结点构成的图是零图
E. 图中的基本回路都是简单回路
F. 有n(n>1)个孤立结点构成的图是平凡图
G. 无向完全图Kn每个结点的度数是n
10. 一棵树T有2个2度顶点，1个3度顶点，3个4度顶点，树叶片数为（）
A.8 B.9 C.10 D.11
二、 计算题（3*10=30）
1. 求P∨（﹁P→（Q∨（﹁Q→R）））的主析取范式和主合取范式.
2. 设图G2如题图所示：
（1） 写出图G2的邻接矩阵；
（2） 求G2中长度为4的通路条数； （3） 求G2中长度为4的回路条数.
（4） 求G2的可达矩阵.
3. 设有一组权为2,3,5,7,11,13,17,19,23,29,31.
（1） 求最优二叉树T；
（2） 求T的权.
三、 分析题（3*10=30）
1. 今有a，b，c，d，e，f，g7个人，已知下列事实：a会讲英语，b会讲英语和汉语，c会讲英语，意大利语和俄语，d会讲日语和汉语，e会讲德语和意大利语，f会讲法语，日语和俄语，g会讲法语和德语.这七个人应如何排座位，才能使每个人都能和身边的人交谈.
2. 设A={1,2,3,4,5,6,7,8,9,10}，R是A上的二元关系，R={
（1） 用列元素法表示R，画出R的关系图；
（2） 依据（1）中结果，说明R的性质.
3. 设A={1,2,3,6,9,18}，≤为整除关系.
（1） 画出
（2） 求子集B={3,6,9}的最大元，最小元，极大元，极小元.
四、 证明题（4*5=20）
1. 设A={
证明：~是一个等价关系.
2. 证明：每个节点的度至少为2的图必包含1个回路.( 即若G的最小度大于等于2则G包含圈)
3. 已知在某群G中，存在a,b∈G，且有a3b3=(ab) 3，a 4b 4=(ab) 4，a 5b 5=(ab)
5.
证明：
4. 编程证明：对于给定的一组无向图数据，判断其是否成其为欧拉图.（PS:如果无向图连通并且所有结点的度都是偶数，则存在欧拉回路，否则不存在）连续T组数据输入，每组数据第一行给出两个正整数，分别表示结点数目N(1 < N <= 1000)和边数M；随后M行对应M条边，每行给出两个正整数，分别表示该边连通的两个结点的编号，结点从1～N编号.
若为欧拉图输出1，否则输出0.
DB
2017-2018学年《离散数学》模拟试题
一、 单项选择题（10*2=20）
DBBCC ADCEB
二、 计算题（3*10=30）
T权=5+10+17+34+65+160+95+42+53+24
三、 分析题（3*10=30）
解：用结点表示人，用边表示连接的两个人能讲同一种语言，构造出图G如下：
在G中存在着一条哈密顿回路如下，根据这条回路安排座位，就能够使每个人都能和他身边的人交谈。
解：R={<1,9>,<2,8> ,<3,7> ,<4,6> ,<5,5> ,<9,1>,<8,2> ,<7,3> ,<6,4> }
易知 R既不是自反也不是反自反的
R是对称的
R不是反对称的
R不是传递的。
四、 证明题（4*5=20）
1. 设A={
证明：~是一个等价关系.
2. 证明：每个节点的度至少为2的图必包含1个回路.
反证：如果G中不存在回路,则必有一个节点的度为1
可以说明：任意找一个节点,开始遍历,那么最终会访问到一个叶子节点.
任何一个访问到的节点u,存在以下几种情况
1. 是叶子节点（证明结束） 2. 存在节点v,v尚未被访问,且边(u,v)存在,则继续访问v
3. 任何与u有边相连的节点都已经被访问,这种情况会构成回路（与假设矛盾,证明结束）
因为节点个数有限,所以只有有限次可能会落入情况2,随着遍历的进行,必然会落入情况1和3
任取G中一点v0,设v0的一个邻居为v1,v0和v1构成一个链C.
取v1的不在C中的邻居v2.若v2不存在,则C已经变成了圈；若v2存在,则将v2添加到C中.
再取v2的不在C中邻居v3.同样地,若v3不存在,则C包含圈；若v3存在,将v3添加到C中.
重复上述过程,当G的有限的顶点被取完的时候,C必包含圈.
3. 已知在某群G中，存在a,b∈G，且有a3b3=(ab) 3，a 4b 4=(ab) 4，a 5b 5=(ab)
5.
证明：
4.编程证明：对于给定的一组无向图数据，判断其是否成其为欧拉图（.PS:如果无向图连通并且所有结点的度都是偶数，则存在欧拉回路，否则不存在）连续T组数据输入，每组数据第一行给出两个正整数，分别表示结点数目N(1 < N <= 1000)和边数M；随后M行对应M条边，每行给出两个正整数，分别表示该边连通的两个结点的编号，结点从1～N编号.
若为欧拉图输出1，否则输出0.
#include
#include
#include
using namespace std;
const
int
MAX = 1005;
int
mp[MAX][MAX];
int
vt[MAX];
int
degree[MAX];
int
main()
{
int
t;
cin >> t;
while
(t--)
{
int
n, m;
cin >> n >> m;
int
va, vb;
memset(vt, 0, sizeof(vt));
memset(mp, 0, sizeof(mp));
memset(degree, 0, sizeof(degree));
for
(int
i = 0; i < m; i++)
{
cin >> va >> vb;
mp[va][vb] = mp[vb][va] = 1;
degree[va]++;
degree[vb]++;
}
queue
(n);
vt[n] = 1;
while
(!())
{
int
tp = ();
();
for
(int
i = 1; i <= n; i++)
{
if
(!vt[i] && mp[tp][i])
数是否为偶数
{
vt[i] = 1;
(i);
}
}
}
if
(vt[1] == 1)//首先判断图是否连通
{
int
flag = 1;
for
(int
i = 1; i <= n; i++)//判断每个点的度 {
if
(degree[i] % 2
!= 0)
{
flag = 0;
break;
}
}
if
(flag)
cout << 1
<< endl;
else
cout << 0
<< endl;
}
else
cout << 0
<< endl;
}
return
0;
}
4.
发布者：admin，转转请注明出处：http://www.yc00.com/xiaochengxu/1689732437a281799.html
评论列表（0条）