计算思维的结构-桂林电子科技大学中国大学mooc课后章节答案期末考试题库2023年

计算思维的结构_桂林电子科技大学中国大学mooc课后章节答案期末考试题库2023年抽象（Abstraction）与自动化（Automation）是计算思维的本质特征，在计算学科各领域中均存在为数不少的抽象工具。E-R图（实体-联系图）就是其中一种对客观世界进行抽象的工具，使用该工具可以大大降低软件系统研制，特别是数据库应用系统研制的复杂性。一个公司有一个销售部门，一个销售部门有若干员工，每位员工都可以销售若干商品，每个商品都可以由若干员工销售，一个商品可以存放在若干不同的仓库中，一个仓库可以存放不同的商品，一个员工可以管理若干仓库，该单位销售部的E-R图（提示：销售时有一个“销售明细”属性；存放时有一个“存放与出库时间”的属性）如下所示，图中空白填写顺序应为（）【图片】

参考答案:

销售明细

存放与出库时间

销售部门

Vcomputer机器指令由4位十六进制数构成（1位操作码，3位操作数），其机器指令集如下表1所示。现有一段内存地址为80~8B的Vcomputer程序，如下表2所示，若机器从内存地址80开始执行，程序的执行结果是以下选项中的哪种情况（）。【图片】【图片】

参考答案:

程序不会终止

采用蒙特卡洛（MonteCarlo）方法，计算下图所示区间内曲线【图片】下的近似面积(该区间内曲线与x轴、y轴所围成的区域的面积)，那么随机数x，y的取值范围分别为（）【图片】【图片】

参考答案:

和

下图所示是字母“啊”的16´16点阵图，其第四行的二进制编码是（）【图片】

参考答案:

1010100100000100

用“伟大的计算原理”描述计算，其好处不包括（）

参考答案:

强调使用信息，而不是创造知识

折半搜索算法也称二分查找算法，是一种在有序数据集中查找某一特定元素的搜索算法。折半搜索要求数据集中的结点按关键字值升序或降序排列。折半搜索算法的基本原理是：首先将待查值与有序数据集的中间项进行比较，以确定待查值位于有序数据集的哪一半，然后将待查值与新的有序数据集的中间项进行比较。循环进行，直到相等为止。采用折半搜索算法在一个有10000件商品（有序排列）的超市中查找一件特定的商品，最多只需要查找的次数是（）

参考答案:

14

采用蒙特卡洛（MonteCarlo）方法，计算下图所示区间内曲线【图片】下的近似面积，那么随机数x，y的取值范围分别为（）【图片】

参考答案:

和

周以真给出的计算思维的本质是（）

参考答案:

抽象、自动化

计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。设p=3,q=11,n=3×11=33，构建一个RSA公开密钥密码系统，用公钥(3,33)对m=9进行加密，得到的加密报文为（）

参考答案:

3

采用蒙特卡洛（MonteCarlo）方法，计算2≤x≤4范围内曲线【图片】与【图片】之间的近似面积（如下图阴影部分），那么随机数x，y的取值范围分别为（）【图片】

参考答案:

x∈[2,4]，y∈[-1,0]

已知数列{an}满足:【图片】，请补全横线处的程序。（）【图片】

参考答案:

coutAn(n-1,value)

根据顺序存储和链式存储各自的优势，判断以下案例应选择哪种存储方式：若想编写一个下跳棋的游戏程序，那么表示棋盘的数据结构将会是一个静态数据结构，这是因为棋盘的大小在游戏过程中不会改变，所以应该选择；而若要编写一个多米诺游戏的程序，则根据表构建的多米诺模式的数据结构将会是一个动态数据结构，这是因为这个模式的大小是可变的，而且不能预先确定，因此应该选择。（）

参考答案:

顺序存储

链式存储

下图为一个存放在Vcomputer机器连续存储单元中的一个栈，已知栈顶地址为74，栈底地址为71。那么当前执行出栈操作取出的数值是；执行一次出栈操作后栈顶地址为。（）【图片】

参考答案:

57、73

下面是采用蒙特卡罗方法编写的计算圆周率p的值的Raptor程序。根据你的理解，请补全空白处（1）的代码【图片】

参考答案:

x*x+y*y<=1

采用蒙特卡洛（MonteCarlo）方法，计算1≤x≤3范围内曲线y=1与【图片】之间的近似面积（如下图阴影部分），那么随机数x，y的取值范围分别为（）【图片】

参考答案:

[1,3],[1,3+sin3]

下列说法不正确的是（）

参考答案:

人的脑力因人而异，可以按算法中的大小O来划分成若干个数量级

