MOOC 离散数学概论(北京大学)1002525004 最新慕课完整章节测试答案
10 抽象代数
文章目录
单元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 形式语言与自动机基本概念
单元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→BA→abS A→bBB→b B→cCC→D D→bBD→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→BA→cC A→bBB→bB B→aC→D C→abBD→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 形式语言与自动机-有限状态机
单元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 形式语言与自动机-图灵机与计算理论
单元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