這是我的學(xué)長，SDZ學(xué)長整理，我就發(fā)出了，如果你們有幸去了浙大軟科記得謝謝他，哈哈哈

這兩種方法在形式上相像，其區(qū)別在于：pa是指針變量，a是數(shù)組名。值得注意的是：pa是一個可以變化的指針變量，而a是一個常數(shù)。因為數(shù)組一經(jīng)被說明，數(shù)組的地址也就是固定的，因此a是不能變化的，不允許使用a＋＋、＋＋a或語句a＋=10，而pa＋＋、＋＋pa、pa＋=10則是正確的。

假設(shè)現(xiàn)在我們有以下數(shù)組：

int a[5] = { 1,2,3,4,5 }; 那么，在C語言中如何取得數(shù)組中的元素呢？第一種方式：直接通過下標獲取//取得第0個元素 printf("%d\n", a[0]);

第二種方式：通過數(shù)組的地址，在C語言中，數(shù)組的名稱實際上就是該數(shù)組首個元素的地址，可以通過(*名稱)獲取其中的值。

//獲取第0個元素 printf("%d\n", *a); //獲取第1個元素，只需要將地址+1，存儲輸出的是是連續(xù)的內(nèi)存空間 printf("%d\n", *(a+1));

第三種方式：通過指向該數(shù)組的指針。

//聲明一個指針，同時讓其指向a int* p = a; //通過解引用來獲取指針p指向的值，獲得第0個元素 printf("%d\n", *p); //指針+1即可獲得第1個元素 printf("%d\n", *(p + 1));

• （1）棧（stack）：數(shù)調(diào)用過程中的各種參數(shù)、局部變量、返回值以及函數(shù)返回地址。
• （2）堆（heap）：用于程序動態(tài)申請分配和釋放空間。C語言中的malloc和free，C++中的new和delete均是在堆中進行的。
• （3）全局（靜態(tài)）存儲區(qū)：分為DATA段和BSS段。DATA段（全局初始化區(qū)）存放初始化的全局變量和靜態(tài)變量；BSS段（全局未初始化區(qū)）存放未初始化的全局變量和靜態(tài)變量。
• （4）文字常量區(qū)：存放常量字符串。程序結(jié)束后由系統(tǒng)釋放。
• （5）程序代碼區(qū)：存放程序的二進制代碼。

英文自我介紹，提問你做過哪些項目并介紹項目內(nèi)容實現(xiàn)方法，問你來自哪里介紹你的家鄉(xiāng)/學(xué)校，研究生計劃，為什么想要讀研等問題。

計算機網(wǎng)絡(luò)

牢記每一層的協(xié)議及其內(nèi)容、應(yīng)用。

物理層：

數(shù)據(jù)鏈路層

功能：為網(wǎng)絡(luò)層提供服務(wù)；封裝成幀（透明傳輸）；鏈路管理；流量控制；差錯控制；

網(wǎng)絡(luò)層

功能一：路由選擇與分組轉(zhuǎn)發(fā)（最佳路徑）

功能二：異構(gòu)網(wǎng)絡(luò)互聯(lián)

功能三：擁塞控制（全局性）

協(xié)議：IP協(xié)議

傳輸層

傳輸層提供進程和進程之間的邏輯通信。
網(wǎng)絡(luò)層提供主機之間的邏輯通信。

復(fù)用和分用
復(fù)用：應(yīng)用層所有的應(yīng)用進程都可以通過傳輸層再傳輸?shù)骄W(wǎng)絡(luò)層。
分用：傳輸層從網(wǎng)絡(luò)層收到數(shù)據(jù)后交付指明的應(yīng)用進程。

傳輸層對收到的報文進行差錯檢測。

數(shù)據(jù)鏈路層的首部校驗和只校驗了首部

傳輸層的兩種協(xié)議TCP與UDP。

物理層

在物理層上所傳送的數(shù)據(jù)單位是比特。 物理層(physical layer)的作用是實現(xiàn)相鄰計算機節(jié)點之間比特流的透明傳送，盡可能屏蔽掉具體傳輸介質(zhì)和物理設(shè)備的差異。使其上面的數(shù)據(jù)鏈路層不必考慮網(wǎng)絡(luò)的具體傳輸介質(zhì)是什么。“透明傳送比特流”表示經(jīng)實際電路傳送后的比特流沒有發(fā)生變化，對傳送的比特流來說，這個電路好像是看不見的。

解釋什么DNS，為什么要用DNS，有了IP地址為什么還要有域名？域名結(jié)構(gòu)為什么這樣設(shè)計？ICMP、IGMP協(xié)議；IP地址的分類？等。
1.OSl，TCP/IP；五層協(xié)議的體系結(jié)構(gòu)，以及各層協(xié)議
2.IP地址的分類

• 分類的IP地址(網(wǎng)絡(luò)號+主機號)
  
