下列排序方法中,最好与最坏时间复杂度不相同的排序方法是【】

尾插法建表是将新结点插入到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。试写出尾插法建表的算法。函数头为:LinkListGreateListR(void)

已知稀疏矩阵采用带行表的三元组表表示,其形式说明如下:

define MaxRow 100 //稀疏矩阵的最大行数

typedef struct

int i,j,v; //行号、列号、元素值

}TriTupleNode;

typedef struct{

TriTupleNode data[MaxSize];

int RowTab[MaxRow+1];//行表

int m,n,t: //矩阵的行数、列数和非零元素个数

}RTriTupleTable;

下列算法f31的功能是:以行优先的顺序输入稀疏矩阵的非零元素(行号、列号、元素值),

建立稀疏矩阵的带行表的三元组表存储结构请在空缺处填合适内容,使其成为一个完

整的算法。(注:矩阵的行、列下标均从1起计)

void f31(RTriTupleTable *R)

{int i,k;

scanf("%d %d %d", & R->m, R->n, &R->t);

R→RowTab[1]=0;

k=1;//k指示当前输人的非零元素的行号

for(i=0:(1)i++)

{scanf("% %d %d", (2) , (3) ,&R->data[i]. v);

while(kdata[i]. i)

{ (4)

R->RowTab[k]=i

}

}

}

(1)

(2)

(3)

(4)

设输入为整数数组a[n],a[n],其中≤a[i

void demo(int a[], int b], int c[], int k)

{

int i,

for(i=0;i

for(j=0:j

for(i=: i

for(j=n-1>=0--)

{

b[c[a[j]]-1]=a[j]:

c[a[j]]—

}

(1)当标号①行的循环执行完后,c[i(0≤i

(2)当标号②行的循环执行完后,c[i(≤i

(3)算法执行后,b数组的内容有何特点?

(4)当k=0(n)时,算法的时间复杂度是多少?

(1)

(2)

(3)

(4)

下列程序段search(a,n,k)是在数组a的前n(n>=1个元素中找出第k(1的值。这里假设数组a中各元素的值都不相同,在空缺处填写相应的语句

#define MAXN 100

int a[MAXN],n, k;

int search(int],int n, int k)

(int low, high,i,j,m,t;

k--,low=0;high=n-11

do {i-low;j-high ;t-aClow],

do{while(i

if(i<) a[i++]=];

while(i=[]) i++:

if(i

}while(i

a[i]-t:

if (1)

if(i

}while( (4) );

return(a[k]);

}

(1)

(2)

(3)

(4)

下面是二分查找算法的非递归实现方法,在空缺处填入合适内容,使其成为一个完整的算法。

int BinSearch(SeqList R, KeyType k, int n)

{int low=, mid, high=n;//初始化上下界

while(low<=high){

mid=(low+high)/2;

if(R[mid]. key==k)

return mid,//查找成功,返回其下标

if(R[mid]. key>k)

(1) ;//修改上界

Else (2) ;//修改下界

}

Return0;//查找失败,返回0值

}

(1)

(2)

画出题图所示二叉树的中序线索链表的存储表示。

已知3阶B树如题图所示。

(1)画出将关键字88插入之后的B树。

(2)画出将关键字47和66依次插入之后的B树。

设散列表长度为11,散列函数h(x)=x%1,给定的关键字序列为:1,12,13,34,38,33,27,22,试画出用拉链法解决冲突时所构造的散列表。

假设二叉树包含的结点为1,3,7,2,12

(1)画出两棵高度最大的二叉树

(2)画出两棵完全二叉树,要求每个双亲结点的值大于其孩子结点的值。

在一般情况下用直接插入排序、直接选择排序和冒泡排序的过程中,所需移动记录次数最少的是( )