阿克曼函数：【图片】求阿克曼函数的值A(0,0)=_____（）

参考答案:

1

下列有关复杂性的说法不正确的是（）

参考答案:

若两个系统各自有M个和N个可能状态，那么组合系统的复杂度为

当系统的结构不能被描述，或描述它的最小算法与系统本身具有相同的信息比特数时，则称该系统为根本复杂系统。在达到根本复杂之前，人们仍可以编写出能够执行的程序，否则，做不到。下列选项中正确的是（）

参考答案:

序列“aababbababbbabaaababbab…”是根本复杂系统_序列“aaaaaaa…”是一个亚（准）复杂性系统

背包问题就是给定n种物品和一个背包，设Wi为物品i的重量，Vi为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大。用贪婪算法解决背包问题，贪婪准则为：每次都选择Vi/Wi值（价值密度）最大的物品装包。假设n=3；W1=100，V1=50；W2=20，V2=30；W3=20，V3=40；C=110。下列说法正确的是（）

参考答案:

选物品为2和3，总价值为70

下列关于“道德选择”的说法不正确的是（）

参考答案:

道德选择可能会在使一些人受益的同时损害其他一些人的利益，但是这是利益分配中不可避免的，因此不必考虑利益问题

计算思维的结构问题涉及以下哪两个方面（）

参考答案:

计算思维不同元素之间的逻辑关系_计算思维的组成元素

2010年，在美国NSF的资助下，美国国家研究委员会（NRC）召开了一系列会议，给出了“关于计算思维的本质和适用范围的工作报告”（Reportofaworkshoponthescopeandnatureofcomputationalthinking），报告给出了“计算思维”的五个公开问题（OpenQuestions）。其中最重要的核心问题是（）

参考答案:

计算思维的结构问题

设【图片】，下面是求解e的近似值的算法伪代码，请选择正确的选项填写在空白处（）伪代码：eRes=0eCur=1k=1i=1While(abs(eRes-eCur)>=1.0E-10){eRes=eCureCur=eCur+1.0/ki=i+1}PrinteRes

参考答案:

k=k*i

下列叙述分别体现了软件开发的系统化方法需要遵循的基本原则：抽象第一的原则、层次划分的原则、模块化原则。请按下列叙述选择对应的原则（）（1）对实际的事物进行人为处理，抽取所关心的、共同的、本质特征的属性，并对这些事物及其特征属性进行描述。由于抽取的是共同的、本质特征的属性，从而大大降低了系统元素的绝对数量。（2）根据系统模型说明的原因和真实系统提供的依据，提出以模型代替真实系统进行模拟实验，达到认识真实系统特性和规律性的方法。（3）如果一个系统过于复杂，以至于很难处理，那么，就得先将它分解为若干子系统。

参考答案:

抽象第一原则、模块化原则、层次划分原则

图像的压缩有很多方法，其中一类是通过编码的方式现实的，该类方式又分为无损编码和有损编码，其中，行程编码就是一种无损压缩编码，传真机便采用了行程编码。根据行程编码规则，写下每一行开始时连续的白色像素数目，然后是连续的黑色像素数目，以此类推；若该行开头没有白色像素，则开始数字为0。下图所示是字母“a”的6´5点阵图，若对其进行“行程编码”，那么第四行的行程编码是（）【图片】

参考答案:

0,1,3,1

猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就多吃了一个。第二天又将剩下的桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半多一个。第10天只剩一个桃子，求第一天共摘下来多少个桃子？注：递推也是一种迭代，但是往往被人误以为是递归（递归是自己调用“自己”，递推不是）。下图是使用Raptor实现上述猴子吃桃问题的迭代程序（递推程序），请补全横线处的程序。()【图片】

参考答案:

a+1

下面是汉字“计”的16´16点阵图，其第3行的二进制编码为（）【图片】【图片】

参考答案:

0001000001000000

栈是计算机中一种常用的数据结构，假设有一空栈，首先数值3A入栈，然后数值2B、8C依次入栈，随后执行一次出栈操作，最后数值9D和8E依次入栈。按栈底到栈顶的存储顺序列出当前栈内所有数据应为（）

参考答案:

3A、2B、9D、8E

计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。在一个RSA公钥密码系统中，设私钥为（3，143），对加密报文17解密结果为。（）

参考答案:

51

计算机方法论中最基本的三个概念是（）

参考答案:

抽象、理论、设计

下面不属于计算思维特征的是（）

参考答案:

计算机的，不是人的思维

