不少程序員在新年過后想要提升自己，跳槽到更有前途的大廠中，他們也已經開始申請各方面的相關開發職位，但他們中許多人還不知道能夠遇到什么樣的編程面試題，今天小編就來總結一下：

一、什么是數據結構?

數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。結構包括邏輯結構和物理結構。

數據的邏輯結構包括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面試題相關內容，可以關注動力節點Java官網。