数据结构重点整理.doc

《数据结构重点整理.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、__________________________________________________考点1算法的时间复杂度(不会出简单的for循环)例题.1下面程序段的时间复杂度为DO(n*log2n)。for(k=1;k<=j;k++)｛inti=1;      while(i<=n) i=i*2;｝O(1)初始化线性表检查线性表是否为空O(n)删除线性表中的所有元素；得到线性表的长度；得到线性表中指定序号为pos的元素；遍历一个线性表；从线性表中查找具有给定值的第一个元素；更新线性表中具有给定

2、值的第一个元素；向线性表中按给定条件插入一个元素；从线性表中删除符合给定条件的第一个元素O(n^2)对线性表进行排序2几种数据结构（数据结构定义：具有结构的数据元素的集合）逻辑结构：集合、线性结构（线性表、广义表、堆栈和队列）非线性结构（树、图）存储结构：顺序存储结构、链式存储结构、索引结构、散列结构等集合和线性结构：1：1树形结构：1：N图形结构：N:N3线性表顺序存储和链接存储的特点顺序存储：随机存取，预先定义表长；插入删除时有大量元素的移动（当下标为1开始的实话移动n-i+1，当下标为0开始

3、的实话移动n-i），查找方便。链式存储：非随机存取，表长不需要预先定义是动态分配，插入删除不需要大量的元素移动，查找时从第一个元素开始查找。4根据线性表的常用操作，选择最合适的存储方式顺序表和链表的比较：空间方面：a当表长难估较大时，选择链式存储b当表长较小时，选择顺序存储时间方面：a插入与删除较多时选择链式存储b查找方面较多时用顺序存储语言方面：当语言没有指针，选用链式存储时选用静态链表（静态链表需要预先设定空间）某线性链表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点,用仅有尾指

4、针的单循环链表存储方式实现这两种操作6链表的特点____________________________________________________________________________________________________例题：链表不具有的特点是（A）。A、可随机访问任意元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比7链表的插入删除8链表各操作的时间复杂度O(1)初始化链表检查链表是否为空O(n)删除链表中的所有元素；得到链表的长度；

5、得到链表中指定序号为pos的元素；遍历一个链表；从链表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向链表中按给定条件插入一个元素；从链表中删除符合给定条件的第一个元素O(n2)对链表进行排序例题：在一个长度为n单链表；在表头插入元素的时间复杂度为O(1)；在表尾插入元素的时间复杂度为O(n)。9栈的特点：先进后出，后进先出。10栈的顺序存储、链式存储的出栈入栈时间复杂度：O(1)13根据给定递归算法和输入求输出（读递归程序）14数组上的循环队列的进队出队操作（参考期中考试最后

6、大题）判空：rear==front满：(rear+1)%MaxSize==front进队操作：rear=(rear+1)%MaxSize;Q(rear)=x出队操作：front=(front+1)%MaxSize;X=Q(front)入队时需先修改入队指针（队尾指针）rear==(rear+1)%QueueMaxSize出队时需要修改队头指针front==(front+1)%QueueMaxSize15链队的插入O(1)voidEnQueue(LinkQueue&HQ,constElemType&

7、item){LNode*newptr=newLNode;if(newptr==NULL){cerr<<“Memoryalocationfailure."<data=item;newptr->next=NULL;if(HQ.rear==NULL)HQ.front=HQ.rear=newptr;elseHQ.rear=HQ.rear->next=newptr;}17稀疏矩阵的定义：其非零元素的个数远远小于零元素的个数。稀疏矩阵的严格定义：稀疏因子d=非零元

8、素/所有元素个数通常认为d£0.3的矩阵为稀疏矩阵三元组表示形式：(i,j,value)i为第i行，j为第j列，value为非0元素的值18广义表的特点规定：大写字母表示广义表名称，小写字母表示原子，广义表非空时：a是广义表的表头head。其余元素组成表尾tail；____________________________________________________________________________________________________广义表中的数据元素有