软件技术基础考试大作业
学号：
姓名：
年月日
第一部分数据结构程序设计（A4纸打印）
说明：
（1）共七组选题，每位学生选择一组选题，每组选题包含两个小题，每组选题人数为20--21人，每位学生独立完成所选题目（两个小题）。

【建议按学号顺序选题】（2）内容包括题目描述、预备知识、问题分析、数据结构设计、源代码等。

选题一
1．约瑟夫（Joseph）问题
编号为1，…，n的n个人按顺时针方向围坐一圈，从第1号的人开始按顺时针方向自1开始顺序报数，报到m时停止报数（m<n）。

报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

试设计程序模拟约瑟夫问题，按照出列的顺序打印各人的编号。

要求：建立循环单链表存储n个人的编号信息，进行问题的求解。

2．八皇后问题
八皇后问题，就是在一个8×8的棋盘上放置8个皇后。

规则：不允许两个皇后在同一行、同一列和同一对角线上，即在每一行、每一列只能有一个皇后，且任意两个皇后不能在同一对角线上。

编写程序，将八皇后的所有摆法全部实现，并输出。

要求：八皇后问题是一个古老的搜索问题，使用递归方法实现。

在递归过程中，一一测试每一种摆法，直至得出全部正确答案为止。

当确定某个皇后的位置时，需要解决行、列、两条对角线上的冲突问题。

选题二
1．集合的基本运算
假设以两个递增有序排列的线性表A和B分别表示两个集合，现需建立有序线性表C、D 和E，其元素分别为A和B中元素的交集、并集和差集。

请编写程序实现。

要求：输入线性表A和B，输出其交集、并集和差集。

2．二叉树的遍历及其应用
采用二叉链表作为二叉树的存储结构，实现如下功能：
（1）输入二叉树的特殊先序序列，建立二叉树。

（2）实现二叉树的层次遍历和中序遍历。

（3）求二叉树的深度。

（4）将二叉树中所有结点的左、右子树互相交换。

（5）求二叉树中叶子结点的数目。

编写程序实现，并输出相关数据。

选题三
1．括号匹配问题
假设一个算术表达式中可以包括3种括号：圆括号“（”和“）”、方括号“[”和“]”以及花括号“{”和“}”，且这3种括号可按任意的次序嵌套使用。

设计一个程序，判定所给表达式中所含括号是否匹配。

要求：输入一个算术表达式，将其保存在带头结点的单链表或数组中，通过顺序栈实现括号匹配问题的求解。

2．有向图结点的入度、出度和度的求解
设计一个程序，对于具有N个结点的有向图，求每个结点的入度、出度和度。

要求：用邻接矩阵存储有向图。

选题四
1．舞伴问题
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。

跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。

若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

请编写程序模拟上述舞伴配对问题。

要求：男士与女士的姓名与性别以同一数组输入，分别按性别建立两个队列，输出结果要求给出配成舞伴的男士与女士的姓名，以及未配对队伍中剩余元素的个数和队头元素的姓名。

2．稀疏矩阵的加减法
假设稀疏矩阵A和B（m行n列）都采用三元组表示，编写程序计算C＝A+B，D=A-B，矩阵C和D也采用三元组表示。

编写程序实现，并输出结果。

选题五
1．有向图遍历的实现
已知一个有向图，用邻接表作为其存储结构，编程实现深度优先遍历图中结点的操作，并输出结点序列。

2．图书借阅管理
图书馆存放一批图书，图书信息存放在库存表中，借阅信息存放在借阅表中，每次借阅时，需更新两个表。

在借阅时，首先查询库存表，若找到要借的书，将借阅者的姓名、借阅号、书号、书名存入借阅表中，并修改库存表中相应书的库存量；若未找到，则给出“没有此书！”的信息。

要求：库存表、借阅表以结构数组实现。

选题六
1. 查找十字链表元素
已知一个稀疏矩阵以十字链表的形式存储，设计程序实现查找指定元素位置的算法。

2. 渡口管理问题
某汽车轮渡口，过江渡船每次能载10辆车过江。

过江车辆分为客车类和货车类，上船有如下规定：同类车先到先上船，客车先于货车上渡船，且每上4辆客车，才允许上一辆货车；若等待客车不足4辆，则以货车代替，若无货车等待则允许客车都上船。

编程实现模拟渡口管理的过程。

提示：分别构造客车队列和货车队列实现过程管理。

选题七
1. 求解迷宫问题
假设迷宫是一个m行n列的矩阵，该矩阵元素仅有0和1两种取值。

其中元素0表示无障碍，元素1表示有障碍。

设入口为（0，0），出口为（m-1，n-1）。

每次移动时只能从一个无障碍的单元（矩阵元素位置）移到周围8个方向上任一无障碍的单元。

请编写程序模拟上述求解迷宫问题，给出一条通过迷宫的路径或报告一个“无法通过”的消息。

提示：迷宫通过键盘输入的方式设置。

2. 构造循环队列
从键盘输入一个整数序列a1，a2，…a n，编程实现：当a i>0时，a i进队；当a i<0时，a i退队；当a i=0时，表示输入结束。

要求：将队列构造为循环队列，并写出入队和退队的函数，并能处理异常情况。

第二部分简述题（A4纸手写）
说明：每题要求字数不低于500字
1.简述软件生命周期各阶段的功能与作用。

2.简述使用UML（统一建模语言）进行面向对象分析与设计的步骤和方法。

3.简述数据库设计的过程。

4.简述数据库中的三种数据模型。

5.简述操作系统的发展过程。

6.简述存储器管理技术与组织结构。

第三部分UML建模绘图题（A4纸打印）
说明：
（1）在Rational Rose环境下进行绘图；
（2）按照老师提供的幻灯片文件内容绘制，将其中的英文图翻译为中文图；
（3）在截图时需将图标题截取下来，图标题包括学生的学号、姓名和图名；
（4）需将浏览窗口的绘图目录信息截取下来；
（5）每张图需配以文字说明和简单的绘图步骤。