2017春计算机科学导论(桂林电子科技大学)1001861006 中国大学MOOC答案100分完整版

矩仇涵烯玫告钢疲忍毋悔潜练

第1章绪论

习题1

1、单选题：

下图源自以下哪份文件的封面（）

‌

‌
A: Jeannette M. Wing. Computational Thinking[J]. Communications of the ACM. 2006, 49(3).
B: Denning P J, et al. Computing as a discipline. Communications of the ACM , 1989, 32( 1)
C: President’s Information Technology Advisory Committee. Computational Science: Ensuring America’s Competitiveness[EB/OL]. http://www.nitrd.gov/pitac/reports/20050609_computational/computational.pdf, June 2005.
D: ACM / IEE E-Curriculum 2001 Task Force. Computing Curricula 2001. Computer Science. IE EE Computer Society Press and ACM Press, 2001.
答案: President’s Information Technology Advisory Committee. Computational Science: Ensuring America’s Competitiveness[EB/OL]. http://www.nitrd.gov/pitac/reports/20050609_computational/computational.pdf, June 2005.

2、单选题：
‏下列有关计算学科的定义及其根本问题，说法不正确的是（）‌

A: 计算学科是对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。
B: 计算学科的根本问题是什么能被（有效地）自动进行。
C: 学科的根本问题隐藏于学科基本问题之中，或者说，是学科所有问题之中最基本的问题。
D: 计算学科不包括对计算过程的分析以及计算机的设计和使用。
答案: 计算学科不包括对计算过程的分析以及计算机的设计和使用。

3、单选题：

‌下列有关计算学科二维定义矩阵的说法不正确的是（）

‌

A: 计算学科二维定义矩阵的概念为我们认知学科提供了一个模型。
B: 计算学科二维定义矩阵是对计算学科一个高度概括。
C: 计算学科二维定义矩阵横向一维由抽象、理论、设计等3个过程组成，根据CS2013报告，其纵向一维可划分为18个学科知识领域。
D: 在计算学科二维定义矩阵中， 3个过程（学科形态）及其具体内容（值）都是不变的。
答案: 在计算学科二维定义矩阵中， 3个过程（学科形态）及其具体内容（值）都是不变的。

4、单选题：
‏下列有关计算思维特征的说法不正确的是（）‌

A: 计算思维是概念化，不是程序化
B: 计算思维是根本的，不是刻板的技能
C: 计算思维是计算机的，不是人的思维
D: 计算思维是数学和工程思维的互补与融合
答案: 计算思维是计算机的，不是人的思维

5、多选题：
‏“计算机科学导论”课程如何构建是计算教育面临的一个重大问题。对于如何解决该问题，下列阐述正确的是（）‎

单元测验1

1、单选题：

下图源自以下哪份文件的封面（）

‏

‏
A: Jeannette M. Wing. Computational Thinking[J]. Communications of the ACM. 2006, 49(3).
B: Denning P J, et al. Computing as a discipline. Communications of the ACM , 1989, 32( 1)
C: President’s Information Technology Advisory Committee. Computational Science: Ensuring America’s Competitiveness[EB/OL].http://www.nitrd.gov/pitac/reports/20050609_computational/computational.pdf, June 2005.
D: 美国国家科学基金CDI 计划官方网站[EB/OL]. http://www.nsf.gov/crssprgm/cdi/
E: 美国国家科学基金CPATH 计划2009 年项目申报说明 [EB/OL]. http://www.nsf.gov/cise/funding/cpath_faq.jsp#1.
F: ACM / IEE E-Curriculum 2001 Task Force. Computing Curricula 2001. Computer Science. IE EE Computer Society Press and ACM Press, 2001
答案: President’s Information Technology Advisory Committee. Computational Science: Ensuring America’s Competitiveness[EB/OL].http://www.nitrd.gov/pitac/reports/20050609_computational/computational.pdf, June 2005.

