还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
一、单项分值分
201、约瑟夫环游戏(本题10分)
2、八皇后问题(图形表示加20分)
3、表达式的求值问题
4、迷宫问题(图形表示加10分)
二、单项分值50分
5、HTML文档标记匹配算法【基本要求】输入一段HTML代码,判断该代码是否符合HTML的语法【提示】HTML文档由不同的标记划分为不同的部份与层次与括号类似,这些标记需要成对浮现,对于名为VmyTag》的起始标记,相应的结束标记为/myTag〉常用的HTML标记•html/htmD:HTML文档•title/title:文档标题•body/body〉:文档体•hl/hl:节的头部•center/center:居中对齐【问题描述】处于对不同目的的旅客对交通工具有不同的要求例如,因公出差的旅客希望在旅途中的时间尽可能短,出门旅游的游客则希翼旅费尽可能省,而老年旅客则要求中转次数至少编制一个全国城市间的交通咨询程序,为旅客提供两种或者三种最优决策的交通咨询【基本要求】1提供对城市信息进行编辑如添加或者删除的功能2城市之间有两种交通工具火车和飞机提供对列车时刻表和飞机航班进行编辑增设或者删除的功能3提供两种最优决策最快到达或者最省钱到达全程只考虑一种交通工具4旅途中耗费的总时间应该包括中转站的等候时间5咨询以用户和计算机的对话方式进行由用户输入起始站、终点站、最优决策原则和交通工具,输出信息最快需要多长期才干到达或者至少需要多少旅费才干到达,并详细说明挨次于何时乘坐哪一趟列车或者哪一次班机到何地【测试数据】【实现提示】1对全国城市交通图和班车时刻表及飞机航班表的编辑,应该提供文件形式输入和键盘输入两种方式飞机航班表的信息应包括起始站的出发时间、终点站的到达时间和票价;列车时刻表则需根据交通图给出各个路段的详细信息,例如对于从北京到上海的火车,需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息继续阅读•left/left:左对齐•p/p:段落HTML语言有合理的嵌套,如htmlXbody/body/html
6、程序源代码的相似性【问题描述】对于两个C++语言的源程序代码,用哈希表的方法分别统计两个程序中使用C++语言关键字的情况,并最终按定量的计算结果,得出两份程序的相似性【基本要求】建立C++语言关键字的哈希表,统计在每一个源程序中C++关键字浮现的频度,得到两个向量XI和X2,通过计算向量XI和X2的相对距离来判断两个源程序的相似性例如关键Int ForChar ifelse whiledo字Void breakclass程序1关键字频度4304307002程序2关键字频度4205405201Xl=[4,3,0,4,3,0,7,0,0,2]X2=[4,2,0,5,4,0,5,2,0,1]设s是向量XI和X2的相对距离,s=sqrt£xil-xi22,当X1=X2时,s=0,反映出可能是同一个程序;s值越大,则两个程序的差别可能也越大【测试数据】选择若干组编译和运行都无误的C++程序,程序之间有相近的和差别大的,用上述方法求s,对照两个程序的相似性【提高要求】建立源代码用户标识符表,比较两个源代码用户标识符浮现的频度,综合关键字频度和用户标识符频度判断两个程序的相似性
三、单项分值60分含Onlogn排序算法及折半、索引查找算法的,各加10分,含基数排序及动态表的,各加20分
7、飞机订票系统【问题描述】通过此系统可以实现如下功能录入可以录入航班情况数据可以存储在一个数据文件中,数据结构、具体数据自定查询可以查询某个航线的情况如,输入航班号,查询起降时间,起飞抵达城市,航班票价,票价折扣,确定航班是否满仓;可以输入起飞抵达城市,查询飞机航班情况;订票订票情况可以存在一个数据文件中,结构自己设定,可以订票,如果该航班已经无票,可以提供相关可选择航班;退票可退票,退票后修改相关数据文件;客户资料有姓名,证件号,订票数量及航班情况,定单要有编号;修改航班信息当航班信息改变可以修改航班数据文件;【基本要求】根据以上功能说明,设计航班信息,订票信息的存储结构,设计程序完成功能;
8、图书管理系统【问题描述】设计一个计算机管理系统完成图书管理基本业务【基本要求】1)每种书的登记内容包括书号、书名、著作者、现存量和库存量;2)对书号建立索引表(线性表)以提高查找效率;3)系统主要功能如下*采编入库新购一种书,确定书号后,登记到图书帐目表中,如果表中已有,则只将库存量增加;*借阅如果一种书的现存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变现存量;*归还注销对借阅者的登记,改变该书的现存量【进一步完成内容】1)系统功能的进一步完善;2)索引表采用树表3)设计内容4)程序流程图5)源程序6)软件测试报告(包括所用到的数据及结果)
9、小型英汉词典【问题描述】设^一个英汉词典,支持Member(查找)、Insert(插入)、Delete(删除)操作【基本要求】实现字典的常用方法有有序线性表(Memeber用二分检索实现)、AVL树(二叉搜索树)、Patricia Trie,散列表等,任选一种方法实现字典的操作,查找单词、插入单词(插入时,先查找,找不到插入,找到提示用户)、删除单词(删除时,先查找,找到删除,找不到提示用户)【测试数据】任•英文单词【提高要求】选用两种以上的方法实现字典的操作,并比较不同实现算法的时间复杂度和空间复杂度【提示】字典可以自己建立,但必须按字母a~z建立26个文件,建议从网上下载,文件类型为txto
四、单项分值80分(图形显示加20分)
10、校园导航问题【问题描述】以我校为例,设计一个校园导游程序,主要为来访的客人提供信息查询【基本要求】提供至少5个景点的校园导游咨询(包括景点介绍、景点间距离等)本程序的目的是为来客提供路径咨询和景点查询(根据用户指定的始点和终点输出相应最短简单路径或者输出用户指定景点的详细信息);系统管理员又可根据实际情况对导游图进行修改,删除路径或者景点选取九个大家熟悉的景点,抽象成一张带权无向图(如图所示)以图中顶点表示景点,存放景点名称、代号等信息;以边表示路径,边上的权值表示两地的距离,为此图选择适当的数据结构100m本演示程序采用c语言编写,完成为了无向图的建立和其他操作:
①输入的形式和输入值的范围主函数中调用图表建立函数之后,通过输入1到6不同的阿拉伯数字进行功能选择;在查找景点详细信息操作时需要输入景点的的序号;在求路径函数中,也是输入对应景点序号值;在删除路线函数里,输入构成边的两个景点的序号对;在所有输入操作中,输入的值都是整数
②输出的形式菜单函数,输出功能菜单目录;查找函数信息操作,输出景点序号,名称,还有详细介绍;求最短路径函数,输出路线经过的顶点和路线的长度!删除函数,当删除成功后会输出删除成功;求删除操作后显示删除的元素的值
③程序所能达到的功能完成无向带权图的生成(通过建立顶点数组和邻接矩阵)、通过选择菜单进行不同操作,查看景点信息、求景点间最短路径、删除景点或者路线
④测试数据A.查看景点详细信息操作中输入3B.查询最短路径操作中输入3,5C.删除操作中先后输入1(删除景点),2)(删除边)D.删除景点操作中输入1E.删除边操作中输入1,5F.查看一个景点到其他景点所有路线输入
111、并查集检查网络【问题描述】给定一个计算机网络以及机器间的双向连线列表,每一条连线允许两端的计算机进行直接的文件传输,其他计算机间若存在一条连通路径,也可以进行间接的文件传输请写出程序判断任意指定两台计算机,它们之间是否可以进行文件传输?【输入要求】输入若干测试数据组成对于每一组测试,第1行包含一个整数N^10000,即网络中计算机的总台数,于是每台计算机可用1到N之间的一个正整数表示接下来的几行输入格式为I ClC2或者C或者C C1C2或者S,其中C1和C2是两台计算机的序号,I表示在C1和C2间输入一条连线,C表示检查C1和C2间是否可以传输文件,S表示该组测试结束当N为0时,表示全部测试结束,不要对该数据做任何处理【输出要求】对每一组C开头的测试,检查C1和C2间是否可以传输文件,若可以,则在一行中输出“yes”,否则输出“no”当读到S时,检查整个网络若网络中任意两机器间都可以传输文件,则在一行中输出“The networkis connected.n,否则输出“There arek components.,其中k是网络中连通集的个数两组测试数据之间请输出一空行分隔
12、哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止【基本要求】1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中)2)分别采用动态和静态存储结构3)初始化键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;4)编码利用建好的哈夫曼树生成哈夫曼编码;5)输出编码;6)设字符集及频度如下表字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161【进一步完成内容】1)译码功能;2)显示哈夫曼树;3)界面设计的优化
13、全国交通咨询摹拟。