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

试写出二分查找的递归算法。

下面的程序将数列1,2,3,…,n*n,依次按蛇型方式存放在二维数组An,n]中图示如下(当n为5时):

完善下列程序。

#define NMAX 10

# include"stdio.h"

main()

{int i,j,n,k, p,,m;

int a [NMAX][NMAX];

scanf("%d", &n);

m=1;

for(k=1;(1);k++)

else(2);

for(p=1; p<=q;p++)

{if((3))

{i=q-p+1;j=p;}

else{i=p:j=q-p+1;)

if((4))

(i=i+n-qij-j+n-q:)

A[i][j]m: (5)

}

for(i=1,i<=n;i++)

{for(j=1; j<=n,j++)

printf("%4d", a[ i][j]):printf("\n")

}

}

}

(1)

(2)

(3)

(4)

(5)

下面函数的功能是:利用栈的非递归实现二叉树的中序遍历。请在空缺处填入合适内容,使其成为一个完整的算法

void Inorderl(BinTree bt)

{

SeqStack S; BinTNode *,

InitStack(&S); Push(&S,bt);

while(!StackEmpty(&.S)){

while(GetTop(&.S))

push(&s GetTop(&s)->Ichild)//直到左子树空为止

p-Pop(&.S);//空指针退栈

if( (1) ){

printf( Get Top(&s)->data)/访问根结点

p=pop(&s)push(&s, (2) )//右子树进栈

}

}

}

(1)

(2)

请在下列算法的横线上填入适当的语句。

int inclusion(LinkList ha, LinkList hb)

{//以ha和hb为头指针的单链表分别表示有序表A和B本算法判别表A是否包含在表

//B内若是,则返回1,否则返回0

LinkList pa,pb;

pa=ha->next; pb=hb->next;

(1)   

While (2)  

if (pa->data==pb->data)

(3)   

else

(4)  

(5)  

}

(1)

(2)

(3)

(4)

(5)

请在空缺处填入合适内容,使其成为一个完整的直接插入排序算法

void InsertSort (SeqList R, int n)

{//对顺序表R做直接插入顺序

int i.j:

for(i=2, i<=n:i++)

if(i.key=有序区中所有的key,则不动

R[o]=R[i];//当前记录复制为哨兵

for(-i-1ro.key

(1)    ;//记录后移

(2)    ;//R[i]插入到正确位置

}

}

(1)

(2)

何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

一个深度为h的满k叉树有如下性质:第h层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号,问:

(1)各层的结点数目是多少?

(2)编号为i的结点的双亲结点(若存在)的编号是多少?

(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?

将下题所示的森林转换为一棵二叉树。

树中结点的最大层次称为树的( )

对题图所示的有向网,采用 Dijkstra算法,求以顶点0为源点到其余各顶点的最短路径,画出求解全过程。