欢迎来到天天文库
浏览记录
ID:51077265
大小:434.00 KB
页数:24页
时间:2020-03-18
《《数据结构》复习思考题.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、(0012)《数据结构》复习思考题一、常用的存储表示方法有哪儿种?二、卜列程序段带标号语句的频度和时间复杂度。(1)i=o;while(I2、方法有哪儿种?五、确定下列算法中输出语句的执行次数,并给出算法的时间复杂隊(1)voidcombi(intn){intlj,k;for(1=1;I<=n;I++)for(j=I+1;jv=n;j++)for(k=j+1;k<=n;k++)cout«I,j,k;)(2)voidbinary(intn){while(n){cout«n;n=n/2;}}六、为什么在单循环链表中设直尾指针比设置头指针更好?七、何吋选用顺序表、何吋选用链表作为线性表的心储结构为宜?八、指出以卜算法屮的错谋和低效之处,并把它改写为一个既正确乂高效的算法。StatusDeleteK3、(SqList&a,imI,intk){〃本过程从顺序蚣储结构的线性表a屮删除第I个元素起的k个元索。if(IvlIIkvOIII+k>a.length)returnERROR;else{for(count=l;count=I+l;j—)a.elemfj-11=a.elemfjl;a.length—;}rreturnOK;)//DeleteK九、假设某个单向循环链表的长度大于1,且表屮既无头结点也无头指针。已知s为指向链表中某个结点指针,试编写算法在链表中删除指针s所指结点的前驱结4、点。十、假设某个单向循环链表的长度人于1,且表屮既无头结点也无头指针。已知s为指向链表屮某个结点指针,试编写算法在链表中删除指针s所指结点的前驱结点。十一、已知L1和L2分别指向两个单链表的头结点,且己知其长度分别为m和n。试写一算法将这两个链表连接在一起,请分析你的算法的时间复杂度十二、已知单链表L是一•个递增有序表,试写一高效算法,删除表屮值大于min且小于max的结点(若表中有这样的结点),同时释放被删结点的空间,这里min和max是两个给定的参数。请分析你的算法的时间复杂度。十三、若以1234作为双端队列的输入序列,试分别求出满足以下条件的输出5、序列:(1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列;(2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列;(3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列。十四、设两个栈共亨空间vfO..m-ll,两栈的栈底分别设在向量的两端,且每个元素占一个分量。试设计这两个栈的插入和删除算法。十五、简述以下算法的功能。(1)voidDemol(SeqStack*S){intI;arr[64];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(1=6、0,I7、mpty(S))if((I=Pop(S))!=m)Push(&T,I);while(!StackEmpty(&T)){I=Pop(&T);Push(S,I);1)(2)voidDemo3(CirQueue*Q){//设DataType为int型intx;SeqStackS;InitStack(&S);while(!QueueEmpty(Q)){x=DeQueue(Q);Push(&S,x);)while(!StackEmpty(&s)){x=Pop(&S);EnQueue(Q,x);}]//Demo3(3)CirQueueQI,Q2;//设DataTy8、pe为int型intx,I,m=0;...〃设QI已有内容,Q2已初始化过while(!Que
2、方法有哪儿种?五、确定下列算法中输出语句的执行次数,并给出算法的时间复杂隊(1)voidcombi(intn){intlj,k;for(1=1;I<=n;I++)for(j=I+1;jv=n;j++)for(k=j+1;k<=n;k++)cout«I,j,k;)(2)voidbinary(intn){while(n){cout«n;n=n/2;}}六、为什么在单循环链表中设直尾指针比设置头指针更好?七、何吋选用顺序表、何吋选用链表作为线性表的心储结构为宜?八、指出以卜算法屮的错谋和低效之处,并把它改写为一个既正确乂高效的算法。StatusDeleteK
3、(SqList&a,imI,intk){〃本过程从顺序蚣储结构的线性表a屮删除第I个元素起的k个元索。if(IvlIIkvOIII+k>a.length)returnERROR;else{for(count=l;count=I+l;j—)a.elemfj-11=a.elemfjl;a.length—;}rreturnOK;)//DeleteK九、假设某个单向循环链表的长度大于1,且表屮既无头结点也无头指针。已知s为指向链表中某个结点指针,试编写算法在链表中删除指针s所指结点的前驱结
4、点。十、假设某个单向循环链表的长度人于1,且表屮既无头结点也无头指针。已知s为指向链表屮某个结点指针,试编写算法在链表中删除指针s所指结点的前驱结点。十一、已知L1和L2分别指向两个单链表的头结点,且己知其长度分别为m和n。试写一算法将这两个链表连接在一起,请分析你的算法的时间复杂度十二、已知单链表L是一•个递增有序表,试写一高效算法,删除表屮值大于min且小于max的结点(若表中有这样的结点),同时释放被删结点的空间,这里min和max是两个给定的参数。请分析你的算法的时间复杂度。十三、若以1234作为双端队列的输入序列,试分别求出满足以下条件的输出
5、序列:(1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列;(2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列;(3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列。十四、设两个栈共亨空间vfO..m-ll,两栈的栈底分别设在向量的两端,且每个元素占一个分量。试设计这两个栈的插入和删除算法。十五、简述以下算法的功能。(1)voidDemol(SeqStack*S){intI;arr[64];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(1=
6、0,I7、mpty(S))if((I=Pop(S))!=m)Push(&T,I);while(!StackEmpty(&T)){I=Pop(&T);Push(S,I);1)(2)voidDemo3(CirQueue*Q){//设DataType为int型intx;SeqStackS;InitStack(&S);while(!QueueEmpty(Q)){x=DeQueue(Q);Push(&S,x);)while(!StackEmpty(&s)){x=Pop(&S);EnQueue(Q,x);}]//Demo3(3)CirQueueQI,Q2;//设DataTy8、pe为int型intx,I,m=0;...〃设QI已有内容,Q2已初始化过while(!Que
7、mpty(S))if((I=Pop(S))!=m)Push(&T,I);while(!StackEmpty(&T)){I=Pop(&T);Push(S,I);1)(2)voidDemo3(CirQueue*Q){//设DataType为int型intx;SeqStackS;InitStack(&S);while(!QueueEmpty(Q)){x=DeQueue(Q);Push(&S,x);)while(!StackEmpty(&s)){x=Pop(&S);EnQueue(Q,x);}]//Demo3(3)CirQueueQI,Q2;//设DataTy
8、pe为int型intx,I,m=0;...〃设QI已有内容,Q2已初始化过while(!Que
此文档下载收益归作者所有