华工数据结构作业

（2）

（3）邻接矩阵

（4）邻接表

5. 对于如上图所示的有向图，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 答：(1) 以顶点①为根的深度优先生成树（不唯一）：② ③ ④ ⑤ ⑥ ① ①

或

② ③

② ③

⑤ ④

(2) 以顶点②为根的广度优先生成树：

①

④ ⑤

③

②

⑤

④

6.已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。

先序序列 _BC_EF__ 中序序列 BDE_AG_H 后序序列 _DC_GH_A 答：后序最后一个是A，所以A是先序的第一个得到： 先序序列 ABC_EF__ 中序序列 BDE_AG_H 后序序列 _DC_GH_A

_____________(A)____________ ____________/___\\___________ ________(BDE_)_(G_H)________

先序的第二个元素是B，所以B是A的左子树根节点 由中序B在最前，知道其他元素都在B的右子树上

所以，后序序列为(DE_)B(G_H)A，对比已有的后序序列_DC_GH_A 得后序序列为：EDCBGHFA，中序序列为：BDECAGFH 先序序列 ABC_EF__ 中序序列 BDECAGFH 后序序列 EDCBGHFA 所以，二叉树为：

_____________(A)_____________ ____________/___\\____________ __________(B)____(F)_________ ___________\\_____/_\\_________ ___________(C)_(G)_(H)_______ ___________/_________________ _________(D)_________________ __________\\__________________ __________(E)________________

7．分析下列两个程序段的运行时间（时间复杂度）。 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++); }

答：O(n3)

void odd (int n)

{ int i, j, x = 0, y = 0; for (i =1; i <= n; i++) if odd(i)

{ for(j = i; j <= n; j++) x++; for( j = 1; j <= i; j++) y++; } }

答：O(n2)

8.有一组数据：25，50，70，21，4，18，100，43，7，12。现采用汽泡排序算法进行排序，写出每趟排序的结果，并标明第一趟数据的移动情况。 答：第一趟： 25，50，70，21，4，18，100，43，7，12

25，50，70，21，4，18，100，43，7，12 25，50，21，70，4，18，100，43，7，12 25，50，21，4，70，18，100，43，7，12 25，50，21，4，18，70，100，43，7，12 25，50，21，4，18，70，100，43，7，12 25，50，21，4，18，70，43，100，7，12 25，50，21，4，18，70，43，7，100，12 25，50，21，4，18，70，43，7，12，100

第二趟 25，21，4，18，50，43，7，12，70，100 第三趟 21，4，18，25，43，7，12，50，70，100 第四趟 4，18，21，25，7，12，43，50，70，100 第五趟 4，18，21，7，12，25，43，50，70，100 第六趟 4，18，7，12，21，25，43，50，70，100 第七趟 4，7，12，18，21，25，43，50，70，100