數(shù)據(jù)結(jié)構(gòu)課件20180814直播數(shù)據(jù)結(jié)構(gòu)綜合題-趙尚

數(shù)據(jù)結(jié)構(gòu)算法綜合題淺析2017年使用408卷的院校：復(fù)旦，上海交大，中科大，浙大，同濟(jì)，華南理工，中山大學(xué)……408分?jǐn)?shù)構(gòu)成:，滿分150：數(shù)據(jù)結(jié)構(gòu)45、計(jì)組45、操作系統(tǒng)35、計(jì)網(wǎng)25自主命題院校：清華、北大、北航、哈工大……計(jì)算機(jī)考研題目中，涉及手寫代碼題的，一般只有數(shù)據(jù)結(jié)構(gòu)算法題和操作系統(tǒng)pv操作部分。語言要求：C/C++C++優(yōu)勢(shì)：

1.C++是C的超集，沿襲了C的語法規(guī)則，增加了面向?qū)ο蠊δ埽ǖ佳幸话阕疃嘤玫浇Y(jié)構(gòu)體，

C/C++都具備）2.在某些表達(dá)上簡(jiǎn)化，比如非格式化輸出時(shí)iostream的用法比stdio.h更方便（但是格式化輸出時(shí)仍然是printf的功能更強(qiáng)大）、定義動(dòng)態(tài)數(shù)組時(shí)new比malloc要簡(jiǎn)潔一些。3.多了引用&，在對(duì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行增刪節(jié)點(diǎn)時(shí)，傳參采用引用寫法可以防止斷鏈。十年408真題數(shù)據(jù)結(jié)構(gòu)部分大題2009201020112012201320142015201620172018算法題單鏈表倒數(shù)第k個(gè)線性表數(shù)組循環(huán)左移線性表求中位數(shù)線性表/排序/二分兩個(gè)鏈表公共結(jié)點(diǎn)線性表求>n/2的主元素線性表二叉樹WPL樹刪除單鏈表中絕對(duì)值重復(fù)結(jié)點(diǎn)線性表|n1-n2|最小,|s1-s2|最大線性表/排序樹轉(zhuǎn)中綴樹數(shù)組中未出現(xiàn)的最小正整數(shù)線性表理論題最短路徑圖線性探測(cè)再散列查找鄰接矩陣關(guān)鍵路徑圖

歸并構(gòu)造哈夫曼樹樹

順序查找平均長(zhǎng)度查找

dijkstra圖

鄰接矩陣n次方的意義圖

正則k叉樹樹

prim最小生成樹圖

最小生成樹圖

線性表算法題：?jiǎn)捂湵韨?cè)重考察基本操作、數(shù)組側(cè)重技巧/優(yōu)化復(fù)雜度代碼題對(duì)線性表（順序表、鏈表）的考察比較多，408十年真題（09-18）有8年是考察線性表的，2年（14、17）考察樹。理由：線性表代碼不太復(fù)雜，便于手寫，算法思想偏基礎(chǔ)。同時(shí)考察時(shí)間復(fù)雜度，從logn到n2都有，可以設(shè)置給分等級(jí)。第一類：線性表基礎(chǔ)操作題，帶有一定的數(shù)學(xué)思想題目難度低，相對(duì)容易拿分，套路固定第二類：技巧題這類題目容易想到的方法，其時(shí)間復(fù)雜度總會(huì)高于最優(yōu)解一個(gè)量級(jí)，技巧性強(qiáng)，套路難尋。第三類：樹涉及樹肯定有樹的遍歷（前中后序），考察重點(diǎn)是能否成功實(shí)現(xiàn)算法，而非優(yōu)化復(fù)雜度。已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data域的值，并返回1；否則，只返回0。要求：1）描述算法的基本設(shè)計(jì)思想。2）描述算法的詳細(xì)實(shí)現(xiàn)步驟。3）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用C、C++或Java語言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。

【2009年計(jì)算機(jī)聯(lián)考真題】算法要求：查找輸出單鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)的data值，并返回1或0分別表示是否查找到?！窘夥ㄒ弧肯缺闅v鏈表，記錄下總的長(zhǎng)度L，再分兩種情況討論：1.如果L>=k，再從頭遍歷第二次，找到長(zhǎng)度為L(zhǎng)-k處的結(jié)點(diǎn)，輸出data值并返回1.2.如果L<k，則直接返回0.