2、单选题：
‎下列有关计算学科的定义及其根本问题，说法不正确的是（）‌

3、单选题：

‍下列有关计算学科二维定义矩阵的说法不正确的是（）

‍

4、单选题：
‍下列有关计算思维特征的说法不正确的是（）‎

A: 计算思维是概念化，不是程序化
B: 计算思维是根本的，不是刻板的技能
C: 计算思维是计算机的，不是人的思维
D: 计算思维是数学和工程思维的互补与融合
E: 计算思维是思想，不是人造品
F: 计算思维面向所有的人，所有地方
答案: 计算思维是计算机的，不是人的思维

5、多选题：
‌根据我国高等学校的情况，教育部高等学校计算机科学与技术教学指导委员会制定的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》采纳了Computing Curricula 2005（CC2005）报告划分的4个分支学科，并以专业方向的形式进行规范，其中包括（）‌

A: 计算机科学
B: 计算机工程
C: 软件工程
D: 信息技术
E: 信息系统
答案: 计算机科学;
计算机工程;
软件工程;
信息技术

6、多选题：
下列有关计算学科主要专业培养内容，正确的是（）‍

A: 计算机科学，涉及很宽的范围，包括了计算的理论、算法和实现，以及机器人技术、计算机视觉、智能系统、生物信息学和其他新兴的有前途的领域。
B: 计算机工程，是对现代计算系统和由计算机控制的有关设备上的软件与硬件的设计、构造、实施和维护进行研究的学科。
C: 软件工程，是指以系统、学科、定量的方法，把工程应用于软件的开发、运行和维护；同时，展开对上述过程中各种方法和途径进行研究的学科。
D: 信息系统，是指如何将信息技术的方法与企业生产和商业流通结合起来，以满足这些行业需求的学科。
E: 信息技术，从广义上来说，它包括了所有计算技术的各个方面，在此专指作为一门学科的信息技术。它侧重在一定组织及社会环境下，通过选择、创造、应用、集成和管理的计算技术来满足用户的需求。
答案: 计算机科学，涉及很宽的范围，包括了计算的理论、算法和实现，以及机器人技术、计算机视觉、智能系统、生物信息学和其他新兴的有前途的领域。;
计算机工程，是对现代计算系统和由计算机控制的有关设备上的软件与硬件的设计、构造、实施和维护进行研究的学科。;
软件工程，是指以系统、学科、定量的方法，把工程应用于软件的开发、运行和维护；同时，展开对上述过程中各种方法和途径进行研究的学科。;
信息系统，是指如何将信息技术的方法与企业生产和商业流通结合起来，以满足这些行业需求的学科。;
信息技术，从广义上来说，它包括了所有计算技术的各个方面，在此专指作为一门学科的信息技术。它侧重在一定组织及社会环境下，通过选择、创造、应用、集成和管理的计算技术来满足用户的需求。

7、多选题：
学科知识体由哪3个层次组成（）‎

A: 分支领域
B: 知识单元
C: 知识点
D: 核心课程
答案: 分支领域;
知识单元;
知识点

8、多选题：
‍下列有关计算思维的描述，正确的有（）‍

A: 计算思维是通过约简、嵌入、转化和仿真等方法，把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的思维方法
B: 计算思维是一种递归思维，是一种并行处理，是一种把代码译成数据又能把数据译成代码的方法，是一种多维分析推广的类型检查方法
C: 计算思维是一种采用抽象和分解来控制庞杂的任务或进行巨大复杂系统设计的方法，是基于关注点分离（Separation of Concerns）的方法
D: 计算思维是一种选择合适的方式去陈述一个问题，或对一个问题的相关方面建模使其易于处理的思维方法
E: 计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维方法
F: 计算思维是利用启发式推理寻求解答，即在不确定情况下的规划、学习和调度的思维方法
G: 计算思维是利用海量数据来加快计算，在时间和空间之间、在处理能力和存储容量之间进行折中的思维方法
答案: 计算思维是通过约简、嵌入、转化和仿真等方法，把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的思维方法;
计算思维是一种递归思维，是一种并行处理，是一种把代码译成数据又能把数据译成代码的方法，是一种多维分析推广的类型检查方法;
计算思维是一种采用抽象和分解来控制庞杂的任务或进行巨大复杂系统设计的方法，是基于关注点分离（Separation of Concerns）的方法;
计算思维是一种选择合适的方式去陈述一个问题，或对一个问题的相关方面建模使其易于处理的思维方法;
计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维方法;
计算思维是利用启发式推理寻求解答，即在不确定情况下的规划、学习和调度的思维方法;
计算思维是利用海量数据来加快计算，在时间和空间之间、在处理能力和存储容量之间进行折中的思维方法

