考研数据结构知识点解析

第一章

数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小

标识单位。

数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。

·线性结构：多对多关系。

·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。

·链式存储结构：如链表。

·索引存储结构：·稠密索引：每个结点都有索引项。

·稀疏索引：每组结点都有索引项。

·散列存储结构：如散列表。

·数据运算。

·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。

·常用的有：检索、插入、删除、更新、排序。

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。·原子类型：由语言提供。

·结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。·优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：·算法是正确的；·执行算法的时间；

·执行算法的存储空间（主要是辅助存储空间）；

·算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。

空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。

数据结构重点难点

1. 数据结构重点内容：

什么是数据结构？

数据元素和数据项的基本概念。

4大类逻辑结构。

算法的时间复杂度。

线性结构的基本特征；

在线性表（n个元素）的第i个位置前插入一个元素核心语句；

链表插入的核心语句；

栈 ( Stack )的定义和特点；

栈的操作实现(1) 入栈(2)出栈；

会做入栈出栈的题；实现递归；

队列的定义和特性；

顺序循环队列的表示和实现；

链式队列的存储结构；

判断链队列是否空；

串的基本概念；

串长的求法；

空串和空白串的区别；

串相等的条件；

串联接操作；

串的表示和实现；

数组的两种顺序映象的方式：1)以行序为主序，2)以列序为主序；

稀疏矩阵的压缩存储；

广义表的定义；

广义表的长度定义；

广义表的深度定义； 非空广义表的表头、表尾；

二叉树的定义；

二叉树的特点；

二叉树的性质；

二叉树的第i层上至多有多少个结点；

深度为k的二叉树中至多含有2k-1个结点；

二叉树的先（根）序遍历；

二叉树的中（根）序遍历；

二叉树的后（根）序遍历；

线索二叉树的生成——线索化；

森林与二叉树的转换；

树与二叉树的转换；

树的先根遍历和后根遍历；

Huffman树定义；

构造Huffman树的步骤并会做题；

Huffman树编码；

图的结构定义；

图的数组(邻接矩阵)存储表示并会做题；

图的邻接表存储表示并会做题；

有向图的十字链表存储表示并会做题；

深度优先搜索遍历图；

广度优先搜索遍历图；

普里姆算法求最小生成树；

克鲁斯卡尔算法求最小生成树；

求每一对顶点之间的最短路径；

顺序表的查找；

有序表的折半查找；

有序表的折半查找适用条件；

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

◆ 数据：指能够被计算机识别、存储和加工处理的信息载体。

◆ 数据元素：就是数据的基本单位，在某些情况下数据项组成。

◆ 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

◆ 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

◆ 逻辑结构：指各数据元素之间的逻辑关系。

◆ 存储结构：就是数据的逻辑结构用计算机语言的实现。

◆ 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。

◆ 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

◆

例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。

那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?

是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?

这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。(所以各位赶快学C语言吧)。

最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

一、填空题

1.数据结构基本概念：研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的一 门课程。（关系、操作两方面缺一不可）

2.双向链表：考点：插入和删除

s

插入s前后指针变化：p->prior->next=s;s->prior=p->prior;

s->next=p;p->prior=s; (前两个和后两个顺序不能颠倒)

P

删除p前后指针变化：p->prior->next=p->next;

p->next->prior=p->prior;

3.串 形参列表 （加粗的作为参考的重点）

StrAssign(&T，chars)：生成一个其值等于chars的串T

StrCopy(&T，S)：由串S复制得到串T

StrEmpty(S)：判断S是否为空

StrCompare(S，T)：比较串S和T

StrLength(S)：返回串S的长度

ClearString(&S)：将串S清空

Concat(&T，S1，S2)：连接串S1和S2，生成新串T

SubString(&Sub，S，pos，len)：返回串S中第pos个字符起长度为len的子串

Index(S，T，pos)：返回主串S中第pos个字符之后子串T第一次出现的位置

Replace(&S，T，V)：用V替换主串S中出现的所有与T相等的不重叠的子串 StrInsert(&S，pos，T)：在串S的第pos个字符之前插入串T

StrDelete(&S，pos，len)：从串S中删除第pos个字符起长度为len的子串

DestroyString(&S)：销毁串S

可能题型：