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

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

下面的程序将数列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为源点到其余各顶点的最短路径,画出求解全过程。

在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第7个记录60插人到有序区时为寻找插位置需比较( )次。

在具有n个单元且采用顺序存储的循环队列中,队满时共有( )个元素

树是一种常用于( )组织的B树的变形树。

快速排序在系统内部需要一个( )来实现递归。

广义表(())的表头是( )表尾是

已知二维数组A[m]n],采用行序为主方式存储,每个元素占k个单元,并且第一个元素的存储地址为LOC(A[O]]),则A[i]的地址是( )

堆排序是一种( )选择排序

在完全二叉树中除最下面的一层外,各层结点都达最大值每一层上结点个数恰好是上一层结点个数的( )倍。

链式存储的栈,其链头即为( )

n个顶点的强连通图至少有【】条边。

下列排序方法中最稳定的是【】

判断一个顺序栈st(最多元素为 StackSize)为栈满的条件表达式是【】

对特殊矩阵采用压缩存储的目的主要是为

已知一个顺序存储的线性表,设每个结点需占个存储单元,若第一个结点的地址为d,则第个结点的地址为【】

在关键字序列(12,23,34,45,56,67,78,89,1)中二分查找关键字为45、89和12的结点时,所需进行的比较次数分别为【】

二叉树中第6层上的结点个数最多为【】

图的广度优先遍历类似树的【】

在题图中,从顶点1出发进行广度优先遍历可得到的序列是【】

若无向图G(V,E)中含7个顶点,则保证图G在任何情况下都是连通的,需要的边数最少是【】

已知广义表的表头为a,表尾为(b,c,d),则此广义表为【】

广义表L=(a,(b,c)),进行tail(L)操作后的结果为【】

设栈S和队列Q的初始状态为空,元素el,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,el,则栈S的容量至少应该是【】

已知散列表的存储空间为T[o18],散列函数H(key)=key%17,并用二次探查法处理冲突。散列表中已插人下列关键字:T[5]=39,[6]=57和T[7]=7,则下一个关键字23插入的位置是【】

数据序列{8,9,10,4,5,6,20,1,2}只能是【】的两趟排序后的结果。