第一范文网 - 专业文章范例文档资料分享平台

2010青海省数据库考试含答案深入

来源:用户分享 时间:2025/7/5 17:20:21 本文由閺夆晞濮ら埅锟� 分享 下载这篇文档手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ:xxxxxx 处理(尽可能给您提供完整文档),感谢您的支持与谅解。

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 typedef char datatype; typedef struct node{ datatype data;

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=0)

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); //左子女入队

搜索更多关于: 2010青海省数据库考试含答案深入 的文档
2010青海省数据库考试含答案深入.doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
本文链接:https://www.diyifanwen.net/c8d5zo4xw9968ub00wpnt_1.html(转载请注明文章来源)
热门推荐
Copyright © 2012-2023 第一范文网 版权所有 免责声明 | 联系我们
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ:xxxxxx 邮箱:xxxxxx@qq.com
渝ICP备2023013149号
Top