考研计算机专业基础综合815之严蔚敏《数据结构》考研复习重点笔记及考研真题详解

 

 

复习笔记【节选自识库学习网，如需转载请注明出处】

 

　复习笔记

一、什么是数据结构

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

二、基本概念和术语

1数据

数据是对客观事物的符号表示，是计算机科学中所有能输入到计算机中并能被计算机程序处理的符号的总称。

2数据元素

数据元素是数据的基本单位。

3数据对象

数据对象是性质相同的数据元素的集合，是数据的一个子集。

4数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

（1）数据结构的基本结构

根据数据元素之间关系的不同特性，通常有下列四类基本结构：

①集合。数据元素属于“同一个集合”，并无其他复杂关系。

②线性结构。数据元素之间存在一个对一个的关系。

③树形结构。数据元素之间存在一个对多个的关系。

④图状结构或网状结构。数据元素之间存在多个对多个的关系。

【注意】区分这四种基本结构可以根据元素间的对应关系。

如图1-1所示为上述四类基本结构的关系图。

图1-1　四类基本结构的关系图

（2）数据结构的形式定义

数据结构的形式定义为：

Data_Structure=(D,S)

其中：D表示数据元素的有限集，S表示D上关系的有限集。

（3）数据结构在计算机中的表示

数据结构包括数据元素的表示和关系，在计算机中称为数据的物理结构（又称存储结构）。

其中，关系有两种表示方法：顺序映象和非顺序映象。这两种表示方法对应两种存储结构：顺序存储结构和链式存储结构。

a．顺序映象：用相对位置来表示数据元素之间的逻辑关系。

b．非顺序映象：用指针表示数据元素之间的逻辑关系。

5数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

6抽象数据类型

抽象数据类型（ADT）由一个值域和定义在该值域上的一组操作组成。

【注意】抽象数据类型是对数据类型架构的一种全局体现，使我们能够更加清晰地看待某一数据类型。

7多形数据类型

多形数据类型是指其值的成分不确定的数据类型。

8数据操作的类型

基本的操作主要有：

（1）插入

（2）删除

（3）更新

（4）查找

（5）排序

从操作的特性来分，所有的操作可以归结为两类：

加工型操作：改变了（操作之前的）结构的值；

引用型操作：即不改变结构的值，只是查询或求得结构的值。

上述5种操作中除“查找”为引用型操作外，其余都是加工型操作。

9算法

【定义】算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

【特性】

（1）有穷性

（2）确定性

（3）可行性

（4）输入

（5）输出

【注意】在考试中这五个特性可能出现在选择或者填空题中（通常直接考察其名称）。

考研真题精选

1若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。[计算机统考（408）2010年研]

【答案】D查看答案

【解析】4个选项所给序列的进、出栈操作序列分别为：

选项A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop

选项B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop

选项C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop

选项D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop

按照题目要求，不允许连续三次进行退栈操作，所以选项D所给序列为不可能得到的出栈顺序。

2若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（　　）。[计算机统考（408）2012年研]

A．只有e

B．有e、b

C．有e、c

D．无法确定

【答案】A查看答案

【解析】由题目可知，若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，其中a为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e，而后序遍历的倒数第二个结点为e，说明a的孩子结点只有e。

3循环队列放在一维数组A[0..M－1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（　　）。[计算机统考（408）2014年研]

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M

B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）

C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M

D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）

【答案】A查看答案

【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。

              更多完整版考研资料可转识库学习网