数据结构知识点归纳

《数据结构知识点归纳》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。数据结构的章节比重大致为：1.概论:概念，时间复杂度。2.线性表:基础章节，必考内容之一。概念，算法设计题。3.栈和队列:基本概念。4.串:基本概念。5.多维数组及广义表:基本概念。6.树和二叉树:重点难点章节，各校必考章节。概念，问答，算法设计题。7.图:重点难点章节，各

2、校必考章节。概念，问答，算法设计题。8.查找:重点难点章节，概念，问答。9.排序:重点难点章节，问答各种排序算法的排序过程二、各章节的主要内容：第一章概述主要内容：本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点:（1）数据结构的基本概念。（数据；数据元素；数据项；数据结构；数据的逻辑结构：线性和非线性，具体分为集合、线性结构、树形结构和图状结构；数据的存储结构：顺序存储和链式存储；运算）（2）算法的度量：时间效率和空间效率，分别用时间复杂度和空间复杂度度量，掌握时间复杂度的度量方法量方法。（大O表示法）参考题目：填空题：1、数据

3、结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（）和（）。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;i

4、

5、的重中之重，无论哪一章都涉及到了这个概念。线性表一章注意以下几个方面:（1）.线性表的相关基本概念，如:前驱、后继、表长、空表、首元结点，头结点，头指针等概念。（2）线性表的结构特点，主要是指:除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。（3）线性表的顺序存储方式及基本运算（插入、删除操作、平均移动次数、时间复杂度）。（4）线性表的链式存储方式及基本运算（单链表插入、删除，求长度操作、平均移动次数、时间复杂度）。（5）顺序存储和链式存储的特点，不同之处。（6）线性表的简单算法题参考题目：一、选择题：1、线性表是（）A．一个有限序列，可以为空B．一个有

6、限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空2、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）。A．nB．n/2C．n/3D．n/43、链表不具有的特点是（）。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->next=P->nex

7、t;P->next=SB．P->next=S->next;S->next=P；C．P->next=P;P->next=S；D．P->next=S;S->next=P；6、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）A．Ｏ（1）B．Ｏ（log2n）C．O（n）D．O（n2）7、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（）。A．s->next=p->next;p->next=s;B．q->next=s;s->next=p;C．p->next=s->next;s->nex