Question

数据结构与算法试题，高分，求答案啊

3已知一株非空二元树，其先根与中根遍历的结果为：
先根：ABCDEFGHI
中根：CBEDAGFHI
根据先根和中根遍历结果，将此二元树构造出来。
4分析下列程序的运行时间：
A） void mystery (int n)
{int I,j,k;
for (I=1;I<n;I++)
for (j=I+1;j<=n;j++)
for (k=1;k<=j;k++)
{some statement requiring O(1) time;}
}
B) void podd (int n)
{int I,j,x,y;
for (I=1;I<=n;I++)
if (odd (i) )
{for j=I;j<=n;j++}
x=x+1;
for (j=1;j<=I;j++)
y=y+1;
}
}
5已知数学表达式是（3+b）sin(x+5)－a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）
三 实现下列算法
1 在指针实现的线性表L中，实现在线性表L中删除关键字为x的结点。
2 在线索二元树中，由结点P求其先根顺序的后继。
3 在二元查找树F中，实现插入记录R。
四 对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。
五 设要分类的数据存放在数组A
3 1 4 1 5 9 2 6 5 3
中，要进行堆分类，首先得为其建立一个初始堆，试画出初始建设堆过程中，二元树的变化和数组A的变化。
tank1734684@163.com请注明账号

Answer 1

3 已知一株非空二元树，其先根与中根遍历的结果为：
先根：ABCDEFGHI  
中跟：CBEDAGFHI    

将此二元树构造出来。

答：                  A

                       /     \

                    B        F

                  /   \      /   \  

               C     D   G    H

                     /                \

                    I                  E

 

 

4.分析下列程序的运行时间：

A)      void  mystery(int n)

{int  i, j, k;

 for(i=1; i<n; i++)

 for(j=i+1; j<=n; j++)

 for(k=1; k<=j; k++)

{some  statement  requiring  O(1)  time;}

        }

我的答案是 n3 不过不是很确定

 

B）void  podd(int  n)

   {int  I, j, x, y;

    for(I=1; I<=n; I++)

       if( odd(I ) )

          {for(j=I; j<=n; j++)

                x=x+1;

       for(j=1; j<=I; j++)

              y=y+1;

       }

    }

n2 也不是很确定 

 

5 已知数学表达式是(3+b)sin(x+5)—a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。

表达式对应的二叉树为

 

 

所以对应的前缀为：-*+3bsin+x5/a*xx

后缀为：3b+x5+sin*axx*/-

 

 

三 实现下列算法

在指针实现的线性表L中，实现在线性表L中删除关键字为x的结点。
答：

int visited[n];  

void dfs(Graph g, int i)

{edgeNode *t;

printf(“%4d”,i); 

visited[i]=1;     

t=g[i];          

while(t!=NULL) {

if (visited[t->vno]= =0)  

dfs(g,t->vno);

t=t->next;

}

}

 

 

在线索二元树中，由结点P求其中根顺序的后继。

答：

typedef enum {lLINK ,THREAD} PointerTag ;  // LINK==0; 指针，

THREAD==1；线索 

typedef struct BinThrNode { 

TElemType data；  

struct BinThrNode *lchilid， *rchild；

 PointerTag ltag， rtag；

}  BinThrNode,* BinThrTree; 

中序遍历线索二叉树

p所指结点前驱的求法： 

当p->ltag==THREAD时，前驱为p->lchild； 

当p->ltag==LINK时，前驱为p->lchild的最右下方结点。

 

 

在二元查找树F中，实现插入记录R。

答：

Void INSERT(records R, BST &F)

{if(F= =NULL)

  {F=new celltype;

F-> data=R;

 F->lchild=NULL;

F->rchild=NULL;}

else if(R,key<F->data.key)

   INSERT(R,F->lchild);

else if(R,key>F->data.key)

INSERT(R,F->rchild);

}

 

四、对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分）

五 设要分类的数据存放在数组A
3 1 4 1 5 9 2 6 5 3
中，要进行堆分类，首先得为其建立一个初始堆，试画出初始建设堆过程中，二元树的变化和数组A的变化。

Answer 2

给你第一题解法吧：后面的实在是不想做。

先根：ABCDEFGHI 

中根：CBEDAGFHI 

遍历的基本方法：先左子树后右子树。

1,先根遍历可以确定根节点为A,

2,依据1步，可以在中根遍历中确定左子树为：CBED,右为：GFHI

3,在可以重复1,2步。就可以得到结果。

       A

      B          F

C      D    G     H

                         I

4, O(n^3)+O(1)