发布时间 : 星期四 文章数据结构复习题汇总更新完毕开始阅读63b051366d175f0e7cd184254b35eefdc8d31534
四. 算法设计与分析 :
1.请设计求n的阶乘的递归算法与非递归算法,其中非递归算法请用栈或队列实现;
参考答案:
long Factorial1 ( long n ) { if ( n == 0 ) return 1;
else return n * Factorial1 (n-1); }
long Factorial2 (long n){ SeqStack
for(int i=n; i>0; i--) sqs.push(i);
while(sqs.Empty()==0) fac=fac*sqs.pop(); }
return fac; }
2.已知二叉树用二叉链表存储,试编写一函数实现计算该树的高度。请定义必要的数据结构。
template
DataType data;
BiNode
int Depth(BiNode *root) {
if (root == NULL) return 0; else {
hl= Depth(root->lchild); hr= Depth(root ->rchild); return max(hl, hr)+1;
11. 现有一棵二叉查找(排序)树(Binary Search Tree)BST,以二叉链表形式存储,进行中序遍历可得到从小到大排列的有序序列。
1)请编写一函数,对该二叉查找树进行变换,使得对新的二叉树进行中序遍历可得到从大到小排列的有序序列。 template
void Exchange(BiNode
if(root!=NULL){
Exchange(root->lchild); Exchange(root->rchild);
root->lchild<- -> root->rchild; } }
2)请用中文文字直接描述在新的二叉树上找最大元素的方法。 有关的数据结构已描述如下:
struct Binary_node { // 二叉树结点 int data;
Binary_node *left; Binary_node *right;};