2023年湖北省数据总结基础

1、给出折半查找的递归算法，并给出算法时间复杂度性分析。

2、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。

3、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。#include <>typedef char datatype;typedef struct node listnode;

typedef listnode* linklist;

删除单链表中重复的结点*/

linklist deletelist(linklist head)else

s=q; /找与p结点值相同的结点*/q=q->next;}

p=p->next;}

return head;}

4、设有一组初始记录关键字序列（k1，k2，，kn），要求设计一个算法能够在o(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于ki，右半部分的每个关键字均大于等于ki。

void quickpass(int r,int s, int t)

r[i]=x;}

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) /ifp=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()

/判断有向图是否有根，有根则输出之。}/judgeroot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。6、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得：

二叉树t中具有非空的左，右两个儿子的结点个数n2;只有非空左儿子的个数nl;只有非空右儿子的结点个数nr和叶子结点个数n0。n2、nl、nr、n0都是全局量，且在调用count(t)之前都置为 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)

if (p->lchild!=null)(3)__4)__

2023年湖北省数据总结基础

2023年湖北省数据概述基础

2023年湖北省数据总结高级

2019湖北省数据简介高级

其他用户还读了