山东大学2002计算机研究生入学考试专业课辅导班《数据结构》笔记第一章1、基本概念：数据---数据结构：a、逻辑：集合、线性表、树、图b、物理：顺序、链式抽象数据类型（不用写很全的描述）2、算法分析：a、时间复杂性（会分析语句执行次数，比较交换次数。）b、空间复杂性（只在后续的内部排序中提到。）第二章1、线性表的定义、特点。2、顺序存储地址表示：loc(ai)=loc(a1)+(i-1)l.3、链式存储：几种链的相互关系a、一般单链表b、循环单链表（最后空指针指向头）c、双向链表4、算法设计看清题义的描述（有无头接点、结构、不许另外申请额外空间）、不丢失指针，不要遗漏特殊情况。例一，见图，求逆转ifl.link=nillreturn;ifl.link.link=nill,return;p=l.link;q=p.link;r=q.linkwhiler<>nill{q.link=p;p=q;q=r;}q.link=p;l.link=nill,l.link=q;在草纸上将每一步指针画出，可以有效帮助解题第三章1、栈的表示和实现，操作受限的线性表。2、栈的应用（书中的例子不考，不用看）但考试中可以用到栈。3、利用栈实现递归的工作原理（画栈的变化一部分不错要求，此部分为唯一带*号而要掌握的一节）4、队列的定义、表示和实现：a、链式b、顺序---循环队列（假溢出情况而导致循环队列）第四章要求不多，基本概念1、串的基本定义；2、三种存储表示的基本思想：定长顺序存储、堆分配存储、串的块链存储表。第五章1、数组的定义及顺序表示（行先、列先）。2、稀疏惧阵、特殊惧阵（值相同或零元素在距阵的分布有一定规律）的定义、用途、结构表示、三元组。运算（转置、加减乘除）不做要求。3、▲广义表的定义及存储结构表示。画出结构，指出表头表尾。第六章树写算法时可描述一下算法思想和写算法所需要的结构，算法设计题不会超过1/3。1、树的定义、表示方法、求法。2、二叉树的定义、性质及存储（含完全、满二叉树）性质：参数，不同度接点数，父子关系（肯定考，考试时可以用事例来验证一下。）例：n个接点的二叉树有n+1个指针域空间。存储：顺序：按完全二叉树编号；链式：二、三叉。3、▲二叉数的遍历序列及算法。由前序、后序可以唯一确定二叉数。许多其它算法是从此得到的。a)中序递归b)中序非递归用栈（思想--后进先出，先出的要后进）从根开始左子后代压栈的循环退栈访问右自入栈c)按层次遍历，用队列（思想：先进的先出，先出的要先进）图的按广度遍历与此思想相似，按邻接表。掌握方法，遍历结构，算法不做要求5、森林《———》二叉树、一般树《...
