单选题 （共 20 题 ），每题只有一个选项正确
命题公式 $(\neg P \rightarrow Q) \rightarrow(\neg Q \vee P)$ 中成真赋值的个数为（）
$\text{A.}$ 0
$\text{B.}$ 1
$\text{C.}$ 2
$\text{D.}$ 3
下列命题公式中, 哪个是永真式（）
$\text{A.}$ $p \wedge \neg q$
$\text{B.}$ $p \rightarrow q$
$\text{C.}$ $(\neg p \vee q) \vee p$
$\text{D.}$ $(\neg p \wedge q) \wedge p$
下面的联结词集合不是完备集的是 $\qquad$
$\text{A.}$ $\{\uparrow\}$ （ 表示与非）
$\text{B.}$ $\{\neg, \rightarrow\}$
$\text{C.}$ $\{\neg, \leftrightarrow\}$
$\text{D.}$ $\{\neg, \vee\}$
联结词组中, 下面哪一个选项是命题公式的最小联结词组？（）
$\text{A.}$ $\{\neg\}$
$\text{B.}$ $\{\uparrow\}$
$\text{C.}$ $\{\wedge\}$
$\text{D.}$ $\{\vee, \wedge\}$
下列 4 个推理中, 不正确的是（）
$\text{A.}$ $A \Rightarrow(A \wedge B)$
$\text{B.}$ $(A \vee B) \wedge \neg A \Rightarrow B$
$\text{C.}$ $(A \rightarrow B) \wedge A \Rightarrow B$
$\text{D.}$ $(A \rightarrow B) \wedge \neg B \Rightarrow \neg A$
下面是真命题的是（ ）
$\text{A.}$ $\{a\} \subseteq\{\{a\}\}$
$\text{B.}$ $\{\{\varnothing\}\} \in\{\varnothing,\{\varnothing\}\}$
$\text{C.}$ $\varnothing \in\{\varnothing,\{\varnothing\}\}$
$\text{D.}$ $a \in\{\{a\}\}$
设 $A, B$ 是集合, 若 $A-B=\varnothing$, 则
$\text{A.}$ $B=\varnothing$
$\text{B.}$ $A=\varnothing$
$\text{C.}$ $A \cap B=\varnothing$
$\text{D.}$ $A \cap B=A$
设集合 $A=\{1,2,3,4,5,6,7,8,9\}$ 上的关系 $R=\{(x, y) \mid x, y \in A$ 且 $x+y=10\}$, 则 $R$ 的性质是 ( ).
$\text{A.}$ . 自反的
$\text{B.}$ 对称的
$\text{C.}$ 对称的、传递的
$\text{D.}$ 反自反的、传递的
下列运算中, 哪种运算关于整数集不能构成半群？（）.
A
$\text{A.}$ $a \circ b=b$
$\text{B.}$ $a \circ b=2 a b$
$\text{C.}$ $a \circ b=|a-b|$
$\text{D.}$ .$ a \circ b=\max \{a, b\}$
若一个代数系统是独异点 (含么半群), 则以下选项中一定满足的是（）。
$\text{A.}$ 封闭性, 且有零元;
$\text{B.}$ 结合律, 且有么元;
$\text{C.}$ 交换性, 且有么元;
$\text{D.}$ 结合律, 且每个元素有逆元.
1. 任何图中必定有偶数个
$\text{A.}$ 入度为偶数的结点
$\text{B.}$ 度数为奇数的结点
$\text{C.}$ 出度为奇数的结点
$\text{D.}$ 度数为偶数的结点
下列关于图连通性的描述中不正确的是
$\text{A.}$ 强连通图必然是单向连通的;
$\text{B.}$ 单向连通图也必然是强连通的;
$\text{C.}$ 弱连通图未必是单向连通的;
$\text{D.}$ 单向连通图必然是弱连通的.
设 $D=\langle V, E\rangle$ 为有向图， $V=\{a, b, c, d, e, f\}$,
$E=\{\langle a, b\rangle,\langle b, c\rangle,\langle a, d\rangle,\langle d, e\rangle,\langle f, e\rangle\}$ 是
$\text{A.}$ 强连通图
$\text{B.}$ 单向连通图
$\text{C.}$ 弱连通图
$\text{D.}$ 不连通图
已知无向图 $G$ 的邻接矩阵为 $\left[\begin{array}{lllll}0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0\end{array}\right]$,有（）.
$\text{A.}$ 5 点, 8 边
$\text{B.}$ 6 点, 7 边
$\text{C.}$ 5 点, 7 边
$\text{D.}$ 6 点, 8 边
若图有穿梭于图 $G$ 的每条边一次且仅一次的回路，该图为（）。
$\text{A.}$ 半欧拉图
$\text{B.}$ 欧拉图
$\text{C.}$ 半哈密顿图
$\text{D.}$ 哈密顿图
下面哪一种图不一定是树（）。
$\text{A.}$ . 无回路的连通图
$\text{B.}$ 有 $n$ 个顶点 $n-1$ 条边的连通图
$\text{C.}$ 每对顶点之间都有通路的图
$\text{D.}$ 连通但删去一条边则不连通的图
n阶非平凡的无向树至少有（）片树叶。
$\text{A.}$ 2
$\text{B.}$ 3
$\text{C.}$ 4
$\text{D.}$ 5
设图 $G$ 是有 6 个顶点的连通图, 总度数为 20 ,则从 $G$ 中删去（ ）边后使之变成树。
$\text{A.}$ 10
$\text{B.}$ 5
$\text{C.}$ 3
$\text{D.}$ 2
下面给出的符号串集合中, 哪一个不是前缀码？（）
$\text{A.}$ $\{0,10,110,1111\}$
$\text{B.}$ $\{1101,1001,101,110\}$
$\text{C.}$ $\{01,001,000,10\}$
$\text{D.}$ $\{b, c, a a, a c, a b a, a b c\}$
二部图 $K_{2,3}$ 是（）。
$\text{A.}$ 欧拉图
$\text{B.}$ 哈密顿图
$\text{C.}$ 非平面图
$\text{D.}$ 平面图