权威预测：
【例1】数据类型和抽象数据类型是如何定义的?二者有何相同和不同之处?抽象
数据类型的主要特点是什么?使用抽象数据类型的好处是什么?
【解】 数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合，如
C语言中的整型、实型、字符型及其上的加、减等操作。实际上数据类翌是厂家提供给用的已实现了的基本数据结构。
抽象数据类型(ADT)指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象敛据类型的定义仅取决于它的逻辑特性．而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。
抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的鼓据类型，还包括用户在设计软件系统时自行定义的敛据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分．封装在一起．对用户透明(提供接口)，而不必了解实现细节。
【例2】选择数据结构应从哪些方面考虑?
【解】通常考虑算法所{iI}要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时闻，计算机执行每条指令所需时间和程序中指令重复执行的次数。
【例3】若有100个学生，每个学生有学号．姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构?
【解】把学号、姓名、平均成绩看成一个记录，含三个数据项，并将100个这样的记录存于数组中。因一般无增删操作，故宜采用顺序存储，可定义如下：
}
本算法时间复杂度为O(n)。算法只是按题目要求把正负数分开，如要求统计负数和大于等于零的个数，则最后以t来定。如t为负数，则0至i共i十1个负数，n一1一i个正数(包括零)。另外，题目并未提及零的问题，不妨将零放到正数一边。
【例14】什么是循环队列?
【解】常规的一维数组(顺序存储结构)表示的队列，由于队尾插入和队头删除容易造
成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度(容量)。为了解决“假溢出”问题，提出循环队列这种结构。这是一种首尾元素相接的数据结构。循环队列常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。
【例15】如果输入序列为123456，试问能否通过栈结构得到以下两个序列：435612和135426。请说明为什么不能或如何才能得到。
【解】 输入序列为123456，不能得出435612。理由是，输出序列最后两元素是12，前面4个元素(4356)得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下：
1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
【例16】 (1)什么是递归程序?(2)递归程序的优缺点是什么?(3)递归程序在执行时，应借助于什么来完成?(4)递归程序的入口语句、出口语句一般用什么语句实现?
【解】 (1)一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数厂在执行中，又调用函数厂自身，这称为直接递归；若函数厂在执行中，调用函数g，而g在执行中，又调用函数_厂，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。
(2)递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存
空间较多，运行效率低。
(3)递归程序执行中需借助栈这种数据结构来实现。
(4)递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本
项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分；归纳项是将原来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“到达”基本项。
【例17】用一个数组S(设大小为SIZE)作为两个堆栈的共享空间。请说明共享方法和栈满／栈空的判断条件，并用c或PASCAL设计人栈操作pLlsh(i，x)和出栈操作pop(i)。其中i为O或l，用于表示栈号，x为人栈值。
【解】 两栈共享一向量空间(一维数组)，栈底设在数组的两端，两栈顶相邻时为栈满。
设共享数组为s[SIZE]，则一个栈顶指针为一1，另一个栈顶指针为SIZE时，栈为空。
用C描述入栈操作push(i，x)如下：
const int SIZE=<共享栈可能达到的最大容量>；
tvpedef char Elem Type； ／／假设栈元素类型为char
typedef structnode
