程序设计和算法综合训练教学大纲2016年.docx

《程序设计和算法综合训练教学大纲2016年.docx》由会员分享，可在线阅读，更多相关《程序设计和算法综合训练教学大纲2016年.docx（10页珍藏版）》请在优知文库上搜索。

1、?程序设计与算法综合训练?教学大纲课程编号：课程名称：程序设计与算法综合训练英文名称：ComprehensiveTrainingofProgrammingDesignandAlgorithm学分/学时：/80课程性质：必修适用专业：软件工程/网络工程/计算机科学与技术专业先修课程：高级语言程序设计(C语言版)，数据构造(C语言版)开课单位：计算机科学与技术学院一、课程的教学目标与任务?程序设计与算法综合训练?是一门面向软件工程专业、网络工程专业、计算机科学与技术专业的综合实践课程。它是配合专业学科平台课程?高级语言程序设计?和？数据构造?而开设的实践性教育环节。本课程的目的是：通过本课程的综合

2、实践训练，使学生加深对?高级语言程序设计?和？数据构造?课程中基本知识与基本原理的理解；掌握各种数据类型的使用技巧和模块化程序设计的方法；掌握程序设计的过程和技巧，确立分析问题、建设模型和运用程序进展问题求解的思维方式；掌握复杂数据构造在计算机中的存储表示及其运算，建设正确的数据组织与数据处理的设计思想,培养学生综合运用数据构造课程的相关设计理论与实际问题相结合解决数据组织与分析、数据处理与算法设计等设计问题的能力。二、课程具体内容及基本要求工程一迷宫问题的求解(8学时)问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出

3、口的通路，或得出没有通路的结论。1 .基本要求(1)首先实现一个以链表作存储构造的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出。其中：(Lj)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于教材第50页图3.4所示的迷宫，输出一条通路为：(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),。(2)编写递归形式的算法，求得迷宫中所有可能的通路。(3)以方阵形式输出迷宫及其通路。2 .重点、难点重点：针对迷宫问题的特点，利用栈的后进先出特点，选择适当的数据构造。难点：递归算法的设计与求解。3 .作业及课外学习要求：按照题意

4、要求独立进展设计，设计完毕后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求4研究中的“指标点4.1能够运用科学的研究方法对复杂软件工程问题进展需求分析研究；指标点4.2熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点4.3能够对原型验证方法进展研窕与分析，合理验证软件系统”的指标达成度进展评估。使学生在解决具体问题的过程中，能够灵活熟练地选择适宜的数据构造及设计有效的算法，从而加深对常用数据构造的理解，强化学生的逻辑思维能力和动手能力,稳固良好的编程习惯,掌握工程软件设计的基本方法,为后续课程的学习打下坚实根基。工程二停车场管理系统的设计与实现(8

5、学时)问题描述：停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在停车场的最北端)，假设车场内已停满n辆汽车，那么后来的汽车只能在门外的便道上等候，一旦有车开走，那么排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进展管理的模拟程序。1 .基本要求(1)以栈模拟停车场，以队列模拟车场外的便道，按

6、照从终端读入的输入数据序列进展模拟管理。(2)每一组输入数据包括三个数据项：汽车“到达或离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进展操作后的输出数据为：假设是车辆到达，那么输出汽车在停车场内或便道上的停车位置；假设是车离去；那么输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。(3)栈以顺序构造实现，队列以链表实现。2 .重点、难点重点：针对停车场问题的特点，利用栈的后进先出特点，选择栈这种数据构造来模拟停车场，利用队列先进先出的特点，选择队列这种数据构造来模拟车场外的便道。难点：离散事件问题的模拟算法设计与求解。3 .作业及课外学习要求：按照题意要求

7、独立进展设计，设计完毕后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求4研究”中的“指标点4.1能够运用科学的研究方法对复杂软件工程问题进展需求分析研究；指标点4.2熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点4.3能够对原型验证方法进展研究与分析，合理验证软件系统”的指标达成度进展评估。使学生在解决具体问题的过程中，能够灵活熟练地选择适宜的数据构造及设计有效的算法，从而加深对常用数据构造的理解，强化学生的逻辑思维能力和动手能力,稳固良好的编程习惯,掌握工程软件设计的基本方法,为后续课程的学习打下坚实根基。工程三银行业务模拟系统的设计与实现(8

8、学时)问题描述：假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，那么可上前办理业务，反之，假设四个窗口均有客户所占，他便会排在人数最少的队伍后面。现在需要编制程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。1 .基本要求(1)初始化(OpenForDay),模拟银行开门时各数据构造的状态。(2)事件驱动(EventDrived),对客户到达和离开事件做相应处理。(3)下班处理(CloseForDay),模拟银行关门时的动作

