大学数据构造课后习题答案.docx

《大学数据构造课后习题答案.docx》由会员分享，可在线阅读，更多相关《大学数据构造课后习题答案.docx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大学数据构造课后习题答案大学数据构造课后习题答案参考答案第一章、绪论一、选择题1B；2A；3B；4C；5C；6B；7C；8C；9D；10B。二、填空题1、存储；2、无，1，无，1；3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性构造，树形构造，图形构造；7、顺序构造，链式构造，索引构造，散列构造；8、顺序。三、问答题与算法题1、3；2、T1(n)=5n2-O(n);T2(n)=3n2+O(n);T3(n)=8n2+O(logn);T4(n)=1.5n2+O(n)。T4(n)较优，T3(n)较劣。3、见课本。第二章线性表一、选择题1C；2A；3

2、D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.二、填空题1、O(1),O(n)；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L-next=L且L-prior=L；8、顺序。三、问答题与算法题1、头指针：结点或头结点的指针变量。其作用是存放第一个结点或头结点的地址，从头指针出发能够找到链表中所有结点的信息。头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。首结点：是链表的第一个结点。2、(1)基于空间的考虑。

3、当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储构造为好。(2)基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储构造为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储构造。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。3、尾指针是指向终端结点的指针，用它来表示单循环链表能够使得查找链表的开场结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开场结点和终端结点的位置分别是r

4、ear-next-next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)4、S=P-Prior;P-Prior=S-Prior;S-Prior-Next=P;S-Prior=P;S-Next=P-Next;P-Next=S;S-Next-Prior=S;5、:将开场结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开场结点，返回新链表的头指针6、15，26，51，37，48，,55。7、CreatList_L(LinkListLintn)L=(LinkList)molloc(sizeof(Lnode);/头结点L-next=NULL

5、;q=L;For(i=1;i+i)41P=(LinkList)molloc(sizeof(Lnode);Scanf(p-data);p-next=NULL;q-next=p;q=p;returenOK;8、Voids(SqlistS,intx)inti=0;n=S.Length;while(xS.elemiin)i+;/查找插入点if(i=n)S.elemn=x;/插在最后一个结点的后面elsefor(j=n-1;jj+)S.elemj+1=S.elemj;/元素后移S.elemi=x;/插入9、intListLength(LinkListL)q=L-next;i=0;while(q)i+;q

6、=q-next;returni;10、int(LinkListL,intx)p=L-next;/p为定位指针q=L;/q为定位指针的前导while(p-data!=x)p)q=p;/q前进p=p-next;/p前进if(!q)returnERROR;/查找失败q-next=p-next;free(p);returnOK;11、voidmergelist(linklistLa,linklistLb)pa=La-next;pb=Lb-next;pc=La;while(papb)if(pa-datapa-data)pc-next=pa;pc=pa;pa=pa-next;elseif(pa-data=

7、pa-data)pc-next=pa;pc=pa;pa=pa-next;pb=pb-next;else(pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pb:pb;12、Voidinvertlinklist(linklistL)if(!L)returnOK;/空表p=L-next;if(!p)returnOK;/仅有一个结点的表elseq=p-next;/q指向p的后继42p-next=NULL;while(q)r=q-next;/r指向q的后继q-next=p;/逆置p=q;/p前进q=r;/q前进L=p;/第一个结点13、VoiddelDuplicate(in

8、tA，intn)for(i=0;ii+)for(j=i+1;j=n-1;j+)if(ai=aj)n-;for(k=j+1;k=n-1;k+)ak-1=ak;第三章栈和队列一、选择题1A；2D；3C；4C；5D；6C；7C；8B；9C；10C；11，；12；13。二、填空题1、栈顶；2、满，空，n；3、后进先出，先进先出；4、头；5、L-next=NULL，S.top=S.base，S.top-S.base=S.stacksize，L=NULL，Q.front=Q.rear，Q.rear%maxQsize=Q.front;6、Q.rear-Q.front+n)%n；7、1nC2n；8、n。n?1

9、三、问答题与算法题1、；2、(1)intpush_L(LinkstacksSelemTypee)p=(LinkStack)molloc(sizeof(Snode);if(!p)returnERROR;p-data=e;p-next=s;s=p;ReturnOk;(2)intpop_L(LinkstacksSelemTypee)if(!S)returnERROR;q=s;e=s-data;s=s-next;free(q);RetuenOk;433、(1)intEnQueue_L(QueueptrQLQelemTypee)p=Queueptrmolloc(sizeof(Qnode);if(!p)r

10、eturnERROR;p-data=e;p-next=QL-next-next;QL-next-next=p;RetuenOk;(2)intDeQueue_L(QueueptrQLQelemTypee)if(QL-next=QL)returnERROR;p=QL-nextwhile(p-next!=QL)p=p-next;p-next=QL-next;e=QL-next;free(QL);QL=p;ReturnOk;4、(1)栈S元素反序存放；(2)把栈s1复制到s2；(3)把栈S中值等于m的元素删除；(4)队列Q元素反序存放;(5)链表中的元素反序存放；5、Inthw4(LinkListL)

11、initstack(S);bool=1;n=0;p=L-next;while(p)n+;p=p-next;/求串长p=L-next;/p指向第一个结点for(i=0;idata);p=p-next;if(n%2=1)p=p-next;/对照解法1while(pbool)pop(S,ch);if(ch!=p-data)bool=0;p=p-next;returnbool;6、voidClearStack(LinkStackS)。while(!S)p=s;s=s-next;free(p);44returnOK;7、intStacksize(LinkStackS)。n=0;p=s;While(!p)

12、n+;p=p-next;returnn;8、见、(5)第四章串一、选择题1B；2B；D；4B；5C；6D。二、填空题、空格串；2、静态分配的顺序串、动态分配顺序串、块连串；3、?4、块的大小；5、；6、StrAssing，StrCompare，StrLength，Concat，SubString；7、13,6；8、形式，目的主。三、问答题与算法题1、空串是指不包含任何字符的串，它的长度为零。空格串是指包含一个或多个空格的串，空格也是字符,长度不为零。串常量是指在程序中只可引用但不可改变其值的串。串变量是能够在运行中改变其值的。主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，

13、而包含子串的串就称为主串。目的串和形式串:在串匹配运算经过中，将主串称为目的串，而将需要匹配的子串称为形式串，两者是相对的。2、()Stocktom,March51999；()正数；()正数；()3、voidStrInsert(char*S,char*T,inti)/将串T插入到串S的第i个位置上char*Temp;if(i=strlen(S)Temp=(char*)malloc(sizeof(charMaxsize);/设置一个临时串strcpy(Temp,Si);/将第i位起以后的字符拷贝到临时串中strcpy(Si,T);/将串T拷贝到串S的第i个位置处，覆盖后面的字符strcat(S,Temp);/把临时串中的字符连接到串S后面free(Temp);、voidStrDelete(char*S,inti,intm)/串删除charTempMaxsize;/定义一个临时串if(i+mstrlen(S)45【大学数据构造课后习题答案】