不少程序員在新年過(guò)后想要提升自己，跳槽到更有前途的大廠中，他們也已經(jīng)開(kāi)始申請(qǐng)各方面的相關(guān)開(kāi)發(fā)職位，但他們中許多人還不知道能夠遇到什么樣的編程面試題，今天小編就來(lái)總結(jié)一下：

一、什么是數(shù)據(jù)結(jié)構(gòu)?

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。結(jié)構(gòu)包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)包括4種

(1)集合：數(shù)據(jù)元素之間除了有相同的數(shù)據(jù)類(lèi)型再?zèng)]有其他的關(guān)系

(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間是一對(duì)一的關(guān)系 ——線性表、棧、隊(duì)列

(3)樹(shù)形結(jié)構(gòu)：數(shù)據(jù)元素之間是一對(duì)多的關(guān)系

(4)圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間是多對(duì)多的關(guān)系。

物理結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

二、解釋一下順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)

順序存儲(chǔ)結(jié)構(gòu)是用一段連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)數(shù)據(jù)元素，可以進(jìn)行隨機(jī)訪問(wèn)，訪問(wèn)效率較高。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用任意的存儲(chǔ)空間來(lái)存儲(chǔ)數(shù)據(jù)元素，不可以進(jìn)行隨機(jī)訪問(wèn)，訪問(wèn)效率較低。

三、頭指針和頭結(jié)點(diǎn)的區(qū)別?

頭指針：是指向第一個(gè)節(jié)點(diǎn)存儲(chǔ)位置的指針，具有標(biāo)識(shí)作用，頭指針是鏈表的必要元素，無(wú)論鏈表是否為空，頭指針都存在。

頭結(jié)點(diǎn)：是放在第一個(gè)元素節(jié)點(diǎn)之前，便于在第一個(gè)元素節(jié)點(diǎn)之前進(jìn)行插入和刪除的操作，頭結(jié)點(diǎn)不是鏈表的必須元素，可有可無(wú)，頭結(jié)點(diǎn)的數(shù)據(jù)域也可以不存儲(chǔ)任何信息。

四、線性結(jié)構(gòu)的特點(diǎn)

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

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

(3)除最后元素之外，其它數(shù)據(jù)元素均有唯一的"后繼";

(4)除第一元素之外，其它數(shù)據(jù)元素均有唯一的"前驅(qū)"。

五、數(shù)組和鏈表的區(qū)別?

從邏輯結(jié)構(gòu)來(lái)看：數(shù)組的存儲(chǔ)長(zhǎng)度是固定的，它不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況。鏈表能夠動(dòng)態(tài)分配存儲(chǔ)空間以適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況，并且易于進(jìn)行插入和刪除操作。

從訪問(wèn)方式來(lái)看：數(shù)組在內(nèi)存中是一片連續(xù)的存儲(chǔ)空間，可以通過(guò)數(shù)組下標(biāo)對(duì)數(shù)組進(jìn)行隨機(jī)訪問(wèn)，訪問(wèn)效率較高。鏈表是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)空間不是必須連續(xù)的，可以是任意的，訪問(wèn)必須從前往后依次進(jìn)行，訪問(wèn)效率較數(shù)組來(lái)說(shuō)比較低。

如果從第i個(gè)位置插入多個(gè)元素，對(duì)于數(shù)組來(lái)說(shuō)每一次插入都需要往后移動(dòng)元素，每一次的時(shí)間復(fù)雜度都是O(n)，而單鏈表來(lái)說(shuō)只需要在第一次尋找i的位置時(shí)時(shí)間復(fù)雜度為O(n)，其余的插入和刪除操作時(shí)間復(fù)雜度均為O(1)，提高了插入和刪除的效率。

六、單鏈表結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)的區(qū)別?

當(dāng)進(jìn)行插入和刪除操作時(shí)，順序存儲(chǔ)結(jié)構(gòu)每次都需要移動(dòng)元素，總的時(shí)間復(fù)雜度為O(n^2)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)確定i位置的指針后，其時(shí)間復(fù)雜度僅為O(1)。由于順序存儲(chǔ)結(jié)構(gòu)需要進(jìn)行預(yù)分配存儲(chǔ)空間，所以容易造成空間浪費(fèi)或者溢出。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不需要預(yù)分配存儲(chǔ)空間，元素個(gè)數(shù)不受限制。

七、棧和隊(duì)列的區(qū)別

隊(duì)列是允許在一段進(jìn)行插入另一端進(jìn)行刪除的線性表，對(duì)于進(jìn)入隊(duì)列的元素按“先進(jìn)先出”的規(guī)則處理，在表頭進(jìn)行刪除在表尾進(jìn)行插入。

棧是只能在表尾進(jìn)行插入和刪除操作的線性表。對(duì)于插入到棧的元素按“后進(jìn)先出”的規(guī)則處理，插入和刪除操作都在棧頂進(jìn)行。由于進(jìn)棧和出棧都是在棧頂進(jìn)行，所以要有一個(gè)size變量來(lái)記錄當(dāng)前棧的大小，當(dāng)進(jìn)棧時(shí)size不能超過(guò)數(shù)組長(zhǎng)度，size+1，出棧時(shí)棧不為空，size-1。

八、棧的兩個(gè)應(yīng)用：括號(hào)匹配是怎么應(yīng)用的?(如何實(shí)現(xiàn)要會(huì)用語(yǔ)言描述)

括號(hào)匹配，表達(dá)式的計(jì)算

將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式：

①?gòu)淖笸遥\(yùn)算數(shù)輸出，運(yùn)算符號(hào)入棧

②棧內(nèi)：(優(yōu)先級(jí)低，()內(nèi)符號(hào)依次入棧一起輸出

? 同級(jí)符號(hào)先進(jìn)棧的先輸出——b站2.2.4

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-kVzQBPAL-1626507074517)(C:\Users\24380\Pictures\棧的應(yīng)用1.jpg)]

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-iTYMxGrX-1626507074522)(C:\Users\24380\Pictures\棧的應(yīng)用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 << "匹配次數(shù):" << 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("除數(shù)為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("除數(shù)為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 << "運(yùn)算結(jié)果為：" << result1<<endl;
	}
	cout << endl;
	int result2 = calculate(strlen(b), b);
	if (cerr_flag == 0)
	{
		cout << "運(yùn)算結(jié)果為：" << result2;
	}
	return 0;
}

如何構(gòu)造哈夫曼樹(shù)?(如何實(shí)現(xiàn)要會(huì)用語(yǔ)言描述)

找w最小求和，再找w最小;左小右大;構(gòu)造結(jié)束后，左0右1

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

每個(gè) 字符 的 二進(jìn)制編碼 為(從根節(jié)點(diǎn) 數(shù)到對(duì)應(yīng)的葉子節(jié)點(diǎn)，路徑上的值拼接起來(lái)就是葉子節(jié)點(diǎn)字母的應(yīng)該的編碼)

以上就是“為程序員準(zhǔn)備的數(shù)據(jù)結(jié)構(gòu)面試題”，你能回答上來(lái)嗎?如果想要了解更多的Java面試題相關(guān)內(nèi)容，可以關(guān)注動(dòng)力節(jié)點(diǎn)Java官網(wǎng)。