• 子網(wǎng)的劃分（網(wǎng)絡(luò)號+子網(wǎng)號+主機號)
• 構(gòu)成超網(wǎng)（無分類編址方法）

3.ARP是地址解析協(xié)議，簡單語言解釋一下工作原理
1.首先，每個主機都會在自己的ARP緩沖區(qū)中建立一個ARP列表，
以表示IP地址和MAC地址之間的對應(yīng)關(guān)系。

2.當源主機要發(fā)送數(shù)據(jù)時，首先檢查ARP列表中是否有對應(yīng)IP地址的目的主機的MAC地址，
如果有，則直接發(fā)送數(shù)據(jù)，
如果沒有，就向本網(wǎng)段的所有主機發(fā)送ARP數(shù)據(jù)包，
該數(shù)據(jù)包包括的內(nèi)容有：源主機 IP地址，源主機MAC地址，目的主機的IP 地址。

3.當本網(wǎng)絡(luò)的所有主機收到該ARP數(shù)據(jù)包時，首先檢查數(shù)據(jù)包中的IP地址是否是自己的IP地址，
如果不是，則忽略該數(shù)據(jù)包，
如果是，則首先從數(shù)據(jù)包中取出源主機IP地址和MAC地址寫入到ARP列表中，
如果已經(jīng)存在，則覆蓋，
然后將自己的MAC地址寫入ARP響應(yīng)包中，告訴源主機自己是它想要找的MAC地址。

4.源主機收到ARP響應(yīng)包后，將目的主機的IP地址和MAC地址寫入ARP列表，并利用此信息發(fā)送數(shù)據(jù)。
如果源主機一直沒有收到ARP響應(yīng)數(shù)據(jù)包，表示ARP查詢失敗。

廣播發(fā)送ARP請求，單播發(fā)送ARP響應(yīng)。

4.TCP三次握手和四次揮手的全過程

5.在瀏覽器中輸入www.baidu.com后執(zhí)行的全部過程

6.TCP和UDP的區(qū)別？
TCP與UDP區(qū)別

UDPTCP

是否連接	無連接	面向連接
是否可靠	不可靠傳輸，不使用流量控制和擁塞控制	可靠傳輸，使用流量控制和擁塞控制
連接對象個數(shù)	支持一對一，一對多，多對一和多對多交互通信	只能是一對一通信
傳輸方式	面向報文	面向字節(jié)流
首部開銷	首部開銷小，僅8字節(jié)	首部最小20字節(jié)，最大60字節(jié)
適用場景	適用于實時應(yīng)用（IP電話、視頻會議、直播等）	適用于要求可靠傳輸?shù)膽?yīng)用，例如文件傳輸

7.DNS域名系統(tǒng)，簡單描述其工作原理。
當DNS客戶機需要在程序中使用名稱時，它會查詢DNS服務(wù)器來解析該名稱。客戶機發(fā)送的每條查詢信息包括三條信息：指定的DNS域名，指定的查詢類型，DNS域名的指定類別。基于UDP服務(wù)，端口53. 該應(yīng)用一般不直接為用戶使用，而是為其他應(yīng)用服務(wù)，如HTTP，SMTP等在其中需要完成主機名到IP地址的轉(zhuǎn)換。

客戶機向其本地域名服務(wù)器發(fā)出DNS請求報文

本地域名服務(wù)器收到請求后，查詢本地緩存，假設(shè)沒有該記錄，則以DNS客戶的身份向根域名服務(wù)器發(fā)出解析請求

根域名服務(wù)器收到請求后，判斷該域名所屬域，將對應(yīng)的頂級域名服務(wù)器的IP地址返回給本地域名服務(wù)器

本地域名服務(wù)器向頂級域名服務(wù)器發(fā)出解析請求報文

頂級域名服務(wù)器收到請求后，將所對應(yīng)的授權(quán)域名服務(wù)器的IP地址返回給本地域名服務(wù)器

本地域名服務(wù)器向授權(quán)域名服務(wù)器發(fā)起解析請求報文

授權(quán)域名服務(wù)器收到請求后，將查詢結(jié)果返回給本地域名服務(wù)器

本地域名服務(wù)器將查詢結(jié)果保存到本地緩存，同時返回給客戶機

8.了解交換機、路由器、網(wǎng)關(guān)的概念，并知道各自的用途

交換機（多接口網(wǎng)橋）：擴展以太網(wǎng)

路由器：
第一，網(wǎng)絡(luò)互連
第二，數(shù)據(jù)處理，提供包括分組過濾、分組轉(zhuǎn)發(fā)、優(yōu)先級、復(fù)用、加密、壓縮和防火墻等功能；
第三，網(wǎng)絡(luò)管理，路由器提供包括配置管理、性能管理、容錯管理和流量控制等功能。

網(wǎng)段：一般指一個計算機網(wǎng)絡(luò)中使用同一物理層設(shè)備（傳輸介質(zhì)，中繼器，集線器等）能夠直接通訊的那一部分。

數(shù)據(jù)結(jié)構(gòu)

