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

写一算法将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。

给定一个整数数组bON-1],b中连续的相等元素构成的子序列称为平台,平台的长度是连续相等元素的个数,下面算法求出b中最长平台的长度,请将算法补充完整。

voidPlatform(intb[]intN)

{//求具有N个元素的整型数组b中最长平台的长度

intlen-1st=0i=0;j-0;

while(i

{

while(i

if(i-j+1>len)

(2);(3);}//局部最长平台及最长平台起始下标

i++;j=i

printf(“最长平台长度%d,在b数组中起始下标为%d",len,s)

}

(1)

(2)

(3)

已知线性表(a1,a2,a3,,an)按顺序存放在数组a中,每个元素均为整数,下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如,有7个整数的原始序列为(x,x,-x,-x,x,x,-x),变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)请在程序中划线处填入合适的内容,使其成为完整的算法。

f33(int a[], int n)

{  intk,m,temp:

m=  (1)  ;

while(a[m]<0&&m

m=  (2)  

k=m;

while(k

{ while(a[k]>=.&k

k=  (3)  

if(k

{temp=a[k];

a[k]=a[m];

a[m]=  (4)  

m=  (5)  ;

}

(1)

(2)

(3)

(4)

(5)

阅读下列对正整数关键字序列L操作的算法,并回答问题:

(1)设L=(28,19,27,49,56,12,10,25,0,50),写出33(L,4)的返回值

(2)简述函数f33的功能。

int Partition (SeqList L, int low, inthigh);

∥对L[low... high]做划分,返回基准记录的位置,并使左部的关键字

∥都小于或等于基准记录的关键字,右部的关键宇都大于基准记录的关键字

int f33(SeqList L, int k)

int low, high, pivotpos;

low=1;

high=L. length;

if (khigh)

return-1:

do

{

pivotpos=Partition(&l,low,high);∥调用快速排序的划分算法

if (pivotpos

low=pivotpos+1;

else if (pivotpos>k)

high=pivotpos-1;

}while (pivotpos!=k);

return L. data [pivotpos]

}

(1)

(2)

某类物品的编号由一个大写英文字母及2位数字(9)组成,形如E32运用基数排序对下列物品编号序列进行按字典序列的排序,写出每一趟(分配和收集)后的结果E13,A37,F43,B32,B47,E12,F37,B12第一趟第二趟第三趟:

假设某个不设头指针的无头结点单向循环链表的长度大于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)

对于给定的一组关键字(26,18,60,14,745,13,32),写出执行堆排序算法的每一趟排序结果。

假设高度为h的二叉树上只有度为0和度为2的结点,问此类二叉树中的结点数可能达到的最大值和最小值各为多少?并说明是什么样的二叉树?

画出以顶点V1为初始源点进行DFS和BFS遍历所生成的森林。

完全二叉树中,结点个数为n,则编号最大的分支结点的编号为( )