数据结构主要知识点广东湛科院.doc

《数据结构主要知识点广东湛科院.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构主要知识点第一部分：1、数据是客观事物的符号表示，在计算机科学中是指所有能输入到算机中并被计算机所处理的符号的总称。2、数据对象是性质相同的数据元素的集合。3、数据结构是相互间存在一种或多种特定关系的数据元素的集合。4、数据结构的四种基本形式是：集合、线性结构、树形结构和图状结构或网状结构。5、数据类型是一个值的集合和定义在这个值集上的一组操作的总称。6、顺序存储结构的特点是：1）占用一块地址连续的内存单元；2）用存储位置的物理相邻表示数据间的逻辑相邻；3）可以实现随机存取。7、链式存储结构的特点是：1）动态分配存储空间；2

2、）用指针表示数据间的逻辑关系；3）不能实现随机存取。8、算法是对特定问题求解步骤的一种描述、是指令的有限序列。9、算法满足以下5个性质：1）输入：一个算法可以有0个或多个输入；2）输出：一个算法要有一个或多个输出；3）有穷性：一个算法必须在执行有穷步骤后结束，每一步骤也必须在有限时间内完成；4）确定性：算法中的每一步骤都有明确的含义，没有二义性；5）可行性：算法中描述的每一个操作，都可以通过已经实现的基本运算，执行有限次后完成。10、算法的四项基本要求是：1）正确性、可读性、健壮性和效率与低存储需量。2）评价算法时间效率的指标是时间

3、复杂度。3）时间复杂度是用算法中基本操作的重复执行次数与问题规模之间的函数关系，来描述算法的时间效率。但由于难以求得基本操作的重复执行次数与问题规模之间的精确的解析的函数关系，所以算法时间复杂度通常用问题规模（n）的某类函数的阶来表示。评价算法空间效率的指标是空间复杂度。11、五种常见的算法时间复杂度是：常量阶、线性阶、对数阶、多项式阶和指数阶。12、描述以下三个概念的区别：头指针、头结点、第一个元素结点。第一个元素结点是指链表中存储线性表中第一个数据元素的结点。为操作方便，通常在链表的第一个结点之前附设一个结点，称为头结点，该结点

4、的数据域不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对第一个元素结点进行同一处理。头指针是指向链表中第一个结点（或为头结点或为第一个元素结点）的指针。若链表中附设头结点，则不管线性表是否为空，头指针均不为空，若链表中不设头结点，则空链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。13、在顺序表中插入或删除一个元素，需要平均移动表长一半的元素，具体移动元素的个数与表长和该元素在表中的位置有关。在单链表中，除第一个数据元素结点外

5、，任一结点的存储位置由其直接前驱结点的指针域的值指示。在单链表中设置头结点的作用是插入和删除第一个数据元素结点时不必进行特殊处理。第二部分：1、已知L是无表头结点的单链表，且P结点即不是第一个结点也不是最后一个结点，试写出实现下列操作的语句序列：1)在Ｐ结点后插入Ｓ结点S->next=P->next;P->next=S;2)在Ｐ结前后插入Ｓ结点Q=p;P=L;while(P->next!=Q)P=P->next;S->next=P->next;P->next=S;3)在表首插入S结点S->next=L;L-S;4)在表尾插入S结点P

6、=L;while(P->next!=NULL)P=P->next;S->next=P->next;P->next=S;2、已知L是带表头结点的单链表，且P结点即不是第一个结点也不是最后一个结点，试写出实现下列操作的语句序列：1）删除P结点直接后继结点Q=p->next;P->next=P->next->next;free(Q);2）删除P结点直接前驱结点Q=p;P=L;while(P->next->next!=Q)P=P->next;Q=p->next;P->next=P->next->next;free(Q);3）删除P结点Q=P

7、;P=L;while(P->next!=Q)P=P->next;P->next=P->next->next;free(Q);4）删除第一个数据元素结点P=L;Q=P->next;P->next=P->next->next;free(Q);5）删除最后一个数据元素结点while(P->next->next!=NULL)P=P->next;Q=p->next;P->next=P->next->next;free(Q);第三部份：1、顺序栈的存储结构定义#defineSTACK_INIT_SIZE100typedefstruct{//这里

8、SElemType的类型根据具体情况，由程序员自行定义SElemType*base;//栈基址SElemType*top;//栈顶指针intstacksize;//当前已经分配的存储单元，以元素为单位}SqStack;//顺序栈数据类