2020年Java常見算法筆試題

2020年Java常見算法筆試題

長(zhǎng)沙中公優(yōu)就業(yè)      2022-05-04 02:49:01     99

2020年Java常見算法筆試題,最小生成樹算法  連通圖:在無(wú)向圖G中,若從頂點(diǎn)i到頂點(diǎn)j有路徑,則稱頂點(diǎn)i和頂點(diǎn)j是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通,則

課程價(jià)格 請(qǐng)咨詢

上課時(shí)段: 授課校區(qū):

詳細(xì)介紹

      最小生成樹算法

  連通圖:在無(wú)向圖G中,若從頂點(diǎn)i到頂點(diǎn)j有路徑,則稱頂點(diǎn)i和頂點(diǎn)j是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通,則稱G為連通圖。

  生成樹:一個(gè)連通圖的生成樹是該連通圖的一個(gè)極小連通子圖,它含有全部頂點(diǎn),但只有構(gòu)成一個(gè)數(shù)的(n-1)條邊。

  最小生成樹:對(duì)于一個(gè)帶權(quán)連通無(wú)向圖G中的不同生成樹,各樹的邊上的權(quán)值之和最小。構(gòu)造最小生成樹的準(zhǔn)則有三條:

  必須只使用該圖中的邊來(lái)構(gòu)造最小生成樹。

  必須使用且僅使用(n-1)條邊來(lái)連接圖中的n個(gè)頂點(diǎn)。

  不能使用產(chǎn)生回路的邊。

  Prim算法

  假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖,T(U,TE)是G的最小生成樹,其中U是T的頂點(diǎn)集,TE是T的邊集,則由G構(gòu)造從起始頂點(diǎn)v出發(fā)的最小生成樹T的步驟為:

  初始化U={v},以v到其他頂點(diǎn)的所有邊為候選邊(U中所有點(diǎn)到其他頂點(diǎn)的邊)。

  重復(fù)以下步驟(n-1)次,使得其他(n-1)個(gè)頂點(diǎn)被加入到U中。

  從候選邊中挑選權(quán)值最小的邊加入TE,設(shè)該邊在V-U(這里是集合減)中的頂點(diǎn)是k,將k加入U(xiǎn)中。

  考察當(dāng)前V-U中的所有頂點(diǎn)j,修改候選邊,若邊(k,j)的權(quán)值小于原來(lái)和頂點(diǎn)j關(guān)聯(lián)的候選邊,則用(k,j)取代后者作為候選邊。

  Kruskal算法

  假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖,T(U,TE)是G的最小生成樹,其中U是T的頂點(diǎn)集,TE是T的邊集,則由G構(gòu)造從起始頂點(diǎn)v出發(fā)的最小生成樹T的步驟為:

  置U的初始值等于V(即包含G中的全部頂點(diǎn)),TE的初始值為空

  將圖G中的邊按權(quán)值從小到大的順序依次選取,若選取的邊未使生成樹T形成回路,則加入TE,否則放棄,知道TE中包含(n-1)條邊為止。

  Dijkstra——貪心算法

  從一個(gè)頂點(diǎn)到其余頂點(diǎn)的最短路徑

  設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖,把圖中頂點(diǎn)集合V分成兩組,第1組為已求出最短路徑的頂點(diǎn)(用S表示,初始時(shí)S只有一個(gè)源點(diǎn),以后每求得一條最短路徑v,...k,就將k加到集合S中,直到全部頂點(diǎn)都加入S)。第2組為其余未確定最短路徑的頂點(diǎn)集合(用U表示),按最短路徑長(zhǎng)度的遞增次序把第2組的頂點(diǎn)加入S中。

  步驟:

  初始時(shí),S只包含源點(diǎn),即S={v},頂點(diǎn)v到自己的距離為0。U包含除v外的其他頂點(diǎn),v到U中頂點(diǎn)i的距離為邊上的權(quán)。

  從U中選取一個(gè)頂點(diǎn)u,頂點(diǎn)v到u的距離最小,然后把頂點(diǎn)u加入S中。

  以頂點(diǎn)u為新考慮的中間點(diǎn),修改v到U中各個(gè)點(diǎn)的距離。

  重復(fù)以上步驟知道S包含所有頂點(diǎn)。

  ASL

  由于查找算法的主要運(yùn)算是關(guān)鍵字的比較,所以通常把查找過(guò)程中對(duì)關(guān)鍵字的平均比較次數(shù)(平均查找長(zhǎng)度)作為衡量一個(gè)查找算法效率的標(biāo)準(zhǔn)。ASL=∑(n,i=1)Pi*Ci,其中n為元素個(gè)數(shù),Pi是查找第i個(gè)元素的概率,一般為Pi=1/n,Ci是找到第i個(gè)元素所需比較的次數(shù)。

  順序查找

  原理是讓關(guān)鍵字與隊(duì)列中的數(shù)從最后一個(gè)開始逐個(gè)比較,直到找出與給定關(guān)鍵字相同的數(shù)為止,它的缺點(diǎn)是效率低下。時(shí)間復(fù)雜度o(n)。

    以上就是長(zhǎng)沙中公優(yōu)就業(yè)Java培訓(xùn)機(jī)構(gòu)小編介紹的“2020年Java常見算法筆試題”的內(nèi)容,希望對(duì)大家有幫助,如有疑問(wèn),請(qǐng)?jiān)诰€咨詢,有專業(yè)老師隨時(shí)為你服務(wù)。

Java筆試題

培訓(xùn)啦提醒您:交易時(shí)請(qǐng)核實(shí)對(duì)方資質(zhì),對(duì)于過(guò)大宣傳或承諾需謹(jǐn)慎!任何要求預(yù)付定金、匯款等方式均存在風(fēng)險(xiǎn),謹(jǐn)防上當(dāng)。