9、多选题：

‍下列有关学科二维定义矩阵的说法正确的是（）

‏

‍

‏
A: “横向”关系即抽象、理论和设计3个过程的关系，是定义矩阵中最为重要的内容。它反映的是人们在计算领域的认识规律，即是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）的过程。
B: “横向”关系还蕴含着学科中的基本问题。由于人们对客观世界的认识过程就是一个不断提出问题和解决问题的过程，这种过程反映的正是抽象、理论和设计3个过程之间的相互作用，它与3个过程在本质上是一致的。
C: “纵向”关系即各分支领域中具有共性的核心概念、数学方法、系统科学方法、社会与职业问题等内容的关系。这些内容蕴含在学科3个过程中，并将学科各分支领域结合成一个完整的体系，而不是互不相关的领域。
D: 在定义矩阵中，“横向”关系最重要，“纵向”关系次之。
答案: “横向”关系即抽象、理论和设计3个过程的关系，是定义矩阵中最为重要的内容。它反映的是人们在计算领域的认识规律，即是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）的过程。;
“横向”关系还蕴含着学科中的基本问题。由于人们对客观世界的认识过程就是一个不断提出问题和解决问题的过程，这种过程反映的正是抽象、理论和设计3个过程之间的相互作用，它与3个过程在本质上是一致的。;
“纵向”关系即各分支领域中具有共性的核心概念、数学方法、系统科学方法、社会与职业问题等内容的关系。这些内容蕴含在学科3个过程中，并将学科各分支领域结合成一个完整的体系，而不是互不相关的领域。;
在定义矩阵中，“横向”关系最重要，“纵向”关系次之。

10、多选题：
“计算机科学导论”课程如何构建是计算教育面临的一个重大问题。对于如何解决该问题，下列阐述正确的是（）‌

A: 《计算作为一门学科》报告确认了“计算机科学导论”课程的构建问题是一个重要问题。报告认为，该课程要培养学生面向学科的思维能力，使学生领会学科的力量以及从事本学科工作的价值之所在。报告希望该课程能用类似于数学那样严密的方式将学生引入计算学科各个富有挑战性的领域之中。
B: CC2001报告认为，“计算机科学导论”课应该讲授学科中那些富有智慧的核心思想。
C: CC2004和CC2005则进一步指出，该课程的关键是课程的结构设计问题。
D: CS2001 Interim Review（草案）将“计算思维”与“计算机科学导论”课程绑定在一起，曾明确要求“计算机科学导论”课程讲授计算思维的本质。
E: 论文《通过计算创造性来学习》（Soh L K, Shell D F, Ingraham E, et al. Learning through computational creativity[J]. Communications of the Acm, 2015, 58(8):33-35）论述了“计算机科学导论”课程的重要性，认为它的作用超过了一门一般的计算机科学专业课程，进一步佐证了这门课程构建的重要性。
答案: 《计算作为一门学科》报告确认了“计算机科学导论”课程的构建问题是一个重要问题。报告认为，该课程要培养学生面向学科的思维能力，使学生领会学科的力量以及从事本学科工作的价值之所在。报告希望该课程能用类似于数学那样严密的方式将学生引入计算学科各个富有挑战性的领域之中。;
CC2001报告认为，“计算机科学导论”课应该讲授学科中那些富有智慧的核心思想。;
CC2004和CC2005则进一步指出，该课程的关键是课程的结构设计问题。;
CS2001 Interim Review（草案）将“计算思维”与“计算机科学导论”课程绑定在一起，曾明确要求“计算机科学导论”课程讲授计算思维的本质。;
论文《通过计算创造性来学习》（Soh L K, Shell D F, Ingraham E, et al. Learning through computational creativity[J]. Communications of the Acm, 2015, 58(8):33-35）论述了“计算机科学导论”课程的重要性，认为它的作用超过了一门一般的计算机科学专业课程，进一步佐证了这门课程构建的重要性。

