离散数学南昌大学软件学院试卷(软工)(A)备课讲稿

2022年南昌大学软件工程专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、对机器语言程序员透明的是（）A.中断字B.主存地址寄存器C.通用寄存器D.条件码2、指令间“一次重叠”说法有错的是( )A.仅“执行k”与“分析k+1”重叠B."分析k”完成后立即开始“执行k”C.应尽量使“分析k+1”与“执行k”时间相等D.只需要一套指令分析部件和执行部件3、输入输出系统硬件的功能对（）是透明的。

A.操作系统程序员B.应用程序员C.系统结构设计人员D.机器语言程序设计员4、在尾数下溢处理方法中，平均误差最大的是（）A.截断法C.恒置"1"法D.ROM查表法5、非线性流水线是指( )A.一次运算中使用流水线中的多个功能段B.一次运算中要多次使用流水线中的某些功能段C.流水线中某些功能段在各次运算中的作用不同D.流水线的各个功能段在各种运算中有不同的组合6、“启动I/O”指令是主要的输入输出指令，是属于（）。

A.目态指令B.管态指令C.目态、管态都能用的指令D.编译程序只能用的指令7、在多用户机器上，应用程序员不能使用的指令是（）A.“执行”指令B.“访管”指令C.“启动IO”指令D“测试与置定”指令8、开发并行的途径有（），资源重复和资源共享。

A.多计算机系统C.分布式处理系统D.时间重叠9、微指令由（）直接执行。

A.微指令程序B.硬件C.汇编程序D.编译程序10、多处理机的各自独立型操作系统（）。

A.要求管理程序不必是可再入的B.适合于紧耦合多处理机C.工作负荷较平衡D.有较高的可靠性二、填空题11、流水线消除速度瓶颈的方法有________和瓶颈子过程多套并联两种。

12、段式存储管理是指________，为此每道程序在系统中都有一个________13、程序在空间上的局部性主要是因为程序通常是________地存储和执行，数据通常是外地存贮。

14、目前已有的向量处理机结构主要采用________和________两种结构。

离散数学考试题(后附详细答案)一、命题符号化(共6小题，每小题3分，共计18分)1. 用命题逻辑把下列命题符号化a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。

b) 我今天进城，除非下雨。

c) 仅当你走，我将留下。

2. 用谓词逻辑把下列命题符号化a) 有些实数不是有理数b) 对于所有非零实数x,总存在y使得xy=1。

c) f是从A到B的函数当且仅当对于每个a€ A存在唯一的b € B ,使得f(a)=b.二、简答题(共6道题，共32分)1. 求命题公式(P T(Q T R)).r(R T(Q T P))的主析取范式、主合取范式，并写出所有成真赋值。

(5分)2. 设个体域为{1,2,3}，求下列命题的真值(4分)a) -x y(x+y=4)b) y -x (x+y=4)3. 求-x(F(x) T G(x)) T ( xF(x) T-I X G(X))的前束范式。

(4 分)4. 判断下面命题的真假，并说明原因。

(每小题2分，共4分)a) (A _.B)—C=(A-B) (A-C)b) 若f是从集合A到集合B的入射函数，则|A| < |B|5. 设A是有穷集，|A|=5，问(每小题2分，共4分)a) A上有多少种不同的等价关系？b) 从A到A的不同双射函数有多少个？6. 设有偏序集<A, < >，其哈斯图如图1,求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)7. 已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数K IS;P(S);N,N ；P(N);R,R X R,{o,1}(写出即可)(6 分)三、证明题(共3小题，共计40分)1. 使用构造性证明，证明下面推理的有效性。

(每小题5分，共10分)a) A T (B A C),(E T—F) T—C, B T (A A ~S)二B T Eb) -x(P(x) T—Q(x)), -x(Q(x) V R(x)) , x—R(x)二x~P(x)2. 设R1是A上的等价关系，R2是B上的等价关系，A工._且B =_,关系R满足：<<X1,y1>,<X2,y2>>€ R，当且仅当< x 1, X2> € R1 且<y 1,y2> € R2。

《离散数学》试题A系别__________ 班级________ 学号（最后两位）______ 姓名_______-V单项选择题（每小题2分，共16分》1.下列命题为假命题的是（）A.如果4是偶数，那么一个公式的合取范式惟一B.如果4是偶数，那么一个公式的合取范式不惟一C.如果4是奇数，那么一个公式的合取范式惟一D.如果4是奇数，那么一个公式的合取范式不惟一2.下列是真命题的是（）A.⑷［{{“}}:B. {{O}}e 沖，沖}};C. {a}U{b}={a,b,c}；D. {0>}G {{O}} o3.设集合人={1, 2, 3}，R是A上的二元关系，下列关系R屮不是等价关系的是（）A.R:{<1, 1〉, <2, 2〉, <3, 3〉}B.R={<1, 1>, <2, 2>, <3, 3>, <3, 2>, <2, 3>}C.R={<1, 1>, <2, 2>, <3, 3>, <1,2>}D.R={<1, 1>, <2, 2>, <3, 3>, <1, 2>, <2, 1>, <1, 3>, <3, 1>, <2, 3>〈3,2〉}4。

