数据结构简答题

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

数据结构是一门研究非数值计算的程序设计问题中，计算机操作对象及对象间的关系和施加于对象的操作等的学科。

2、数据存储结构有哪几种类型？

存储结构可分为顺序存储、链式存储、索引存储和散列存储。

3、数据逻辑结构包括哪几种类型？

逻辑结构包括线性结构和非线性结构。更细分的话可以说，逻辑结构包括集合、线性结构（线性表、栈、队列等）、树形结构和网状结构。

4、数据结构与数据类型有什么区别？答：数据结构这一术语有两种含义，一是作为一门课的名称，二是作为一个科学的概念，目前尚无公认定义，一般认为，数据结构包括三个方面数据的逻辑结构，数据的存储结构，数据的运算。而数据类型是值的集合和操作的集合，可以看做是已实现了的数据结构，后者是前者的一种简化情况。

5、数据类型和抽象数据类型是如何定义的？二者有何相同和不同之处？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？数据类型和抽象数据类型是如何定义的？二者有何相同和不同之处？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？

答：数据类型是程序设计语言中的一个概念，数据类型是值的集合和操作的集合，可以看做是已实现了的数据结构

抽象数据类型指一个数学模型及定义在该模型上的一组操作。抽象的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示与实现无关。无论其内部如何变化。只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念，但是抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义，表示和实现三部分，封装在一起，对用户透明(提供接口)，而不必了解实现细节。

6、名词解释

7、算法的时间复杂度答：算法时间复杂度用来度量算法执行时间的多少，用大O阶表示，即T(n)=O(f(n))，其中n为问题规模，也就是问题的大小

8、算法的五个重要特性

有穷性、确定性、可行性、输入、输出

9、评价算法好坏的依据

正确性、可读性、健壮性、高效率和低存储需求

1、对顺序存储结构和链式存储结构，比较它们的优缺点。在什么情况下用顺序表比链表好？

1）顺序存储时，相邻数据元素的存放地址相邻（逻辑与物理统一），内存中可用存储单元的地址也连续。优点：存储密度大，存储空间利用率高。缺点：插入删除需要移动元素。2）链式存储时，相邻元素随意存放，存储空间由结点值和指针两部分组成。优点：插入删除方便。缺点：存储利用率低。在线性表长度变化不大，主要操作是查找时，采用顺序表。在线性表长度变化较大，插入删除操作时，采用链表。

2、试举一例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。答：线性表的插入删除操作。在顺序存储方式下平均移动一半元素，时间复杂度为O(n),在链式存储方式下，插入和删除的时间复杂度都是O(1)。

3、说明头指针、头节点、首元结点的概念

头指针是指向链表中第一个结点（或头节点或首元结点）的指针。头节点是在链表的首元结点之前附加的一个结点，头结点是为了操作的统一方便而设立的。数据域一般无意义，只放空表标志和表长等信息。

首元素结点是指链表中存储线性表中第一个元素结点。

3、简述顺序存储队列假溢出的避免方法及队满和空的条件。答：避免方法：一是将队列元素向前“平移”(占用0至rear －front 1);二是将队列看成首尾相连，即看做循环队列(0...m－1)。在循环队列下，定义front＝rear时为队空，而判断队满则常用两种方法:一种是用 “牺牲一个单元” ，即rear+1=front (准确说是(rear+1) %m= =front 时，m是队列容量)时为队满:另一种方法是 “设标记”，如设标记tag, tag=0时为队空: tag=1时，若因插人导致front=rear 则为队满。

1、栈、队列的名词解释。两者之间的联系与区别。栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出表。队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾， 允许删除的端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出表。栈与队列都是操作受限的线性表，只允许在端点插入删除。都可通过顺序结构和链式结构实现。插入删除时间复杂度都为O(1)。栈只允许在栈顶插入删除，队列在队头删除队尾插入。

2、栈和队列的应用有？

栈：表达式的转换和求值、函数调用和递归实现、深度优先搜索遍历

队列：计算机系统中各种资源的管理、消息缓冲器的管理、广度优先搜索遍历

2、什么是递归程序？

一个函数在结束本函数前，直接或间接调用函数自身，称为递归。

递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。

递归程序执行中需要借助栈这种数据结构来实现。

递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序有基本项和归纳项组成。

1、什么是串？

串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。

2、描述一下概念的区别：空格串和空串

