数据结构java版期末试题

《数据结构（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、单链

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

华东交大理工学院

课程设计(论文)任务书

电信分院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）课设考核：

从以下

2009年全国硕士研究生入学统一考试

计算机科学与技术学科联考 计算机学科专业基础综合

考试大纲 教育部考试中心

中国学位与研究生教育学会工科工作委员会

目 录

I. 考查目标

II. 考试形式和试卷结构考查范围 III. 考查范围

数据结构 计算机组成原理 操作系统 计算机网络 IV.

试题示例

Ⅰ.考查目标

计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ.考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分 计算机组成原理 45分

- 1 -

操作系统 35分 计算机网络 25分 四、试卷题型结构

单项选择题 80分（40小题，每小题2分） 综合应用题 70分

Ⅲ.考查范围

数据结构

【考查目标】

1.理解数据结构的基本概念；掌握数据的逻辑结构

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的平方根成正

数据结构（本科）期末综合练习一（单选题）

单选题

1. 一个数组元素a[i] 与( )的表示等价。

A. *(a+i) B. a+i C. *a+i D. &a+i

2. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值

3. 下面程序段的时间复杂度为( )。 for(int i=0; i

for(int j=0; j

22

A. O(m) B. O(n) C. O(m*n) D. O(m+n)

4. 执行下面程序段时，执行S语句的次数为( )。 for(int i=1; i<=n; i++)

for(int j=1; j<=i; j++) S;

22

A. n B. n/2 C. n(n+1) D. n(n+1)/2

5. 下面算法的时间复杂度为( )。 int f(unsign