[填空题]【说明】 为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1.n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R[]中的元素互不相同)。 【算法】 1．变量声明 X：DataType i，j，low，high，mid，R[0..n]) 2．每循环一次插入一个R[i] 循环：i以1为步长，从2到n，反复执行 ①准备 X＜-R[i]； (1) ；high＜-i-1; ②找插入位置 循环：当 (2) 时，反复执行 (3) ; 若X.key＜R[mid].key 则high＜-mid-1 否则 (4) ③后移 循环：j以-1为步长，从 (5) ，反复执行 R[j+1]＜-R[j] ④插入 R[low]＜-X 3．算法结束

[简答题]已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。
关键字自小到大有序(key₁＜key₂＜……＜key_n)；

[填空题]【说明2.1】 以下C语言函数用二分插入法实现对整型数组a中n个数的排序功能。 【函数2.1】 void fun1 (int a[]) { int i,j,k,r,x,m; for(i=2;i＜=n;i++) { (1) ; k=1;r=i-1; while(k＜=r) { m=(k+r)/2; if(x＜a[m])r=m-1; else (2) ; } for(j=i-1;j＞=k;j--) a[j+l]=a[j]; (3) ; } } 【说明2.2】 以下程序可以把从键盘上输入的十进制数(long型)以二～十六进制形式输出。 【程序2.2】 #include＜stdio.h＞ main（　） { charb[16]={’0’,’l’,’2’,’3 ,4,’5’,’6’,’7’,’8’,’9’,’A’,’B’,’C’,’D’,’E’,’F’}; int c[64],d,i=0,base; long n; printf("enter a number:/n"); scanf("%1d",&n); printf("enter new basc:/n"); scanf("%d", &base); do { c[i]= (4) ; i++; n=n/base; } while(n!=0); printf("transmite new base:/n"); for(--i;i＞=0;--i) { d=c[i]; printf("%c", (5) ); } }

[填空题]若采用直接插入法对字母序列(W，S，E，L，X，G，I)进行排序，使字母按升序排列，那 么第一次排序的结果为 【1】 。

[填空题]若采用直接插入法对字母序列(W，S，E，L，X，G，I)进行排序，使字母按升序排列，那么第一次排序的结果为______。

[填空题][说明] 求树的宽度，所谓宽度是指在二叉树的各层上，具有结点数最多的那一层的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 [函数] int Width ( BinTree *T { int front=-1, rear=-1; /*队列初始化*/ int flag=0, count=0, p; /*p用于指向树中层的最右边的结点, flag 记录层中结点数的最大值*/ if ( T!=Null) { rear++; (1) ; flag=1; p=rear; } while ( (2) ) { front++; T=q [front]]; if (T->lchild!=Null ) { roar+-+; (3) ; count++; } if ( T-＞rchild!=Null ) { rear++; q[rear]=T-＞rchild; (4) ; } if (front==p ) // 当前层已遍历完毕 { if( (5) ) flag=count; count=0; p=rear, //p 指向下一层最右边的结点 } } return ( flag ); }

[填空题][说明]
求树的宽度，所谓宽度是指在二叉树的各层上，具有结点数最多的那一层的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
[函数]
int Width ( BinTree *T

int front=-1, rear=-1; /*队列初始化*/
int flag=0, count=0, p; /*p用于指向树中层的最右边的结点, flag 记录层中结点数的最大值*/
if ( T!=Null)

rear++;
(1) ;
flag=1;
p=rear;

while ( (2) )

front++;
T=q [front]];
if (T->lchild!=Null )

roar+-+;
(3) ;
count++;

if ( T-＞rchild!=Null )

rear++; q[rear]=T-＞rchild;
(4) ;

if (front==p ) // 当前层已遍历完毕

if( (5) )
flag=count;
count=0;
p=rear, //p 指向下一层最右边的结点


return ( flag );