搜索
一、算法设计题（每题15分，共60分）答题要求：①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。4、编程实现单链表的就地逆置。23．在数组A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。3、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）（1）下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。5、设从键盘输入一整数的序列：a1,a2,a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。Knap(S，n)若S=0则Knap←true否则若（S0）或(S0且n1)则Knap←false否则若Knap(1),_=true则print(W[n])；Knap←true否则Knap←Knap(2)_,_设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如：设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。将n(n1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算法，将R中保存的序列循环左移p（0pn）个位置，即将R中的数据（x0,x1,x2,…,xn-1），变换为(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。4．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。7．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。【8.给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。【22.给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写出算法:将数组a和b归并为递增有序数组c[l..m+n]。(要求：算法的时间复杂度为O(m+n))4、要求二叉树按二叉链表形式存储，（15分）（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。3、已知一棵二叉树的中序遍历结果为：DBFEAGHCI，后序遍历结果为：DFEBHGICA。（1）画出这棵二叉树，并写出它的前序遍历结果；（2）将这棵二叉树转换成等价的森林或树。24.将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。stringbestr1str2typedefstructnode{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,*q;if(bt){ADDQ(Q,bt);while(!EMPTY(Q)){p=DELQ(Q);q=(1)___;p-rchild=(2)___;(3)___=q;if(p-lchild)(4)___;if(p-rchild)(5)___;}}}25.设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedefstructnode{intdata;structnode*lchild,*rchild;}node;intN2,NL,NR,N0;voidcount(node*t){if(t-lchild!=NULL)if(1)___N2++;elseNL++;elseif(2)___NR++;else(3)__;if(t-lchild!=NULL)(4)____;if(t-rchild!=NULL)(5)____;}26.树的先序非递归算法。voidexample(b)btree*b;{btree*stack[20],*p；inttop;if(b!=null){top=1;stack[top]=b;while(top0){p=stack[top];top--;printf(“%d”,p-data);if(p-rchild!=null){(1)___;(2)___;}if(p-lchild!=null)(3)___;(4)__;}}}}27.由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#defineMAX100typedefstructNode{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv){TNODE*root;if(argc3)exit0;strcpy(pred,argv[1]);strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE*restore(char*ppos,char*ipos,intn){TNODE*ptr；char*rpos;intk;if(n=0)returnNULL;ptr-info=(1)_______;for((2)_______;rposipos+n;rpos++)if(*rpos==*ppos)break;k=(3)_______;ptr-llink=restore(ppos+1,(4)_______,k);ptr-rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr-llink);postorder(ptr-rlink);printf(“%c”,ptr-info);}28.证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29.①试找出满足下列条件的二叉树1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同30.设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。31.设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。32.请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。33.设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。34.一棵二叉树以二叉链表来表示，求其指定的某一层k(k1)上的叶子结点的个数。35.二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG，试画出该二叉树，并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法。36.设二叉树的结点结构是（Lc,data,Rc），其中Lc、Rc分别为指向左、右子树根的指针，data是字符型数据。试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。2、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶图1连通网G点到自己的弧）5、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。4、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7}写出G的拓扑排序的结果。37.在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：（1）．建立有向图G的邻接表存储结构；（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。38．二部图（bipartitegraph）G=（V，E）是一个能将其结点集V分为两不相交子集V1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。（1）．请各举一个结点个数为5的二部图和非二部图的例子。（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【39．我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。40.请编写一个判别给定二叉树是否为二叉排序树的算法，设