数据结构简答题

试比拟顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用

存储单元的地址必须是连续的。

优点：存储密度大（=1）,存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两局部，一局部存放结点值，

另一局部存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵敏。缺点：存储密度小（＜1）,存储空间利用率低。顺

序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。

假设线性表的长度变化不大，且其主要操作是查找，则采纳顺序表；

假设线性表的长度变化较大，且其主要操作是插入、删除操作，则采纳链表。

作为线性表的两种基本的存储结构：顺序袤和链表。它们在存赭和操作上各有优

畦表

1顺序表

优点1、方法简单，各种高级舞中都1、插入、胭除时，只

有数组，容易实现；要找到对应前驱结点，

2、不用为表示结点1、司的逻辑关系修改指针即可，无需移

而噌加额外的存储开销，存储密度动元素；

大；3、具有按元素序号随机访问2、采用动态存储分

的特点，查找速度快.配，不会造成内存浪费

和溢出.

缺点1、插入删除操作时，需要移动元1、在有些语言中，不

素，平均移动大约表中一半的元支持指针，不容易实

素，对元素较多的顺序表效率低.现；

2、采用静态空间分配，需要强先2、需要用额外空间存

分配足够大的存储空间，会造成内储线性表的关系，存储

存的浪费和流出.密度小3、不能随机访

间，查找时要从头指针

开始遍历.

一棵度为2的有序树与一棵二叉树有何区别

答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而

言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序.

而二叉树无论其孩子数是否为2,均需确定其左右次序，也就是说二叉树的结点次序不是相

对于另一结点而言而是确定的。

三、算法的时间且杂度仅与问题的规模相关吗？

不，事实上，算法的时间豆杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，

但在最坏的情况卜.，其时间且杂度就是只与求解问题的规模相关的.我们在讨论时间豆杂度

时，一般就是以最坏情况卜的时间红杂度为准的.

四、

常用的存储表示方法有哪儿种？

常用的存储表示方法有四种：

顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻

辑关系由存储单兀的邻接关系来体现.由此得到的存储表示称为顺序存储结构.

链接存储方法：它不要求逻辑上相邻的结点在物理位置匕亦相邻，结点间的逻辑关系是由

附加的指针字段表示的,由此得到的存储表示称为链式存储结构,

索引存储方法：除建立存储结点值息外，还建立附加的索引表来标识结点的地址。

散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址.

为什么在单循环捱表中设置尾指针比设置头指针更好？

答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点

和终端结点都很方便，设一带头结点的单循环链表，其尾指针为心r,则开始结点和终端

结点的位置分别是rear->next->next和rear,查找时间都是0(1)«若用头指针来表示该链表，

则查找终端结点的时间为O(n).

何时选用顺序表、何时选用链表作为线性表的存储结构为宜？

答：在实际应用中，应根据具体问题的要求和性肮来选择顺序表或链表作为线性表的存储

结构，通常有以下儿方面的考虑：

1.基于空间的考虑.当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约

存储空间，宜采用顺序表：反之，当线性表长度变化大，难以估计其存储规模时，乐用动

态链表作为存储结构为好.

2.基于时间的考虑.若线性表的操作上要是进行查找，很少做插入和删除操作时，采用顺序

表做存储结构为宜：反之，若需要对线性表进行频密地插入或删除等的操作时，宜采用链

表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的

单循环链表为宜。

简述以下术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据

类型。

数据是对客观事物的符号表示。在计算机科学中是指全部能输入到计算机中并被计算机程序

处理的符号的总称。

数据元素是数据的根本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象

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

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

试描述数据结构和抽象数据类型的概念与程序设计言语中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数

据类型由具体言语系统内部定义，直接提供应编程者定义用户数据，因此称它们为预定义数

据类型。抽象数据类型通常由编程者定义，包含定义它所使用的数据和在这些数据上所进行

的操作。在定义抽象数据类型中的数据局部和操作局部时，要求只定义到数据的逻辑结构和

操作说明，不考虑数据的存储结构和操作的具体完成，这样抽象层次更高，更能为其他用户

提供良好的使用接口。

描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。

头结点是在首元结点之前附设的一个结点,该结点不存储数据元素,其指针域指向首元结点,

其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一

处理。

线性表的两种存储结构各有哪些优缺点？

线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接

存取数据元素，方便灵敏、效率高，但插入、删除操作时将会引起元素的大量移动，因而降

低效率：而在链接存储结构中内存采纳动态分配，利用率高，但需增设指示结点之间关系的

