为程序员准备的数据结构面试题

不少程序员在新年过后想要提升自己，跳槽到更有前途的大厂中，他们也已经开始申请各方面的相关开发职位，但他们中许多人还不知道能够遇到什么样的编程面试题，今天小编就来总结一下：

一、什么是数据结构?

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。

数据的逻辑结构包括4种

(1)集合：数据元素之间除了有相同的数据类型再没有其他的关系

(2)线性结构：数据元素之间是一对一的关系 ——线性表、栈、队列

(3)树形结构：数据元素之间是一对多的关系

(4)图状结构：数据元素之间是多对多的关系。

物理结构包括顺序存储结构和链式存储结构。

二、解释一下顺序存储与链式存储

顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。

三、头指针和头结点的区别?

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

四、线性结构的特点

(1)集合中必存在唯一的一个"第一个元素";

(2)集合中必存在唯一的一个"最后的元素";

(3)除最后元素之外，其它数据元素均有唯一的"后继";

(4)除第一元素之外，其它数据元素均有唯一的"前驱"。

五、数组和链表的区别?

从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。

六、单链表结构和顺序存储结构的区别?

当进行插入和删除操作时，顺序存储结构每次都需要移动元素，总的时间复杂度为O(n^2)，而链式存储结构确定i位置的指针后，其时间复杂度仅为O(1)。由于顺序存储结构需要进行预分配存储空间，所以容易造成空间浪费或者溢出。链式存储结构不需要预分配存储空间，元素个数不受限制。

七、栈和队列的区别

队列是允许在一段进行插入另一端进行删除的线性表，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。

栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行。由于进栈和出栈都是在栈顶进行，所以要有一个size变量来记录当前栈的大小，当进栈时size不能超过数组长度，size+1，出栈时栈不为空，size-1。

八、栈的两个应用：括号匹配是怎么应用的?(如何实现要会用语言描述)

括号匹配，表达式的计算

将中缀表达式变为后缀表达式：

①从左往右，运算数输出，运算符号入栈

②栈内：(优先级低，()内符号依次入栈一起输出

​ 同级符号先进栈的先输出——b站2.2.4

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kVzQBPAL-1626507074517)(C:\Users\24380\Pictures\栈的应用1.jpg)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iTYMxGrX-1626507074522)(C:\Users\24380\Pictures\栈的应用2.jpg)]

bool match(string str)
{
	stack<int> con;
	int count = 0;
	string::iterator iter = str.begin();
	while (iter != str.end())
	{
		if (*iter == '(')
			con.push(*iter);
		else if (*iter == ')')
		{
			if (con.empty())
				return 0;
			else
			{
				count++;
				con.pop();
			}
		}
		iter++;
	}
	if (con.empty())
	{
		cout << "匹配次数:" << count << endl;
		return 1;
 
	}
	else
	{
		return 0;
	}
 
}

#include<iostream>
#include<stack>
#include<stdexcept>
using namespace  std;
int cerr_flag=0;
int calculate(int len, char* str)
{
	stack<int> Num;
	stack<char> Symbol;
	bool bFlag = false;
	char c,OperSymbol;
	int temp;
	int num1, num2;
	for (int i = 0; i < len; i++)
	{
		c = str[i];
		if (isdigit(c))
		{
			temp = c - '0';
			Num.push(temp);
			continue;
		}
		else if (c == '*' || c == '/')
		{
			if (Symbol.size() > 0 && (Symbol.top() == '*' || Symbol.top() == '/'))
 
				bFlag = true;
			else
				bFlag = false;
 
		}
		else if (c == '+'||c=='-')
		{
			if (Symbol.size() == 0)
				bFlag = false;
			else
				bFlag = true;
 
		}
		if (bFlag)
		{
			num1 = Num.top();
			Num.pop();
			num2 = Num.top();
			Num.pop();
			OperSymbol = Symbol.top();
			Symbol.pop();
 
			switch (OperSymbol)
			{
			case '+':
				temp = num2 + num1;
				Num.push(temp);
				break;
			case '-':
				temp = num2 - num1;
				Num.push(temp);
				break;
			case '*':
				temp = num2 * num1;
				Num.push(temp);
				break;
			case '/':
				try{
					if (num1 == 0)
						throw invalid_argument("除数为0");	
				}
				catch (const invalid_argument& e)
				{
					cerr << "捕获异常：" << e.what() << endl;
					cerr_flag = 1;
					return NULL ;
				}
				temp = num2 / num1;
				Num.push(temp);
				break;
			default:
				break;
			}
 
		}
		Symbol.push(c);
	}
	while (Symbol.size() > 0)
	{
		num1 = Num.top();
		Num.pop();
		num2 = Num.top();
		Num.pop();
		OperSymbol = Symbol.top();
		Symbol.pop();
 
		switch (OperSymbol)
		{
		case '+':
			temp = num2 + num1;
			Num.push(temp);
			break;
		case '-':
			temp = num2 - num1;
			Num.push(temp);
			break;
		case '*':
			temp = num2 * num1;
			Num.push(temp);
			break;
		case '/':
			try{
				if (num1 == 0)
					throw invalid_argument("除数为0");
			}
			catch (const invalid_argument& e)
			{
				cerr << "捕获异常：" << e.what() << endl;
				cerr_flag = 1;
				return NULL;
			}
			temp = num2 / num1;
			Num.push(temp);
			break;
		default:
			break;
		}
	}
	return Num.top();
}
int main()
{
	char *a = "1+4*4-8/2";
	char *b = "2-9/0+2*3";
	int result1 = calculate(strlen(a), a);
	if (cerr_flag == 0)
	{
		cout << "运算结果为：" << result1<<endl;
	}
	cout << endl;
	int result2 = calculate(strlen(b), b);
	if (cerr_flag == 0)
	{
		cout << "运算结果为：" << result2;
	}
	return 0;
}

如何构造哈夫曼树?(如何实现要会用语言描述)

找w最小求和，再找w最小;左小右大;构造结束后，左0右1

[例]频率表 A：60, B:45, C:13 D:69 E:14 F:5 G:3**

每个 字符 的 二进制编码 为(从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码)

以上就是“为程序员准备的数据结构面试题”，你能回答上来吗?如果想要了解更多的相关内容，可以关注极悦Java官网。