微软创新联盟作业(一)

1、微软创新联盟作业(一)要求：1、6月7日前，组员把作业上发到我邮箱：；2、 认真完成。选择性完成，有些题目觉得简单，可以写伪代码；姓名：* 班级：* 题目01：集合的交、并、差运算3题目02：链表的操作3题目03：线性表的逆置操作3题目04：求阶乘3题目05：约瑟夫环3题目06：敢死队问题4题目07：简单计数器4题目08：任意长的整数加法4题目09：运动会分数据统计4题目10：纸牌游戏5题目11：表达式求值5题目12：停车场管理问题5题目13：小学生作业5题目14：猴子吃桃子5题目15：数制转换6题目16：括号匹配6题目17：模拟队列6题目18：串的查找和替换6题目19：稀疏矩阵的转置、相加6

2、题目20：稀疏矩阵的相乘6题目21：遍历二叉树7题目22：线索二叉树的应用7题目23：哈夫曼编码译码器7题目24：求树中当前结点所在的层次数7题目25：打印二叉树结构7题目26：图基于邻接矩阵的遍历7题目27：图基于邻接表的遍历8题目28：克鲁斯卡尔算法求网的最小生成树8题目29：普里姆算法求最小生成树8题目30：校园导航问题8题目31：教学计划编制问题8题目32：二叉排序树的实现8题目33：哈希表的设计与实现8题目34：牌照中的多关键字排序9题目35：排序算法比较9题目36：排序中记录移动次数的比较9题目37：函数的最小值9题目38：学生成绩管理系统9题目39：串模式匹配算法的设计与实现10

3、题目40：模拟民航公司自动订票系统10题目41：全国交通咨询模拟10题目42：10题目43：分酒问题10题目44：11题目45：n皇后问题11题目46：舞伴问题11题目01：集合的交、并、差运算1、问题描述：编制一个能演示执行集合的交、并和差运算的程序。2、基本任务A）集合元素用小写英文字母，执行各种操作应以对话方式执行。B）利用单链表表示集合，理解好三种运算的含义。题目02：链表的操作1、问题描述：实现链表的合并、排序操作2、基本要求：A)建立两个链表A和B，链表元素个数分别为m和n个。B)假设元素分别为(x1,x2,xm)，和(y1,y2, yn)。把它们合并成一个线性表C，使得： 当m&

4、gt;=n时，C=x1,y1,x2,y2,xn,yn,xm 当n>m时，C=y1,x1,y2,x2,ym,xm,yn 输出线形表CC) 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。3、测试数据：A)A表(30，41，15，12，56，80) B表(23，56，78，23，12，33，79，90，55)B)A表(30，41，15，12，56，80，23，12，34) B表(23，56，78，23，12)题目03：线性表的逆置操作1、问题描述：分别以不同存储结构实现线性表的就地逆置。线性表的就地逆置就是在原表的存储空间内将线性表(a1,a2,a3,an)逆置为(an，an-1

5、，a2，a1)。2、基本要求：A)分别建立顺序表和链表；B)在两种不同的存储结构下实现线性表的就地逆置，并将结果输出。3、测试数据 12,38,27,46,53,85,17题目04：求阶乘1、问题描述：设计一个程序求较大整数的阶乘(该阶乘大于长整数的取值范围)。2、基本要求：略题目05：约瑟夫环1、问题描述： 编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列

6、为止。设计一个程序来求出出列顺序。2、基本要求：A)利用单向循环链表作为存储结构模拟此过程；B)键盘输入总人数、初始报数上限值m及各人密码；C)按照出列顺序输出各人的编号。3、测试数据： m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，则正确的输出是什么？ 输入数据：输入m的初值，n，输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的输出序列。 题目06：敢死队问题1、问题描述：有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐

7、成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。   排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。2、基本要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。题目07：简单计数器1、问题描述：设计一元稀疏多项式简单计数器，能够完成多项式相加和相减的运算。2、基本要求：A)用带表头结点的单链表存储多项式；B)输出多项式，输出

8、形式为整数序列：n，c1，e1，c2，e2cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。C)多项式a和b相加，建立多项式a+b，输出相加的多项式。D)多项式a和b相减，建立多项式a-b，输出相减的多项式。3、测试数据：A)(2x+5x8-3.1x11)+(7-5x8+11x9)B)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)C)(x+x2+x3)+0D)(x+x3)-(-x-x-3)题目08：任意长的整数加法1、问题描述：设计一个程序实现两个任意长的整数的求和运算。2、基本要求：A)利用双向循环链表，设计一个实现