第2章计算学科的基本问题

习题2

1、单选题：
‎汉诺塔问题是使用递归算法的一个典型案例，下面给出的利用Raptor实现的汉诺塔问题盘子移动move的子程序，正确的是（）

A:
B:
C:
D:
答案:

2、单选题：
设p=3， q=7，n=3×7=21，构建一个RSA公钥密码系统，公钥为，私钥为。（）‌

A: (3,12)      (7,12)
B: (5,12)      (5,12)
C: (3,21)     (7,21)
D: (5,21)      (5,21)
答案: (5,21)      (5,21)

3、单选题：
‍按照题2构建的RSA公钥密码系统对报文9加密的结果为，对密文10解密的结果为。（）‍

A: 19    18
B: 18     19
C: 21     18
D: 18    21
答案: 18     19

4、单选题：
‍假设f=0.01%，p→¥，根据阿姆达定律可以得到并行计算机系统最大的加速能力Sp为（）‎

A: 10000
B: 1000
C: 100
D: 10
答案: 10000

5、单选题：
‏下列有关“图灵测试”和希尔勒的“中文屋子”的描述不正确的是（）‍

A: “图灵测试”要求接受测试的思维机器在内部构造上与人脑一样
B: “图灵测试”是从功能的角度判定机器是否能思维
C: 图灵发表的关于“图灵测试”的论文标志着现代机器思维问题讨论的开始
D: “中文屋子”是希尔勒以自己为主角设计的假象实验用来反驳强人工智能的观点
答案: “图灵测试”要求接受测试的思维机器在内部构造上与人脑一样

6、单选题：
通常验证一个问题的解是否正确远比找到一个问题的解要容易的多，这就是所谓的“证比求易”（Algorithm of verifying is easier than finding solutions）。比如，对于求48 770 428 433 377 171的一个真因子的问题，最坏情况下需要计算次数的数量级约为；而验证223 092 827是否是真因子只需要1次。这个结论有重要的认知价值，与“评论别人的文章比写文章容易”类似，属于教育学中的元认知。（）‎

A: 2亿
B: 2百亿
C: 2千亿
D: 2万亿
答案: 2亿

7、填空题：
‌下面程序能否自终止的      （填能或否）。‍‌y=x;
while x not 0 do;
    x=x–1;
end;
y=y–1;
while y not 0 do;
     y=y–1;
end;‍‌‍‌‍
答案: 能

单元测验2

1、单选题：
‌汉诺塔问题是使用递归算法的一个典型案例，下面给出的利用Raptor实现的汉诺塔问题盘子移动move的子程序，正确的是（）‎

A:
B:
C:
D:
答案:

2、单选题：
‏盘子数为4的汉诺塔问题需要移动盘子的次数为（）‌

A: 7
B: 8
C: 15
D: 16
答案: 15

3、单选题：
在“证比求易算法”中，若从2开始，一步一步地求48 770 428 433 377 171数的真因子是；若按自然数的顺序给老百姓编号后，求真因子的算法是。（）‍

A: 并行算法、并行算法
B: 并行算法、顺序算法
C: 顺序算法、顺序算法
D: 顺序算法、并行算法
答案: 顺序算法、并行算法

