简述数据的四种逻辑结构及其特点.docx

1、简述数据的四种逻辑结构及其特点。答案数据的逻辑结构通常有集合结构、线性结构、树型结构、图形结构这4种基本结构。集合结构，数据元素间的关系是“属于同一个集合二集合是元素关系极为松散的一种结构。线性结构，该结构的数据元素之间存在一对一的关系。树型结构，该结构的数据元素之间存在一对多的关系。图形结构，该结构的数据元素之间存在多对多的关系，图形结构也称为网状结构。2、简述数据的四种存储结构及其特点。答案数据结构一般用四种基本的存储结构来表示数据之间的关系。1、顺序存储结构，把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，可以实现随机存取，但要使用一整块存储单元，可能产生较多的外部碎片。2、链式存储结构，该方法不要求逻辑上相信邻的数据元素在物理位置上也相邻，不会出现碎片现象,可以充分利用所有存储单元。缺点是每个元素因存储指针而占用额外的存储空间，只能实现顺序存取。3、索引存储结构，该方法在存储数据元素信息的同时，还建立附加的索引表。优点是检索速度快。缺点是增加附加的索引表占用较多的存储空间。在增加和删除数据时要修改索引表,因而花费较多的时间。4、哈希(散列)存储结构，该方法的基本思想是根据数据元素的关键字直接计算出该数据元素的存储地址。优点是检索、增加、删除结点的操作都很快。缺点是如果散列函数不好,可能出现数据元素存储地址的冲突，而解决冲突会增加时间和空间开销。3、设线性表中数据元素递增有序。试设计一个算法，将X插入到线性表的适当位置上，以保持线性表的有序性，并分析算法的时间复杂度。intinsertElem(Seqlist*L,inti,ElemTypex)intnewsize,i;EIemType*newbase;if(L->length>=L->listsize)(newsize=(L->listsize+LISTINCREAMENT)*sizeof(ElemType);newbase=(ElemType*)realloc(L->elem,newsize);if(!(newbase)returnERROR;1.->elem=newbase;1.->listsize+=LISTINCREAMENT;)for(i=L->length-l;L->elemi>x&&i>=0;i)1.->elemi+l=L->eIemi;1.->elemi+l=x;1.->length+;returnOK;)4、有顺序表A和B,其元素均按从小到大的顺序排列，编写一个算法将它们合并成一个顺序表C,要求C中的元素也是按从小到大排列的。voidMergeList(Seqlist*lc,Seqlistla,Seqlistlb)inti,j,lnea,lenb;ElemTypeel,e2;InitList(Ic);Iena=ListLength(Ia);Ienb=ListLength(Ib);i=l；j=l；while(i<lena&&j<lenb)GetEIem(Ia,I,&el);GetElem(lb,j,&e2);if(el<e2)InSertElem(lc,ListLenth(45Ic)+l,el);i+;)elseInsetElem(lc,ListLenth(*lc)+1,e2);j+;)while(i<=lena)GetElem(la,I,&el);i+;InsertElem(lc,ListLength(*lc)+1,e1);while(i<=lenb)GetElem(Ib,j,&e2);j+;InSertElem(IC,ListLength(5Hc)+1,e2);)4、若对n阶下三角矩阵A,以行序为主序方式将其元素(包括主对角线上所有元素)依次存放于一维数组Bl.n*(n+1)/2+1中，请推导出在B中确定的位置k的映射函数。答案对于下三角中的元素aij,其特点是：j且lin,存储到向量B中后，根据存储原则，它前面有M行，共有1+2+3+i-l=i(i-l)2个元素，而aij又是它所在的行中的第j个元素，所以在存储中aij是第i(i-l)2+j个元素。在存储完下三角中的元素之后，紧接着存储主对角线上方的常量，因为是同一个常数，所以存储一个即可。综上所述，若下三角矩阵A经过压缩存储后，对于矩阵中的任意元素a,存储在B中下标为k的单元，则k与ij之间的关系为：n(n+1)+5、若对n阶上三角矩阵A,以列序为主序方式将其元素(包括主对角线上所有元素)依次放于一维数组Bl.n*(n÷1)/2+1中，请推导出在B中确定ali的位置k的映射函数。答案对于上三角中的元素au，其特点是：i<=j且IWjWn,存储到向量B中后，根据存储原则，它前面有j-1歹J,共有1+2+3+j-l=j（三）2个元素，而au又是它所在的行中的第i个元素,所以在存储中a,是第j(j-l)2+i个元素。在存储完上三角中的元素之后，紧接着存储主对角线下方的常量，因为是同一个常数，所以存储一个即可。综上所述，若下三角矩阵A经过压缩存储后，对于矩阵中的任意元素ag存储在B中下标为k的单元，则k与i,j之间的关系为：6、设输入序列为a,b,c,d,借助一个栈，写出可以得到的两个输出序列和不能得到的两个序列。答案能得到的输出序列：d,c,b,aa,b,c,d不能得到的输出序列：a,c,d,ba,d.b,c7、请定义单链表存储结构，并写出用头插法创建带头结点的单链表的算法。typedefstructnode(ElemTypedata;structnode*next;)LinkList;单链表的创建-头插法1.inkList*CreateList_nx(intn)intI;1.inkList*head,*p;head=(LinkList*)malloc(sizeof(LinkList);head->next=NULL;fbr(i=l;i<=n;i+)p=(LinkList*)malloc(sizeof(LinkList);Scanf(fc4%d,(p->data);p->next=head->next;head->next=p;)returnhead;)8、请定义单链表存储结构，并写出用尾插法创建带头结点的单链表的算法。typedefstructnode(ElemTypedata;structnode*next;)LinkList;单链表的创建-尾插法(7分)1.inkList*CreateList(intn)(intI;1.inkList*head,*p,*r;head=(LinkList*)malloc(sizeof(LinkList);r=head;fbr(i=l;i<=n;i+)p=(LinkList*)malloc(sizeof(LinkList);Scanf(4%d,<fe(p->data);r->next=p;r=P；)r->next=NULL;returnhead;)10、对于给定的权值(15,3,14,2,6,9,16,17)。(1)请构造哈夫曼树。(2)计算该哈夫曼树的带权路径长度WPL值。(3)写出它的哈夫曼编码。规定：哈夫曼树构造中左子树权值小于右子树。23哈夫曼编码：15:1113:1010114:1102:101006:10119:10016:0017:01哈夫曼树的带权路径长度WPL值WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5)=22911已知一棵二叉树的先序、中序遍历序列分别为ABCDEFGHl和BCAEDGHFI。请画出这棵二叉树和它的中序线索树。13、设二叉树采用二叉链表存储结构，请编写二叉树的先序遍历的非递归算法。voidPreOrder_Nonrecursive(BiTree*t)(BiTree*sM,*p;inttop=0;if(t!=NULL)fP=t；dowhile(p!=NULL)prini(tt%c,p->data);stop=p;top+;p=p->left;lf(top>0)top-;p=stop;p=p->right;)while(p!=NULLtop>0);)14、设二叉树采用二叉链表存储结构，请编写二叉树的中序遍历的非递归算法。VoidinOrder_Nonrecursive(BiTree*t)BiTree*sM,*p;inttop=0;if(t!=NULL)P=t；do(while(p!=NULL)stop=p;top+;p=p->left;)lf(top>0)top-=stop;print(u%c,p->data);p=p->right;)while(p!=NULLtop>0);15、已知一棵二叉树的先序、中序遍历序歹IJ分别为ABDFCEGH和BFDAGEHC。清画出这棵二叉树并将其转换成对应的树（或森林）。17、已知某图的邻接表如图所示。（1）写出此邻接表对应的邻接矩阵。（2）写出由Vl开始的深度优先遍历的序列。（3）写出由Vl开始的深度优先的生成树。（4）写出由V1开始的广度优先遍历的序歹h（5）写出由W开始的广度优先的生成树。（1）邻接矩阵存储结构1O1I1OO21OOO103100010410000150110006000100VlV2V3V4V5V6VlV2V3V4V5V6234 S 6(2)由Vl开始的深度优先遍历的序列：VlV2V5V3V4V6(4)由Vi开始的广度优先遍历的序列：VlV2V3V4V5V617、已知某图的邻接表如图所示。(1)画出该图。(2)画出该图的邻接矩阵存储结构。(3)写出以顶点Vl为出发点的深度优先遍历序列。(4)写出以顶点Vl为出发点的广度优先遍历序列。答案(1)画出该图(3)由Vl开始的深度优先的生成树(5)由“开始的广度优先的生成树V2V5(2)邻接矩阵存储结构23456Vexnumarcnum 2kind101110020000113000010400101150000016000000Vl V2 V3 V4 V5 V6(3)以顶点VI为出发点的深度优先遍历序列：Vl V2V5 V6V3 V4(4)以顶点Vl为出发点的广度优先遍历序列：Vl V2 V3 V4V5 V618、已知一个有向无环图如下图所示，写出它的一个拓扑序列。拓扑序歹IJ为VlV2V3V5V4V619、已知一个无向网如下图所示，要求分别用Prim和Kruskal算法生成最小树。20、下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。(10分