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

以二叉链表为存储结构,分别写出求二叉树高度及宽度的算法,所谓宽度是指二叉树的各层上,具有结点数最多的那一层上的结点总数。

阅读下列函数algo,并回答问题:

(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q

(2)简述算法algo的功能

void algo(Queue *Q)

{

Stack S:

InitStack(&S),

while( !QueueEmpty())

Push(&, DeQueue(Q));

while(!StackEmpty(&))

EnQueue(Q, Pop(&S));

}

(1)

(2)

假设某个不设头指针的无头结点单向循环链表的长度大于1,s为指向链表中某个结点的指针。算法f30的功能是,删除并返回链表中指针s所指结点的前趋。请在空缺处填入合适的内容,使其成为完整的算法。

typedefstructnode{

DataTypedata;

structnode*next;

}LinkList;

DataTypef30(LinkLists){

LinkListpre,p:

DataTypee;

Pre=s;

p=s->next;

while((1))

pre=P:

(2)

pre>next=(3)

e=p->data;

free(p);

returne;

}

(1)

(2)

(3)

请阅读下列算法,回答问题。

voidsort(intr[],intn)

{//对r[1n]中的关键字进行递增排序

inti,j;

for(i-2;i<=n:i++)

{

x=r[i];r[o]=x:=i-1;

while(x<])

{

+1]=],j=j-1;

}

r+1]=x

}

}

(1)这是什么类型的排序算法,该排序算法稳定吗?

(2)设置r[]的作用是什么?若将while语句中判断条件改为x<=r,该算法还是否稳

定,是否能完成正常排序工作?

(1)

(2)

数据结检全真发

已知二维数组Amn按“行优先顺序”存储在内存中,假设每个元素占d个存储单元,第一个元素的存储地址表示为LOC(AO]]),写出计算数组A的任一个元素A[i的存储地址公式。

下面是求二叉树高度的递归算法,试补充完整。说明:二叉树的两指针域为 Ichild与 rchild,算法中p为二叉树的根,lh和rh分别为以p为根的二叉树的左子树和右子树的高,hi为以p为根的二叉树的高,hi最后返回

height(p)

{if (p)

if(p->Ichild=-NULL) Ih=;

else Ih=(1)

if(p->rchild==NULL)rh-0;

else rh= height(p->rchild);

if(>rh) hi=lh+1;else hi=(2)

}

else hi=(3);

return hi;

}

(1)

(2)

(3)

求下列广义表的运算结果:

(1)head(tail((a,b),c(,d)).

(2)tail(head((a,b),(c,d))).

在循环队列的顺序存储结构中,分别写出队插入元素)出队(删除元素)时修改队尾、队头指针的操作语句。

已知关键字序列R={11,4,3,2,17,3019},请构造一棵哈夫曼树,并计算出它的带权路径长度

归并排序算法需要辅助空间为( )

若查找过程中需要访问外存,则称之为( )

采用邻接表表示时,图的广度优先搜索遍历的时间复杂度为( )

从循环队列中删除一个元素时,其操作是先( ),后( )

度数不为零的结点称为( )

( )是一种介于顺序查找和二分查找之间的查找方法。

具有( )条边的无向图称为无向完全图。

若一条简单路径上的起点和终点为同一顶点,则称该路径为( )

广义表A=(a,b,(c,d),(e,(f,g))),head(tail(head(tail(tail()))))的值为( )

按照二叉树的定义,具有3个结点的二叉树有【】种

取出广义表A=((x,y,z),(a,b,c,d))中原子b的函数是( )

由带权为9,2,5,7的4个叶子结点构成的一棵哈夫曼树的带权路径长度是【】

下面对非空线性表的逻辑特征描述不正确的是【】

设有一组关键字(19,14,23,1,6,20,4,27,511,10,9),用散列函数H(key)=key%13构造散列表,用拉链法解决冲突,散列地址为1的链中记录个数为【】

下列有关树的叙述中,正确的是【】

三元组表是稀疏矩阵的一种【】

以下属于逻辑结构的是【】

一棵完全二叉树上有1001个结点,其中叶子结点的个数是【】

查找运算主要是对关键字的【】

用线性探查法查找散列表,可能要探查多个散列地址。这些位置上的键值【】

下列广义表是线性表的是【】

稀疏矩阵采用顺序存储方式压缩存储后,必会失去【】功能。

用单链表表示的链队中,队尾指针在链表的【】位置。

一棵二叉树的中序序列为ABDCEFG,后序序列为 BDCAFGE,则其左子树中的结点个数为【】

设有一个5阶上三角矩阵A[1.5,1..5],现将其上三角中的元素按列优先顺序存放在一维数组B1..15]中。已知B[1]的地址为100,每个元素占用2个存储单元,则A[3,4]的地址为【】