datalink時(shí)間復(fù)雜度O(n)空間復(fù)雜度O(1)

^…listqp相距為k-1【解法二】設(shè)置兩個(gè)距離為k-1的指針p和q，p超前q的結(jié)點(diǎn)數(shù)為k-1，當(dāng)p遍歷到鏈表末尾時(shí)，則q所指向的就是倒數(shù)第k個(gè)結(jié)點(diǎn)。優(yōu)點(diǎn)：只遍歷一次，靈活運(yùn)用兩個(gè)指針的方法。時(shí)間復(fù)雜度O(n)空間復(fù)雜度O(1)

typedef

int

ElemType;

//鏈表數(shù)據(jù)的類型定義typedef

struct

LNode

//鏈表結(jié)點(diǎn)的結(jié)構(gòu)定義{

ElemTypedata;

//結(jié)點(diǎn)數(shù)據(jù)

struct

LNode

*link;

//結(jié)點(diǎn)鏈接指針}LNode,

*LinkList;int

Search_k(LinkList

list,intk){

LNode

*p=list->link,*q=list->link;

//指針p、q指示第一個(gè)結(jié)點(diǎn)

intcount=0;

while(p!=NULL)

//遍歷鏈表直到最后一個(gè)結(jié)點(diǎn)

{

if

(count<k)count++;

//計(jì)數(shù)，若count<k只移動(dòng)p

elseq=q->link;

p=p->link;

//之后讓p、q同步移動(dòng)

}//while

if(count<k)

return

0;

//查找失敗返回0

else

{

//否則打印并返回1

printf(”%d”,q->data);

return

1;

}}技巧題（多以數(shù)組為載體）題目最優(yōu)解的時(shí)間復(fù)雜度往往不超過O(n)，一旦利用到排序（最少nlogn），注定與滿分無緣，但思維難度低節(jié)約時(shí)間，代碼完成質(zhì)量高的情況下，扣分不會(huì)很多（2-3分以內(nèi)）?？紙?chǎng)上第一反應(yīng)想到的方法，其時(shí)間復(fù)雜度總會(huì)高于最優(yōu)解的量級(jí)，技巧性強(qiáng)，套路難尋。void

quick_sort(int

*array,

intleft,

intright){

if(left>=right)

return;

int

i

=left-1,j=right+

1,tmp=0;

while(1)

{

intmid=

(left+right)/2;

while(array[++i]

<array[mid]);

while(array[--j]

>array[mid]);

if(i

>=j)

break;

tmp=array[i];array[i]=array[j];array[j]=tmp;

}

quick_sort(array,left,

i

-

1);

quick_sort(array,j+

1,right);}快速排序模板區(qū)間二分應(yīng)用：給定一個(gè)升序數(shù)組data[n]，求滿足data[i]>x的最小i值。int

findmin(intn){

intlow=0,high=n-1;

while

(low<=high)

{

intmid=low+(high-low)/2;

if

(data[mid]>x)high=mid-1;

elselow=mid+1;

}

returnlow;}二分查找模板題目關(guān)鍵字：有序、中位小小小……X大大大大一個(gè)長(zhǎng)度為L(zhǎng)（L≥1）的升序序列S，處在第L/2個(gè)位置的數(shù)稱為S的中位數(shù)。例如，若序列S1=（11，13，15，17，19），則S1的中位數(shù)是15，兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若S2=（2，4，6，8，20），則S1和S2的中位數(shù)是11?，F(xiàn)在有兩個(gè)等長(zhǎng)升序序列A和B，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，找出兩個(gè)序列A和B的中位數(shù)。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C++或Java語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

【2011年計(jì)算機(jī)聯(lián)考真題】方法一：直接將兩序列合并（S1+S2），低級(jí)排序，時(shí)間復(fù)雜度O(n2)，空間O(n)方法二：直接將兩序列合并（S1+S2），高級(jí)排序，時(shí)間復(fù)雜度O(nlogn)，空間O(n)方法三：有序歸并兩序列，直接找出中位數(shù)。11131517192468202468111315171920方法三關(guān)鍵之處代碼for(i=0,j=0,k=0;i<=end1&&j<=end2;k++){

if(A[i]<=B[j])

//依次比較A、B中的元素

C[k]=A[i++];

//將較小值復(fù)制到C中

elseC[k]=B[j++];}while(i<=end1)C[k++]=A[i++];

