数据结构(C语言清华)习题答案

习题1参考答案一、单项选择题1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B二、填空题1.线性结构，非线性结构2.集合，线性，树，图3.一对一，一对多或多对多4.时间，空间5.前趋，一，后继，多6.有多个7.一对一，一对多，多对多8.O(2n)9.O(n)10.O(2n)11.O(log3n)12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。13.事后统计，事前估计三、算法设计题1.O(2n)2.O(2n)3.O(n3)4.O(n)5.O(n)习题2参考答案一、单项选择题1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C20．A二、填空题1．线性2．n-i+13．相邻4．前移，前，后5．物理存储位置，链域的指针值6．前趋，后继7．顺序，链接8．一定，不一定9．线性，任何，栈顶，队尾，队头10．单链表，双链表，非循环链表，循环链表11．使空表和非空表统一；算法处理一致12．O(1)，O(n)13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇14．2、3；15．O(1)三、简答题1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。6．共有14种可能的出栈序列，即为：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。一般地，要解决队列的上溢现象可有以下几种方法：（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。（2）要避免出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题1．算法思想为：（1）应判断删除位置的合法性，当i0或in-1时，不允许进行删除操作；（2）当i=0时，删除第一个结点：（3）当０in时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：delete(LinkList*q,inti){//在无头结点的单链表中删除第i个结点LinkList*p,*s;intj;if(i0)printf(Can'tdelete);elseif(i==0){s=q;q=q-next;free(s);}else{j=0;s=q;while((ji)&&(s!=NULL)){p=s;s=s-next;j++;}if(s==NULL)printf(Cant'tdelete);else{p-next=s-next;free(s);}}}2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：intListLength(LinkList*L){//求带头结点的单链表的表长intlen=0;ListList*p;p=L;while(p-next!=NULL){p=p-next;len++;}return(len);}3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q-next=s;操作即可，算法描述如下：voidinvert(LinkList*head){//逆置head指针所指向的单循环链表linklist*p,*q,*s;q=head;p=head-next;while(p!=head)//当表不为空时，逐个结点逆置{s=q;q=p;p=p-next;q-next=s;}p-next=q;}4．定义类型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：insert(LinkList*head){LinkList*p,*s,*q;p=head-next;//p指向待插入的结点，初始时指向第一个结点while(p!=NULL){s=head;//s指向q结点的前趋结点q=head-prior;//q指向由prior域构成的链表中待比较的结点while((q!=NULL)&&(p-dataq-data))//查找插入结点p的合适的插入位置{s=q;q=q-prior;}s-prior=p;p-prior=q;//结点p插入到结点s和结点q之间p=p-next;}}5．算法描述如下：delete(LinkList*head,intmax,intmin){linklist*p,*q;if(head!=NULL){q=head;p=head-next;while((p!=NULL)&&(p-data=min)){q=p;p=p-next;}while((p!=NULL)&&(p-datamax))p=p-next;q-next=p;}}6．算法描述如下：delete(LinkList*head,intmax,intmin){LinkList*p,*q;q=head;p=head-next;while(p!=NULL)if((p-data=min)||(p-data=max)){q=p;p=p-next;}else{q-next=p-next;free(p);p=q-next;}}7．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：（1）插入（即入队）算法：insert(LinkList*rear,elemtypex){//设循环链队列的队尾指针为rear,x为待插入的元素LinkList*p;p=(LinkList*)malloc(sizeof(LinkList));if(rear==NULL)//如为空队，建立循环链队列的第一个结点{rear=p;rear-next=p;//链接成循环链表}else//否则在队尾插入p结点{p-next=rear-next;rear-next=p;rear=p;}}（2）删除（即出队）算法：delete(LinkList*rear){//设循环链队列的队尾指针为rearif(rear==NULL)//空队printf(underflow\n);if(rear-next==rear)//队中只有一个结点rear=NULL;elserear-next=rear-next-next;//rear-next指向的结点为循环链队列的队头结点}8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：intInsertDecreaseList(SqList*L,elemtypex){inti;if((*L).len=maxlen){printf(“overflow);return(0);}for(i=(*L).len;i0&&(*L).elem[i-1]x;i--)(*L).elem[i]=(*L).elem[i-1];//比较并移动元素(*L).elem[i]=x;(*L).len++;return(1);}习题3参考答案一、单项选择题1．B2．D3．C4．D5．B6．C7．D8．C9．D二、填空题1.固定长度，设置长度指针2.两个串的长度相等，对应位置的字符相等3.“BCDEDE”4.含n个字符的有限序列（n≥0）5.不含任何字符的串，仅含空格字符的字符串三、算法设计题1．算法描述为：intdelete(r,s,t,m)//从串的第m个字符以后删除长度为t的子串charr[];ints,t,m;{inti,j;for(i=1;i=m;i++)r[s+i]=r[i];for(j=m+t-i;j=s;j++)r[s-t+j]=r[j];return(1);}//delete2．算法思想为：（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较；（3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。设单链表类型为LinkList；注意，此时类型LinkList中的data成分为字符类型。LinkStringfind(s,t)LinkString*s,*t;{LinkString*ps,*pt;ps=s;while(ps!=NULL){pt=t;while((pt!=NULL)&&(ps-data!=pt-data))pt=pt-next;if(pt==NULL)ps=NULL;else{ps=ps-next;s=ps;}}returns;}//find习题4参考答案一、单项选择题1.A2.A3.A4.B5.BA6.C7.A8.A9.C10.C11.C12.C13.B14.D15.A16.B二、填空题1.线性结构，顺序结构，以行为主序，以列为主序2.i×n+j个元素位置；3.5，34.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））5.n×(n+1)/2；6.e；7.418.head(head(tail(Ls)))9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1）