数据结构与算法分析__复习.doc

《数据结构与算法分析__复习.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法分析任课教师：熊太松学院：应用数学学院专业：学号：姓名：第一章绪论名词解释1.算法的定义2数据结构的定义简答题算法的特性有限性确定性可行性1简述数据元素的关系的表示方法与存储结构。方法：顺序映像链非顺序映像储存结构：顺序存储链式存储第二章线性表简答题1线性结构的特点：在数据元素的非空有限集中：1存在唯一的一个被称作第一个的数据元素2存在唯一的一个被称作最后一个的数据元素3除第一个元素外，其他元素只有一个前驱4除最后一个元素外，其他元素只有一个后继2线性表的特点均匀性有序性3描述线性表的

2、顺序表示与链式表示的特点顺序表：逻辑上相邻数据元素，物理存储位置相邻，需要先分配在、再使用链式表：逻辑上相邻数据元素，物理存储不一定相邻，它是前一个元素记录下下一个元素的地址，然后指向下一个，所以不连续，也是动态分配的选择题1.线性表是（A）。2.A．一个有序序列，可以为空B.一个有序序列，不能为空C.一个无限序列，可以为空D.一个无限序列，不能为空2.已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（D）。A.108B.180C.176D.1

3、123.在单链表中删除指针p所指结点的后继结点，则执行（A）。A.p->next=p->next->nextB.p->next=p->nextC.p=p->next->nextD.p=p->next;p->next=p->next->next在顺序表L中第i个位置上插入一个新的元素e：StatusListInsert_Sq(SqList&L,inti,ETe){if(i<1

4、

5、i>L.length+1)returnERROR;if(L.length>=L.listsize){p=(ET*)reall

6、oc(L.elem,(L.listsize+10)*sizeof(ET));if(p==NULL)exit(OVERFLOW);L.elem=p;}for(j=L.length;j>=i;--j)L.elem[j]=L.elem[j-1];L.elem[j]=e;++L.length；returnOK;}程序题1用C语言实现用顺序表示的线性表的插入算法（算法2.4）、删除算法（算法2.5）及合并算法（算法2.7），并分析这三个算法的时间复杂度。2用C语言实现用链式表示的线性表的插入算法（算法2.9）

7、、删除算法（算法2.10）及合并算法（算法2.12），并分析这三个算法的时间复杂度。