//若A未檢測(cè)完，復(fù)制while(j<=end2)C[k++]=B[j++];

//若B未檢測(cè)完，復(fù)制1113151719246820方法四（最優(yōu)法）分別求兩個(gè)升序序列A、B的中位數(shù)，設(shè)為a和b，求序列A、B的中位數(shù)過程如下：1）若a=b，則a或b即為所求中位數(shù)，算法結(jié)束。2）若a<b，則舍棄序列A中較小的一半，同時(shí)舍棄序列B中較大的一半，要求兩次舍棄的長(zhǎng)度相等。3）若a>b，則舍棄序列A中較大的一半，同時(shí)舍棄序列B中較小的一半，要求兩次舍棄的長(zhǎng)度相等。在保留的兩個(gè)升序序列中，重復(fù)過程1）、2）、3），直到兩個(gè)序列中均只含一個(gè)元素時(shí)為止，較小者即為所求的中位數(shù)。s1s2d1d1m1m2int

M_Search(intA[],intB[],intn){

ints1=0,d1=n-1,m1,s2=0,d2=n-1,m2;

while(s1!=d1||s2!=d2)

{m1=(s1+d1)/2;

m2=(s2+d2)/2;

if(A[m1]==B[m2])

returnA[m1];

//滿足條件1）

if(A[m1]<B[m2]){

//滿足條件2）

if((s1+d1)%2==0){

//若元素個(gè)數(shù)為奇數(shù)

s1=m1;

//舍棄A中間點(diǎn)以前的部分且保留中間點(diǎn)

d2=m2;

//舍棄B中間點(diǎn)以后的部分且保留中間點(diǎn)

}

else{

//元素個(gè)數(shù)為偶數(shù)

s1=m1+1;

//舍棄A中間點(diǎn)及中間點(diǎn)以前部分

d2=m2;

//舍棄B中間點(diǎn)以后部分且保留中間點(diǎn)

}

}

else{

//滿足條件3）

if((s2+d2)%2==0){

//若元素個(gè)數(shù)為奇數(shù)

d1=m1;

//舍棄A中間點(diǎn)以后的部分且保留中間點(diǎn)

s2=m2;

//舍棄B中間點(diǎn)以前的部分且保留中間點(diǎn)

}

else{

//元素個(gè)數(shù)為偶數(shù)

d1=m1;

//舍棄A中間點(diǎn)以后部分且保留中間點(diǎn)

s2=m2+1;

//舍棄B中間點(diǎn)及中間點(diǎn)以前部分

}

}

}

returnA[s1]<B[s2]?A[s1]:B[s2];}s1s2d1d1m1m2時(shí)間復(fù)雜度O(logn)空間復(fù)雜度O(1)【騰訊2016校招筆試算法題】春節(jié)期間小明使用微信收到很多個(gè)紅包，非常開心。在查看領(lǐng)取紅包記錄時(shí)發(fā)現(xiàn)，某個(gè)紅包金額出現(xiàn)的次數(shù)超過了紅包總數(shù)的一半。請(qǐng)幫小明找到該紅包金額。寫出具體算法思路和代碼實(shí)現(xiàn)，要求算法盡可能高效。給定一個(gè)紅包的金額數(shù)組gifts及它的大小n，請(qǐng)返回所求紅包的金額。沒找到，返回0。已知一個(gè)整數(shù)序列A=（a0,a1,…,an-1），其中0≤ai＜n（0≤i＜n）。若存在ap1=ap2=…=apm=x且m>n/2(0≤pk＜n，1≤k≤m)，則稱x為A的主元素。例如A=（0,5,5,3,5,7,5,5)，則5為主元素；又如A=（0,5,5,3,5,1,5,7），則A中沒有主元素。假設(shè)A中的n個(gè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出-1。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C++或Java語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

【2013年計(jì)算機(jī)聯(lián)考真題】本題如果采用先排好序再統(tǒng)計(jì)的方法（時(shí)間復(fù)雜度可為O(nlog2n)，推薦用快速排序），只要解答正確，最高可拿11分。即便是寫出O(n2)的排序算法（選擇、插入、冒泡），最高也能拿10分。輸出數(shù)組a[n]中未曾出現(xiàn)的最小正整數(shù)。要求時(shí)間復(fù)雜度盡可能優(yōu)化。

【2018年計(jì)算機(jī)聯(lián)考真題回憶版】1.排序（快速排序最佳），然后就簡(jiǎn)單了。時(shí)間復(fù)雜度O(nlogn)，空間O(1)。即使不能達(dá)到最優(yōu)要求，也只扣2-3分以內(nèi)。推薦算法不熟練的同學(xué)在考場(chǎng)上用自己熟悉的方法最快速度寫出，不要過多浪費(fèi)時(shí)間。2.空間換時(shí)間，new一個(gè)動(dòng)態(tài)數(shù)組flag[n+1]，以a[i]作為新開的數(shù)組下標(biāo)索引。時(shí)間復(fù)雜度O(n)，空間O(n)。int

minnum(int

*a,intn){

int

*flag=new

int[n+1],i;

for

(i=0;i<n+1;i++)flag[i]=0;

for

(i=0;i<n;i++)

if

(a[i]>=1&&a[i]<=n)flag[a[i]]=1;

for

(i=1;i<n+1;i++)

if

(flag[i]==0)

return

i;

returnn+1;}有關(guān)于樹的代碼實(shí)現(xiàn)涉及樹肯定有樹的遍歷（前中后序），考察重點(diǎn)是能否成功實(shí)現(xiàn)算法，而非優(yōu)化復(fù)雜度。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，將給定的表達(dá)式樹（二叉樹）轉(zhuǎn)換為等價(jià)的中綴表達(dá)式（通過括號(hào)反映操作符的計(jì)算次序）并輸出。例如，當(dāng)下列兩棵表達(dá)式樹作為算法的輸入時(shí)：輸出的等價(jià)中綴表達(dá)式分別為(a+b)*(c*(-d))和(a*b)+(-(c-d))。二叉樹結(jié)點(diǎn)定義如下：typedefstructnode{chardata[10]; //存儲(chǔ)操作數(shù)或操作符

structnode*left,*right;}BTree;要求：1）給出算法的基本設(shè)計(jì)思想。2）根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。

【2017年計(jì)算機(jī)聯(lián)考真題】觀察發(fā)現(xiàn)，表達(dá)式樹的中序序列加上一些括號(hào)即為等價(jià)的中綴表達(dá)式。操作數(shù)全部為葉節(jié)點(diǎn)，操作數(shù)本身不加括號(hào)，根節(jié)點(diǎn)操作符所進(jìn)行的運(yùn)算（最外層運(yùn)算）不加括號(hào)。其余所有運(yùn)算都要加括號(hào)。void

BtreeToE(BTree

*root){

BtreeToExp(root,

1);

//根的高度為1}void

BtreeToExp(BTree

*root,

intdeep){

if(root==

NULL)

return;

//空結(jié)點(diǎn)返回

if(root->left==NULL&&root->right==NULL)

//若為葉結(jié)點(diǎn)

printf(“%s”,root->data);

//輸出操作數(shù)，不加括號(hào)

else{

if(deep>1)

printf(“(”);

//若有子表達(dá)式則加1層括號(hào)

BtreeToExp(root->left,deep+1);

printf(“%s”,root->data);

//輸出操作符

BtreeToExp(root->right,deep+1);

if(deep>1)

printf(“)”);

//若有子表達(dá)式則加1層括號(hào)

}}二叉樹的帶權(quán)路徑長(zhǎng)度（WPL）是二叉樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。給定一棵二叉樹T，采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)結(jié)構(gòu)為:

其中葉結(jié)點(diǎn)的weight域保存該結(jié)點(diǎn)的非負(fù)權(quán)值。設(shè)root為指向T的根結(jié)點(diǎn)的指針，請(qǐng)?jiān)O(shè)計(jì)求T的WPL的算法，要求：1）給出算法的基本設(shè)計(jì)思想；2）使用C或C++語言，給出二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義；3）根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。