9、任意长的整数进行加法运算的演示程序。B)要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，00003、测试数据：略题目09：运动会分数据统计问题描述：参加运动会的n个学校编号为1n，比赛分成m个男子项目和w个女子项目，项目编号分别为1m和m+1m+w。有些项目取前五名，得分依次为6，4，3，2，1；有些项目取前三名，得分依次为4，2，1。写一程序产生各学校的成绩单(包括各校所取得的每项成绩的项目号、成绩、姓名和得分)和团体总分报表(包括校号、男子团体总分、女子团体总分和团体总分)。基本要求：1)可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以

10、按学校编号或名称、学校总分、男女团体总分排序输出；4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。5)数据存入文件并能随时查询。题目10：纸牌游戏1、问题描述：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？2、基本要求：略题目11：表达式求值1、问题描述：设计一个程序求任意一个浮点数

11、表达式的计算结果。2、基本要求：题目12：停车场管理问题1、问题描述：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在南端，最先到达的第一辆车停放在停车场的最北端)，若停车场内已停了n辆汽车，则后来的汽车只能在门外的通道上等候，一旦有车开走，收排在通道上的第一辆车即可开入；当停车场内每辆车要离开时，在它之后进入的车辆必须先退出停车场为其让路，待该辆车开出大门，其他车辆再按原次序进入停车场，每辆停放在停车场的车在它离开停车场时必须按它停留在停车场内的时间长短交纳停车费。试为停车场编写按上述要求进行管理的模拟程序。

12、2、基本要求A）要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。B）汽车的模拟输入信息格式可以是：(到达离去，汽车牌照号码，到达离去的时刻)。例如，(A，1，5)表示1号牌照车在5这个时刻到达，而(D，5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(E，0，0)时结束。题目13：小学生作业1、问题描述：利用栈求表达式的值，可供小学生作业，并能给出分数。2、基本要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。题目1

13、4：猴子吃桃子1、问题描述：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。2、基本要求：A)采用数组数据结构实现上述求解B)采用链数据结构实现上述求解C)采用递归实现上述求解D)如果采用4种方法者,适当加分题目15：数制转换1、问题描述：任意给定一个M进制的数x，转换为其它任意进制的数据。2、基本要求：A)对给字一个M进制的数据x，求出此数x的10进制值(用MD表示)；B)实现对x向任意的一个非M进制的数的转换。C)至少用两种或两种以上的方法实现上述要求(用栈解决，用数组解决，其它方法解决)。题目1

14、6：括号匹配1、问题描述：2、基本要求：题目17：模拟队列1、问题描述：利用“单链表”和“栈”模拟队列的基本操作。2、基本任务：模拟队列的操作要求实现以下基本操作· 将队列置成空队列· 返回队列的第一个元素· 把元素插入队列的后端· 删除队列的第一个元素· 判定队列是否为空题目18：串的查找和替换1、问题描述：在一篇英文的文章中，给出要查找的单词，并将文章中所有的该单词替换为指定的另一个单词。2、基本要求A)英文文章是预先存储于文件中；B)打开该文件后，在文章中完成对指定查找单词的替换，并要求同时给出替换的次数；C)替换完成后再次将结果存入到文

15、件中。题目19：稀疏矩阵的转置、相加1、问题描述：稀疏矩阵采用三元组表示，要求完成对该稀疏矩阵的转置操作，两个稀疏矩阵的相加运算。2、基本要求：A)稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。B)求出A的转置矩阵D，输出D。题目20：稀疏矩阵的相乘1、问题描述：稀疏矩阵采用三元组表示，要求完成对该稀疏矩阵的相乘运算。2、基本要求：A)利用三元组方式存储稀疏矩阵；B)完成两个稀疏矩阵相乘，并分别按三元组方式和矩阵方式输出结果。题目21：遍历二叉树1、问题描述：要求能够输入树的各个结点，并能够输出用不同方法遍历二叉树的遍历序列。2、基本任务：A)分别建立建立

16、二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； B)能够利用不同的方法实现二叉树的先序、中序、后序、层次遍历的序列。题目22：线索二叉树的应用1、问题描述：实现线索二叉树的建立、插入、删除、恢复线索的实现。2、基本任务：略题目23：哈夫曼编码译码器1、问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。2、基本任务：题目24：求树中当前结点所在的层次数1、问题描述：分别利用递归和非递归的方法，求当前结点所在二叉树中的层次数。2、基本任务A)要求建立二叉树，并在二叉树中查找到指定的第一个

