算法与数据结构张乃孝 前三章习题课

1、首元结点、头结点、头指针的区别首元结点、头结点、头指针的区别习题选讲习题选讲栈与队列栈与队列树与二叉树树与二叉树首元结点、头结点、头指针的区别首元结点：首元结点：链表中存储线形表中第一个数据元素的结点头结点头结点：在链表首元结点之前附设一个结点。该结点的数据域不存储数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针：头指针：是指向链表中第一个结点（头结点或首元结点） 的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的头指针为空。 2.1 单项选择题单项选择题1. 一个向量（即一批地址连续的存储单元）第一个元素的存储

2、地址是100，每个元素的长度为2，则第5个元素的地址是_ _。 A. 110 B. 108 C. 100 D. 1202. 线性表的顺序存储结构是一种_ _的存储结构，而链式存储结构是一种_ _的存储结构。A随机存取 B索引存取 C顺序存取 D散列存取3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_ _。A. 正确 B. 不正确4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_ _。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续或不连续都可以BACBD5. 在以下的叙述中，正确的是_ _。线性表的顺序存储结构优于链表存储结构线性表的顺序存储结

3、构适用于频繁插入/删除数据元素的情况线性表的链表存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构优于顺序存储结构6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法_ _。A. 正确 B. 不正确7. 不带头结点的单链表head为空的判定条件是_。A. head= =NULL B. head-next= =NULLC. head-next= =head D. head!=NULL8. 带头结点的单链表head为空的判定条件是_。A. head= =NULL B. head-next= =NULLC. head-next= =head D. head!=NULLCAAB

4、9. 非空的循环单链表head的尾结点（由p所指向）满足_。A. p-next= =NULL B. p= =NULLC. p-next= =head D. p= =head 10. 在双向循环链表的p所指结点之后插入s所指结点的操作是_。A. p-right=s; s-left=p; p-right-left=s; s-right=p-right;B. p-right=s; p-right-left=s; s-left=p; s-right=p-right;C. s-left=p; s-right=p-right; p-right=s; p-right-left=s;D. s-left=p;

5、s-right=p-right; p-right-left=s; p-right=s;11. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;C. q-next=s; s-next=p; D. p-next=s; s-next=q;CDC12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A. s-next=p; p-next=s; B. s-next=p-next; p-next=s;C. s-next=p-n

6、ext; p=s; C. p-next=s; s-next=p;13. 在一个单链表中，若删除p所指结点的后续结点，则执行_。A. p-next= p-next-next； B. p= p-next; p-next= p-next-next；C. p-next= p-next; D. p= p-next-next；14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。A. n B. n/2 C. (n-1)/2 D. (n+1)/2 BAD15. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_ _。A. O(1) B. O(

7、n) C. O (n2) D. O (nlog2n)1. B 2. A, C 3. B 4. D 5. C 6. A 7. A 8. B 9. C 10. D 11.C 12.B 13.A 14.D 15.BB首元结点、头结点、头指针的区别首元结点：首元结点：链表中存储线形表中第一个数据元素的结点头结点头结点：在链表首元结点之前附设一个结点。该结点的数据域不存储数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针：头指针：是指向链表中第一个结点（头结点或首元结点） 的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的头

8、指针为空。 linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NULL;r=NULL; while(ch=getchar( )!= n) p=(listnode *)malloc(sizeof(listnode); pdata=ch; if(head=NULL) head=p; r=head; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); linklist createlistr1( ) char ch; linklist

