考研专业课之统考计算机蓝宝书(9)

第二章 栈、队列和数组

【考纲解析与应试指导】

栈、队列和数组都属于四大逻辑结构中的线性结构，他们是线性表的变形或者说是在某方面受限制的线性表，栈和队列是操作受限的线性表，数组是数据元素是非原子类型的线性表。对栈和队列的复习要从逻辑结构的特点及其与线性表的不同来入手，栈是只允许在一端进行插入和删除的线性表，队列只允许在一端插入，另一端只允许删除的线性表，这样的限制又决定了他们与线性表的基本操作的不同，要特别注意顺序栈和顺序队列的溢出问题和计数问题；数组一般都是采用顺序存储的方式，采取顺序存储方式就产生了以哪种方式优先存储的问题，在各种方式下元素存取地址的计算问题，大家要掌握特殊矩阵压缩时下标变换的技巧。大纲上的另一个知识点就是栈和队列的应用，根据栈和队列的特点要懂得在什么样的情况下能够使用栈和队列。另外数组除了初始化和销毁之外只能进行存取和修改操作。

栈和队列一般考题以选择题和小分值的综合应用题居多，选择题基本上每年必考的，对于一些经典的考题在习题中都列举出来了。栈的应用考题方面要注意与递归问题的结合。数组的考题以元素计算方面的选择题和特殊矩阵压缩的大题居多。

【核心考点】
堆栈与队列的基本概念、基本操作。
堆栈与队列的顺序存储结构与链式存储结构的构造原理。
在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。
数组的概念、多维数组的实现
对称矩阵和稀疏矩阵的压缩存储

【知识点精讲】
2.1 栈
2.1.1. 栈的定义及基本运算

栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。
对于栈，常做的基本运算有：

• ·2010年迦思佑考研6000词逻辑辨证记忆
• ·2010年迦思佑张纪元考研6000词汇记忆课堂录音
• ·10版研究生英语难句过关-盘内容
• ·【VIP专享】2009新东方考研英语复试听力(音频+讲义)
• ·沪江考研原创：和我一起突破考研长难句1-33
• ·胡敏考研英语词汇-读故事记单词（09最新版）MP3
• ·2010淘金高阶考研英语词汇词典版MP3
• ·2010考研英语阅读理解精读100篇（高分版）文本下载
• ·2009年考研英语大纲词汇
• ·2010考研英语万能作文MP3

• 麦考瑞内部雅思7-7.5分部分题库
• 一月速背6000单词
• 英语口语需要自然流露
• 7月名师讲座
• 点滴积累学英语系列之一