数据结构简答题期末复习

灰太狼 2022-04-02 13:22 403阅读 0赞

**1、数据结构定义**

数据结构是指相互之间存在着一种或多种关系的[数据][Link 1]元素的集合和该集合中数据[元素][Link 2]之间的关系组成。

**2、其逻辑结构的四种关系并画出它们的关系图**

1.  **集合结构 2.线性结构 3.树形结构 4.图形结构**

https://blog.csdn.net/dyw\_666666/article/details/82343558

**3、数据结构的特性**

数组：优点是插入快，如果知道下标，可以非常快地存取。缺点是查找慢，删除慢，大小固定。

有序数组：优点是比无序的数据查找快。缺点是删除和插入慢，大小固定。

栈：优点是提供后进先出方式的存取。缺点是存取其他项很慢。

队列：提供先进先出方式的存取。缺点是存取其他项很慢。

链表：优点是插入快，删除快。缺点是查找慢。

二叉树：优点是查找、插入、删除都快（如果树保持平衡）。缺点是删除算法复杂。

红－黑树：查找、插入、删除都快。树总是平衡的。缺点是算法复杂。

2-3-4树：优点是查找、插入、删除都快。树总是平衡的。类似的树对磁盘存储有用。缺点是算法复杂。

哈希表：优点是如果关键字已知则存取极快。插入快。缺点是删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分。

堆：优点是插入、删除快，对最大数据项的存取很快。缺点是对其他数据项存取慢。

图：优点是对现实世界建模。缺点是有些算法且复杂。

**4、存储结构由哪两种基本的存储方法实现？**

主要分顺序存储结构和链式存储结构两种。

**5、顺序表和链表的比较？p50**

一.顺序表：

1.1.从空间角度：

分配方式：静态分配

存储密度：为1

1.2.从时间角度：

存取方式：随机存取

操作：插入删除：O(N) ; 按序访问：O(1);

二.链表：

2.1.从空间角度：

分配方式：动态分配

存储密度：小于1

2.2.从时间角度：

存取方式：顺序存取

**6、单链表、循环表和双向链表的*比较***

*《数据结构-C语言版》(严蔚敏)* p51

**7、栈和队列的异同点？**

1) 栈与队列的相同点：

1.  都是线性结构。
2.  插入操作都是限定在表尾进行。
3.  都可以通过顺序结构和链式结构实现。、
4.  插入与删除的时间复杂度都是O（1），在空间复杂度上两者也一样。
5.  多链栈和多链队列的管理模式可以相同。

2) 栈与队列的不同点：

1.  删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。
2.  应用场景不同；常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。
3.  顺序栈能够实现多栈空间共享，而顺序队列不能。

**8、衡量算法的基本标准？**

时间复杂度：程序执行的次数

空间复杂度：程序执行过程中大概所占用的最大内存

难易程度

健壮性

**9、二叉树的三种遍历方法**

[https://blog.csdn.net/dyw\_666666/article/details/85233036][https_blog.csdn.net_dyw_666666_article_details_85233036]

遍历二叉树的所有结点且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。

前序遍历：根节点->左子树->右子树（根节点在前面）

中序遍历：左子树->根节点->右子树（根节点在中间）

后序遍历：左子树->右子树->根节点（根节点在后边）

例如：求下面树的三种遍历

![http://hi.csdn.net/attachment/201109/21/0\_13166086420zyt.gif][http_hi.csdn.net_attachment_201109_21_0_13166086420zyt.gif]

前序遍历：abdefgc

中序遍历：debgfac

后序遍历：edgfbca

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE
[Link 2]: https://baike.baidu.com/item/%E5%85%83%E7%B4%A0
[https_blog.csdn.net_dyw_666666_article_details_85233036]: https://blog.csdn.net/dyw_666666/article/details/85233036
[http_hi.csdn.net_attachment_201109_21_0_13166086420zyt.gif]: /images/20220402/5d10244636d94a30b05a31e495f0e88c.png