软件技术基础--考试大作业

《软件技术基础--考试大作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件技术基础考试大作业学号：姓名：年月日第一部分数据结构程序设计（A4纸打印）说明：（1）共七组选题，每位学生选择一组选题，每组选题包含两个小题，每组选题人数为20-21人，每位学生独立完成所选题目（两个小题）。【建议按学号顺序选题】（2）内容包括题目描述、预备知识、问题分析、数据结构设计、源代码等。选题一1.约瑟夫（Joseph）问题编号为1,…，n的n个人按顺时针方向围坐一圈，从第1号的人开始按顺时针方向自1开始顺序报数，报到山吋停止报数（m

2、，按照出列的顺序打印各人的编号。要求：建立循环单链表存储n个人的编号信息，进行问题的求解。2.八皇后问题八皇后问题，就是在一个8X8的棋盘上放置8个皇后。规则：不允许两个皇后在同一行、同一列和同一对角线上，即在每一行、每一列只能有一个皇后，且任意两个皇后不能在同一对角线上。编写程序，将八皇后的所冇摆法全部实现，并输出。要求：八皇后问题是一个古老的搜索问题，使用递归方法实现。在递归过程屮，一一测试每一种摆法，直至得出全部正确答案为止。当确定某个皇后的位置时，需要解决行、列、两条对角线上的冲突问题。选题二1.集合的基本运算假设以两个递增有序排列的线性表A和B分别表示两个集合

3、，现需建立有序线性表C、D和E,其元素分别为A和B屮元素的交集、并集和差集。请编写程序实现。要求：输入线性表A和氏输出其交集、并集和差集。2.二叉树的遍历及具应用采用二叉链表作为二叉树的存储结构，实现如卜•功能：（1）输入二叉树的特殊先序序列，建立二叉树。（2）实现二叉树的层次遍历和中序遍历。（3）求二叉树的深度。（4）将二叉树中所有结点的左、右子树互相交换。（5）求二叉树中叶了结点的数目。编写程序实现，并输岀相关数据。选题三1.括号匹配问题假设一个算术表达式中可以包括3种括号:圆括号“（”和“）”、方括号“[”和“]”以及花括号和“}”，且这3种括号可按任意的次序嵌套

4、使用。设计一个程序，判定所给表达式中所含括号是否匹配。要求：输入一个算术表达式，将其保存在带头结点的单链表或数组中，通过顺序栈实现括号匹配问题的求解。2.有向图结点的入度、出度和度的求解设计一个程序，对于具有N个结点的有向图，求每个结点的入度、出度和度。要求：用邻接矩阵存储有向图。选题四1.舞伴问题假设在周末舞会上，男士们和女士们进入舞厅时，各口排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。请编写程序模拟上述舞伴配对问题。要求：男士与女士的姓名与性别以同一数组输入，分别按性别建立两个队列，输

5、出结果要求给出配成舞伴的男士与女士的姓名，以及未配对队伍中剩余元索的个数和队头元索的姓名。2.稀疏矩阵的加减法假设稀疏矩阵A和B（m行n列）都采用三元组表示，编写程序计算C=A+B,D-A-B，矩阵C和D也采用三元组表示。编写程序实现，并输出结果。选题五1.有向图遍历的实现已知一个冇向图，用邻接表作为其存储结构，编程实现深度优先遍历图中结点的操作，并输出结点序列。2.图书借阅管理图书馆存放一批图书，图书信息存放在库存表屮，借阅信息存放在借阅表屮，每次借阅时，需更新两个表。在借阅时，首先查询库存表，若找到要借的书，将借阅者的姓名、借阅号、书号、书名存入借阅表中，并修改库存

6、表中相应书的库存量；若未找到，则给出“没有此书！”的信息。要求：库存表、借阅表以结构数组实现。选题六1.查找十字链表元素已知一个稀疏矩阵以十字链表的形式存储，设计程序实现查找指定元素位置的算法。1.渡口管理问题某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类，上船冇如下规定：同类车先到先上船，客车先于货车上渡船，口每上4辆客车，才允许上一辆货车;若等待客车不足4辆，则以货车代替，若无货车等待则允许客车都上船。编程实现模拟渡口管理的过程。提示：分别构造客车队列和货车队列实现过程管理。选题七1.求解迷宫问题假设迷宫是一个ni行n列的矩阵，该矩阵元素仅有

7、0和1两种取值。其中元素0表示无障碍，元素1表示冇障碍。设入口为（0,0）,出口为（旷1,n-1）。每次移动时只能从一个无障碍的单元（矩阵元素位置）移到周围8个方向上任一无障碍的单元。请编写程序模拟上述求解迷宫问题，给出一条通过迷宫的路径或报告一个“无法通过”的消息。提示：迷宫通过键盘输入的方式设置。2.构造循环队列从键盘输入一个整数序列切，a2,…缶，编程实现：当弘＞0吋，进队；当弘〈0吋，3d退队；当afO时，农小输入结束。耍求：将队列构造为循环队列，并写岀入队和退队的函数，并能处理异常情况。第二部分简述题（A4纸手写）说明：每题要求