设八={1, 2, 3},则A上所有的二元关系共有（）个。

A. 23；B. 32；C. 23X3；D. 3么2。

5.设R, S是集合A上的关系，则下列说法正确的是（）A.若R，S是自反的，则是自反的；B.若R, S是反自反的，则是反自反的；C.若R, S是对称的，则是对称的；D.若R，S是传递的，则/?。

5是传递的。

6.设Z是整数集合，函数/定义为：Z^Z,/（x） =|x|-2%,则/是（）的.A.双射B.满射C.单射D.非单射也非满射7.设Z）=〈V,£〉为有向图，其中V = ｛a，b，c，d，e，f｝，E =｛〈a，6〉，〈Z?，c〉，〈a，6/〉，〈t/，e〉，〈/＞〉｝，则该有向图是（）.八.强连通图 B.单向连通但非强连通图C.弱连通图但非单向连通图D.不连通图8.设G是有5个顶点的无向完全图，则0是（）A.没有哈密尔顿通路B.没有欧拉回路C.是欧拉图D.是平面图二、填空题（每空2分，共24分》1.设G（x）:x是人，F（x）: x喜欢读书，则命题“不是所有的人都喜欢读书”可符号化为 _______________________ 。

南昌大学考试试卷A【适用时间：20 11 ～20 12学年第学期试卷类型[A]卷】一、单项选择题：（每小题2分，共 30 分）1、以下叙述中正确的是( )。

A.在对一个C++程序进行编译的过程中，可发现注释中的拼写错误B.在C++程序中，main函数必须位于程序的最前面C. C++本身没有输入输出语句D. C++程序的每一行只能写一条语句2、以下叙述中不正确的是( )。

A.在C++程序中，逗号运算符的优先级最低B.在定义变量时，必须给变量赋初值C.在C++程序中，count和Count是两个不同的变量D.表达式1/3+1/3+1/3的结果为03、用C++语言编写的代码程序( )。

A.可以执行B.经过编译解释才能执行C.经过编译可执行D.是一个源程序4、以下关于函数参数的叙述不正确的是( )。

A.实参只能是常数B.函数的形参命名可以任意，只要符合标识符规则C.形参的值与实参的值不一定时刻保持一致D.函数参数的值可以是内存单元地址5、设”int a=12;”，则执行完语句”a+=a-=a*a;”后，a的值是( )。

A.-132B.144C.-264D.2886、以下函数的功能是( )。

int function(char *x){ char *p=x; while(*p++); return(p-x-1); }A. 求字符串的长度B. 将字符串x连接到字符串p后面C. 将字符串x复制到字符串p中D. 将字符串x反向存放7、已知教师记录的描述为:struct teacher{int id;char name[20];struct{int y:int m:int d:}birth;}t;将变量t中的d成员赋值为12的语句为（）。

A.d=12B.birth.d=12C.t.d=12D.t.birth.d=128、在以下选项中，与k=n++完全等价的表达式是( )。

A. k=n,n=n+1B. n=n+1,k=nC. k=++nD. k+=n+19、已定义int a,b;下列switch语句中格式正确的是( )。

北京工业大学经管学院期末试卷《离散数学》（A）学号姓名：成绩一、单项选择题（每题2分，共18分）1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不．滑”可符号化为（D）A ．P→Q B．P ∨QC．P∧Q D．P ∧Qp→q，蕴涵式，表示假设、条件、“如果，就”。

“→”与此题无关2. 关于命题变元P和Q的极大项M1表示( C )。

书P15-P19，此题换作p、q更容易理解A.┐P∧QB.┐P∨Q p∨┐q ---- 01---- 1 ----- M1C.P∨┐QD.P∧┐Q3.设R（x）：x是实数；S（x,y）：x小于y。

用谓词表达下述命题：不存在最小的实数。

