2015-2016学年第二学期期末考试《数据结构》大作业

李老师

一、应用题(每小题10分，共50分)
1．把下图中的二叉树转化成森林。











2．给定表（45,36,56,6,64,32,8,41），按数据元素在表中的次序构造一棵二叉查找树。
3．写出中缀表达式A-(B+C/D)*E的后缀形式。
4. 下图是一个地区的交通网络模型，顶点表示城市，边表示城市间的公路，边的权值表示构造公路的费用，请问如何构造出能连通各个城市且造价最低的交通网，并写出其构造过程。


5. 已知数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出冒泡排序每趟的结果。

二、算法设计题（每小题50分，共25分）
1.判断单链表head(head指向表头)是否是递增的。
2.设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数。