高级语言抽象掉了汇编语言所关心的寄存器、位、磁盘等概念，使软件开发的生产率提高了若干倍，同时，软件的可靠性、简洁性也大为提高，相对于汇编语言，高级语言有效地降低了软件的复杂性。因此，1999年图灵奖获得者布鲁克斯（FrederickP.Brooks）认为在软件领域人们所取得的进展，如果说有重大进展的话，那就是从汇编语言到高级语言的进展，其他的进展只能算是一种渐进。（）

参考答案:

正确

对软件的分析，可以从系统的角度，也可以从集合的角度来分析。因此，控制和降低软件的复杂度的问题就可以转化为如何降低系统的复杂性，或更为基础地如何降低集合复杂性的问题。下列哪些选项能够有效地降低系统（或集合）的复杂性（）

参考答案:

要使一个集合的复杂性下降，就要想办法使它有序；而要使一个集合有序，最好的办法就是对它按等价类进行分割。_系统软件开发中，要遵循抽象第一的原则。所谓抽象，就是要对实际的事物进行人为处理，抽取所关心的、共同的、本质特征的属性，并对这些事物及其特征属性进行描述。由于抽取的是共同的、本质特征的属性，从而大大降低了系统元素的绝对数量。_我们知道，一个系统就是一个集合。那么，一个系统的分解也就是一个集合的分解。在集合分解中，有一个称为等价类的重要概念，使用该概念可以将一个集合划分为若干互不相交的子集（等价类），从而降低了系统的复杂性。_要使一个软件系统的复杂性下降，无非也是分割，就要将其进行分割，也就是将一个大系统划分为若干小的子系统，最终，使人们易于理解和交流。

关于软件的复杂性，1999年图灵奖获得者布鲁克斯（FrederickP.Brooks）在其著作《人月神话》（TheMythicalMan-month）一书中从复杂度、一致性、可变性、不可见性等方面做了系统的分析，揭示了软件所固有的困难。下列有关布鲁克斯总结的软件所固有的困难的说法不正确的是（）

参考答案:

一致性，软件不必随接口变化就能保持各子系统之间的一致性

下列有关系统同构的说法不正确的是（）

参考答案:

不同系统间的数学同构关系具有自反性和传递性，但不具有对称性。因此，系统同构可以用于模型简化，不能用于划分等价类

下面关于数学家和计算机科学家的说法正确的是（）

参考答案:

计算机科学家倾向于将问题分解成若干状态，并精确地定义事物处理的每一步骤_数学家倾向于用公式来描述事物的状态_计算机科学家侧重于对变化的动态过程（不连续过程）状态的重点把握_数学家侧重于强烈的几何推理和关于无限问题的推理

笛卡儿积具有重要的理论价值，可以说，事物之间所有的关联都在笛卡儿积之中。然而，人与机器对笛卡儿积产生的“组合爆炸”问题是无法进行处理的。因此，尽管笛卡儿积“完美无缺”，但却无任何实际的应用价值。因此，在实际工作中，我们还要充分运用与集合相关的函数、关系、定义等数学工具，将注意力放在事物之间具有实质性关联的方面，最终控制和降低系统的复杂性。集合A1，A2，…，An的乘积一般用法国数学家笛卡儿（ReneDescartes）的名字命名，即笛卡儿积。下列有关集合乘积描述不正确的是（）

参考答案:

若集合A有n个元素，集合B有m个元素，A×B有个元素

计算思维表述体系给出了42个核心概念，其中属于协作类别的是（）

参考答案:

同步、并发、并行、事件、服务

计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。在一个RSA公钥密码系统中，设公钥为（5，34），其私钥为。（）

参考答案:

(13，34)

下面数组可以按行主序、列主序的方式在主存中的存放，下列选项中正确的是（）5E6AC58C9BB47EB355

参考答案:

列主序时存放顺序为5E、8C、7E、6A、9B、B3、C5、B4、55_行主序时存放顺序为5E、6A、C5、8C、9B、B4、7E、B3、55

编码是计算思维中的一个核心概念。ASCII码用8位二进制码来表示英文中的大小写字母、标点符号、数字0到9以及一些控制数据（如换行、回车和制表符等），这8位二进制码可以分为高4位和低4位。下表是ASCII码对照表，那么字符‘M’的ASCII码是（）【图片】

参考答案:

01001101

在一个计数范围是0～11的计算系统中，其模是（）

参考答案:

12

编码是计算思维中的一个核心概念。ASCII码用8位二进制码来表示英文中的大小写字母、标点符号、数字0到9以及一些控制数据（如换行、回车和制表符等），这8位二进制码可以分为高4位和低4位。下表是ASCII码对照表，那么字符‘+’的ASCII码是（）【图片】