棧

出棧順序滿足卡特蘭數(shù)：$$(1/(n+1))?C_{2n}^n$$
括號匹配，后綴式的求值

隊列

循環(huán)隊列實現(xiàn)

稀疏矩陣的存儲方法：

順序：三元組法和偽地址法
鏈式：鄰接表法和十字鏈表法

KMP（O(m+n)）

#include<iostream> using namespace std; const int N=1000010; char p[N],s[N]; int n,m; int ne[N]; int main() {cin>>n>>p+1>>m>>s+1;for(int i=2,j=0;i<=n;i++){while(j&&p[i]!=p[j+1]) j=ne[j];if(p[i]==p[j+1]) j++;ne[i]=j;}for(int i=1,j=0;i<=m;i++){while(j&&s[i]!=p[j+1]) j=ne[j];if(s[i]==p[j+1]) j++;if(j==n){printf("%d ",i-j);j=ne[j];}}return 0; }

普通模式串比較優(yōu)點：適合規(guī)模較大的外存字符串匹配，因為可以分段進行，先讀入內(nèi)存一部分進行匹配，完成之后即可寫回外存，確保發(fā)生不匹配的時候不需要將之前的寫回外存的部分再次讀入，減少了I/O操作，提高效率。

二叉樹

五個主要性質(zhì)

在二叉樹的第ｉ（ｉ>=１）層最多有２＾(ｉ - １)個結(jié)點。

深度為k(k>=0)的二叉樹最少有k個結(jié)點，最多有２＾ｋ－１個結(jié)點。

對于任一棵非空二叉樹，若其葉結(jié)點數(shù)為n0，度為2的非葉結(jié)點數(shù)為n2，則ｎ0 = ｎ2 ＋１。
靈活運用：n個節(jié)點的樹，空指針的個數(shù)為n+1.

