数据结构课后习题答案

11绪论1.1回答下列概念：数据结构，数据的逻辑结构，数据的存储结构，算法数据结构:按照某种逻辑关系组织起来的一批数据，用一定的存储方式存储在计算机的存储器中，并在这些数据上定义一个运算的集合，就称为一个数据结构。数据的逻辑结构:数据元素之间的逻辑关系，是根据实际问题抽象出来的数学模型。数据的存储结构:是指数据的逻辑结构到计算机存储器的映射。算法:是指对数据元素进行加工和处理1.2数据结构研究的三方面内容是什么？它们之间有什么联系和区别？三方面内容:数据的逻辑结构、数据的存储结构和数据运算的集合。联系和区别：数据的逻辑结构是数学模型，数据的存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。1.3简述数据结构中讨论的三种经典结构及其逻辑特征。三种经典结构：线性表、树和图。线性表：有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点，数据元素间存在着一对一的相互关系。树：有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点，数据元素间存在着一对多的层次关系。图：可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点，数据元素间存在着多对多的网状关系。1.4实现数据存储结构的常用存储方法有哪几种？简述各种方法的基本思想。常用存储方法有四种：顺序存储、链接存储、索引存储、散列存储。各种方法的基本思想：顺序存储：把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。链接存储：通过附加指针域表示数据元素之间的关系。索引存储：除了存储数据元素，还要建立附加索引表来标识数据元素的地址。散列存储：根据数据元素的关键字直接计算出该结点的存储地址，称为关键字－地址转换法。1.5算法的特性是什么？如何定性的评价一个算法的优劣？算法的特性：有穷性、确定性、可行性、输入、输出。算法的定性评价标准有：正确性、可读性、健壮性、简单性。1.6算法的定量评价标准是什么？算法的定量评价标准有：时间复杂度和空间复杂度。时间复杂度：是一个算法运行时所耗费的系统时间，也就是算法的时间效率。空间复杂度：是一个算法运行时所耗费的存储空间，也就是算法的空间效率。1.7写出下列程序段中带标号语句的频度，并给出执行各程序段的时间复杂度（n为整数）。（1）i=1;（2）s=1;while（in）dofor(i=1;i=n;i++)【1】i++;【1】s=s*i;（3）s=0;（4）i=1;for(i=l;in;i++)while(i*i=n)for(j=n;j=i;j--)【1】i++;【1】s=s+i+j;（5）i=1；（6）x=1;y=100;while（in）dodo{2【1】i=i*2;【1】x++;y--;}While(xy);答：（1）n-1,O(n)（2）n,O(n)（3）(n+2)(n-1)/2,O(n2)（4）,O()（5）㏒(n-1)+1,O(㏒n)（6）50,O(1)2线性表2.1回答下列概念：线性结构，线性表，顺序表，单链表，静态链表线性结构：设Data_Structure=（D，S），r∈S，相对r，D中有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋和一个后继，则称Data_Structure是相对r的线性结构。线性表：是具有相同属性的n（n≥0）个数据元素的有限序列。顺序表：顺序表（SequentialList）是采用顺序存储结构的线性表。单链表：每个结点只附加一个指向后继的指针域，这样的链表称为单链表（SingleLinkedList）静态链表：用数组实现的链表，指针就变换为数组的下标，结点即为数组中的下标变量，由于需要预先分配一个较大的数组空间，因此这种链表称之为静态链表。2.2比较顺序表和链表这两种线性表不同存储结构的特点。１．逻辑关系的表示：顺序表隐含表示关系，链表显示表示关系。2．存储密度：顺序表的存储密度大，而链表的存储密度小。3．存储分配方式：顺序表的存储空间是预先静态分配的一块连续存储空间，在程序执行之前必须明确规定它的存储规模。链表不用事先估计存储规模，动态分配和释放存储空间，存储空间可连续也可不连续。4．存取方法：顺序表可以随机存取，链表必须顺序存取。5．插入、删除操作：在顺序表中做插入、删除时平均移动表中一半的元素；在链表中作插入、删除时，只要修改指针域，而不需要移动元素。所以顺序表的插入、删除效率低，链表的插入、删除效率高。6．实现语言：顺序表容易实现，任何高级语言中都有数组类型。而链表的操作是基于指针的，对于没有提供指针类型的高级语言，必须采用静态链表。总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入、删除的线性表，即动态性较强的线性表宜选择链接存储。2.3已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。（1）线性表采用顺序存储#defineMAX1024typedefintDataType;typedefstruct{DataTypedata[MAX];intlast;}SeqList;intLocateElem(SeqList*L,DataTypeitem){inti,j=0;for(i=0;i=L-last;i++)if(L-data[i]item)j++;returnj;}nn3（2）线性表采用单链表存储typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}LinkList;LinkList*locateElem(LinkList*L,DataTypeitem){LinkList*p=L-next;inti=0;while(p){if(p-dataitem)i++;p=p-next;}returni;}2.4已知长度为n的线性表A中的元素是整数，写算法删除线性表中所有值为item的数据元素。分两种情况编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。（1）线性表采用顺序存储#defineMAX1024typedefintDataType;typedefstruct{DataTypedata[MAX];intlast;}SeqList;intLocateElem(SeqList*L,DataTypeitem){inti=0;While(i=L-last)if(L-data[i]==item){for(j=i+1;j=L-last;j++)L-data[j-1]=L-data[j];L-last--;}Elsei++;}（2）线性表采用单链表存储typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}LinkList;intdeleteDupNode(LinkList*L,DataTypeitem){LinkList*p,*q,*r;q=L;p=L-next;while(p)if(p-data==item){q-next=p-next;free(p);p=q-next;}else{q=p;p=p-next;}}2.5设长度为Max的顺序表L中包含n个整数且递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持表的有序性，并且分析算法的时间复杂度。4#defineMAX1024typedefintDataType;typedefstruct{DataTypedata[MAX];intlast;}SeqList;intinserts(SeqList*L,DataTypex){inti;if(L-last==Max-1){printf(“full”);return0;}i=L-last;while(i=0&&L-data[i]x)L-data[i+1]=L-data[i--];L-data[i+1]=x;L-last++;return1;}2.6设带头结点的单链表L中的数据元素是整型数且递增有序。试写一算法，将x插入到单链表的适当位置上，以保持表的有序性，并且分析算法的时间复杂度。typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}LinkList;voidInsertList(LinkList*L,datetypex){LinkList*p,*s;s=(LinkList*)malloc(sizeof(Linklist));s-data=x;p=L;while((p-next)&&(p-next-datax))p=p-next;s-next=p-next;p-next=s;}2.7试写一算法实现对不带头结点的单链表H进行就地逆置。typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}LinkList;LinkList*Reverse(LinkList*H){LinkList*p,*q;if(!H)return;p=H-next;q=H-next;H-next=NULL;While(q){q=q-next;p-next=H;H=p;p=q;}returnH;}52.8若带头结点的单链表L中的数据元素是整型数，编写算法对单链表L进行排序。typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}LinkList;voidInsertList(LinkList*L){LinkList*p,*q,*s;if(!L-next||！L-next-next)return;q=L-next-next;L-next-next=NULL;while(q){s=q;q=q-next;p=L;while((p-next)&&(p-next-datas-data))p=p-next;s-next=p-next;p-next=s;}}2.9设单链表X和单链表Y分别存储了两个字符串，设计算法找出X中第一个不在Y中出现的字符。typedefcharDataType;typedefstructNode{DataTypedata;structNode*next;}LinkList;linklist*search(linklist*x,linklist*y){linklist*p,*q;p=x;q=y;while(p&&q){if(p-data!=q-data)q=q-next;else{p=p-next;q=y;}}returnp;}2.10已知递增有序的两个单链表A和B各存储了一个集合。设计算法实现求两个集合的交集运算C=A∩B。typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}LinkList;LinkList*union(LinkList*A,LinkList*B){LinkList*C,*p,*q,*s*r;p=A-next;q=B-next;C=A;r=C;while(p&&q){if(p-data==q-data){r-next=p;r=p;6p=p-next;q=q-next;}elseif(p-dataq-data)p=p-next;elseq=q-next;}r-next=NULL;free(B);returnC;}2.11已知递增有序的两个单链表A和B，编写算法将A、B归并成一个递增有序的单链表C。typedefintDataType;type