数据结构考研辅导材料.pdf

第1章引论1.1 数据结构课程的地位和考试要求1.1.1 数据结构课程的地位数据结构是计算机科学与技术专业本科生的专业基础课程之一，是程序设计系列课程中 一个不可或缺的环节，对于信息系统的研究和开发起到重要的支撑作用。因此，国内外大专 院校计算机和软件工程专业都把数据结构列为考研的必考科目。2009年教育部更是把 这门课程列为全国硕士研究生入学考试计算机专业基础综合考试的考试科目之一，在满分 150分中占了 45分。复习好数据结构，对于通过联考有着至关重要的作用。1.1.2 考试要求2010年教育部指定考试大纲明确提出，对于数据结构部分，主要考查：(1)理解数据结构的基本概念；掌握数据的逻辑结构，存储结构及其差异，以及各种基 本操作的实现。(2)在掌握基本的数据处理原理和方法的基础上，能够对算法进行时间复杂度和空间复 杂度分析。(3)能够选择合适的数据结构和方法进行问题求解。具备采用C或C+或JAVA语言设 计与实现算法的能力。换句话说，考查的目标有两个：知识和技能。1.知识方面从数据结构的结构定义和使用，以及存储表示和操作的实现两个层次，系统地考查：(1)掌握常用的基本数据结构(包括顺序表、链接表、栈与队列、数组、二叉树、堆、树与森林、图、查找结构、索引结构、散列结构)及其不同的实现(2)掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法2.能力方面从解决问题的角度出发，系统地考查：(1)掌握运用基本数据结构来设计算法方法的能力(2)掌握算法设计和分析的思考方式及技巧，提高分析问题和解决问题的能力。前者在全国联考的试卷中占20分，主要通过选择填空题方式考查；后者在全国联考的 试卷中占25分，主要通过综合应用题方式考查。1.1.3 考查的知识点分析2010年考试大纲，对其主要条目做了细化和整理，总结出数据结构部分主要考 查的知识点有45个，分布在6章内1.线性表包括4个知识点：(1)线性表的定义、特点和基本操作(已考)(2)线性表的存储表示，包括顺序存储和链式存储(已考)(3)特殊链表的定义和基本运算的实现，包括循环链表和双向链表(4)线性表的应用，包括基于一维数组的一些算法、一元多项式的组织和操作等2.栈、队列和数组包括7个知识点：-1-(1)栈与队列的定义、特点和基本操作(已考)(2)栈的存储表示及其操作的实现，包括顺序栈和链式栈(3)队列的存储表示及其操作的实现，包括循环队列和链式队列(4)特殊队列的定义和存储表示，包括双端队列(已考)和优先队列(5)栈与队列的应用，包括递归改非递归(分治与回溯)、表达式计算、括号配对、数 值转换、分层处理(6)多维数组的定义和特点，包括二维数组计算、基于矩阵的算法实现(7)特殊矩阵的定义和特点，包括对称矩阵、三对角矩阵、稀疏矩阵3.树与二叉树包括9个知识点：(1)树与二叉树的定义、性质(已考)(2)二叉树的存储表示，包括顺序存储和链接存储(3)二叉树的遍历及其应用，包括前序、中序、后序(已考)和层次序遍历(4)线索二叉树的定义(已考)、存储表示和寻找前驱、后继(5)树与森林的存储表示(已考)和遍历(已考)(6)二叉排序树的定义、存储表示、基于二叉排序树的算法实现(7)平衡二叉树的定义(已考)、存储表示、基本操作和平衡旋转(已考)(8)哈夫曼(Huffman)树的定义(已考)、存储表示和应用(9)堆的定义(已考)、存储表示和基本操作的实现(已考)4.图包括8个知识点：(1)图的基本概念，包括顶点的度、路径、回路、连通图(已考)等(2)图的存储表示，包括邻接矩阵、邻接表(3)图的遍历，包括深度优先搜索和广度优先搜索的实现(4)最小生成树的定义(已考)、构成方法，包括Kruskal算法和Prim算法(6)最短路径的概念(已考)和求解方法，包括Dijkstra算法和Floyd算法(7)拓扑排序的定义、实现方法(已考)(8)关键路径的定义、求解方法5.查找包括6个知识点：(1)查找的概念和性能评价标准(2)顺序查找算法和性能分析(3)折半查找算法和性能分析(已考)(4)m阶B树的定义和存储结构(已考)、查找、插入与删除的平衡化(5)m阶B+树的定义和存储结构、搀着、插入与删除的平衡化(6)散列法的概念、散列函数的选择、解决冲突的线性探测法(已考)、二叉探测法、双散列法和链地址法、散列法的性能分析6.内排序包括10个知识点：(1)排序的概念和性能评价标准，包括排序码比较次数、元素移动次数、附加存储数、稳定性(2)直接插入排序的思路、算法和性能分析(已考)、稳定性(3)折半插入排序的思路、算法和性能分析、稳定性(4)起泡排序的思路、算法和性能分析(已考)、稳定性(5)简单选择排序的思路、算法和性能分析(已考)、稳定性(6)快速排序的思路、算法和性能分析(已考)、稳定性-2-(7)堆排序的思路、算法和性能分析、稳定性(8)二路归并排序的思路、算法和性能分析(已考)、稳定性(9)基数排序的思路、算法和性能分析(10)排序方法的性能比较(已考)(11)排序方法的应用在复习过程要切实掌握这些知识点，才能够对考试应付自如。复习方法参看第8章。1.2 数据结构和算法的预备知识这些知识是考试大纲没有明确要求，但贯穿于所有各章的必备知识。对于理解和掌 握各章的内容起到了支持作用。1.2.1 数据结构的主要概念1.什么是数据数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算 机程序识别和处理的符号的集合。数据主要分两大类:数值性数据和非数值性数据。数据结构主要研究的是非数值型数据。2.什么是数据元素数据的基本单位就是数据元素。例如，在学校的学籍管理系统中学生文件是由一系列学 生记录组成，每个学生记录就是一个数据元素。在计算机程序中数据元素常作为一个整 体进行考虑和处理。数据元素又可称为元素、结点、记录。有时一个数据元素可以由若干数据项组成。数据项是具有独立含义的最小标识单位。例 如，每个学生记录又可由学号、姓名、性别等数据项组成。数据元素的集合构成一个数据对象，它是针对某种特定的应用。3.什么是数据结构数据结构指某一数据元素集合中的所有数据成员之间的关系。完整的定义为：数据结构=D,R,M 其中，D是某一数据元素的集合；R是该集合中所有数据成员之间的关系的有限集合；M是作用在该集合所有数据成员之上的方法(或操作)。4.数据结构的三个要素数据结构是指数据元素间的逻辑关系，即数据的逻辑结构。数据逻辑结构的要点是：令数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；令数据的逻辑结构可以看作是从具体问题抽象出来的数据模型(面向应用的)；令数据的逻辑结构与数据元素本身的形式、内容无关；令数据的逻辑结构与数据元素的相对存储位置无关。数据的物理结构是数据元素及其关系在计算机存储内的表示，也称为数据的存储结构。作用于数据结构上的运算是讨论数据结构的另一个重要方面。讨论数据结构必须讨论相 关的操作。操作的实现依赖于相应的存储结构。图1.1是它们之间的关系。逻辑结构|私用操作集|他用 访问 D映射到俑用 一|公用操作集|物理结构图1.1数据结构三个要素的关系5.数据逻辑结构的分类数据的逻辑结构通常划分为线性结构、树形结构、图结构和集合结构。如图1.2所示。-3-a 线性结构（b 集合结构图1.2数据逻辑结构的分类线性结构中元素之间的关系是一对一的关系，集合结构中元素之间的关系为空，树形结 构中元素之间的关系是分层的一对多的关系，图结构中元素之间的关系是多对多的关系。这4种关系中集合结构的实现往往采用其他逻辑结构的存储表示。6.数据存储结构的分类数据存储结构分为4类：顺序存储表示、链接存储表示、索引存储表示、散列存储表示。7.数据类型与抽象数据类型数据类型是一组性质相同的值的集合，以及定义于这个值集合上的一组操作的总称。数 据类型可分为两大类：基本数据类型和构造数据类型。基本数据类型可以看作是计算机中已实现的数据结构。例如，C语蕾中的基本数据类型 有字符型（char、整型（int、浮点型（float、双精度型（double 和无值（void,可直 接使用由它们定义的变量和相应的操作。构造数据类型由基本数据类型或构造数据类型组成，在应用中可视为一种数据模型。构 造数据类型由不同成分类型构成，在C语言中用typedef struct来定义。数据类型和数据结构的共同点在于它们都有其抽象性，它们并不特指适用于何处，就像 利用半径求圆周的公式一样，想用到哪里就可放到哪里。数据类型与数据结构之间的区别在于数据结构本身是一种数据的组织形式和使用形式，通过把它定义成数据类型才能在计算机上使用。从这个意义上来看，数据类型是从编程者使 用的角度可由计算机实现的数据结构。注意，数据类型本身不能参加运算，必须定义属于某 种数据类型的变量，使用这些变量才能参与运算。抽象数据类型由用户定义，用以表示应用问题的数据模型。抽象数据类型由构造数据类 型组成，包括数据的组成和一组相关的服务（或称操作）。抽象数据类型的三大特征是信息隐蔽、数据封装、使用与实现相分离。面向对象方法中 的类（class 完美地实现了抽象数据类型。1.2.2 算法及算法分析1.算法的概念所谓算法,就是基于特定的计算模型在信息处理过程中为了解决某一类问题而设计的一 个指令序列。算法的5个要素是令有输入：待处理的信息，即用数据对具体问题的描述；令有输出：经过处理后得到的信息，即问题的答案；令确定性：对于相同的输入数据，算法执行确定的预设路线，得到确定的结果；令可行性：算法的每一基本操作都可以实施，并能够在常数时间内完成；令有穷性：对于任何输入，算法都能经过有穷次基本操作得到正确的结果。2.设计算法的三个阶段设计算法通常经过三个主要阶段 1 从问题出发，寻找可能的解决方案，结合计算机选择合适的算法；2 建立解决问题的数据模型和程序框架，并用伪代码描述一系列步骤；-4-(3)细化程序框架，用程序设计语言写出完整的数据结构和程序代码。3.算法的性能分析设计算法就是为了求解问题。算法的效率是衡量是否具有可计算性的关键。性能分析的 目的就是要了解算法的效率。性能，指算法功能实际执行的功效或表现如何。主要从算法执 行的时间和空间效率进行分析。(1)时间复杂度算法的时间复杂度度量是通过统计算法的每一条指令的执行次数和执行时间得到的。因 此，算法的时间代价的计算公式为：算法的执行时间=算法中每条语句执行时间之和；每条语句的执行时间二该语句的执行次数(或频度)X该语句执行一次所需时间；语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量,很难确 定，因此设每条语句执行一次所需时间为单位时间。则一个算法的运行时间二该算法中所 有语句的执行次数(或频度)之和。例如，有一个求两个n阶方阵的乘积C=AXB的算法，其执行次数如表1.1所列。表1.1程序语句语句执行次数void MatrixMultiply(int A,int B,int C,int n)tint i,j,k;for(i=0;i n;i+).n+1for(j=0;j n;j+)f.n(n+l)iCij=o；.n2for(k=0;k n;k+).n2(n+l)Cij=Cij+Aik*Bkj;)；.n3总 计.2n3+3n2+2n+l(2)渐进时间复杂度：大0表示法算法中所有语句的频度之和是矩阵阶数n的函数T(n)=2n3+3n2+2n+1称n是问题的规模。则时间复杂度T(n)是问题规模n的函数。当n趋于无穷大时，称时 间复杂度的数量级为算法的渐进时间复杂度T(n)=0(n3)一 算法的大0表示大0表示表明当n-8时，T(n)的变化趋势。教科书上对大0表示的较严格的定义是：如果存在正常数。、N和一个函数/(九)，使得对于任何几N,都有T(n)aX/(n)则可以认为在n足够大之后，/伽)给出了 T(0的一个上界，记为T二01(初事实上，大0表示给出了算法执行效率的一个保守的估计，即对于规模为n的任意输 入，算法的执行时间都不会超过0(/(0)。对于表1.1所示的例子，其大0表示为T(n)=0(n3)在分析一个程序的渐进时间复杂性时，我们需要抓关键操作，为此需要分解程序结构。在程序的许多并列的程序段中找出最复杂的程序段，特别是包括多层嵌套循环的程序段，其 最内层循环中的执行语句即为关键操作。分析关键操作的执行次数，就可直接得到大0表-5-示的结果。例如，表1.1所示程序最内层循环中执行语句Cij=Ci|j+Aik*Bk|j 就是关键操作，它的执行次数为d,则整个程序的大0表示为0 1?,这样不必再一条语句 一条语句做繁琐的计算。3 空间复杂度空间复杂度是对算法的存储效率的度量。算法所用存储存储空间可分为两大部分：固定 部分和可变部分。存储空间的固定部分主要包括程序指令代码所占用的空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占用的空间等。这部分空间可以通过 程序分析很容易地统计出来。存储空间的可变部分主要包括尺寸与问题规模有关的成分变量 所占用的存储空间、递归栈所占用的存储空间、通过malloc和free命令动态使用的存储空 间等。这部分存储空间需要分析程序的执行过程才能统计出来。通常，空间复杂度的度量只是在相同功能的不同算法之间比较优劣时才使用。在这种情 况下，一般比较它们完成功能时所需的附加存储空间即可。4 不同大。表示的比较表1.2显示了不同的函数（=/（九）当n增大时的增长趋势。如果一个算法的时间复杂度 达到O log2n,就说明这个算法具有很高的时间效率,如果一个算法的时间复杂度达到O n!,一旦n变大，算法的运行时间将达到不可计算的程度。因此，如果用“V”表示优于，则有c log2n n nlog2n n2 n3 2n 3n l(3)n(n+l)(2n+l)nln少二i=lxn+1-l x-1xwl,n06【参考答案】证明过程如下。(1)当n=l,=+D成立。设当n=k时公式成立,即i=i 2 i=i 2-8-当口=1+1 时，i=i+(k+l)=处W+k+l=(k+D(k+2),结论成立。i=i i=i 2 2(2)当 n=l,*=i=i=l1*(1+1)*(2*1+1)成立.6k设当n=k时公式成立，即Xi?i=lk+1 k当 n=k+l 时,=/+(k+l)2 i=l i=lk*(k+l)*(2*k+l)6k*(k+l)*(2*k+l)+(k+iy6_(k+l)(2k2+k+6k+6)_(k+1)(21?+7k+6)6 6_(k+l)(k+2)(2k+3)_(k+l)(k+1)+l)(2(k+1)+1)6 6结论成立。0(3)当 n=0,i=0Yo+i i父=1=成立,x-1k v k+1 i设当n=k时成立,i=0 X 1k+l k k+1 当口=卜+1 时，fxi=fxi+xk+l=+xk+l i=0 i=0 X-1结论成立，这实际上就是求等比级数的和。证毕题1.2.14设n为正整数，分析下列各程序段中加下划线的语句的执行次数。(1)int i,j,k;for(i=1;i=n;i+)for(j=l;j=n;j+)ciU=0.0;for(k=1;k=n;k+)(2)int i,j,k,x=0,y=0;for(i=1;i=n;i+)for(j=l;j=i;j+)for(k=1;k I2,算法A2好于Ai令 当n=2时，22=22,算法Ai与A2相当-9-令当n=3时，23 42,算法A2好于Ai令当n4时，2nn2,算法A2好于A1令当n-8时，算法A2在时间上显然优于A1。另一种解法是对算法Ai和A2的时间复杂度Ti(n)和T2(n)取对数，得nlog2和21ogn,用 大 0 表示，有 Ti(n)=O(n),T2(n)=O(logn)o 显然，算法 A?好于 Ai。题1.2.16按增长率由小至大的顺序排列下列各函数：2100,(3/2)11,(2/3,，(4/3)n,nl n3/2,n2/3,右,n!,n,log2n,n/log2n,2(log2n),log2(log2n),nlog2n,口喝11。【参考答案】各函数的排列次序如下：(2/3)1 2100,Iog2(log2n),login,(log2n)2,Vn，n2/3,n/login,n,nlog2n,n3/2,(4/3)n,(3/2)n,nlog2n，n!,nno题1.2.17已知有实现同一功能的两个算法，其时间复杂度分别为0(2)和O(n10),假设 计算机可连续运算的时间为O秒(100多天)，又每秒可执行基本操作(根据这些操作来估 算算法时间复杂度)1()5次。试问在此条件下，这两个算法可解问题的规模(即n值的范围)各为多少？哪个算法更适宜？请说明理由。【参考答案】根据假设，计算机可连续运行IO7秒，每秒可执行基本操作1()5,那么计 算机可连续执行基本操作1。7*1()5=1012次。在此能力限制下，算法1的时间复杂性为0(2,则可求得问题规模nWlog2(H)i2)=i21og210；算法2的时间复杂性为0(储),则其问题规模 n(1012)01o显然，算法1适用的问题规模范围更大些，更适宜些。由此得到一个结论：虽 然在一般情况下，多项式阶的算法比指数阶的算法能更快解决问题，但高次多项式的算法在 n的范围上还不如指数阶的算法。题1218试举一个例子，说明对相同的逻辑结构，同一种运算在不同的存储方式下实 现，其运算效率不同。【参考答案】例如，线性表中的插入和删除操作，在顺序存储方式下平均移动近一半的 元素，时间复杂度为0(n)；而在链式存储方式下，插入和删除时间复杂度都是0(1)。题1.2.19运算是数据结构要讨论的一个重要方面。试举一个例子，说明两个数据结构 的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的 特性，是两个不同的结构。【参考答案】例如，栈和队列的逻辑结构相同，其存储表示也可相同，无论是顺序存储 表示还是链接存储表示，但由于其运算集合不同而成为不同的数据结构。题1220指出下列各算法的功能并求出其时间复杂度。(1)int Prime(int n)int i=2,x=(int)sqrt(n);sqrt(n)为求 n 的平方根while(i x)return 1;else return 0;)；(2)int sum 1(int n)int p=1,s=0;for(int i=1;i=n;i+)-10-p*=i;s+=p;return s;)；(3)int sum2(int n)int s=0;for(int i=1;i=n;i+)int p=1;for(int j=1;j=i;j+)p*=j;s+=p；)return s;)；(4)int fun(int n)int i=1,s=1;while(s n)s+=+i;return i;)；(5)void mtable(int n)for(int i=1;i=n;i+)for(int j=i;j=n;j+)cout i j setw(2)i*j cout endl;)；【参考答案】(1)判断整数n是否素数，如果是则函数返回1,否则返回0。算法时间复杂性T(n)二。(布)。(2)计算i!,即1,1*2,1*2*3,!*2*3*4,l*2*3*n的和。算法时间复杂性T(n)=i=lO(n)o(3)同样计算fi!。算法时间复杂性T(n)=O(n2)。这是因为没有像上题那样保留计算 i二l的中间结果，每次都重新计算1*2*i,程序步数达到二=里*2=0.2)i=l j=l i-l,(4)求出满足不等式1+2+3+i2n的最小i值。例如，n=100,当i=14时，满足 1+2+-+13=91100,1+2+14=1052100。从i(i-l)/2Vn可得，i2-i-2n0,用代数法求解得.1 J1+8口1 data得到该结点的数据值，用p-link或p-next得到该结点所 保存的链表下一结点的地址。用p+可以让指针p指向物理上的下一结点，但p+与p-link 可能不相等，因为p-link指示的是p所指示结点的逻辑上的下一结点，而一个链表结点的 逻辑上的下一个结点不一定是物理上的下一个结点。如果有两个指针p和q都是链表结点指针，它们的初始状态如图1.3(a)所示。语句p=q的执行结果如图1.3(b)所示，由于地址的传送，p也指向q所指向的结点。语句q=p-link的执行结果如图1.3(c)所示,把p所指示结点的link域内保存的结点地 址赋给指针q，使得指针q指向p的下一结点。最后，语句p=p-link就是链表操作中常用的让指针p进到链表下一结点的语句，如 图1.3(d)所示。(a)(b)p=q(c)q=p-link(d)p=p-link图L3指针操作-13-第3章栈、队列和多维数组3.1 栈和队列的基本概念栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其访问规则较 线性表有更多的限制，故又称它们为访问受限的线性表。3.1.1 知识点复习1.栈的定义及基本运算通常，栈(Stack)可定义为只允许在表的末端进行插入和删除的线性表。允许插入 和删除的一端叫做栈顶(top),而不允许插入和删除的另一端叫做栈底(bottom)。当栈 中没有任何元素时则成为空栈。由于栈只能通过在它的栈顶进行访问，因此，栈又叫做后进先出(LIFO,Last In First Out)的线性表。栈的基本运算包括(1)栈初始化voidinitStack(Stack&S)：创建一个空栈S并使之初始化。(2)判栈空否bool isEmpty(Stack&S)：当栈S为空栈时函数返回true值，否则返回 false 值。(3)进栈bool Push(Stack&S,type x)：当栈S未满时，函数将元素x加入并使之成 为新的栈顶，若操作成功，则函数返回true值，否则函数返回false值。(4)出栈bool Pop(Stack&S,type&x)：当栈S非空时，函数将栈顶元素从栈中退出 并通过引用参数x返回退出元素的值。若操作成功，则函数返回true值，否则函数返回 false 值。(5)读栈顶元素bool getTop(Stack&S,type&x)：当栈S非空时，函数将通过引用参 数x返回栈顶元素的值(但不退出)。若操作成功，则函数返回true值，否则函数返回false 值。利用上述5种基本运算，可以实现基于栈结构的应用问题的求解。2.队列的定义及基本运算队列(Queue)是另一种限定存取位置的线性表。它只允许在表的一端插入，在另一 端删除。允许插入的一端叫做队尾(rear),允许删除的一端叫做队头(front)o新的元素每次都在队尾加入，且最早进入队列的元素最先退出队列。队列所具有的 这种特性就叫做先进先出(FIFO,First In First Out)。队列的基本运算包括：(1)队列初始化void initQueue(Queue&Q)：创建一个空的队列Q并初始化。(2)判队列空否bool isEmpty(Queue&Q)：当队列Q为空时函数返回true值，否则 返回false值。(3)进队列bool enQueue(Queue&Q,type x)：当队列Q未满时，函数将元素x加入 并使之成为新的队尾，若操作成功，则函数返回true值，否则函数返回false值。(4)出队列bool deQueue(Queue&Q,type&x)：当队列Q非空时，函数将队头元素 从队列中退出并通过引用参数x返回退出元素的值。若操作成功，则函数返回true值，否则函数返回false值。(5)读队头元素bool getFront(Queue&Q,type&x)：当队列Q非空时,函数将通过引 用参数x返回队头元素的值(但不退出)。若操作成功，则函数返回true值，否则函数返 回false值。-43-同栈样，利用队列的5种基本运算就可以完成基于队列的各种运算。3.理解栈和队列的要点(1)栈操作Pop(S,x)与getTop(S,x)是有区别的。前者退出栈顶的元素，因此每执行 一次Pop操作，栈中的元素个数就少一个；后者仅复制出一份栈顶元素，栈中元素个数 不发生变化。(2)当一串元素通过栈时，出栈元素的次序如何排列，与进栈和出栈操作的排列组合 有关。如果每个元素进栈后立即出栈，所有出栈元素的排列与进栈顺序完全相同；如果 所有元素都进栈后才开始出栈，所有出栈元素的排列与进栈顺序完全颠倒。(3)队列操作deQueue(Q,x)与getFront(Q,x)是有区别的。前者退出队列的队头元素，因此每执行一次deQueue操作，队列中的元素个数就少一个；后者仅复制出一份队头元 素，栈中元素个数不发生变化。(4)当一串元素通过队列时，无论其入队和出队操作如何组合，最后输出的元素的次 序都与入队时相同。(5)栈和队列的进出规则：利用铁路调车轨道的栈式结构分析，当列车车厢按照1,2,.,n的编号进栈时，可能的不同出栈序列数目的计算可利用Catalan函数算出：1 1(2n)!n+1 匕11 n+1 n!xn!而列车车厢按照编号1,2,3,.,n进队列时，可能的出队列序列只有一种，该序列中 各元素的编号仍然是1,2,3,3.1.2 关键问题点拨1.栈是一种先进后出的顺序存取结构，它是顺序存储结构吗？【点拨】顺序存取和顺序存储是两个不同的概念。顺序存取是指只能逐个存或逐个取 结构中的元素，例如栈只能在栈顶位置存或取；顺序存储是指利用一个连续的空间相继 存放结构中的元素，例如栈可基于一维数组存放栈的元素。2.一个较早进栈的元素能否先于在它之后进栈的元素从栈中取出？【点拨】如果它进栈后一直未退出，在它之后进栈的元素一旦压在它的上面，它就不 能先于后进栈的元素取出。如果在它之后要进栈的元素还未进栈，它是可以退出的。3.一般来讲，只允许栈顶元素从栈中退出，在什么情况下元素可以从栈底泄出？【点拨】在操作系统中设计调度算法时有此特例。4.以1,2,.,n的顺序进栈，如何判断可能的出栈序列？【点拨】要注意各进栈元素出栈的时机。假如5先于3和4出栈，那么3就不可能在 4之前出栈，因为4 一定压在3的上面。分析可能的出栈序列有多少，类似于分析不同 二叉树有多少，最终推导出Catalan函数。5.队列具有先进先出的特性，可不可以加塞，在队列其他位置进出队列？【点拨】不可以。队列与栈同属限制了存取位置的顺序存取结构，如果允许在其他位 置进出队列，它就成为普通的线性表，而不是队列了。6.以1,2,.,n进队，可能的出队序列有多少？【点拨】可能的出队序列只有一种，各元素的出队顺序与进队顺序相同。7.栈、队列和向量(一维数组)有什么不同？【点拨】栈和队列是顺序存取的，向量是直接存取的。8.双端队列有何特点？【点拨】双端队列允许在队列的每一端进队和出队。这相当于同时存在两个队列或两 个栈，甚至栈和队列交织在一起，比一般的栈和队列要复杂。9.优先级队列有何特点？【点拨】优先级队列在队尾插入，在队头删除。但每次出队的元素总是队列中优先级-44-最高的元素。为此，每个新元素进队后总要调用一个调整算法，按元素的优先级调整到 适当位置。所以这种队列不是先进先出的，在实现上需要使用第4章介绍的“堆，3.1.3 选择填空题解析题3.1.1栈的插入和删除操作在（）进行。A.栈顶 B.栈底 C.任意位置 D.指定位置【解析】选A。栈的定义要求在栈顶插入与删除。题 3.1.2 对一4初始为空的栈 s 执行操作 Push s,5,Push s,2,Push s,4,Pop s,x,getTop s,x 后，x 的值应是（oA.5 B.2 C.4 D.0【解析】选B。连续3次进栈后，栈内数据为5,2,4,经过1次退栈，栈内还有5,2,栈顶读到x中应为2。题3.1.3用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234,为了 得到1342出栈顺序，相应的S和X的操作序列为（oA.SXSXSSXX B.SSSXXSXX C.SXSSXXSX D.sxssxsxx【解析】选D。用排除法选择答案。选项A、B、C所得出栈序列分别为1243、3241、1324,都不是正确答案。选项D得到的出栈序列为1342。题3.1.4假设一个栈的输入序列是1,2,3,4,则不可能得到的输出序列是（）。A.1,2,3,4 B.4,1,2,3 C.4,3,2,1 D.1,3,4,2【解析】选B。借用上一小题的符号，用S表示进栈操作，用X表示出栈操作，则 选项A、C和D的输出序列可以分别用操作序列sxsxsxsx、ssssxxxxx、SXSSXSXX,这都是合法的操作序列。只有选项B的输出序列找不到合法的操作序列。题3.1.5已知一个栈的进栈序列为1,2,3,其输出序列的第一个元素是i,则第j个出栈元素是（）。A.j-i B.n-i C.j-i+1 D.不确定【解析】选D。当i第一个出栈时，1,2,1都压在栈内，之后还可能有i之后的元素进栈，究竟第j个出栈元素是哪个，不一定。题3.1.6已知一个栈的进栈序列为1,2,3,n,其输出序列是pi,P2,P3,Pno若 Pi=n,贝ll pi的值是（）。A.i B.n-i C.n-i+1 D.不确定【解析】选C。当第一个出栈元素是n时，1,2,3,都压在栈内，后续出栈的元素依次为n-1,n-2,第i个出栈元素应是n-i+1 题3.1.7已知一个栈的进栈序列为1,2,3,，n,其输出序列是pi,p2,P3,小。若 Pl=3,则 p2 的值（oA.一定是2 B.一定是1 C.可能是1 D.可能是2【解析】选D。当第一个出栈元素为3时，1,2 一定压在栈内，下一个出栈的元素可 能是2,不可能是1。当然也可能2暂不出栈，4,5,.进栈，所以第二个出栈的元素也可 能不是2。题3.1.8已知一个栈的进栈序列为pi,P2,P3,，Pn，其输出序列是1,2,3,，n0若 P3=1,则 P1 的值（）A.一定是2 B.可能是2 C.不可能是2 D.一定是3【解析】选C。当p3=l时，输入序列为pi,p2,1邛4,，因为输出的第一个元素是 1,则Pl,P2一定在栈内。如果下一个出栈的是P2，可以断定P2=2,则pi不可能是2。当然可能是3,但不一定是3：也许P1暂不出栈，p4,P5,Pi=3进栈，Pi再出栈。-45-题3.1.9已知一个栈的进栈序列为pi,P2,P3,，Pn，其输出序列是1,2,3,no若 P3=3,则 P1 的值()oA.一定是2 B.可能是2 C.不可能是1 D.一定是1【解析】选B。当p3=3时，输入序列为pi,p2,3,p4,，因为输出的第三个元素是 3,则有多种可能：当P1=1，P2=2时，允许的进/出栈顺序是P1进栈P1出栈P2进栈P2 出栈。当Pl=2,P2=l时，允许的进/出栈顺序是Pl进栈P2进栈P2出栈Pl出栈。如果 Pl P2、3进栈不出，P4=2,P5=l，允许的进出栈顺序可以是P4进栈P5进栈P5出栈P4 出栈。因此可以断定P1=1或P1=2是可能的选择，但不是一定的选择。题3.1.10已知一个栈的进栈序列为P1，P2，P3,Pn，其输出序列是1,2,3,若 Pn=1,则 P1 的值()A.n-i+1 B.n-i C.i D.不确定【解析】选A。当pn=l时,输入序列为Pl,P2,P3,P4,Pn-l,1，因输出序列为1,2,3,n,所以第一次输出1时,pi,p2,p3,p4,都应在栈内，这样可得pn-l=2,Pn-2=3,，pn.i=i+1,，Pi=n-i+l。3.1.4 综合应用题选讲题3.1.11请综述栈的基本性质。【参考答案】栈的基本性质如下：(1)集合性。栈是由若干个元素集合而成，没有元素的空集合称为空栈；线性。除栈底和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；运算受限。只允许在栈顶实施进栈或出栈操作，且栈顶位置由栈顶指针指示；数学性质。当多个编号元素依某种顺序进栈，且可任意时刻出栈时，所获得的编号元素排列的数目，恰好满足Catalan函数的计算，即1 pn 1(2n)!n+2n-n+i(叫2.其中，n为编号元素的个数。A72 3 4 fv题3.1.12若一个栈的输入序列为1,2,输出序列的第一个元素是n,贝悌i个输出元素是什么(iWiWn)?【参考答案】n-i+晨按照题意，输出序列应该是n,(n-l),(n-2),.,1,需要把1,2,.,(n-1)一个一个压在底下，再后进先出地一个一个退出栈。这样，第1个进的第n 个出，第2个进的第n-1个出，第3个进的第n-2个出，依次类推，可知第i个 进的，第n-i+1个出。题3.1.13铁路进行列车调度时，常把站台设计成栈式结构的站台，如图3.1所示。试问：(1)设有编号为1,2,3,4,5,6的六辆列车，顺序开入 栈式结构的站台，则可能的出栈序列有多少种？(2)若进站的6辆列车顺序如上所述，那么是否能够得到435612,325641,154623和135426的出站序列,如果不能，说明为什么不能；如果能，说明如何得到(即写出“进栈”或“出栈”的序列)。【参考答案】(1)编号为1,2,3,4,5,6的6辆列车顺序开入栈式结构站台，可能的不同出栈序列有1n+1 2n1 12x11x10 x9x8x77 6x5x4x3x2xl=132 种。6+1(2)不能得到435612和154623这样的出栈序列。因为若在4,3,5,6之后再将1,2出栈，贝IJ 1,2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先-46-于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。题3.1.14试证明：若借助栈可由输入序列1,2,3,，n得到一个输出序列pi,p2,P3,，Pn(它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存 在ivjvk,使得PjVpLPi。(提示：用反证法)【参考答案】证明过程如下。(1)必要性：按照题意，当ivjk时进栈顺序是i、j、k,这3个元素出栈的相对顺序是Pl、Pj、Pk。例如，当i=l,j=2,k=3时一个合理的出栈序列是pi=2,pj=3,pk=1。如果Pj Pk p成立，意味着出栈顺序为3、1、2,这恰恰是不可能的。当较大的数首先出栈时，那些 较小的数都是降序压在栈内的，如2、1,这些数不可能如1、2那样正序出栈。(2)充分性：如果PjVpkR成立，表明当ivjvk时各元素进栈出栈后的相对顺序为pj、pk、Pio 现做具体分析：当ivj时PjPi，表明pj是在pi进栈后进栈并压在pi上面，且pj在pi出栈前出栈；当jvk时pjVpk，表明pj必须在pk入栈之前就出栈，否则Pj就被压在Pk下面了；当ivk时pkpi，表明Pi是先于Pk进栈的。综上所述可知：这与正确的出栈顺序P1Pj XL分别代表endl端的进队和出队，XR代表end2端的出队。表3.1输出序列进队出队顺序输出序列进队出队顺序1,4,2,3SLXRSLSLSLXLXRXR3,1,2,4SLSLSLXLXRSLXRXR-47-2,4,1,3SLSLXLSLSLXLXRXR 4,1,2,3SLSLSLSLXLXRXRXR3,4,1,2SLSLSLXLSLXLXRXR4,1,3,2SLSLSLSLXLXRXLXR3,1,4,2SLSLSLXLXRSLXLXR4,3,1,2SLSLSLSLXLXLXRXR还有2种是不可能通过输入受限的双端队列输出的，即4,2,1,3和4,2,3,lo 再看输出受限的双端队列。假设endl端和end2端都能输入，仅end2端可以输出。如果都从end2端输入，从end2端输出，就是一个栈了，当输入序列为1,2,3,4,输出序 列可以有14种。对于其他10种不能输出的序列，通过交替从endl和end2端输入，还 可以输出其中8种。设SL代表endl端的输入，SR、XR代表end2端的输入和输出，则可 能的输出序列及进队和出队顺序如表3.2所示。表3.2输出序列进队出队顺序输出序列进队出队顺序1,4,2,3SLXRSLSLSRXRXRXR 3,1,2,4SLSLSRXRXRXRSLXR 2,4,1,3SLSRXRSLSRXRXRXR 4,1,2,3SLSLS