Question

有一道数据结构的题不会写？

第二题第三问，不应该是（11×9＋4）×2＝206吗?





Answer 1

数据结构习题求解 用C++写,我不会用C++写,以前学的是C实验题2-1 实现顺序表的各种基本运算,完成以下功能:(1) 初始化顺序表L.(2) 采用尾插

Answer 2

我也不会呀，我都不知道什么数据结构，哈哈哈哈，不好意思了

Answer 3

简述一下思路吧: 通过单向循环链表模拟参与报数的人（data：该人的密码 next：该人的下一个人）

Answer 4

瑞士计算机科学家Niklaus Wirth在1976年写了一本书，名为《算法+数据结构=编程》。

40多年后，这个等式仍被奉为真理。这就是为什么在面试过程中，需要考察软件工程师对数据结构的理解。

几乎所有的问题都需要面试者对数据结构有深刻的理解。无论你是初入职场的新兵，还是久经沙场的老兵。

即便对于一些非常基础的工作来说，学习数据结构也是必须的。那么，就让我们先从一些基本概念开始入手。

1、什么是数据结构

简单的说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题的时候选择最合适的数据结构。

2、为什么我们需要数据结构

数据是计算机科学当中最关键的实体，而数据结构则可以将数据以某种组织形式存储，因此，数据结构的价值不言而喻。

无论你以何种方式解决何种问题，你都需要处理数据——无论是设计员工薪水、股票价格、购物清单，还是简单的电话簿问题。

数据需要根据不同的场景，按照待定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

3、常见的数据结构

首先列出一些最常见的数据结构，我们将逐一说明。

• 数组

• 栈

• 队列

• 链表

• 树

• 图

• 字典树（高效的树形结构）

• 散列表（哈希表）

4、数组

数组是最简单的、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。下图是一个包含元素（1、2、3、4）的简单数组，数组长度为4。




请点击输入图片描述

每个数据元素都关联一个正数值，我们称之为索引，它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。

以下是数组的两种类型：

• 一维数组（如上图所示）

• 多维数组（数组的数组）

数组的基本操作：

• Insert——在指定索引位置插入一个元素

• Get——返回指定索引位置的元素

• Delete——删除指定索引位置的元素

• Size——得到数组所有的元素

面试中关于数组的常见问题：

• 寻找数组中第二小的元素

• 找到数组中第一个不重复出现的整数

• 合并两个有序数组

• 重新排列数组中的正负值

5、栈

可以把栈当成一叠书，为了拿到中间的书，只能先把上面的书拿走，这就是LIFO（后进先出）的工作原理。

下图是包含三个数据元素（1、2、3）的栈其中顶部的3将被先移除。




请点击输入图片描述

栈的基本操作：

• Push——在顶部插入一个元素

• Pop——返回并移除栈顶元素

• isEmpty——如果栈为空，则返回true

• Top——返回顶部元素，但不移除

面试中关于栈的常见问题：

• 使用栈计算后缀表达式

• 对栈的元素进行排序

• 判断表达式是否括号平衡

6、队列

与栈相似，队列是另一种顺序存储元素的线性数据结构。栈与队列的最大差别在于是LIFO（后进先出），而队列是FIFO（先进先出）。

下图是包含四个元素（1、2、3、4）的队列，其中在顶部的1先被移除。




请点击输入图片描述

队列的基本操作：

• Enqueue()——队列尾部插入元素

• Dequeue()——移除队列头部元素

• isEmpty()——如果队列为空，则返回true

• Top()——返回队列的第一个元素

面试中关于队列的常见问题：

• 使用队列表示栈

• 对队列的前n个元素倒叙

• 使用队列生成从1到n的二进制数

7、链表

链表乍一看有点像数组，但在内存分配、内部结构以及数据插入和删除的基本操作方面均有所不同。

链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。链表还包含一个头指针，它指向链表的第一个元素，但当列表为空时，它指向null或无具体内容。

链表一般用于实现文件系统、哈希表和邻接表。链表内部结构展示：




请点击输入图片描述

链表包括以下类型：

• 单链表（单向）

• 双链表（双向）

链表的基本操作：

• InsertAtEnd——在链表的末尾插入指定元素

• InsertAtHead——在链接列表的开头插入指定元素

• Delete——从链接列表中删除指定元素

• DeleteAtHead——删除链接列表的第一个元素

• Search——从链表中返回指定元素

• isEmpty——如果链表为空，则返回true

面试中关于链表的常见问题：

• 反转链表

• 检测链表中的循环

• 返回链表倒数第N个节点

• 删除链表中的选项

8、图

图是一组以网络形式相互连接的节点。及诶单也称为顶点。一对节点（x,y）称为边（edge），表示顶点x连接到顶点y。边可以包含权重、成本，显示从顶点x到y所需的成本。




请点击输入图片描述

图的类型：

• 无向图

• 有向图

在程序语言中，图可以用两种形式表示：

• 邻接矩阵

• 邻接表

常见图遍历算法：

• 广度优先搜索

• 深度优先搜索

面试中关于图的常见问题：

• 实现广度和深度优先搜索

• 检查图是否为树

• 计算图的边数

• 找到两个顶点之间的最短路径

9、树

树形结构是一种层级式的数据结构，由节点和连接它们的边组成。树类似于图，但区分树和图的重要特征是树中不存在环路。这是一个简单树的示意图，以及树结构中的基本术语：




请点击输入图片描述

• Root - 根节点

• Parent - 父节点

• Child - 子节点

• Leaf - 叶子节点

• Sibling - 兄弟节点

以下是树形结构的主要类型：

• N元树

• 平衡树

• 二叉树

• 二叉搜索树

• A V L树

• 红黑树

• 2-3树

面试中关于树结构的常见问题：

• 求二叉树的高度

• 在二叉搜索树中查找第n个最大值

• 查找与根节点距离n的节点

• 二叉树中查找给定节点的祖先节点

10、字典树

字典树也称“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。它能够提供快速检索，主要用于搜索字典中的单词，在搜索引擎中自动提供建议，甚至被用于IP路由。

一下是字典树中存储三个单词“top”，“thus”，“their”的例子，绿色部分代表三个单词的底部：




请点击输入图片描述

面试中关于字典树的常见问题：

• 计算字典树中的总单词树

• 打印存储在字典树中的所有单词

• 使用字典树对数组的元素进行排序

• 使用字典树从字典中形成单词

11、哈希表

哈希法是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引中的过程。因此，对象以键值存储，这些键值对的集合被称为“字典”。可以使用键搜索每个对象。基于哈希法有很多不同的数据结构，但最常用的数据结构是哈希表（通常由数组实现）。

散列数据结构的性能取决于以下三个因素：

• 哈希函数

• 哈希表的大小

• 碰撞处理方法

下图为如何在数组中映射哈希键值的说明：




请点击输入图片描述

面试中关于哈希结构的常见问题：

• 在数组中查找对称键值对

• 追踪遍历的完整路径

• 查找数组是否是另一个数组的子集

• 检查给定的数组是否不相交