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

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

阅读下列函数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},请构造一棵哈夫曼树,并计算出它的带权路径长度

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