部分习题参考答案(数据结构)PPT参考幻灯片.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,练习题,2,习题,2.2,、,2.3,、,2.4,、,2.5,和,2.6,。,2.2,设计一个算法，将,x,插入到一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。,void Insert(SqList*&L,ElemType x),int i=0,j;,while(ilength,for(j=L-length-1;j=i;j-),L-dataj+1=L-dataj;,L-datai=x;,L-length+;,1,2.3,设计一个算法，将一个带头结点的数据域依次为,a,1a,2,，,，,a,n,（,n3,）的单链表的所有结点逆置，即第一个结点的数据域变为,a,n,，,，最后一个结点的数据域为,a,1,。,void Reverse(LinkList*&L),LinkList*p=L-next,*q;,L-next=NULL;,while(p!=NULL)/,扫描所有的结点,q=p-next;/,让,q,指向*,p,结点的下一个结点,p-next=L-next;/,总是将*,p,结点作为第一个数据结点,L-next=p;,p=q;/,让,p,指向下一个结点,2,2.4,设有一个双链表，每个结点中除有,prior,、,data,和,next,三个域外，还有一个访问频度域,freq,，在链表被起用之前，其值均初始化为零。每当进行,LocateNode(h,，,x),运算时，令元素值为,x,的结点中,freq,域的值加,1,，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的,LocateNode,运算的算法。,3,bool LocateNode(DLinkList*h,ElemType x),DLinkList*p=h-next,*q;,while(p!=NULL&p-data!=x),p=p-next;/,找,data,域值为,x,的节点*,p,if(p=NULL)/,未找到的情况,return false;,else/,找到的情况,p-freq+;/,频度增,1,q=p-prior;/*q,为,p,前驱节点,while(q!=h&q-freqfreq),p-prior=q-prior;p-prior-next=p;/,交换*,p,和*,q,的位置,q-next=p-next;,if(q-next!=NULL)/*p,不为最后一个节点时,q-next-prior=q;,p-next=q;q-prior=p;,q=p-prior;/q,重指向*,p,的前趋节点,return true;,4,2.5,设,ha=(a,1,a,2,a,n,),和,hb=(b,1,b,2,b,m,),是两个带头结点的循环单链表，编写将这两个表合并为带头结点的循环单链表,hc,的算法。,void Merge(LinkList*ha,LinkList*hb,LinkList*&hc),LinkList*p=ha-next;,hc=ha;,while(p-next!=ha)/,找到,ha,的最后一个节点*,p,p=p-next;,p-next=hb-next;/,将,ha,的最后一个节点的,next,指向,hb,的第一个数据节点,while(p-next!=hb)p=p-next;/,找到,hb,的最后一个节点*,p,p-next=hc;/,构成循环单链表,free(hb),；,/,释放,hb,单链表的头节点,5,2.6,设非空线性表,ha,和,hb,都用带头节点的循环双链表表示。设计一个算法,Insert(ha,hb,i),。其功能是：,i=0,时，将线性表,hb,插入到线性表,ha,的最前面；当,i0,时，将线性表,hb,插入到线性表,ha,中第,i,个节点的后面；当,i,大于等于线性表,ha,的长度时，将线性表,hb,插入到线性表,ha,的最后面。,void Insert(DLinkList*&ha,DLinkList*&hb,int i),DLinkList*p=ha-next,*q;,int lena=1,j=0;,while(p-next!=ha)/,求出,ha,的长度,lenalena+;,p=p-next;,6,if(i=0)/,将,hb,的所有数据结点插入到,ha,的头结点和第,1,个数据结点之间,p=hb-prior;/p,指向,hb,的最后一个结点,/,p-next=ha-next;/,将*,p,链到,ha,的第,1,个数据结点前面,ha-next-prior=p;,ha-next=hb-next;,hb-next-prior=ha;/,将,ha,头结点与,hb,的第,1,个数据结点链起来,else if(inext;,while(jnext;,j+;,q=p-next;/q,指向*,p,结点的后继结点,/,p-next=hb-next;/hb-prior指向,hb,的最后一个结点,hb-next-prior=p;,hb-prior-next=q;,q-prior=hb-prior;,7,else/,将,hb,链到,ha,之后,ha-prior-next=hb-next;/ha-prior,指向,ha,的最后一个结点,hb-next-prior=ha-prior;,hb-prior-next=ha;,ha-prior=hb-prior;,free(hb);/,释放,hb,头结点,8,练习题,3,习题,3.1,、,3.2,、,3.3,、,3.4,和,3.6,。,3.1,有,5,个元素，其进栈次序为：,A,、,B,、,C,、,D,、,E,，在各种可能的出栈次序中，以元素,C,、,D,最先出栈（即,C,第一个且,D,第二个出栈）的次序有哪几个？,答：,要使,C,第一个且,D,第二个出栈，应是,A,进栈，,B,进栈，,C,进栈，,C,出栈，,D,进栈，,D,出栈，之后可以有以下几种情况：,（,1,）,B,出栈，,A,出栈，,E,进栈，,E,出栈，输出序列为,CDBAE,；,（,2,）,B,出栈，,E,进栈，,E,出栈，,A,出栈，输出序列为,CDBEA,；,（,3,）,E,进栈，,E,出栈，,B,出栈，,A,出栈，输出序列为,CDEBA,。,所以可能的次序有：,CDBAE,、,CDBEA,、,CDEBA,。,9,3.2,假设以,I,和,O分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由,I,和,O,组成的序列。,（,1,）下面所示的序列中哪些是合法的？,A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO,（,2,）通过对（,1,）的分析，写出一个算法判定所给的操作序列是否合法。若合法返回,1,；否则返回,0,。（假设被判定的操作序列已存入一维数组中）。,解：,（,1,）,A,、,D,均合法，而,B,、,C,不合法。因为在,B,中，先进栈一次，立即出栈三次，这会造成栈下溢。在,C,中共进栈五次，出栈三次，栈的终态不为空。,10,（,2,）本题使用一个链栈来判断操作序列是否合法，其中,A,为存放操作序列的字符数组，,n,为该数组的元素个数（这里的,ElemType,类型设定为,char,）。对应的算法如下：,int judge(char A,int n),int i;,ElemType x;,LiStack*ls;,InitStack(ls);,for(i=0;i0,时，,a,i,进队，当,a,i,rear=qu-front=0;,while(1),printf(,输入,a,值,:);scanf(%d,if(a0),if(qu-rear+1)%QueueSize=qu-front),printf(,队列满,不能入队,n);,else,qu-rear=(qu-rear+1)%QueueSize;/,入队,qu-dataqu-rear=a;,else if(arear=qu-front),printf(,队列空,不能出队,n);,else,qu-front=(qu-front+1)%QueueSize;/,出队,x=qu-dataqu-front;,printf(,出队元素,:%dn,x);,else break;,14,3.6,输入,n,（由用户输入）个,10,以内的数，每输入,i,（,0i9,），就把它插入到第,i,号队列中。最后把,10,个队中非空队列，按队列号从小到大的顺序串接成一条链，并输出该链的所有元素。,typedef struct node,int data;,struct node*next;,QNode;,15,void Insert(QNode*QH,QNode*QT,int x)/,将,x,插入到相应队列中,QNode*s;,s=(QNode*)malloc(sizeof(QNode);/,创建一个节点,s-data=x;s-next=NULL;,if(QHx=NULL)/,对应的队列为空队时,QHx=s;,QTx=s;,else,QTx-next=s;/,将*,s,节点链到,QTx,所指节点之后,QTx=s;/,让,QTx,仍指向尾节点,16,void Create(QNode*QH,QNode*QT)/,根据用户输入创建队列,int n,x,i;,printf(n:);,scanf(%d,for(i=0;in;i+),do,printf(,输入第,%d,个数,:,i+1);,scanf(%d,while(x10);,Insert(QH,QT,x);,17,void Link(QNode*QH,QNode*QT)/,将非空队列链接起来并输出,QNode*head,*tail;/,总链表的首节点指针和尾节点指针,int first=1,i;,for(i=0;inext=QHi;,tail=QTi;,printf(n,输出所有元素,:);,while(head!=NULL),printf(%d,head-data);,head=head-next;,printf(n);,18,void main(),int i;,QNode*QHMAXQNode,*QTMAXQNode;,/,各队列的队头,QH,和队尾指针,QT,for(i=0;iMAXQNode;i+),QHi=QTi=NULL;/,置初值,Create(QH,QT);/,建立队列,Link(QH,QT);/,链接各队列并输出,19,练习题,4,习题,4.1,、,4.2,和,4.3,。,4.1,采用顺序结构存储串，编写一个实现串通配符匹配的算法,pattern_index(),，其中的通配符只有,?,，它可以和任一字符匹配成功，例如，pattern_index(?re,，,there are),返回的结果是,2,。,int Pattern_Index(SqString substr,SqString str),int i,j,k;,for(i=0;istr.length;i+),for(j=i,k=0;jstr.length&k=substr.length),return(i);,return(-1);,20,4.2,有两个串,s1,和,s2,，设计一个算法求一个这样的串，该串中的字符是,s1,和,s2,中公共字符（不是子串关系）。,SqString CommChar(SqString s1,SqString s2),SqString s3;,int i,j,k=0;,for(i=0;is1.length;i+),for(j=0;js2.length;j+),if(s2.dataj=s1.datai),break;,if(jtag=0&g2-tag=0)/,均为原子的情况,if(g1-val.data!=g2-val.data)return false;,return(,Same(,g1-link,g2-link);,else if(g1-tag=1&g2-tag=1)/,均为子表的情况,return(,Same,(g1-val.sublist,g2-val.sublist),&,Same,(g1-link,g2-link);,else/,一个为原子,另一为子表的情况,return false;,29,练习题,7,7.1,、,7.2,、,7.3,、,7.4,、,7.5,、,7.7,、,7.9,7.1,设二叉树,bt,的一种存储结构如表,7.1,所示。其中，,bt,为树根节点指针，,lchild,、,rchild,分别为节点的左、右孩子指针域，在这里使用节点编号作为指针域值，,0,表示指针域值为空；,data,为节点的数据域。请完成下列各题：,（,1,）画出二叉树,bt,的树形表示；,（,2,）写出按先序、中序和后序遍历二叉树,bt,所得到的节点序列；,（,3,）画出二叉树,bt,的后序线索树。,表7.1,二叉树,bt,的一种存储结构,1,2,3,4,5,6,7,8,9,10,lchild,0,0,2,3,7,5,8,0,10,1,data,j,h,f,d,b,a,c,e,g,i,rchild,0,0,0,9,4,0,0,0,0,0,30,答：,（,1,）二叉树,bt,的树形表示如图,7.1,所示。,图,7.1,二叉树,bt,的逻辑结构,图,7.2,二叉树,bt,的后序线索化树,（,2,）先序遍历序列：,abcedfhgij,中序遍历序列：,ecbhfdjiga,后序遍历序列：,echfjigdba,（,3,）二叉树,bt,的后序遍历序列为,echfjigdba,，则后序线索树如图,72,所示。,31,7.2,已知一棵二叉树的中序序列为,cbedahgijf,，后序序列为,cedbhjigfa,，给出该二叉树树形表示。,32,7.3,设给定权集合,W=2,3,4,7,8,9,，试构造关于,W,的一棵哈夫曼树，并求其带权路径长度,WPL,。,答：由权值集合,W,极选的哈夫曼树如图,7.4,所示。其带权路径长度,WPL=(9+7+8)2+43+(2+3)4=80,。,33,7.4,一棵具有,n,个节点的完全二叉树以顺序方式存储在数组,A,中，假设每个节点的元素为单个字符，没有对应节点时,A,中元素取值为,#,。设计一个算法构造该二叉树的二叉链存储结构。,void Ctree(BTNode*&b,char A,int i),/,由二叉树的顺序存储结构,A,建立二叉链存储结构，二叉链的根节点由,b,指向,if(i=MaxSize|Ai=#)/,若,i,无效或,Ai,为无效节点,b=NULL;,else,b=(BTNode*)malloc(sizeof(BTNode);,b-data=Ai-1;,Ctree(b-lchild,A,2*i);/,递归构造*,b,的左子树,Ctree(b-rchild,A,2*i+1);/,递归构造*,b,的右子树,34,7.5,假设二叉树中每个节点的值为单个字符，设计一个算法将一棵以二叉链方式存储的二叉树,b,转换成对应的顺序存储结构,Avoid Ctree(BTNode*b,SqBTree A,int i),if(b!=NULL),Ai=b-data;,Ctree(b-lchild,A,2*i);,Ctree(b-rchild,A,2*i+1);,else,Ai=#;,35,7.7,假设二叉树采用二叉链存储结构，,t,指向根节点，,p,所指节点为任一给定的节点，设计一个算法，输出从根节点到,p,所指节点之间路径。,int Path(BTNode*t,BTNode*s),BTNode*StMaxSize;,BTNode*p;,int i,flag,top=-1;/,栈顶指针置初值,do,while(t)/,将,t,的所有左节点进栈,top+;,Sttop=t;,t=t-lchild;,p=NULL;/p,指向当前节点的前一个已访问的节点,flag=1;/,设置,t,的访问标记为已访问过,36,while(top!=-1&flag),t=Sttop;/,取出当前的栈顶元素,if(t-rchild=p)/,右子树不存在或已被访问,访问之,if(t=s)/,当前访问的节点为要找的节点,输出路径,for(i=0;idata);,return 1;,else,top-;,p=t;/p,指向则被访问的结,else,t=t-rchild;/t,指向右子树,flag=0;/,设置未被访问的标记,while(top!=-1);/,栈不空时循环,return 0;/,其他情况时返回,0,37,7.9,假设二叉树采用二叉链存储结构，设计一个算法判断一棵二叉树是否是对称同构。所谓对称同构是指其左右子树的结构是对称的。,解：,判断二叉树是否对称同构的递归模型如下：,f(b)=true,若,b=NULL,或,b-lchild,与,b-rchild,均为,NULL,f(b)=false,若,b-lchild,与,b-rchild,中之一为,NULL,f(b)=f(b-lchild)&f(b-rchild),其他情况,38,bool Symm(BTNode*t1,BTNode*t2)/,判断二叉树,t1,和,t2,是否对称,ift1=NULL&t2=NULL),return true;,else if(t1=NULL|t2=NULL),return false;,else,return(symm(t1-lchild,t2-lchild)&,symm(t1-rchild,t2-rchild);,bool Symmtree(BTNode*b)/,判断二叉树,b,是否对称,if(b=NULL),return true;,else,return Symm(b-lchild,b-rchild);,39,练习题,8,习题,8.2,、,8.3,、,8.5,、,8.,6,。,8.2,对于如图,8.2,所示的带权无向图，给出利用普里姆算法（从顶点,0,开始构造）和克鲁斯卡尔算法构造出的最小生成树的结果。,答：,利用普里姆算法从顶点,0,出发构造的最小生成树为：,(0,1),(0,3),(1,2),(2,5),(5,4),。利用克鲁斯卡尔算法构造出的最小生成树为：,(0,1),(0,3),(1,2),(5,4),(2,5),。,40,8.3,对于如图,8.3,所示的带权有向图，采用狄克斯特拉算法求出从顶点,0,到其他各顶点的最短路径及其长度。,答：,采用狄克斯特拉算法求出从顶点,0,到其他各顶点的最短路径及其长度如下：,从,0,到,1,的最短路径长度为,:1,，路径为,:0,1,从,0,到,2,的最短路径长度为,:4,，路径为,:0,1,2,从,0,到,3,的最短路径长度为,:2,，路径为,:0,3,从,0,到,4,的最短路径长度为,:8,，路径为,:0,1,4,从,0,到,5,的最短路径长度为,:10,，路径为,:0,3,5,41,8.5,假设图,G,采用邻接表存储，编写一个算法输出邻接表。,解：直接利用邻接表的结构来输出图,G,的邻接表表示。对应的算法如下：,void DispAdj(ALGraph*G)/,输出邻接表,G,int i;,ArcNode*p;,printf(,邻接表,:n);,for(i=0;in;i+),p=G-adjlisti.firstarc;,printf(%2d:,i);,while(p!=NULL),printf(%2d,p-adjvex);,p=p-nextarc;,printf(n);,42,8.6,假设图,G,采用邻接表存储，分别设计实现以下要求的算法：,（,1,）求出图,G,中每个顶点的出度；,（,2,）求出图,G,中出度最大的一个顶点，输出该顶点编号；,（,3,）计算图,G,中出度为,0,的顶点数；,（,4,）判断图,G,中是否存在边,。,解：,对应（,1,）、（,2,）、（,3,）和（,4,）的功能的函数分别是,OutDs(),、,MaxOutDs(),、,ZeroDs(),和,Arc(),。,43,int OutDegree(ALGraph*G,int v),ArcNode*p;,int n=0;,p=G-adjlistv.firstarc;,while(p!=NULL),n+;,p=p-nextarc;,return n;,void OutDs(ALGraph*G)/,求出图,G,中每个顶点的出度,int i;,printf(1),各顶点出度,:n);,for(i=0;in;i+),printf(,顶点,%d:%dn,i,OutDegree(G,i);,44,void MaxOutDs(ALGraph*G)/,求出图,G,中出度最大的一个顶点,int maxv=0,maxds=0,i,x;,for(i=0;in;i+),x=OutDegree(G,i);,if(xmaxds),maxds=x;,maxv=i;,printf(2),最大出度,:,顶点,%d,的出度,=%dn,maxv,maxds);,45,void ZeroDs(ALGraph*G)/,计算图,G,中出度为,0,的顶点数,int i,x;,printf(3),出度为,0,的顶点,:);,for(i=0;in;i+),x=OutDegree(G,i);,if(x=0),printf(%2d,i);,printf(n);,46,void Arc(ALGraph*G)/,判断图,G,中是否存在边,int i,j;,ArcNode*p;,printf(4),输入边,:);scanf(%d%d,p=G-adjlisti.firstarc;,while(p!=NULL&p-adjvex!=j),p=p-nextarc;,if(p=NULL),printf(,不存在,);,else,printf(,存在,);,printf(,边,n,i,j);,47,练习,9,教材中,p271,习题,1,、,2,、,3,和,5,。,9.1,对于,A0.10,有序表，采用二分查找法时，求成功和不成功时的平均查找长度。并对于有序表,12,18,24,35,47,50,62,83,90,115,134,，当用二分查找法查找,90,时，需进行多少次查找可确定成功；查找,47,时需进行多少次查找可确定成功；查找,100,时，需进行多少次查找才能确定不成功。,48,答：,对于,A0.10,有序表构造的判定树如图,9.1(a),所示。因此有：,ASL,succ,=3,ASL,unsucc,=3.67,49,9.2,将整数序列,4,5,7,2,1,3,6,中的数依次插入到一棵空的二叉排序树中，试构造相应的二叉排序树，要求用图形给出构造过程，不需编写程序。,50,9.3,将整数序列,4,5,7,2,1,3,6,依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树，要求用图形给出构造过程，不需编写程序。,51,52,9.5,编写一个算法，判断给定的二叉树是否是二叉排序树。,KeyType predt=-32768;,/predt,为全局变量,保存当前节点中序前趋的值,初值为,-,bool JudgeBST(BSTNode*bt),bool b1,b2;,if(bt=NULL),return true;,else,b1=JudgeBST(bt-lchild);/,判断左子树,if(!b1|predt=bt-key)/,判断根节点,return false;,predt=bt-key;,b2=JudgeBST(bt-rchild);/,判断右子树,return b2;,53,练习题,10,10.2,、,10.4,和,10.6,10.2,如果只想在一个有,n,个元素的任意序列中得到其中最小的第,k,（,kn,）个元素之前的部分排序序列，那么最好采用什么排序方法？为什么？例如有这样一个序列：,57,40,38,11,13,34,48,75,6,19,9,7,，要得到其第,4,个元素之前的部分有序序列，用所选择的算法实现时，要执行多少次比较？,54,答：,采用堆排序最合适，建立初始堆（小根堆）所花时间不超过,4n,，每次选出一个最小元素所花时间为,log,2,n,，因此得到第,k,个最小元素之前的部分序列所花时间大约为,4n+klog,2,n,，而冒泡排序和简单选择排序所花时间为,kn,。,对于序列,57,40,38,11,13,34,48,75,6,19,9,7,，形成初始堆（小根堆）并选最小数据,6,，需进行,18,次数据比较；选次小数据,7,时，需进行,5,次数据比较；再选数据,9,时，需进行,6,次数据比较；选数据,11,时，需进行,4,次数据比较，总共需进行,33,次关键字比较。整个过程如图,10.1,所示。,55,56,10.4,给定,n,个记录的有序表,A0.n-1,和,m,个记录的有序表,B0.m-1,，将它们归并为一个有序表，存放到,C0.m+n-1,中，试写出这一算法。,void Merge(RecType A,int n,RecType B,int m,RecType C),int i,j,k=0;,while(in&jm),if(AiBj),Ck=Bj;,k+;j+;,else/Ai=Bj,Ck=Ai;,k+;i+;,Ck=Bj;,k+;j+;,57,while(in),Ck=Ai;,k+;i+;,while(jm),Ck=Bj;,k+;j+;,58,10.6,设,n,个记录,R0.n-1,的关键字只取三个值：,0,，,1,，,2,。编写一个时间复杂度为,O(n),的算法将这,n,个记录排序。,解：,采用基数排序法，将关键字为三个值的记录分别放到,3,个队列中，然后收集起来即可。,59,