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

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

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按行优先存储的三元组表。