《数据结构课后答案.doc》由会员分享，可在线阅读，更多相关《数据结构课后答案.doc（76页珍藏版）》请在三一办公上搜索。
1、第一章绪论一、问答题1. 什么是数据结构？2. 叙述四类基本数据结构的名称与含义。3. 叙述算法的定义与特性。4. 叙述算法的时间复杂度。5. 叙述数据类型的概念。6. 叙述线性结构与非线性结构的差别。7. 叙述面向对象程序设计语言的特点。8. 在面向对象程序设计中，类的作用是什么？9. 叙述参数传递的主要方式及特点。10. 叙述抽象数据类型的概念。二、判断题（在各题后填写“”或“”）1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ）2. 算法就是程序。（ ）3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（ ）三、计算下列程序段中X=X+1的语句频度
2、for(i=1;i=n;i+) for(j=1;j=i;j+)for(k=1;k=j;k+) x=x+1;【解答】i=1时： 1 = (1+1)1/2 = (1+12)/2 i=2时： 1+2 = (1+2)2/2 = (2+22)/2 i=3时： 1+2+3 = (1+3)3/2 = (3+32)/2 i=n时： 1+2+3+n = (1+n)n/2 = (n+n2)/2x=x+1的语句频度为：f(n) = (1+2+3+n) + (12 + 22 + 32 + + n2 ) / 2 = (1+n)n/2 + n(n+1)(2n+1)/6 / 2 =n(n+1)(n+2)/6 =n3/6+n
3、2/2+n/3区分语句频度和算法复杂度：O(f(n) = O(n3)四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出【解答】（1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用
4、内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue() int i,n;float x,a,p; printf(“nn=”); scanf(“%f”,&n); printf(“nx=”); scanf(“%f”,&x);for(i=0;in;i+) scanf(“%f ”,&ai); /*执行次数：n次 */ p=a0; for(i=1;i=n;i+) p=p+
5、ai*x; /*执行次数：n次*/ x=x*x;printf(“%f”,p); 算法的时间复杂度：T(n)=O(n) 通过参数表中的参数显式传递float PolyValue(float a , float x, int n) float p,s;int i;p=x; s=a0;for(i=1;inext=S;（2）P-next= P-next-next;（3）P-next= S-next;（4）S-next= P-next;（5）S-next= L;（6）S-next= NULL;（7）Q= P;（8）while(P-next!=Q) P=P-next;（9）while(P-next!=NU
6、LL) P=P-next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;2.4 已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。Status Insert_SqList(SqList &va,int x)/把x插入递增有序表va中 if(va.length+1va.listsize) return ERROR; va.length+; for(i=va.length-1;va.elemix&i=0;i-) va.elemi+1=va.elemi; va.elemi+1=x; return OK;/Insert_SqList2.5 写
7、一算法，从顺序表中删除自第i个元素开始的k个元素。提示：注意检查i和k的合法性。 （集体搬迁，“新房”、“旧房”） 以待移动元素下标m（“旧房号”）为中心，计算应移入位置（“新房号”）： for ( m= i1+k; mlast; m+) Lelem mk = Lelem m ; 同时以待移动元素下标m和应移入位置j为中心： 以应移入位置j为中心，计算待移动元素下标：2.6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它
8、们的值为任意的整数）。 Status Delete_Between(Linklist &L,int mink,int maxk)/删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 p=L; while(p-next-datanext; /p是最后一个不大于mink的元素 if(p-next) /如果还有比mink更大的元素 q=p-next; while(q-datanext; /q是第一个不小于maxk的元素 p-next=q; /Delete_Between2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2., an）逆置为（an
9、, an-1,., a1）。（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。（2）以单链表作存储结构。方法1:在原头结点后重新头插一遍方法2:可设三个同步移动的指针p, q, r，将q的后继r改为p2.8假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C.提示：参P.28 例2-1void merge(LinkList A; LinkList B; LinkList *C) pa=Anext; pb=Bnext; *C=
10、A; (*C)next=NULL;while ( pa!=NULL & pb!=NULL ) if ( padata data ) smaller=pa; pa=panext; smallernext = (*C)next; /* 头插法 */ (*C)next = smaller;else smaller=pb; pb=pbnext; smallernext = (*C)next; (*C)next = smaller;while ( pa!=NULL) smaller=pa; pa=panext; smallernext = (*C)next; (*C)next = smaller;whi
11、le ( pb!=NULL) smaller=pb; pb=pbnext; smallernext = (*C)next; (*C)next = smaller;LinkList merge(LinkList A; LinkList B) LinkList C；pa=Anext; pb=Bnext; C=A; Cnext=NULL; return C; while(pa|pb) if(pa-datadata|!pb) pc=pa;q=pa-next;pa-next=pre;pa=q; /将A的元素插入新表 else pc=pb;q=pb-next;pb-next=pre;pb=q; /将B的元
12、素插入新表 pre=pc; C=A;A-next=pc; /构造新表头/reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.2.9假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。提示：设指针p指向s结点的前趋的前趋，则p与s有何关系？Status Delete_Pre(CiLNode *s)/删除单循环链表中结点s的直接前驱 p=s; while(p-next-next!=s) p=p-next; /找到s的前驱的前驱p p-
13、next=s; return OK;/Delete_Pre2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)/把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型. s=L-next; A=(CiList*)malloc(sizeof(CiLNode);p=A;
14、B=(CiList*)malloc(sizeof(CiLNode);q=B; C=(CiList*)malloc(sizeof(CiLNode);r=C; /建立头结点 while(s) if(isalphabet(s-data) p-next=s;p=s; else if(isdigit(s-data) q-next=s;q=s; else r-next=s;r=s; /while p-next=A;q-next=B;r-next=C; /完成循环链表/LinkList_Divide2.11 设线性表A=(a1, a2,am)，B=(b1, b2,bn)，试写一个按下列规则合并A、B为线性表
15、C的算法，使得： C= (a1, b1,am, bm, bm+1, ,bn) 当mn时；或者 C= (a1, b1,an, bn, an+1, ,am) 当mn时。线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。提示：void merge(LinkList A; LinkList B; LinkList *C) 或：LinkList merge(LinkList A; LinkList B)void merge1(LinkList &A,LinkList &B,LinkList &C)/把链表A和B合并为C,A和B的元素间隔
16、排列,且使用原存储空间 p=A-next;q=B-next;C=A; while(p&q) s=p-next;p-next=q; /将B的元素插入 if(s) t=q-next;q-next=s; /如A非空,将A的元素插入 p=s;q=t; /while/merge12.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。提示：注明用头指针还是尾指针。void Divide_LinkedPoly(LinkedPoly &L,&A,&B)/把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B p
17、=L-next; A=(PolyNode*)malloc(sizeof(PolyNode); B=(PolyNode*)malloc(sizeof(PolyNode); pa=A;pb=B; while(p!=L) if(p-data.exp!=2*(p-data.exp/2) pa-next=p;pa=p; else pb-next=p;pb=p; p=p-next; /while pa-next=A;pb-next=B; /Divide_LinkedPoly2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加
18、1的运算 。提示：可将低位放在前面。2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。提示：float PolyValue(Polylist p; float x) 第三章栈和队列1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。【解答】（1）可能得到的出站车厢序列是：123、132、213、231、321。(2)不能得到
19、435612的出站序列。因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时按照“后进先出”的原则，出栈的顺序必须为X(2)X(1)。能得到135426的出站序列。因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、
20、E、C、C、C （4） A、C、E、C提示： A、B、C、D、E （输出队首元素A） A、B、C、D、E、A （把队首元素A插入到队尾） B、C、D、E、A （删除队首元素A） C、D、E、A （再次删除队首元素B） C、D、E、A （输出队首元素C） C、D、E、A、C （把队首元素C插入到队尾） D、E、A、C （删除队首元素C） E、A、C （再次删除队首元素D）3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： AB【解答】 5.试写一个算法，判断
21、依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。提示：（1）边读边入栈，直到&（2）边读边出栈边比较，直到int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0 InitStack(s); while(e=getchar()!=&) push(s,e); while(e=getchar()!=) if(StackEmpty(s) return 0; pop(s,c); if(e!=c) return 0; i
22、f(!StackEmpty(s) return 0; return 1;/IsReverse6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。void NiBoLan(char *str,char *new)/把中缀表达式str转换成逆波兰式new p=str;q=new; /为方便起见,设str的两端都加上了优先级最低的特殊符号 InitStack(s); /s为运算符栈 while(*p) if(*p是字母) *q+=*p; /直接输出 else c=gettop(s); if(*p优先级比c高) push(
23、s,*p); else while(gettop(s)优先级不比*p低) pop(s,c);*(q+)=c; /while push(s,*p); /运算符在栈内遵循越往栈顶优先级越高的原则 /else /else p+; /while/NiBoLan /参见编译原理教材7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列Q Q=(CiLNode*)malloc(sizeof(CiLNode); Q-next=Q;/InitCiQ
24、ueue void EnCiQueue(CiQueue &Q,int x)/把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q-next指向头结点,Q-next-next指向队头元素 p=(CiLNode*)malloc(sizeof(CiLNode); p-data=x; p-next=Q-next; /直接把p加在Q的后面 Q-next=p; Q=p; /修改尾指针 Status DeCiQueue(CiQueue &Q,int x)/从循环链表表示的队列Q头部删除元素x if(Q=Q-next) return INFEASIBLE; /队列已空 p=Q-next-next; x=p-d
25、ata; Q-next-next=p-next; free(p); return OK;/DeCiQueue8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。提示： 初始状态：front=0, rear=0, tag=0 队空条件：front=rear, tag=0 队满条件：front=rear, tag=1 其它状态：front !=rear, tag=0（或1、2） 入队操作：（入队）if (front=rear) tag=1；（或直接tag=1）出队操作：（出队）tag
26、=0；问题：如何明确区分队空、队满、非空非满三种情况？9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S) int i, n, A255; n=0; while(!EmptyStack(S) n+; Pop(&S, &An); for(i=1; i=n; i+) Push(&S, Ai); 将栈S逆序。（2）void proc_2(Stack S, int e) Stack T; int d;InitStack(&T); while(!EmptyStack(S) Pop(&S, &d); if (d!=e) Push( &T, d); wh
27、ile(!EmptyStack(T) Pop(&T, &d); Push( &S, d); 删除栈S中所有等于e的元素。（3）void proc_3(Queue *Q) Stack S; int d;InitStack(&S); while(!EmptyQueue(*Q) DeleteQueue(Q, &d);Push( &S, d); while(!EmptyStack(S) Pop(&S, &d); EnterQueue(Q，d) 将队列Q逆序。第四章串1. 设s=I AM A STUDENT, t=GOOD, q=WORKER。给出下列操作的结果：StrLength(s); SubStr
28、ing(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,A,4); StrReplace(s,STUDENT,q); StrCat(StrCat(sub1,t), StrCat(sub2,q);参考答案StrLength(s)=14;SubString(sub1,s,1,7) sub1=I AM A ;SubString(sub2,s,7,1) sub2= ;StrIndex(s,4,A)=6;StrReplace(s,STUDENT,q); s=I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q) s
29、ub1=I AM A GOOD WORKER。2. 编写算法，实现串的基本操作StrReplace(S,T,V)。StrCat(S,T)； SubString(Sub,S,pos,len)。int String_Replace(Stringtype &S,Stringtype T,Stringtype V);/将串S中所有子串T替换为V,并返回置换次数 for(n=0,i=1;iT0) /找到了与T匹配的子串:分三种情况处理 if(T0=V0) for(l=1;l=T0;l+) /新子串长度与原子串相同时:直接替换 Si+l-1=Vl; else if(T0=i+T0;l-) Sl+V0-T0
30、=Sl; for(l=1;l=V0;l+) Si+l-1=Vl; else /新子串长度小于原子串时:先将后部左移 for(l=i+V0;l=S0+V0-T0;l+) Sl=Sl-V0+T0; for(l=1;lnext;p;p=p-next) r=(LStrNode*)malloc(sizeof(LStrNode); r-ch=p-ch; q-next=r;q=r; q-next=NULL;/StringAssign void StringCopy(LString &s,LString t)/把串t复制为串s.与前一个程序的区别在于,串s业已存在. for(p=s-next,q=t-next
31、;p&q;p=p-next,q=q-next) p-ch=q-ch;pre=p; while(q) p=(LStrNode*)malloc(sizeof(LStrNode); p-ch=q-ch; pre-next=p;pre=p; p-next=NULL;/StringCopy char StringCompare(LString s,LString t)/串的比较,st时返回正数,s=t时返回0,snext,q=t-next;p&q&p-ch=q-ch;p=p-next,q=q-next); if(!p&!q) return 0; else if(!p) return -(q-ch); e
32、lse if(!q) return p-ch; else return p-ch-q-ch;/StringCompare int StringLen(LString s)/求串s的长度(元素个数) for(i=0,p=s-next;p;p=p-next,i+); return i;/StringLen LString * Concat(LString s,LString t)/连接串s和串t形成新串,并返回指针 p=malloc(sizeof(LStrNode); for(q=p,r=s-next;r;r=r-next) q-next=(LStrNode*)malloc(sizeof(LStr
33、Node); q=q-next; q-ch=r-ch; /for /复制串s for(r=t-next;r;r=r-next) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /for /复制串t q-next=NULL; return p;/Concat LString * Sub_String(LString s,int start,int len)/返回一个串,其值等于串s从start位置起长为len的子串 p=malloc(sizeof(LStrNode);q=p; for(r=s;start;start-
34、,r=r-next); /找到start所对应的结点指针r for(i=1;inext) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /复制串t q-next=NULL; return p;/Sub_String4叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。char StrCompare(Stringtype s,Stringtype t)/串的比较,st时返回正数,s=t时返回0,st时返回负数 for(i=1;i=s0&is0&it0) return 0; e
35、lse if(is0) return -ti; else if(it0) return si; else return si-ti;/StrCompare5已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T.int HString_Replace(HString &S,HString T,HString V)/堆结构串上的置换操作,返回置换次数 for(n=0,i=0;i=S.length-T.length;i+) for(j=i,k=0;kT.length&S.chj=T.chk;j+,k+); if(k=T.length) /找到了与T匹配的子串:分三种情况处理 if(T.length=V.length) for(l=1;l=T.length;l+) /新子串长度与原子串相同时:直接替换 S.chi+l-1=V.chl-1; else if(T.lengthV.length) /新子串长度大于原子串时:先将后部右移 for(l=S.l
