耿版数据结构课后作业参考答案

数据结构课后作业参考答案浙江工商大学信电学院1概论1.1.1什么是数据结构？答：按照某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。1.1.2叙述四类基本数据结构的名称和含义。答：1、集合结构：结构中的数据元素除了同属于一个集合之外无其它任何关系；2、线性结构：结构中的数据元素之间存在着一对一的线性关系；3、树形结构：结构中的数据元素之间存在着一对多的层次关系；4、图状关系：结构中的数据元素之间存在着多对多的任意关系。1.1.3叙述算法的定义和特性。答：算法是规则的有限集合，是为了解决特定问题而规定的一系列操作。算法具备以下特性：有限性、确定性、零或多个输入、一或多个输出、可行性。1.1.4叙述算法的时间复杂度。答：算法的时间复杂度是指算法执行时间的增长率随着问题规模的增大在数量级上的变化趋势。1.1.5叙述数据类型的概念。答：数据类型是指一组性质相同的值集合以及定义在该值集合上的一组操作的总称。1.1.6叙述线性结构与非线性结构的差别。答：数据元素之间存在一对一线性关系的结构为线性结构；存在一对多或者多对多关系的称为非线性关系。1.1.7叙述面向对象程序设计语言的特点。答：在面向对象程序设计语言中，借助对象描述抽象数据类型，存储结构的说明和操作函数的说明被封装在一个整体结构中。该整体结构被称为类，而属于某个类的具体变量被称为对象。1.1.8在面向对象程序设计中，类的作用是什么？答：类的概念与操作密切相关，同一种数据类型和不同操作组将组成不同的数据类型，结构说明和过程说明被统一在一个整体对象之中。其中数据结构的定义为对象的属性域，过程或函数定义在对象中，称为方法，是对对象的性能描述。1.1.9叙述参数传递的主要方式及特点。答：参数表中的参数分为两种：第一种参数只为操作提供待处理数据，又称值参；第二种参数既能为操作提供待处理数据，也能返回操作结果，也称变量参数。1.1.10叙述抽象数据类型的概念。答：抽象数据类型是指基于一类逻辑关系的数据类型以及定义在该类型之上的一组操作。数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内部如何表示及实现无关。1.3计算下列程序段中x=x+1的语句频度。答：O(niijjk1111)=O(n3)2线性表2.1描述以下三个概念的区别：头指针，头结点，首元素结点。头指针：在一个链表中，称指向表头结点的指针为头指针。原因：由于单链表中每个结点的存储地址是存放在其前趋结点的指针域中的，而第一个结点无前趋，因而应设一个头指针H指向第一个结点。头结点：链表中不存放实际数据的表头结点称为头结点。原因：通过增加头结点，使得在插入（删除）结点到链表时，i=1和i1时的操作保持一致，从而简化算法。首元素结点：链表中存放实际数据的第一个结点。2.2（1）在顺序表中插入或删除一个元素，需要平均移动＿＿一半＿＿元素，具体移动的元素个数与＿＿插入或删除的位置＿＿有关。（2）在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置＿＿不一定＿相邻。（3）在带头结点的非空单链表中，头结点的存储位置由＿＿头指针＿＿指示，首元素结点的存储位置由＿＿头结点的next域＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿其直接前趋的next域＿＿指示。补充题：建立学生成绩单链表，实现对它的记录的遍历、插入和删除#includemalloc.h#includestdio.h#includestring.h#includeconio.hstructstudent{intnum;/*学号*/floatscore;/*成绩*/structstudent*next;/*指针域*/};#defineLENsizeof(structstudent)structstudent*create()/*此函数返回一个指向链表的头结点*/{structstudent*head;/*指向student类型变量的指针head为头指针*/structstudent*p,*tail;/*tail指向链表末尾元素，p指向新分配的结点*/floattemp;/*临时数据变量*/head=NULL;do{p=(structstudent*)malloc(sizeof(structstudent));/*分配新结点*/printf(NumberScore:);fflush(stdin);/*清除输入缓冲区*/scanf(%d%f,&p-num,&temp);if(p-num==0){free(p);break;};p-score=temp;/*取得结点数据*/p-next=NULL;if(head==NULL){head=p;tail=p;}else{tail-next=p;tail=p;/*指向尾结点*/}}while(p-num!=0);return(head);}voiddisplay(structstudent*head){structstudent*p;p=head;while(p!=NULL){printf(%4d%5.1f\n,p-num,p-score);p=p-next;}}structstudent*insert(structstudent*head,structstudent*new){structstudent*p,*q;if(head==NULL)head=new;else{if(head-num=new-num){new-next=head;head=new;}/*新结点插在链首*/else{p=head;while(p-numnew-num&&p-next!=NULL){q=p;p=p-next;}if(p-numnew-num){q-next=new;new-next=p;}else{p-next=new;new-next=NULL;}}}return(head);}structstudent*delete(structstudent*head,intnum)/*在头为head的单链表中将指定的学号为num的结点删除*//*算法返回新的链表的表头结点*/{structstudent*p1,*p2;/*设置两个指针，用以指示删除位置*/if(head==NULL)printf(\nListnull\n);else{p1=head;while(num!=p1-num&&p1-next!=NULL)/*p1所指的结点不是要删除的结点，且其后还有结点*/{p2=p1;p1=p1-next;/*后移一个结点*/}if(num==p1-num)/*找到了要删除的结点*/{if(p1==head)head=p1-next;/*若p1所指为第一个结点，则把第二个结点的地址赋给head*/elsep2-next=p1-next;/*否则将下一个结点的地址赋给前一个结点的指针域*/printf(delete:%4d\n,num);free(p1);}elseprintf(%4dnotbeenfound!\n,num);}return(head);}voidmain(){structstudent*head,*stu;floattemp;intnumber;printf(Inputrecords:\n);head=create();display(head);stu=(structstudent*)malloc(LEN);printf(InputtheinsertNumberScore:);scanf(%d%f,&stu-num,&temp);stu-score=temp;stu-next=NULL;head=insert(head,stu);display(head);printf(\nInputthenumbertodelete:);scanf(%4d,&number);head=delete(head,number);display(head);getch();}3栈和队列3.1按图3.1(b)回答相关问题：答：1、依次考虑最先出栈的车厢：123，132；213，231；321；2、不能得到435612的出栈序列，因为如果4最先出栈，则321依次排列直到栈底，无论后续如何操作，1均无法在2之前出栈；可以得到135426的出栈序列，过程如下：1S1X2S3S3X4S5S5X4X2X6S6X。3.3给出栈的两种存储结构名称，在这两种存储结构中如何判别栈空与栈满？答：1、顺序栈：栈顶指针为-1时栈为空，栈顶指针为栈规模-1时栈为满；2、链栈：栈顶指针的指针域为空时栈为空，理论上不存在栈满的情况。补充题：用顺序栈把输入的1个字符串反序输出#includestdio.h#defineM10typedefstructstack{chars[M];inttop;}StackType;intpush(StackType*st,charx){if(st-top==M-1){printf(Overflow);return(0);}st-top++;st-s[st-top]=x;return(1);}charpop(StackType*st){if(st-top==-1){printf(Stackempty);return(0);}return(st-s[st-top--]);}main(){StackTypey;inti;charz;y.top=-1;printf(pleaseinput10characters\n);for(i=0;iM;i++){scanf(%c,&z);push(&y,z);}printf(\n);for(i=0;iM;i++){z=pop(&y);printf(%c,z);}printf(\n);}本次实验常见错误：（1）没有调通。如果凭个人力量无法调通，应该求助别人（2）实验报告格式不全（3）scanf(“%s”,s)–不能输入空格（4）指针移动在pop函数外（5）pop函数中弹出所有元素4串4.1设s=‘IAMASTUDENT’,t=‘GOOD’,q=‘WORKER’。给出下列操作的结果：StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s,‘A’,4);StrReplace(s,‘STUDENT’,q);StrCat(StrCat(sub1,t),StrCat(sub2,q));如果考虑下标从1开始StrLength(s)=14;sub1=‘IAMA’;sub2=‘’;StrIndex(s,4,‘A’)=6;StrReplace(s,‘STUDENT’,q)=‘IAMAWORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))=‘IAMAGOODWORKER’;如果考虑下标从0开始StrLength(s)=14;sub1=‘AMAS’;sub2=‘S’;StrIndex(s,4,‘A’)=5;StrReplace(s,‘STUDENT’,q)=‘IAMAWORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))=‘AMASGOODSWORKER’;4.2编写算法，实现串的基本操作StrReplace(S,T,V)。#includestdio.h#includeconio.h#defineMaxSize100typedefstruct//定义串{charstr[MaxSize];intlen;}String;voidDisplay(String*s)//显示s串{inti;printf(\n);for(i=0;is-len;i++)printf(%c,s-str[i]);}voidStrDelete(String*s,i