9、 head=(linklist)malloc(sizeof(listnode); listnode *p，*r r=head; while(ch=getchar( )!= n p=(listnode*)malloc(sizeof(listnode); pdata=ch; rnext=p; r=p; rnext=NULL; return(head); 说明：第一个生成的结点是开始结点，将开始说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它置上插入，该位置上的插入操作和链表中其它位置上的

10、插入操作处理是不一样的，原因是开位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，始结点的位置是存放在头指针（指针变量）中， 而其余结点的位置是在其前趋结点的指针域中。而其余结点的位置是在其前趋结点的指针域中。算法中的第一个算法中的第一个if语句就是用来对第一个位置语句就是用来对第一个位置上的插入操作做特殊处理。上的插入操作做特殊处理。在上面的算法中，第一个结点的处理和其它结点是不在上面的算法中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针，接前驱

11、结点，它的地址就是整个链表的指针， 需要放需要放在链表的头指针变量中；而其它结点有直接前驱结点，在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。其地址放入直接前驱结点的指针域。如果我们在链表的开始结点之前附加一个结点，如果我们在链表的开始结点之前附加一个结点，并称它为并称它为头结点头结点，那么会带来以下两个优点：，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊和在表的其它位置上的操作一

12、致，无需进行特殊处理；处理；b b、无论链表是否为空，其头指针是指向头结点、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。因此空表和非空表的处理也就统一了。 求表长算法思路：设一个移动指针和计数器，初始化后，所指结点后面若还有结点，向后移动，计数器加1。(1)设L是带头结点的单链表(线性表的长度不包括头结点)。算法如下： int Length_LinkList1 (LinkList L) Lnode * p=L; /* p指向头结点*/ int j=0; while (p-next)

13、p=p-next; j+ /* p所指的是第 j 个结点*/ return j;加头没加尾加头没加尾(2)设L是不带头结点的单链表。算法如下：int Length_LinkList2 (LinkList L) Lnode * p=L; int j; if (p=NULL) return 0; /*空表的情况*/ j=1; /*在非空表的情况下，p所指的是第一个结点*/;while (p-next ) p=p-next; j+ return j;如果我们在链表的开始结点之前附加一个结点，如果我们在链表的开始结点之前附加一个结点，并称它为并称它为头结点头结点，那么会带来以下两个优点：，那么会带来以

14、下两个优点： a、由于开始结点的位置被存放在头结点的、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊和在表的其它位置上的操作一致，无需进行特殊处理；处理；b b、无论链表是否为空，其头指针是指向头结点、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。因此空表和非空表的处理也就统一了。2.21 void reverse(SqList &A)/顺序表的就地逆置 for(i

15、=1,j=A.length;ij;i+,j-) A.elemiA.elemj;/reverse 例例2.5 已知单链表H，写一算法将其倒置。 算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。算法如下： void reverse (Linklist H) LNode *p; p=H-next; /*p指向第一个数据结点*/ H-next=NULL; /*将原链表置为空表H*/ while (p) q=p; p=p-next; q-next=H-next; /*将当前结点插到头结点的后面*/ H-next=q; 该算法只是对链表中顺序扫

16、描一边即完成了倒置，所以时间性能为O(n)。2.22 void LinkList_reverse(Linklist &L)/链表的就地逆置;为简化算法,假设表长大于2Rev(linklist L) /带头结点的单链表Pnode p,q,r; p=L-link;if(p=NULL) return; q=p-link; if(q=NULL) return; r=q-link; while(r!=NULL) q-link=p; p=q; q=r; r=r-link; q-link=p; L-link-link=NULL; L-link=q;已知线性表已知线性表A的长度为的长度为n，并且采用顺

17、序存储结构，写一，并且采用顺序存储结构，写一算法删除线性表中所有值为算法删除线性表中所有值为X的元素的元素Del (sqlist L,datatype x)int I,j; for(I=0;in;I+) if(L-datai=x) for(j=I;jn;j+) L-dataj=L-dataj+1; L-n-; L 指向无头结点的线性链表，写出删除链表中从下标为指向无头结点的线性链表，写出删除链表中从下标为I的结的结点开始的连续点开始的连续k个结点的算法个结点的算法Linklist Del (linklist L,int I,int k)pnode p,q; int j=0; p=L; whil

18、e(p-link!=NULL&jlink;j+ for(j=1;jlink; p-link=q-link; free(q); Return(L);删除单链表中值相同的多余结点删除单链表中值相同的多余结点Diff_link(Linklist llist)pnode p,q,r; p=llist-link; while( p!=NULL) q=p; r=q-link; while(r!=NULL) if(r-info=p-info) t=r-link; q-link=t; free(r); r=t; else q=r;r=r-link; P=p-link归并两个单链表为一个单链表归并两个单

19、链表为一个单链表Linklist combine(linklist x,linklist y)linklist llist=(linklist)malloc(sizeof(struct Node);Pnode p=llist,px=x-link,py=y-link;While(px!=NULL|py!=NULL) if(px!=NULL) p-link=(linklist)malloc(sizeof(struct Node); p=p-link; P-info=px-info; px=px-link; if(py!=NULL)p-link=(linklist)malloc(sizeof(str

20、uct Node); p=p-link; P-info=px-info; py=py-link;P-link=NULL;Return(llist);12、归并两个线性表void merge1(LinkList &A,LinkList &B,LinkList &C)/把链把链表表A和和B合并为合并为C,A和和B的元素间隔排列的元素间隔排列,且使用原存储空间且使用原存储空间 p=A-next;q=B-next;C=A; while(p&q) s=p-next;p-next=q; /将将B的元素插入的元素插入 t=q-next;q-next=s; /如如A非空非空,将

21、将A的元素插入的元素插入 p=s;q=t; /while/merge1 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList hc)/把链表把链表hb接在接在ha后面形成链表后面形成链表hc hc=ha;p=ha; while(p-next) p=p-next; p-next=hb; return(hc);/ListConcat 2.19 Status Delete_Between(Linklist L,int mink,int maxk)/删除元素删除元素递增排列的链表递增排列的链表L中值大于中值大于mink且小于且小于maxk的所有元素

22、的所有元素 p=L; while(p-next-datanext; /p是最后一个是最后一个 不大于不大于mink的元素的元素 if(p-next) /如果还有比如果还有比mink更大的元素更大的元素 q=p-next; while(q-datanext; /q是第一个不小于是第一个不小于maxk的元素的元素 p-next=q; /Delete_Between 2.31 Status Delete_Pre(listnode *s)/删除单循环链表中结删除单循环链表中结点点s的直接前驱的直接前驱 p=s; while(p-next-next!=s) p=p-next; /找到找到s的前驱的的前驱

23、的前驱前驱p p-next=s; return OK;/Delete_Pre Linklist combine(Linklist list1,Linklist list2)Linklist list3=(Linklist)malloc(sizeof(struct Node); Pnode p1=list1-link,p2=list2-link,p3=list3; if(p1=list1&p2=list2) list3-link=list3; return list; while(p1!=list1|p2!=list2) p3-link=(Pnode)malloc(sizeof(stru

24、ct Node); p3=p3-link; if(p2=list2|(p1!=list1&p1-infoinfo) p3-info=p1-info; p1=p1-link; else p3-info=p2-info; p2=p2-link; p3-link=list3; return list3;2.32 P指向双向链表的中间结点，写出完成下列功能的语句。指向双向链表的中间结点，写出完成下列功能的语句。（1）在）在p结点后插入指针结点后插入指针S所指向的结点。所指向的结点。（2）删除）删除P所指结点的前驱结点。所指结点的前驱结点。（3）删除）删除P结点。结点。(1) s-pre=p;

25、s-next=p-next; p-next-pre=s; p-next=s;(2) q=p-pre; p-pre=q-pre; q-pre-next=p; free(q);(3) p-pre-next=p-next; p-next-pre=p-pre; free(p);解决计算机与打印机之间速度不匹配的问题，需要解决计算机与打印机之间速度不匹配的问题，需要设置一个数据缓冲区，应是一个什么结构。设置一个数据缓冲区，应是一个什么结构。判断一个队列Q（元素最多为n)为空的条件是：Q-rear=Q-front判断一个队列Q（元素最多为n)为满的条件是：Q-rear-Q-front=n判断一个循环队列Q

26、（元素最多为n)为空的条件是：判断一个循环队列Q（元素最多为n)为满的条件是：Q-rear=Q-frontQ-front=Q-rear+1)%n设有两个栈都采用顺序存储表示，并且共有一个存储区，设有两个栈都采用顺序存储表示，并且共有一个存储区，现采用栈顶相对，迎面增长的方式存储，写出对两个站进现采用栈顶相对，迎面增长的方式存储，写出对两个站进行插入删除的操作。行插入删除的操作。分析：两个栈的栈底分别设在数组的两个断点，用两个指针指示两个栈的栈顶，两个栈迎面增长，当两个栈定相遇时发生溢出。#define maxsize 100Typedef struct tstackdatatype datam

27、axsize;Int top1,top2;Int stacksize;tstack;(1)初始化算法：State initstack(tstack *ts)ts=(tstack*)malloc(sizeof(sturct tstack); if(ts=NULL) printf(“out of spacen”);Ts-stacksize=maxsize;Ts-top1=-1;Ts-top2=maxsize;Return OK;入栈算法：Push(tstack *ts,int I,datatype x)if(top1=top2）return(overflow);If(I=0)top1+; ts-d

28、atats-top1=x; Elsetop2-; ts-datats-top2=x; Retrun ok;出栈算法：出栈算法：Pop(tstack *ts,int I,datatype x)if(I=0) if(top1=-1) return error;X=ts-datats-top1;Top1-;elseif(top2=maxsize) return error;X=ts-datats-top2;Top2+;Return x;3.17 int IsReverse()/判断输入的字符串中判断输入的字符串中&前和前和&后部分是否为逆串后部分是否为逆串,是则返回是则返回1,否则返

29、回否则返回0 InitStack(s); while(e=getchar()!=&) if(e=) return 0;/不允许在不允许在&之前出现之前出现 push(s,e); while( (e=getchar()!=) if(StackEmpty(s) return 0; pop(s,c); if(e!=c) return 0; if(!StackEmpty(s) return 0; return 1;/IsReverse abcde&edcba3.31 int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0 InitSta

30、ck(S);InitQueue(Q); while(c=getchar()!=) Push(S,c);EnQueue(Q,c); /同时使用栈和队列两种结构 while(!StackEmpty(S) Pop(S,a);DeQueue(Q,b); if(a!=b) return 0; return 1; /Palindrome_Test abcba递归算法为：long Fib(intlong Fib(int n) n)if(n=1|n=2) /if(n=1|n=2) /终止递归条件终止递归条件 return 1;return 1; else else return Fib(n-1)+Fib(n-

31、2); return Fib(n-1)+Fib(n-2); 非递归算法为 long Fib1(int n) int a,b,c;/C代表当前项，a和b分别代表当前项前面的第2项和第1项 a=b=1; /给a和b赋初值1 if(n=1|n=2) return 1; else for(int i=3;i3)转化为递归函数，其递归出口是 ，递归体是 。F(1)=1F(n)=f(n-1)+1/n有如下递归算法：Void print(int w) int I; if(w!=0) print(w-1); for(I=1;Inext)Int count(listnode h)if (h=null) retu

32、rn 0; else return(1+count(h-next); 2、正向显示以h为头指针的单链表的所有节点值递归模型：Traverse(h) h=null 不做任何事Traverse(h)=输出*h结点之值；traverse(h-next) 其他情况Void traverse （listnode h)if(h=null) return; printf(“%d”,h-data); traverse(h-next);3、反向显示以h为头指针的单链表的所有结点值Void revtraverse(listnode h)if(h=null) return; revtraverse(h-next);

33、 printf(“%d”,h-data); 4、删除以h为头指针的单链表中值为x的第一个结点Int delnode(listnode h,int x)listnode p; if(h=null) return 0; if(h-data=x) p=h; h=h-next; free(p); return(1); else delnode(h-next,x);2.11设顺序表va中的数据元素递增有序，试写一算法将X插入顺序表的适当位置，该表有序。Void insert(vector a,int n,int x) int I,j; if(xan) an+1=x; else I=1; while(x=

34、aI) I+; for(j=n;j=I;j-) aj+1=aj; aI=x;n+;比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。 A和B分别为 A 和 B 中除去最大共同前缀后的子表。例如A=(x,y,y,z,x,z)， B=(x,y,y,z,y,x,x,z)，两表最大共同前缀为 (x,y,y,z) 。则 A=（x,z）， B=（y,x,x,z），若A=B= 空表，则A=B；若A=空表且B空表，或两者均不空且A首元素小于B首元素，则AB。 算法思路：首先找出A、B的最大共同前缀；然后求出A和B，之后在按比较规则进行比较，AB 函数返回

35、1；A=B返回0；AB返回-1。算法如下：int compare( A,B,m,n)int A,B;int m,n; int i=0,j,AS,BS,ms=0,ns=0; /*AS,BS作为A,B*/ while (Ai=Bi) i+; /*找最大共同前缀*/ for (j=i;jm;j+) ASj-i=Aj;ms+; /*求A,ms为A的长度*/ for (j=i;j0 | ms0 & ns0 & AS0data=p-data;r-next=s;r=s;p=p-next;If(q!=NULL)s=(node*)malloc(sizeof(node);s-data=q-data

36、;r-next=s;r=s;q=q-next;r-next=NULL;return(z);int GetValue_NiBoLan(char *str)/对逆波兰式求值 p=str; InitStack(s); /s为操作数栈 while(*p) if(*p是数) push(s,*p); else pop(s,a);pop(s,b); r=compute(b,*p,a); /假设compute为执行双目运算的过程 push(s,r); /else p+; /while pop(s,r);return r;/GetValue_NiBoLan Compute(int b,char c,int a)

37、float d; switch(c) case +:d=b+a; break; case -:d=b-a; break; case*:d=b*a; break; case /: d=b/a; break; 试找出分别满足下面条件的所有二叉树：试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同；）前序序列和中序序列相同； （2）中序序列和后序）中序序列和后序序列相同；序列相同；（3）前序序列和后序序列相同；）前序序列和后序序列相同； （4）前序、中序、后）前序、中序、后序序列均相同。序序列均相同。解：解：（1） 空二叉树或任一结点均无左子树的非空二叉树空二叉树或任一结点均无左子树的

38、非空二叉树（2） 空二叉树或任一结点均无右子树的非空二叉树空二叉树或任一结点均无右子树的非空二叉树（3） 空二叉树或仅有一个结点的二叉树空二叉树或仅有一个结点的二叉树（4） 同（同（3） AEBCDFHIGJABECDHIGJF ABFGCEDHIJABECDFGJHI例例3：一棵二叉树的层序序列为：一棵二叉树的层序序列为ABCDEFGHIJ,中序列为中序列为DBGEHJACIF,求这棵二叉树求这棵二叉树ACBDEFGHJI例例4、已知一棵树的先根遍历序列、已知一棵树的先根遍历序列GFKDAIEBCHJ,后根后根遍历序列为遍历序列为DIAEKFCJHBG,求对应的树。求对应的树。树的先根对应二

39、叉树的先序，树的后根对应二叉树的中树的先根对应二叉树的先序，树的后根对应二叉树的中序遍历序遍历例5、若n个节点k条边的无向图是一个森林，(nk),则该森林中有多少棵树？解：设森林中有m棵树，每棵树的顶点数为.例6、深度为5的二叉树至多有结点数为多少？（深度从1开始计数）A 16 B 30 C 31 D 32例7、高度为h的二叉树上只有度为0和2的结点，则此类二叉树中所包含的结点数至少为多少？（从1开始计数）A 2h B 2h-1 C 2h+1 D h+1M=n-k int LeafCount(Bitree T)/求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 els

40、e if(!T-lchild&!T-rchild) return 1; /叶子结点 else return LeafCount(T-lchild)+LeafCount(T-rchild);/左子树的叶子数加上右子树的叶子数/LeafCount_BiTree Int leafnum=0;Void countleaf(bintree t)if(t=null) return 0;If(t-lchild=null &t-rchild=null)leafnum+;Elsecountleaf(t-lchild); countleaf(t-rchild);void Bitree_Revolu

41、te(Bitree T)/交换所有结点的左右子树 T-lchildT-rchild; /交换左右子树 if(T-lchild) Bitree_Revolute(T-lchild); if(T-rchild) Bitree_Revolute(T-rchild); /左右子树再分别交换各自的左右子树/Bitree_Revolute 证明：如果给了一棵二叉树结点的先根次序和对称次序则此二叉树即可构造出来。如果给了先根和后根次序行吗？举出不行的例子。证明(1)由先根次序可以确定二叉树的根R(2)已知D后，通过对陈次序可以确定D的两棵子树L和R(3)LR确定后，又可以根据先根和中根确定LR的两个根依次类推直到L和R的结点数为1先根和后根不能确定举反例先根：abcd后根：dcba例11：void PreOrder_Nonrecursive(Bitree T)/先序遍历二叉树的非递归算法 InitStack(S); Push(S,T); /根指针进栈 while(!StackEmpty(S) while(Gettop(S,p)&p) visit(