MOOC数据结构与算法Python版-第⼀周测验
1 以下关于基于有穷观点的能⾏⽅法说法错误的是：B
A.指令执⾏在有限步骤后终⽌
B.由有限数量的任意指令构成
C.指令每次执⾏都得到唯⼀的结果
D.原则上可以由⼈单独采⽤纸笔完成
不是任意指令，是由有限数量的明确有限指令组成。
2 以下关于ADT抽象数据类型说法错误的是：D
A.ADT建⽴的封装技术将可能的处理实现细节隐蔽起来。
B.采⽤程序设计语⾔的控制结构和基本数据类型来实现ADT的所提供的逻辑接⼝。
C.ADT是对数据进⾏处理的⼀种逻辑描述。
D.同⼀ADT只有唯⼀的数据结构可以实现。
同⼀ADT可以采⽤不同的数据结构来实现。
3 关于“图灵机”，下列说法不正确的个数为：A
1）图灵机给出的是计算机的理论模型；
2）图灵机的状态转移函数q, X, Y, R(或L或N), p，其实就是⼀条指令，即在q状态下，当输⼊为X时，输出为Y，读写头向右(R)、向左(L)移动⼀格或不动(N)，状态变为p；
3）图灵机是⼀种离散的、有穷的、构造性的问题求解思路；
netstat 和ps4）凡是能⽤算法⽅法解决的问题也⼀定能⽤图灵机解决，凡是图灵机解决不了的问题算法也解决不了。
A.0
B.3
C.2
D.1
20世纪30年代，图灵提出了图灵机模型，建⽴了指令、程序及通⽤机器执⾏程序的理论模型，奠定了计算理论的基础，因此(1)正确；选项(2)是图灵机的五元组形式的指令集，是⼀个⾏动集合，⼜称状态转移函数，因此正确；图灵机是⼀种离散的、有穷的、构造性的问题求解思路，⼀个问题的求解可以通过构造其图灵机（即算法和程序）来解决，因此(3)正确；(4)为图灵可计算性问题，正确。所以没有错误的。
4 下图为⽤状态转换图⽰意的⼀个图灵机，其字母集合为{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手机一键变电脑
A.将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的
形式。
B.识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串。
C.识别是否如0101，01010101的0、1串，即⼀个0接续⼀个1，且0的个数和1的个数相同。模板背景图
D.将形如0101，01010101的0、1串，即⼀个0接续⼀个1，且0的个数和1的个数相同， 转换为XYXY， XYXYXYXY的形式。
根据本题中的描述及状态转移图，可以看到该图灵机是将⼀个0、1串中的0转换成X，1转换成Y。接着，具体来看S1、S2、S3的转移，⼀个串从S1开始，当遇到第⼀个0，将0转换成X，然后向右移⼀位，进⼊状态S2，该状态检测下⼀位是否为1，当不是的话，什么都不做，直接向右移⼀位，知道遇到第⼀个1，遇到以后，将1转换成Y，向左移动，进⼊到状态S3，该状态回溯0、1串，直到遇到X，然后指向在其右侧的符号，返回到S1状态。这个过程即为⼀个左侧连续0的个数和右侧连续1的个数相同的0、1串，每次都寻排在最前⾯的⼀个0和⼀个1，将它们分别转换成X，Y，直到所有的0和1转换为X和Y。因此，答案(D)正确。
5 下图为⽤状态转换图⽰意的⼀个图灵机，其字母集合为{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(停留在原处)。
该图灵机能实现的功能是：D
A.识别是否如0101，01010101的0、1串，即⼀个0接续⼀个1，且0的个数和1的个数相同。
B.将形如0101，01010101的0、1串，即⼀个0接续⼀个1，且0的个数和1的个数相同， 转换为XYXY， XYXYXYXY的形式。
exposed thermal padC.将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的
形式。
D.识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串。
该图灵机由上题衍⽣出来，即类似(A)(C)中的间隔字符串⽆法通过S4，⽽类似(B)(D)中的字符串可以运⾏⾄S4将0、1串变更为X、Y串，但在S5状态中图灵机⼜将X、Y串变回0、1串，因此该图灵机不是⽤来转换字串的，该图灵机是⽤来检验字串的，因此(B)正确。
6 ⼀个图灵机应该由以下哪些部分组成？ABD
A.⽆限长的分格纸带
B.读写头
C.字符
D.状态寄存器
逻辑结构上图灵机有四个部分组成
1. ⼀个⽆限长的存储带，带⼦有⼀个个连续的存储格⼦组成，每个格⼦可以存储⼀个数字或符号
2. ⼀个读写头，读写头可以在存储带上左右移动，并可以读、修改存储格上的数字或符号
3. 内部状态存储器，该存储器可以记录图灵机的当前状态，并且有⼀种特殊状态为停机状态
4. 控制程序指令，指令可以根据当前状态以及当前读写头所指的格⼦上的符号来确定读写头下⼀步的动作（左移还是右移），并改变状
态存储器的值，令机器进⼊⼀个新的状态或保持状态不变。
7⼀般来说我们可以把⽣活中常见的问题分为哪⼏类？ABD
A.证明问题
B.过程问题
C.计算问题
D.分类问题
问题的分类：
What 是什么？ ⾯向判断与分类的问题
Why 为什么？ ⾯向求因与证明的问题
python3基础教程慕课版电子版How 怎么做？ ⾯向过程与构建的问题
8以下哪些⽅法不是以算法的概念来解决问题？AC
A.星象占⼘
B.DNA计算
C.智慧众包
D.光⼦计算
星象占⼘显然不是，智慧众包是靠具有智慧和直觉的众多的⼈脑⼀起来解决问题，所以这两个不是以算法的概念来解决问题。
zorin系统
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论