数据结构复习题汇总

四. 算法设计与分析 ：

1.请设计求n的阶乘的递归算法与非递归算法，其中非递归算法请用栈或队列实现；

参考答案：

long Factorial1 ( long n ) { if ( n == 0 ) return 1;

else return n * Factorial1 (n-1); }

long Factorial2 (long n){ SeqStacksqs; long fac=1; if (n>0) {

for(int i=n; i>0; i--) sqs.push(i);

while(sqs.Empty()==0) fac=fac*sqs.pop(); }

return fac; }

2.已知二叉树用二叉链表存储，试编写一函数实现计算该树的高度。请定义必要的数据结构。

template struct BiNode {

DataType data;

BiNode *lchild, *rchild; };

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*root) {

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;};