具有n個結(jié)點的完全二叉樹的深度為int_down(log(2，ｎ)+1=int_UP(log(2，n+1))

如果將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號１，２，３，．．．．．．，ｎ，然后按此結(jié)點編號將樹中各結(jié)點順序的存放于一個一維數(shù)組，并簡稱編號為i的結(jié)點為結(jié)點i（ ｉ>=１ && ｉ<=ｎ）,則有以下關(guān)系：
（1）若 ｉ= 1，則結(jié)點i為根，無父結(jié)點；若 ｉ> 1，則結(jié)點 i 的父結(jié)點為結(jié)點int_DOWN（ｉ / ２）;
（2）若 ２＊ｉ <= ｎ，則結(jié)點 ｉ 的左子女為結(jié)點 ２＊ｉ；
（3）若２＊ｉ＜＝ｎ，則結(jié)點ｉ的右子女為結(jié)點２＊ｉ＋１；
（4）若結(jié)點編號ｉ為奇數(shù)，且ｉ！＝１，它處于右兄弟位置，則它的左兄弟為結(jié)點ｉ－１；
（5）若結(jié)點編號ｉ為偶數(shù)，且ｉ！＝ｎ，它處于左兄弟位置，則它的右兄弟為結(jié)點ｉ＋１；
（6）結(jié)點ｉ所在的層次為 int_DOWN（log（2，ｉ））＋１。

補充：
n個節(jié)點可以構(gòu)造的二叉樹個數(shù)為卡特蘭數(shù)：$$(1/(n+1))?C_{2n}^n$$
遍歷的改進：非遞歸（避免了系統(tǒng)棧）或線索二叉樹（避免用戶棧）

數(shù)據(jù)結(jié)構(gòu)：排序算法及時間復(fù)雜度，隨手寫一個你自己熟悉排序算法（偽代碼形式），二叉樹相關(guān)知識。
九大排序九大排序

所有排序方法可分為兩類，

（1）一類是穩(wěn)定的，包括直接插入排序、起泡排序、和歸并排序，基數(shù)桶式排序；

（2）另一類是不穩(wěn)定的，包括直接選擇排序、希爾排序、快速排序和堆排序。

二叉搜索樹：中序遍歷為順序

AVL樹的旋轉(zhuǎn)：

右旋A：自己左兒子的右兒子–》自己的左兒子，自己–》自己的左兒子的右兒子。

左旋A：自己右兒子的左兒子–》自己的右兒子，自己–》自己的右兒子的左兒子。

#include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<unordered_map> using namespace std; const int N=10005,M=100005; int n,m,K,st[N],l[N],r[N],w[N],h[N],idx=0;void update(int u) {h[u]=max(h[l[u]],h[r[u]])+1; } int get_balance(int u) {return h[l[u]]-h[r[u]]; } void R(int &u) {int p=l[u];l[u]=r[p],r[p]=u;update(u),update(p);u=p; } void L(int &u) {int p=r[u];r[u]=l[p],l[p]=u;update(u),update(p);u=p; }void insert(int &u,int val) {if(u==-1){u=++idx;w[idx]=val;}else if(val<=w[u]){insert(l[u],val);if(get_balance(u)==2){if(get_balance(l[u])==1) R(u);else L(l[u]),R(u);}}else{insert(r[u],val);if(get_balance(u)==-2){if(get_balance(r[u])==-1) L(u);else R(r[u]),L(u);}}update(u);} int q[N]; int maxx=0; void bfs(int u) {int hh=0,tt=-1;q[++tt]=u;int id=0;while(hh<=tt){int t=q[hh++];id++;if(l[t]!=-1) q[++tt]=l[t],maxx=max(id*2,maxx);if(r[t]!=-1) q[++tt]=r[t],maxx=max(id*2+1,maxx);} } int main() {cin>>n;memset(l, -1, sizeof l);memset(r, -1, sizeof r);memset(w,0x3f,sizeof w);int root=-1;for(int i=1;i<=n;i++){int val;scanf("%d",&val);insert(root,val);}bfs(root);for(int i=0;i<n-1;i++){printf("%d ",w[q[i]]);}printf("%d\n",w[q[n-1]]);//cout<<idx<<" "<<maxx<<endl;if(maxx>idx){printf("NO");}else{printf("YES");}return 0; }

在大量查找的情況下，平衡二叉樹的效率更高，也是首要選擇。在大量增刪的情況下，紅黑樹是首選。

數(shù)據(jù)結(jié)構(gòu)中有一類平衡的二叉搜索樹，稱為紅黑樹。

它具有以下 5 個屬性：

• 節(jié)點是紅色或黑色。
• 根節(jié)點是黑色。
• 所有葉子都是黑色。（葉子是 NULL節(jié)點）
• 每個紅色節(jié)點的兩個子節(jié)點都是黑色。
• 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。

鄰接矩陣與鄰接表優(yōu)缺點：
鄰接矩陣的優(yōu)點是可以快速判斷兩個頂點之間是否存在邊，可以快速添加邊或者刪除邊。而其缺點是如果頂點之間的邊比較少，會比較浪費空間。因為是一個 n?n 的矩陣。

而鄰接表的優(yōu)點是節(jié)省空間，只存儲實際存在的邊。其缺點是關(guān)注頂點的度時，就可能需要遍歷一個鏈表。還有一個缺點是，對于無向圖，如果需要刪除一條邊，就需要在兩個鏈表上查找并刪除。

擴展
逆鄰接表
在鄰接表中對于有向圖有一個很大的缺陷，如果我們比較關(guān)心頂點入度那么就需要遍歷所有鏈表。為了避免這種情況出現(xiàn)，我們可以采用逆鄰接表來存儲，它存儲的鏈表是別的頂點指向它。這樣就可以快速求得頂點的入度。
鄰接表：反映的是頂點出度的情況。
逆鄰接表：反映的是頂點的入度情況。

十字鏈表的好處就是因為把鄰接表和逆鄰接表整合在一起，這樣既容易找到vi為尾的弧，也容易打到以vi為頭的弧，因而容易求得頂點的出度和入度。而且它除了結(jié)構(gòu)復(fù)雜一點燃上，其實創(chuàng)建圖的算法的時間復(fù)雜度與鄰接表相同，因此，在有向圖的應(yīng)用中，十字鏈表是非常好的數(shù)據(jù)結(jié)構(gòu)模型。

圖論

最短路

最短路算法分為兩大類：
m：邊數(shù)，n:點數(shù)

• 單源最短路，常用算法有：
• dijkstra，邊權(quán)為正。在稠密圖上的時間復(fù)雜度是 O($n^2$)，稀疏圖上的時間復(fù)雜度是 O(mlogn)。
  算法思想：
  證明集合S里面的點已經(jīng)是最短距離。假設(shè)集合S點為x，dist[x]有兩個選擇：dist[x]，dist[u]+d[u][s],因為d[u][s]>0且dist[u]>dist[x]。
• bellman - ford算法，不論邊權(quán)是正的是負。算法平均時間復(fù)雜度是 O(nm)
  for n次
  for 所有邊 a,b,w (松弛操作)
  dist[b] = min(dist[b],back[a] + w)
• spfa，不論邊權(quán)是正的是負。算法平均時間復(fù)雜度是 O(km)，k 是常數(shù)。 強烈推薦該算法。
• 多源最短路，一般用floyd算法。代碼很短，三重循環(huán)，時間復(fù)雜度是 O($n^3$)。

代碼：

樸素dijkstra算法 —— 模板題 AcWing 849. Dijkstra求最短路 I

int g[N][N]; // 存儲每條邊 int dist[N]; // 存儲1號點到每個點的最短距離 bool st[N]; // 存儲每個點的最短路是否已經(jīng)確定// 求1號點到n號點的最短路，如果不存在則返回-1 int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < n - 1; i ++ ){int t = -1; // 在還未確定最短路的點中，尋找距離最小的點for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;// 用t更新其他點的距離for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);st[t] = true;}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n]; }

堆優(yōu)化版dijkstra —— 模板題 AcWing 850. Dijkstra求最短路 II

typedef pair<int, int> PII;int n; // 點的數(shù)量 int h[N], w[N], e[N], ne[N], idx; // 鄰接表存儲所有邊 int dist[N]; // 存儲所有點到1號點的距離 bool st[N]; // 存儲每個點的最短距離是否已確定// 求1號點到n號點的最短距離，如果不存在，則返回-1 int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1}); // first存儲距離，second存儲節(jié)點編號while (heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j});}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n]; }

Bellman-Ford算法 —— 模板題 AcWing 853. 有邊數(shù)限制的最短路

注意在模板題中需要對下面的模板稍作修改，加上備份數(shù)組，詳情見模板題。int n, m; // n表示點數(shù)，m表示邊數(shù) int dist[N]; // dist[x]存儲1到x的最短路距離struct Edge // 邊，a表示出點，b表示入點，w表示邊的權(quán)重 {int a, b, w; }edges[M];// 求1到n的最短路距離，如果無法從1走到n，則返回-1。 int bellman_ford() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;// 如果第n次迭代仍然會松弛三角不等式，就說明存在一條長度是n+1的最短路徑，由抽屜原理，路徑中至少存在兩個相同的點，說明圖中存在負權(quán)回路。for (int i = 0; i < n; i ++ ){for (int j = 0; j < m; j ++ ){int a = edges[j].a, b = edges[j].b, w = edges[j].w;if (dist[b] > dist[a] + w)dist[b] = dist[a] + w;}}if (dist[n] > 0x3f3f3f3f / 2) return -1;return dist[n]; }

spfa 算法（隊列優(yōu)化的Bellman-Ford算法） —— 模板題 AcWing 851. spfa求最短路
時間復(fù)雜度 平均情況下 O(m)O(m)，最壞情況下 O(nm)O(nm), nn 表示點數(shù)，mm 表示邊數(shù)

int n; // 總點數(shù) int h[N], w[N], e[N], ne[N], idx; // 鄰接表存儲所有邊 int dist[N]; // 存儲每個點到1號點的最短距離 bool st[N]; // 存儲每個點是否在隊列中// 求1號點到n號點的最短路距離，如果從1號點無法走到n號點則返回-1 int spfa() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true;while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j]) // 如果隊列中已存在j，則不需要將j重復(fù)插入{q.push(j);st[j] = true;}}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n]; }

spfa判斷圖中是否存在負環(huán) —— 模板題 AcWing 852. spfa判斷負環(huán)
時間復(fù)雜度是 O(nm), n 表示點數(shù)，m 表示邊數(shù)

int n; // 總點數(shù) int h[N], w[N], e[N], ne[N], idx; // 鄰接表存儲所有邊 int dist[N], cnt[N]; // dist[x]存儲1號點到x的最短距離，cnt[x]存儲1到x的最短路中經(jīng)過的點數(shù) bool st[N]; // 存儲每個點是否在隊列中// 如果存在負環(huán)，則返回true，否則返回false。 bool spfa() {// 不需要初始化dist數(shù)組// 原理：如果某條最短路徑上有n個點（除了自己），那么加上自己之后一共有n+1個點，由抽屜原理一定有兩個點相同，所以存在環(huán)。queue<int> q;for (int i = 1; i <= n; i ++ ){q.push(i);st[i] = true;}while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true; // 如果從1號點到x的最短路中包含至少n個點（不包括自己），則說明存在環(huán)if (!st[j]){q.push(j);st[j] = true;}}}}return false; }

floyd算法 —— 模板題 AcWing 854. Floyd求最短路

初始化：for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) d[i][j] = 0;else d[i][j] = INF;// 算法結(jié)束后，d[a][b]表示a到b的最短距離 void floyd() {for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }

