数据结构的习题1-3章

第一章绪论1-1简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1-2设三个函数f,g,h分别为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn请判断下列关系是否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n1.5)(4)h(n)=O(nlgn)1-3设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0;while(in){k=k+10*i;i++;}◆T(n)=n-1∴T(n)=O(n)◇这个函数是按线性阶递增的(2)i=0;k=0;do{k=k+10*i;i++;}while(in);◆T(n)=n∴T(n)=O(n)◇这也是线性阶递增的(3)i=1;j=0;while(i+j=n){if(ij)j++;elsei++;}◆T(n)=n/2∴T(n)=O(n)◇虽然时间函数是n/2,但其数量级仍是按线性阶递增的。(4)x=n;//n1while(x=(y+1)*(y+1))y++;◆T(n)=n1/2∴T(n)=O(n1/2)◇最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(5)x=91;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;◆T(n)=O(1)◇这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有?没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。1-4按增长率由小至大的顺序排列下列各函数：2100,(3/2)n，(2/3)n，nn,n0.5,n!，2n，lgn,nlgn,n(3/2)(2/3)^n2^100lgn√nn^(3/2)n^lgn(3/2)^n2^nn!n^n1-5上机作业（advanced)：完成复数的抽象数据类型各种操作的实现，并用客户程序进行测试。要求提交源程序的打印稿及运行结果截图并贴在作业本上。使用复数数据类型的客户程序：#include“stdafx.h”#include“CpxNum.h”intmain(intargc,char*argv[]){cpxNumc1,c2;doublereal,imag;cout“请输入复数的实部和虚部：”；cinrealimag;assign(c1,real,imag);cout”生成的复数是：”;print(c1);......;cout”c1+c2的结果是：”;print(cplus(c1,c2));coutendl;......;return(0);}称一个函数g(n)是O(f(n))，当且仅当存在常数c0和n0=0，对一切nn0均有|g(n)|=c|f(n)|成立，也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。我们常用大O表示法表示时间复杂度，注意它是某一个算法的时间复杂度。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。此外，一个问题本身也有它的复杂度，如果某个算法的复杂度到达了这个问题复杂度的下界，那就称这样的算法是最佳算法。常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。第二章线性表2-1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。2-2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2-3在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?2-5在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?2-6下述算法的功能是什么?LinkListDemo(LinkListL){//L是无头结点单链表ListNode*Q,*P;if(L&&L-next){Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnL;}//Demo上机作业（advanced)：要求编写客户程序进行测试。要求提交源程序的打印稿及运行结果截图并贴在作业本上。2-7已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。2-8设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。第三章栈和队列3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)?(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。3.2循环队列的优点是什么?如何判别它的空和满?3.3指出下述程序段的功能是什么?(1)voidDemo1(SeqStack*S){inti;arr[64];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,in;i++)Push(S,arr[i]);}//Demo1(2)SeqStackS1,S2,tmp;DataTypex;...//假设栈tmp和S2已做过初始化while(!StackEmpty(&S1)){x=Pop(&S1);Push(&tmp,x);}while(!StackEmpty(&tmp)){x=Pop(&tmp);Push(&S1,x);Push(&S2,x);}(3)voidDemo2(SeqStack*S,intm){//设DataType为int型SeqStackT;inti;InitStack(&T);while(!StackEmpty(S))if((i=Pop(S))!=m)Push(&T,i);while(!StackEmpty(&T)){i=Pop(&T);Push(S,i);}}(4)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(5)CirQueueQ1,Q2;//设DataType为int型intx,i,n=0;...//设Q1已有内容，Q2已初始化过while(!QueueEmpty(&Q1)){x=DeQueue(&Q1);EnQueue(&Q2,x);n++;}for(i=0;in;i++){x=DeQueue(&Q2);EnQueue(&Q1,x);EnQueue(&Q2,x);}上机作业（advanced)：要求编写客户程序进行测试。要求提交源程序的打印稿及运行结果截图并贴在作业本上。3.4利用栈的基本操作，写一个将栈S中所有结点均删去的算法voidClearStack(SeqStack*S)，并说明S为何要作为指针参数?3.5利用栈的基本操作，写一个返回S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数?3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)?(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。答：(1)出栈序列为：1324(2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push(3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。(3)在1，2，3，4的24种排列中，可通过相应入出栈操作得到的序列是：1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,43123.2链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3循环队列的优点是什么?如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.4设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?若只设尾指针呢?答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5指出下述程序段的功能是什么?(1)voidDemo1(SeqStack*S){inti;arr[64];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,in;i++)Push(S,arr[i]);}//Demo1(2)SeqStackS1,S2,tmp;DataTypex;...//假设栈tmp和S2已做过初始化while(!StackEmpty(&S1)){x=Pop(&S1);Push(&tmp,x);}while(!StackEmpty(&tmp)){x=Pop(&tmp);Push(&S1,x);Push(&S2,x);}(3)voidDemo2(SeqStack*S,intm){//设DataType为int型SeqStackT;inti;InitStack(&T);while(!StackEmpty(S))if((i=Pop(S))!=m)Push(&T,i);while(!StackEmpty(&T)){i=Pop(&T);Push(S,i