数据结构与算法-考研试题(清华大学 1996年非递归)

程序设计（1996年清华大学）

写出和下列递归过程等价的非递归过程。

void test(int sum){
    int a;
    scanf("%d",&a);
    if(a==0) sum=1;
    else{
        test(sum);
        sum=sum*a;
    }
    pritf("%d",sum);
}

答案解析

#define STACKSIZE 100 typedef struct { DataType items[STACKSIZE]; int top; }SqStack; SqStack stack; int sum=1; void test(){ InitStack(stack); scanf("%d",&a); while(a!=0){ &n...

查看完整答案

讨论

数据结构与算法

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

用数组 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的值分别为多少？

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

若用单链表来表示队列则应该选用【】

递归

递归函数最终会结束，那么这个函数一定【】

在单 CPU 计算机系统中，完成相同功能的递归程序比非递归程序【】

对于正整数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个【】的有限序列。

如果待排序序列中两个数据元素具有相同的值，在排序前后它们的位置发生颠倒，则称该排序算法是不稳定的，【】就是不稳定的排序算法。

快速排序的最大递归深度是__________，最小递归深度是__________。

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序序列，用【】方法最快

回答问题并写出推导过程：对50个整数进行快速排序需进行关键字间比较次数可能达到的最大值和最小值各为多少？

对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

非递归

表示一个有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？

有 n 个顶点的有向强连通图最多有多少条边？最少有多少条边？

设无向图的顶点个数为n，则该无向图最多有【】条边。

在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为li，那么查找失败到达失败结点时所做的数据比较次数是多少？

设有12个数据{25，40，33，47，12，66，72，87，94，22，5，58}，它们存储在散列表中，利用双散列解决冲突，要求插入新数据的平均查找次数不超过3次。① 该散列表的大小m应该设计多大？② 试为该散列表设计相应的散列函数（用除留余数法）并计算寻找下一个“空位”时向前跨步步长的再散列函数。③ 顺次将各个数据散列到表中。④ 计算查找成功的平均查找次数。

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

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

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

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

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