1、矩阵中元素按行和按列都已排序,要求查找时间复杂度为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
{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)__; }}}}
3、连通图的生成树包括图中的全部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
while (eg>=n) //破圈,直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。
{edge[k].w=0; eg--; }//测试下一条边edge[k],权值置0表示该边被删除 k++; //下条边 }//while }//算法结束。
connect()是测试图是否连通的函数,可用图的遍历实现,
4、请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
5、本题应使用深度优先遍历,从主调函数进入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。
6、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
7、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(15分)
(1)下面所示的序列中哪些是合法的?
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定被判定的操作序列已存入一维数组中)。
8、有一个带头结点的单链表,每个结点包括两个域,一个是整型域info,另一个是指向下一个结点的指针域next。假设单链表已建立,设计算法删除单链表中所有重复出现的结点,使得info域相等的结点只保留一个。 #include
struct node * next; } listnode;
typedef listnode* linklist;
/*--------------------------------------------*/ /* 删除单链表中重复的结点 */
/*--------------------------------------------*/ linklist deletelist(linklist head) { listnode *p,*s,*q; p=head->next; while(p) {s=p;
q=p->next; while(q)
if(q->data==p->data)
{s->next=q->next;free(q); q=s->next;} else
{ s=q; /*找与P结点值相同的结点*/ q=q->next; }
p=p->next; }
return head; }
9、数组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); //左子女入队
相关推荐: