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

3已知一株非空二元树,其先根与中根遍历的结果为:先根:ABCDEFGHI中根:CBEDAGFHI根据先根和中根遍历结果,将此二元树构造出来。4分析下列程序的运行时间:A)... 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请注明账号
展开
 我来答
零度cat仔
2013-11-04 · 超过13用户采纳过TA的回答
知道答主
回答量:36
采纳率:0%
帮助的人:27.4万
展开全部

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的变化。

濮浚02
2012-05-11 · TA获得超过132个赞
知道答主
回答量:47
采纳率:0%
帮助的人:31.6万
展开全部

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

先根: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)

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式