下面程序段的时间复杂度是【】

for(i=0;

i<2*n;i++)for(j=1j<3n;

j++)A[ij]=0;

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

(1)假设数组L[8]={3,0,5,1,6,4,2,7},写出执行函数调用f33(L,8)后的L

(2)写出上述函数调用过程中进行元素交换操作的总次数。

void f33(int R[],int n)

{int i,t,

for(i=0;

while(R[i]!=i)

{t=R[i][j]:

R[R[i]]-R[i]

R[i]=t;

}

(1)

(2)

已知二叉树的定义如下:

typedef struct node{

int data;

struct node *Ichild, rchild;

}* Bitptr;

编写递归算法求二叉树的高度。函数原型为:intf34(Bitptr)

下面的算法是将给定的关键字序列依次插入散列表中,请仔细阅读程序并把未完成的部分填上。

void HashInsert( HashTable T, NodeType new)

{ }//将新结点new插入散列表T[om-1]中

int (  (1)  ),sign;

sign=HashSearch(t,new.key,&pos);//在表T中查找new的插入位置

if(  (24)  )//找到一个开放的地址pos

t[pos]=  (3)  )//插入新结点new,插入成功

else  //插入失败

f(  (4)  )

printf("duplicate key!");//重复的关键字

else

//sign

Error("hash table overflow!");//满错误,终止程序执行

//HashInsert

（1）

（2）

（3）

（4）

下面的算法在中序线索树中找由指针p所指结点的后继并由指针指向该后继结点,试补充完整(线索树的结点有五个域data, Ichild, rchild,左、右标志域ltag、rtag,并规定标志0指向孩子,1指向线索 Bin ThrNode为结点类型)

BinThrNode inorder_ next(BinThrNode *p)

{

BinThrNode*q

(1)   ;

if (p->rtag-0)

while((2))q=(3)

return(q);

}

(1)

(2

(3)

简述队列的概念及其特点。

对题图所示的有向图,试利用 Dijkstra算法求出从源点1到其他各顶点的最短路径,并写出算法的动态执行情况。

?下面的排序算法的思想是:第一趟比较将最小的元素放在r[1]中,最大的元素放在r[n中,第二趟比较将次小的放在r[2]中,将次大的放在r[n-1中依次下去,直到待排序列为递增序列。(注:代表两个变量的数据交换)

void sort(intr[],intn)

{

int i=1,j,t,min, max;

while(i

{

min=max=i:

for (j=i+;j<=n-i+1:++j)

{

Ifr[j]

else if(r[j]>r[max])(2) ;

r[min] r[i];

(3) 

i++

}

}

(1)

(2)

(3)

求下列广义表的长度length()和深度 depth)

(1)a=((a),((b),c),d)

(2)B-(a,(a,b),d,e,((i,),k)

设二维数组Ax的每个元素占4个字节已知LOC(a)=100,A共占多少个字节?A的终端结点a45的起始地位为何?按行和按列优先存储时,a2的起始地址分别为何?

已知广义表LS=((a,x,y,z),(b,c)),运用head和tail函数取出原子c的运算是( )