数据结构复习题(附答案)
更新时间:2024-07-04 03:43:01 阅读量: 综合文库 文档下载
- 数据结构题库及答案推荐度:
- 相关推荐
一、算法设计题(每题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 str2 b e n g
设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法存储。 S2 S1 S3 S1 S4 S1 S6 S5 S1 S5 S1 S1 ①分别求出str1、str2的长度m、n ②将两个链表的表尾对齐。p、q两个指针。 ③p、q两个指针同步移动,直到指向相同结点。 先将n个数据(前后对应交换)原地逆置,然后再将前n-p和后p个分别原地逆置。 Void reverse(int r[], int left, int right) { int k=left, j=right, temp; while (k temp=r[k]; r[k]=r[j]; r[j]=temp; k++;j--; } } Void leftshift(int r[], int n, int p) { if(p>0&&p { reverse(r,0,n-1);reverse(r,0,n-p-1);reverse(r,n-p,n-1);} } 4. [题目分析]题目中要求矩阵两行元素的平均值按递增顺序排序,由于每行元素个数相等,按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和,放入一维数组中,然后选择一种排序方法,对该数组进行排序,注意在排序时若有元素移动,则与之相应的行中各元素也必须做相应变动。 void Translation(float *matrix,int n) //本算法对n×n的矩阵matrix,通过行变换,使其各行元素的平均值按递增排列。 {int i,j,k,l; float sum,min; //sum暂存各行元素之和 float *p, *pi, *pk; for(i=0; i {sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素. for (j=0; j *(p+i)=sum; //将一行元素之和存入一维数组. }//for i for(i=0; i for(j=i+1;j {pk=matrix+n*k; //pk指向第k行第1个元素. pi=matrix+n*i; //pi指向第i行第1个元素. for(j=0;j {sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;} sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和. }//if }//for i free(p); //释放p数组. }// Translation [算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它 2 排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n). 7.[题目分析]我们用l代表最长平台的长度,用k指示最长平台在数组b中的起始位置(下标)。用j记住局部平台的起始位置,用i指示扫描b数组的下标,i从0开始,依次和后续元素比较,若局部平台长度(i-j)大于l时,则修改最长平台的长度k(l=i-j)和其在b中的起始位置(k=j),直到b数组结束,l即为所求。 void Platform (int b[ ], int N) //求具有N个元素的整型数组b中最长平台的长度。 {l=1;k=0;j=0;i=0; while(i {while(i if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点 printf(“最长平台长度%d,在b数组中起始下标为%d”,l,k); }// Platform 8.[题目分析]矩阵中元素按行和按列都已排序,要求查找时间复杂度为O(m+n),因此不能采用常规的二层循环的查找。可以先从右上角(i=a,j=d)元素与x比较,只有三种情况:一是A[i,j]>x, 这情况下向j 小的方向继续查找;二是A[i,j] void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. {i=a; j=d; flag=0; //flag是成功查到x的标志 while(i<=b && j>=c) if(A[i][j]==x) {flag=1;break;} else if (A[i][j]>x) j--; else i++; if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型. else printf(“矩阵A中无%d 元素”,x); }算法search结束。 [算法讨论]算法中查找x的路线从右上角开始,向下(当x>A[i,j])或向左(当x 22、[题目分析]数组A和B的元素分别有序,欲将两数组合并到C数组,使C仍有序,应将A和B拷贝到C,只要注意A和B数组指针的使用,以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。 void union(int A[],B[],C[],m,n) //整型数组A和B各有m和n个元素,前者递增有序,后者递减有序,本算法将A和B归并为递增有序的数组C。 {i=0; j=n-1; k=0;// i,j,k分别是数组A,B和C的下标,因用C描述,下标从0开始 while(i if(a[i]=0) c[k++]=b[j--]; }算法结束 4、要求二叉树按二叉链表形式存储。15分 (1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。 BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x;BiTree bt; scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0) {bt=(BiNode *)malloc(sizeof(BiNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } else error(“输入错误”); return(bt); }//结束 BiTree int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是,返回1,否则,返回0 {int tag=0; BiTree p=bt, Q[]; // Q是队列,元素是二叉树结点指针,容量足够大 if(p==null) return (1); QueueInit(Q); QueueIn(Q,p); //初始化队列,根结点指针入队 while (!QueueEmpty(Q)) {p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队 else {if (p->lchild) return 0; //前边已有结点为空, 本结点不空 else tag=1; //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0; else tag=1; } //while return 1; } //JudgeComplete 3、已知一棵二叉树的中序遍历结果为:DBFEAGHCI,后序遍历结果为:DFEBHGICA。 (1)画出这棵二叉树,并写出它的前序遍历结果; (2)将这棵二叉树转换成等价的森林或树。 前序遍历结果为:ABDEFCGHI 24. (1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild) 25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild) 26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild 27. (1)*ppos // 根结点 (2)rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1 28. 证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 当n=1时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。 设当n=m-1时结论成立,现证明当n=m时结论成立。 设中序序列为S1,S2,?,Sm,后序序列是P1,P2,?,Pm。因后序序列最后一个元素Pm是根,则在中序序列中可找到与Pm相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m),因中序序列是由中序遍历而得,所以Si是根结点,S1,S2,?,Si-1是左子树的中序序列,而Si+1,Si+2,?,Sm是右子树的中序序列。 若i=1,则S1是根,这时二叉树的左子树为空,右子树的结点数是m-1,则{S2,S3,?,Sm}和{P1,P2,?,Pm-1}可以唯一确定右子树,从而也确定了二叉树。 若i=m,则Sm是根,这时二叉树的右子树为空,左子树的结点数是m-1,则{S1,S2,?,Sm-1}和{P1,P2,?,Pm-1}唯一确定左子树,从而也确定了二叉树。 最后,当1 可唯一确定二叉树的左子树,由{Si+1,Si+2,?,Sm}和 {Pi,Pi+1,?,Pm-1}可唯一确定二叉树的右子树 。 29. 原则,本题解答如下: (1) 若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树 (2) 若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树. (3) 若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树. (4) 若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二 叉树。 30. .[题目分析]后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性,设p在q的左边。后序遍历必然先遍历到结点p,栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时,将栈中元素从栈顶开始逐个到辅助栈中去匹配,第一个匹配(即相等)的元素就是结点p 和q的最近公共祖先。 typedef struct {BiTree t;int tag;//tag=0 表示结点的左子女已被访问,tag=1表示结点的右子女已被访问 }stack; stack s[],s1[];//栈,容量够大 BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0) {while(bt!=null && bt!=p && bt!=q) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下 if(bt==p) //不失一般性,假定p在q的左侧,遇结点p时,栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。 for(i=top;i>0;i--)//;将栈中元素的树结点到s1去匹配 {pp=s[i].t; for (j=top1;j>0;j--) if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”);return (pp);} } while(top!=0 && s[top].tag==1) top--; //退栈 if (top!=0){s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍历 }//结束while(bt!=null ||top>0) return(null);//q、p无公共祖先 }//结束Ancestor 31. .[题目分析]对一般二叉树,仅根据一个先序、中序、后序遍历,不能确定另一个遍历序列。但对于满二叉树,任一结点的左右子树均含有数量相等的结点,根据此性质,可将任一遍历序列转为另一遍历序列(即任一遍历序列均可确定一棵二叉树)。 void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2) //将满二叉树的先序序列转为后序序列,l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1) {post[h2]=pre[l1]; //根结点 half=(h1-l1)/2; //左或右子树的结点数 PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost 32. .[题目分析]叶子结点只有在遍历中才能知道,这里使用中序递归遍历。设置前驱结点指针pre,初始为空。第一个叶子结点由指针head指向,遍历到叶子结点时,就将它前驱的rchild指针指向它,最后叶子结点的rchild为空。 LinkedList head,pre=null; //全局变量 LinkedList InOrder(BiTree bt) //中序遍历二叉树bt,将叶子结点从左到右链成一个单链表,表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树 if(bt->lchild==null && bt->rchild==null) //叶子结点 if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历左子树 pre->rchild=null; //设置链表尾 } return(head); } //InOrder 时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n) 33.[题目分析]两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用递归算法。 int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1); else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar 34. .[题目分析]对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {if(bt==null || k<1) return(0); BiTree p=bt,Q[]; //Q是队列,元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数 int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针,level 是二叉树的层数 while(front<=rear) {p=Q[++front]; if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点 if(p->lchild) Q[++rear]=p->lchild; //左子女入队 if(p->rchild) Q[++rear]=p->rchild; //右子女入队 if(front==last) {level++; //二叉树同层最右结点已处理,层数增1 last=rear; } //last移到指向下层最右一元素 if(level>k) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel 35. .[题目分析] 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历 序列中的每个结点都是“局部根”。确定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。这样,定义一个全局变量指针R,指向层次序列待处理元素。算法中先处理根结点,将根结点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理二叉树的结点。队列中元素的数据结构定义如下: typedef struct { int lvl; //层次序列指针,总是指向当前“根结点”在层次序列中的位 置 int l,h; //中序序列的下上界 int f; //层次序列中当前“根结点”的双亲结点的指针 int lr; // 1—双亲的左子树 2—双亲的右子树 }qnode; BiTree Creat(datatype in[],level[],int n) //由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数 {if (n<1) {printf(“参数错误\\n”); exit(0);} qnode s,Q[]; //Q是元素为qnode类型的队列,容量足够大 init(Q); int R=0; //R是层次序列指针,指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点 p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据 for (i=0; i if (i==0) //根结点无左子树,遍历序列的1—n-1是右子树 {p->lchild=null; s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==n-1) //根结点无右子树,遍历序列的1—n-1是左子树 {p->rchild=null; s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else //根结点有左子树和右子树 {s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信 息入队列 s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信 息入队列 } while (!empty(Q)) //当队列不空,进行循环,构造二叉树的左右子树 { s=delqueue(Q); father=s.f; for (i=s.l; i<=s.h; i++) if (in[i]==level[s.lvl]) break; p=(bitreptr)malloc(sizeof(binode)); //申请结点空间 p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据 if (s.lr==1) father->lchild=p; else father->rchild=p; //让双亲的子女指针指向该结点 if (i==s.l) {p->lchild=null; //处理无左子女 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==s.h) {p->rchild=null; //处理无右子女 s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信 息入队列 } }//结束while (!empty(Q)) return(p); }//算法结束 36. .[题目分析]因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。 void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度 {BiTree p=bt,l[],s[]; //l, s是栈,元素是二叉树结点指针,l中保留当前最长路径中的结点 int i,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栈,记住最高栈顶指针,退栈 } else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath 2、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧) [题目分析]有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0,1,2表示这三种状态。前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点的状态为1,就可以输出回路了。 void Print(int v,int start ) //输出从顶点start开始的回路。 {for(i=1;i<=n;i++) if(g[v][i]!=0 && visited[i]==1 ) //若存在边(v,i),且顶点i的状态为1。 {printf(“%d”,v); if(i==start) printf(“\\n”); else Print(i,start);break;}//if }//Print void dfs(int v) {visited[v]=1; for(j=1;j<=n;j++ ) if (g[v][j]!=0) //存在边(v,j) if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if else {cycle=1; Print(j,j);} visited[v]=2; }//dfs void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i); }//find_cycle 5、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。20分 void Hospital(AdjMatrix w,int n) //在以邻接带权矩阵表示的n个村庄中,求医院建在何处,使离医院最远的村庄到医院的路径最短。 {for (k=1;k<=n;k++) //求任意两顶点间的最短路径 for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (w[i][k]+w[k][j] for (j=1;j<=n;j++) //求从某村庄i(1<=i<=n)到其它村庄的最长路径。 if (w[i][j]>s) s=w[i][j]; if (s<=m) {m=s; k=i;}//在最长路径中,取最短的一条。m记最长路径,k记出发顶点的下标。 Printf(“医院应建在%d村庄,到医院距离为%d\\n”,i,m); }//for }//算法结束 对以上实例模拟的过程略。各行中最大数依次是9,9,6,7,9,9。这几个最大数中最小者为6,故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。 1、对图1所示的连通网G,请用Prim算法构造其最小生成树(每选取一条边画一个图)。 4、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7}, E={ G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V7 37.[题目分析]本题应使用深度优先遍历,从主调函数进入dfs(v)时 ,开始记数,若退出dfs()前,已访问完有向图的全部顶点(设为n个),则有向图有根,v为根结点。将n个顶点从1到n编号,各调用一次dfs()过程,就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题,这里只给出判断有向图是否有根的算法。 int num=0, visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数; AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v) {visited [v]=1; num++; //访问的顶点数+1 if (num==n) {printf(“%d是有向图的根。\\n”,v); num=0;}//if p=g[v].firstarc; while (p) {if (visied[p->adjvex]==0) dfs (p->adjvex); p=p->next;} //while visited[v]=0; num--; //恢复顶点v }//dfs void JudgeRoot() //判断有向图是否有根,有根则输出之。 {static int i ; for (i=1;i<=n;i++ ) //从每个顶点出发,调用dfs()各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot 算法中打印根时,输出顶点在邻接表中的序号(下标),若要输出顶点信息,可使用g[i].vertex。 38.[题目分析] 将顶点放在两个集合V1和V2。对每个顶点,检查其和邻接点是否在同一个集合中,如是,则为非二部图。为此,用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g) //判断以邻接矩阵表示的图g是否是二部图。 {int s[]; //顶点向量,元素值表示其属于那个集合(值1和2表示两个集合) int Q[];//Q为队列,元素为图的顶点,这里设顶点信息就是顶点编号。 int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组 for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化,各顶点未确定属于那个集合 Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1 while(f {v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号 if (!visited[v]) {visited[v]=1; //确保对每一个顶点,都要检查与其邻接点不应在一个集合中 for (j=1,j<=n;j++) if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列 else if (s[j]==s[v]) return(0);} //非二部图 }//if (!visited[v]) }//while return(1); }//是二部图 [算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。 39.[题目分析] 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。 void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图的一棵最小代价生成树。 {typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数 node edge[]; scanf( \输入边数和顶点数。 for (i=1;i<=e;i++) //输入e条边:顶点,权值。 scanf(\ for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。 {edge[0]=edge[i]; j=i-1; while (edge[j].w k=1; eg=e; while (eg>=n) //破圈,直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。 {edge[k].w=0; eg--; }//测试下一条边edge[k],权值置0表示该边被删除 k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数,可用图的遍历实现, 40.根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结点值比较,即可得出结论,为此设全局指针变量pre(初值为null)和全局变量flag,初值为true。若非二叉排序树,则置flag为false。 #define true 1 #define false 0 typedef struct node {datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST(BTree t,int flag) // 判断二叉树是否是二叉排序树,本算法结束后,在调用程序中由flag得出结论。 { if(t!=null && flag) { Judgebst(t->llink,flag);// 中序遍历左子树 if(pre==null)pre=t;// 中序遍历的第一个结点不必判断 else if(pre->data 41. 非递归建立二叉排序树,在二叉排序树上插入的结点都是叶子结点。 void Creat_BST(BiTree bst,datatype K[],int n) // 以存储在数组K中的n个关键字,建立一棵初始为空的二叉排序树。 {for(i=1;i≤n;i++) {p=bst;f=null;//在调用Creat_BST时,bst=null while(p!=null) if(p->data s=(BiTree)malloc(sizeof (BiNode));// 申请结点空间 s->data=K[i];s->LLINK=null;s->RLINK=null; if(f==null)bst=s; //根结点 else if(s->data else f->RLINK=s;//右子树根结点的值大于等于根结点的值 }//算法结束 42. int BinSrch(rectype r[ ],int k,low,high) //在长为n的有序表中查找关键字k,若查找成功,返回k所在位置,查找失败返回0。 {if(low≤high) //low和high分别是有序表的下界和上界 {mid=(low+high)/2; if(r[mid].key==k)return (mid); else if(r[mid].key>k)return (BinSrch(r,k,mid+1,high)); else return (BinSrch(r,k,low,mid-1)); } else return (0);//查找失败。 }//算法结束 算法时间复杂度为O(logn)。 43. .[题目分析] 用链地址法解决冲突的哈希表是一个指针数组,数组分量均是指向单链表的指针,(第i个)单链表结点有两个域,一个是哈希地址为i的关键字,另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。 typedef struct node {keytype key; struct node *next; }HSNode;*HSList typedef struct node *HLK; void Delete(HLK HT[],keytype K) //用链地址法解决冲突,从哈希表中删去关键字为K的记录 {i=H(K);//用哈希函数确定关键字K的哈希地址 if(HT[i]==null){printf(“无被删除记录\\n”);exit(0);} HLK p,q; p=H[i];q=p; //p指向当前记录(关键字),q是p的前驱 while(p && p->key!=k){q=p;p=p->next;} if(p==null){printf(“无被删除记录”);exit(0); } if(q==H[i]) //被删除关键字是链表中第一个结点 {HT[i]=HT[i].next;free(p);} else{q->next=p->next;free(p);} }//结束Delete 44. .[题目分析]首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为i,则其余m-1(m为表长)个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率,减少数据移动,应将最后一个同义词前移填充被删除关键字。 void HsDelete(rectype HS[],K) //在以除余法为散列函数、线性探测解决冲突的散列表HS中,删除关键字K {i=K % P; // 以造表所用的除余法计算关键字K的散列地址 if(HS[i]==null){printf(“散列表中无被删关键字”);exit(0);} // 此处null代表散列表初始化时的空值 switch {case HS[i]==K:del(HS,i,i,K);break; case HS[i]!=K:di=1;j=(i+ di)%m; // m为 表长 while(HS[j]!=null && HS[j]!=K && j!=i)// 查找关键字K {di=di+1; j=(i+di)%m; }// m为 表长 if(HS[j]==K)del(HS,i,j,K); else {printf(“散列表中无被删关键字”);exit(0);} }// switch }算法结束 void del(rectype HS[],in i,int j,rectype K) //在散列表HS中,删除关键字K,K的散列地址是i,因解决冲突而将其物理地置于表中j。算法查找关键字K的同义词,将其最后一个同义词移到位置j,并将其同义词的位置置空。 {di=1;last=j;x=(j+di)% m;// 探测地址序列,last记K的最后一个同义词的位置 while(x!=i) //可能要探测一圈 {if(HS[x]==null)break; // 探测到空位置,结束探测 else if(HS[x]%P==i)last=x;// 关键字K的同义词 di=di+1;x=(j+di) % m; // 取下一地址探测 } HS[j]=HS[last]; HS[last]=null; //将哈希地址last的关键字移到哈希地址j } 45. [题目分析] 因为二叉树各结点已标明了平衡因子b,故从根结点开始记树的层次。根结点的层次为1,每下一层,层次加1,直到层数最大的叶子结点,这就是平衡二叉树的高度。当结点的平衡因子b为0时,任选左右一分枝向下查找,若b不为0,则沿左(当b=1时)或右(当b=-1时)向下查找。 int Height(BSTree t) // 求平衡二叉树t的高度 {level=0;p=t; while(p) {level++; // 树的高度增1 if(p->bf<0)p=p->rchild;//bf=-1 沿右分枝向下 //bf是平衡因子,是二叉树t结点的一个域,因篇幅所限,没有写出其存 储定义 else p=p->lchild; //bf>=0 沿左分枝向下 }//while return (level);//平衡二叉树的高度 } //算法结束 46. .[题目分析]非零元素个数是100,负载因子取0.8,表长125左右,取p为127,散列地址为0到126。哈希函数用H(k)=(3*i+2*j) % 127,i,j为行值和列值。 #define m 127 typedef struct {int i,j;datatype v;}triple; void CreatHT(triple H[m]) //100个非零元素生成稀疏矩阵的哈希表,表中元素值均初始化为0。 {for(k=0;k<100;k++) {scanf(&i,&j,&val);//设元素值为整型 h=(3*i+2*j)% m; //计算哈希地址 while(HT[h].v!=0)) h=(h+1) % m; //线性探测哈希地址 HT[h].i=i;HT[h].j=j;HT[h].v=val; //非零元素存入哈希表 } }//算法CreatHT结束 datatype Search(triple HT[m],int i,int j) //在哈希表中查找下标为i,j的非零元素,查找成功返回非零元素,否则返回零值。 {int h=(3*i+2*j) % m; while ((HT[h].i!=i || HT[h].j!=j) && HT[h].v!=0) h=(h+1)% m; return (HT[h].v); }//Search 2、画出向小顶堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时,每加入一个数据后堆的变化。 47. void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法 { change=1;low=0;high=n-1; //冒泡的上下界 while(low { change=0; //设不发生交换 for(i=low;i if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} //有交换,修改标志change high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i]a[i-1];change=1;} low++; //修改下界 }//while }//BubbleSort2 48. typedef struct node { ElemType data; struct node *prior,*next; }node,*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1; // 设标记 DLinkedList p,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;//有交换
正在阅读:
数据结构复习题(附答案)07-04
《青春期》教育主题班会教案09-28
常见的蔬菜(vegetables)01-25
河南省名牌认定准则06-10
大学物理热学题库及答案01-13
学号姓名基础理论知识测试(2)07-22
2017年吉林省普通高校对口招生统一考试--高考题(计算机应用基础部分)04-27
2018学年八年级数学上册全一册学案 人教版38〔优秀篇〕03-01
车队年底总结报告02-28
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 复习题
- 数据结构
- 答案
- 1—4按课文内容填空
- 国有企业转让单一债权后又以该债权转让前未经评估为由主张合同无
- 老阿姨观后感
- 2015年中小学教师系列崇左市高级评委会通过人员名单:132人
- 含参变量的积分
- 论传媒时代的文学理论教学-最新教育文档
- 配套K12辽宁省大石桥市第二高级中学2017-2018学年高二生物
- 年产万吨碳酸饮料工厂设计毕业设计
- 行政机关公文处理(讲座)
- 听力练习
- 2012美术教师考编资料,精心整理的哦
- 关于购置苹果平板电脑的请示
- 2018—2019年新人教部编本二年级语文下册16.雷雨教案(精品教学
- 中国矿业大学(北京)20012003年获国家级科技奖励项目...
- 初中体育课教案篮球运球教学设计与反思
- 王三运在中国共产党甘肃省第十二次代表大会上的报告(2012年4月2
- 2012届高考英语一轮单元总复习讲义精品荟萃:外研版必修3Module
- stata入门中文讲义
- 山东省网上信访信息系统用户操作手册v1 - 图文
- 华为Sybase数据库培训教材 - 图文