1-4章习题答案2015

1一、名词解释（见教材）数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵二、填空1、数据的逻辑结构被分为_集合结构_、_线性结构___、_树形结构__、__图形结构__4种。2、数据的存储结构被分为_顺序结构__、链接结构_、索引结构_、和__散列结构__4种。3、在定义某种数据结构时，其数据域的数据类型可分为简单类型和结构体类型两种，为增强其通用性，应将其再定义为通用数据类型。4、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为1：N、M：N。5、数据结构简单地说是指数据以及相互之间的联系。6、算法应具备以下5个特性：有穷性、正确性、可行性、输入和输出。7、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是处理问题的样本量。8、对于一个单链表，在表头插入结点的时间复杂度为O(1)，在表尾插入元素的时间复杂度为O(n)。9、在表长为n的顺序表中，在等概率情况下，插入和删除一个元素平均需移动表长的一半（即n/2）个元素，具体移动元素的个数与表长（n）和该元素在表中的位置有关。10、顺序表的定义如下：typedefintElemType;2structList{ElemType*list;intsize;intMaxSize;};其中ElemType的含义是：通用数据类型；size的含义是：顺序表中元素的个数。11、设单链表中指针p指向结点A，q指针指向其后继结点。若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为p-next=q-next;。12、栈的运算规则为后进先出，队列的运算规则为先进先出。13、一个函数调用了自身，这是递归调用。14、非零元素个数远远少于零元素个数的矩阵称为稀疏矩阵。非零元素所在的行；t的含义是：非零元素的个数。三、选择题1、顺序表物理结构中的存储单元（A）。A.一定是连续的B.一定是不连续的C.不一定是连续的D.经删除操作后不连续2、对一个线性表的存取操作很少，而插入和删除操作较多时应采用B数据结构。A．线性表B.队列C.图D.树3、对一个线性表的随机读取操作较多时，应采用B存储结构。A.静态顺序存储B.动态顺序存储C.动态链接存储D.静态链接存储4、顺序表适用于（A）的场合。A.频繁查询B.频繁插入与删除C.问题规模较小D.问题规模较大35、链表不具有的特点是（A）。A．可随机访问任一元素B.插入、删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比6、栈的插入和删除操作在（A）进行。A．栈顶B．栈底C．栈顶或栈底D．任意位置7、向一个顺序栈S（栈顶指针为top）中插入元素x时，首先要（B）。A．S-stack[S-top]=x;B．S-top++;C．S-top--;D．x=S-stack[S-top];8、对一个顺序存储结构的栈，栈满的判断条件是（D）A.S.top==-1B.S.top==0C.S.top==MaxSizeD.S.top==MaxSize-19、若循环队列有n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队满的条件是(C)A.front==rearB.(front-1)%n==rearC.(rear+1)%n==frontD.(rear-1)%n==front10、若循环队列有n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队空的条件是(A)A.front==rearB.(front-1)%n==rearC.(rear+1)%n==frontD.(rear-1)%n==front11、队的插入操作在（C）进行。A．队首B．队首或队尾C．队尾D．任意位置12、下面程序段的时间复杂度为（C）。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;A．O(m2)B.O(n2)C．O(m×n)D.O(m+n)413、一个求从1到正整数n之间所有正整数之和的单循环语句的时间复杂度为（B）。A．O(1)B.O(n)C．O(n2)D.O(n3)14、下列是顺序存储线性表排序的算法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)15、下面程序段的时间复杂度为（B）。for(inti=1;i=n;i++)for(intj=1;j=n;j++)printf(“%d*%d=%d\n”,i,j,i*j);A．O(n)B.O(n2)C．O(1)B.O(n3)四、简答题1、简述数据的逻辑结构和物理结构的关系答：数据结构是指数据元素之间逻辑关系的整体，是从具体问题抽象出来的数据模型，有线性结构、树型结构和图型结构三种类型。物理结构是数据及其逻辑结构在计算机中的表示，5分为顺序存储和非顺序存储两种类型。数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。2、叙述顺序表和链表在存储方式、空间占用、读取操作、插入和删除操作等方面的不同；【答案要点】1.两者的存储结构不同。顺序用物理相邻实现逻辑相邻，大多用数组实现，链接存储用链接的方式实现逻辑相邻，物理上不一定相邻；2.存储相同数量的数据，顺序存储占用空间小，链接存储占用空间大；3.读取操作：顺序存储为按元素序号随机访问，效率较高；链接存储为按元素序号顺序访问，效率较低；4.插入和删除操作：顺序存储要移动约半数元素，效率较低；链接存储不需移动现有元素，效率较高；3、举例说明顺序存储的栈在元素出栈和进栈时栈顶指针的变化。4、说明顺序存储的队列，在解决队满与队空的判断条件时，为什么将队首指针指向第一个元素之前？这样解决后存储容量有什么变化？5、用f(n)=n!为例说明栈与递归算法之间的关系。答：（参考答案）要点1：栈只能在栈顶操作；要点2：递归算法是解决一个问题时，是通过解决与它具有相同解法的子问题而得到的；要点3：在进行递归调用时，计算机系统自动建立栈，用于存储递归调用参数（下例中的）n和返回地址（下例中的r）,进栈；要点4：当在一定条件下结束递归调用时，系统按照栈中存储的系数和返回地址逐步返回（出栈）到最初调用处，并得到最终结果。要点4：例：求f(n)=n!f(n)=1n=0f(n)=n*f(n-1)n0当n=3时进栈退栈nf(n)60f(0)=1111*f(1-1)1*1=122*f(2-1)2*1=233*f(3-1)3*2=6五、基本要求：1、写出顺序表定义2、写出链表结点定义3、写出堆栈定义4、写出循环顺序队列定义5、写出链队定义六、算法分析以下有一组算法，请根据各算法的不同，回答不同的问题。算法1：//利用数组a[]排序voidsort(inta[],intn){inti,j,k,t;for(i=0;in-1;i=i+1){j=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)。7问题2：此算法属于：A.。A.直接选择排序B.直接插入排序算法2：intFindList(structList*L,ElemTypex){inti;for(i=0;iL-size;i++)if(L-list[i]==x){x=L-list[i];returni;}return-1;}问题1、算法适用的数据结构？问题2、算法功能？问题3、算法返回？问题4、算法有无健壮性？若有，是哪（些）语句？问题5、算法的关键语句是哪（些）语句？问题6、算法的时间复杂度大O（）？算法3：//在链表的表尾插入一个元素voidInsertLastList(structsNode**HL,ElemTypex){structsNode*newp;newp=malloc(sizeof(structsNode));if(newp==NULL){printf(Memoryallocationfailare!\n);exit(1);}8newp-data=x;newp-next=NULL;if(*HL==NULL)*HL=newp;else{structsNode*p=*HL;while(p-next!=NULL)p=p-next;p-next=newp;}}问题1、算法适用的数据结构？问题2、算法功能？问题3、算法返回？问题4、算法有无健壮性？若有，是哪（些）语句？问题5、算法的关键语句是哪（些）语句？问题6、算法的时间复杂度大O（）？算法4：//根据数据结构的类型的定义分析算法typedefintElemType;structStackSq{intMaxSize;ElemType*stack;inttop;};voidPush(structStackSq*S,ElemTypex){if()againMalloc(S);S-top++;S-stack[S-top]=x;9}问题1：根据此算法定义的数据结构的类型，此算法的功能是向顺序栈中推入一个元素。问题2：if语句中的条件应为：B.。A.S.top==S.MaxSizeB.S.top==S.MaxSize-11算法5：ElemTypeOutQueue(structQueueSq*Q){if(Q-front==Q-rear){printf(Queueisempty!\n);exit(1);}Q-front=(Q-front+1)%Q-MaxSize;returnQ-queue[Q-front];}问题1、算法适用的数据结构？问题2、算法功能？问题3、算法返回？问题4、算法有无健壮性？若有，是哪（些）语句？问题5、算法的关键语句是哪（些）语句？问题6、算法的时间复杂度大O（）？七、分析题1、有一个顺序存储的栈，最大存储空间MaxSize=5，栈顶指针top，现有A、B、C、D四个元素。要求1：写出顺序存储栈结构定义。要求2：画出初始化状态。要求3：画出以上四个元素依次进栈后的状态。要求4：在要求3的基础上，画出三个元素出栈后，又有E、F二个元素进栈，画出队首、队10尾指针位置。要求5：以下是从栈中删除元素，并将被删除的元素值由函数返回的算法，请填写算法中缺失的语句。答1：typedefcharElemType;structStack{ElemType*stack[];inttop;intMaxSize;};答2：01234Top=-1答3：ABCD01234Top=3答4：AEF01234Top=2答5：ElemTypePop(Stack&S){if(S.top==-1){cerrStackisempty!endl;exit(1);}ElemTypetemp=S.stack[S.top];S.top--;11returntemp;}2、有一个顺序存储的循环队列，最大存储空间为5，假设队首指针指向队首元素的前一个位置，队尾指针指向队尾元素，现队列中已有A、B、C、三个元素。要求1：已有顺序存储队列结构的定义，请填写定义中缺失的语句。要求2：填写出初始化算法语句。要求3：画出经初始化后，以上三个元素依次进队后，队首、队尾指针位置。要求4：画出以上三个元素依次出队后，元素D、E依次进队后队首、队尾指针位置。要求5：以下是向队列中插入元素的算法，在