《数据结构》复习思考题.doc

《《数据结构》复习思考题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、(0012)《数据结构》复习思考题一、常用的存储表示方法有哪儿种？二、卜列程序段带标号语句的频度和时间复杂度。(1)i=o；while(I

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,I

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