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

数据结构课后作业参考答案浙江工商大学信电学院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()=O(n3)2 线性表2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。头指针：在一个链表中，称指向表头结点的指针为头指针。原因：由于单链表中每个结点的存储地址是存放在其前趋结点的指针域中的，而第一个结点无前趋，因而应设一个头指针H指向第一个结点。头结点：链表中不存放实际数据的表头结点称为头结点。原因：通过增加头结点，使得在插入（删除）结点到链表时，i=1和i1时的操作保持一致，从而简化算法。首元素结点：链表中存放实际数据的第一个结点。2.2（1） 在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。（2） 在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。（3） 在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。补充题：建立学生成绩单链表，实现对它的记录的遍历、插入和删除#include#include#include#includestruct studentint num; /*学号*/float score; /*成绩*/struct student *next; /*指针域*/;#define LEN sizeof(struct student)struct student *create() /*此函数返回一个指向链表的头结点*/ struct student *head; /*指向student类型变量的指针head为头指针*/struct student *p,*tail; /*tail指向链表末尾元素，p指向新分配的结点*/float temp; /*临时数据变量*/head=NULL;do p=(struct student *)malloc(sizeof(struct student);/*分配新结点*/printf(Number Score:);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;elsetail-next=p;tail=p; /*指向尾结点*/while(p-num!=0);return(head);void display(struct student *head)struct student *p;p=head;while(p!=NULL)printf(%4d %5.1fn,p-num,p-score);p=p-next;struct student *insert(struct student *head,struct student *new)struct student *p,*q;if(head=NULL)head=new;elseif(head-num=new-num)new-next=head;head=new;/*新结点插在链首*/elsep=head;while(p-numnum&p-next!=NULL)q=p;p=p-next;if(p-numnew-num)q-next=new;new-next=p;elsep-next=new;new-next=NULL;return(head);struct student *delete(struct student *head,int num)/*在头为head的单链表中将指定的学号为num的结点删除*/*算法返回新的链表的表头结点*/struct student *p1,*p2; /*设置两个指针，用以指示删除位置*/if(head=NULL) printf(nList nulln);elsep1=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*/else p2-next=p1-next;/*否则将下一个结点的地址赋给前一个结点的指针域*/printf(delete:%4dn,num);free(p1);else printf(%4d not been found!n,num);return(head);void main()struct student *head,*stu;float temp;int number;printf(Input records:n);head=create();display(head);stu=(struct student *)malloc(LEN);printf(Input the insert Number Score:);scanf(%d %f,&stu-num,&temp);stu-score=temp;stu-next=NULL;head=insert(head,stu);display(head);printf(nInput the number to delete:);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个字符串反序输出#include#define M 10typedef struct stackchar sM;int top;StackType;int push(StackType *st,char x)if(st-top=M-1)printf(Overflow);return(0);st-top+;st-sst-top=x;return(1);char pop(StackType *st)if(st-top=-1)printf(Stack empty);return(0);return(st-sst-top-);main()StackType y;int i;char z;y.top=-1;printf(please input 10 charactersn);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=I AM A STUDENT, 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= I AM A ; sub2= ; StrIndex(s,4, A)=6; StrReplace(s, STUDENT,q)= I AM A WORKER; StrCat(StrCat(sub1,t), StrCat(sub2,q)= I AM A GOOD WORKER;如果考虑下标从0开始StrLength(s)=14; sub1= AM A S; sub2= S; StrIndex(s,4, A)=5; StrReplace(s, STUDENT,q)= I AM A WORKER; StrCat(StrCat(sub1,t), StrCat(sub2,q)= AM A SGOODSWORKER;4.2 编写算法，实现串的基本操作StrReplace(S,T,V)。#include#include#define MaxSize 100typedef struct/定义串 char strMaxSize; int len;String;void Display(String *s)/显示s串 int i; printf(n); for(i=0;ilen;i+) printf(%c,s-stri);void StrDelete(String *s,int i,int k) /*删掉s串中位置i开始的k个字符*/int j; if (is-len | i+ks-len) printf(位置参数值错误n); else for (j=i+k;jlen;j+) /*将s的第i+k个位置之后的字串前移k位*/ s-strj-k=s-strj; s-len=s-len-k; /*修改s长度*/ s-strs-len=0; int StrIndex(String s,String t) /*求s串中t子串的位置（从0开始）*/int i,j;i=0;j=0; while(is.len & j=t.len)return(i-j); else return(-1); void StrInsert(String *s,int i,String t) /*s串中位置i处插入t串*/ String r; int j; if (is-len) printf(位置参数值错误n); else for (j=i;jlen;j+) /*将s的第i个位置之后的字串复制到r中*/ r.strj-i=s-strj; r.len=j-i; r.strr.len=0; for (j=0;jstri+j=t.strj;for(j=0;jstri+t.len+j=r.strj;s-len=s-len+t.len; /*修改s串长度*/ s-strs-len=0; String StrReplace(String s,String t,String v) /*s串中的t子串被v子串代替*/int i; i=StrIndex(s,t); while (i=0) StrDelete(&s,i,t.len); StrInsert(&s,i,v); i=StrIndex(s,t); return s; void StrAssign(String *s, char t)/*s串内容由t串内容代替*/int i=0;while(ti!=0)s-stri=ti;i+;s-stri=0;s-len=i;void main() String a,b,c,d; StrAssign(&a,fghabcdefghijk); a.len=11; StrAssign(&b,fgh); b.len=3; StrAssign(&c,dlg); c.len=3; Display(&a); Display(&b); Display(&c); d=StrReplace(a,b,c); Display(&d); getch();5 数组和广义表5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算：（1） 数组A共占用多少字节；（2） 数组A的最后一个元素的地址；（3） 按行存储时，元素a36的地址；（4） 按列存储时，元素a36的地址；答：1、数组A共占用668=288字节； 2、数组A最后一个元素的地址：1000+288-6=1282； 3、按行存储时元素a36的地址：1000+286+56=1126； 4、按列存储时元素a36的地址：1000+566+26=1192。5.3 设计以三元组表为存储结构的稀疏矩阵加法程序。#include#include#include#define MAXSIZE 100 /*非零元素的个数最多为100*/*稀疏矩阵三元组表的类型定义*/typedef struct int row,col; /*该非零元素的行下标和列下标*/ int e; /*该非零元素的值*/Triple;typedef struct Triple dataMAXSIZE+1; /* 非零元素的三元组表。data0未用*/int m,n,len; /*矩阵的行数、列数和非零元素的个数*/TSMatrix;void AddTSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C) /*矩阵B和矩阵A相加*/int i=0,j=0;C-m = A.m;C-n = A.n;C-len = 0;while(iA.len&jdataC-len.row = A.datai.row;C-dataC-len.col = A.datai.col;C-dataC-len+.e = A.datai.e+B.dataj.e;i+;j+;else if(A.datai.row = B.dataj.row)&(A.datai.col B.dataj.col)C-dataC-len.row = B.dataj.row;C-dataC-len.col = B.dataj.col;C-dataC-len+.e = B.dataj.e;j+;else if(A.datai.row = B.dataj.row)&(A.datai.col dataC-len.row = A.datai.row;C-dataC-len.col = A.datai.col;C-dataC-len+.e = A.datai.e;i+;else if(A.datai.row B.dataj.row)C-dataC-len.row = B.dataj.row;C-dataC-len.col = B.dataj.col;C-dataC-len+.e = B.dataj.e;j+;else /if(A.datai.row dataC-len.row = A.datai.row;C-dataC-len.col = A.datai.col;C-dataC-len+.e = A.datai.e;i+;if(i=A.len&jdataC-len.row = B.dataj.row;C-dataC-len.col = B.dataj.col;C-dataC-len+.e = B.dataj.e;j+;else if(idataC-len.row = A.datai.row;C-dataC-len.col = A.datai.col;C-dataC-len+.e = A.datai.e;i+;void ShowTSMatrix(TSMatrix M)/*打印矩阵M*/ int i,j,dir=0;for (i=0;iM.m;i+)for (j=0;jlen=0;for (i=0;im;i+)for (j=0;jn;j+)if(rand()dataM-len.row = i;M-dataM-len.col = j;M-dataM-len.e = 1;M-len+;void main()TSMatrix A, B, C;A.m=5;A.n=5;B.m=5;B.n=5;srand( (unsigned)time(NULL) );InitTSMatrix(&A);printf(The matrix A is:n);ShowTSMatrix(A);InitTSMatrix(&B);printf(The matrix B is:n);ShowTSMatrix(B);AddTSMatrix(A, B, &C);printf(The matrix C is:n);ShowTSMatrix(C);6 树和二叉树6.1试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态具有3个结点的树 具有3个结点的二叉树6.3 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，nk个度为k的结点，则该树中有多少个叶子结点？树上结点总数n=n0 + n1 + + nk分支总数B=n1 + 2n2 + 3n3 + + knk除了根结点，每个分支都对应一个结点，n= B + 1 n0 + n1 + + nk = n1 + 2n2 + 3n3 + + knk + 1 n0 = n2 + 2n3 + + (k-1)nk + 16.4 假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。EB FA D HC G I K J6.9 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10, 请为这8个字母设计哈夫曼编码，100.400.210.190.600.280.110.060.050.030.02010011100.320010000.170.100.0700110010000100000001100010补充：用输入的n个整数建立n个结点的完全二叉树#include#include#include#define MAX 1000struct nodeint data;struct node *lc; /*left左指针*/struct node *rc; /*right右指针*/;typedef struct node NODE;int setuptree(NODE *adrMAX)NODE *p;int i; /*i结点个数控制变量*/int n; /*n为结点的个数*/int k; /*k为结点的编号*/int f; /*f左右结点控制变量*/printf(Enter the number of nodes:);scanf(%d,&n);for(i=1;ilc=p-rc=NULL;adri=p;for(i=1;idata);if(k1)f=k/2;if(k%2=0)adrf-lc=p;else adrf-rc=p;return 0;void pre_order(struct node *p)if(p!=NULL)printf(%d,p-data);pre_order(p-lc);pre_order(p-rc);void main() NODE *adrMAX; memset(adr, 0, MAX*sizeof(NODE*); setuptree(adr); pre_order(adr1);7 图7.1 已知如图7.28所示有向图，请给出该图的：（1） 每个顶点的入度、出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表；（5） 十字链表；（6） 强连通分量。答：1、每个顶点的入度和出度：顶点123456入度321122出度022313 2、邻接矩阵： 3、邻接表：4、逆邻接表：5、十字链表：略6、强连通分量：7.3 已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。答：源点 终点 最短路径 路径长度 1 2 1，3，2 19 3 1，3 15 4 1，3，2，4 29 5 1，3，5 25 6 1，3，2，4，6 44 中间过程No.V2V3V4V5V6SV-S11,2(20)1,3(15)12,3,4,5,621,3,2(19)1,3(15)1,3,5(25)1,32,4,5,631,3,2(19)1,3(15)1,3,2,4(29)1,3,5(25)1,2,34,5,641,3,2(19)1,3(15)1,3,2,4(29)1,3,5(25)1,3,2,4,6(44)1,2,3,45,6补充：输入每条边的顶点u和 v及其权值w，然后建立用邻接矩阵表示的图#include#define MAX_VERTEX_NUM 10 /*最多顶点个数*/#define INFINITY 32768 /*表示极大值, 即*/#define Ok 1#define AdjType int#define OtherInfo int#define Error -1typedef enum DG, DN, UDG, UDN GraphKind;/*图的种类:DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网*/typedef char VertexData; /*假设顶点数据为字符型*/typedef struct ArcNodeAdjType adj; /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/OtherInfo info;ArcNode;typedef structVertexData vexsMAX_VERTEX_NUM;/*顶点向量*/ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; /*邻接矩阵*/int vexnum, arcnum; /*图的顶点数和弧数*/GraphKind kind; /*图的种类标志*/AdjMatrix; /*（Adjacency Matrix Graph）*/int LocateVertex(AdjMatrix *G, VertexData v) /*求顶点位置函数*/int j=Error, k;for(k=0; kvexnum; k+)if(G-vexsk=v)j=k;break;return(j);int CreateDN(AdjMatrix *G) /*创建一个无向网*/int i, j, k, weight;VertexData v1, v2;scanf(%d, %dn, &G-arcnum, &G-vexnum);/*输入图的顶点数和弧数*/for(i=0; ivexnum; i+) /*初始化邻接矩阵*/for(j=0; jvexnum; j+)G-arcsij.adj=INFINITY;for(i=0; ivexnum; i+)scanf(%c, &G-vexsi);/* 输入图的顶点*/scanf(%c,&v1);for(k=0; karcnum; k+)scanf(%c,%c,%d%c, &v1, &v2, &weight);/*输入一条弧的两个顶点及权值*/i=LocateVertex(G, v1);j=LocateVertex(G, v2);G-arcsij.adj=weight;/*建立弧*/G-arcsji.adj=weight;/*建立弧*/return(Ok);void DisplayDN(AdjMatrix *G) /*显示一个网*/int i,j;printf( ); for(i=0; ivexnum; i+)printf( %c , G-vexsi); /* 输出图的顶点*/printf(n); /* 换行*/for(i=0; ivexnum; i+) printf(%c , G-vexsi); /* 输出图的顶点*/for(j=0; jvexnum; j+)if(G-arcsij.adj = INFINITY)printf( );elseprintf(%-4d, G-arcsij.adj);printf(n); /* 换行*/void main()AdjMatrix G;CreateDN(&G);DisplayDN(&G);/*test data:5,5BCADEA,B,20B,D,10A,C,88E,C,76B,E,23*/8 查找8.1 若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？（1） 查找不成功，即表中没有关键字等于给定值K的记录。（2）查找成功，且表中只有一个关键字等于给定值K的记录。（3）查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。(1) 不同。因为有序顺序表搜索到其关键字比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。(2) 相同。搜索到表中对象的关键字等于给定值时就停止搜索，报告成功信息。(3) 不同。有序顺序表中关键字相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键字相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键字的对象都找了出来，所需时间就不相同了。前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。 补充：对输入的n个整数进行折半查找#define M 50#include#includemain()int i,length;int low,high,mid;int key,s;int stM;printf(Please input SSTable length:n);scanf(%d,&length);printf(Please input SSTable data:n);for(i=1;i=length;i+)printf(%d:t,i);scanf(%d,&sti);while(1)s=0;printf(Please input Search Key:n);scanf(%d,&key);if(key=-1)return(0);low=1;high=length;while(low=high)mid=(low+high)/2;if(keystmid)