参考答案:

00101011

数组、列表和树等数据结构是在何种意义上的数据抽象（）

参考答案:

逻辑结构

人们通常用排序网络来理解并并行计算的思维。下面给出一个排序网络，左侧输入右侧输出，若自上而下输入为3、2、6、5，那么输出自上而下依次为（）【图片】

参考答案:

6、5、3、2

计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。在一个RSA公钥密码系统中，设私钥为（7，119），对加密报文20解密，原报文为。（）

参考答案:

62

计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。在一个RSA公钥密码系统中，设公钥为（3，15），对报文5加密结果为。（）

参考答案:

5

十六进制数【图片】转换为二进制数为（）

参考答案:

00100011

背包问题就是给定n种物品和一个背包，设Wi为物品i的重量，Vi为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大。用贪婪算法解决背包问题，贪婪准则为：每次都选择价值最大的物品装包。假设n=3；W1=100，V1=50；W2=20，V2=30；W3=20，V3=40；C=110。下列说法正确的是（）

参考答案:

选物品1，这种方案的总价值为50

Vcomputer机器内存中71~78存储单元为存储系统分配给一个循环队列的连续存储空间（Vcomputer机器内存初始时内容都为0），如图该队列当前的队头地址为72，队尾地址为77。若当前状态下插入82、4C，然后执行3次出队操作，最后再插入4D、9E，最终上述操作完成后该循环队列队头地址为，队尾地址为。（）【图片】

参考答案:

75，73

十六进制数(88)16转换为二进制数为（）

参考答案:

10001000

人们通常用排序网络来理解并并行计算的思维。下面给出一个排序网络，左侧输入右侧输出，若自上而下输入为4、2、6、1，那么输出自上而下依次为（）【图片】

参考答案:

1、2、4、6

下面给出了汉诺塔（Hanoi）问题的递归算法Raptor程序的move()子程序，请补全横线处的程序。()【图片】【图片】【图片】

参考答案:

move(u-1,x,z,y)

模型与实现是认识与实践的一种具体体现，在计算学科中，它反映了抽象、理论和设计3个过程的基本内容。模型与实现包括建模、验证和实现3方面的内容。以下论述不正确的是（）

参考答案:

建模主要属于学科理论形态方面的内容_模型的实现则主要属于学科理论形态方面的内容

编码是计算思维中的一个核心概念。ASCII码用8位二进制码来表示英文中的大小写字母、标点符号、数字0到9以及一些控制数据（如换行、回车和制表符等），这8位二进制码可以分为高4位和低4位。下表是ASCII码对照表，那么下列说法错误的是（）【图片】

参考答案:

符号‘#’的ASCII码是00100010_字母‘l’的ASCII码是01101101

“充分条件，必要条件”是征服数学的关键，只要能够清楚的分辨，就能克服数学。遗憾的是，即使顶尖的高手，在辩论中，也常搞混这两个概念。伟大的科学家是成为家庭内部矛盾处理行家的什么条件（）

参考答案:

既不是充分条件，也不是必要条件

计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。设p=11,q=17,n=11×17=187，构建一个RSA公钥密码系统，公钥为，私钥为。（）

参考答案:

(3,187)

(107,187)

假设f=10%，p→¥，根据阿姆达定律可以得到并行计算机系统最大的加速能力Sp为（）

参考答案:

10

已知一个采用一维数组形式实现的队列Q（每项占一个存储单元），当前队头地址为11，队尾地址为17。现在向队内插入一项，同时移走两项。那么，当前队头地址为，队尾地址为。（）

参考答案:

13，18

设某一含有4个结点的树形结构，结点中的数据分别为A3、3B、8C和D7。已知A3和8C为兄弟关系，而D7为A3的子结点。则该树中叶子结点有，根结点是。（）

参考答案:

8C、D7；3B

归并排序是一个采用“分治法”原理进行排序的算法。“分治法”的核心思想就是将一个大而复杂的问题分解成若干个子问题分而治之。即，先将一个待排序的数组随机的分成两组且两组数组的元素个数相等或接近相等（若为奇数，其中一个数组的元素多1个），继续对分组的数组进行分组，直到每个数组的元素个数为1；最后，不断地将两个已排好序的相邻数组的元素归并起来，直到归并为一个包含所有元素的数组。归并两个已排序好的数组是容易的，只要不断地移出两组元素最前端较小的元素即可，在该过程中，需要开辟一块与原序列大小相同的空间以便进行归并操作。请选择正确的选项使得以下过程实现对8个元素的数组按升序排序（）初始数组：13，42，25，106，87，102，91，49第一次分组：[13，42，25，106]，[87，102，91，49]第二次分组：[13，42]，[25，106]，[87，102]，[91，49]第三次分组：[13]，[42]，[25]，[106]，[87]，[102]，[91]，[49]第一次归并：[13]，[42]，[25]，[106]，[87]，[102]，[49，91]第二次归并：[13，42]，[25，106]，[87，102]，[49，91]第三次归并：第四次归并：[13，25，42，49，87，91，102，106]