其中错误的表达式是：（D）4.在论域D={a,b}中与公式（x∃）A（x）等价的不含存在量词的公式是（B）A.)b(AA∨)a(A)a(A∧ B. )b(C. )b()b(A→A→ D. )a(A)a(A5．下列命题公式为重言式的是（C）A．Q→（P∧Q）B．P→（P∧Q）C．（P∧Q）→P D．（P∨Q）→Q牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。

熟练的可直接看出C不存在1→0的情况6. 设A=｛1，2，3｝，B=｛a,b｝，下列二元关系R为A到B的函数的是( A )A. R=｛<1,a>,<2,a>,<3,a>｝B. R=｛<1,a>,<2,b>｝C. R=｛<1,a>,<1,b>,<2,a>,<3,a>｝D. R=｛<1,b>,<2,a>,<3,b>,<1,a>｝-第1页-第 2页7.偏序关系具有性质（ D ） 背A.自反、对称、传递B.自反、反对称C.反自反、对称、传递D.自反、反对称、传递8.设R 为实数集合，映射:,R R σ→2()21,x x x σ=-+-则σ 是( D ).(A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射.书P96.设函数f ：A→B（1）若ranf=B ，则f 是满射的【即值域为B 的全集，在本题中为R ，该二次函数有最高点，不满足】（2）若对于任何的x 1,x 2∈A , x 1≠x 2,都有f(x 1)≠f(x 2)，则称f 是单射的【即x,y 真正一一对应，甚至不存在一个y 对应多个x 。

离散考试题与答案一、选择题1. 下列哪个不是离散数学的基本概念？A. 集合B. 二进制C. 图论D. 函数答案：C2. 设A = {1, 2, 3, 4}，B = {3, 4, 5, 6}，则A ∩ B = ?A. {1, 2}B. {3, 4}C. {5, 6}D. {3, 4, 5, 6}答案：B3. 在一个完全图中，有多少条边？A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B4. 若f(x) = x^2 + 3x，则f(-2)的值为？A. -4B. -2C. 0D. 2答案：C5. 若A = {a, b, c}，B = {b, c, d}，则A - B = ?A. {a, b, c}B. {b, c, d}C. {a, d}D. {}答案：A二、填空题1. 设f(x) = x^2 + 5，求f(-3)的值。

答案：162. 设A = {1, 2, 3}，B = {3, 4, 5}，则A ∪ B = ？答案：{1, 2, 3, 4, 5}3. 在一个有向图中，若存在一条从顶点A到顶点B的路径，并且从B到A也存在一条路径，则该图称为_____图。

答案：强连通图4. 二进制数11111111转换为十进制的结果为______。

答案：2555. 若给定集合A = {1, 2, 3, 4}，则集合A的所有子集的个数为______。

答案：16三、简答题1. 解释集合的并、交和差的运算。

答案：集合的并运算指的是将两个集合中的所有元素合并成一个新的集合，新集合中的元素包括原来两个集合中的所有元素，但不重复。

集合的交运算指的是求出两个集合中共有的元素，构成一个新的集合。

集合的差运算指的是在一个集合中去除另一个集合中的元素，得到一个新的集合。

2. 什么是图论？答案：图论是研究图及其在各个领域中的应用问题的一门学科。

图由若干个顶点及连接这些顶点的边构成，图论主要研究图的性质、结构和算法问题。

3. 什么是函数？答案：函数是一种将每个输入值唯一对应到输出值的关系。

—南昌大学考试试卷—【适用时间：20 16 ～20 17 学年第一学期试卷类型：[ A ]卷】一、填空题：（每空 2分，共 20 分）得 分评阅人1、使得公式q ∧(p →q )→p 成假的赋值是： 。

2、公式)),(()),()((y z R z y x Q x P x ∀→∧∃的约束变元为________，自由变元为_______。

3、设A={4,2,l}，B={5,l,3}，则B-A=________，B ⊕A=_______。

4、设A =⎨1,2,3,4⎬，A 上二元关系R 定义为：R =⎨<1,2>,<2,1>,<2,3>,<3,4>⎬ s(R )= 。

5、设A={2,3,4,5}，a * b =max(a , b )。

代数系统<A ，*>的幺元是 ，零元是 。

6、设无向树T 有3个度数为3的结点，其余结点都为树叶，则T 的结点数为________。

7、若一条路中，所有的__ __均不相同，称为迹。

二、选择题：（每题 3分，共 15 分）得 分评阅人1．下列句子不是．．命题的是（ ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的D ．太好了！2．设p ：天下雨；q ：我走路上学。

命题“只要不下雨，我就走路上学”可符号化为（ ） A ．p → q B ．q →pC ．┐p → qD ．q → ┐p3．下列关系矩阵所对应的关系具有反对称性的是（ ）A ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001110101B ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101110001C ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001100100D ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0010101014.﹤A ，≤﹥是一个偏序集，其中A 是正整数l2的正因子的集合，≤为整除关系，元素6能盖住元素（ ）A ．1B ．3C ．6D ．12 5．下列图是欧拉图的是（ ）三、综合题：（每题9分，共45分）得 分 评阅人。

离散数学考试试题(A 卷及答案)一、 (10 分)判断下列公式的类型(永真式、永假式、可满足式)？1)((P Q)∧Q)一 ((Q∨R)∧Q) 2)((Q P)∨P)∧ (P∨R)3)((P∨Q)R)((P∧Q)∨R)解： 1)永真式； 2) 永假式； 3)可满足式。

二、 (8 分) 个体域为{1， 2}，求x3y (x+y=4)的真值。

解：x3y (x+y=4) 一 x ((x+1=4)∨(x+2=4))一((1+1=4)∨(1+2=4))∧((2+1=4)∨(2+1=4))一(0∨0)∧(0∨1)一1∧1一0三、 (8 分) 已知集合 A 和 B 且|A|=n， |B|=m，求 A 到 B 的二元关系数是多少？ A 到 B 的函数数是多少？解：因为|P(A×B) |=2|A×B|=2|A| |B|=2mn，所以 A 到 B 的二元关系有 2mn 个。

因为|BA|= |B| |A|=mn，所以 A 到 B 的函数 mn 个。

四、 (10 分) 已知 A={1,2,3,4,5}和 R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求 r(R) 、s(R)和 t(R)。

解： r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>}t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}五、 (10 分) 75 个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20 人这三种东西都乘过，其中 55 人至少乘坐过其中的两种。