数据结构作业题

《数据结构作业题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1简述下列术语：线性表，顺序表，链表。答：线性表是最常用且最简单的一种数据结构，一个线性表是N个数据元素的有限序列。顺序表是指用一组地址连续的储存单元依次存储线性表的数据元素。用这种方法存储的线性表简称顺序表。链表是用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。2何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?答：线性表的逻辑顺序与物理顺序一致;数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。而存储链表中结点的一组任意的存储单元可以是连续的，也可以是

2、不连续的，甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同。3在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?答：在顺序表中插入和删除一个结点平均需要移动1个结点，具体移动次数取决于时间复杂和空间复杂程度。4链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?答：链表元素的有序并不一定是值得有序，而是逻辑次序上的有序；链表中的元素并不需要物理位置上相邻，因为其逻辑联系已经在结点中包括了。5

3、设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。答：usingSystem;usingSystem.Collections.Generic;usingSystem.Collections;usingSystem.Text;namespacetest{classarrlist_test{publicstaticArrayLista=newArrayList();publicstaticvoidmain(){do{currency.write("请写入下一个值");a.Add(Console.ReadLi

4、ne());a.Sort();}while(currency.choice());for(inti=0;inext;while(pa!=null)pa=pa->next,i++;returni;7写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。答：voidDeleteList(LinkListL)　　　

5、　{　　　　　　ListNode*p,*q,*s;　　　　　p=L-next;　　　　　while(p->next&&p->next->next)　　　　　　{　　　　　　　q=p;　　　　　　　while(q->next)　　　　　　　　if(p->data==q->next->data)　　　　　　　　　{s=q->next;q->next=s->next;free(s);　　　　　　　　　}　　　　　　　　elseq=q->next;　　　　　　　p=p->next;　　　　　　}　　　　}8写一算法从一给定的向量A删

6、除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。答：#includetypedefintdatatype;#definemaxsize100/*定义顺序表*/typedefstruct{datatypedata[maxsize];intlast;}SeqList;/*初始化*/voidinit_SeqList(SeqList*L){L->last=-1;}/*输入顺序表*/voidinput_SeqList(SeqList*L,intn){inti;L->

7、last=0;//初始化for(i=0;idata[i]));L->last=L->last+n;}/*判断*/intmeasure(SeqList*L,intx,inty,intn){if((L->data[0]>=L->data[n-1]&&x>=L->data[n-1]&&y<=L->data[0])

8、

9、//是n-1(L->data[0]<=L->data[n-1]&&x>=L->data[0]&&y<=L->data[n-1]))return1;elsereturn0;}

10、/*删除值*/intdelete_list(SeqList*L,intx,inty){inti=0,j=0;while(ilast){/*if((L->data[i]>=x)&&(L->data[i]<=y))distence++;elseL->data[i-distence]=L