MOOC 离散数学概论(北京大学)1002525004 最新慕课完整章节测试答案

单元10测验

1、单选题：

‌设是代数系统，*是X上的二元运算，R是X上的等价关系。若当且时，有，则称R是X上关于*的同余关系，称R产生的等价类是关于*的同余类。考察代数系统，是整数集合，是整数加法。问以下的二元关系是上的关于的同余关系个数是？

‍

‌

‍

‌a)

‍

‌

‍

‌b)

‍

‌

‍

‌c)

‍

‌

‍

‌d)

‍

‌

‍选项：
A: 0
B: 1
C: 2
D: 3
答案: 【 0】

2、多选题：
‎设I为整数集合。选出下列是I上的二元运算的二元关系‏
选项：
A:
B:
C:
D:
E:
F:
G:
H:
I:
答案: 【 ;
;
;
;
;
;
】

3、多选题：
‌下面说法不正确的有‎‌‎
选项：
A: 代数结构的幺元和逆元一定不同
B: 所有代数结构的幺元都有逆元
C: （Q*代表正有理数，代表数乘）构成阿贝尔群
D: （Q代表有理数，代表数乘）构成群
答案: 【 代数结构的幺元和逆元一定不同;
（Q代表有理数，代表数乘）构成群】

4、多选题：

​有限集合A上二元关系全体及关系合成运算组成代数结构，以下关于该结构说法正确的有

‏选项：
A: 既满足交换律又满足结合律
B: 其零元为空关系
C: 其幺元是相等关系
D: 只满足结合律不满足交换律
E: 零元为相等关系
F: 幺元为空关系
G: 每个定义域为A的关系都有逆元
答案: 【 其零元为空关系;
其幺元是相等关系;
只满足结合律不满足交换律;
每个定义域为A的关系都有逆元】

5、多选题：
‎以下说法错误的有​
选项：
A: 所有的群都有零元和幺元
B: 若代数结构上*运算满足结合律，那么其任一可约元素必有逆元
C: 运算满足结合律的代数结构中，任一元素的逆元（如果存在）唯一
D: 对数的普通乘法构成半群
答案: 【 所有的群都有零元和幺元;
若代数结构上*运算满足结合律，那么其任一可约元素必有逆元】

6、填空题：

‌设，A上的二元运算*定义为：，则在代数结构中，幺元是( )，零元是( )。(注：答案之间用英文逗号,分开)

‌答案: 【 2,6】

7、填空题：

‏设，A上的二元运算*定义为：，则在代数结构中，幺元是( )，零元是( )；(注：答案之间用英文逗号,分开)

‍答案: 【 9,3】

8、填空题：

‌设是代数系统，*是X上的二元运算。。问*是否满足结合律，是否满足交换律，是否有幺元，是否有零元，每个元素是否有逆元。

​

‌

​

‌只回答是否，5个判断中间用“/”隔开

​

‌

​答案: 【 是/否/否/否/否】

9、填空题：

​设是代数系统，*是X上的二元运算，e是关于*的幺元。对于X中的元素x，若存在，使得，则称y是x的左逆元。若存在，使得，则称z是x的右逆元。指出下表中各元素的左、右逆元的情况。表格（取变量方法是先纵后横）幺元是____，有两个左逆元和两个右逆元的是____，没有左逆元的是____(注：答案之间用英文逗号,分开)

​

​

​答案: 【 a,c,e】

10、填空题：

‎设是补运算。问X和Y是否同构，如果是，回答是；如果否，则因为__结构的__运算不符合相关要求

‍

‎

‍

‎填字母、汉字(注：答案之间用英文逗号,分开，并且注意大小写)

‍答案: 【 否,Y,补##%_YZPRLFH_%##否,Y,'】

单元11测验

1、单选题：

‌设一个短语结构语法是G=({A}，{a}，{A→a|aA}，A)，那么下面不是它产生的语句个数是

​

‌

​

‌(1)aaaaaaaaaa (2)aaaaaaAaaa (3)AaAaaAaAA (4)aaAaaAaaa

​

‌

​

‌本次测验采用的语法定义如图其他题目相同

​

‌

​选项：
A: 3
B: 1
C: 2
D: 4
答案: 【 3】