4、单选题：
‎在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为，而将所有在多项式时间内可以验证的问题称为。（）‎

A: P类问题、NP类问题
B: NP类问题、P类问题
C: NP-C问题、P类问题
D: NP类问题、NP-C问题
答案: P类问题、NP类问题

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

A: 1000
B: 100
C: 10
D: 1
答案: 10

6、单选题：
‏假设f=0.1%，p→¥，根据阿姆达定律可以得到并行计算机系统最大的加速能力Sp为（）‍

A: 1000
B: 100
C: 10
D: 1
答案: 1000

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

A: (5，34)
B: (9，34)
C: (13，34)
D: (17，34)
答案: (13，34)

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

A: 41
B: 90
C: 43
D: 91
答案: 41

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

A: 41
B: 90
C: 43
D: 91
答案: 90

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

A: (3, 32)    (11, 32)
B: (3, 51)    (11, 51)
C: (11, 32)    (3, 32)
D: (11, 51)    (3, 51)
答案: (3, 51)    (11, 51)

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

A: 3
B: 8
C: 19
D: 53
答案: 8

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

A: 13
B: 46
C: 62
D: 124
答案: 62

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

A: (107,187)     (3,187)
B: (3,187)       (107,187)
C: (107,160)     (3,160)
D: (3,160)       (107,160)
答案: (3,187)       (107,187)

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

A: 9
B: 17
C: 34
D: 51
答案: 51

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

A: 3
B: 5
C: 11
D: 15
答案: 5

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

A: 利用价值最大的贪婪准则时，选物品1，这种方案的总价值为60
B: 最优解选物品为2和3，总价值为80
C: 使用贪婪准则，不能保证得到最优解
D: 利用价值最大的贪婪准则时，选物品2和3，总价值为80
答案: 利用价值最大的贪婪准则时，选物品2和3，总价值为80

17、单选题：
‍哲学家共餐问题反映的是计算学科中的（）问题。‍

A: 进程同步
B: 进程异步
C: 进程调度
D: 存储器管理
答案: 进程同步

18、单选题：

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

‍

A: 选择结构、顺序结构、循环结构
B: 顺序结构、循环结构、选择结构
C: 顺序结构、选择结构、循环结构
D: 循环结构、选择结构、顺序结构
答案: 顺序结构、选择结构、循环结构

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

A: 利用价值密度最大的贪婪准则时，选物品1，这种方案的总价值为60
B: 最优解选物品为2和3，总价值为80
C: 使用贪婪准则，能保证得到最优解
D: 利用价值密度最大的贪婪准则时，选物品2和3，总价值为80
答案: 利用价值密度最大的贪婪准则时，选物品1，这种方案的总价值为60

20、单选题：
下列有关“图灵测试”和希尔勒的“中文屋子”的描述不正确的是（）

21、单选题：
‎下列图中存在欧拉回路的是。（）‏

A:
B:
C:
D:
答案:

22、单选题：
‌下列选项中存在哈密尔顿回路是（）

A:
B:
C:
D:
答案:

23、单选题：

下列图中存在欧拉路径的有。（）

‌

‌
A: a、c、d
B: a、b、c
C: b、c、d
D: a、b、d
答案: a、c、d

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

A: 9
B: 6
C: 3
D: 27
答案: 3

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

A: 9
B: 6
C: 3
D: 27
答案: 9

26、单选题：
在“证比求易算法”中，对公主给出的数进行验证，显然是在多项式时间内可以解决的问题，因此，这类问题属于NP类问题。现在，P=NP是否成立的问题是计算学科和当代数学研究中最大的悬而未决的问题之一。2000年5月，美国克莱数学研究所（The Clay Institute of Mathematics）提供100万美元求解这一问题。‍下面论述错误的是（）‍