【2014年計(jì)算機(jī)聯(lián)考真題】前序遍歷leftweightrightintWPL(BiTreeroot){

return

wpl_PreOrder(root,0);}int

wpl_PreOrder(BiTree

root,intdeep){

static

int

wpl=0;

//靜態(tài)變量wpl

if(root->lchild==NULL&&root->rchild==NULL)

//若為葉結(jié)點(diǎn)，累積wpl

wpl+=deep*root->weight;

if(root->lchild!=NULL)

//若左子樹不空，對(duì)左子樹遞歸遍歷

wpl_PreOrder(root->lchild,deep+1);

if(root->rchild!=NULL)

//若右子樹不空，對(duì)右子樹遞歸遍歷

wpl_PreOrder(root->rchild,deep+1);

return

wpl;}假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，設(shè)計(jì)一個(gè)算法，求出根結(jié)點(diǎn)到給定某結(jié)點(diǎn)之間的路徑，要求：（1）給出算法的基本設(shè)計(jì)思想。（2）寫出二叉樹采用的存儲(chǔ)結(jié)構(gòu)代碼。（3）根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。

initialstack;boolAncestors(Node*root,

intx){

if

(!root)

return

false;

if

(root->data==x)

return

true;

if

(Ancestors(root->lChild,x)||Ancestors(root->rChild,x))

{

stack.push(root->data);

return

true;

}

return

false;}動(dòng)態(tài)規(guī)劃、深度優(yōu)先搜索等套路歷年408真題未曾涉及，但在部分院校自主命題中出現(xiàn)過的一些類型。由斐波那契數(shù)列問題引入動(dòng)態(tài)規(guī)劃（dynamicprogramming，dp問題）1,1,2,3,5,8,13……intfib(intn){

if

(n==0||n==1)

return

1;

returnfib(n-1)+fib(n-2);}int

fib_dp(intn){

int

dp[maxn]={-1,-1,-1,...,-1};

if

(n==0||n==1)

return

1;//邊界條件

if

(dp[n]!=-1)

return

dp[n];

dp[n]=fib_dp(n-1)+fib_dp(n-2);

//狀態(tài)轉(zhuǎn)移方程（遞推關(guān)系式）

return

dp[n];}設(shè)有n個(gè)不全為負(fù)的整型元素存儲(chǔ)在一維數(shù)組A[n]中，它包含很多連續(xù)的子數(shù)組，例如數(shù)組A={1，-2，3，10，-4，7，2，-5}，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間上盡可能高效的算法，求出數(shù)組A的子數(shù)組之和的最大值（例如數(shù)組A的最大的子數(shù)組為{3，10，-4，7，2}，因此輸出為該子數(shù)組的和18）。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。和【2018年清華大學(xué)912真題】非常相似：動(dòng)態(tài)規(guī)劃思想算法要求：找出最大和區(qū)間，求sumint

findmax(int

*A){

int

dp[maxn];

dp[0]=A[0];

//邊界條件

for

(int

i=1;i<n;i++)

dp[i]=max(A[i],A[i]+dp[i-1]);

//狀態(tài)轉(zhuǎn)移方程（遞推關(guān)系式）

int

ans=0;

for

(int

i=1;i<n;i++)

if

(dp[i]>dp[ans])

ans=i;

return

dp[ans];}解法：設(shè)置數(shù)組dp[i]表示以A[i]為結(jié)尾的連續(xù)序列最大和。1.此連續(xù)序列若只有A[i]一個(gè)元素，那dp[i]=A[i]2.此連續(xù)序列若不止一個(gè)元素，那dp[i]=A[i]+dp[i-1]以上兩者，比較后取最大值就是dp[i]一些經(jīng)典的動(dòng)態(tài)規(guī)劃問題：1.最長(zhǎng)公共子串2.最長(zhǎng)上升（下降）子序列3.最大連續(xù)子序列和4.數(shù)塔問題5.背包問題（01背包、完全背包）深度優(yōu)先搜索（dfs）void

dfs(){

if(到達(dá)終點(diǎn)狀態(tài))

{

...//根據(jù)題意來添加

return;

}

if(越界或者是不符合法狀態(tài))

return;

for

(循環(huán)查找下一個(gè)位置)

{

if(下一個(gè)位置狀態(tài)合法)

{

....//根據(jù)題意來添加更新狀態(tài);

//如flag[i]=1;k++

dfs();

剪枝;

(還原狀態(tài)，回溯);//如flag[i]=0;k--

}

}}輸出字符數(shù)組ch[]的全排列void

dfs(char*

ch,int

n,intlength)//n是全排列的范圍，從后數(shù){

if

(n==1)

{

cout<<ch<<endl;

return;

}

for

(int

i=length-n;i<length;i++)

{swap(ch[i],ch[length-n]);

dfs(ch,n-1,length);swap(ch[i],ch[length-n]);

}}char

