数据结构自考2019年4月真题及答案解析

已知二叉树的存储结构类型定义如下:

typedef struct node{

int data;

}BinNode:

uct node* Ichild, *rchild;

typedef BinNode *BinTree;

编写递归算法,对于给定的一棵二叉树T,计算并返回所有结点data域的值之和函数原型为:intf34(BinTree);。例如,对于题34图所示的二叉树T,f34(T)应返回24

设顺序表的存储类型定义如下

typedef int KeyType;

typedef struct(

KeyType key;

)RecType;

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

int f33(ReeType R[],int i,int j)

{

RecType x=];

while(i

while(=x. key)j--;

if(i

RCi]. key =Rj]. key; i++;

}

while(i

if(i

]. key=R[i]. key; j--;

}

}

RCi]. key x. key;

return i;

}

(1)设 RecType[]={52,14,256,-9,-38,30,128258,64},给出执行f33(R,0,8)后的结果。

(2)给出该算法的功能。

二叉树的存储结构类型定义如下

typedef int DataType;

typedef struct node

{DataType data;//data是数据域

struct nodelchild, rchild;//分别指向左右孩子

)BinTNode;

typedef BinTNode *BinTree;

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

int height(BinTree T)

{

int lhigh=0, rhigh=;

if(T==NULL) return 0;

else{

Ihigh=height(T->);

rhigh=height(T->rchild);

if(lhigh>rhigh) return Ihigh+1:

else return rhigh+;

}

}

void f31(BinTree T)

int leftHigh=0, rightHigh=;

BinTree temp;

if(T==NULL)return;

else{

if(height(T->Ichild)rchild))

temp=T->Ichild;

T->Ichild=T->rchild;

T->rchild=temp;

}

31(T->lchild);

f31(T->rchild);

return;

}

(1)设二叉树T如题图所示,画出执行f31(T)后得到的二叉树T1。

(2)给出函数f31()的功能。

?设顺序表的存储类型定义如下:

define ListSize 100

typedef int KeyType;

typedef struet(

KeyType key;

}NodeType;

typedef NodeType SeqList[ List Size];

函数f32()的功能是,基于二分查找在长度为n的有序表中插入一个关键字x,并保持R

的有序性。请在空白处填上适当语句使算法正确。

void f32(SeqList R, KeyType x, int n)

{

int low =0, high=n-1, mid, inspace, i,find=0;

while(low<=high&&! find){

mid=(low+high)/2:

if(x

else if(x>R[mid]. key) low =mid+1;

else find=1;

}

if(find)

inspace=  ②   

else

inspace=low;

for(i=n; ( ③    );i--)

R[i+1]-R[];

R[inspace]. key=x;

}

设有关键字序列(65,23,31,26,7,91,53,5,72,52),散列函数为H(key)=key%11,将关键字依次放入表长为11的散列表H中,采用线性探测法处理冲突。请回答下列问题:

(1)画出构造的散列表,并给出查找每个关键字的探查次数。

(2)求散列表的平均查找长度ASL。

顺序表类型定义如下:

define ListSize 100

typedef struct{

int data[ListSize];

int length;

}SeqList;

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

void mysum(SeqList SL1, SeqList SL2)

{   intminlength,k=0;

minlength=SL2->length;

for(k=0; k

if(SL1->data[k]data[k]) SL1->data[k]+=SL2->data[k];

else SL2->data[k]+=SL1->data[k];

return;

}

void f30(SeqList SL1, SeqList SL2)

{if(sl->length>sl2->length)mysum(sl,s2);

else mysum(SL2,SL1);

return;

}

(1)若SL1->data中的数据为(52,14,256,-9-38,30,128,257,64),SL2->data中的数据为(32,14,-63,15,29,51,16,8),则执行算法f0(&sl,&sl2)后s1->data和sL2->data中的数据各是什么?

(2)该算法的功能是什么?

已知有向带权图G如题图所示。请回答下列问题:

(1)给出图G的邻接矩阵。

(2)求出G中从源点A到其余各顶点的最短路径。要求根据迪杰斯特拉算法的求解过程依次给出各条路径,包括路径上经过的顶点及其长度。

已知二叉树T的前序遍历序列是A,B,C,D,,L,,O,N,中序遍历序列是C,B,,,AM,O,L,N,请画出T。

索引顺序查找是一种将顺序查找和二分查找思想结合在一起的查找方法,又称为( )

设稀疏矩阵M如下所示。矩阵的行列下标均从1开始。请画出M按行优先存储的三元组表。

5阶B树T中,除根结点之外每个结点中所含关键字个数最少是( )

要使n个记录的关键字序列k1,k2,成为小根堆,关键字之间必须满足的关系是( )

设连通带权图G中有n个顶点,使用普里姆算法构造G的最小生成树T,T中含有的边数是( )

利用二叉树中的空指针域,使之指向结点在某种遍历次序下的前趋或后继结点,此时域中的内容称为( )

若用n个带权字符构造哈夫曼树T,则T中结点的总数是( )

广义表((a,b),(c,d),e)的表尾是( )。

若广义表L的深度是∞,则L一定是( )

用S表示入栈操作,又表示出栈操作,若元素人栈顺序为1234,为了得到1342的出栈顺序,相应的SX操作串为( )

将下列数据依次插入到初始为空的二叉排序树中,能得到高度最小的二叉排序树的序列是【】

线性表的存储方式中,能够随机存取表中任一元素的存储结构是( )

下列选项中,每一趟都能选出一个元素放在其最终位置上,且不稳定的排序算法是【】

对有序表(1,9,12,41,2,7,82,5,100)采用二分查找方法查找值82,查找过程中关键字的比较次数是【】

已知数据序列(8,9,10,4,5,6,20,1,2)是某种排序算法第一趟排序后得到的结果,则该算法可能是【】

对题图所示的有向图进行拓扑排序。下列选项中能够得到的拓扑序列是【】

若对题图所示的无向图进行深度优先搜索遍历则下列选项中正确的遍历序列是【】

已知完全二叉树T的第4层有5个叶结点,则T的结点个数最多是【】

在一棵非空二叉树的后序遍历序列中,所有列在根结点前面的是【】

设n阶方阵M是对称矩阵,采用压缩存储方式将M中的元素保存在一维数组B中,则下列选项中,正确的是【】

设二维数组M有3行4列,按行优先的方式存储,每个元素占6个存储单元。第1个元素的存储地址为100,则M[2][2]的存储地址为【】

使用一个大小为6的数组保存循环队列Q。若从Q中出队两个元素,并入队一个元素,此时队尾rear和队头 front的值分别为和4。则在执行这三个操作之前rear和 front的值分别是【】

设栈S的输入序列为1,2,3,4,5,则下列选项中不可能是S的输出序列的是【】

下列选项中,不宜通过栈求解的问题是【】

线性表是一种由n个数据元素组成的数据结构,n的取值是【】                            

在一个单链表中,已知q所指结点是p所指结点的后继结点,若在p和q之间插入s所指结点,则正确的操作是【】