2015-2016第2学期数据结构大作业题目
《数据结构大作业》要求
一、作业目的
1、掌握用数据结构的知识进行C++程序设计。
2、应用所学的数据结构完成一个具有一定实际意义的应用程序的设计、编码、调试，锻炼
实践动手能力，提高编程水平。
二、作业内容
1、图书管理系统
问题描述：实现图书管理系统，主要为图书管理员和借阅者提供管理和查询服务。
基本功能要求：
程序必须采用链表数据结构实现。
图书信息至少包括以下信息：书名，ISBN、作者、出版社、出版时间，入库时间，库存量（图书馆购买此书的数目），借阅数（被借阅的本数）。
图书管理员身份可以完成以下操作：
（1）录入：增加一本图书信息；
（2）删除：删除某一本图书的信息；
（3）修改：修改某一本图书的信息；
（4）查询：根据书名或图书ISBN等查询图书信息（可选择：简单条件查询，组
合条件查询等）。
（5）排序：根据书名或入库时间等信息进行排序，尽可能提高查找和维护性能；
（6）借书：借出一本书，该书的借阅量增加一本。
（7）还书：还回一本书，该书的借阅量减少一本。
（8）统计：统计所有的借出的图书数目，即：所有图书借阅量之和。
（9）输出：输出所有图书的所有信息，要求格式清晰，方便查看。
扩展功能要求：
（1）导入：把用户信息从文件读入程序；
（2）导出：把用户信息导出到文件中保存；
2、学生管理系统
必须完成学籍登记表中的下面功能。
登记表中包括：学号、姓名、班级（如：14级软件1班）、性别、手机号码、选修课程等信息。
程序必须采用链表数据结构实现；
（1）插入：将某学生的基本信息插入到登记表中；
（2）删除：将满足条件的基本信息删除；
（3）修改：对基本信息的数据项进行修改；
（4）查询：查找满足条件（学号或姓名等字段）的学生；
（5）排序：根据学生信息（例如：学号或电话号码等）进行排序，尽可能提高查找和维护性能；
（6）增加课程信息（如：课程名、课程编号、开课学期等信息）管理（增加、删除和查找和输出，不限存储结构）；
（7）实现学生的选课功能（学生选择一门课后，该课程信息会出现在该生“选修课程”）；
（8）输出：将登记表中的所有学生的（或满足条件）信息全部输出，要求格式清晰，方便查看。
扩展功能要求：
（1）导入：把用户信息从文件读入程序；
（2）导出：把用户信息导出到文件中保存；
3、家谱管理系统
问题描述：家谱用于记录某家族历代家族成员的情况与关系。本系统要求能对家谱进行存储、更新、查询、统计等操作。
基本功能要求：
程序必须采用树形数据结构实现。
（1）录入：录入家庭成员信息，家庭成员的基本信息包括：（姓名，性别，出生日期，死亡日期，职业等）。各家庭成员之间的关系，以树形结构存储；
（2）修改：修改成员信息；
（3）删除：删除成员信息（删除某成员必须把其子孙全部删除）；
（4）输出：将家谱以较友好的格式输出（显示）；
（5）查询：按基本信息查询成员。
（6）统计：统计并显示结果，统计的项目可以包括（平均寿命、男女比例等）；
扩展功能要求：
（1）导入：把用户信息从文件读入程序；
（2）导出：把用户信息导出到文件中保存；
三、作业要求
1、选题：从3个题目中任选其一，独立完成。选做第2和3个题目的将得到较高的分数。
2、程序代码要求：程序要求能够正常运行，基本功能必须全部实现。完成可选做的扩展功
能将得到较高的分数。容错性强和功能细节考虑更完全也将得到较高的分数。
3、开发语言：C++;开发平台：vc++6.0或Visual studio。
四、提交要求
1、每位同学必须把源程序和设计说明书电子版提交到：ftp://10.5.1.5
每位同学的作业放在一个文件夹中提交，文件夹按以下格式命名：“班内序号+姓名”
14软件1班：提交到王方丽老师（办公室：B1-310）的“/上传/数据结构大作业”
文件夹中。
用户名：wang 密码：wang
数据结构大作业提交截止日期：:学委联系指导老师。
14软件2班：提交到张伟娜老师（办公室：B1-311，办公电话：36903374）的“/
上传/数据结构大作业”文件夹中。
用户名：zhangweina密码：zhangweina
数据结构大作业提交截止日期：开学后第六周周五之前
14信息1班：提交到李妍老师（办公室：B1-312，办公电话：36903372）的“/
上传/数据结构大作业-14信息1班”文件夹中。
用户名：li 密码：li
数据结构大作业提交截止日期：开学后第六周周五之前
每位同学必须提交数据结构大作业设计说明书打印版（不少于3000字）。（学习委员收齐后按序号排好序交到指导老师办公室）
2、独立完成，不得抄袭，凡是发现抄袭的（无论抄与被抄者），均不及格。
3、大作业提交后根据程序和说明书情况进行答辩，答辩名单和答辩时间另行通知。
五、评分标准：
程序50%，程序设计说明书50%（程序说明书不能说明问题的参考答辩情况）。
六、数据结构大作业设计说明书内容要求：
1. 封面：要求写明课程、题目名称、学院、专业班级、年级、姓名、学号、班内序号（见
下页）。
2. 概述：开发环境、用到的基本原理或技术、需求说明等。
3. 程序概要设计：各种功能完成的详细情况（已经实现了哪些功能，哪些功能未实现或有
什么bug）、程序流程是什么（流程图）等。
4. 程序详细设计：各种功能的实现方法描述、关键代码分析（要用文字描述，描述过程中
可以在文字中穿插少量代码，但不要贴大段的代码）。
5. 使用情况：展示各种功能的运行情况（必须有截图说明）。
6. 总结：分析程序的优点和不足、开发时遇到的困难及解决的问题、总结。
7. 参考文献。
七、格式要求：
一级标题（小三宋体，1.5倍行间距）
二级标题（四号宋体，1.2倍行间距）
正文格式：5号宋体，单倍行间距
其他格式说明：
1.标题中除了“、”和“.”之外不允许出现其他标点符号；
2.每段段首缩进两个字符；
3.文档可以不要目录，如果有目录一定是自动生成的目录；
4.如果有图，图标题放在图的下面。
封面格式：见下页。
成绩：
评语：
华南理工大学广州学院2015-2016学年度第2学期
课程名称：数据结构大作业
题目：
专业班级：
年级：
姓名：
学号：
班内序号：
数据结构书面作业练习题
习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o
A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序
列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为
数据结构第1章作业
第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]对换；
数据结构大作业含源代码
数据结构大作业 作业题目：职工信息管理系统 姓名： 学号： 班级: 指导教师: 日期：
一、主要功能： 这个职工信息管理系统是由C语言编写的程序，它用起来很方便又很灵活。它由输入职工信息，输出职工信息，按职工号，部门号，工资排序，按职工号，部门号，工资来输出职工的所有信息。删除有关职工的所有信息，保存职工的所有信息并退出等11个模块儿组成。 二、实验环境：C语言、C++、C# 等等。 三、功能说明： 下面按步骤来介绍一下，职工信息管理系统的基本操作。 这是运行程序以后出现的主界面。如图（1）所示： 图（1）主界面 1.输入职工的信息 该模块儿的功能是分别输入职工的姓名，职工号，部门号，工资等信息。每次输入职工的所有信息以后，界面上会显示出《输入完成！》的命令。如图（2）所示：
图（2）输入职工信息 2.输出所有的职工信息 该模块儿的功能是显示出有关职工的所有信息。操作如图（3）所示： 图（3）输出所有的职工信息 3.按职工号排序 该模块儿的功能是按职工号排序所有的职工。我们按3的时候，界面上会显示出《排序完成！》的命令。如图（4）所示：
图（4）按职工号排序 4.输出所有的职工号码 该模块儿的功能是显示出已排序好的所有职工的号码。操作如图（5）所示： 图（5）输出所有的职工号 5.按部门号排序 该模块儿的功能是按部门号排序所有职工的部门号。我们按5的时候，界面上会显示出《排序完成！》的命令。如图（6）所示：
图（6）按部门号排序 6.输出所有的部门号 该模块儿的功能是显示出已排序好的所有部门号。操作如图（7）所示： 图（7）输出所有的部门号 7.按职工的工资排序 该模块儿的功能是按工资排序所有职工的工资。我们按7的时候，界面上会显示出《排序完成！》的命令。如图（8）所示：
数据结构第二章课后习题题解
2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i]
} } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 0980 输出利用先序遍历创建的二叉树的层次遍历序列（中）#include while(fornt != rear) { fornt = (fornt+1)%100; p = q[fornt]; cout< 数据结构大作业报告 数据结构大作业实验报告课程名称:数据结构设计题目:客户去银行储蓄模拟程序一( 实验题目 (1)内容描述:编写一个程序反映客户到银行储蓄的过程。 (2)基本要求:要实现以下功能:1:排队 2:储蓄 3:查看排队4.:删除自己所排的队 5.不再排队,剩下的客户依次储蓄 6:下班 二( 实验的工程组成图和程序结构图 main bank 本工程的组成结构如左图所示,程序结构图如右图所示。三( 工程所包含的函数的功能描述 Bank():模拟客户到银行去储蓄的过程。客户排队储蓄，所以要用到一个队列， 这里设计了一个不带头结点的单链表作为队列。 四( 实验工程的算法描述及流程图 //客户排队去银行储蓄,用到了队列的知识,这里设计了一个不带头结点的单链表作为队列来完成排队储蓄过程 #include #include 第二章习题 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。× 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。×9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。× 11.线性表中每个元素都有一个直接前驱和一个直接后继。（×） 12.线性表中所有元素的排列顺序必须由小到大或由小到小。（×） 13.静态链表的存储空间在可以改变大小。（×） 14.静态链表既有顺序存储结构的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 15.静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。（） 16.静态链表与动态链表的插入、删除操作类似，不需要做元素的移动。（） 17.线性表的顺序存储结构优于链式结构。（×） 18.在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。（×） 19.在单链表中，可以从头结点开始查找任何一个结点。（） 20.在双链表中，可以从任何一结点开始沿同一方向查找到任何其他结点。（×） 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 ，在任何位置上插入或删除操作都是等概率的。插n．对顺序存储的线性表，设其长度为2． 入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) （n -1）/2 (D) n 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 数据结构实验讲义 一实验步骤 随之计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10，000行的程序的难度绝不仅仅是一个5，000行的程序两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如(从实际问题中提出来的)一个“真正的，，软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的五个步骤：’ (一)问题分析和任务定义 通常，实习题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。注意：本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输入?对非法输入的回答方式是什么等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。 (二)数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的规格说明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类c语言写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。 (三)编码实现和静态检查 编码是把详细设计的结果进一步求精为程序设计语言程序。程序的每行不要超过60个字符。每个函数体，即不计首部和规格说明部分，一般不要超过40行，最长不得超过60行，否则应该分割成较小的函数。要控制if语句连续嵌套的深度。其他要求参见第一篇的 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 数据结构与算法分析课程设计报告 课题名称： A Text Editor Imlementation 提交文档学生姓名：苟丁 提交文档学生学号： 0843042229 同组成员名单：无 指导教师姓名：孙界平 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2010 年 5 月 7 日 1. 实验题目:带括号的算术表达式求值 2. 实验的目的和要求: 1.采用C++的ASCII码文件和串函数实现; 2.熟练掌握串运算的应用; 3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一 个C++程序; 4.上机调试程序,掌握查错、排错使程序能正确运行 3.实验的环境: 1、硬件环境：联想笔记本电脑，Intel(R) Pentium(R) Dual T3400 ，2GB内存 2、软件环境：Windows XP 下的Microsoft Visual Studio 2008 4.算法描述: ●具体操作与函数描述 （1）编辑一个文本文件，命名为text.txt. （2）函数run()提供给用户选择符的输入：w,r,I,d,f,c,q,h,n,p,b,e,g,v. 用户可以选择H选择符寻求帮助，得知操作符分别代表的动作。 （3） R代表函数Read()将文本读入缓冲区，缓冲区以前的任何内容都将将消失。 （4） W代表函数Write()将缓冲区的内容写入文本文件。 （5） I代表函数Insert（）插入新行，用户可以在适当的提示下键入新行并提供新行。 （6） D代表delete()行数所执行的删除操作，可以删除当前行，并进入下一行。 （7） F代表函数findChar(),用于查找目标行。 （8） C代表函数changLine(),将用户请求的字符串修改成用户请求的替换文本，可选择的是仅在当前行中有效。 （9） Q代表函数quit(),用户执行此命令可以退出编辑。 （10）N代表函数next(),用户可以从当前行移到下一行。 （11）P代表函数pre(),用户可以从当前行移到下一行。 （12）E代表end(),可以移到最后一行。 （13）G代表go(),用户可以指定到选择的行。 （14）V查看缓冲区的全部内 ●测试程序说明： 第1章绪论 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链式存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 ⑷下面（）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 ⑸算法分析的目的是（），算法分析的两个主要方面是（）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性H 数据复杂性和程序复杂性 3. 判断题 （1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 （2）每种数据结构都具备三个基本操作：插入、删除和查找。 （3）逻辑结构与数据元素本身的内容和形式无关。 （4）基于某种逻辑结构之上的基本操作，其实现是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。 数据结构课程设计课题名称 专业名称 学生姓名 学号+电话 指导教师 评分细则 目录 评分细则----------------------------------------------------------------------------------------------------------------- 2 一、课题描述 ---------------------------------------------------------------------------------------------------------- 4 二、需求分析 ---------------------------------------------------------------------------------------------------------- 4 2.1 ------------------------------------------------------------------------------------------------------------------ 4 2.2- ------------------------------------------------------------------------------------------------------------------4 2.3--------------------------------------------------------------------------------------------------------------------4 三、概要设计 ---------------------------------------------------------------------------------------------------------- 4 3.1 结构分析 ----------------------------------------------------------------------------------------------------------- 4 3.2函数------------------------------------------------------------------------------------------------------------ 4 3.2.1 malloc() --------------------------------------------------------------------------------------------- 4 3.2.2getchar() ----------------------------------------------------------------------------------------------------- 5 3.2.3 list_create() ------------------------------------------------------------------------------------------------ 5 3.2.4 list_disp() --------------------------------------------------------------------------------------------------- 5 3.2.5 list_sort() --------------------------------------------------------------------------------------------------- 5 四、详细设计 ---------------------------------------------------------------------------------------------------------- 5 4.1课题分析 ----------------------------------------------------------------------------------------------------- 5 4.1.1选择 ------------------------------------------------------------------------------------------------- 5 4.1.2冒泡 --------------------------------------------------------------------------------------------------------- 5 4.1.3 堆------------------------------------------------------------------------------------------------------------ 6 4.1.4 快速--------------------------------------------------------------------------------------------------------- 6 4.1.5 基数--------------------------------------------------------------------------------------------------6 4.1.6 希尔--------------------------------------------------------------------------------------------------------- 6 4.1.7 归并--------------------------------------------------------------------------------------------------6 4.2课题实现 ----------------------------------------------------------------------------------------------------- 7 五、测试数据及结果------------------------------------------------------------------------------------------------- 9 六、调试分析及总结----------------------------------------------------------------------------------------------- 10 2011年12月考试数据结构第二次作业 一、单项选择题（本大题共100分，共 25 小题，每小题 4 分） 1. 树型结构是数据元素之间存在一种：( ) A. 一对多关系 B. 多对多关系 C. 多对一关系 D. 一对一关系 2. 以下的排序算法属于稳定排序算法的是（） A. 基数排序 B. 快速排序 C. 希尔排序 D. 堆排序 3. 适于对动态查找表进行高效率查找的组织结构是（） A. 有序表 B. 分块有序表 C. 二叉排序树 D. 线性链表 4. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（） A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 5. 在一棵二叉树中，度为2的结点有2个，那么，该树有（）个叶结点。 A. 3 B. 4 C. 5 D. 6 6. 图中有n个顶点，e条边，如果用邻接矩阵表示图，则深度优先搜索遍历图的时间复杂性为（）。 A. O(n) B. O(e) C. O(n2) D. O(n+e) 7. 分块查找中块内的查找采用的查找方法是（） A. 顺序查找 B. 折半查找 C. 顺序查找、折半查找都可以 D. 顺序查找、折半查找都不可以 8. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi 相关的所有弧的时间复杂度是( ) A. O(n) B. O(e) C. O(n+e) D. O(n*e) 9. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. –1 10. 若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？（） A. 对称矩阵 B. 一般矩阵 C. 稀疏矩阵 D. 对角矩阵 11. 平衡二叉树的平衡因子的取值不可能是（） A. 1 B. -1 C. 0 D. 2 12. 在二叉树的中序遍历递归算法中，顺着搜索路径，在第( )次经过结点时作访问操作。 A. 1 B. 2 C. 3 D. 4 13. VSAM文件中的记录均存放在（）。 A. 数据集 B. 索引集 C. 顺序集 D. 以上都不是 14. 关键路径是AOE网络中（） A. 从源点到汇点的最长路径 B. 最短的回路 C. 从源点到汇点的最短路径 D. 最长的回路 15. 对数据元素序列（49，72，68，13，38，50，97，27）进行排序，如果采用起泡排序方法，则第二趟排序结果是（） A. 49，68，13，38，50，72，27，97 B. 13，38，49，50，27，68，72，97 C. 49，13，38，50，68，27，72，97 D. 13，38，49，27，50，68，72，97 16. 如果只想得到1024个元素组成的序列中的前6个最小元素，那么用（）方法最快。 A. 起泡排序 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 数据结构习题 第一章绪论 1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： 5) for (i = 1; i <= n; i++ ) { for (j = 1; j <= i; j++) { for (k = 1; k <= j; k++) { @ x += delta; } } } 答案：n*(n+1)*(n+2) =1+（1+2）+（1+2+3）+...+(1+2+3+...+n) =∑ =+ n i i i 1 2 / )1 ( * =1/2*∑ =+ n i i i i 1 * =n*(n+1)*(2n+1)/12 +n*(n+1)/4 =n*(n+1)*(n+2)/6 7) x = n; //n是不小于1的常数 y = 0; while (x >= (y + 1) * (y + 1)) { @ y++; } 答案：n向下取整 8) x = 91; y = 100; while (y > 0) { @ if (x > 100) { x -= 10; y--;} else { x++; } } 答案：if 执行次数为1100， if 判断内部执行为100次 1.19 试编写算法，计算i!·2i （i = 0, 1, …, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT ，则当n > arrsize 或对某个k （0 ≤ k ≤ n-1）使k!·2k > MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。 1.20 试编写算法求一元多项式∑==n i i i x a x 0n )(P 的值P n (x 0)，并确定算法中每一语句的执行 次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a i （i=0, 1, …, n ）、x 0和n ，输出为P n (x 0)。数据结构第二次单元测试
数据结构大作业报告
数据结构第2章基础习题 作业
数据结构课程作业
数据结构大作业要求
(完整版)数据结构课后习题及解析第二章
数据结构第二次实验报告
数据结构作业第1章
大数据结构大作业报告材料
2011年12月考试数据结构第二次作业
数据结构第一章课后习题与答案
数据结构作业