长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_________。

已知二叉树采用二叉链表存储，其结点结构定义如下：

typedef struct Node{

ElmType data;

struct Node *lchild，*rchild;

}*BiTree;

请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。

下面程序实现二分查找算法。

Typedef struct{

KeyType key;

InfoType otherinfo;

}SeqList[N+1];

int BinSearch(SeqList R, int n，KeyType K)

{ int low=1，high=n;

while( (1) ){

mid=(1ow+high)/2;

if( (2) )return mid;

if(R[mid].key>K)

high=mid-1;

else

(3) ;

}

return O;

} //BinSearch

请在空白处填写适当内容，使该程序功能完整。

数组A[]中存储有n个整数，请阅读下列程序。

void f32(intA[]，int n){

inti，j，k，x;

k=n-l;

  while(k>0){

i=k; k=0;

for(j=O;j

 if(A[j]>A[j+1]){

  x=A[j];

 A[j]=A[j+l];

 A[j+1]=x;

 k=j;

   } //end of if

 }//end of while

return;

}

请回答下列问题：

(1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么?

(2)说明该算法的功能。

已知字符串处理函数f31程序如下。

int f31(char*strl，char*str2)

{ while(*strl==*str2&&(*strl!=’\0’)){

strl++;

str2++;

}

return(*strl-*str2 ? 1∶0);

}

请回答下列问题：

(1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是f31(”abcde”，”abcde”)，则函数的返回值是什么?

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

已知下列程序，Ls指向带头结点的单链表。

Typedefstruct node {

      DataType data;

      struct node * next;

} * LinkList;

     void f30( LinkList Ls )

 { LinkList p, q;

    q = Ls->next;

        if ( q && q->next )

      {Ls->next = q->next;

          p=qwhile ( p->next )

        p = p->next;

        p->next = q;

        q->next = NULL;

   }

}

请回答下列问题：

(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。

(2)请简述算法的功能。

已知一棵二叉排序树如图所示。请回答下列问题：

(1)画出插入元素23后的树结构;

(2)请画出在原图中删除元素57后的树结构。

已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。

已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。

请回答下列问题：

(1)请画出对应的图G。

(2)画出图G的邻接表存储结构。

假设二叉树的RNL遍历算法定义如下：若二叉树非空，则依次执行如下操作：

(1)遍历右子树;

(2)访问根节点;

(3)遍历左子树。

已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。

高度为3的3阶B-树最少的关键字总数是_________。