大学计算机学习指导——面向计算思维能力培养

本书是“计算思维导论”和“计算思维导论实验”课程的配套教材，是帮助学生学习和理解计算思维概念、训练计算思维能力的学习指导书。本书内容丰富，共6章，第1章为引论；第2章为计算系统的基本思维；第3章为算法类问题求解框架；第4章为算法与复杂性；第5章为数据抽象、设计与挖掘；第6章为计算机网络。每章内容分两部分，*部分详细列出本章的知识点和解析；第二部分给出练习题，包括单选题、多选题、判断题、填空题及简答题5种题型。本书适合作为高等学校理工类各专业计算思维课程的学习指导书。

潘梅园，南京航空航天大学计算机科学与技术学院教师，从事计算机基础课程教学工作。主持和参加教改项目2项，省部级教改项目1项，省部级课题2项，成果获省部级科学技术进步奖特等奖1项，二等奖2项，三等奖1项，编撰教材4部，主要研究网络数据库系统，多年来，一直从事大学计算机教学实践及面向计算思维的教学改革研究。

目 录

第1章 引论 1
1.1 知识点 1
1.2 练习题 6
第2章 计算系统的基本思维 12
2.1 理解0和1的思维 12
2.1.1 知识点 12
2.1.2 练习题 18
2.2 图灵机与冯·诺依曼计算机 27
2.2.1 知识点 27
2.2.2 练习题 33
2.3 现代计算机 42
2.3.1 知识点 42
2.3.2 练习题 44
2.4 不同抽象层级的计算机（软件） 49
2.4.1 知识点 49
2.4.2 练习题 51
第3章 算法类问题求解框架 55
3.1 知识点 55
3.2 练习题 61
第4章 算法与复杂性 71
4.1 问题及其算法 71
4.1.1 知识点 71
4.1.2 练习题 74
4.2 递归及递归算法 78
4.2.1 知识点 78
4.2.2 练习题 80
4.3 遗传算法：计算复杂性与仿生学算法示例 83
4.3.1 知识点 83
4.3.2 练习题 85
第5章 数据抽象、设计与挖掘 91
5.1 知识点 91
5.2 练习题 98
第6章 计算机网络 108
6.1 知识点 108
6.2 练习题 116

前  言
计算思维是大学计算机基础教学研究的热点课题之一。计算思维课程从计算机基础教学中如何培养大学生的计算思维能力出发，在课堂教学上，把计算（机）的知识放在思维层面进行讲解，使学生通过思考“这些知识是如何形成的”来贯通知识，提高计算思维能力。计算思维课程针对的是高等学校低年级非计算机专业的学生，在教学活动中，我们发现了两个问题：一是计算思维课程理论性较强，涉及面广，教师对课程的讲授深度产生困惑；二是学生在具体的学习过程中对课程内容的理解有一定的困难。鉴于教师教学与学生学习这两方面的问题，我们编写了本书。
本书的目的在于培养学生的计算思维能力，切入点是“计算思维导论”课程理论教学中的难点，通过多种类型的题目训练，提高学生对计算思维的理解。本书内容丰富，用6个章节对知识点进行了解析，希望学生在计算思维的学习或实践中遇到疑惑时，通过学习知识点的解析获得一些帮助。
本书共分为6章，第1章为引论；第2章为计算系统的基本思维；第3章为算法类问题求解框架；第4章为算法与复杂性；第5章为数据抽象、设计与挖掘；第6章为计算机网络。每章内容分两部分，部分详细列出本章的知识点和解析；第二部分给出练习题，包括单选题、多选题、判断题、填空题及简答题5种题型。
计算思维导论课程建议在大学一年级学期开设。考虑到教学进度和学生接受程度，总学时安排为理论24学时，实践30学时为宜。
本书由潘梅园、朱敏、钱忠民和王立松4位老师共同创作和编写，其中，潘梅园老师负责第1、3、4、5章的编写以及统筹全稿，朱敏老师负责第6章的编写，钱忠民老师负责第2章的编写，王立松老师为本书的编写提供了许多素材。南京航空航天大学长期从事大学计算机教学的一线老师对本书进行了讨论，刘绍翰、张志航、张定会、刘佳、朱玉莲和臧洌老师对练习题进行了改造并提出了很好的修改建议。本书也选用了哈尔滨工业大学战德臣老师主编的《计算思维导论》教材中的一些素材。
本书在成稿过程中得到了很多专家教授的指点和帮助，哈尔滨工业大学的战德臣教授给予了本书很多的建议，南京航空航天大学的袁家斌教授审阅了全书，在此对他们表示衷心的感谢。感谢南京航空航天大学教务处、计算机科学与技术学院及电子工业出版社对本书的出版工作所给予的大力支持。在此对在本书出版工作中作出贡献的所有人员一并表示衷心的感谢。
面向计算思维能力培养的大学计算机是一门发展中的课程，由于时间仓促和编者的水平有限，书中的内容难免有不完善之处，敬请广大读者谅解，并诚挚地欢迎读者提出宝贵建议。

                                       编  者