数据结构复习提纲（含题目）

数据结构复习提纲：

信息管理与信息系统（商务信息） 1、 常见的数据结构中，线性结构有哪些，非线性结构有哪些？

知识点：

线性结构：线性表，栈，队，串，数组 非线性结构：树，图

题型分析： 选择题：

1．从逻辑上可以把数据结构分为（ ）两大类。【武汉交通科技大学 1996 一 、4（2分）】

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构

2.以下数据结构中，哪一个是线性结构（ ）？【北方交通大学 2001 一、1（2分）】

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 3．以下数据结构中，（ ）是非线性数据结构【中山大学 1999 一、4】

A．树 B．字符串 C．队 D．栈 4. 下列数据中，（ ）是非线性数据结构。【北京理工大学 2001 六、1（2分）】

A．栈 B. 队列 C. 完全二叉树 D. 堆 填空题：

答案：CDAC 2、 线性表的两种存储方式（原理，特点、各自的优缺点）

知识点：

顺序存储结构：

原理：使用数组，数组把线性表的数据元素存储在一块连续地址空间的内存单位中 特点：线性表中逻辑上相邻的数据元素在物理地址上也相邻。 优点：算法简单，存储密度大，空间单位利用效率高 缺点：需要预先确定数据元素的最大个数，并且插入和删除操作时需要移动较多的数据元素。（可简化为：插入或删除元素时不方便）

链式存储结构：

原理：把存放数据元素的结点用指针域构造成链。

特点：数据元素间的逻辑关系表现在结点的连接关系上

优点：不需要预先确定数据元素的最大个数，插入和删除操作是不需要移动数据元素（可简

化为：插入或删除元素时很方便，使用灵活。）

缺点：存储密度小，空间单位利用效率低 题型分析： 一.选择题：

1．下述哪一条是顺序存储结构的优点？（ ） A．存储密度大 B．插入运算方便

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

2．下面关于线性表的叙述中，错误的是哪一个？（ ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

1

B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。

3. 链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比

4.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ ）。 A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构

5.链式存储结构所占存储结构（ ）。

A.分两部分，一部分存放结点值，另一部分存放表示节点间关系的指针 B.只有一部分，存放结点值

C.只有一部分，存储表示结点间关系的指针

D.分两部分，一部分存放结点值，另一部分存放结点所占单元数

5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址是（）。

A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以

6.线性表在（）情况下适用于使用链式结构实现。

A.需经常修改L中的结点值 B.需不断对L进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂

7.单链表的存储密度（）。

A.大于1 B.等于1 C.小于1 D.不能确定

二.填空题：

1．链接存储的特点是利用________来表示数据元素之间的逻辑关系。

2.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。

3.顺序表中逻辑上相邻的数据元素，其物理地址 。单链表中逻辑上相邻的数据元素，其物理地址 。

三.简答应用题：

1.解释顺序存储结构和链式结构的特点，并比较顺序存储结构和链式存储结构的优缺点。（答案参考上面的知识点）

答案：一.ABBCADBC

二.1． 指针 2．物理上相邻 指针 3.必定相邻 不一定相邻 3、 计算机算法的5个特性及5个目标

知识点：

5个特性：输入性，输出性，有限性，确定性，可执行性

2

5个目标：正确性，可读性，健壮性，高时间效率，高空间效率 （注意：有限性亦称为有穷性）

题型分析： 一.选择题：

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

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有限性

C. 确定性、有限性、稳定性 D. 易读性、稳定性、安全性

二.填空题：（无论它怎么考，背熟知识点就得啦。） 4、 数据的两种结构：物理（存储）、逻辑的含义

知识点：

物理结构：又称为存储结构，是数据的逻辑结构在计算机中的存储表示。它是依赖于计算机的。 数据的存储结构总共4种：顺序存储结构，链式存储结构，索引存储结构，散列存储结构。 基本形式有两种：1.顺序存储结构2.链式存储结构

（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻

辑关系。存储密度大，但有些操作（如插入、删除）效率较差。

（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数

据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。

（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索

引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。

（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并

将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。

逻辑结构：数据元素之间的相互联系方式。即从逻辑关系上描述数据，它与数据的存储无关，是独立于

计算机的。

逻辑结构细分为以下四种：（其中树结构和图结构合称非线性结构） 集合结构： 仅同属一个集合 线性结构: 一对一（1:1)

非线性结构: 树 结 构: 一对多（1:n)

图 结 构: 多对多 (m:n)

题型分析： 一.选择题： 1. 数据结构在计算机内存的表示是指（）。

A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系

3

2.在数据结构中，与所使用的计算机无关的是数据的（）结构。 A.逻辑 B.存储 C.逻辑与存储 D.物理 3.非线性结构是数据元素之间存在一种（）。

A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 二.填空题：

1．数据的物理结构包括 的表示和 的表示。 2．数据的逻辑结构是指 。

3．一个数据结构在计算机中 称为存储结构。

4.数据结构按逻辑结构可分为两大类，它们分别是_______和_______。

5.数据逻辑结构包括 ， ， 三种类型，其中_____和______合称为_______。 6.线性结构中元素之间存在______关系，树形结构中元素之间存在________关系。图形结构中元素之间存在______。 三.简答应用题：

1.简述线性结构与非线性结构的不同点。

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

答案：一.AAB

二.1．数据元素 数据元素间关系 2．数据元素之间的相互联系方式

3．表示（又称映像）。 4.线性结构，非线性结构

5.线性结构，树形结构，图形结构，树形结构，图形结构，非线性结构 6.一对一，一对多，多对多 三.

1.线性结构反映数据元素之间的逻辑关系是一对一的，非线性结构反映数据元素间的逻辑关系是多对多的。 2.

（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻

辑关系。存储密度大，但有些操作（如插入、删除）效率较差。

（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数

据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。

（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索

引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。

（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并

将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。 5、 在单链表指针为p的结点之后插入指针为q的结点，如何操作？

（知识点与题型分析将归纳到提纲第21点） q?next=p?next； p?next=q；

4