17、结点；B)分别利用递归和非递归的方法求当前结点在二叉树中的层次数。题目25：打印二叉树结构1、问题描述：按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。例如：2、基本任务A)可以利用RDL遍历方法实现；B)利用结点的深度控制横向位置。C)在屏幕上打印出树形结构题目26：图基于邻接矩阵的遍历1、问题描述：对任意给定的图(顶点数和边数自定)，建立它的邻接矩阵并输出，并实现图的深度优先搜索遍历和广度优先搜索遍历。2、基本任务：A)建立基于邻接矩阵的图, 并按矩阵方式输出邻接矩阵；B)对图实现深度遍历和广度遍历，并输出遍历的序列。题目

18、27：图基于邻接表的遍历1、问题描述：对任意给定的图(顶点数和边数自定)，建立它的邻接表并输出，并实现图的深度优先搜索遍历和广度优先搜索遍历。2、基本任务：A)建立基于邻接表的图, 并按邻接表方式输出图；B)对图实现深度遍历和广度遍历，并输出遍历的序列。题目28：克鲁斯卡尔算法求网的最小生成树1、问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。2、基本任务A）选择合适的存储结构，完成网的建立；B）利用克鲁斯卡尔算法求网的最小生成树，并输出。题目29：普里姆算法求最小生成树1、问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。2、基本任务A）选择合适

19、的存储结构，完成网的建立；B）利用普里姆算法求网的最小生成树，并输出。题目30：校园导航问题1、问题描述：设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径(最短路径)。2、基本任务：略题目31：教学计划编制问题1、问题描述：针对信息与计算科学专业的课程，根据课程之间的依赖关系(如离散数学应在数据结构之前开设)制定课程安排计划，并满足各学期课程数目大致相同。2、基本任务：略题目32：二叉排序树的实现1、问题描述：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。2、基本任务A）选择合适的存储结构构造二叉排序

20、树；B) 对二叉排序树T作中序遍历，输出结果；C) 在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。D）尽量给出“顺序和链式”两种不同结构下的操作，并比较。题目33：哈希表的设计与实现 1、问题描述： 设计哈希表实现电话号码查询系统。2、基本要求：A）设每个记录有下列数据项：电话号码、用户名、地址；B）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；C）采用再哈希法解决冲突；D）查找并显示给定电话号码的记录；E）查找并显示给定用户名的记录。F）在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法(至少两种)，考察平均查找长度的变化。题目3

21、4：牌照中的多关键字排序1、问题描述：了解多关键字的使用范围，并实现对牌照按多关键字排序后的快速查找。排序和查找是在数据信息处理中使用频度极高的操作。为加快速度需先对数据记录按关键字排序，在汽车数据模型中，汽车牌照是关键字，而且是具有结构特点的一类关键字。因为汽车牌照号是数字、字母和汉字混编的，例如：赣AD7328，这种记录集合是一个适于利用多关键字进行排序的典型例子2、基本任务A）利用链式基数排序方法实现排序。B）在排序的基础上，利用二分查找的思想，实现对这批汽车记录按关键字的查找。 题目35：排序算法比较1、问题描述：利用随机函数产生N个随机整数(20000以上)，对这些数进行多种方法进行

22、排序。2、基本任务A）要求自动产生随机数，并将随机数保存到数据文件中；B）利用多种方法对数据文件中的数据进行排序，并输入排序的中间结果；C）统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比)，找出其中两种较快的方法。题目36：排序中记录移动次数的比较1、问题描述：任意选取三种不同的排序方法，研究在排序过程中记录的移动次数。2、基本任务：A）对一组数据实现多种排序，并在排序过程中记录记录的移动次数；B）研究各种情况下数据在排序时的移动次数，并分析结果。题目37：函数的最小值1、问题描述：设计程序按从大到小的次序依次输出函数f(a,b)=2*a2+b2的最小的100个函数值及相应的

23、两个参数的值，其中a和b均为自然数。2、基本任务：A)作为函数值的存储结构应尽可能节省空间。B)所设计算法及整个程序的时间复杂度应尽可能小。题目38：学生成绩管理系统1、问题描述现有学生成绩信息文件1(1.txt)，内容如下姓名    学号   语文  数学   英语     张明明  01     67    78      82李成友 

24、; 02     78    91      88学生成绩信息文件2(2.txt),内容如下:姓名    学号   语文  数学   英语     陈果    31     57    68      82李华

25、明  32     88    90      68编写程序完成数据的合并，查询，排序等操作。2、基本任务A）选择合适的存储结构，对数据文件操作；B）管理系统中要提供以下功能：· 实现对两个文件数据进行合并,生成新文件3.txt· 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt·  对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)· 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现)题目39：串模式匹配算法的设计与实现略题目40：模拟民航公司自动订票系统略题目41：全国交通咨询模拟1、问题描述：处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。2、基本要求A）提供对城市信息进行编辑(如：添加或删除)的功能。B)城市