计算机问题求解 – 论题1-5 - 数据与数据结构 2018年10月16日

Part I 计算机中的数据

问题1: “变量”是不是“量”？ x  x + 1 该如何理解？

改变“位置”和改变“内容” Y  V[X]; V[X]  V[X+1]; V[X+1]  Y;

什么是“结构”？ 问题2： 你认为这段话中哪些词最关键？ 你会想到什么儿时的游戏吗?

数据和“位置” “全班同学排好队！”是什么意思？ 每人有了一个“位置”。 其实这个“位置”是相对的。 如果安排一种按照位置进行的“游戏”，“到了什么位置就知道该做什么”。 如何以前面的观点来理解vector, 或称为list, 或称为one-dimensional array是一种数据结 构？

问题3： 你怎么理解计算机语言中的 数据类型？ 整型数integer: 一个名字、一个集合、一组运算

问题4： 数组是数据类型吗？ 抽象的逻辑结构：“顺序”结构 计算机中的“实现”：同类型数据的“序列”。程序设计语言为你提供了定义特定数组的“设施” 物理位置：你可以不用管

结构为解题服务 问题5： Collatz 问题： 这个序列的长度(包括首尾)称为22的“周期”，值为16。 问题5： 你能否写一个程序，输入为两个正整数(i,j)，输出为 从i到j所有整数最大的周期值。例如当输入为1，10 时输出是20。

问题6： 数组（向量）和循 环是什么关系？

问题6： 你能解释一下上面两个图的含义吗？ 有什么启发吗？

问题7 你觉得数组有什么缺点吗？ 从“解题”的角度看，“顺序”可能是我们关心的特征，如何实现其实解题者未必需要关系。

An array is an indexed data structure, which means you can select its elements in arbitrary order as determined by the subscript value. You can also access the elements in sequence using a loop that increments the subscript. However, you can’t do the following with an array object: Increase or decrease its length, which is fixed. Add an element at a specified position without shifting the other elements to make room. Remove an element at a specified position without shifting the other elements to fill in the resulting gap.

Part II 抽象数据类型与问题求解

“随意”和“受限” 在书架的一层上取一本书 在机场的饮水机旁取一个纸杯 问题8： 你能说出这两者的差别吗？

抽象数据类型 为什么称为“抽象”？ 对数据对象的操作与“解题”有关，与计算机中的结构无关 只规定“操作”，不管怎么实现 创建、插入、读取、查看、删除…

Find Palindrome 问题9： Able was I ere I saw Elba 如何利用栈？ A palindrome is a string that reads the same in either direction: left to right or right to left. A well-known palindrome regarding Napoleon Bonaparte is “Able was I ere I saw Elba” (the island where he was sent in exile). We would like a program that reads a string and determines whether it is a palindrome. Able was I ere I saw Elba 问题9： 如何利用栈？

Write a menu‐driven program that maintains a list of customers waiting for service. The program user should be able to insert a new customer in the line, display the customer who is next in line, remove the customer who is next in line, display the length of the line, or determine how many people are ahead of a specified customer. 先到先服务 问题10： 如何利用队列？

更复杂的“位置”关系 – “树”

问题11： 你能举出一些可以抽象为树结构的日常关系吗？

用树排序： 第1步：将数组表示为“二分搜索树” 用树排序： 第1步：将数组表示为“二分搜索树” 问题12: 你能看出这 个树是如何 生成的吗?

用树排序： 第2步：以“某种”方式遍历树 问题13: 为什么输出肯定 是从小到大的? “ left-first traversal” 用树排序： 第2步：以“某种”方式遍历树 问题13: 为什么输出肯定 是从小到大的? “ left-first traversal” “ second-visit output:

问题14： 树和递归有什么关系？

利用树和栈解更复杂的问题 如何自动表述一个带括号的算术式的计算序列？ 例如： (10 + (( 22 – 3  4) / 2 – 2  2 )  (( 14 – 2) / (1 + 3 ) )

第1步：构造一个表达式树  + / 10 - 22 2 3 4 14 1

第2步：遍历这个树 Left-first traversal; Third-visit output; 10 22 3 4  - 2 2 2  - / + 14 2 - 1 3 + / 

第3步：栈操作

家庭作业 pp.46- 2.10 – 2.16