A: 库克（S. A. Cook）等人认为NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，所有NP问题都是在多项式时间内可解的，这些问题被称为NP完全性问题。
B: 库克因其在计算复杂性理论方面（主要是在NP完全性理论方面）的奠基性工作，于1982年获ACM图灵奖。
C: 历史上第一个NP完全性问题是库克于1971年提出的可满足性问题。
D: 若P≠NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。
答案: 若P≠NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。

27、单选题：
‎通常验证一个问题的解是否正确远比找到一个问题的解要容易的多，这就是所谓的“证比求易”（Algorithm of verifying is easier than finding solutions）。比如，对于求48 770 428 433 377 171的一个真因子的问题，最坏情况下需要计算次数的数量级约为；而验证223 092 827是否是真因子只需要1次。这个结论有重要的认知价值，与“评论别人的文章比写文章容易”类似，属于教育学中的元认知。（）‎

A: 2亿
B: 2百亿
C: 2千亿
D: 2万亿
答案: 2亿

28、多选题：
‏下列属于计算机中的博弈问题的有（）

A: 国际象棋
B: 中国象棋
C: 西洋跳棋
D: 围棋
答案: 国际象棋;
中国象棋;
西洋跳棋;
围棋

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

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

第3章计算学科的3个学科形态

习题3

1、单选题：

‎抽象（Abstraction）与自动化（Automation）是计算思维的本质特征，在计算学科各领域中均存在为数不少的抽象工具。E-R图（实体-联系图）就是其中一种对客观世界进行抽象的工具，使用该工具可以大大降低软件系统研制，特别是数据库应用系统研制的复杂性。

‏

‎一个公司有一个销售部门，一个销售部门有若干员工，每位员工都可以销售若干商品，每个商品都可以由若干员工销售，一个商品可以存放在若干不同的仓库中，一个仓库可以存放不同的商品，一个员工可以管理若干仓库，该单位销售部的E-R图（提示：销售时有一个“销售明细”属性；存放时有一个“存放与出库时间”的属性）如下所示，图中空白填写顺序应为（）

‏

‎

‏

‎

‏
A: 销售明细   销售部门存放与出库时间
B: 存放与出库时间   销售明细销售部门
C: 销售明细存放与出库时间   销售部门
D: 销售部门   销售明细存放与出库时间
答案: 销售明细存放与出库时间   销售部门

2、单选题：
‍计算机对语言进行处理，首先要解决的是语言的歧义性问题，给出句子“I saw the man on the hill with the telescope”，不可能解释为（）‌

A: I with the telescope
B: the man with the telescope
C: the hill with the telescope
D: I on the hill
答案: I on the hill

3、单选题：
‍在图灵的带子机中，设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是11100101，读写头对准最右边第一个为1的方格，状态为初始状态q1。执行以下命令后的计算结果为（）‏q1 0 0 L q2‏q1 1 0 L q3‏q1 b b N q4‏q2 0 0 L q2‏q2 1 0 L q2‏‏q2 b b N q4‏q3 0 0 L q2‏q3 1 0 L q3‏q3 b b N q4‏

A: 10000101
B: 10100101
C: 00000000
D: 00000101
答案: 00000000

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

A: qi表示机器目前所处的状态。
B: Sj表示机器从方格中读入的符号。
C: Sk表示机器用来代替Sj写入方格中的符号。
D: R、L、N分别表示向左移一格、向右移一格、不移动。
答案: R、L、N分别表示向左移一格、向右移一格、不移动。

5、单选题：

‍Vcomputer机器指令由4位十六进制数构成（1位操作码，3位操作数），其机器指令集如下表所示。那么下列选项中的指令能表示“将地址为E8的内存单元的值装入寄存器R0中” 的是（）

‍

‍
A: 10E8
B: 1E80
C: 20E8
D: 2E80
答案: 10E8

