- 1.49 MB
- 2022-04-22 11:36:41 发布
- 1、本文档共5页，可阅读全部内容。
- 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
- 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
- 文档侵权举报电话：19940600175。
'第2章线性表2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}elseif(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}else{//相等时取La的元素，删除Lb的元素pc->next=pa;pc=pa;pa=pa->next;q=pb->next;deletepb;pb=q;}}pc->next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb的头结点}（2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。voidunion(LinkList&La,LinkList&Lb,LinkList&Lc,){pa=La->next;pb=Lb->next;//初始化Lc=pc=La;//用La的头结点作为Lc的头结点Lc->next=NULL;while(pa||pb){if(!pa){q=pb;pb=pb->next;}elseif(!pb){q=pa;pa=pa->next;}elseif(pa->data<=pb->data){q=pa;pa=pa->next;}else{q=pb;pb=pb->next;}q->next=Lc->next;Lc->next=q;//插入}deleteLb;//释放Lb的头结点}（3）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。voidMix(LinkList&La,LinkList&Lb,LinkList&Lc,){pa=la->next;pb=lb->next;∥设工作指针pa和pb；Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb)if(pa->data==pb->data)∥交集并入结果表中。{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;deleteu;}
elseif(pa->datadata){u=pa;pa=pa->next;deleteu;}else{u=pb;pb=pb->next;deleteu;}while(pa){u=pa;pa=pa->next;deleteu;}∥释放结点空间while(pb){u=pb;pb=pb->next;deleteu;}∥释放结点空间pc->next=null;∥置链表尾标记。deleteLb;∥注：本算法中也可对B表不作释放空间的处理（4）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。voidDifference（LinkedListA，B，*n）∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0{p=A->next；∥p和q分别是链表A和B的工作指针。q=B->next；pre=A；∥pre为A中p所指结点的前驱结点的指针。while（p!=null&&q!=null）if（p->datadata）{pre=p；p=p->next；*n++；}∥A链表中当前结点指针后移。elseif（p->data>q->data）q=q->next；∥B链表中当前结点指针后移。else{pre->next=p->next；∥处理A，B中元素值相同的结点，应删除。u=p；p=p->next；deleteu；}∥删除结点（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL){if(L->next==NULL)returnNULL;pmax=L->next;//假定第一个结点中数据具有最大值p=L->next->next;while(p!=NULL){//如果下一个结点存在if(p->data>pmax->data)pmax=p;p=p->next;}returnpmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L->next;L->next=NULL;while(p){q=p->next;//q指向*p的后继p->next=L->next;L->next=p;//*p插入在头结点之后
p=q;}}（8）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。voiddelete(LinkList&L,intmink,intmaxk){p=L->next;//首元结点while(p&&p->data<=mink){pre=p;p=p->next;}//查找第一个值>mink的结点if(p){while(p&&p->datanext;//查找第一个值≥maxk的结点q=pre->next;pre->next=p;//修改指针while(q!=p){s=q->next;deleteq;q=s;}//释放结点空间}//if}（9）已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。voidExchange（LinkedListp）∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。{q=p->llink；q->llink->rlink=p；∥p的前驱的前驱之后继为pp->llink=q->llink；∥p的前驱指向其前驱的前驱。q->rlink=p->rlink；∥p的前驱的后继为p的后继。q->llink=p；∥p与其前驱交换p->rlink->llink=q；∥p的后继的前驱指向原p的前驱p->rlink=q；∥p的后继指向其原来的前驱}∥算法exchange结束。（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。[题目分析]在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。voidDelete（ElemTypeA[]，intn）∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。{i=1；j=n；∥设置数组低、高端指针（下标）。while（i=’0’&&x<=’9’)||x==’.’)//拼数if(x!=’.’)//处理整数{num=num*10+（ord(x)-ord(‘0’)）;scanf(“%c”,&x);}else//处理小数部分。
{scale=10.0;scanf(“%c”,&x);while(x>=’0’&&x<=’9’){num=num+(ord(x)-ord(‘0’)/scale;scale=scale*10;scanf(“%c”,&x);}}//elsepush(OPND,num);num=0.0;//数压入栈，下个数初始化casex=‘’:break;//遇空格，继续读下一个字符。casex=‘+’:push(OPND,pop(OPND)+pop(OPND));break;casex=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;casex=‘*’:push(OPND,pop(OPND)*pop(OPND));break;casex=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;default://其它符号不作处理。}//结束switchscanf(“%c”,&x);//读入表达式中下一个字符。}//结束while（x！=‘$’）printf(“后缀表达式的值为%f”,pop(OPND));}//算法结束。[算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。（5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。①下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。①A和D是合法序列，B和C是非法序列。②设被判定的操作序列已存入一维数组A中。intJudge(charA[])//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。{i=0;//i为下标。j=k=0;//j和k分别为I和字母O的的个数。while(A[i]!=‘ ’)//当未到字符数组尾就作。{switch(A[i])
{case‘I’:j++;break;//入栈次数增1。case‘O’:k++;if(k>j){printf(“序列非法n”)；exit(0);}}i++;//不论A[i]是‘I’或‘O’，指针i均后移。}if(j!=k){printf(“序列非法n”)；return(false);}else{printf(“序列合法n”)；return(true);}}//算法结束。[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘ ’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。(6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。 算法如下： //先定义链队结构: typedefstructqueuenode{ Datatypedata; structqueuenode*next; }QueueNode;//以上是结点类型的定义 typedefstruct{ queuenode*rear; }LinkQueue;//只设一个指向队尾元素的指针 (1)置空队 voidInitQueue(LinkQueue*Q) {//置空队：就是使头结点成为队尾元素 QueueNode*s; Q->rear=Q->rear->next;//将队尾指针指向头结点 while
(Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next; Q->rear->next=s->next; free(s); }//回收结点空间 } (2)判队空 intEmptyQueue(LinkQueue*Q) {//判队空 //当头结点的next指针指向自己时为空队 returnQ->rear->next->next==Q->rear->next; } (3)入队 voidEnQueue(LinkQueue*Q,Datatypex) {//入队 //也就是在尾结点处插入元素 QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点 p->data=x;p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p; Q->rear=p;//将尾指针移至新结点 } (4)出队 DatatypeDeQueue(LinkQueue*Q) {//出队,把头结点之后的元素摘下 Datatypet; QueueNode*p; if(EmptyQueue(Q)) Error("Queueunderflow"); p=Q->rear->next->next;//p指向将要摘下的结点 x=p->data;
//保存结点中数据 if(p==Q->rear) {//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear=Q->rear->next;Q->rear->next=p->next;} else Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 returnx; }（7）假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义#includetemplateclassQueue{//循环队列的类定义public:Queue(int=10);~Queue(){delete[]Q;}voidEnQueue(Type&item);TypeDeQueue();TypeGetFront();voidMakeEmpty(){front=rear=tag=0;}//置空队列intIsEmpty()const{returnfront==rear&&tag==0;}//判队列空否intIsFull()const{returnfront==rear&&tag==1;}//判队列满否private:intrear,front,tag;//队尾指针、队头指针和队满标志Type*Q;//存放队列元素的数组intm;//队列最大可容纳元素个数}构造函数templateQueue::Queue(intsz):rear(0),front(0),tag(0),m(sz){//建立一个最大具有m个元素的空队列。Q=newType[m];//创建队列空间assert(Q!=0);//断言:动态存储分配成功与否}插入函数templatevoidQueue::EnQueue(Type&item){
assert(!IsFull());//判队列是否不满，满则出错处理rear=(rear+1)%m;//队尾位置进1,队尾指针指示实际队尾位置Q[rear]=item;//进队列tag=1;//标志改1，表示队列不空}删除函数templateTypeQueue::DeQueue(){assert(!IsEmpty());//判断队列是否不空，空则出错处理front=(front+1)%m;//队头位置进1,队头指针指示实际队头的前一位置tag=0;//标志改0,表示栈不满returnQ[front];//返回原队头元素的值}读取队头元素函数templateTypeQueue::GetFront(){assert(!IsEmpty());//判断队列是否不空，空则出错处理returnQ[(front+1)%m];//返回队头元素的值}(8）如果允许在循环队列的两端都可以进行插入和删除操作。要求：①写出循环队列的类型定义；②写出“从队尾删除”和“从队头插入”的算法。[题目分析]用一维数组v[0..M-1]实现循环队列，其中M是队列长度。设队头指针front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。（1）#defineM队列可能达到的最大长度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;（2）elemtpdelqueue(cycqueueQ)//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。{if(Q.front==Q.rear){printf(“队列空”);exit(0);}Q.rear=(Q.rear-1+M)%M;//修改队尾指针。return(Q.data[(Q.rear+1+M)%M]);//返回出队元素。}//从队尾删除算法结束voidenqueue(cycqueueQ,elemtpx)//Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。{if(Q.rear==(Q.front-1+M)%M){printf(“队满”;exit(0);)Q.data[Q.front]=x;//x入队列
Q.front=(Q.front-1+M)%M;//修改队头指针。}//结束从队头插入算法。（9）已知Ackermann函数定义如下:①写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。②写出计算Ack(m,n)的非递归算法。intAck(intm,n){if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ack(m-1,1));elsereturn(Ack(m-1,Ack(m,m-1));}//算法结束（1）Ack(2,1)的计算过程Ack(2,1)=Ack(1,Ack(2,0))//因m<>0,n<>0而得=Ack(1,Ack(1,1))//因m<>0,n=0而得=Ack(1,Ack(0,Ack(1,0)))//因m<>0,n<>0而得=Ack(1,Ack(0,Ack(0,1)))//因m<>0,n=0而得=Ack(1,Ack(0,2))//因m=0而得=Ack(1,3)//因m=0而得=Ack(0,Ack(1,2))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(1,1)))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(0,Ack(1,0))))//因m<>0,n<>0而得=Ack(0,Ack(0,Ack(0,Ack(0,1))))//因m<>0,n=0而得=Ack(0,Ack(0,Ack(0,2)))//因m=0而得=Ack(0,Ack(0,3))//因m=0而得=Ack(0,4)//因n=0而得=5//因n=0而得（2）intAckerman(intm,intn){intakm[M][N];inti,j;for(j=0;j//定义在头文件"RecurveList.h"中classList;classListNode{//链表结点类friendclassList;private:intdata;//结点数据ListNode*link;//结点指针ListNode(constintitem):data(item),link(NULL){}//构造函数};classList{//链表类private:ListNode*first,current;intMax(ListNode*f);intNum(ListNode*f);floatAvg(ListNode*f,int&n);public:List():first(NULL),current(NULL){}//构造函数~List(){}//析构函数ListNode*NewNode(constintitem);//创建链表结点,其值为itemvoidNewList(constintretvalue);//建立链表,以输入retvalue结束voidPrintList();//输出链表所有结点数据intGetMax(){returnMax(first);}//求链表所有数据的最大值intGetNum(){returnNum(first);}//求链表中数据个数floatGetAvg(){returnAvg(first);}//求链表所有数据的平均值};ListNode*List::NewNode(constintitem){//创建新链表结点ListNode*newnode=newListNode(item);returnnewnode;}voidList::NewList(constintretvalue){//建立链表,以输入retvalue结束first=NULL;intvalue;ListNode*q;cout<<"Inputyourdata:n";//提示cin>>value;//输入while(value!=retvalue){//输入有效q=NewNode(value);//建立包含value的新结点if(first==NULL)first=current=q;//空表时,新结点成为链表第一个结点else{current->link=q;current=q;}//非空表时,新结点链入链尾cin>>value;//再输入}current->link=NULL;//链尾封闭}
voidList::PrintList(){//输出链表cout<<"nTheListis:n";ListNode*p=first;while(p!=NULL){cout<data<<"";p=p->link;}cout<<‘n’;}intList::Max(ListNode*f){//递归算法:求链表中的最大值if(f->link==NULL)returnf->data;//递归结束条件inttemp=Max(f->link);//在当前结点的后继链表中求最大值if(f->data>temp)returnf->data;//如果当前结点的值还要大,返回当前检点值elsereturntemp;//否则返回后继链表中的最大值}intList::Num(ListNode*f){//递归算法:求链表中结点个数if(f==NULL)return0;//空表,返回0return1+Num(f->link);//否则,返回后继链表结点个数加1}floatList::Avg(ListNode*f,int&n){//递归算法:求链表中所有元素的平均值if(f->link==NULL)//链表中只有一个结点,递归结束条件{n=1;return(float)(f->data);}else{floatSum=Avg(f->link,n)*n;n++;return(f->data+Sum)/n;}}#include"RecurveList.h"//定义在主文件中intmain(intargc,char*argv[]){Listtest;intfinished;cout<<“输入建表结束标志数据：”;cin>>finished;//输入建表结束标志数据test.NewList(finished);//建立链表test.PrintList();//打印链表cout<<"nTheMaxis:"<=pos;j--){*(p+x)=*p;p--;}//串s的pos后的子串右移，空出串t的位置。q--;//指针q回退到串t的最后一个字符for(j=1;j<=x;j++)*p--=*q--;//将t串插入到s的pos位置上[算法讨论]串s的结束标记(" ")也后移了，而串t的结尾标记不应插入到s中。（8）已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2,其多余的字符送S3。[题目分析]本题要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按给定长度n格式化成两端对齐的字符串”，即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1，找到第一个非空格字符，计数到n，第n个拷入字符串s2的字符不得为空格，然后将余下字符复制到字符串s3中。voidformat(char*s1,*s2,*s3)//将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐{char*p=s1,*q=s2;inti=0;while(*p!=" "&&*p=="")p++;//滤掉s1左端空格if(*p==" "){printf("字符串s1为空串或空格串n");exit(0);}while(*p!=" "&&i0)i++;while(ilchild==NULL&&T->rchild==NULL)return1;//判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1elsereturnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);}（2）判别两棵树是否相等。（3）交换二叉树每个结点的左孩子和右孩子。voidChangeLR(BiTree&T){BiTreetemp;if(T->lchild==NULL&&T->rchild==NULL)return;else{temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;
}ChangeLR(T->lchild);ChangeLR(T->rchild);}（4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。voidDoubleTraverse(BiTreeT){if(T==NULL)return;elseif(T->lchild==NULL&&T->rchild==NULL)cout<data;else{cout<data;DoubleTraverse(T->lchild);cout<data;DoubleTraverse(T->rchild);}}（5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。[题目分析]求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。intWidth(BiTreebt)//求二叉树bt的最大宽度{if(bt==null)return(0);//空二叉树宽度为0else{BiTreeQ[];//Q是队列，元素为二叉树结点指针，容量足够大front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置temp=0;maxw=0;//temp记局部宽度,maxw记最大宽度Q[rear]=bt;//根结点入队列while(front<=last){p=Q[front++];temp++;//同层元素数加1if(p->lchild!=null)Q[++rear]=p->lchild;//左子女入队if(p->rchild!=null)Q[++rear]=p->rchild;//右子女入队if(front>last)//一层结束，{last=rear;if(temp>maxw)maxw=temp;//last指向下层最右元素,更新当前最大宽度temp=0;}//if}//whilereturn(maxw);
}//结束width（6）用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。intLevel(BiTreebt)//层次遍历二叉树，并统计度为1的结点的个数{intnum=0;//num统计度为1的结点的个数if(bt){QueueInit(Q);QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列while(!QueueEmpty(Q)){p=QueueOut(Q);printf(p->data);//出队,访问结点if(p->lchild&&!p->rchild||!p->lchild&&p->rchild)num++;//度为1的结点if(p->lchild)QueueIn(Q,p->lchild);//非空左子女入队if(p->rchild)QueueIn(Q,p->rchild);//非空右子女入队}}//if(bt)return(num);}//返回度为1的结点的个数（7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。[题目分析]因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。voidLongestPath(BiTreebt)//求二叉树中的第一条最长路径长度{BiTreep=bt,l[],s[];//l,s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点inti，top=0,tag[],longest=0;while(p||top>0){while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下if(tag[top]==1)//当前结点的右分枝已遍历{if(!s[top]->Lc&&!s[top]->Rc)//只有到叶子结点时，才查看路径长度if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top--;}//保留当前最长路径到l栈，记住最高栈顶指针，退栈}elseif(top>0){tag[top]=1;p=s[top].Rc;}//沿右子分枝向下}//while(p!=null||top>0)}//结束LongestPath（8）输出二叉树中从每个叶子结点到根结点的路径。[题目分析]采用先序遍历的递归方法，当找到叶子结点*b时，由于*b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。对应的递归算法如下：voidAllPath(BTNode*b,ElemTypepath[],intpathlen){inti;if(b!=NULL){if(b->lchild==NULL&&b->rchild==NULL)//*b为叶子结点{
cout<<""<data<<"到根结点路径:"<data;for(i=pathlen-1;i>=0;i--)cout<data;//将当前结点放入路径中pathlen++;//路径长度增1AllPath(b->lchild,path,pathlen);//递归扫描左子树AllPath(b->rchild,path,pathlen);//递归扫描右子树pathlen--;//恢复环境}}}
第6章图2．应用题（1）已知如图6.27所示的有向图，请给出：①每个顶点的入度和出度；②邻接矩阵；③邻接表；④逆邻接表。图6.27有向图
（2）已知如图6.28所示的无向网，请给出：①邻接矩阵；②邻接表；③最小生成树图6.28无向网a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
图6.29邻接矩阵（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。图6.30有向网D终点i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e∞10(a,c,e)10(a,c,e)f∞6(a,c,f)g∞∞16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S终点集{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}（5）试对图6.31所示的AOE-网：①求这个工程最早可能在什么时间结束；②求每个活动的最早开始时间和最迟开始时间；图6.31AOE-网③确定哪些活动是关键活动
【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l-e=0?来确定关键活动，从而确定关键路径。1¶2¸3·4¹5º6»Ve01915293843Vl01915373843<1,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>e00151919152938l170152719273738l-e1700801280此工程最早完成时间为43。关键路径为<1,3><3,2><2,5><5,6>3．算法设计题（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：①增添一个新顶点v，InsertVex(G,v)；②删除顶点v及其相关的边，DeleteVex(G,v);③增加一条边，InsertArc(G,v,w);④删除一条边，DeleteArc(G,v,w)。//本题中的图G均为有向无权图,其余情况容易由此写出StatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点v{if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE;G.vexs[++G.vexnum]=v;returnOK;}//Insert_VexStatusInsert_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上插入边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(i==j)return
ERROR;if(!G.arcs[j].adj){G.arcs[j].adj=1;G.arcnum++;}returnOK;}//Insert_ArcStatusDelete_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上删除顶点v{n=G.vexnum;if((m=LocateVex(G,v))<0)returnERROR;G.vexs[m]<->G.vexs[n];//将待删除顶点交换到最后一个顶点for(i=0;iadjvex=j;p->nextarc=NULL;if(!G.vertices.firstarc)G.vertices.firstarc=p;else{for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc)if(q->adjvex==j)returnERROR;
//边已经存在q->nextarc=p;}G.arcnum++;returnOK;}//Insert_Arc（2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。数据结构考研指导232页7.3.7（3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。数据结构考研指导232页7.3.8（4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。解1：intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//else}//exist_path_DFS解2：（以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。）intvisited[MAXSIZE];//指示顶点是否在当前路径上intlevel＝1;//递归进行的层数intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--){level++;k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for
}//elseif(level==1)return0;}//exist_path_DFS（5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径{{if(i==j&&k==0)return1;//找到了一条路径,且长度符合要求elseif(k>0){visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){l=p->adjvex;if(!visited[l])if(exist_path_len(G,l,j,k-1))return1;//剩余路径长度减一}//forvisited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中}//elsereturn0;//没找到}//exist_path_len
第7章查找2．应用题（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：①画出描述折半查找过程的判定树；②若查找元素54，需依次与哪些元素比较？③若查找元素90，需依次与哪些元素比较？④假定每个元素的查找概率相等，求查找成功时的平均查找长度。①先画出判定树如下（注：mid=ë(1+12)/2û=6）：30563374287424547295②查找元素54，需依次与30,63,42,54元素比较；③查找元素90，需依次与30,63,87,95元素比较；④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.08（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。1271721116214913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，21（3）已知如下所示长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。解：
（4）对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。①插入90②插入25③插入45④删除60 （5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：①画出哈希表的示意图；②若查找关键字63，需要依次与哪些关键字进行比较？③若查找关键字60，需要依次与哪些关键字比较？④假定每个关键字的查找概率相等，求查找成功时的平均查找长度。①画表如下：012345678910111213141516173217634924401030314647②查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！③查找60,首先要与H(60)=60%16=1
2号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。④对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3+6）＝23/11（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key%7，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520 比较次数11123412 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以关键字27为例：H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突）H3=（6+33）%10=5所以比较了4次。（7）设哈希函数H（K）=3Kmod11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。①线性探测法；②链地址法。①散列地址012345678910关键字 4 12493813243221 比较次数 1 1121212 ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11②ASLsucc=（1*5+2*3）/8=11/8ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11（5）
设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：①画出哈希表的示意图；②若查找关键字63，需要依次与哪些关键字进行比较？③若查找关键字60，需要依次与哪些关键字比较？④假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：（1）画表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3+6）＝23/11（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key%7，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520 比较次数11123412 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以关键字27为例：H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突）H3=（6+33）%10=5所以比较了4次。（7）设哈希函数H（K）=3Kmod11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。①线性探测法；②链地址法。散列地址012345678910关键字 4 12493813243221 比较次数 1 1121212 ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11
第8章排序2．应用题（1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。①直接插入排序②折半插入排序③希尔排序（增量选取5，3，1）④冒泡排序⑤快速排序⑥简单选择排序⑦堆排序⑧二路归并排序①直接插入排序[212]1630281016*20618[21216]30281016*20618[2121630]281016*20618[212162830]1016*20618[21012162830]16*20618[210121616*2830]20618[210121616*202830]618[2610121616*202830]18[2610121616*18202830]②折半插入排序排序过程同①③希尔排序（增量选取5，3，1）102166181216*203028（增量选取5）621210181616*203028（增量选取3）2610121616*18202830（增量选取1）④冒泡排序21216281016*20618[30]212161016*20618[2830]212101616*618[202830]2101216616*[18202830]21012616[16*18202830]
210612[1616*18202830]2610[121616*18202830]2610121616*18202830]⑤快速排序12[6210]12[283016*201618]6[2]6[10]12[283016*201618]28261012[181616*20]28[30]18261012[16*16]18[20]283016*26101216*[16]18202830左子序列递归深度为1，右子序列递归深度为3⑥简单选择排序2[121630281016*20618]26[1630281016*201218]2610[30281616*201218]261012[281616*203018]26101216[2816*203018]2610121616*[28203018]2610121616*18[203028]2610121616*1820[2830]2610121616*182028[30]⑧二路归并排序2121630102816*2061821216301016*2028618210121616*2028306182610121616*18202830⑦堆排序第一步,形成初始大根堆（详细过程略），第二步做堆排序。1221620103016*28618302816102016*182126初始排序不是大根堆形成初始大根堆
1228162102016*18630282016101216*182306交换1与10对象从1到9重新形成堆620162101216*182830201816101216*623028交换1与9对象从1到8重新形成堆2181620101216*6283018121610216*12203028交换1与8对象从1到7重新形成堆16*121620102186283016*1216102186203028交换1与7对象从1到6重新形成堆
1012162016*2186283016121016*2186203028交换1与6对象从1到5重新形成堆612102016*2181628301261016*21816203028交换1与5对象从1到4重新形成堆126102016*1218162830106216*121816203028交换1与4对象从1到3重新形成堆26102016*1218162830621016*121816203028交换1与3对象从1到2重新形成堆
26102016*1218162830261016*121816203028交换1与2对象得到结果（2）给出如下关键字序列｛321，156，57，46，28，7，331，33，34，63｝，试按链式基数排序方法，列出每一趟分配和收集的过程。3．算法设计题（1）试以单链表为存储结构，实现简单选择排序算法。voidLinkedListSelectSort(LinkedListhead)//本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下//当前结点和最小结点的前驱指针p=head->next;while(p!=null){q=p->next;r=p;//设r是指向关键字最小的结点的指针while(q!=null){if(q->datadata)r=q;q:=q->next;}if(r!=p)r->data<-->p->data;p=p->next;}（2）有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。typedefstructnode{ElemTypedata;structnode*prior,*next;}node，*DLinkedList;voidTwoWayBubbleSort(DLinkedListla)//对存储在带头结点的双向链表la中的元素进行双向起泡排序。{intexchange=1;//设标记DLinkedListp,temp,tail;head=la//双向链表头，算法过程中是向下起泡的开始结点tail=null;//双向链表尾，算法过程中是向上起泡的开始结点while(exchange)
{p=head->next;//p是工作指针，指向当前结点exchange=0;//假定本趟无交换while(p->next!=tail)//向下（右）起泡，一趟有一最大元素沉底if(p->data>p->next->data)//交换两结点指针，涉及6条链{temp=p->next;exchange=1;//有交换p->next=temp->next;temp->next->prior=p//先将结点从链表上摘下temp->next=p;p->prior->next=temp;//将temp插到p结点前temp->prior=p->prior;p->prior=temp;}elsep=p->next;//无交换，指针后移tail=p;//准备向上起泡p=tail->prior;while(exchange&&p->prior!=head)//向上（左）起泡，一趟有一最小元素冒出if(p->dataprior->data)//交换两结点指针，涉及6条链{temp=p->prior;exchange=1;//有交换p->prior=temp->prior;temp->prior->next=p；//先将temp结点从链表上摘下temp->prior=p;p->next->prior=temp;//将temp插到p结点后（右）temp->next=p->next;p->next=temp;}elsep=p->prior;//无交换，指针前移head=p;//准备向下起泡}//while(exchange)}//算法结束（3）设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。[题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是兰色，则元素不动，指针左移（即k-1）；若当前元素是红色砾石，分i>=j（这时尚没有白色砾石）和i=j){temp=r[k];r[k]=r[i];r[i]=temp;i++;}//左侧只有红色砾石，交换r[k]和r[i]else{temp=r[j];r[j]=r[i];r[i]=temp;j++;//左侧已有红色和白色砾石，先交换白色砾石到位temp=r[k];r[k]=r[i];r[i]=temp;i++;//白色砾石（i所指）和待定砾石（j所指）}//再交换r[k]和r[i]，使红色砾石入位。if(r[k].key==2)if(i<=j){temp=r[k];r[k]=r[j];r[j]=temp;j++;}//左侧已有白色砾石，交换r[k]和r[j]else{temp=r[k];r[k]=r[i];r[i]=temp;j=i+1;}//i、j分别指向红、白色砾石的后一位置}//whileif(r[k]==2)j++;/*处理最后一粒砾石elseif(r[k]==1){temp=r[j];r[j]=r[i];r[i]=temp;i++;j++;}//最后红、白、兰色砾石的个数分别为:i-1;j-i;n-j+1}//结束QkSor算法[算法讨论]若将j（上面指向白色）看作工作指针，将r[1..j-1]作为红色，r[j..k-1]为白色，r[k..n]为兰色。从j=1开始查看，若r[j]为白色，则j=j+1；若r[j]为红色，则交换r[j]与r[i]，且j=j+1，i=i+1；若r[j]为兰色，则交换r[j]与r[k];k=k-1。算法进行到j>k为止。算法片段如下：inti=1,j=1,k=n;while(j<=k)if(r[j]==1)//当前元素是红色{temp=r[i];r[i]=r[j];r[j]=temp;i++;j++;}elseif(r[j]==2)j++;//当前元素是白色else//(r[j]==3当前元素是兰色{temp=r[j];r[j]=r[k];r[k]=temp;k--;}对比两种算法，可以看出，正确选择变量（指针）的重要性。（4）编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：①采用顺序存储结构，至多使用一个记录的辅助存储空间；②算法的时间复杂度为O(n)。（5）借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..n]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请简要说明算法思想并编写算法。[题目分析]把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回0为止。intindex(RecTypeR[],intl,h,datatypekey){inti=l,j=h;while(ikey)j--;
if(R[j].key==key)returnj;while(i<=j&&R[i].key
您可能关注的文档
- 2011年海淀中考一模《物理》试题及答案.doc
- 2011年版本的毛邓三课后习题答案.doc
- 2011年环评案例书后思考题答案.doc
- 2011年税务师《税收相关法律》考试真题及答案解析.doc
- 2011年证券从业资格考试《证券交易》分章练习1500题(含参考答案).doc
- 2011年质量专业相关知识(初级)考前预测题及答案.pdf
- 2011年造价员《基础知识》模拟试题与答案.doc
- 2011期货投资分析课后习题答案.doc
- 2011毛概1至15章完整版的课后习题答案.doc
- 2011造价员《基础知识》考前试题与答案(单项).doc
- 2011造价员《基础知识》考前试题与答案1-20.doc
- 2011银行从业资格考试《个人理财》章节习题及答案.doc
- 2012-2015一级建造师《建筑实务》真题及答案(完整版)已排版下载即可打印.doc
- 2012.01第一版报关实务教材参考答案.doc
- 2012CPA税法练习题答案(1-11).doc
- 2012《一课一练 创新练习》8年级英语上册(人教版)夹卷参考答案.pdf
- 2012《一课一练%20创新练习》9年级数学上册(人教版)参考答案[1].pdf
- 2012《一课一练%20创新练习》9年级数学全一册(北师大版)参考答案[1].pdf
相关文档
- 施工规范CECS140-2002给水排水工程埋地管芯缠丝预应力混凝土管和预应力钢筒混凝土管管道结构设计规程
- 施工规范CECS141-2002给水排水工程埋地钢管管道结构设计规程
- 施工规范CECS142-2002给水排水工程埋地铸铁管管道结构设计规程
- 施工规范CECS143-2002给水排水工程埋地预制混凝土圆形管管道结构设计规程
- 施工规范CECS145-2002给水排水工程埋地矩形管管道结构设计规程
- 施工规范CECS190-2005给水排水工程埋地玻璃纤维增强塑料夹砂管管道结构设计规程
- cecs 140：2002 给水排水工程埋地管芯缠丝预应力混凝土管和预应力钢筒混凝土管管道结构设计规程（含条文说明）
- cecs 141：2002 给水排水工程埋地钢管管道结构设计规程 条文说明
- cecs 140：2002 给水排水工程埋地管芯缠丝预应力混凝土管和预应力钢筒混凝土管管道结构设计规程 条文说明
- cecs 142：2002 给水排水工程埋地铸铁管管道结构设计规程 条文说明
微信/支付宝扫码支付下载-
关注微信公众号售出明细实时看