什么圖一定包含歐拉回路?
B 樹和紅黑樹的區(qū)別是什么?
歐拉回路和哈密爾頓回路有啥區(qū)別
都是平衡的。 然后B+樹的高度是log_m的。 一個結(jié)點保存更多元素 因此對磁盤操作友好

操作系統(tǒng)：解釋操作系統(tǒng)的文件、鏈接，什么是抖動？
l 交流環(huán)節(jié)
數(shù)據(jù)結(jié)構(gòu)：決策樹相關(guān)知識問的非常多，因為涉及到現(xiàn)在廣泛應(yīng)用的機器學(xué)習(xí)基礎(chǔ)算法
項目交流：
項目整體介紹
l 項目創(chuàng)新點、項目來源、項目的效益
l 項目負責(zé)部分，采用了什么技術(shù)實現(xiàn)的，所寫代碼量，與現(xiàn)有類似系統(tǒng)相比的有什么優(yōu)勢
l 然后老師會就你負責(zé)的部分深入問，比如你說采用了技術(shù)老師反問現(xiàn)在用**比較多為什么不用，一系列的問題問道啞口無言未知
論文交流：
（1）論文第幾作者；
（2）論文中負責(zé)哪幾部分；
（3）論文發(fā)表的期刊的性質(zhì)（中文核心、SCI、EI、國家級、省級等）；
（4）有沒有通訊作者（指導(dǎo)老師），若有老師給予你們什么幫助；
（5）論文發(fā)表的意義或者說為什么要發(fā)表這篇論文；
軟著交流：此部分涉及的比較少，一般問在軟著中第幾位、軟著的代碼量、申請軟著中你擔(dān)任了什么角色此部分一般和項目交流結(jié)合。

