数据结构练习答案.doc

《数据结构练习答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、09数据结构练习一参考一、填空题：1直接前驱2直接后继3元素个数4一个指针域5前驱6后继7指针域8next(指针域)9头结点10相互间存在一种或多种特定关系11结构12集合线性结构树形结构图形结构13逻辑结构物理结构操作（运算）14逻辑结构15物理结构16顺序印象和非顺序印象17顺序印象的特点是用元素在存储器中的相对位置表示数据元素之间的逻辑关系，非顺序印象的特点借助于指针表示数据元素之间的逻辑关系18顺序存储结构和链式存储结构19s->next=p->next;p->next=s;20q=p->next;p->next=q->next;free(q);21t->prior

2、=p->prior;p->prior->next=t;t->next=p;p->prior=t;22q=p->next;q->next->prior=p;p->next=q->next;free(q);23往前挪24被删除元素后面一个元素25n/226O(1)27O(n)28操作受限制29Q.front==(Q.rear+1)%MaxQueueSize30Q.front==Q.rear31最后一个32第一个33最后一个34O（n）35O(1)36O(n)37q->next或p->next->next38零个字符的串39零40任意个连续字符组成的子序列414212000二、选

3、择题1A2C3C4B5A6D7C8C9A10A11A12B13A14B15D16D17B18B19B20D21A22C23D24C25D26A27A28C29D30D31C32C33A34B35A36D37B38B39D40C41D42B43B44C45D46B47A48D49D50B51D52B53B54B55C56B57C58D59B60三、判断题1否2否3否4是5否6否7是8否9否10否11否12否13否14是15是16否17否18是19是20否21否22是23否24否25是26否27是28是29是30是五、算法设计1．设有一个顺序表L，其元素为整形数据，设计一个算法

4、将L中所有小于0的整数放在前半部分，大于等于0的整数放在后半部分。voidtiaozheng(SqList&L){i=1;j=L.Length;while(i0){i--;GetElem(L,i,righte);}//找到右边第一个小于0的元素e=L.elem[i-1];L.elem[i-1]=L.elem[j-1];L.elem[j-1]=e;}}2．设计一个算法从顺

5、序表中删除重复的元素，并使剩余元素间的相对次序保持不变。//思路：设a[0]..a[j]是没有重复元素的顺序表，检查a[i]是否在这个顺序表中，不在就存入a[j+1]voidshanchu(SqList&A){j=0;for(i=1;ij)L.elem[++j]=L.elem[i];}L.length=j+1;//注意j是从0开始的}3．用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中

6、数据都是由小到大顺序排列的，且这（m+n）个数据中没有重复的。（1）设计一个算法将此两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。（2）如果顺序表B的大小为（m+n）个单元，是否可不利用顺序表C而合并成的线性表存放于顺序表B中？试设计此算法。（3）设顺序表A有m+n个元素，且前m个有序，后n个有序，设计一个算法，使得整个顺序表有序。voidMerge1(SqListA,SqListB,SqList&C){InitList_sq(C);i=j=1;k=0;a_len=ListLength_sq(A);b_len=ListLength_sq(B);

7、while((i<=a_len)&&(j<=b_len))∥A和A均为非空{GetElem_sq(A,i,ai);GetElem_sq(B,j,bj);if(ai<=bj){ListInsert_sq(C,++k,ai);++i;}else{ListInsert_sq(C,++k,bj);++j;}}while(i<=a_len){GetElem_sq(A,i++,a);ListInsert_sq(C,++k,a);}while(j<=Lb_len){GetElem(B,j++,b);ListInsert_sq(C