在磁带上。四、简答题。(共6 小题,每小题约 5分,共 32分) 1. 简述下列术语:数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。数据: 数据是信息的载体,是计算机程序加工和处理的对象,包括数值数据和非数值数据。数据项: 数据项指不可分割的、具有独立意义的最小数据单位,数据项有时也称为字段或域。数据元素: 数据元素是数据的基本单位, 在计算机程序中通常作为一个整体进行考虑和处理, 一个数据元素可由若干个数据项组成。数据逻辑结构: 数据的逻辑结构就是指数据元素间的关系。数据存储结构: 数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型: 是指变量的取值范围和所能够进行的操作的总和。算法: 是对特定问题求解步骤的一种描述,是指令的有限序列。 2. 简述栈和线性表的区别。答:一般线性表使用数组来表示的。线性表一般有插入、删除、读取等对于任意元素的操作。而栈只是一种特殊的线性表。栈只能在线性表的一端插入(称为入栈,push )或者读取栈顶元素或者称为“弹出、出栈”(pop) 。 3. 简述栈和队列这两种数据结构的相同点和不同点。答:相同点:栈和队列都是特殊的线性表,只在端点处进行插入,删除操作。不同点:栈只在一端(栈顶)进行插入,删除操作;队列在一端( top )删除,一端(rear) 插入。 4. 如果进栈的元素序列为 A,B,C,D ,则可能得到的出栈序列有多少种? 写出全部的可能序列。答:可能序列有 14 种: ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA 。 5. 如果进栈的元素序列为 1,2,3,4,5,6, 能否得到 4,3,5,6,1,2和1,3,5,4,2,6 的出栈序列? 并说明为什么不能得到或如何得到。