操作系統(tǒng)

線程和進程的區(qū)別

進程是資源分配最小單位，線程是程序執(zhí)行的最小單位。

進程有自己獨立的地址空間，每啟動一個進程，系統(tǒng)都會為其分配地址空間，建立數(shù)據(jù)表來維護代碼段、堆棧段和數(shù)據(jù)段，線程沒有獨立的地址空間，它使用相同的地址空間共享數(shù)據(jù)；

資源擁有：進程之間的資源是獨立的；同一進程內(nèi)的線程共享本進程的資源。

線程之間通信更方便，同一個進程下，線程共享全局變量，靜態(tài)變量等數(shù)據(jù)，進程之間的通信需要以通信的方式（IPC）進行；（但多線程程序處理好同步與互斥是個難點）

進程的通信方式

共享存儲

消息傳遞
直接通信方式
間接通信方式（郵箱通信方式）

管道通信
管道連接讀進程和寫進程實現(xiàn)他們通信的共享文件。（是共享存儲的優(yōu)化與發(fā)展，存儲空間到緩沖區(qū)，可以實現(xiàn)一邊讀一遍寫）

I/O系統(tǒng)的層次結(jié)構(gòu)

1.用戶層I/O軟件

實現(xiàn)與用戶的交互，用戶可以直接調(diào)用此層提供的接口、函數(shù)等；

2.設(shè)備獨立性軟件

用于實現(xiàn)用戶程序和設(shè)備驅(qū)動器的統(tǒng)一接口、設(shè)備命名、設(shè)備保護以及設(shè)備分配和釋放等，同時為數(shù)據(jù)的傳輸提供必要的空間

3.設(shè)備驅(qū)動程序

與硬件直接相關(guān)，用于具體實現(xiàn)系統(tǒng)施加給硬件設(shè)備的指令

4.中斷處理程序

保護被中斷的CPU環(huán)境，轉(zhuǎn)入中斷處理程序，處理，返回恢復(fù)現(xiàn)場

虛擬存儲器的定義和特征

基于局部性原理，在程序裝入時，可以將程序的一部分裝入內(nèi)存，而將其余部分留在外存，就可以啟動程序執(zhí)行。在程序執(zhí)行過程中，當所訪問的信息不在內(nèi)存時，由操作系統(tǒng)將所需要的部分調(diào)入內(nèi)存,然后繼續(xù)執(zhí)行程序。另一方面，操作系統(tǒng)將內(nèi)存中暫時不使用的內(nèi)容換出到外存上，從而騰出空間存放將要調(diào)入內(nèi)存的信息。這樣，系統(tǒng)好像為用戶提供了一個比實際內(nèi)存 大得多的存儲器，稱為虛擬存儲器。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-LaqC7Ybw-1626070952001)(C:%5CUsers%5Cpxlsdz%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20201229182347967.png)]

為什么說分段系統(tǒng)較之分頁系統(tǒng)更易于實現(xiàn)信息共享和保護？
A.對于分頁系統(tǒng)，每個頁面是分散存儲的，為了實現(xiàn)信息共享和保護，則頁面之間需要一一對應(yīng)起來，為此需要建立大量的頁表項；

B.而對于分段系統(tǒng)，每個段都從0開始編址，并采用一段連續(xù)的地址空間，這樣在實現(xiàn)共享和保護時，只需為所要共享和保護的程序設(shè)置一個段表項，將其中的基址與內(nèi)存地址一一對應(yīng)起來即可.

其他

在數(shù)據(jù)中查找異常值的方法

簡單統(tǒng)計,或者簡單使用散點圖也能很清晰的觀察到異常值的存在,排序

3?原則
這個原則有個條件：數(shù)據(jù)需要服從正態(tài)分布。在3?原則下，異常值如超過3倍標準差，那么可以將其視為異常值。

箱型圖
四分位距(IQR)就是上四分位與下四分位的差值。而我們通過IQR的1.5倍為標準，規(guī)定：超過**（上四分位+1.5倍IQR距離，或者下四分位-1.5倍IQR距離）**的點為異常值。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-qLKtVeic-1626070952002)(C:%5CUsers%5Cpxlsdz%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20201229182357739.png)]

