数据结构和JAVA关系大吗

《数据结构（JAVA）》综合性、设计性实验成绩单

开设时间：

班级 学号 姓名 实验题目实验三 栈和队列及递归算法 成绩 教师签名

《数据结构（JAVA）》

实 验 报 告

实验题目： 栈和队列及递归算法 指导教师： 实验组长（姓名+学号）： 组员（姓名+学号）：

实验时间：

组长签名：

一、实验报告撰写提纲

1、实验目的

1． 理解栈和队列抽象数据类型，掌握栈和队列的存储结构和操作实现，理解栈和队列

在实际应用问题的作用。

2、实验内容

（1） （2） （3） （4）

使用一个栈，将十进制转换成二进制。

分别用循环单链表、循环双链表结构设计队列，并讨论他们之间的差别。 使用3个队列分别保留手机最近10个“未接来电”、“已接来电”、“以拨电话”。 走迷宫。

一个

华东交大理工学院

课程设计(论文)任务书

电信分院2009 电子商务专业一班

一、课程设计(论文)题目走迷宫

二、课程设计(论文)工作自 2011 年6月20 日起至 2011 年6月30 日止。

三、课程设计(论文) 地点: 机房

四、课程设计(论文)内容要求：

1．本课程设计的目的

（1）熟练掌握数据结构的基本算法，提高算法设计与分析能力

（2）基本掌握面向对象设计基本思路和方法；

（3）利用所学的基本知识和技能，解决简单的程序设计问题；

（4）提高学生的科技论文写作能力。

2．课程设计的任务及要求

1）基本要求：

（1）课程设计前必须根据课程设计题目认真准备实验源程序及调试时所需的数据；（2）要求采用简明、严格的问题描述，设计求解算法；

（3）数据结构选用得当，程序结构合理；

（4）程序简明易懂，多运用输出提示，程序运行正确；

（5）对设计进行总结和讨论。

2）课程设计论文编写要求

（1）要按照书稿的规格打印撰写课设论文

（2）论文包括目录、正文、总结和体会、参考文献、附录等

（3）正文中要有问题描述、设计求解算法、算法的实现、调试分析（调试时出现的主要问题：编译语法错误及修改，重点是运行逻辑问题修改和调整）

（4）课设论文装订按学校的统一要求完成

3）课设考核：

从以下

一.选择题（共15题，每题3分）

（1）下面关于算法说法错误的是_______。 a. 算法最终必须由计算机程序实现

b. 为解决某问题的算法同为该问题编写的程序含义是相同的 c. 算法的可行性是指指令不能有二义性 d. 以上几个都是错误的 （2）下面说法错误的是______.

a. 算法原地工作的含义是指不需要任何额外的辅助空间

