数据结构java版叶核亚pdf

《数据结构（Java版）》课程样卷

教材：《数据结构（Java版）（第4版）》，叶核亚编著，电子工业出版社，2015年7月出版。 试题范围：第1～9章，掌握基础原理，熟悉经典算法，问答题形式考核。

编程题重点是：1.单/双链表； 2.二叉树/树，递归算法。这是必须掌握的，即使部分学生掌握不了递归算法，也必须考。

不考内容：6.3 线索二叉树求父母、插入、删除算法（没写），7.5.2 Floyd，8.5.3 平衡二叉树，第10章。可作为课程设计题。

试卷范围和难度不超过样卷。

4-0 模拟样卷

一、 填空题（16分=2分×8题）

1. 声明抽象数据类型的目的是________________________________________。 2. 以下数据存储结构声明为_________________________________________。

table∧…∧∧Node…∧ 3. 已知java.lang.String类声明以下成员方法：

public String replaceAll(String pattern, String str) String target=\

System.out.println(\

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

开设时间：

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

《数据结构（JAVA）》

实 验 报 告

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

实验时间：

组长签名：

一、实验报告撰写提纲

1、实验目的

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

在实际应用问题的作用。

2、实验内容

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

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

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

一个

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

一、实验目的

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、单链

华东交大理工学院

课程设计(论文)任务书

电信分院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、用一维数组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、用一维数组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. 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的平方根成正

2010湖北省JAVA版数据结构试题及答案

1、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。

A）4 B）5

C）6 D）7

2、以下属于顺序存储结构优点的是（ A ）。

A) 存储密度大 B) 插入运算方便

C）删除运算方便 D）可方便地用于各种逻辑结构的存储表示

3、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A) 5，4，3，2，1，6 B) 2，3，5，6，1，4

C) 3，2，5，4，1，6 D) 1，4，6，5，2，3

4、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈

C）队列 D）树

5、队列的操作的原则是（ A ）。

A）先进先出 B) 后进先出

C) 只能进行插入D) 只能进行删除

6、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A) 5，4，3

2010湖北省JAVA版数据结构试题及答案

1、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。

A）4 B）5

C）6 D）7

2、以下属于顺序存储结构优点的是（ A ）。

A) 存储密度大 B) 插入运算方便

C）删除运算方便 D）可方便地用于各种逻辑结构的存储表示

3、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A) 5，4，3，2，1，6 B) 2，3，5，6，1，4

C) 3，2，5，4，1，6 D) 1，4，6，5，2，3

4、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈

C）队列 D）树

5、队列的操作的原则是（ A ）。

A）先进先出 B) 后进先出

C) 只能进行插入D) 只能进行删除

6、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A) 5，4，3

一、 选择题

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