南郵「アルゴリズム分析と設計A」2018-2019学年第1学期期末試験の思い出

2019.1.8 13:30-15:20《アルゴリズム分析と設計A》試験
試験が終わったばかりで、問題を思い出します.
まずまとめてみると、難易度はまったく自分が想像していたほどではなく、検査する時間がなく、できないことが多いと思います.主に自分で復習するのがよくない.
一、選択問題

アルゴリズムの5つの特性

動的計画法の特徴

分岐限界法の概念

リュックサックの問題は最大の価値を求めます

クルースカルアルゴリズムは,新しいノードを加えた後,元の生成森林と回路を形成し,その中で生成森林がどのようなデータ構造を用いたかを判断する.(同级生はアルバムを调べると言っていますが???

二、空欄を埋める

で最初に証明されたNP は何ですか?

遡及法の2つの性質.

貪欲法の鍵.

f(n)の下限を求める.

三、簡単な解答

Prim とKruskal の異同点.

リュックサック問題は非啓発アルゴリズムのS 0~S 3を書き出し,解を書き出した.

キーパス:earliest[i]とlatest[i]の繰返し式、表の記入、キーアクティビティの判断、キーアクティビティとキーパスの書き出し.

図論関連問題、最小費用を求め、最終的な設計図を描く.(Prim かKruskal かわからない)

サブセットと数:まず条件を満たすサブセットを書き出し、空間状態ツリーを描き、最後に解ベクトルを書き出します.

四、証明問題
最長共通サブシーケンス問題
Xm={x1,x2,…,xm},Yn={y1,y2,…yn},xm=yn.証明:Zk={z 1,z 2,...,zk}がXmとYnの最長共通サブシーケンスである場合、zk=xm=ynであり、Zk−1はXm−1とYn−1の最長共通サブシーケンスである.
五、プログラムの穴埋め問題

一般的なリュックサックの問題のプログラムは空にします.

最長共通サブシーケンスのプログラムが空になります.