空格是一个字符，其ASCII码值是32。空格串是用空格组成的串，其长度等于空格的个数。

空串是不含任何字符的串，即空串的长度是零。

1、什么是广义表？广义表与线性表的区别

线性表中的元素可以是各种各样的，但必须具有相同的性质，属于同一数据对象。

广义表中的元素可以是元素也可以是子表。

2、试叙述一维数组和有序表的异同

一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中的元素按值排序（非递增或非递减），而一维数组中元素没有按元素值排列顺序的要求。

1、树与二叉树的区别和联系？

树与二叉树是两种不同的数据结构，在逻辑上都是树形结构，区别主要有：

一是二叉树的度至多为2，树无此限制；

二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还有右子树，树无此限制；

三是二叉树允许为空，树一般不允许为空。

1、完全图

也叫简单完全图，假设一个图有n个顶点，那么如果任意两个顶点之间都有边的话，该图就称为完全图。

2、连通、连通分量、强连通分量的概念，极大连通子图？极小连通子图？在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。图中任意两点是连通的，则称图G为连通图。无向图中的极大连通子图称为连通分量。有向图中，若v到w和w到v都有路径存在，则称这两个点是强连通的。任一对顶点都是强连通的，则此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

极大是要求该连通子图包含其所有的边（暗指无向图），亦为连通分量。

极小是在保持连通的情况下使边数最少的子图（暗指无向图），亦为最小生成树。

3、对一个图进行遍历可以获得不同的遍历序列，那么导致得到不同遍历序列不唯一的因素有哪些？

遍历不唯一的因素有：开始遍历的结点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。

4、在什么情况下，Prim算法和Kruskual算法生成不同的最小生成树MST？

在有相同权值边时生成不同的MST，在这种情况下，用Prim算法或Kruskual算法会产生不同的MST。

6、Prim算法和Kruskual算法区别

Prim算法是加点法，适合边稠密图；Kruskual算法是一种按权值的递增次序选择合适边来构造生成树的加边法，适合边稀疏而顶点较多的图。

1、散列表存储的基本思想是什么？

散列表的基本思想是用关键字的值决定数据元素的存储地址

2、散列表存储中解决碰撞的基本方法有哪些？

a、开放定址法 根据di的取值又分为线性探测再散列、二次探测再散列、伪随机探测再散列

b、再散列法

c、链地址法

d、建立公共溢出区

3、如何衡量hash函数的优劣？

能否将关键字均匀映射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。

4、在查找算法中，设置监视哨的作用是什么？

监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。5、对于一个有序顺序表来说，折半查找是否任何时候比顺序查找快？为什么？答：并非在任何情况下折半查找都比顺序查找快。例如，若待查元素是该顺序表的第一个元素，则顺序查找顺序表会更快。对有序顺序表采用顺序查找，若元素存在表中，则在任一位置，查找都可能成功。同样，若元素不在表中，则在任一位置， 查找都可能结束。折半查找必须经一-系列计算，方知查找成功还是失败。尽管如此，一般说来，在大多数情况下，折半查找还是比顺序查找快。

1、排序稳定性的概念假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的。

2、稳定排序有哪些?不稳定排序有哪些？

稳定排序：直接插入排序、冒泡排序、归并排序、基数排序

不稳定排序：选择排序、希尔排序、快速排序、堆排序

3、快速排序是在所有情况下，排序速度最快的吗？为什么？

不是，因为当序列已有序时，快速排序退化成了冒泡排序，时间复杂度为O(n2）。

当待排序列无序，使每次划分完成后，枢轴（pivot）两侧子文件长度相当，此时快速排序性能最好。

4、

比较次数 与序列初态 无关 的算法是：二路归并排序、简单选择排序、基数排序 比较次数 与序列初态 有关 的算法是：快速排序、直接插入排序、冒泡排序、堆排序、希尔排序

5、简述堆的结构

堆是一种特殊的完全二叉树，所有父结点都比子结点要小的完全二叉树我们称为最小堆。反之，如果所有父结点都比子结点要大，这样的完全二叉树称为最大堆。

1、文件是由大量性质相同的记录组成的集合、按记录类型不同分为操作系统文件和数据库文件。

2、文件存储结构的基本形式有哪些？

文件基本组织方式有顺序组织、索引组织、散列组织和链组织。

文件的存储结构可以采用将基本组织结合的方法，常用的结构有顺序结构、索引结构、散列结构。