自考计算机网络数据结构模拟试卷九

设顺序表中关键字是递增有序的,试写一顺序查找算法,将哨兵设在表的高下标端。然后求出等概率情况下查找成功时的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)为例,写出执行二路归并排序的各趟排序结束时,关键字序列的状态。

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

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

用S表示入栈操作,×表示出栈操作若元素入栈的顺序为1234,为了得到1342出栈顺序相应的S和的操作串为( )

在顺序表中插入一个元素,需要移动元素,具体移动的元素个数与( )有关。

当线性表的长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用( )作为其存储结构。

设广义表L=((),()),试求head(l) tail)、length(l)和 depth(L)

数据元素及其关系在计算机内的存储方式,称为数据的( )

若对关键字序列(43,2,80,48,26,57,15,7,21,24,66)进行一趟增量为3的希尔排序,则得到的结果为( )

已知一组关键字为{15,36,28,97,24,7847,52,13,86},其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是( )

已知广义表LS=((a,x,y,z),(b,c),运用head和tail函数取出原子c的运算是( )

将一棵树转换成一棵二叉树,二叉树的根结点没有( )子树。

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

下面关于线性表的叙述中,错误的是【】

若根结点的层数为1,则具有n个结点的二叉树的最大高度是【】

若构造一棵个有n个结点的二叉排序树,在最坏情况下,其深度不超过【】

n个结点的线索二叉树上含有的线索数为【】

设无向图的顶点个数为n,则该图最多有【】条边。

假设在构建散列表时,采用线性探查法解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为【】

对长度为n的关键字序列进行堆排序的空间复杂度为【】

对于n阶对称矩阵,如果以行序或列序放入内存中,则需要【】个存储单元

非空广义表的表尾不可能是【】

已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排序时,前两趟排序的结果为(13,51,35,93,24,42,68,56,77)(13,24,51,35,93,42,56,68,77)所采用的排序方法是【】

设有广义表L=(x,y,a,L),则L的深度是【】

数据结构是具有【】的数据元素的集合。

对于数据结构,以下叙述中不正确的是【】

在一个图中,所有顶点的度数之和等于所有边数的【】倍。