9、，统计客户平均逗留时间。2 .重点、难点重点：(1)通过实验掌握对离散事件模拟的认识；(2)进一步理解队列的实现与应用；(3)对链表的操作有更深层次的理解。难点：离散事件的模拟。3 .作业及课外学习要求：按照题意要求独立进展设计，设计完毕后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求4研究中的“指标点4.1能够运用科学的研究方法对复杂软件工程问题进展需求分析研究；指标点4.2熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点4.3能够对原型验证方法进展研究与分析，合理验证软件系统”的指标达成度进展评估。使学生在解决具体问题的过程中，能够灵活熟练地选

10、择适宜的数据构造及设计有效的算法，从而加深对常用数据构造的理解，强化学生的逻辑思维能力和动手能力，稳固良好的编程习惯，掌握工程软件设计的基本方法,工程四哈夫曼编/译码系统的设计与实现(16学时)问题描述：利用哈夫曼编码进展通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进展译码解码)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。1 .基本要求(1)初始化(Initialzation)从数据文件DataFile.data中读入字符及

11、每个字符的权值，建设哈夫曼树HUffTree；(2)编码(EnCoding)o用已建好的哈夫曼树，对文件ToBeTran.data中的文本进展编码形成报文，将报文写在文件Code.txt中；(3)译码(Decoding)o利用已建好的哈夫曼树，对文件COdeFile.data中的代码进展解码形成原文，结果存入文件Textfile.txt中；输出(Output)o输出DataFile.data中出现的字符以及各字符出现的频度(或概率)；输出ToBeTran.data及其报文Code.txt；输出CodeFileJata及其原文Textfile.txt；2 .重点、难点重点：(1)通过实验理解哈夫

12、曼树的特征及其应用；(2)哈夫曼树的构造算法设计；(3)利用构造的哈夫曼树进展编码和译码。难点：(I)字符的哈夫曼树编码及存储；(2)字符的译码与串的匹配算法。3 .作业及课外学习要求：按照题意要求独立进展设计，设计完毕后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求4研究中的“指标点4.1能够运用科学的研究方法对复杂软件工程问题进展需求分析研究；指标点4.2熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点4.3能够对原型验证方法进展研究与分析，合理验证软件系统”的指标达成度进展评估。使学生在解决具体问题的过程中，能够灵活熟练地选择适宜的数据构造及

13、设计有效的算法，从而加深对常用数据构造的理解，强化学生的逻辑思维能力和动手能力，稳固良好的编程习惯，掌握工程软件设计的基本方法,工程五通讯录查询系统的设计与实现(8学时)问题描述:为某个单位建设一个员工通讯录管理系统,可以方便查询每一个员工的与地址。设计散列表存储，设计并实现通讯录查找系统。1 .基本要求(1)每个记录有以下数据项：号码、用户名、地址；(2)从键盘输入各记录，分别以号码为关键字建设散列表；(3)采用二次探测再散列法解决冲突；(4)查找并显示给定号码的记录；(5)通讯录信息文件保存。2 .重点、难点重点：(1)通过实验深入理解哈希表既是一种存储形式，又是一种查找方法；(2)哈希表

14、的构造；(3)哈希冲突方案的设计。难点：哈希表的构造与哈希冲突方案的设计3 .作业及课外学习要求：按照题意要求独立进展设计，设计完毕后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求4研究中的“指标点4.1能够运用科学的研究方法对复杂软件工程问题进展需求分析研究；指标点4.2熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点4.3能够对原型验证方法进展研究与分析，合理验证软件系统”的指标达成度进展评估。使学生在解决具体问题的过程中，能够灵活熟练地选择适宜的数据构造及设计有效的算法，从而加深对常用数据构造的理解，强化学生的逻辑思维能力和动手能力，稳固良好

15、的编程习惯，掌握工程软件设计的基本方法,为后续课程的学习打下坚实根基。工程六电视大赛观众投票及排名系统的设计与实现(8学时)问题描述：在很多的电视大赛中，通常中选手表演完毕后，现场观众通过手中的按键对参赛选手进展投票，然后对选手获得的票数进展统计，从高到低进展降序排序，从而自动产生冠军、亚军和季军。要求编写算法模拟实现上述系统的功能。1 .基本要求(1)首先输入参赛选手的人数(范围为1-9个)，然后根据人数通过ma11oc函数来分配存放选手信息的顺序表；(2)将选手的编号和姓名依此存入顺序表中；(3)观众通过按键进展投票，按1为1号选手投票，按2,为2号选手投票，以此类推，以按0,作为投票完毕标志；(4)投票完毕后进展排序，在此采用各种排序算法，然后为每个选手计算名次，得票一样的名次也一样；2 .重点、难点重点：(1)参赛选手数据构造的设计；(2)排序算法的设计；难点：各种排序算法的性能分析与比较3 .作业及课外学习要求：按照题意要求独立进展设计，设计完毕后要按要求写出课程设计报告。本知识点的讲授和学习，可以支撑“毕业要求4研究中的“指标点4.1能够运用科学的研究方法对复杂软件工程问题进展需求分析研究；指标点4.2熟悉复杂软件系统的开发和应用环境，研究制定合理的软件设计与开发方案。指标点43能够对原型验证方法进展研究与分析，合理验证软件系统”的