数据结构1-4章习题答案

1一、名词解释抽象数据类型、数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵二、填空1、抽象数据类型是由一组数据结构和在该组数据结构上的一组操作所组成。2、在定义某种数据结构时，其数据域的数据类型可分为简单类型和结构体类型两种，为增强其通用性，应将其再定义为通用数据类型。3、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为1：N、M：N。4、数据结构简单地说是指数据以及相互之间的联系。5、算法应具备以下5个特性：有穷性、正确性、可行性、输入和输出。6、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是处理问题的样本量。7、对于一个以顺序实现的循环队列Q[m]，队首、队尾指针分别为f和r，其盘空的条件是f=r，盘满的条件是(r+1)%m=f。8、循环链表的主要优点是最大限度的利用空间。9、链表对于数据元素的插入和删除不需要移动结点，只需改变相关结点的指针域的值。10、在一个链式栈中，若栈顶指针等于NULL，则为空栈。11、主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的返回地址地址。12、某算法在求解一个10阶方程组时，运算次数是500，求解一个30阶方程组时，运算次数是4500，则该算法的时间复杂度为O（N2）。三、选择题1、对一个线性表的存取操作很少，而插入和删除操作较多时应采用B存储结构。2A．顺序存储B.链式存储C.索引存储D.散列式存储2、对一个线性表的随机存取操作较多时，应采用B存储结构。A.静态顺序存储B.动态顺序存储C.动态链接存储D.静态链接存储3、对一个顺序存储结构的栈，栈满的判断条件是（D）A.S.top==-1B.S.top==0C.S.top==MaxSizeD.S.top==MaxSize-14、若循环队列有n个顺序存储单元，front、rear分别为队首和队尾指针则判断队满的条件是(C)A.(front+1)%n==rearB.(front-1)%n==rearC.(rear+1)%n==frontD.(rear-1)%n==front5、下列是顺序存储线性表排序的算法voidSort(List&L){inti,j;ElemTypex;for(i=1;iL.size;i++){x=L.list[i];for(j=i-1;j=0;j--)if(xL.list[j])L.list[j+1]=L.list[j];elsebreak;L.list[j+1]=x;};}问：此算法的时间复杂性为：BA.O(n)B.(n2)C.(n*i)D.(n*j)四、简答题1、简述线性表的顺序存储和链接存储实现的异同。3答：（参考答案）2、举例说明顺序存储的栈在元素出栈和进栈时栈顶指针的变化。3、说明顺序存储的队列，在解决队满与队空的判断条件时，为什么将队首指针指向第一个元素之前？这样解决后存储容量有什么变化？4、举例说明栈与递归算法之间的关系。答：（参考答案）要点1：栈只能在栈顶操作；要点2：递归算法是解决一个问题时，是通过解决与它具有相同解法的子问题而得到的；要点3：在进行递归调用时，计算机系统自动建立栈，用于存储递归调用参数（下例中的）n和返回地址（下例中的r）,进栈；要点4：当在一定条件下结束递归调用时，系统按照栈中存储的系数和返回地址逐步返回（出栈）到最初调用处，并得到最终结果。例：求f(n)=n!f(n)=1n=0f(n)=n*f(n-1)n0当n=3时进栈退栈nf(n)0f(0)=1111*f(1-1)1*1=122*f(2-1)2*1=233*f(3-1)3*2=6五、算法分析以下有一组算法，请根据各算法的不同，回答不同的问题。算法1：//利用数组a[]排序voidsort(inta[],intn){inti,j,k,t;for(i=0;in-1;i=i+1){4j=i;for(k=i+1;kn;k=k+1)if(a[k]a[j])j=k;t=a[i];a[i]=a[j];a[j]=t;}}问题1：此算法的时间复杂度为：O(n2)。问题2：此算法属于：A.。A.直接选择排序B.直接插入排序算法2：//在链表的表尾插入一个元素voidInsertRear(LNode*&HL,constElemType&item){1：LNode*newptr;2：newptr=newLNode;3：if(newptr==NULL){4：cerrMemoryallocationfailare!endl;5：exit(1);}6：newptr-data=item;7：newptr-next=NULL;8：if(HL==NULL)9：HL=newptr;10：else{11：LNode*p=HL;12：while(p-next!=NULL)13：p=p-next;14：p-next=newptr;5}}问题1：从算法评价的角度看，此算法中的3：—5：语句体现了算法的：健壮性。问题2：此算法返回类型为：A.A.空B.逻辑值算法3：//根据数据结构的类型的定义分析算法typedefintElemType;structStack{intMaxSize;ElemType*stack;inttop;};voidPush(Stack&S,constElemType&item){if(){intk=sizeof(ElemType);S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;}S.top++;S.stack[S.top]=item;}问题1：根据此算法定义的数据结构的类型，此算法的功能是向顺序栈中推入一个元素。问题2：if语句中的条件应修改为：B.。A.S.top==S.MaxSizeB.S.top==S.MaxSize-1六、广义表：A(a,(b,c,d),(#),((e,f),g))要求1：画出此广义表的图形表示。要求2：画出此广义表带表头附加结点的存储结构。要求3：此广义表长度：4；此广义表深度：3。6七、已知线性表A={a1、a2、……an}采用链接存储结构，其数据域由4个值域组成，假设依次为charcode[]charname[]intmaxintmin要求：1、定义单链表结点（包括对数据域的定义）；2、从单链表的表尾删除一个结点。（参考答案）答1：structgoods{charcode[5];charname[15];intmax;intmin;};typedefgoodsElemType;structLNode{ElemTypedata;LNode*next;};答2：ElemTypeDelete(LNode*HL){LNode*p=HL;while(p-next!=NULL)p=p-next;temp=p-data;deletep;returntemp;}