对有n个记录的表按记录键值有序的顺序建立二叉排序树在这种情况下其查找的时间复杂度为【】

设顺序表中关键字是递增有序的,试写一顺序查找算法,将哨兵设在表的高下标端。然后求出等概率情况下查找成功时的ASL

假设有向图采用邻接表表示法,其定义如下:

typedef struct{

VertexNode adjlist[MaxVertexNum]:

int n,e;//图的当前顶点数和弧数

}ALGraph;//邻接表类型

其中顶点表结点 VertexNode结构为: vertex firstedge

边表结点 EdgeNode结构为:adjvex next

下列算法f33的功能是,对以邻接表表示的有向图进行拓扑排序

(1)阅读算法f33,并在空缺处填入合适的内容,使其成为一个完整的算法

(2)对于题33图所示的邻接表,将执行算法f33后的topo[]结果填入给定的数组中

void f33(ALGraph G, int topo []

{

int i.j,k,count=0:

int indegree[MaxVertexNum];

EdgeNode*p//为指向边表结点的指针

3D

Queue Q://Q为队列

FindIndegree(G, indegree);//求各顶点的人度,并置于入度向量indegree

InitQueue(&Q);

for(i=0: i

if(! indegree[i])En Queue(&Q,i);

while(!QueueEmpty(&Q))

{

j=①

topo[i]=++count;

for(p=G. adjlist[]. firstedge; P: P=p->next)

{

k=p->adjvex;

if--indegree-[k]②

}

ifcount

}

(1)①

②

(2)topo

下面的算法是用希尔排序法完成文件中各个记录按关键字递增次序排序请仔细阅读程序并把未完成的部分填上。

void ShellPass(SeqList R,int d)

{//希尔排序中的一趟排序,d为当前增量

for(i=d+i<=n;i++)//将rd+1n]分别插入各组当前的有序区

if(R[j]. key<  (1)   )

{

R[0]=R[i];j=i-d;

//R[0]只是暂存单元,不是哨兵

Do//查找Ri的插入位置

R+d=  (2)  //后移记录

j=j-d;

//查找前一记录

}while( (3)  &.& R[o].key

R[j+d]-R[o];

//插入Ri]到正确的位置上

}// end if

}//ShellPass

void ShellSort(SeqList R)

int incrementn;/增量初值,不妨设n>0

do{

increment=increment/3+1;//求下一增量

do{

ShellPass(r,  (4)  );//一趟增量为 increment的 Shell插入排序

}while(  (5)  )

)//ShellSort

(1)

(2)

(3)

(4)

(5)

阅读下列算法,并回答问题:

(1)无向图G如图所示,写出算法f31(&G)的返回值

(2)简述算法f31的功能

#define MaxNum 20

int visited[MaxNum];

void DFS(Graph,inti);//从顶点v出发进行深度优先搜索,访问顶点v时置

//[visited]为1

int f31(Graph #G)

{int I, k;

for(i=0in;i++)g->n为图G的顶点数目

visited[]=0;

for (i=k=: i: i++)

if (visited[i]==)

{k++

DFS(G,i);

}

return k;

}

(1)

(2)

下面是生成二叉排序树的算法,请仔细阅读程序并把未完成的部分填上。

BSTree CreateBST(void)

{//输入一个结点序列,建立一棵二叉排序树,将根结点指针返回

BSTree=  (1)  ;//初始时T为空树

KeyType key;

scanf("%d",  (2)   );//读入一个关键字

while(key)

//假设key=0是输入结束标志

InsertBST(&t,key);//将key插入二叉排序树T

scanf(%d",&key);//读入下一关键字

}

return   (3)  ;

//返回建立的二叉排序树的根指针

)//BSTree

}

(1)

(2)

(3)

已知二叉树如下:

请画出该二叉树对应的森林。

假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成,这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.0,0.32,0.03,0.21,0.10}

(1)为这8个字母设计哈夫曼编码。

(2)若用三位二进制数(7)对这8个字母进行等长编码,则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?

以关键字序列(265,301,751,129,937,63,742,694,76,438)为例,写出执行二路归并排序的各趟排序结束时,关键字序列的状态。

表示逻辑关系的存储结构可以有四种方式,即顺序存储方式、链式存储方式、( ) 和散列存储方式。

写出如下无向图的邻接矩阵和邻接表。