《数据结构算法题.doc》由会员分享，可在线阅读，更多相关《数据结构算法题.doc（11页珍藏版）》请在金锄头文库上搜索。
1、前五章习题算法2.2算法设计题1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1)void delete(SqList &L,ElemType x,ElemType y) int i=0,k=0; while(i=x &L.elemi=y) k+; /记录被删记录的个数 else L.elemi-k=L.elemi; /前移k个位置 i+; L.length=L.length-k;2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(
2、1),时间复杂度为O(n) void move(SqList &L) int i=0,j=L.length-1; int temp; while(ij) /使得正数都在前半部分，负数都在后半部分 while(i0)i+; while(ij&L.elemj0)j-; if(ij) /交换L.elemi(负数)和L.elemj(正数) temp=L.elemi; L.elemi=L.elemj; L.elemj=temp; i=1; while(iL.length/2) /通过交换使得正负数相间 j=L.length-2; temp=L.elemi; L.elemi=L.elemj; L.elem
3、j=temp; i=i+2; j=j-2; 3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作.交集:void intersection(SqList A,SqList B ,SqList &C) int i=0,j=0,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) j+; else C.elemk=A.elemi; k+;i+;j+; /共同的元素 C.length=k;并集:void Union
4、(SqList A,SqList B ,SqList &C) int i=0,j=0,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) C.elemk=B.elemj;k+;j+; else C.elemk=A.elemi; k+;i+;j+; /共同的元素只放一个 while(iA.len)C.elemk=A.elemi;k+;i+ while(jB.len)C.elemk=B.elemj;k+;j+ C.length=k;差集:void differnce(SqList A,SqList B ,SqList &C) int i=0,j=0
5、,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) j+; else i+;j+; /共同的元素只放一个 while(iA.length)C.elemk=A.elemi;k+;i+ C.length=k;2.3线性表的链式存储结构 简答题:1. 描述以下三个概念的区别:头结点,头指针,首元结点(第一个元素结点).在单链表中设置头结点的作用是什么? 答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以
6、对空表.非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表.双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。 头结点headdatalink 头指针 首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。2
7、. 试比较线性表的两种存储结构的优缺点,在什么情况下用顺序表比链表好? 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（next; /p指向单链表第一个结点L-next=NULL; /形成空的单链表while(p) /采用头插入法将p结点插入到头结点的后面实现逆置q=p;p=p-next;q-next=L-ne
8、xt;L-next=q;return OK;2试设计一个算法,求A和Bl两个单链表表示的集合的交集并集和差集,单链表中的数据递增有序排列并集：LinkList Bingji(LinkList &Head1,LinkList &Head2,LinkList &Head3) LNode *p1=Head1-next; LNode *p2=Head2-next;LNode *p3=Head3=Head1;while(p1 & p2) if(p1-data data) p3-next =p1; p3=p3-next ; p1=p1-next ; else if(p1-data p2-data) p3-
9、next =p2; p3=p3-next ; p2=p2-next ; else p3-next = p1; p3=p3-next ; p1=p1-next ; q=p2; free(q); p2=p2-next ; p3-next =(p1)?p1:p2;free(Head2);return Head3; 交集：LinkList Jiaoji(LinkList &Head1,LinkList &Head2,LinkList &Head3) LinkList pa,pb,r,p; pa=Head1-next;pb=Head2-next; r=Head3=Head1;while(pa&pb)if
10、(pa-datadata) r-next =pa-next ; free(pa); pa=r-next ;elseif(pa-datapb-data)pb=pb-next;elser-next=pa; r=pa;pa=pa-next;while(pa) r-next =pa-next ;free(pa); pa=r-next ; while (Head2-next) /释放Head2链表所有的结点空间 p=Head2-next; Head2-next=p-next; free(p); return Head3; 差集：LinkList Chaji(LinkList &Head1,LinkLis
11、t &Head2,LinkList &Head3) LinkList pa,pb,r,p; pa=Head1-next;pb=Head2-next; r=Head3=Head1;while(pa&pb)if(pa-datadata) r-next=pa; r=r-next; pa=pa-next;elseif(pa-datapb-data)pb=pb-next;elser-next=pa-next; free(pa);pa=r-next; while (Head2-next) /释放Head2链表所有的结点空间 p=Head2-next; Head2-next=p-next; free(p); return Head3;3已知线性表中的元素以值递增有序排列,并以单链表作存储结构,试写一高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删除的结