指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。

对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度

会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为

什么？

应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元

素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入

运算是不需要移动元素的，只需修改指针即可，所以很简单完成表的容量的扩充。

对于线性表的两种存储结构，假设线性表的总数根本稳定，且很少进行插入和删除操作，

但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。

应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元

素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据

元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是

一种顺序存取的存储结构。

在单循环链表中设置尾指针比设置头指针好吗？为什么

设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查

找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为

rear,则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是0（1）。

假设用头指针来表示该链表，则查找终端结点的时间为0（n）»

假定有四个元素A,B,C,D依次进栈，进栈过程中同意出栈，试写出全部可能的出栈序列。

共有14种可能的出栈序列，即为：

ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA

什么是队列的上溢现象？一般有几种解决方法，试简述之。

在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队列的容量（即存储的

空间大小）为maxnum。当有元素要参加队列（即入队）时，假设rear=maxnum,则会发生

队列的上溢现象，此时就不能将该元素参加队列。对于队列，还有一种“假溢出”现象，队

列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方法的选择

不当所致，可以用循环队列解决。

一般地，要解决队列的上溢现象可有以下几种方法：

（1）可建立一个足够大的存储空间以防止溢出，但这样做往往会造成空间使用率低，浪费

存储空间。

（2）要防止出现“假溢出”现象可用以下方法解决：

第一种：采纳移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动

一个位置，假定空余空间足够。

第二和每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中

的第一个位置。

第三种：采纳循环队列方法。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组

完成，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。

如何了解循环队列是空还是满

第一，采纳计数器来推断，空时.，计数器为0,满时，计数器为maxsize；第二，另设一个

布尔变量以匹别队列的空和满；第三，少用一个元素的空间，约定入队前，测试尾指针在循

环意义下加1后是否等于头指针，假设相等则认为队满（注意：rear所指的单元始终为空）；

1.数据结构和数据类型两个概念之间有区别吗？

答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素.

数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操

&

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

答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的

逻辑关系是多对多的.

说明线性表，栈,队列的异同点

相同点:都是线性结构，都是逻辑结构的概念,都可以用顺序存储或者链表存储.栈和队列两种

特别的线性表,即受限的线性表,只是对插入，删除运算加以限制.

不同点：1运算规则不同：线性表为随机存取.栈只同意在一端进行插入.删除运算.列队只

同意在一端进行插入，另一端进行删除运算.

2用途不同，堆栈用于子程序调用和爱护现场，队列用于多道作业处理,指令存储及其他运算

等等.

当你为解决某一问题而选择数据结构时，应从哪些方面考虑

通常从两方面考虑：第一是算法所需的存储空间量：第二是算法所需的时间.对算法所需的

时间又涉及以下三点：（1）程序运行时所需输入的数据总量。（2）计算机执行每条指令所需

的时间。（3）程序中指令重复执行的次数

简述逻辑结构与存储结构的关系

答：数据的逻辑结构反映数据元素之间的逻辑关系［即数据元素之间的关联方法或“邻接关

系"），数据的存储结构是数据结构在计算机中的表示，包含数据元素的表示及其关系的表

zj\O

数据运算是数据结构的一个重要方面，试举例说明两个数据结构的逻辑结构和存储方法完全

相同，只是对于运算的定义不同，因而两个结构具有显著不同的特性，则这两个数据结构是不

同的.

答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运

算集合不同而成为不同的数据结构。

线性表有两种存储结构：一是顺序表，二是链表。试问：⑴两种存储表示各有哪些主要

优缺点

（2）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的

总数也会自动地改变。在此情况下，应选用哪种存储结构为什么

⑶假设线性表的总数根本稳定，且很少进行插入和删除，但要求以最快的速度存取线性

表中的元素，那么，应采纳哪种存储结构为什么

解答：⑴顺序存储是按索引（隐含的）直接存取数据元素，方便灵敏，效率高，但插入、

删除操作时将引起元素移动，因而降低效率；链接存储内存采纳动态分配，利用率高，但需

增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删

除操作十分简单。（2）应选用链接表存储结构。其理由是，链式存储结构用一组任意的存

储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存

储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很简单完

成表的容量扩充。

⑶应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差

一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任

一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表

则是一种顺序存取的存储结构。2、用线性表的顺序结构来描述一个城市的设计和规划适宜

吗为什么

不适宜。因为一个城市的设计和规划涉及非常多的工程，很复杂，经常需要修改、扩