文章目錄

• • 樹
  • 排序

樹

葉子節(jié)點數(shù)=度為2的節(jié)點數(shù)+1
總?cè)~子節(jié)點數(shù)=葉子節(jié)點數(shù)+度為1的節(jié)點數(shù)+度為2的節(jié)點數(shù)

排序

栗子：

一組記錄的排序碼為（46，79，56，38，40，84），一趟排序的結(jié)果為（40，38，46，56，79，84），則采用的是（）排序算法。

• A選項起泡算法：相鄰元素兩兩比較，一個元素大于右側(cè)相鄰元素交換位置，否則位置不變。 一趟排序為：46，56，38，40，79，84

• B選項直接插入：每一步將一個待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。
  一趟排序為：38，40，46，79，56，84

找到一個最小的放最前面，其他不變

• C選項快速：挑選一個基準元素，大于基準元素的放在其右邊，小于基準元素的放在其左邊，從而拆分為兩部分，以此類推直到不可拆分為止。
  以源數(shù)據(jù)第一個元素46為基準，采用雙邊循環(huán)法設置left和right兩個指針指向數(shù)組最左和最右兩端，從右指針開始，如果大于或等于基準元素則指針向左移動，如果小于基準元素則停止。轉(zhuǎn)向left指針向右移動如果小于或等于基準元素則繼續(xù)向右移動，如果大于基準元素則停止。交換兩指針元素后，右指針繼續(xù)上述操作比較，直到最后把基準元素和兩指針重復元素交換位置。第一趟排序結(jié)束得出如下排序，所以C正確。
  一趟排序為：40，38，46，56，79，84
• D選項2-路歸并：將一個數(shù)組分成兩個數(shù)組，分別對兩個數(shù)組進行排序，循環(huán)第一步，直到劃分出來的“小數(shù)組”只包含一個元素，只有一個元素的數(shù)組默認為已經(jīng)排好序
  一趟排序為：46，56，79合并；38，40，84合并
  栗子：
  
  p^.llink 表示 p 的前驅(qū)結(jié)點，p^.rlink表示 p 的后繼結(jié)點。刪除 p 所指結(jié)點時須將 p 的前驅(qū)結(jié)點的rlink指向 p 的后繼結(jié)點，將 p 的后繼結(jié)點的 llink 指向 p 的前驅(qū)結(jié)點。

總結(jié)

以上是生活随笔為你收集整理的数据结构+算法——错题总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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