LSTM
由于在誤差反向傳播時，算出來的梯度會隨著往前傳播而發(fā)生指數(shù)級的衰減或放大！而且這是在數(shù)學(xué)上板上釘釘?shù)氖虑椤Ｒ虼?#xff0c;**RNN****的記憶單元是短時的。
計一個全新的、可以解決梯度爆炸消失問題從而記住長距離依賴關(guān)系的神經(jīng)網(wǎng)絡(luò)。

input gate 決定了對輸入的數(shù)據(jù)做哪些處理，forget gate 決定了哪些知識被過濾掉，無需再繼續(xù)傳遞，而 output gate 決定了哪些知識需要傳遞到下一個時間序列。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-EcdWlPEF-1626070952003)(%E4%B8%93%E4%B8%9A%E9%97%AE%E9%A2%98_md_files/image_20200717140940.png?v=1&type=image&token=V1:xFVbt772xm4VIXnq0ZIOVRXoGy9X5rCXjU4CUYqmlGc)]

二項分布的前提是什么

回歸分析的應(yīng)用場景

數(shù)據(jù)庫數(shù)據(jù)模型的組成
1.數(shù)據(jù)模型通常由數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)的完整性約束條件三部分組成。

2.數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)描述數(shù)據(jù)庫的組成對象以及對象之間的聯(lián)系。

3.數(shù)據(jù)操作：數(shù)據(jù)操作是指對數(shù)據(jù)庫中各種對象（型）的實例（值）允許執(zhí)行的操作的集合，包括操作及有關(guān)的操作規(guī)則。（增刪改查）

4.完整性約束條件：數(shù)據(jù)的完整性約束條件是一組完整性規(guī)則

操作系統(tǒng)原理課程里面有很多數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，部分歸納總結(jié)如下：

鏈表

• 進程管理-PCB的連接
• 外存分配方式-鏈接分配

隊列

• 進程通信-消息隊列的實現(xiàn)
• 處理機調(diào)度-任務(wù)就緒列隊的實現(xiàn)
• 存儲器管理-Clock置換算法的實現(xiàn)（循環(huán)隊列）

棧

• 存儲器管理-LRU(Least Recently used)置換算法

樹

• 進程管理-進程家族關(guān)系描述：進程樹

散列表

• 內(nèi)存管理-連續(xù)分配方式：Hash算法
• 文件管理-hash文件

計算機的啟動過程？

開機上電–>系統(tǒng)自檢（POST）–>運行主引導(dǎo)記錄–>裝載操作系統(tǒng)–>運行操作系統(tǒng)–>進入桌面

• 開機上電和系統(tǒng)自檢與硬件設(shè)備有關(guān)
• 運行主引導(dǎo)記錄，裝載操作系統(tǒng)和運行操作系統(tǒng)與操作系統(tǒng)有關(guān)
• 進入桌面與應(yīng)用軟件有關(guān)

一、先驗概率

1.1 定義

直觀理解，所謂“先”，就是在事情之前，即在事情發(fā)生之前事情發(fā)生的概率。是根據(jù)以往經(jīng)驗和分析得到的概率。

1.2 例子

比如拋硬幣，我們都認為正面朝上的概率是0.5，這就是一種先驗概率，在拋硬幣前，我們只有常識。這個時候事情還沒發(fā)生，我們進行概率判斷。所謂的先驗概率是對事情發(fā)生可能性猜測的數(shù)學(xué)表示。

二、后驗概率

1.1 定義

事情已經(jīng)發(fā)生了，事情發(fā)生可能有很多原因，判斷事情發(fā)生時由哪個原因引起的概率。

貝葉斯定理
概率是基于基于已有經(jīng)驗（背景信息）的更新
貝葉斯公式所討論的事：我們的假設(shè)在現(xiàn)有證據(jù)下成立的概率
先驗概率：在目前信息獲得前/沒有任何信息情況下（僅有背景信息），假設(shè)的成立概率
似然概率：假設(shè)成立的情況下，看到證據(jù)的概率（假設(shè)成立的空間<樣本總數(shù)*先驗概率>中，包含證據(jù)的比例）
后驗概率：分子–我們看見的信息 | 分母–所有的信息

多態(tài)
不同對象對消息做出的不同的表現(xiàn)

相位（虛部）、頻率（實部）
傅里葉變化就是去摘，根據(jù)標準正交基的含義。

首先讓做中文自我介紹，我叫….

問題一:你知道數(shù)據(jù)庫查詢可以怎么優(yōu)化嗎？select底層的東西是什么啊？mysql是怎么優(yōu)化這個的？

問題二：python中不用第三個變量怎么進行交換兩個變量的值

問題三：lucence的檢索方式有幾種？分別介紹一下

你搭建過zookeeper集群，你知道這種集群為什么都要用奇數(shù)臺機器嗎？你都用集群做了什么事情？

問題五：你說一下反射的原理嗎，是怎么實現(xiàn)的？
spring 核心：IOC（控制反轉(zhuǎn)：依賴注入）和AOP（面向切面編程），IOC中最基本的技術(shù)就是“反射(Reflection)”編程，通俗來講就是根據(jù)給出的類名來動態(tài)地生成對象。這種編程方式可以讓對象在生成時才決定到底是哪一種對象。