ch[100];dfs(ch,len,len);dp和dfs問題如果作為筆試代碼題，思維難度稍大。因此常作為復(fù)試機(jī)考題目出現(xiàn)。常見的練習(xí)之處有LeetCode、各個(gè)學(xué)校oj上，考驗(yàn)思維，多做這類題可以鍛煉腦力……

void

dfs(){

if(到達(dá)終點(diǎn)狀態(tài))

{

...//根據(jù)題意來添加

return;

}

if(越界或者是不符合法狀態(tài))

return;

for

(循環(huán)查找下一個(gè)位置)

{

if(下一個(gè)位置狀態(tài)合法)

{

....//根據(jù)題意來添加更新狀態(tài);

//如flag[i]=1;k++

dfs();

剪枝;

(還原狀態(tài)，回溯);//如flag[i]=0;k--

}

}}dp問題的關(guān)鍵：1.邊界條件2.狀態(tài)轉(zhuǎn)移方程（遞推關(guān)系式）【關(guān)于理論分析題】多考察圖論、樹。樹和圖如果考手寫代碼題難度過大，所以重點(diǎn)考察對(duì)基本概念的掌握和知識(shí)的理論應(yīng)用，對(duì)樹圖中幾個(gè)經(jīng)典算法的考察屢見不鮮，如樹中的二叉樹、二叉排序樹、哈夫曼樹，圖中的深度搜索、廣度搜索、圖的遍歷、最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑等，都是理論分析題的重點(diǎn)考察范圍。這部分題目相對(duì)容易拿分，只要把樹圖的基礎(chǔ)掌握牢固、對(duì)各種定義和方法多加記憶，輔以題目練習(xí)。使用Prim（普里姆）算法求帶權(quán)連通圖的最?。ù鷥r(jià)）生成樹（MST）。請(qǐng)回答下列問題。1）對(duì)下列圖G，從頂點(diǎn)A開始求G的MST，依次給出按算法選出的邊。2）圖G的MST是唯一的嗎？3）對(duì)任意的帶權(quán)連通圖，滿足什么條件時(shí)，其MST是唯一的？

【2017年計(jì)算機(jī)聯(lián)考真題】1）Prim算法從一個(gè)任意的頂點(diǎn)開始，每一步在連接樹集合S中頂點(diǎn)和其他頂點(diǎn)的邊中，選擇一條使得樹的總權(quán)重增加最小的邊加入集合S。當(dāng)算法終止時(shí)，S就是最小生成樹。①S中頂點(diǎn)為A，候選邊為(A,D)、(A,B)、(A,E)，選擇(A,D)加入S。②S中頂點(diǎn)為A、D，候選邊為(A,B)、(A,E)、(D,E)、(C,D)，選擇(D,E)，加入S。③S中頂點(diǎn)為A、D、E，候選邊為(A,B)、(C,D)、(C,E)，選擇(C,E)加入S。④S中頂點(diǎn)為A、D、E、C，候選邊為(A,B)、(B,C)，選擇(B,C)加入S。2）圖G的MST是唯一的。（2分）第一小題的最小生成樹包括了圖中權(quán)值最小的四條邊，其他邊都比這四條邊大，所以此圖的MST唯一。3）當(dāng)帶權(quán)連通圖所有邊的權(quán)值均不相同時(shí)，其MST是唯一的。此題不要求回答充分必要條件，所以回答一個(gè)限制邊權(quán)值的充分條件即可?！綿ijkstra和prim的算法思想非常接近】Prim是計(jì)算最小生成樹的算法，比如為N個(gè)村莊修路，怎么修花銷最少。Dijkstra是計(jì)算最短路徑的算法，比如從a村莊走到其他任意村莊的距離。Prim是求未訪問集合中的點(diǎn)j到已訪問集合S的最短距離。（點(diǎn)到集合）Dijkstra是求未訪問集合中某點(diǎn)j到起始點(diǎn)i（固定點(diǎn)）的最短距離。（點(diǎn)到點(diǎn)）

已知含有5個(gè)頂點(diǎn)的圖G如下圖所示。請(qǐng)回答下列問題：1）寫出圖G的鄰接矩陣A（行、列下標(biāo)從0開始）。2）求A2，矩陣A2中位于0行3列元素值的含義是什么？3）若已知具有n（n≥2）個(gè)頂點(diǎn)的圖的鄰接矩陣為B，則Bm（2≤m≤n）中非零元素的含義