一、算法设计题(每题15分,共60分)
答题要求:
①用自然语言说明所采用算法的思想;
②给出每个算法所需的数据结构定义,并做必要说明; ③写出对应的算法程序,并做必要的注释。
1、有一个带头结点的单链表,每个结点包括两个域,一个是整型域info,另一个是指向下一个结点的指针域next。假设单链表已建立,设计算法删除单链表中所有重复出现的结点,使得info域相等的结点只保留一个。
3、约瑟夫环问题(Josephus问题)是指编号为1、2、…,n的n(n>0)个人按顺时针方向围坐成一圈,现从第s个人开始按顺时针方向报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列,…,如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法,模拟此过程。
4、编程实现单链表的就地逆置。
23.在数组 A[1..n]中有n个数据,试建立一个带有头结点的循环链表,头指针为h,要求链中数据从小到大排列,重复的数据在链中只保存一个.
5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(15分)
(1)下面所示的序列中哪些是合法的?
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. 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
否则若(S<0)或(S>0且n<1)
则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 s t r i n g
str2 b e 设str1和str2是分别指向两个单词的头结点,请设计一个尽可能的高效算法,找出两个单词共同后缀的起始位置,分析算法时间复杂度。
将n(n>1)个整数存放到一维数组R中。设计一个尽可能高效(时间、空间)的算
法,将R中保存的序列循环左移p(0
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)分别为进队,出队和判别队列是否为空的函数,请填写算法中得空白处,完成其功能。
typedef struct node
{int data ; struct node *lchild, *rchild; }btnode; void EXCHANGE(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. typedef struct node
{int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t)
{if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ;
if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; }
26.树的先序非递归算法。 void example(b)
btree *b;
{ btree *stack[20], *p; int top; if (b!=null)
{ top=1; stack[top]=b; while (top>0)
{ p=stack[top]; top--; printf(“%d”,p->data); if (p->rchild!=null) {(1)___; (2)___; }
if (p->lchild!=null) (3)___; (4)__;
}}}}
27.由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树,下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列,生成一棵用二叉链表表示的二叉树并打印出后序遍历序列,请写出程序所缺的语句。
#define MAX 100 typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX];
main(int argc,int **argv)
{ TNODE *root;
if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); }
TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr; char *rpos; int k; if(n<=0) return NULL; ptr->info=(1)_______;
for((2)_______ ; rpos ptr->llink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } 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(k>1)上的叶子结点的个数。 35. 二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG,试画出该二叉树,并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法。 36. 设二叉树的结点结构是(Lc,data,Rc),其中Lc、Rc分别为指向左、右子树根的指针,data是字符型数据。试写出算法,求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。 2、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶 点到自己的弧) 5、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。(20分) 2 12 1 9 5 6 3 10 4 4 2 6 7 6 3 2 4 1、对图1 所示的连通网G,请用Prim算法构造其最小生成树(每选取一条边画一个图)。 图1 连通网G 4、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7}, E={ 37.在有向图G中,如果r到G中的每个结点都有路径可达,则称结点r为G的根结点。编写一个算法完成下列功能: (1).建立有向图G的邻接表存储结构; (2).判断有向图G是否有根,若有,则打印出所有根结点的值。 38.二部图(bipartite graph) G=(V,E)是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图,使得:V1中的任何两个结点在图G中均不相邻,V2中的任何结点在图G中也均不相邻。 (1).请各举一个结点个数为5的二部图和非二部图的例子。 (2).请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图,并分析程序的时间复杂度。设G用二维数组A来表示,大小为n*n(n为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【 39.我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。注:圈就是回路。 40. 请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用llink-rlink法存