参考答案:

[13，25，42，106]，[49，87，91，102]

抽象（Abstraction）与自动化（Automation）是计算思维的本质特征，在计算学科各领域中均存在为数不少的抽象工具。E-R图（实体-联系图）就是其中一种对客观世界进行抽象的工具，使用该工具可以大大降低软件系统研制，特别是数据库应用系统研制的复杂性。有一个图书管理系统，一本图书可被多个读者借阅，一个读者可借阅多本图书，一个管理员既可管理图书信息，也可管理读者信息，图书，读者，管理员3个实体的属性如下：图书（图书号，书名，类别，出版社，出版日期，作者名，可借数量）读者（读者姓名，读者号，最大可借书量，已借书量，性别，读者类别）管理员（管理员号，管理员类别，性别，联系电话，登录密码）该图书管理系统的E-R图如下所示，图中空白处的填写顺序为（）【图片】

参考答案:

借阅号、读者号、管理员号

美国ACM前主席Denning给出的两个否定，不是说周以真提出的计算思维不好，而是说，Denning自己提出的“伟大的计算原理”更能充分地展示计算机科学的伟大。其实，周以真是从这个层面给出计算思维本质的结构，Denning是从出发给出计算思维的结构框架，显然，还可以从这个层面给出计算思维的结构框架。（）

参考答案:

思维、原理、思想方法

在计算机理论的研究中，可以将无符号数分配给任何用特定语言编写的程序，这样的无符号数就称为哥德尔数。这种分配使得程序可以作为单一的数据项输入给其他程序。这样就可以将程序转化为歌德尔数并作为单一的数据项输入给其他程序。特别的，当一个程序以自身（转化为哥德尔数）为输入，该程序能够终止，那么这个程序就是一个自终止的程序，否则就不是。下面程序能否自终止的（填能或否）。whilexnot0do;end;

参考答案:

否

下列属于计算机中的博弈问题的有（）

参考答案:

国际象棋_西洋跳棋_围棋_中国象棋

通常验证一个问题的解是否正确远比找到一个问题的解要容易的多，这就是所谓的“证比求易”（Algorithmofverifyingiseasierthanfindingsolutions）。比如，对于求48770428433377171的一个真因子的问题，最坏情况下需要计算次数的数量级约为；而验证223092827是否是真因子只需要1次。这个结论有重要的认知价值，与“评论别人的文章比写文章容易”类似，属于教育学中的元认知。（）

参考答案:

2亿

计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。设p=3,q=11,n=3×11=33，构建一个RSA公开密钥密码系统，用私钥(7,33)对c=3进行解密，得到的解密报文为（）

参考答案:

9

计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。在一个RSA公钥密码系统中，设公钥为（5，91），对报文6加密的密文为。（）

参考答案:

41

在图灵机中，一个给定机器的“程序”认为是机器内的五元组（【图片】）或（【图片】）或（【图片】）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。下列有关各元素的含义不正确的是（）

参考答案:

R、L、N分别表示向左移一格、向右移一格、不移动

程序有3种基本结构(循环结构、顺序结构、选择结构)，下面3幅图分别对应的是（）【图片】

参考答案:

顺序结构、选择结构、循环结构

哲学家共餐问题反映的是计算学科中的问题。（）

参考答案:

进程同步

美国ACM前主席Denning在《超越计算思维》一文中对周以真教授提出的计算思维给了哪两个否定（）

参考答案:

计算思维不是计算机科学独有的特征_计算思维不能充分的代表计算机科学的特征

计算思维表述体系给出了42个核心概念，其中属于抽象的是（）

参考答案:

抽象、抽象层次、概念模型、实现模型

计算思维表述体系给出了42个核心概念，其中属于设计类别的是（）

参考答案:

分解、复合、折中、可靠性、安全性、重用性

美国ACM前主席Denning在《超越计算思维》一文中增加了以下计算原理的两个类别，最终形成了7个伟大的计算原理。（）

参考答案:

评估、设计

用欧几里得算法求得自然数216与78的最大公因子为