软件基础编程训练课程设置说明两门课：1、软件基础授课：32学时闭卷笔试，百分制，成绩＝卷面＋平时作业考试时间：暂定第11周周六（11月16日）2、软件基础编程训练上机：一周（24学时），其中教师指导12学时成绩：优、良、中、及格、不及格设计报告＋源程序上机时间：第8，9，10周，周四晚，5:10~9:10上机地点：原计算机系二楼东侧设计要求独立完成作业，一旦发现抄袭，按不及格处理模块化程序设计锯齿型书写格式必须上机调试通过实习报告实习题目、班级、姓名、学号、完成日期设计：需求分析、数据结构设计、核心算法设计（流程图）、调试分析、用户使用说明、源程序及程序运行结果打印清单程序中每个模块或函数应加注释，说明函数功能、入口及出口参数含义软盘：源程序及程序运行结果，几个同学可合用一张软盘（注明班级、姓名、电话）设计题目一：约瑟夫环问题设有编号为1，2，3……n的n个人顺时针方向围坐一圈，每人有一密码（正整数）。开始时给出一报数上限m，从编号为1的人开始报数，报m的人出列；以后将出列者的密码作为新的m，从顺时针方向紧挨着他的下一个人开始报数……直至所有人出列。试编一算法，求出出列顺序。要求：1、用循环链表实现2、从键盘输入n，m3、各人的密码由计算机随机产生（可用random()函数）设计题目二：栈的应用1、迷宫问题2、皇后问题3、背包问题以上三个题目任选其一设计题目三：二叉树构造已知一棵二叉树的先序和中序遍历序列，试设计完成下列任务的一个算法：构造此二叉树证明构造的正确性（即分别按先序和中序遍历该树，将所得的结果与给出的序列进行比较）要求：1、用二叉链表存储二叉树2、从键盘输入先序和中序遍历序列3、输出验证结果设计题目四：公园导游图给出一张某公园的导游图（景点不少于10个），游客通过终端询问可知：任一景点的相关信息从某一景点到另一景点的最短简单路径游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）要求：1、从键盘或文件输入导游图2、游客通过键盘选择两个景点，输出结果3、输出从入口到出口的最佳路线3、选作：以图形方式显示导游图和查询结果迷宫问题由0和1构成的m*n维矩阵M表示一个迷宫，其中0表示通路，1表示墙壁。迷宫入口为(1,1),出口为(m,n)。迷宫随机产生。试编一算法求出从入口点到出口点可沿八个方向前进的一条通路，或显示没有通路皇后问题求出在N*N的棋盘上放置N个棋子（皇后）的所有合法布局。布局合理规则是：在棋盘任一行、一列和任意对角线上都不能出现两个棋子。背包问题求解“从n个物件中选取恰好填满体积为T的背包”问题的所有解。