b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 d. 同一个算法，实现语言的级别越高，执行效率就越低 （3）在下面的程序段中，对x的赋值语句的频度为_____。 for (int i; i

a. 0(2n) b. 0(n) c. 0(n2) d. O(log2n) （4）下面说法正确的是______。 a. 数据元素是数据的最小单位； b. 数据元素是数据的最小单位；

c. 数据的物理结构是指数据在计算机内的实际存储形式 d. 数据结构的抽象操作的定义与具体实现有关 （5）下面说法正确的是_______。

a. 在顺序存储结构中，有时也存储数据结构中元素之间的关系 b. 顺序

第一章 绪论

1.1 单选题

1. D 2. C 3. D 4. B 5. A 6. B 7. C 8. C 9. A 10. B

第10小题提示：在含有n个元素的数据表中顺序查找任一元素的平均比较次数为

i?1

?pici，p为查找第i个元素的概率，c是查找第i个元素时需要比较的元素数，查找所

i

i

n

有元素的概率之和为1，若查找每个元素的概率相同，则平均查找长度的计算公式可简化为

1ni?1?ci。

1311?2?(3?4?5?6?7)=35/12 412n 此题的计算式为?1?

1.2 算法分析题 1. 判断n是否为一个素数，若是则返回逻辑值true，否则返回逻辑值false。该算法的时间复杂度为O(

nn)。

2. 计算

?i!的值。时间复杂度为O(n)。 ?i!的值。时间复杂度为O(n)。

2i?1ni?1 3. 计算

4. 求出满足不等式1+2+3+...+i≥n的最小i值。时间复杂度为O(n)。 提示：因为1+2+3+...+i=(1+i)i/2，即当n很大时i的平方与n成正比，所以i的值（即函数中while循环的次数）与n的平方根成正

一、 选择题

1、数据结构在计算机内存中的表示是指____A__ A．数据的存储结构 B.数据结构

C. 数据的逻辑结构 D.数据元素之间的关系

2、若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ） A．问题规模 B．语句条数 C．循环层数 D．函数数量

3、下列选项中与数据存储结构无关的术语是（ D ） A.顺序表 C.链队列

B.链表 D.栈

4、已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ D ） A.rear=(rear-1)%m;

B.front=(front+1)%m;

C.front=(front-1)%m;

D.rear=(rear+1)%m; 5、栈和队列的共同点是__C______

A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点

6、已知一堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列______D__

A.1234

实验一、单链表的基本操作

一、实验目的

1、掌握线性链表的操作特点，即指针是逻辑关系的映像。 2、掌握动态产生单链表的方法。

3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。 4、熟练掌握单链表的取元素操作

二、实验内容

1、定义单链表类型并动态创建单链表；

2、实现单链表的取元素操作、插入操作和删除操作； 3、实现输出单链表中各元素值的操作； 4、将单链表中的最小元素移到最前面。

三、实验环境

eclipse环境

四、实验步骤

1、定义单链表节点类；

2、定义单链表类，并实现单链表的创建、插入、删除、取元素操作和将单链表中的最小元素移到最前面的操作；

3、从键盘上依次输入

21、75、30、18、42、56，顺序或逆序创建单链表，

并输出单链表中的各元素值；

5、分别在单链表的第3个位置和第9个位置插入67和10，给出插入成功或失败的信息，并输出单链表中的各元素值；

6、删除单链表中的第6个数据元素和第8个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值；

7、取单链表中的第5个数据元素和第7个数据元素；

8、将单链表中的最小元素移到最前面，并输出单链表中的各元素以检查操作是否正确实现。

五、问题讨论

1、单链

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

1、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。 A）loc(A1)+i*c B）loc(A1)+(i-1)*c C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c

2、下面程序段的时间复杂度是( A )。 s =0;

for( i =0; i

A） O(n2) B） O(n) C） O(m*n) D）O(1)

3、采用链结构存储线性表时，其地址（ B ）。 A）必须是连续的 B）连续不连续都可以 C）部分地址必须是连续 D）必须是不连续的

4、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ A ）。 A）直接选择排序 B）直接插入排序 C）快速排序 D）起泡排序

5、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。 A）3 B）4

家族关系查询系统

1 课程设计介绍

1.1课程设计项目简介

家谱是一种以表谱形式，记载一个以血缘关系为主体的家族世

系繁衍和重要人物事迹的特殊图书载体。家谱是中国特有的文化遗产，是中华民族的三大文献之一，属珍贵的人文资料，对于历史学，民俗学，人口学，社会学和经济学的深入研究，均有不可替代的重要功能。本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息 、插入家族成员等功能。

1.2课设题目分析

本程序的实质是完成对家谱成员信息的建立、查找、插入等功能。可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。 本程序包含以下几个模块 （1）建立家族关系树。此模块将构建一个家族关系，对数据初始化，构造关系树并录入数据一遍后续程序使用。 （2）添加新成员。此模块将添加一个新成员，实现对家族关系的修改。

（3）家族关系的查询。此模块将实现对家族不同关系的查询 （4）主程序模块。此模块实现整个程序的进入和进出，以及各种初始化处理。 （5）

1.3课程题目原理与数据结构

因为家族的成员之间存在一个对多个的层次结构关系，所以不能用线性表来表示和实现。家谱从形状上看

家族关系查询系统

1 课程设计介绍

1.1课程设计项目简介

家谱是一种以表谱形式，记载一个以血缘关系为主体的家族世

系繁衍和重要人物事迹的特殊图书载体。家谱是中国特有的文化遗产，是中华民族的三大文献之一，属珍贵的人文资料，对于历史学，民俗学，人口学，社会学和经济学的深入研究，均有不可替代的重要功能。本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息 、插入家族成员等功能。

1.2课设题目分析

本程序的实质是完成对家谱成员信息的建立、查找、插入等功能。可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。 本程序包含以下几个模块 （1）建立家族关系树。此模块将构建一个家族关系，对数据初始化，构造关系树并录入数据一遍后续程序使用。 （2）添加新成员。此模块将添加一个新成员，实现对家族关系的修改。

（3）家族关系的查询。此模块将实现对家族不同关系的查询 （4）主程序模块。此模块实现整个程序的进入和进出，以及各种初始化处理。 （5）

1.3课程题目原理与数据结构

因为家族的成员之间存在一个对多个的层次结构关系，所以不能用线性表来表示和实现。家谱从形状上看