2、单选题：
​对下面文法的生成式，找出其正则式​​​​G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：​​​​S→aA S→B​​​​A→abS A→bB​​​​B→b B→cC​​​​C→D D→bB​​​​D→d​​​
选项：
A: (aab)*(ab|ε)(cb)*(cd|b)
B: (aab)*(ab|ε)*(cb)*(cd|b)
C: (aab)*(ab|ε)(cb)(cd|b)
D: (aab)*(ab|ε)(cb)*(cd|b)*
答案: 【 (aab)*(ab|ε)(cb)*(cd|b)】

3、单选题：
‎对下面文法的生成式，找出其正则式‏‎‏‎G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：‏‎‏‎S→aA S→B‏‎‏‎A→cC A→bB‏‎‏‎B→bB B→a‏‎‏‎C→D C→abB‏‎‏‎D→d‏‎‏
选项：
A: ab+a|acd|acab+a|b*a
B: ab*a|acd|acab+a|b*a
C: ab*a|acd|acab*a|b*a
D: ab+a|acd|acab+a|b+a
答案: 【 ab+a|acd|acab+a|b*a】

4、单选题：
设文法G有如下产生式 S→aB│bA；‏A→a│aS│bAA；‏B→b│bS│aBB；则L(G)的内容是____‏​‏
选项：
A: L(G)＝{ω│ω中含有相同个数的a和b，且ω非空}。
B: L = {anbmam|n,m≥1}
C: L = {anbnan|n≥1}
D: 其他选项皆不正确
答案: 【 L(G)＝{ω│ω中含有相同个数的a和b，且ω非空}。】

5、单选题：
对下面文法，他的产生语言是G = ({S, A, B, C}, { a, b, c}, P, S)‌其中P:{S→aBC | aSBC，‌CB→BC ，‌aB→ab，‌bB→bb，‌bC→bc，‌cC→cc‌}‌‏‌
选项：
A: L = {anbncn | n≥1}
B: L = {anbmcm|n,m≥1}
C: L = {anbmck|n,m,k≥1}
D: 其他选项皆不正确
答案: 【 L = {anbncn | n≥1}】

6、单选题：
‎对下面文法G=（{S, A}，{a, b}，{S→ABA, A→Aa|a, B→bB|b}，S），产生的语言是‍
选项：
A: L = {anbmak|n,m,k≥1}
B: L = {anbmam|n,m≥1}
C: L = {anbnan|n≥1}
D: 其他选项皆不正确
答案: 【 L = {anbmak|n,m,k≥1}】

7、单选题：

‌以下哪一个是正则集对应的文法？

​选项：
A: ,
B:
C:
D:
答案: 【 ,】

8、单选题：

‏设,则所有以11开头，以11结尾的字符串构成的集合对应文法

‎选项：
A:
B:
C:
D:
答案: 【 】

9、单选题：

‎以下文法对应的语言是（以下出现的n均为整数）

‍选项：
A:
B:
C:
D:
答案: 【 】

10、多选题：

‎以下文法,能产生的字符串有

‎选项：
A: ddcc
B: aaaabbbddcc
C: d
D: ccc
答案: 【 ddcc;
aaaabbbddcc;
d】

单元12测验

1、单选题：
利用泵引理，判断下列属于正则语言的个数是_____​{0n1n|n≥1}​{0n|n为素数}​{0n1m2m+n|m,n≥1}​‍​
选项：
A: 0
B: 1
C: 2
D: 无法确定
答案: 【 0】

2、单选题：

考虑两个机器如图，给出它们的形式描述分别是（从左到右）___________

‌

‌

‏

‌

‏

‌选项：
A: [01+(00+1)(11+0)][11+(10+0)(11+0)]*(01+1+000){(01)*+(10)*+[(001+11)(01+1+000)]*}
B: (01+1+000){(01)*+(10)*+[(001+11)(01+1+000)]*}[01+(00+1)(11+0)][11+(10+0)(11+0)]*
C: [11+(10+0)(11+0)]*{(01)*+[(001+11)(01+1+000)]*}
D: 其余答案皆不正确
答案: 【 (01+1+000){(01)*+(10)*+[(001+11)(01+1+000)]*}[01+(00+1)(11+0)][11+(10+0)(11+0)]*】

3、单选题：

如下状态图，关于他的语法含义正确的是____

‏

‏

‎

‏

PS：这类题目真正掌握应该是给定语法，自行设计状态图

