数据结构课件第2章 线性表.ppt
《数据结构课件第2章 线性表.ppt》由会员分享,可在线阅读,更多相关《数据结构课件第2章 线性表.ppt(89页珍藏版)》请在文库网上搜索。
1、7、 设S=1,2,3,R为S上的关系,其关系图为 则R具有( )的性质。A、 自反、对称、传递; B、什么性质也没有;C、反自反、反对称、传递; D、自反、对称、反对称、传递。8、 设,则有( )。A、1,2 ;B、1,2 ; C、1 ; D、2 。9、 设A=1 ,2 ,3 ,则A上有( )个二元关系。A、23 ; B、32 ; C、; D、。10、全体小项合取式为( )。A、可满足式; B、矛盾式; C、永真式; D、A,B,C 都有可能。三、 用CP规则证明 16% (每小题 8分)1、2、四、(14%) 集合X=, , , ,R=,|x1+y2 = x2+y1 。1、 证明R是X上的
2、等价关系。 (10分)2、 求出X关于R的商集。(4分)五、(10%)设集合A= a ,b , c , d 上关系R= , , , 要求 1、写出R的关系矩阵和关系图。(4分) 2、用矩阵运算求出R的传递闭包。(6分)六、(20%)1、(10分)设f和g是函数,证明也是函数。2、(10分)设函数,证明 有一左逆函数当且仅当f是入射函数。答案:五、 填空 20%(每空2分)1、2(x+1);2、;3、;4、反对称性、反自反性;4、;5、1;6、;7、任意x,如果x是素数则存在一个y,y是奇数且y整除x ;8、。六、 选择 20%(每小题 2分)题目12345678910答案CCCCABDADC七
3、、 证明 16%(每小题8分)1、P(附加前提)TIPTITITIPTICP2、 P(附加前提)TEESPUSTIEGCP八、 14%(1) 证明:1、 自反性: 2、 对称性: 3、 传递性:即由(1)(2)(3)知:R是X上的先等价关系。2、X/R=九、 10%1、; 关系图2、 t (R)= , , , , , , , , 。 六、 20%1、(1)(2)。2、证明:。试卷四试题与答案一、 填空 10% (每小题 2分)1、 若P,Q,为二命题,真值为0 当且仅当 。2、 命题“对于任意给定的正实数,都存在比它大的实数”令F(x):x为实数,则命题的逻辑谓词公式为 。3、 谓词合式公式的
4、前束范式为 。4、 将量词辖域中出现的 和指导变元交换为另一变元符号,公式其余的部分不变,这种方法称为换名规则。5、 设x是谓词合式公式A的一个客体变元,A的论域为D,A(x)关于y是自由的,则 被称为存在量词消去规则,记为ES。二、 选择 25% (每小题 2.5分)1、 下列语句是命题的有( )。A、 明年中秋节的晚上是晴天; B、;C、当且仅当x和y都大于0; D、我正在说谎。2、 下列各命题中真值为真的命题有( )。A、 2+2=4当且仅当3是奇数;B、2+2=4当且仅当3不是奇数;C、2+24当且仅当3是奇数; D、2+24当且仅当3不是奇数;3、 下列符号串是合式公式的有( )A、
5、;B、;C、;D、。4、 下列等价式成立的有( )。A、;B、;C、 ; D、。5、 若和B为wff,且则( )。A、称为B的前件; B、称B为的有效结论C、当且仅当;D、当且仅当。6、 A,B为二合式公式,且,则( )。A、为重言式; B、;C、; D、; E、为重言式。7、 “人总是要死的”谓词公式表示为( )。(论域为全总个体域)M(x):x是人;Mortal(x):x是要死的。A、; B、C、;D、8、 公式的解释I为:个体域D=2,P(x):x3, Q(x):x=4则A的真值为( )。A、1; B、0; C、可满足式; D、无法判定。9、 下列等价关系正确的是( )。A、;B、;C、
6、;D、。10、 下列推理步骤错在( )。PUSPESTIEGA、;B、;C、;D、三、 逻辑判断30% 1、 用等值演算法和真值表法判断公式的类型。(10分)2、 下列问题,若成立请证明,若不成立请举出反例:(10分)(1) 已知,问成立吗?(2) 已知,问成立吗?3、 如果厂方拒绝增加工资,那么罢工就不会停止,除非罢工超过一年并且工厂撤换了厂长。问:若厂方拒绝增加工资,面罢工刚开始,罢工是否能够停止。(10分)四、计算10%1、 设命题A1,A2的真值为1,A3,A4真值为0,求命题的真值。(5分)2、 利用主析取范式,求公式的类型。(5分)五、谓词逻辑推理 15%符号化语句:“有些人喜欢所
7、有的花,但是人们不喜欢杂草,那么花不是杂草”。并推证其结论。六、证明:(10%)设论域D=a , b , c,求证:。答案:十、 填空 10%(每小题2分)1、P真值为1,Q的真值为0;2、;3、;4、约束变元;5、,y为D的某些元素。十一、 选择 25%(每小题2.5分)题目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)十二、 逻辑判断 30%1、(1)等值演算法(2)真值表法P QA1 1111111 0010010 1100010 011111所以A为重言式。2、(1)不成立。若取但A与B不一定等价,可为任意不等价的公式。(2)成立。 证明:即:所
8、以故 。3、解:设P:厂方拒绝增加工资;Q:罢工停止;R罢工超壶过一年;R:撤换厂长前提: 结论:PPTIPTITETI罢工不会停止是有效结论。四、计算 10%(1) 解:(2)它无成真赋值,所以为矛盾式。五、谓词逻辑推理 15%解: 证明:PESTITIPUSTITEUSUSTIUG十三、 证明10% +3x/2+3.4. 设I是如下一个解释:D = 2, 3, abf (2)f (3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011试求 (1) P(a, f (a)P(b, f (b);(2) x$y P (y, x). 解: (1) P(a, f (a)P(b,
9、f (b) = P(3, f (3)P(2, f (2)= P(3, 2)P(2, 3)= 10= 0.(2) x$y P (y, x) = x (P (2, x)P (3, x) = (P (2, 2)P (3, 2)(P (2, 3)P (3, 3)= (01)(01)= 11= 1.5. 设集合A1, 2, 4, 6, 8, 12,R为A上整除关系。(1) 画出半序集(A,R)的哈斯图;(2) 写出A的最大元,最小元,极大元,极小元;(3) 写出A的子集B = 4, 6, 8, 12的上界,下界,最小上界,最大下界.解:(1) (2)无最大元,最小元1,极大元8, 12; 极小元是1.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构课件 第2章 线性表 数据结构 课件 线性