武汉大学数据结构教材

1. 下面程序段的执行次数为（ A ）

for(i=0;i＜n-1;i++)

for(j=n;j＞i;j--)

state;

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

2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）A. 110 B .108 C. 100 D. 120

3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde

4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ D ）

A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front

5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head

武汉纺织大学《数据结构》实验报告

班级： 级 管工类 专业 2 班 姓名： 序号： 1 实验时间： 2014 年 4 月 4 日 指导教师：

实验一：线性结构的基本操作

一、实验目的：

1、熟悉Java 上机环境，掌握Java语言编程方法，熟练运用Java语言实现数据结构设计和算法设计。 2、掌握线性表的顺序存储结构和链式存储结构的定义与基本操作，并能用Java语言实现线性表基本功能。

3、掌握栈、队列的存储结构与基本操作，并能利用该结构编写算法解决实际问题。

二、实验内容：

1、编写一个Java语言程序，利用线性表实现约瑟夫环问题，参考书本程序示例【例2.1】，完善该程序并运行。 实验步骤：

①、在Java编辑环境中新建程序，根据【例2.1】输入完整程序内容，并保存和编译； ②、运行程序，输入约瑟夫环长度number、起始位置start、计数值distance； ③、依次输入约瑟夫环中number个数据元素； ④、输出约瑟夫环执行过程。

2、编写一个程序，利用栈解决递归问题，实现n阶Hanoi塔问题。 实验步

武汉纺织大学《数据结构》实验报告

班级： 信管 专业 班 姓名： 学号： 实验时间： 年 月 日 指导教师：

实验四：查找操作与应用

一、实验目的：

1、掌握顺序查找、折半查找、哈希查找的基本方法和操作过程 2、掌握查找效率的分析方法

二、实验内容：

1、编写程序，实现顺序查找操作，可参考书本P260示例程序。 实验步骤：

①、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（对元素存放的先后顺序没有要求），并按照存储顺序输出所有元素；

②、输入带查找关键字，在顺序表中进行顺序查找； ③、输出查找结果。

2、编写程序，实现有序表折半查找操作，可参考书本P263示例程序。 实验步骤：

①、在Java语言编辑环境中新建程序，建立一个顺序表（表长10），依次输入10个数据元素（要求所有元素按照递增顺序排列），并按照存储顺序输出所有元素；

②、输入带查找关键字，在有序表中进行折半查找； ③、输出查找结果。

3、编写程序，实现哈希

1. 下面程序段的执行次数为（ A ）

for(i=0;i＜n-1;i++)

for(j=n;j＞i;j--)

state;

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

2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）A. 110 B .108 C. 100 D. 120

3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde

4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ D ）

A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front

5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head

武汉纺织大学《数据结构》实验报告

班级： 级 管工类 专业 2 班 姓名： 序号： 1 实验时间： 2014 年 4 月 4 日 指导教师：

实验一：线性结构的基本操作

一、实验目的：

1、熟悉Java 上机环境，掌握Java语言编程方法，熟练运用Java语言实现数据结构设计和算法设计。 2、掌握线性表的顺序存储结构和链式存储结构的定义与基本操作，并能用Java语言实现线性表基本功能。

3、掌握栈、队列的存储结构与基本操作，并能利用该结构编写算法解决实际问题。

二、实验内容：

1、编写一个Java语言程序，利用线性表实现约瑟夫环问题，参考书本程序示例【例2.1】，完善该程序并运行。 实验步骤：

①、在Java编辑环境中新建程序，根据【例2.1】输入完整程序内容，并保存和编译； ②、运行程序，输入约瑟夫环长度number、起始位置start、计数值distance； ③、依次输入约瑟夫环中number个数据元素； ④、输出约瑟夫环执行过程。

2、编写一个程序，利用栈解决递归问题，实现n阶Hanoi塔问题。 实验步

数据结构

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、算法的5个重要特性是_____有穷性_____、___确定性________、___可行性_____、输入和输出。

2、单链表中，除首元素结点外，其它任一元素结点的存储位置由__其前驱的指针域_________指示。

3、在双向链表中，欲在p所指结点之前插入一个由s指向的结点，请完成有关操作。 s->prior=p->prior; p->prior=s; p->next=s->next； s->next=p;

4、对于栈只能在____栈顶____插入和删除元素；对于队列只能在___队尾______插入元素和__队头_____删除元素。

5、在模式匹配的KMP算法中用到了一个next函数，若next[j]=k，则说明在模式串T中存在一个与“T1T2...Tk-1”相等的子串“__Tj-k+1?.Tj-1_______________”。

6、假设有二维数组A6?8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A共占用_____288_______个字节的存储单元，按行存储时，元素A25的第一个字节的地址为______1126______

数据结构习题

一、 单选题

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) 集

数据结构与算法

一 选择题

1．算法的计算量的大小称为计算的（ B ）。

A．效率 B. 复杂性 C. 现实性 D. 难度

2．下面说法正确的是（ C ）

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

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低

A．(1) B.(1),(2) C.(1),(4) D.(3)

3. 连续存储设计时，存储单元的地址（ A ）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续

4. 下述哪一条是顺序存储结构的优点？（A ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表

数据结构复习201406

第一章绪论

基本知识点：数据结构与算法的概念。

重点：数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。

难点：分析算法的时间复杂度。 知识要点：

数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。 数据元素：数据的基本单位，是数据的一个元素。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

数据类型：一个值的集合和定义在这个值集上的一组运算的总称。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间关系和操作（运算）的学科。

数据的逻辑结构是指数据元素之间逻辑关系的整体。 数据的存储结构是指数据结构在计算机内的表示。

四种基本数据结构：集合、线性结构、树形结构、图结构。

算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。 算法执行的时间是问题规模的函数。 算法的时间复杂度是指，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同时，则称该算法的时间复杂度为O(f(n))。