高等学校——数据结构习题答案.doc

第一章1、简述下列术语：数据元素、数据、数据对象、数据结构、存储结构和算法解：数据元素：数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。数据：信息的载体。是描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。数据对象：性质相同的数据元素的集合，是数据的一个子集。数据结构：相互之间存在着一种或多种关系的数据元素的集合，包括数据的逻辑结构和物理结构两方面的内容。存储结构：数据的逻辑结构在计算集中的表示方式，包含顺序存储方法、链接存储方法、索引存储方法、散列存储方法。算法： 对特定问题求解步骤的一种描述，它是指令或语句的有限序列，并具有有穷型、确定性、可行性、输入和输出五个重要特性。2、试写一算法，自大至小依次输出顺序读入的三个整数x，y和z的值解：void f1(void)int x,y,z;printf(enter x,y,z:);scanf(%d,%d,%d,&x,&y,&z);if(xy)if(yz)printf(%d,%d,%d,x,y,z);elseif(xz)printf(%d,%d,%d,x,z,y);elseprintf(%d,%d,%d,z,x,y);elseif(xz)printf(%d,%d,%d,y,x,z);elseif(zy)printf(%d,%d,%d,z,y,x);elseprintf(%d,%d,%d,y,z,x);3、举出一个数据结构的例子，叙述其逻辑结构、存储结构、运算等三方面的内容解：4、分析下列算法的时间复杂度：（1）int prime(int n)for(i=2;isqrt(n);i+)if(n%i=0)return 0;return 1;解：O(n1/2)（2）long sun(int n)s=0;for(i=1;i=n;i+)for(p=1,j=1;jlen=0) return -1; /* 表已空*/while (ilen)if(L-elemi=x)for (j=i;jlen-1;j+)L-elemj=L-elemj+1;/*被删除元素之后的元素左移 */-L-len;elsei+;return 1;4、设线性表(a1，a2，an)存储在带表头结点的单链表中，试设计算法，求出该线性表中值为x的元素的序号。如果x不存在，则序号为0。int Index_Linkst( LNode *H,ELEMTP x)p=H-next; j=1;f=0; /* P 指向第一个结点，j为计数器，f为标志 */while( p )if(p-data!=x)j+;p=p-next; elsef=1;if( f=1 ) return j;elsereturn 0;5、在一个非递减有序线性表中，插入一个值为x的元素，使插入后的线性表仍为非递减有序。分别写出用顺序表和单链表表示时的算法。顺序表：int Insert_Sq (SqList *L ,ELEMTP x)if ( L-len= MAXSIZE-1) return -1; /* 表已满 */if(x=L-elemL-len)L-elemL-len+1=x;L-len+=1;elsei=1;while (x=L-elemi)i+;for(j=L-len;j=i;j-)L-elemj+1=L-elemj;L-elemi=x;L-len+=1;return 1;单链表：int Insert_Linkst (LNode *H, ELEMTP x)p=H;s= (LNode *) malloc (sizeof(LNode); if(s)s-data=x;s-next=NULL;elsereturn 0;while ( p-next)if(p-next-datanext;elses-next=p-next; p-next=s; /* 插入 */return 1;/* Insert_Linkst*/p-next=s;return 1;6、设一个线性表L=(a1，a2，a n)，编写算法将其逆置，即成为（a n，an-1，a2，a1）。要求逆置后的线性表仍占用原来的存储空间，并且用顺序和单链表两种方法表示，写出不同的处理过程。 顺序表：void inverse_Sq( SqList *L ）int i;ELEMTP x;for(i=1;ilen/2;i+)x=L-elemi;L-elemi=L-elemL-len-i+1;L-elemL-len-i+1=x;单链表：void inverse_Linkst (LNode *H）d=h-next;if(d!=NULL)p=d-next;while(p)t=p-next;p-next=d;d=p;p=t;h=d;7、设两个单链表A和B，它们的数据元素分别为(x1，x2，,x m)和(y1，y2 ，y n)。设计一个算法将它们合并为一个单链表C，使得： 当mn时，C(x1，y1，x2，y2，.，x n，y n，.,x m )当nm时，C(y1，x1，y2，x2，.，y m ，x m，.,y n )。LNode * Link_Linkst( LNode *A,LNode *B )p=A-next;q=B-next;m=0;n=0;while(p)m+;p=p-next;while(q)n+;q=q-next;if(m=n)p=A-next;q=B-next;C=A;elsep=B-next;q=A-next;C=B;while(q)t=p-next;p-next=q;q=q-next;p-next-next=t;p=t;return C;8、试写一算法，在无表头结点的单链表中值为a的结点前插入一个值为b的结点, 如果a不存在，则把b插在表尾 。将该算法与第2.3.2节中的算法 27进行比较。void Insertx_Linkst (LNode *H, Elemtp a, Elemtp b)s=(LNode *) malloc (sizeof(LNode); s-data=b;s-next=NULL;if(H=NULL)H=s;elsep=H;q=p-next;if(p-data=a)/*对首元节点处理*/s-next=p;H=s;elsewhile(q&q-data!=a)p=q;q=q-next;p-next=s;s-next=q;9、假设有一个单向循环链表，其结点包含三个域：data，pre和next，其中data为数据域，next为指针域，其值为后继结点的地址，pre也为指针域，其初值为空（NULL），试设计算法将此单向循环链表改为双向循环链表。void Change_Linkst (LNode *H)q=H;p=H-next;while(p)p-pre=q;q=p;p=p-next;H-pre=q;q-next=H;10、已知二维数组A57，其每个元素占四个存储单元，且A00的存储地址为1100，试求出元素A35的存储地址（分别讨论以行为序和以列为序方式存储时的结论）。行为序1100+4*(3*7+5)=1204列为序1100+4*(5*5+3)=121211、设有一个二维数组AMN，对以下三种情况分别编写算法：（1） 求数组A的最外围元素之和； （2）求从A00开始的互不相邻的各元素之和； （3）当M=N时，分别求两条对角线上的元素之和，否则输出MN的信息。int A1(int AMN)/* 求数组A的最外围元素之和*/s=0;for(i=0;iM;i+)if(i=0|i=M-1)for(j=0;jN;j+)s+=Aij;elses+=Ai0+AiN-1;return s;int A2(ELEMTP AMN)/* 求从A00开始的互不相邻的各元素之和*/s=0;for(i=0;iM;i+)if(i%2=0)j=0;elsej=1;for(;jN;j+=2)s+=Aij;return s;void A3(int AMN,int *s1,int *s2)/* 分别求两条对角线上的元素之和*/*s1=0;/* */*s2=0; /* / */if(M!=N)printf(M!=N);elsefor(i=0;iM;i+)*s1+=Aii;*s2+= AiN-1-i;12、现有如下所示的稀疏矩阵A，试写出它的三元组表和十字链表。 3 0 0 7 0 0 -1 0 2 0 0 00 0 0 0 0 0 0 -3A=解：（1）ijv01131147223-13312454-3（2） 5 4 -3 1 1 3 2 3 -1 3 1 2 1 4 7 M.cheadM.rhead13、假设稀疏矩阵A和B（具有相同的行列数）都采用三元组表示，编写算法计算C=A+B。/*思路：依次扫描A、B的行号和列号，若A的当前项的行号等于B当前项的行号，则比较其列号，将较小列号的项放入C，如果列号也相等，相加后放入C；若A当前项的行号小于B当前项的行号，则将A项放入C，否则将B项放入C*/void matadd( SpMatTp *A, SpMatTp *B, SpMatTp *C)int i=1;j=1,k=1;while(im&jm)/*若A的当前项的行号等于B当前项的行号，则比较其列号，将较小列号的项放入C，如果列号也相等，相加后放入C；*/if(A-elemi.i=B-elemj.i)if(A-elemi.jelemj.j)C-elemk.i=A-elemi.i;C-elemk.j=A-elemi.j;C-elemk.v=A-elemi.v;k+;i+;elseif(A-elemi.jB-elemj.j)C-elemk.i=B-elemj.i;C-elemk.j=B-elemj.j;C-elemk.v=B-elemj.v;k+;j+;elseC-elemk.i=B-elemj.i;C-elemk.j=B-elemj.j;C-elemk.v=B-elemj.v+A-elemi.v;k+;j+;i+;elseif(A-elemi.ielemj.i)/*若A当前项的行号小于B当前项的行号，则将A项放入C*/C-elemk.i=A-elemi.i;C-elemk.j=A-elemi.j;C-elemk.v=A-elemi.v;k+;i+;else/*若A当前项的行号大于B当前项的行号，则将B项放入C*/C-elemk.i=B-elemj.i;C-elemk.j=B-elemj.j;C-elemk.v=B-elemj.v;k+;j+;C-m=A-m;/*C的行数*/C-n=A-n;/*C的列数*/C-t=k-1;/*C的非零元个数*/14、设稀疏矩阵A用十字链表表示，编写算法查找元素： （1）已知i，j，查找Aij； （2）已知x的值，查找它在第几行第几列。解：（1）int findmat(CrossList *M,int i,int j,int *val)if(imu&i0)p=M-rheadi;while(p)if(p-col=j)*val=p-val;return 1;/*找到*/elsep=p-right;return 0;/*未找到*/else return -1;/*行号错误*/（2）int findmat(CrossList *M,int x,int *rown,int *coln)for(int i=1;imu;i+)p=M-rheadi;while(p)if(p-val=x)*rown=p-row;*coln=p-col;return 1;elsep=p-right;return 0;上机实习题1. 设A=（a1, a2 ,an）和B=（b1, b2, ,bm）是两个线性表，其数据类型是整型。若n=m 且ai = bi(1in),则称A=B；若ai = bj（1ij），而aj bj (jnm),则称AB；除此以外，均称A=B。设计一个比较A、B大小的程序。 #include #define MAXSIZE 100typedef structint elemMAXSIZE; /*存储线性表中的元素*/int len; /*线性表的当前表长*/SqList;SqList * InitList(SqList *L)L=(SqList *)malloc(sizeof(SqList);L-len=0;return L;int Insert(SqList *L,int i,int x)int j;if (iL-len+1)return 0; /* 不合理的插入位置 i */if ( L-len= MAXSIZE-1)return -1; /* 表已满 */for (j=L-len;j=i;-j)L-elemj+1=L-elemj; /* 插入位置及之后的元素右移*/L-elemi=x; /*插入x */+L-len; /*表长加1 */return 1;int f(SqList *A,SqList*B)SqList *As=NULL,*Bs=NULL;int i=1,j,ms=0,ns=0;As=InitList(As);Bs=InitList(Bs);while(A-elemi=B-elemi)i+;for(j=i;jlen;j+)Insert(As,j-i+1,A-elemj);for(j=i;jlen;j+)Insert(Bs,j-i+1,B-elemj);ms=As-len;ns=Bs-len;if(ms=ns&ms=0)return 0;elseif(ms=0&ns0|(ms0&ns0&As-elem1elem1)return -1;elsereturn 1;int main()SqList *A=NULL,*B=NULL;int n=0,m=0,i=0,d=0;A=InitList(A);B=InitList(B);if(A!=B)printf(A!=B);elseprintf(A=B);printf(nInput n:);scanf(%d,&n);for(i=1;i=n;i+)printf(a%d:,i);scanf(%d,&d);Insert(A,i,d);for(i=1;ilen;i+)printf(%d ,A-elemi);printf(n);printf(nInput m:);scanf(%d,&m);for(i=1;i=m;i+)printf(b%d:,i);scanf(%d,&d);Insert(B,i,d);for(i=1;ilen;i+)printf(%d ,B-elemi);printf(n);printf(n);for(i=1;ilen;i+)printf(%d ,A-elemi);printf(n);for(i=1;ilen;i+)printf(%d ,B-elemi);i=f(A,B);if(i=0)printf(A=B);elseif(i0)printf(AB);return 0;2. 设计一个程序求出约瑟夫环的出列顺序。约瑟夫（Joseph）问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。例如n=7,7个人的密码依次为：3，1，7，2，4，8，4，m的初值取6，则正确的出列顺序应为6，1，4，7，2，3，5。要求使用单向循环链表模拟此出列过程。#include typedef struct nodeint data;struct node *next;int id;LNode;LNode * insert (LNode *rear,int x,int id)LNode *s;s=(LNode *)malloc(sizeof(LNode);s-data=x;s-id=id;if(rear=NULL)rear=s;s-next=s;return rear;elses-next=rear-next;rear-next=s;rear=s;return rear;int main()LNode *rear=NULL,*p=NULL,*q=NULL;int d,m,i=1;printf(input:);scanf(%d,&d);while(d!=0)rear=insert(rear,d,i+);printf(ninput:);scanf(%d,&d);p=rear-next;/*显示数据*/while(p!=rear)printf(%d ,p-data);p=p-next;printf(%d,p-data);printf(input m:);/*输入初始m*/scanf(%d,&m);p=rear;while(p!=p-next)for(i=1;inext;q=p-next;p-next=q-next;m=q-data;printf(%d ,q-id);free(q);printf(%d ,p-id);free(p);return 0;第三章习 题l假定有编号为A、B、C的3辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序(注：每一列车由站台开出时均可进栈，出栈开出站台，但不允许出栈后回退)。写出每一种可能的序列。解：产生：ABC、ACB、BAC、BCA、CBA不会产生：CAB2有字符串次序为5*-y-a/y2，试利用栈排出将次序改变为5y-*ay/-的操作步骤（可用X代表扫描该字符串过程中顺序取一字符进栈的操作，用S代表从栈中取出一字符加到新字符串尾的出栈的操作）。例如，ABC变为BCA的操作步骤为XXSXSS。解：XSXXXSSSXXSXXSXXSSSS3写出链栈的取栈顶元素和置栈空的算法。解：（1）int GetTop(SNode *top,ELEMTP *Y)if(top=NULL)return -1else*y=top-data;return 1;（2）SNode * Empty(SNode *top)while(top)p=top;top=top-next;free(p);return NULL;4假设一个算术表达式中包含圆括弧、方括弧和花括弧，编写一个判别表达式中括弧是否正确配对的算法。解：int f()InitStack(p);Push(p,#);c=getchar();while(c!=#|GetTop(p)!=#)if(c=(|c=|c=)Push(p,c);if(c=)Pop(p,o);if(o!=() return -1;if(c=)Pop(p,o);if(o!=) return -1;if(c=)Pop(p,o);if(o!=) return -1;c=getchar();return 1;5写出计算表达式5+3*4/6-7时操作数栈和运算符栈的变化情况。解：步骤OPTROPND输入字符1#5+3*4/6-7#2#5+3*4/6-7#3#+53*4/6-7#4#+5，3*4/6-7#5#+*5，34/6-7#6#+*5，3，4/6-7#7#+5，12/6-7#8#+/5，126-7#9#+/5，12，6-7#10#+5，2，-7#11#7-7#12#-77#13#-7，7#14#0#6对于给定的十进制正整数，打印出对应的八进制正整数。(1)写出递归算法。(2)写出非递归算法。解：int f(int n)/* 递归算法*/if (n1)/*退栈求值*/fval=stacktop0;top-;stacktop2=fval;stacktop0=stacktop1*stacktop2;return(stacktop0);8对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。解：(sq.front-sq.rear+m)%m9假设用一个数组QM来表示队列，该队列只设一个队头指针front，不设队尾指针而改设计数器count用以记录队列中元素的个数。试编写出相应的置空队列，入队列和出队列的算法。解：typedef struct ELEMTP elemMAXSIZE; int front; /*队头*/ int count; MySqQueue;void Empty(MySqQueue *Sq)/*置空队列*/Sq-front=0;Sq-count=0;int EnQueue(MySqQueue *Sq，ELENTP x)/* 在循环队列Sq的尾部插入一个新的元素x */ if(Sq-count=MAXSIZE)return -1;/*队列上溢*/elseSq-count+;Sq-elem(Sq-front+Sq-count)%MAXSIZE=x;return 1;int DelQueue(MySqQueue *Sq，ELEMTP *y)/*删除循环队列Sq的队头元素，并存人*y中*/if(Sq-count=0)return -1;/*队列下溢*/elseSq-front=(Sq-front+1)%MAXSIZE;*y=Sq-elemSq-front;Sq-count-;return 1;10假设以带头结点的循环链表示列队，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写出相应的置空队列，入队列和出队列的算法。解：typedef struct node /*结点结构*/ELEMTP data;struct node *next;QNode;typedef structQNone *rear; /*队尾指针*/MyLQueue;void Empty(MyLQueue *Lq)/*置空队列*/if(Lq-rear!=NULL)/*循环队列为非空*/head=Lq-rear-next;while(head!=Lq-rear)p=head;head=head-next;free(p);free(head);Lq-rear=NULL;int EnQueue(MyLQueue *Lq，ELENTP x)/* 在循环队列Sq的尾部插入一个新的元素x */ p=(QNone *)malloc(sizeof(QNone);if(p=NULL)return -1;elsep-data=x;p-next=NULL ;if(Lq-rear=NULL)/*循环队列为空*/Lq-rear=p;p-next=p;elsehead=Lq-rear-next;Lq-rear-next=s;Lq-rear=s;s-next=head;return 1;int DelQueue(MyLQueue *Lq，ELEMTP *y)/*删除循环队列Sq的队头元素，并存人*y中*/if(Lq-rear=NULL)/*队列下溢*/return -1;elsehead=Lq-rear-next;if(head=Lq-rear)/*只有一个节点*/*y=head-data;free(head);Lq-rear=NULL;else*y=head-data;Lq-rear-next=head-next;free(head);return 1;上机实习题1设计一个算法，检验C源程序代码中的括弧对是否正确配对。要求在某个C源程序文件上对你的算法进行验正。#include typedef struct nodechar data;struct node *next;SNode; SNode * Push(SNode *top , char x)SNode *p;p=(SNode *)malloc(sizeof(SNode);p-data=x;p-next=top;top=p;return top;SNode *Pop(SNode *top , char *y, int *flag)SNode *p;if(top=NULL)*flag=0; /*链栈已空*/else /*出栈*/p=top;*y=p-data; top=p-next;*flag=1; return top;int main(int argc, char *argv)FILE *fp;char ch,o;int flag=1;SNode *p=NULL;if(argc!=2)printf(You forgot to enter the filenamen);exit(1);if(fp=fopen(argv1,r)=NULL)printf(cannot open filen);exit(1);ch=getc(fp);while(ch!=EOF)if(ch=(|ch=|ch=)printf(Push%cn,ch);p=Push(p,ch);if(ch=)p=Pop(p,&o,&flag);printf():Pop%c,%dn,o,flag);if(flag=0)printf(d lose ();elseswitch (o)case ( :break;case :printf(lose );exit(0);case :printf(lose );exit(0);if(ch=)p=Pop(p,&o,&flag);printf(:Pop%c,%dn,o,flag);if(flag=0)printf(d lose );elseswitch (o)case ( :printf(lose );exit(0);case :break;case :printf(lose );exit(0);if(ch=)p=Pop(p,&o,&flag);printf(:Pop%c,%dn,o,flag);if(flag=0)printf(d lose );elseswitch (o)case ( :printf(lose );exit(0);case :printf(lose );exit(0);case :break;ch=getc(fp);p=Pop(p,&o,&flag);if(flag=0)printf(OK);while(flag!=0)/*如果栈未空*/switch (o) case ( :printf(lose );break; case :printf(lose );break; case :printf(lose );break;p=Pop(p,&o,&flag);fclose(fp);return 0;2设计程序，模拟手机的某些短信息功能。功能要求：（1）接受短信息，若超过存储容量（如最多可存储20条），自动将最早接受的信息删除。（2）显示短信息数量。（3）逐条显示短信息（从最新的开始）；（4）删除其中的任意一条短信息；（5）清除。/*（1）接受短信息，若超过存储容量（如最多可存储20条），自动将最早接受的信息删除。（2）显示短信息数量。（3）逐条显示短信息（从最新的开始）；（4）删除其中的任意一条短信息；（5）清除。*/#include #include #include #define MAXSIZE 20/*存储容量*/#define INFOLEN 100/*信息长度*/typedef struct node /*结点结构*/ char InfoINFOLEN; struct node *next; QNode;typedef struct QNode * front; /*队头指针*/ QNode * rear; /*队尾指针*/ int count;MyInfo;MyInfo *Init() /*初始化*/MyInfo *p;QNode *q;p=(MyInfo *)malloc(sizeof(MyInfo);p-count=0;q=(QNode *)malloc(sizeof(QNode);q-next=NULL;p-front=q;p-rear=q;return p;int GetNew(MyInfo *Lq)/* 获得新短信 */ time_t t;struct tm