問題六：項目+畢業(yè)設(shè)計

問題七：為什么想要做這個項目，你都用到了哪些技術(shù)？

問題八：linux問題：在一個文件夾下面怎么使用命令找含有某字段的文件

問題九：Python中對哪些庫比較熟悉啊？

問題十：學(xué)碩？專碩？

問題十一：你想做什么方向？如果這個方向名額不夠了，你愿意接收調(diào)劑嗎？

編譯型：先將源代碼編譯成目標語言之后通過連接程序連接到生成的目標程序進行執(zhí)行，例如C++。

解釋型：由解釋器根據(jù)輸入的數(shù)據(jù)當場執(zhí)行而不生成任何的目標程序，例如python。

混合型：兩種語言的特征都存在，典型的就是Java。

c和c++，java的區(qū)別?

c是純過程，c++是對象加過程，java是純面向?qū)ο蟮?br /> java的特點？
一次編譯到處運行，沒有指針，完全對象化。

后面就是專業(yè)面試：首先一個老師根據(jù)我的簡歷上的java web項目，問了我一下接口和抽象類的作用。然后又問了我TCP和UDP的區(qū)別；別的老師又問了我數(shù)據(jù)庫的ACID屬性；數(shù)學(xué)中距離的概念等等。

一、原子性（atomicity)

一個事務(wù)要么全部提交成功，要么全部失敗回滾，不能只執(zhí)行其中的一部分操作，這就是事務(wù)的原子性

二、一致性（consistency)

事務(wù)的執(zhí)行不能破壞數(shù)據(jù)庫數(shù)據(jù)的完整性和一致性，一個事務(wù)在執(zhí)行之前和執(zhí)行之后，數(shù)據(jù)庫都必須處于一致性狀態(tài)。

如果數(shù)據(jù)庫系統(tǒng)在運行過程中發(fā)生故障，有些事務(wù)尚未完成就被迫中斷，這些未完成的事務(wù)對數(shù)據(jù)庫所作的修改有一部分已寫入物理數(shù)據(jù)庫，這是數(shù)據(jù)庫就處于一種不正確的狀態(tài)，也就是不一致的狀態(tài)

三、隔離性（isolation）

事務(wù)的隔離性是指在并發(fā)環(huán)境中，并發(fā)的事務(wù)時相互隔離的，一個事務(wù)的執(zhí)行不能不被其他事務(wù)干擾。不同的事務(wù)并發(fā)操作相同的數(shù)據(jù)時，每個事務(wù)都有各自完成的數(shù)據(jù)空間，即一個事務(wù)內(nèi)部的操作及使用的數(shù)據(jù)對其他并發(fā)事務(wù)時隔離的，并發(fā)執(zhí)行的各個事務(wù)之間不能相互干擾。

四、持久性（durability）

一旦事務(wù)提交，那么它對數(shù)據(jù)庫中的對應(yīng)數(shù)據(jù)的狀態(tài)的變更就會永久保存到數(shù)據(jù)庫中。–即使發(fā)生系統(tǒng)崩潰或機器宕機等故障，只要數(shù)據(jù)庫能夠重新啟動，那么一定能夠?qū)⑵浠謴?fù)到事務(wù)成功結(jié)束的狀態(tài)

歐氏距離
曼哈頓距離
切比雪夫距離
閔可夫斯基距離(Minkowski Distance)
馬氏距離(Mahalanobis Distance)
夾角余弦(Cosine)

皮爾遜系數(shù)的定義：

兩個變量之間的皮爾遜相關(guān)系數(shù)定義為兩個變量之間的協(xié)方差和標準差的商：

比如簡述虛擬地址的轉(zhuǎn)換吶、靜態(tài)變量有什么特征吶、如何在64位的操作系統(tǒng)中聲明一個64位的int（long long）吶等等
頁號+頁內(nèi)偏移，TLB或頁表取出物理塊號

（1）它占據(jù)一個永久性的存儲單元。隨著文件的存在而存在。
（2）靜態(tài)局部變量是在編譯時賦初值，在程序執(zhí)行期間，一旦存儲單元中 的值改變，就不會再執(zhí)行賦初值的語句。未賦初值的變量其值為0。

• **編譯型語言 用專用的編譯器，針對特定的操作系統(tǒng)，將高級語言一次性翻譯成機器可執(zhí)行的二進制機器碼，如C語言、C++
• 解釋型語言 用專門的解釋器對源程序解釋成特定平臺的機器碼并立即執(zhí)行，效率低，不能脫離解釋器運行，跨平臺容易，如Python（同時也是腳本語言）與Ruby等
• 腳本語言 程序代碼即是最終的執(zhí)行文件，過程需要解釋器，如JavaScript,Python，shell等**

總結(jié)

以上是生活随笔為你收集整理的复试-专业问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。