填空题(1997年中国科学技术大学)

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:

4 = 4

4 = 3 + 1

4 = 2 + 2

4 = 2 + 1 + 1 

4 = 1 + 1 + 1 + 1

test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。

test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。

算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。

#define MAXN 100
int a[MAXN];
test(int n,int k){
    int i,j;
    for (j=__________;j>=1;j--){
        a[k]=j; 
        if (__________){
            printf ( "%d = %d" , a[0],a[l]);
            for (i = 2 ; i < = k ; i + + )
                printf ( " + % d " , a[i]);
            printf ( "  n " );
        }else test(__________,k + l );
    }
}

答案解析

(1)n (2) j==n (3) n-j

讨论

写出和下列递归过程等价的非递归过程。void test(int sum){     int a;     scanf("%d",&a);     if(a==0) sum=1;     else{         test(sum);         sum=sum*a;     }     pritf("%d",sum); }

一般情况下,将递归转换成等价的非递归算法应该设置【】

用数组 Q(其下标在 0 . . n-1 中,共有n个元素)表示一个环形队列, f 为当前队头元素的前一位置, r 为队尾元素的位置。假定队列中元素个数总小于 n ,求队列中元素个数的公式是__________。

设栈 S 和队列 Q 的初始状态为空,元素 a 、 b 、 c 、 d 、e、 f 依次通过栈 S ,一个元素出栈后即进入队列 Q 。若这 6 个元素出队列的顺序是 b 、 d 、 c 、f、 e 、 a ,则栈 S 的容量至少应该是__________。

顺序队列一般应该组织成为环状队列的形式,而且一般队列头或尾其中之一应该特殊处理。例如,队列为 listarray [ 0 ... n-1] ,队列头指针为front ,队列尾指针为 rear ,则 listarray[rear]表示下一个可以插入队列的位置。请解释其原因。

设一单项链表的头指针为head,链表的记录中包含整数类型的key域,试设计算法,将此链表的记录按照key递增的顺序进行就地排序。

中缀表达式 A-(B + c/d) * E的后缀形式是【 】

用数组表示的循环队列的队首和队尾位置分别为1和 max_size,试给出判断队列为空和为满的边界条件。

若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3。当从队列中删除一个元素, 再加入两个元素后, rear和加front的值分别为多少?

在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印。该缓冲区应念是一个【 】结构。

对于前序遍历和中序遍历结果相同的二叉树为__________;对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树

在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与【 】量级相当。

已知序列17,31,13,11,20,35,25,8,4,11,24,40,27,请画出该序列的二叉排序树,并分别给出下列操作后的二叉排序树:① 插入数据9;② 删除结点17;③ 再删除结点13。

在n个记录的有序顺序表中进行折半查找,最大的比较次数是__________。

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){     int i,j;     for (j=__________;j>=1;j--){         a[k]=j;          if (__________){             printf ( "%d = %d" , a[0],a[l]);             for (i = 2 ; i < = k ; i + + )                 printf ( " + % d " , a[i]);             printf ( "  n " );         }else test(__________,k + l );     } }

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){     int i,j;     for (j=__________;j>=1;j--){         a[k]=j;          if (__________){             printf ( "%d = %d" , a[0],a[l]);             for (i = 2 ; i < = k ; i + + )                 printf ( " + % d " , a[i]);             printf ( "  n " );         }else test(__________,k + l );     } }

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){     int i,j;     for (j=__________;j>=1;j--){         a[k]=j;          if (__________){             printf ( "%d = %d" , a[0],a[l]);             for (i = 2 ; i < = k ; i + + )                 printf ( " + % d " , a[i]);             printf ( "  n " );         }else test(__________,k + l );     } }

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){     int i,j;     for (j=__________;j>=1;j--){         a[k]=j;          if (__________){             printf ( "%d = %d" , a[0],a[l]);             for (i = 2 ; i < = k ; i + + )                 printf ( " + % d " , a[i]);             printf ( "  n " );         }else test(__________,k + l );     } }

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){     int i,j;     for (j=__________;j>=1;j--){         a[k]=j;          if (__________){             printf ( "%d = %d" , a[0],a[l]);             for (i = 2 ; i < = k ; i + + )                 printf ( " + % d " , a[i]);             printf ( "  n " );         }else test(__________,k + l );     } }

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){     int i,j;     for (j=__________;j>=1;j--){         a[k]=j;          if (__________){             printf ( "%d = %d" , a[0],a[l]);             for (i = 2 ; i < = k ; i + + )                 printf ( " + % d " , a[i]);             printf ( "  n " );         }else test(__________,k + l );     } }