数据结构遍历真题

第一根:ABCDEFGHI？

中跟:CBEDAGFHI？

构建这个二叉树。

答:？A

/ \

b？F

/ \/ \

c？D G？H

/ \

我？E

4.分析以下程序的运行时间:

a)？作废？神秘(国际)

{int？I，j，k；

for(I = 1；我& ltn；i++)

for(j = I+1；j & lt= n；j++)

for(k = 1；k & lt= j；k++)

{一些？声明？要求？O(1)？时间；}

}

我的答案是n3，但我不确定。

b)作废？podd(int？n)

{int？I，j，x，y；

for(I = 1；我& lt= n；I++)

if(奇数(I))

{ for(j = I；j & lt= n；j++)

x = x+1；

for(j = 1；j & lt= 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(图g，int i)

{ edge node * t；

printf("%4d "，I)；？

已访问[I]= 1；？

t = g[I]；

while(t！=NULL) {

如果(访问过[t-& gt；vno]= =0)

dfs(g，t->vno)；

t = t-& gt；接下来；

}

}

在线索二叉树中，根顺序的后继者由节点p找到。

答:

typedef枚举{lLINK，THREAD } PointerTag？//LINK = = 0；指针，

THREAD = = 1；线索？

typedef struct BinThrNode {？

遥测数据；

struct BinThrNode *lchilid，* rchild

指针标签ltag，rtag

}?BinThrNode，* BinThrTree？

中序遍历线索二叉树

如何找到P所指节点的前身？

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

当p->；当ltag==LINK时，前驱是p->；lchild的右下节点。

在二叉查找树f中，实现了插入记录r。

答:

空插入(记录R，BST & ampf)

{if(F= =NULL)

{ F =新单元格类型；

f-& gt；数据= R；

f-& gt；lchild = NULL

f-& gt；rchild = NULL}

else if(R，key & ltf-& gt；data.key)

INSERT(R，F-& gt；l child)；

else if(R，key & gtf-& gt；data.key)

INSERT(R，F-& gt；rchild)；

}

第四，对于下面的加权连通无向图，用Prim算法构造一棵最小生成树。画出施工过程的每一步。(12分)

5.让待分类的数据存放在数组a中。

3 1 4 1 5 9 2 6 5 3

为了对堆进行分类，首先要为它建立一个初始堆，并试着画出初始堆构造过程中二叉树和数组A的变化。