数据结构

第一章 习题

判断题

1． 数据元素是数据的最小单位。( )

2． 记录是数据处理的最小单位。 ( )

3． 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )

4．算法的优劣与算法描述语言无关，但与所用计算机有关。( )

5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )

6．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( )

7．程序一定是算法。( )

8．数据的物理结构是指数据在计算机内的实际存储形式。( )

9． 数据结构的抽象操作的定义与具体实现有关。( )

10．在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )

11．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )

12．数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( )

13．数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 ( )

答案

1．× 2．× 3．× 4．× 5．√

6．× 7．× 8． √ 9．× 10．×

11．× 12．√ 13．×

填空题

1．数据的物理结构包括____ 的表示和____ 的表示。

2．对于给定的n个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） ，（4）四种。

3．数据的逻辑结构是指_____。 4．一个数据结构在计算机中______称为存储结构。

5．抽象数据类型的定义仅取决于它的一组（1），而与（2）无关，即不论其内部结构如何变化，只要它的

（3） 不变，都不影响其外部使用。

6．数据结构中评价算法的两个重要指标是_______。

7．数据结构是研讨数据的（1）和（2），以及它们之间的相互关系，并对与这种结构定义相应的（3），设计出相应的（4）。

8． 一个算法具有5个特性: （1） 、 （2） 、（3），有零个或多个输入、有一个或多个输出。

9．计算机执行下面的语句时，语句s的执行次数为 _______ 。

for(i=l；i

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

s；

10.下面程序段的时间复杂度为________。

if (n>1) sum=1；

for (i=0; sum

11．在有n个选手参加的单循环赛中，总共将进行______场比赛。

答案

1．数据元素 数据元素间关系

2．集合 线性结构 树形结构 图状结构或网状结构

3．数据的组织形式，即数据元素之间逻辑关系的总体而逻辑关系 是指数据元素之间的关联方式或称“邻接关系”

4．表示（又称映像）

5．（1）逻辑特性 （2）在计算机内部如何表示和实现（3）数学特性

6．算法的时间复杂度和空间复杂度

7．（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法

8．（1）有穷性 （2）确定性 （3）可行性

9. (n+3)(n-2)/2

10. O(n)

11. n(n-1)/2

选择题(带*是超出目前知识点的题目)

1． 计算机算法指的是( 1 ），它必须具备（ 2 ） 这三个特性。

(1) A． 计算方法 B．排序方法 C． 解决问题的步骤序列 D． 调度方法

(2) A．可执行性、可移植性、可扩充性 B． 可执行性、确定性、有穷性

C． 确定性、有穷性、稳定性 D． 易读性、稳定性、安全性

2． 一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C．

3．从逻辑上可以把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构

C．线性结构、非线性结构 D．初等结构、构造型结构

4*．以下与数据的存储结构无关的术语是（ ）。

A．循环队列 B．链表 C．哈希表 D．栈

5．在下面的程序段中，对x的赋值语句的频度为（ ）。

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

X++;

A．O(2n) B．O(n) C．O(n2) D．O(log2n) 6．以下数据结构中，（ ）是非线性数据结构。

A．树 B．字符串 C．队 D．栈

7*． 下列数据中，（ ）是非线性数据结构

A．栈 B． 队列 C．完全二叉树 D． 堆

8．连续存储设计时，存储单元的地址（ ）。

A．一定连续 B．一定不连续

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

9*．以下属于逻辑结构的是（ ）。

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

答案

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

应用题

1． 数据结构是一门研究什么内容的学科？

2． 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？

3．评价一个好的算法，您是从哪几方面来考虑的？

4． 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？

5．若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？

6．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？

7．在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?

第二章 习题

判断题

1． 链表中的头结点仅起到标识的作用。( )

2． 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )

4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )

5． 对任何数据结构链式存储结构一定优于顺序存储结构。( )

6．顺序存储方式只能用于存储线性结构。( )

7．集合与线性表的区别在于是否按关键字排序。( )

8． 所谓静态链表就是一直不发生变化的链表。( )

9． 线性表的特点是每个元素都有一个前驱和一个后继。( )

10．取线性表的第i个元素的时间同i的大小有关。 ( )

11．循环链表不是线性表。 ( )

12．线性表只能用顺序存储结构实现。( )

13．线性表就是顺序存储的表。( )

14．为了很方便的插入和删除数据，可以使用双向链表存放数据。( )

15．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )

答案

1． × 2． √ 3． √ 4． × 5． ×

6． × 7． × 8． × 9． × 10．×

11．× 12．× 13．× 14．√ 15．×

填空题

1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时,应采用_______存储结构。

2．线性表L=（a1,a2,„,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。

3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;

4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。 5．在单链表中设置头结点的作用是________。

6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一 个新结点的时间复杂度为________。

7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______。

8． 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、 _______、________。

9． 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：s->next=p； s->prior= ________；p->prior=s；________=s；

10．链接存储的特点是利用________来表示数据元素之间的逻辑关系。 11．顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。

12．对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。

13．循环单链表的最大优点是：________。

14．已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________

15．带头结点的双循环链表L中只有一个元素结点的条件是：________

16．在单链表L中，指针p所指结点有后继结点的条件是：__

17．带头结点的双循环链表L为空表的条件是：________。

18．在单链表p结点之后插入s结点的操作是：_______。

答案

1． 顺序

2．（n-1）/2

3．py->next=px->next; px->next=py

4．n-i+1

5．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除。第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。

6．O(1)，O(n)

7．单链表，双向链表