数据结构与算法试题，高分，求答案啊
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的变化。
[email protected]请注明账号
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的变化。
给你第一题解法吧：后面的实在是不想做。
先根：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)
