数据结构知点归纳.doc

一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为:概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。 对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。 数据结构的章节比重大致为： 概论: 概念，时间复杂度。 线性表:基础章节，必考内容之一。概念，算法设计题。 栈和队列:基本概念。 串 :基本概念。 多维数组及广义表 : 基本概念。 树和二叉树 :重点难点章节，各校必考章节。概念，问答，算法设计题。 图:重点难点章节，各校必考章节。概念，问答，算法设计题。 查找 :重点难点章节，概念，问答。 排序 :重点难点章节，问答各种排序算法的排序过程 二、各章节的主要内容： 第一章 概述 主要内容： 本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点: （1）数据结构的基本概念。（数据；数据元素；数据项；数据结构；数据的逻辑结构：线性和非线性，具体分为集合、线性结构、树形结构和图状结构；数据的存储结构：顺序存储和链式存储；运算） （2）算法的度量：时间效率和空间效率，分别用时间复杂度和空间复杂度度量，掌握时间复杂度的度量方法量方法。（大O表示法） 参考题目： 填空题： 1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（ ）和（ ）。 2、数据结构按逻辑结构可分为两大类，它们分别是（ ） 和（ ） 3. 数据的物理结构主要包括（ ）和（ ）两种情况。 4．线性表，栈，队列和二叉树四种数据结构中（ ）是非线性结构，（ ）是线性结构。 5、线性结构中元素之间存在（ ）关系，树形结构中元素之间存在（ ）关系，图形结构中元素之间存在（ ）关系。 6、程序段的时间复杂度是_______。 for(i=1;i=n;i++) { k++; for(j=1;j=n;j++) x=x+k; } 7．下列算法的时间复杂度是_____。 for(i=0;im;i+ +) for(j=0;jn;j+ +) a[i][j]=i； 8．下列算法的时间复杂度是______。 i=s=0; while(sn) { i++; s+=i;} 判断题： 1、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（ ） 2、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （ ） 3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （ ） 第二章 线性表 主要内容： 作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。 线性表一章注意以下几个方面: （1）.线性表的相关基本概念，如:前驱、后继、表长、空表、首元结点，头结点，头指针等概念。 （2）线性表的结构特点，主要是指:除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。 （3）线性表的顺序存储方式及基本运算（插入、删除操作、平均移动次数、时间复杂度）。 （4）线性表的链式存储方式及基本运算（单链表插入、删除，求长度操作、平均移动次数、时间复杂度）。 （5）顺序存储和链式存储的特点，不同之处。 （6）线性表的简单算法题 参考题目： 选择题： 1、线性表是（ ） A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 2、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）。 A．n B．n/2 C．n/3 D．n/4 3、链表不具有的特点是（ ）。 A．随机访问 　　　　B．不必事先估计存储空间 C．插入删除时不需移动元素 D．所需的空间与线性表成正比 4、带头结点的单链表head为空的判定条件是（ ） A．head = NULL； B．head - next = NULL； C．head - next = head； D．head ! = NULL； 5、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ ） A．S-