《软件技术基础》结课大作业
姓名：院振召
学号：120611335
日期：2014年6月21日
说明与要求：
1.开放式考试不仅考察知识，同时考察学生查阅文献的能力；学生可以使用Google、百
度等搜索引擎，图书馆数字资源，如同方CNKI(中国学术期刊全文数据库)查阅资料，寻找答案和解题思路；
2.可以使用各种工具帮助自己解题，可以相互讨论，但是不允许拷贝、复制、剽窃他人
结果。

如果发现雷同，按雷同人数，每次雷同从成绩中扣除10分。

因不存在完美雷同标准，因此将根据批改教师的个人识别，进行雷同确认，因此为避免雷同，请自己设计代码或解题；
3.每个编程问题都要首先说明思路，然后给出代码；程序以及求解方法描述的编辑应该
美观；程序代码应该有层次缩进，以便阅读；
4.每个编程问题的C/C++代码的每一行必须有清晰的注释，说明改行中变量和语句的作
用，如果注释和C/C++语句不符，则视为剽窃。

5.根据自己的情况，采用C或C++语言中德一种作为编程语言，不能使用两种以上的语言；
6.编辑排版时，采用汉字五号宋体，英语和代码采用10号或五号Times New Roman字体，
打印时采用双面打印，连同填写好的封面一起装订，在最后一堂课时上交；禁止使用更大号字；
2014软件技术基础期末作业
1.利用减半递推技术，写出求长度为n的数组中最大元素的递归算法（10分）。

2.编写用回溯法求解n皇后的算法（10分）。

3.给定n个城市间的距离，求从一个城市0出发经过其他城市一次且一次的一条最短路
径（15分）。

4.将单链表看做二叉树，编写递归程序打印单链表（10分）。

5.编写二叉树的层次遍历算法（15分）。

6.自底向上实现归并排序算法（10分）。

7.实现堆排序算法（15分）。

8.实现迪杰斯特拉最短路径算法（15分）。