‏选项：
A: {x|x∈{0，1}+且x的第十个字符为1}
B: {x|x∈{0，1}+且x的第十个字符为0}
C: 只有第九、十字符分别为1，0 时才进入陷阱状态
D: 毫无陷阱状态，因为陷阱也要按照基本法则
答案: 【 {x|x∈{0，1}+且x的第十个字符为1}】

4、单选题：

如下状态图，关于他的语法含义正确的是____

​

​

‎

​

PS：这类题目真正掌握应该是给定语法，自行设计状态图

​选项：
A: {x|x∈{0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}
B: {x|x∈{0，1}*且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}
C: {x|x∈{0，1}+且如果x以0结尾，则它的长度为偶数；如果x以1结尾，则它的长度为奇数}
D: {x|x∈{0，1}*且如果x以0结尾，则它的长度为偶数；如果x以1结尾，则它的长度为奇数}
答案: 【 {x|x∈{0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}】

5、单选题：

识别状态图的语言，正确的是____

‏

‏

‌

‏

PS：这是不确定的有穷状态自动机(non-deterministic finite automaton ,NFA)，稍微区别于确定的有穷状态自动机(deterministic finite automaton，DFA) ，但都是有穷状态自动机(finite automaton,FA)

‏

‌

‏选项：
A: {x|x∈{0, 1}+且x的首尾字符相等}
B: {x|x∈{0, 1}*且x的首尾字符相等}
C: {x|x∈{0, 1}+且x的首尾字符不相等}
D: {x|x∈{0, 1}*且x的首尾字符不相等}
答案: 【 {x|x∈{0, 1}+且x的首尾字符相等}】

6、多选题：
‏以下哪些是正则集？‍
选项：
A: 含有偶数个a和奇数个b的{a,b}*上的字符串集合
B: 含子串aba的{a,b}*上的字符串集合
C:
D:
答案: 【 含有偶数个a和奇数个b的{a,b}*上的字符串集合;
含子串aba的{a,b}*上的字符串集合】

7、多选题：

下图能识别的字符串有

​

​选项：
A: 010101
B: 0111000100
C: 000110101000
D: 01000100010001010
E: 0001110000111000111
答案: 【 010101;
000110101000;
01000100010001010】

8、多选题：

‍

关于上图的说法正确的有

‍选项：
A: 它能识别001100111001
B: 它不能识别101001011000101
C: 这是一个非确定有限自动机
D: 该机器能识别的字符串如果将其倒转过来并视为二进制数，则该数必能被3整除
答案: 【 它能识别001100111001;
该机器能识别的字符串如果将其倒转过来并视为二进制数，则该数必能被3整除】

9、判断题：
‍{0，1}上所有回文串构成的集合是正则的​
选项：
A: 正确
B: 错误
答案: 【 错误】

10、判断题：

‍集合和都不是正则的

​选项：
A: 正确
B: 错误
答案: 【 正确】

单元13测试

1、单选题：
关于“图灵机”，下列说法不正确的个数是_____‍图灵机给出的是计算机的理论模型；‍图灵机的状态转移函数q, X, Y, R(或L或N), p，其实就是一条指令，即在q状态下，当输入为X时，输出为Y，读写头向右(R)、向左(L)移动一格或不动(N)，状态变为p；‍图灵机是一种离散的、有穷的、构造性的问题求解思路；‍凡是能用算法方法解决的问题也一定能用图灵机解决；凡是图灵机解决不了的问题算法也解决不了；‍​‍
选项：
A: 0
B: 1
C: 2
D: 3
答案: 【 0】

2、单选题：

下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5}，其中S1为起始状态，S5为终止状态；箭头表示状态转换，其上标注的如in, out, direction表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

‌

该图灵机的功能是_____。 

‌

‌

‍

‌选项：
A: 将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式。
B: 将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同， 转换为XYXY， XYXYXYXY的形式。
C: 识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串。
D: 识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同。
答案: 【 将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式。】

3、单选题：

下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5，S6}，其中S1为起始状态，S6为终止状态；箭头表示状态转换，其上标注的如in, out, direction表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

‎

该图灵机的功能是_____。

‎

‎选项：
A: 识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串。
B: 识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同。
C: 将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同， 转换为XYXY， XYXYXYXY的形式。
D: 将形如0