6、单选题：
‍在“学生选课”例子中，A={学生，属性，码，关系，学号，姓名，年龄，性别，课程，课程号，课程名，成绩，E-R图，“学生选课”E-R图，关系模型，“学生选课”关系模型…… }一般被划分到以下哪种形态（）‏

A: 抽象
B: 理论
C: 设计
D: 不能划分
答案: 抽象

单元测验3

1、单选题：

‏抽象（Abstraction）与自动化（Automation）是计算思维的本质特征，在计算学科各领域中均存在为数不少的抽象工具。E-R图（实体-联系图）就是其中一种对客观世界进行抽象的工具，使用该工具可以大大降低软件系统研制，特别是数据库应用系统研制的复杂性。

‏

‏一个公司有一个销售部门，一个销售部门有若干员工，每位员工都可以销售若干商品，每个商品都可以由若干员工销售，一个商品可以存放在若干不同的仓库中，一个仓库可以存放不同的商品，一个员工可以管理若干仓库，该单位销售部的E-R图（提示：销售时有一个“销售明细”属性；存放时有一个“存放与出库时间”的属性）如下所示，图中空白填写顺序应为（）

‏

‏
A: 销售明细   销售部门  存放与出库时间
B: 存放与出库时间   销售明细  销售部门
C: 销售明细  存放与出库时间   销售部门
D: 销售部门   销售明细  存放与出库时间
答案: 销售明细  存放与出库时间   销售部门

2、单选题：

抽象（Abstraction）与自动化（Automation）是计算思维的本质特征，在计算学科各领域中均存在为数不少的抽象工具。E-R图（实体-联系图）就是其中一种对客观世界进行抽象的工具，使用该工具可以大大降低软件系统研制，特别是数据库应用系统研制的复杂性。

‍

有一个图书管理系统，一本图书可被多个读者借阅，一个读者可借阅多本图书，一个管理员既可管理图书信息，也可管理读者信息，图书，读者，管理员3个实体的属性如下：

‍

图书（图书号，书名，类别，出版社，出版日期，作者名，可借数量）

‍

读者（读者姓名，读者号，最大可借书量，已借书量，性别，读者类别）

‍

管理员（管理员号，管理员类别，性别，联系电话，登录密码）

‍

该图书管理系统的E-R图如下所示，图中空白处的填写顺序为（）

‍

‍
A: 借阅号、管理员号、读者号
B: 借阅号、读者号、管理员号
C: 读者号、管理员号、借阅号
D: 读者号、借阅号、管理员号
答案: 借阅号、读者号、管理员号

3、单选题：
‍计算机对语言进行处理，首先要解决的是语言的歧义性问题，给出句子“I saw the man on the hill with the telescope”，不可能解释为（）

A: I with the telescope
B: the man with the telescope
C: the hill with the telescope
D: I on the hill
答案: I on the hill

4、单选题：
在图灵的带子机中，设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是11100101，读写头对准最右边第一个为1的方格，状态为初始状态q1。执行以下命令后的计算结果为（）‌‌q1 0 0 L q2‌q1 1 0 L q3‌q1 b b N q4‌q2 0 0 L q2‌q2 1 0 L q2‌q2 b b N q4‌q3 0 0 L q2‌q3 1 0 L q3‌q3 b b N q4‌

A: 10000101
B: 10100101
C: 00000000
D: 00000101
答案: 00000000

5、单选题：
‎硬盘属于哪类设备（）

A: 输入设备
B: 输出设备
C: 既属于输入设备，又属于输出设备
D: 既不属于输入设备，又不属于输出设备
答案: 既属于输入设备，又属于输出设备

6、单选题：
‍现有一台计算机，它的总线宽度（也即数据总线的宽度）为32位，地址总线的宽度为16位，试问该计算机有个不同的地址空间，一次总线传送的数据位数是，最大值是。（）‏

A: 2017春计算机科学导论(桂林电子科技大学)1001861006 中国大学MOOC答案100分完整版第32张，，
B: ，，
C: ，，
D: ，，
答案: ，，