《数据结构与算法》课程设计指导书
一．目的
通过本课程设计，使同学更加系统地理解和掌握数据结构的基本概念；能自如地根据实际要求，设计相应的数据结构，并运用C或C++语言实现所设计的算法，能够利用所学的基本知识和技能，分析和解决简单的程序设计问题，为后续其它专业课程的学习和应用打下良好基础。
二．题目
根据指导教师的具体要求，从下面题目中选择1个来完成
1．学生成绩管理系统
2．简易客房管理系统
3．人事档案管理系统
4．进销存货物管理系统
5．图书管理系统
6．运动会分数统计
7．民航订票系统
8．校园导游咨询
9．长整数的加减法
10．表达式的求值
11．钱币的转换
12．二叉树的应用——哈夫曼树
13．银行排队系统模拟
14．文章编辑器
15．车票管理系统
16．连连看
17．扫雷
18．消消看
19．贪吃蛇
20．俄罗斯方块
21．飞行棋
22．其他题目（需老师同意）
注意
（1）在实现相关管理系统题目时，需要设计良好的数据结构，代码编写时不允许运用现有的数据库管理系统，具体功能应通过对文件的读写操作实现。
（2）其中题目1、2、3、4、5、6、7、14、15必需使用文件进行读写操作，文件读写操作有单独文档给大家做为编程参考。
（3）验收分数跟做的质量挂钩
（4）游戏类实现可以采用别的编程语言，但是因为是数据结构课程设计，所以程序中必需是要正确使用了数据结构的。
三．任务完成形式
1．完整的软件系统
最终必须向指导老师提交完整的程序源代码(.c和.cpp以及.h为后缀的文件)、数据文件以及使用说明文件等。源代码文件要特别注意编程规范、代码风格，关键代码需有合理的注释，不含任何无用代码；数据文件内要求有一定数量的“真实”数据（如对于记录文件，需要有5条以上记录）；使用说明文件的第一行，需要给出设计者的学号、姓名，后面为其它说明。
2．课程设计报告(详细要求请参考附录二)
课程设计报告总体上主要包括以下几个部分：
1）封面
2）目录
3）课程设计报告正文
4）使用说明
5）参考文献
四．总体要求
1．每道题目的程序代码总量不少于600行（其中不包括自动生成代码），有合理注释。
2．课程设计报告正文字数不少于8000字，概念清楚、叙述正确、内容完整、书写规范。
3．独立完成课程设计，不得抄袭他人。
4．功能正确、有一定实用性。
5．尽可能大量使用各种C或者C++语言程序设计技术，尤其在以下几个方面：
指针及其运算、结构、指针数组、数组指针、字符数组与字符串、内存空间动态申请与释放、文件访问与操作、合理的常量与全局变量及函数接口变量定义、数据输入与数据格式检查、数据类型转换、错误处理、工程设计技术（整个系统由一个工程文件、若干个程序文件、若干头文件、甚至库文件等组成）。
程序界面不做较高要求，但要考虑到用户使用的方便，有较好的交互界面。
6．可以使用VC编译环境开发程序，但不允许使用现成的数据库如access，SQL Server等完成上面的课程设计题目，否则成绩评定为不及格。
7．设计时适当考虑程序的可维护性与可扩充性。
8．提倡积极交流与讨论（同学间、bbs站点）、善于查阅资料、分析与借鉴他人编写的软件。
9．认真自觉以个人为单位完成自己的任务，代码和课设报告均严禁雷同，否则成绩为不及格。验收时查看代码，并提出若干个跟程序代码有关的问题，并把问题回答情况计入总评成绩。
10、根据不同的数据结构，要求有一种数据结构算法（冒泡排序算法不包括）。
五．工作阶段与考核方法
大体上可分成五个阶段：
1．资料查阅准备阶段（15%）
2．分析设计阶段（35%）
3．编程调试阶段（40%）
5．验收阶段
考核方法：
只有程序验收通过后，才能按以下方法核定本次课程设计的总成绩，因未能独立完成设计（尤其是抄袭）或概念不清的同学，总成绩将核定为不及格。总成绩由以下几个部分决定：
1．考勤、纪律、实验室卫生
2．工作量（代码量、功能多少、难度）
3．关键技术
4．实用性、创新
5．代码书写规范性
6．程序界面、新技术引用
7．课程设计报告（叙述、书写规范、字数）
8．动手能力、分析问题解决问题能力
六．任务具体要求
1、学生成绩管理系统
问题描述：该系统实现对若干个大学生的学习成绩进行管理。至少包括以下信息：
学号、姓名、科目、成绩，学期。学期取值范围可为1-8。
功能要求：
1．使用中文菜单，界面设计和用户输入输出要人性化些；
2. 将学生信息保存在文本文档中，具体对学生信息进行插入删除查询操作时，将保存在文本文
档中的学生信息提取出来，保存在自己定义的数据结构中，然后再对该数据结构进行操作，所有操作完成，或者在相应的命令后，再将学生信息保存到文本文档中。
3．具有数据输入功能，输入的数据能最终保存在文件中；
4．具有数据删除功能，能最终从文件中删除；
5．排序功能，根据自己设计的数据结构，设计排序算法
6．具有多种查询（如按学号查询、按姓名查询、按成绩查询等）及输出功能；
7．其它功能（如各种统计，统计每个学生所有课程的平均分，统计某门课程所有学生的平均分等等）
8．学生信息的修改（比如修改学生姓名，修改学生某门课程的成绩）
说明：
（1）功能各方面越完善越好
（2）自定义的数据结构可以使用数组，链表，树等，可以使用多种数据结构来存放数据，然后在其上使用不同的排序算法。
（3）若用数组，必须动态分配空间（文本文件中最好有一行表示学生人数）
算法要点：把问题看成是对线性表的操作。将学生成绩组织成顺序表，则登记学生成绩即是建立顺序表操作；查询学生成绩、插入学生成绩、删除学生成绩即是在顺序表中进行查找、插入和删除操作。
2、简易客房管理系统
问题描述：该系统能简单实现对客栈的住宿情况进行管理。至少包括以下信息：
房号、房型、单价（每床）、已住人数；
住客姓名、性别、年龄、身份、身份证号码，房号，床号，入住日期、入住时间、离店日期、
离店时间。
这些信息应存放在两个文件中，分别是客房信息文件、住客信息文件。“房型”可取值1-3，
分别表示单人间、双人间、通铺（可以住很多人的房间）
功能要求：
1．具有建立数据文件(客房信息文件、住客信息文件)功能；
2．具有数据输入功能；
3．具有数据修改功能；
4．具有数据删除功能；
5．能查询（查找）一些基本信息（如按房号查询、按姓名查询、空余客房查询等）；
6．具有多种统计功能（要求有一定的实用性）
（如某客房当前有那些空床、某住客应付多少费用、某天住店总人数和总收入等）
7．能具有排序功能（比如在查询所有的客房信息时，能根据房间价格进行排序，方便客人挑选房间等等）说明：
（1）功能各方面越完善越好
（2）自定义的数据结构可以使用数组，链表，树等，可以使用多种数据结构来存放数据，然后在其上使用不同的排序算法。
（3）若用数组，必须动态分配空间（文本文件中最好有一行来表示数组应该有多大，这样便于动态分配空间）
3、人事档案管理系统
问题描述：该系统能简单实现对人事档案的管理。
该系统包括: 人员基本情况管理、工资管理和考勤管理等几个方面的功能。用户通过输入工资、考勤、职工履历等基本信息,由系统自行生成相应的统计数据以供用户查询, 能对这些基本信息进行更新和删除。
至少包括以下信息：
人员履历表：员工编号，员工姓名，性别，年龄，部门，职位，受教育年限
职工工资表：员工编号，基本工资，缺勤扣发工资，扣税，实发工资
月考勤登记表：员工编号，月缺勤天数
注：假设每个员工每天缺勤扣发工资的多少跟其基本工资存在一定关系，比如是该基本工资的20分之一；假设扣税金额＝（基本工资－缺勤扣发工资－2000）×10％，而若基本工资－缺勤扣发工资－2000的值小于2000则扣税金额为0
功能要求：
1．具有建立数据文件(人员履历表文件、职工工资表文件、月考勤登记表)功能；
2．具有数据输入功能；
3．具有数据修改功能；
4．具有数据删除功能；
5．能查询（查找）一些基本信息（如按员工编号查询、按员工姓名和部门组合查询等，如生成各部门员工花名册）；
6．具有多种统计功能（要求有一定的实用性）
（如不同部门的员工平均工资比较（除了用数字表示外，也可以用星号画图的方式来直观的表示）；不同性别员工工资比较；某部门内部，不同职位员工工资比较；不同受教育水平人的平均工资比较；部门最高实发工资等等）
7．具有排序功能（比如将各部门职工工资平均值进行排序，将部门内部职工工资进行排序等等）
各个功能模块简要叙述（具体实现时，并不局限于这些功能，越完善越好）
?人员基本情况管理：提供对”人员履历表”数据输入、组合条件查询、统计功能；
?职工工资管理：提供对”职工工资表”数据的输入、查询、按统计、显示功能,完成每月对“职工工
资表”数据的月统计,以此生成“职工工资总额构成情况表”实现该表的查询、显示功能。
?职工考勤管理：提供对各部门“月考勤登记表”数据的录入、查询、统计功能；
说明：
（1）功能各方面越完善越好
（2）自定义的数据结构可以使用数组，链表，树等，可以使用多种数据结构来存放数据，然后在其上使用不同的排序算法。
（3）若用数组，必须动态分配空间（文本文件中最好有一行来表示数组应该有多大，这样便于动态分配空间）
4、进销存货物管理系统
问题描述：
该系统能进行简单的货物管理，进货，销售货物，退货等管理
至少包括如下信息：
货物标号，货物名称，货物产地，入库价格，入库时间，现存货物数量，已经销售数量，销售平均单价注：每次销售后，都需要对现存货物数量进行更新，对已销售数量进行更新，也需要对销售平均单价进行更新
功能要求：
1．具有建立数据文件(货物管理表)的功能；
2．具有数据输入功能；
3．具有数据修改功能；
4．具有数据删除功能（当一些已经过时陈旧的商品被特价处理后，将其删除，不再进货）；
5．能查询（查找）一些基本信息（如能查询剩余件数小于某个特定值的商品，以便于及时进货）；6．具有多种统计功能（要求有一定的实用性）
（如统计每种货物是否有盈利（将销售平均单价跟入库价格进行比较），所有货物的盈利或亏损等等）7．具有排序功能（比如对货物盈利水平进行排序比较等等）
说明：
（1）功能各方面越完善越好
（2）自定义的数据结构可以使用数组，链表，树等，可以使用多种数据结构来存放数据，然后在其上使用不同的排序算法。
空间）
5、图书管理系统
问题描述：
该系统能进行简单的图书管理功能
至少包括如下信息：
图书编号，图书名称，作者，出版社，总共册数，在馆册数，现存地址，借阅次数
注：现存地址是假设图书馆有多个书库，不同种类的书存放于不同的地方
功能要求：
1．具有建立数据文件(图书信息)的功能；
2．具有数据输入功能；
3．具有数据修改功能（借书或者还书都需要修改图书数量信息）；
4．具有数据删除功能（当图书因为年代久远，或者遗失，也许需要对其进行删除操作）；
5．能查询（查找）一些基本信息（这里的查询功能应该较为强大，能通过作者进行查询，书名查询，或者结合作者出版社一起进行查询等等）
6．具有多种统计功能（要求有一定的实用性）
（如统计每本书的借阅次数，方便将来新近图书。统计每个书库中图书的数量等等）
7．具有排序功能（比如对每本图书的借阅次数进行排序）
各个功能模块简要叙述（具体实现时，并不局限于这些功能，越完善越好）
?新近图书：在图书信息表中添加相应信息；
?旧书处理：在图书信息表中删除相应信息；
?借书还书：对图书信息表进行修改，若在馆册书为0，则不允许继续借阅；
?图书信息的统计
?图书信息的排序
?图书信息的查找
说明：
（1）功能各方面越完善越好
（2）自定义的数据结构可以使用数组，链表，树等，可以使用多种数据结构来存放数据，然后在其上使用不同的排序算法。
（3）若用数组，必须动态分配空间（文本文件中最好有一行来表示数组应该有多大，这样便于动态分配空间）
6、运动会分数统计
问题描述：参加运动会有n个学校,学校编号为1……n.比赛分成m个男子项目,和w个女子项目.项目编号为男子1......m,女子m+1......m+w.不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由同学自己设定。（m<=20,n<=20）功能要求：
1.可以输入各个项目的前三名或前五名的成绩；
2.能统计各学校总分；
3.可以按学校编号、学校总分、男女团体总分排序输出；
4.可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）
输出形式：有中文提示，各学校分数为整形
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。
7、民航订票系统
任务：通过此系统可以实现如下功能：
1．录入
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
2．查询
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况，最近一天航班的日期和余票额.；
3．订票业务;据顾客要求(航班号,订票额)查询该航班票额情况,若有余票,办理售票手续,输出座位号;若已满员或票额不足,则另询顾客要求.若需要,可预约登记排队等候.
4．退票业务:根据顾客情况(日期,航班)为顾客办理退票手续,然后查询该航班是否有人预约登记,首先询问排在第一位的顾客,若退票额能满足他的要求,则为他办理退票手续,否则依次询问其他排队预约的顾客.
5．修改航班信息：
当航班信息改变可以修改航班数据文件。
基本要求：
1．根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
2．界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
8、校园导游咨询
问题描述：设计校园导游程序，为来访的客人提供服务。
基本要求：
（1）假设有一所校园的平面图，所含景点不小于10个，请选择适当的坐标来表示出该图上的各个景点。；（2）为来访的客人提供从当前位置到其他景点的最短路径的咨询；
（3）必须具有校园平面图的修改和扩充功能（即某些景点坐标的修改和景点个数的增加）。
9、长整数的加减运算
问题描述：
基本要求：
利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是－（215－1）～（215－1）。输入输出形式：按照中国对于长整数的表示习惯，每四位是一组，组间用逗号隔开
更高要求：
（1）长整数的减法
（2）多个长整数的连续加减法，并带括号等。具体方式可以参见表达式的求值部分，利用栈
测试数据：
（1）0；0；应输出“0”
（2）－2345，6789；－7654，3211；应输出“－1，0000，0000”
（3）－9999，9999；1，0000，0000，0000；应输出“9999，0000，0001”
（4）1，0001，0001；－1，0001，0001；应输出“0”
（5）1，0001，0001；－1，0001，0000；应输出“1”
（6）－9999，9999，9999；－9999，9999，9999；应输出“－1，9999，9999，9998”
（7）1，0000，9999，9999；1；应输出“1，0001，0000，0000”
实现提示：
（1）每个结点中可以存放的最大整数为215－1＝32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数。整个链表是为万进制数。
（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。
10、表达式的求值
表达式求值要求：
例如，输入25*(12-27/3)+2*5=
则程序运行后输出25*(12-27/3)+2*5=85
设计要求：
以字符序列的形式从终端输入不含变量的算术表达式（整数和实数都要考虑），利用给定的算符优先关系，实现对算术四则混合运算表达式的求值，
基本要求：
（1）输入四则表达式（有括号和加减乘除，且表达式中有可能会出现带小数点的浮点数）；
（2）判断表达式是否合法（括号是否匹配）；
（3）按照运算符的优先级计算算术表达式的值。
更高要求：
（1）演示在求值过程中运算符栈、操作数栈的变化过程。
（2）判断表达式的语法是否正确（比如1＋＋2就是错误的）
11、钱币的转换
银行经常需要进行输入输出大小写的转换。要求：
出拾元贰角三分
（2）编写程序实现将中文表示的钱币数表示为阿拉伯数字表示的钱币数：比如输入三角，则输出0.3元
（3）需要注意：100000，中文表示是拾万元；0.3元表示为三角。希望大家把具体情况都能考虑清楚。
设计比较良好的用户提示界面。
12、二叉树的应用－哈夫曼树（电文的编码和译码）
哈夫曼编码/译码器
问题描述：设计一个哈夫曼编码/译码系统，对字符串进行编码/译码
基本要求：
（1）从键盘输入字符串，以回车结束；
（2）根据字符串中字符出现的概率进行哈夫曼编码；）
（3）并输出编码结果和编码表；
（4）根据编码结果和编码表还原字符串；
（5）输出编码过程中构造的哈夫曼树。
内容：理解二叉树的基本概念，并在读懂下面详细描述的算法的情况下，编写一个有关二叉树的简单应用程序－电文的编码和译码
具体实验题目和功能要求如下：
（1）电文编码：假如有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求出每个字符的哈夫曼编码
其中：得到的哈夫曼树和哈夫曼编码如下。
图1
要求自己编程实现若从键盘输入若干字符，同时并输入它们各自出现的频率，最后能计算并在屏幕上显示出每个字符的代码。
（2）电文译码：给出一段二进制代码的电文，要求根据前面构造的huffman树进行译码。在前面编码的基础上，键盘输入一段电文，则能在屏幕上显示出自动翻译好的电文。比如根据图1显示的哈夫曼树，键盘输入电文如下：1011010，屏幕上能显示自动翻译的结果为bed
说明事项：
2. 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。并要明确，只有在使用哈夫曼树进行编码的前提下，才有可能进行译码。
3.考虑将此程序设计完善，比如可以将编码后的字符代码保存到文件中，将需要翻译的代码保存到另一个文件中，最后把自动翻译后的结果也保存到文本文档中等等。
在这个程序中，首先要构造一棵哈夫曼树，然后才能根据这棵哈夫曼树构造编码。
因此，步骤一：构造哈夫曼树
步骤二：根据哈夫曼树为每个字符编码
步骤三：根据步骤二中构造好的哈夫曼树进行译码
提示：
具体算法见后面的有关哈夫曼树的基础知识介绍
部分代码（仅供参考）如下：
const int N=5;//叶子结点数目
const int TREENODENUM=2*N-1;//结点总数
//huffman 树结点的结构
typedef char dataType;
typedef struct
{
float weight;
dataType data;
int lchild,rchild,parent;
}huffmanTreeNode;
//哈夫曼编码的结构
typedef struct
{
char bits[N];//详细的编码，不过是反的，要从cnt 开始读
int cnt;//记录这个字符数由几位bit 表示的
dataType data;//编码要表示的字母
}codeType;
有关哈夫曼树的基础知识介绍
（1）哈夫曼树的定义
哈夫曼树：设有n 个权值{}12,,.....n w w w ，构造一棵有n 个叶子结点的二叉树，每个叶子结点的权值为i w ，则wpl 最小的二叉树叫哈夫曼树
1n
k k k wpl w l ==∑
其中：k w 为权值
l为结点到根到路径长度
k
n为叶子结点数
（2）构造Huffman树的方法——Huffman算法
构造Huffman树步骤如下：
①根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令其权值为wj
②在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和
③在森林中删除这两棵树，同时将新得到的二叉树加入森林中
④重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树
例如：
第一步：n棵只有根结点的二叉树，每个结点有相应代表的符号和权值
第二步：从中挑出权值最小的合并生成一棵新的树，置新生成的二叉树的根结点
第三步：不断重复第二步，直到只有一个根结点
第四步：最后完成一棵huffman树
哈夫曼树结点的存储结构
（3）哈夫曼树应用（哈夫曼编码）
哈夫曼树中没有度为1的结点，称为严格的二叉树。
哈夫曼编码：数据通信用的二进制编码
思想：根据字符出现频率编码，使电文总长最短
分支标“1”；每个字符的编码即为从根到每个叶子到路径上得到到0、1序列
例如：
要传输到字符集D＝｛C，A，S，T，；｝
字符出现频率w＝｛2，4，2，3，3｝
得到的哈夫曼树和哈夫曼编码为
（4）Huffman编码算法的基本思想
从叶子tree[i]出发，利用双亲地址找到双亲结点tree[p]，再利用tree[p]的lchild和rchild指针域判断tree[i]是tree[p]的左孩子还是右孩子，然后决定分配代码是“0”还是“1”，然后以tree[p]为出发点继续向上回溯，直到根结点为止
（5）Huffman译码算法的基本思想
从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束
13、银行排队系统模拟
假设某银行有n个窗口对外接待客户，从早晨银行9点开门起到5点关门，不断有客户进入银行，由于每个窗口在某个时刻只能接待一个客户。因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进银行的客户。如果某个窗口的业务员正空闲，则可上前输业务。反之，若个窗口均有客户所占，他便会排在为数最少的队伍后面。编制一个程序模拟银行的这种业务活动并计算一天中客户在银行的平均逗留时间。（提示：参考c++ primer plus中相关章节或者软件工程专业课表中的飞机场模拟）
14、文章编辑
功能：输入一页文字，程序可以统计出文字、数字、空格的个数。
静态存储一页文章，每行最多不超过80个字符，共N行；
要求
（1）分别统计出其中英文字母数和空格数及整篇文章总字数；
（2）统计某一字符串在文章中出现的次数，并输出该次数；
（3）删除某一子串，并将后面的字符前移。
输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：
（1）分行输出用户输入的各行字符；
（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"
（3）输出删除某一字符串后的文章；
上述要求只是基本要求，制作设计时需要添加自己的一些功能，比如可以实现类似记事本这样的应用程序，最好的还可以做成类似于nodepad++这样的程序。
15、车票管理系统
一车站每天有n个发车班次，每个班次都有一班次号（1、2、3…n），固定的发车时间，固定的路线（起始站、终点站），大致的行车时间，固定的额定载客量。如
班次发车时间起点站终点站行车时间额定载量已定票人数
1 8:00 郫县广汉
2 45 30
2 6:30 郫县成都 0.5 40 40
3 7:00 郫县成都 0.5 40 20
4 10:00 郫县成都 0.
5 40 2
…
（一）功能要求：用C/C++设计一系统，能提供下列服务：
（1）录入班次信息(信息用文件保存),可不定时地增加班次数据
（2）浏览班次信息,可显示出所有班次当前状态(如果当前系统时间超过了某班次的发车时间,则显示“此班已发出”的提示信息)。
（3）查询路线：可按班次号查询 ,可按终点站查询
（4）售票和退票功能
A：当查询出已定票人数小于额定载量且当前系统时间小于发车时间时才能售票，自动更新已售票人数
B：退票时，输入退票的班次，当本班车未发出时才能退票，自动更新已售票人数
注意：不可以使用数据库。必需使用文件进行读写操作。
上述功能仅为基本功能，需要自己根据实际情况进行功能上的添加和完善
游戏类
游戏类，即使是同一个名字，也有会有不同的规则，至于采用什么规则，可以在不违反游戏大原则的基础上，进行灵活设置。当然，最终的成绩，是会跟作出的效果挂钩的。因为是数据结构课程设计，所以，游戏类的设计实现时，需要考虑数据结构的设计，如果没有用到任何数据结构，则肯定是不及格的。
例子（参考）（C版）
功能：个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。
1．初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2．完成最低要求：建立一个文件，包括某人5个月的收支情况，能对文件中的信息进行扩充（追加），修改和删除；
3．进一步要求：完成对每月的开支排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。
要求：1）界面友好，函数功能要划分好
2）总体设计和流程图
3）程序要加必要的注释
4）要提供程序测试方案
5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
代码如下：
#include
#include
#include
#include
//文件保存路径
#define FilePath1 "Myinfor.dat"
#define FilePath2 "Myinfor.txt"
//查询用声明
#define Status int
#define OK 1
#define Error 0
#define NotFound 2
typedef struct {
int month;//月份
int spxf;//食品消费
int fzfy;//房租费用
int znjy;//子女教育费用
int sdfy;//水电费用
int ylfy;//医疗费用
int cxfy;//储蓄费用
int srfy;//收入费用
} Infor;
typedef struct {// 查询用自定义数据类型
int data;
}pType;
void menu(void); //菜单
void input(Infor *newI); //接收键盘输入
void writeinfor(Infor *newI);//向文件内写入内容
void changeFormat(void );//将dat格式文件转换为txt文件
Status search(Infor *a);//查询函数[返回查询的结果及查询的状态]
void paixu(Infor *a);//对查询据结果排序
void modify(Infor *a,int mon);//修改数据
void delRecord(int mon);//删除数据
void main()
{
while(1)
{
menu();
}
}
void menu(void)
{
int item;
int mon;
Infor *a;
a=(Infor *)malloc(sizeof(Infor));
do{
printf("\n…………个人帐簿管理系统设计【*****制作】…………\n\n"); printf("\t\t1.录入数据。\n");
printf("\t\t2.查看数据。\n");
printf("\t\t3.修改数据。\n");
printf("\t\t4.查询数据。\n");
printf("\t\t5.排序数据。\n");
printf("\t\t6.删除数据。\n");
printf("\t\t0.退出系统。\n\n");
printf("请输入要进行的操作: " );
scanf("%d",&item);
}while(item>6 || item<-1);
switch(item)
{ //退出程序
case 0: getchar();
getchar();
break;
//录入数据
case 1: input(a);
writeinfor(a);
break;
//查看数据
case 2: changeFormat();
break;
//修改数据
case 3: item=search(a);
mon=a->month;
if (item!=OK) printf("\n没有符合条件的记录!\n");
else
{
printf("\n记录月份食品消费房租费用子女费用水电费用医疗费用储蓄费用本月收入 \n");
printf("----------------------------------------------------------------------- \n");
printf("%7d %8d %8d %8d %8d %8d %8d %8d\n",a->month,a->spxf,a->fzfy,a->znjy,a->sdfy,a->ylf y,a->cxfy,a->srfy);
input(a);
modify(a,mon);
}
break;
//查询数据
case 4: item=search(a);
if (item!=OK) printf("\n没有符合条件的记录!\n");
else{
printf("\n记录月份食品消费房租费用子女费用水电费用医疗费用储蓄费用本月收入 \n");
printf("----------------------------------------------------------------------- \n");
printf("%7d %8d %8d %8d %8d %8d %8d %8d\n",a->month,a->spxf,a->fzfy,a->znjy,a->sdfy,a->ylf y,a->cxfy,a->srfy);
}
break;
//排序数据
case 5: item=search(a);
if (item!=OK) printf("\n没有符合条件的记录!\n");
else
paixu(a);
break;
//删除数据
case 6:
item=search(a);
mon=a->month;
if (item!=OK) printf("\n没有符合条件的记录!\n");
else
{
printf("\n记录月份食品消费房租费用子女费用水电费用医疗费用储蓄费用本月收入 \n");
printf("----------------------------------------------------------------------- \n");
printf("%7d %8d %8d %8d %8d %8d %8d %8d\n",a->month,a->spxf,a->fzfy,a->znjy,a->sdfy,a->ylf y,a->cxfy,a->srfy);
delRecord(mon);
}
break;
}
free(a);//释放内存空间
}
void input(Infor *newI)
{
printf("\n请依次输入数据[说明:中间以空格符隔开]:\n(本月月份食品消费房租费用子女费用水电费用医疗费用储蓄费用收入费用)\n");
scanf("%d%d%d%d%d%d%d%d",&newI->month,&newI->spxf,&newI->fzfy,&newI->znjy,&newI->sdfy,&new I->ylfy,&newI->cxfy,&newI->srfy);
fflush(stdin);
}
void writeinfor(Infor *newI)
{
FILE *fp;
fp=fopen(FilePath1,"ab+");
{
printf("无法创建文件：%s",FilePath1);
exit(0);
}
fwrite(newI,sizeof(Infor),1,fp);//这里可以做特别处理可防止存在同一月份有2条以上的记录问题。这里就不写了。
fclose(fp);
printf("数据录入成功！\n");
}
void changeFormat(void) //暂时只能操作一行文件有待改进
{
FILE *fp1,*fp2;
Infor *a;
a=(Infor *)malloc(sizeof(Infor));
fp1=fopen(FilePath1,"rb+");
if(fp1==NULL)
{
printf("无法找到文件：%s\n",FilePath1);
return ; //返回主函数
}
fp2=fopen(FilePath2,"wt+");
if(fp2==NULL)
{
printf("无法创建文件：%s\n",FilePath2);
return ; //返回主函数
}
fputs(" \n……………………………………个人帐簿管理系统……………………………………\n\n",fp2);
fputs("记录月份食品消费房租费用子女费用水电费用医疗费用储蓄费用本月收入\n",fp2);
fputs("-----------------------------------------------------------------------
\n",fp2);
printf("\n记录月份食品消费房租费用子女费用水电费用医疗费用储蓄费用本月收入\n");
printf("----------------------------------------------------------------------- \n");
rewind(fp1);
fread(a,sizeof(Infor),1,fp1);
while(!feof(fp1))
{
printf("%7d %8d %8d %8d %8d %8d %8d %8d\n",a->month,a->spxf,a->fzfy,a->znjy,a->sdfy,a->ylf y,a->cxfy,a->srfy);
fprintf(fp2,"%7d %8d %8d %8d %8d %8d %8d %8d\n",a->month,a->spxf,a->fzfy,a->znjy,a->sdfy,a ->ylfy,a->cxfy,a->srfy);
fread(a,sizeof(Infor),1,fp1);
}
fputs("-----------------------------------------------------------------------
\n",fp2);
fputs("关闭本程序继续原程序！\n",fp2);
fclose(fp1);
fclose(fp2);
system(FilePath2); //调用打开转换的文本文件
remove(FilePath2);//删除文本文件文件
}
Status search(Infor *a)
{
FILE *fp1;
int mon;
int isfound=0;
printf("请正确输入要查询的月份：");
scanf("%d",&mon);
fflush(stdin);
fp1=fopen(FilePath1,"rb+");
if(fp1==NULL)
{
printf("无法找到文件：%s\n",FilePath1);
return Error; //返回主函数
}
rewind(fp1);
fread(a,sizeof(Infor),1,fp1);
while(!feof(fp1))
{
if(a->month==mon)
{
isfound=1;
实验报告 课程名称:数据结构与算法 实验名称:树的应用 一、实验目的 ⑴、掌握二叉树的静态数组存放。 ⑵、掌握哈夫曼编码的基本概念。 ⑶、掌握哈夫曼编码树的构造方法。 ⑷、掌握哈夫曼编码的构造和使用。 ⑸、理解前缀编码的概念。 二、实验内容 ⑴、按照字符出现概率构造一个哈夫曼树。要求输入为一个文本文件（可以限 制文本仅仅包含字母），通过统计字符出现的次数计算概率，在此基础上构造哈夫曼树。 ⑵、打印出每一个字母对应的哈夫曼编码。 三、实验环境 硬件：Windows XP计算机、鼠标、键盘、显示器 开发环境：Microsoft Visual C++ 6.0 四、实验步骤 ①、点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入5.cpp,再点击确定. ②、编写程序如下： #include
数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：
（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满
《数据结构与算法设计》 实验报告 ——实验二 学院：自动化学院 班级： 学号： ： 一、实验目的
按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。 二、实验容 简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： ①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取 整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 概要设计 1、宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 2、基本函数： （1）void InitStack_char(SqStack *S) //char型栈初始化 （2）void InitStack_int(sqStack *S) //int型栈初始化 （3）void Push_char(SqStack *S,char ch) //char型元素进栈 （4）void Push_int(sqStack *S,int num) //int型元素进栈 （5）char GetTop_char(SqStack *S) //取char型栈顶元素 （6）int GetTop_int(sqStack *S) //取int型栈顶元素 （7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回 （8）char Precede(char a,char b) //判断两运算符的先后次序 （9）Status Pop_char(SqStack *S,char &x) //char型栈出栈 （10）Status Pop_int(sqStack *S,int &x) //int型栈出栈 （11）int Operate(int a,char theta,int b) //计算a和b运算结果 3、流程图
《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列, 西安科技大学 2013年硕士研究生入学考试试题A ───────────────────────────────── 科目编号：824 科目名称： 数据结构与算法设计 考生须知： 1、 答案必须写在答题纸上，写在试题或草稿纸上不给分。 2、 答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。 3、 答题必须写清题号，字迹要清楚，卷面要保持整洁。 4、 试题要随答题纸一起交回。 一、单项选择题（每小题2分，共30分） （1）并归排序的时间复杂度是（ ）。 A ．O(n 2) B ．O(nlog 2n) C ．O(n) D ．O(log 2n) （2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（ ）存储结构最节省时间。 A ．单链表 B ．单循环链表 C ．带尾指针的单循环链表 D ．带头结点的双循环链表 （3）散列文件是一种（ ）。 A ．顺序文件 B ．索引文件 C ．链接文件 D ．计算机寻址文件 （4）常用于函数调用的数据结构是（ ）。 A ．栈 B ．队列 C ．数组 D ．链表 （5）两个矩阵sn ms B A ,相乘的时间复杂度是（ ）。 A ．O(n 2) B ．O(s 2) C ．O(msn) D ．O(mn) （6）图的广度优先搜索遍历使用的数据结构是（ ）。 A ．栈 B ．队列 C ．集合 D ．树 （7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（ ）。 A ．直接前驱 B ．直接后继 C ．开始结点 D ．终端结点 （8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（ ）。 A ．O(n 2) B ．O(1) C ．O(n) D ．O(log 2n) （9）在链队列中执行入队操作，（ ）。 A ．需判断队是否为空 B ．限定在链表头p 进行 C ．需判断队是否为满 D ．限定在链表尾p 进行 （10）对序列（95，83，62，70）进行冒泡排序（由小到大），第2趟排序后的结果为（ ）。 A ．（70，83，62，95） B ．（70，62，83，95） 四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号： 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A．O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（） A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 】 13．以下哪个数据结构不是多型数据类型（）】 A．栈B．广义表C．有向图D．字符串 14．以下数据结构中，（）是非线性数据结构】 2.3 课后习题解答 选择题 1、A 2、A 3、D 4、C 5、D 6、B 7、C 8、B 9、A 10、D 11、B 12、D 2.3.2 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 2.3.3 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } 北京交通大学考试试题（A卷） 课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为 的数据结构。 2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。 3. 直接插入排序用监视哨的作用是。 4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算 是。 5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有。 6. 在AOV网中，顶点表示，边表示。 7. 有向图G可进行拓扑排序的判别条件是。 8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行 Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。 二、选择题（每空2分，共20分） 1.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法 2.查找n个元素的有序表时，最有效的查找方法是（）。 A．顺序查找B．分块查找 C．折半查找D．二叉查找 3.将所示的s所指结点加到p所指结点之后，其语句应为（）。 p (A) s->next=p+1 ; p->next=s; (B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s; 4. 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。 A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数 5. 算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵A 是一个对称矩阵，为了节省存储，将其 下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下，查找成功的平均查找长度是（ ）。 A ．29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为 （ ）。 A ．5 B ．6 C ．7 D ．8 三、 判断题（10分，每小题1分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 2. 数组不适合作任何二叉树的存储结构。（ ） 3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（ ） 4. 在含有n 个结点的树中，边数只能是n-1条。（ ） 5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（ ） 6. 简单选择排序在最好情况下的时间复杂度为O(n)。（ ） 7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ） 8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置 空，因为这会影响以后的查找。（ ） 9. 有n 个数存放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无 ?????? ? ???? ? ??=n n n n a a a a a a A ,2,1,2 ,21,21 ,1Λ Λ 《数据结构与算法分析》课程设计教学任务书 一、课程设计的目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二、课程设计的基本要求 1. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计： 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） c）详细设计： 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释 d）调试分析： 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些，问题如何解决？），算法的改进设想 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“09201199王五”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收 国家二级MS Office高级应用机试（数据结构与算法）模拟试卷 8 (总分：56.00，做题时间：90分钟) 一、选择题(总题数：28，分数：56.00) 1.下列结构中属于线性结构链式存储的是 （分数：2.00） A.双向链表√ B.循环队列 C.二叉链表 D.二维数组 解析：解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。 2.下列叙述中错误的是 （分数：2.00） A.循环链表中有一个表头结点 B.循环链表的存储空间是连续的√ C.循环链表实现了空表与非空表运算的统一 D.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 解析：解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。 3.度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为 （分数：2.00） A.14 B.15 √ C.16 D.不可能有这样的树 解析：解析：根据题目可知本树中还有度为2的结点。树的总结点＝(度1*个数＋度2*个数…)＋1，这里我们设度为2的结点数为x，那么30＝3*3＋2*x＋1*4＋1＝2*x＋14，由此可计算出x＝8。树的叶子结点数等于总结点减去所有度不为0的结点，也就是30－3－8－4＝15。 4.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为 （分数：2.00） A.7 √ B.96 C.48 D.6 解析：解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式：k＝log 2 n。其中n代表长度，k为比较次数。本题中可以计算出k＝7。 5.下列结构中属于非线性结构的是 （分数：2.00） A.二叉链表 B.二维数组√ C.循环队列 2.3 课后习题解答 2.3.2 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 2.3.3 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } } 时间复杂度为O(n)。 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 学院 《数据结构与算法》之实际应用 二零一三年三月十三日 目录 数据结构与算法在实际中的应用 (2) 摘要： (2) 一、定义：............................ 错误！未定义书签。 二、在各领域中的实际应用.............. 错误！未定义书签。 （一）、排队叫号系统（尾插法） (2) （二）、搜索引擎与数据结构算法 (4) （三）、图论应用 (5) （四）、最小生成树在城市高速公路问题中的应用 (5) 三、小结 (6) 四、参考文献 (6) 小组成员： 数据结构与算法在实际中的应用 摘要： 计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理。何为信息，信息就是大量的数据，需要对大量的数据进行处理。进而我们需要《数据结构与算法》这门课作为基础，去发展计算机学科。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。通过《数据结构与算法》的学习，我们能够解决很多学科问题、生活实际问题。 一、定义 《数据结构与算法》应该包括两个部分：数据结构、算法。 数据结构在计算机科学界至今没有标准的定义。根据各自的理解的不同而有不同的表述方法，数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用时间复杂度和空间复杂度衡量。 二、在各领域中的应用 在我们的日常生活中，应用到数据结构的地方有很多地方，实例到处都是，比如说，做搜索引擎，对字符串的各种查找、索引的算法就有很高要求；做人工智能，对模式识别、搜索的要求就很高；做数据库设计，对字典、内外排序、搜索与索引以及数据的连接方式都有很高要求；做通讯密码，对数论、Fourier分析有要求等等。 （一）、排队叫号系统（尾插法） 数据结构包含数的操作,排序和查找等一系列问题。其中，排序的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的排列。数据结构的排序有5种。 常用的大数据结构与算法 在学习了解这些数据结构和算法之前，引用一位前辈的话： “我们不需要你能不参考任何资料，实现红黑树；我们需要的是你能在实践当中，选择恰当的数据结构完成程序开发；在必要的时候，能在已有的数据结构基础上进行适当改进，满足工程需要。但要做到这一点，你需要掌握基础的算法和数据结构，你需要理解并应用一些高级数据结构和算法的思想。因此，在程序员这条道路上，你要想走得更远，你需要活用各种数据结构，你需要吸收知名算法的一些思想，而不是死记硬背算法本身。” 那么，工程实践当中，最常用的算法和数据结构有哪些？ 以下是Google工程师Arjun Nayini在Quora给出的答案，得到了绝大多数人的赞同。 最常用的算法 1.图搜索算法(BFS,DFS) 2.排序算法 3.通用的动态规划算法 4.匹配算法和网络流算法 5.正则表达式和字符串匹配算法 最常用的数据结构 1.图，尤其是树结构特别重要 2.Maps结构 3.Heap结构 4.Stacks/Queues结构 5.Tries树 其他一些相对比较常用的数据算法还有：贪心算法、Prim’s / Kruskal’s算法、Dijkstra’s 最短路径算法等等。 怎么样才能活用各种数据结构？ 你能很清楚的知道什么时候用hash表，什么时候用堆或者红黑色？在什么应用场景下，能用红黑色来代替hash表么？要做到这些，你需要理解红黑树、堆、hash表各有什么特性，彼此优缺点等，否则你不可能知道什么时候该用什么数据结构。 常言道： 程序=算法＋数据结构 程序≈数据结构 小编希望这些算法的掌握能够帮助大家拓宽握数据结构和算法的视野，提高算法设计和动手编程的能力。 数据结构与算法课程设计报告 题目 两两相连的房间问题： 一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？ 问题分析 此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。 实现本程序需要解决以下问题： 1.如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。 2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。 3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。 4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只 访问未走过的房间。 5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。 数据结构的选择和概要设计 通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a 房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。 对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。 选择题： 1、在数据结构中，线性结构中元素之间存在____关系。 A: 一对一 B: 一对多 C: 多对一 D: 多对多 2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的____和运算等的学科。 A: 结构 B: 关系 C: 操作 D: 算法 3、算法分析的两个主要方面是____。 A: 空间复杂度和时间复杂度 B: 正确性和简明性 C: 可读性和文档性 D: 数据复杂性和程序复杂性 4、顺序表中逻辑上相邻的节点其物理位置也____。 A: 一定相邻 B: 不必相邻 C: 按某种规律排列 D: 无要求 5、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。 A: s->next=p->next; p->next=s; B: p->next=s->next; s->next=p; C: q->next=s; s->next=p; D: p->next=s; s->next=q; 6、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是____。 A: edcba B: decba C: dceab D: abcde 7、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。 A: (rear-front+m)%m B: rear-front+1 C: rear-front-1 D: rear-front 8、关于空格串，下列说法中正确的有____。 A: 空格串就是空串 B: 空格串是零个字符的串 C: 空格串的长度为零 D: 空格串的长度就是其包含的空格个数 9、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为____。A: SA+140 B: SA+144 C: SA+222 D: SA+225 10、对于一棵满二叉树，m个树叶，n个节点，深度为h，则____。 A: n=h+m B: h+m=2n C: m=h-1 D: n=2h-1 11、具有65个结点的完全二叉树其深度为____。（根的层次号为1） A: 8 B: 7 C: 6 D: 5 12、满二叉树____二叉树。 A: 一定是完全 B: 不一定是完全 C: 不是 D: 不是完全 13、将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为____。 A: 99 B: 98 C: 50 D: 48 14、如果T2是由森林T转换而来的二叉树，那么T中结点的后序遍历就是T2中结点的____。A: 先序遍历 B: 中序遍历 C: 后序遍历 D: 层次遍历 15、将递归算法转换成对应的非递归算法时，通常需要使用____。 A: 栈 B: 队列 C: 链表 D: 树 16、如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为____。 A: uwvts B: vwuts C: wuvts数据结构与算法知识点必备
824数据结构与算法设计A
计算机学院数据结构与算法分析期末试题(2007级B)_无答案
数据结构与算法各章试题
数据结构与算法第二版2-4章答案
北京交通大学数据结构与算法期末测验考试参考答案
天津科技大学数据结构与算法课程设计
国家二级MS+Office高级应用机试(数据结构与算法)模拟试卷8
《数据结构与算法》课后习题答案
数据结构与算法设计知识点
数据结构与算法实际应用
常用的大数据结构与算法
数据结构与算法课程设计程序与报告
数据结构与算法上海第二工业大学二工大期末考试试卷
相关主题
文本预览