数据结构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）课设考核：

从以下

第一章 绪论

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

实验报告一 JAVA程序设计基础及算法设计

班级________ 学号______ 姓名_____ 专业_____ 一、 实验目的：

（1） 掌握JAVA语言的语法，理解数组和对象的引用模型，理解类的封装、继承和多态 （2） 掌握类的设计方法

（3） 掌握异常处理方法和标准输出方法，了解标准输入方法 （4） 熟悉算法的描述方法、算法时间复杂度的分析和计算方法 （5） 理解数据和算法的基本概念 二、 实验内容：

1、 采用二维数据输出杨辉三角形，二维数据的结构如图1所示：

0 1 2 3 4 5 mat mat[0] 1 mat[1] 1 1 mat[2] 1 2 1 mat[3] 1 3 3 1 mat[4] 1 4 6 4 1 mat[5] 1 5 10 10 5 1

图1 杨辉三角形的二维数组结构

请粘贴源程序及运行测试结果： 源程序：

import java.util.Scanner;

public class Ex {

public static void pri( int

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. 研究数据结构就是研究 D

A) 数据的逻辑结构

B) 数据的逻辑结构和存储结构 C) 数据的存储结构

D) 数据的逻辑结构、存储结构及其数据在运算上的实现 2. 下面关于算法的说法，错误的是 D 。

A) 算法最终必须由计算机程序实现

B) 为解决某问题的算法与为该问题编写的程序含义是相同的 C) 算法的可行性是指指令不能有二义性 D) 以上几个都是错误的

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备

5个特性输入、输出 、 B 。 A) 可执行性、可移植性和可扩充性 B) 可执行性、有穷性和确定性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和确定性

4. 以下属于逻辑结构的概念是 C 。

A) 顺序表 B) 哈希表 C) 有序表 D) 单链表

5. 具有线性结构的数据结构是 D 。

A) 图 B) 树 C) 广义表 D) 栈

6. 数据的存储结构包括顺序、链接、散列和 D 种基本类型。

A) 向量 B) 数组 C) 集