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

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

给定一个整数数组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,则编号最大的分支结点的编号为( )

具有n个叶子结点的哈夫曼树共有( )个结点。

双向循环链表是一种对称结构,它既有向前链接的链又有向后链接的链,设指针p指向某一结点,则双向循环链表结构的对称性可描述为( )

将下三角矩阵A110110]的下三角部分逐行存储到起始地址为1000的内存单元中,已知每个元素占2个存储单元,则A[8][3]的地址是( )

对于一个具有n个元素的线性表,建立其单链表的时间复杂度为( )

n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为( )

常用的构造散列函数的方法有直接地址法、数字分析法、( )平方取中法和折叠法五种。

含有n个记录的文件进行直接选择排序,其平均时间复杂度为( )

为了充分利用数组空间,将队列的数组空间想象成一个首尾相接的圆环,这种方法克服了顺序队列的( )现象。

利用哈夫曼树求得的用于通信的二进制编码称为( )

用不带头结点的单链表表示队列时,在运行删除运算时【】

引入二叉线索树的目的是【】

在队列中存取数据的原则是【】

设长度为n的链队列用单循环链表表示,若只设尾指针,则出队操作的时间复杂度为【】

给定一个空栈,若10,20,23,13依次进栈,然后有两个数出栈,又有3个数进栈,第一次进栈的23现在【】

设有一个10阶的对称矩阵A,采用行优先压缩存储下三角元素,a11为第一个元素,其存储地址为1,每个元素占一个字节空间,则a的地址为【】

已知森林F={T1,T2,T3,T,T:},各棵树T(i=1,,3,4,5)中所含结点的个数分别为7,3,5,1,2,则与F对应的二叉树的右子树中的结点个数为【】

已知某二叉树的后序遍历序列是 dabec,中序遍历序列是 debac,它的前序遍历是【】

设一个图G(顶点编号1~5)的邻接矩阵如下:

则顶点1出发的DFS序列是

能够输入计算机并能被计算机处理的符号统称为【】

对线性表进行二分查找时,要求线性表必须【】

算法分析的两个主要方面是【】

下列说法正确的是【】

设一个栈的输入序列为A,B,C,D,则所得到的输出序列不可能是【】

将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,题根结点编号为1,则编号最大的分支结点的编号为【】