《数据结构练习一参考.doc》由会员分享，可在线阅读，更多相关《数据结构练习一参考.doc（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构练习一参考一、填空题：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=p-prior;p-pr
2、ior-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二、选择题1A2C3C4B5A6D7C8C9A10A11A12B13A14B
3、15D16D17B18B19BD20D21A22C23D24C25D26A27A28C29D30D31C32C33A34B35A36D37B38B39D40C41D42B43B44C45D46B47A48D49D50B51D52B53B54B55C56B57C58D59B60三、判断题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，其元素为整形数据，设计一个算法将L中所有小于0的整数放在前半部分，大于等于0的整数放在后半部分。void tiaozhe
4、ng(SqList &L) i=1; j=L.Length; while(ij) GetElem(L,i,lefte); if(lefte0) i-; GetElem(L,i,righte); /找到右边第一个小于0的元素 e=L.elemi-1; L.elemi-1=L.elemj-1; L.elemj-1=e;2设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。/思路：设a0.aj是没有重复元素的顺序表，检查ai是否在这个顺序表中，不在就存入aj+1void shanchu(SqList &A) j=0; for(i=1; iL.length; i+) k=0;whi
5、le(kj) L.elem+j=L.elemi; L.length=j+1; /注意j是从0开始的3用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小到大顺序排列的，且这（m+n）个数据中没有重复的。（1）设计一个算法将此两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。（2）如果顺序表B的大小为（m+n）个单元，是否可不利用顺序表C而合并成的线性表存放于顺序表B中？试设计此算法。（3）设顺序表A有m+n个元素，且前m个有序，后n个有序，设计一个算法，使得整个顺序表有序。void Merge1(SqList A,SqList B,SqList
6、&C) InitList_sq(C); i=j=1;k=0; a_len=ListLength_sq(A); b_len=ListLength_sq(B); 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; elseListInsert_sq(C,+k,bj);+j; while(i=a_len) GetElem_sq(A,i+,a);ListInsert_sq(C,+k,a); while(j=Lb_len) GetElem(
7、B,j+,b);ListInsert_sq(C,+k,b); Merge1void Merge2(SqList A,SqList &B) for(i=1; i0&B.elemj-1ai) B.elemj=B.elemj-1; j-; B.elemj=ai; B.length+; void Merge3(SqList &A) j =1; for(i=m; i0&a.elemj-1ai) A.elemj=A.elemj-1; j-; A.elemj=ai; 4有一个递增单链表（允许出现值域重复的结点），设计一个算法删除值域重复的结点。并分析算法的时间复杂度。void DelList(LinkLis
8、t &L) p=L-next; while(p-next) if(p-data=p-next-data) q=p-next; p-next=q-next; free(q); else p=p-next;5设计一个带头结点的单链表L中删除一个最小值结点的算法。Status DelMin(LinkList &L) if(L-next) return ERROR;minpre=ppre=L; minp=p=L-next; while(p)if(p-datadata) minp=p; minpre=ppre; ppre=p; p=p-next; minpre-next=minp-next; free(
9、minp);6已知3个单链表A、B、C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），设计一个算法使链表A中仅留下3个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n、和p分别为3个表的长度。7两个整数序列A=（a1，a2，am）和B=（b1，b2，bn）用两个单链表存储，设计一个算法，判断序列B是否是序列A的子序列。Status SubList(LinkList A,LinkList B) pa=A-next; while(pa) pb=B-next; while(pa&pa-data!=pb-dat
10、a) pa=pa-next; /找到第一个元素相同的结点 ta=pa; while(ta&pb&ta-data=pb-data) ta=ta-next; pb=pb-next; if(!pb) return TRUE; if(pa) pa=pa-next; return FALSE;8假设表达式中允许包含3种括号：圆括号、方括号、大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。9设以整数序列1，2，3，4作为顺序栈st的输入，利用push（进栈）和pop（出栈）操作，写出所有可能的输出并编程实现算法。void p(SqStack &S,int k,int *out,int i)/从k开始的可能的出栈序列放到outi中 int x; if(k=n&StackEmpty(S) /判断如果已经全部出站,那么我们可以打印了. print(out,i); p(S,k,out,i); Push(S,x); i-; /恢复站内的状态，即把车m退回到站内;(这里也是回溯) 10设计一个算法，利用栈的InitStack（）、Push（）、Pop（）和StackEmpty( )等基本运算返回指定栈中栈底元素。Status GetBase(Stack S, SElemType &e) InitStack(T); while(!StackEmpty (S) Pop(S,
