2015考研计算机统考（408）《数据结构》重难点精讲

《2015考研计算机统考（408）《数据结构》重难点精讲》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2015考研计算机《数据结构》重难点精讲主讲：杨航空考查目标•1、掌握数据结构的基本概念、基本原理和基本方法。•2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。•3、能够数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。第一章线性表线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。（一）线性表的定义和基本操作（二）线性表的实现1.顺序存

2、储2.链式存储3.线性表的应用难点讲解一、线性表是具有相同数据类型的n(n≥0)个数据元素组成的有限序列。理解线性表的要点是：1）表中元素具有逻辑上的顺序性，在序列中各元素排列有其先后次序。各个数据元素在线性表中的逻辑位臵只取决于其序号。2）表中元素个数有限。3）表中元素都是数据元素。就是说，每一个表元素都是不可再分的原子数据。4）表中元素的数据类型都相同。这意味着每一个表元素占有相同数量的存储空间。5）表中元素具有抽象性。就是说，仅讨论表元素之间的逻辑关系，不考虑元素究竟表示什么内容。难点讲解二、顺序表中数据元素的插入插入一个元素的基本步骤如下：初始表：1）将ai～an顺序向

3、下移动，为新元素让出位臵；2）将item臵入空出的第i个位臵；3)修改表长。在顺序表中进行插入运算的时间复杂度为O(n)在等概率的情况下，任意位臵上插入一个元素，需要移动的元素次数为：=(n+1)/2难点讲解三、顺序表中数据元素的删除在顺序表中删除一个元素需要经过如下步骤：初始表：1）将第i个位臵上的元素删除；2）将ai+1～an顺序向上移动；3）修改表长。在顺序表中进行插入运算的时间复杂度为O(n)在等概率的情况下，任意位臵上删除一个元素，需要移动的元素次数为：=(n+1)/2难点讲解四、顺序表中按值查找数据最简单的方法就是从第一个元素a1起一次和item相比较，直到找到一个

4、与item相等的数据元素。按值查找的评价比较次数为n，时间性能为O(n)。五、顺序表效率分析•时间效率分析：算法时间主要耗费在移动元素的操作上，计算时间复杂度的基本操作：T(n)=O(移动元素次数)移动元素的个数取决于插入或删除元素的位臵。•线性表顺序纯粹结构特点：逻辑关系上相邻的两个元素在物理存储位臵上也相邻；优点：可以随机存取表中任一元素；缺点：在插入、删除某一元素时，需要移动大量元素。难点讲解六、单链表在第1个结点前插入核心语句：newnode->link=first;first=newnode;七、在单链表中间插入核心语句：newnode->link=p->link;p

5、->link=newnode;难点讲解八、在链表末尾插入核心语句：Newnode->link=p->link;p->link=newnode;九、删除不带头结点的单链表中或表尾元素核心语句：q=p->next;P->next=q->next;free(q);难点讲解十、删除不带头结点单链表中第一个元素核心语句：Newnode->link=p->link;p->link=newnode;十一、删除带头结点的单链表核心语句：p->next=q->next;free(q);难点讲解十二、有关指针的一些概念第二章栈、队列和数组栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的

6、，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。难

7、点讲解乊栈的基本特点•不能随意存取栈的任何一个元素，只能存取位于栈顶的元素。•栈又被称为后进先出（LastInFirstOut,LIFO）的线性表，当前能够取出的一定是最好加入的元素。•栈是有长度的，栈的长度等于栈中元素的个数。在递归过程中使用栈时，栈的长度即为递归的深度。•在栈的生存期内栈有三种状态：栈空、栈满和栈非空非满。在栈空情况下出栈操作将无意义；在栈满情况下进栈将出现“溢出”错误。•进栈和出栈时栈顶指针移动的方向是相反的。•栈的变型有“双栈”一种。难点讲解乊队列的基本特点•不能随意