北語202002考試批次算法與數(shù)據(jù)分析結(jié)課(線上)

1、202002 考試批次 算法與數(shù)據(jù)分析結(jié)課作業(yè)（線上）一、論述題 （ 每題 10 分, 共 4道小題 , 總分值 40分 ）1 . 比較分支限界法與回溯法的異同？ （20 分 ）T： 131 9666 29062 .分治法所能解決的問題一般具有哪些特征。 （20 分）答：分治法所能解決的問題一般具有以下幾個(gè)特征：1） 該問題的規(guī)?？s小到一定的程度就可以容易地解決2） 該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3） 利用該問題分解出的子問題的解可以合并為該問題的解；4） 該問題所分解出的各個(gè)子問題是相互獨(dú)立的， 即子問題之間不包含公共的子子問題。3 .算法的定義（20

2、 分 ）4 .利用迭代算法解決問題，需要做好哪些方面的工作（10 分 ）5 .試闡述快速排序（10 分）6 .試闡述貪婪法（10 分 ）7 .動(dòng)態(tài)規(guī)劃算法的基本步驟（10 分）8 .試述分治法的基本思想。（10 分）9 .回溯法中常見哪兩類典型的解空間樹？分析各自的使用場(chǎng)合及時(shí)間復(fù)雜度？ （10 分 ）10 . 算法具有哪些屬性（10 分 ）11 . 常見的兩種分支限界法的算法框架是什么？ （10 分 ）12 .動(dòng)態(tài)規(guī)劃的基本思想 （10 分）13 .分支限界法設(shè)計(jì)算法有哪些步驟。 （10 分）14 . 解析背包問題 （10 分 ）15 .分治法的基本思想 （10 分 ）16 .算法設(shè)計(jì)的質(zhì)量

3、指標(biāo) （10 分）17 .分治法的基本步驟（10 分 ）18. 簡(jiǎn)述回溯法（10 分 ）19. 寫出回溯法搜索子集樹的算法。（10 分 ）20. 經(jīng)常采用的算法主要有哪些（10 分 ）21. 用計(jì)算機(jī)求解問題的步驟（10 分 ）22. 分支限界法的搜索策略是什么？（10 分 ）23. 分治法與動(dòng)態(tài)規(guī)劃法的異同？（10 分 ）24. 設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法有哪些主要步驟。（10 分 ）25. 回溯法的一般描述（10 分 ）二、算法設(shè)計(jì)題 （ 每題 20 分 , 共 3 道小題 , 總分值 60 分 ）1 .貪心算法求活動(dòng)安排問題。 （60 分 ）2 .排列問題。 （60 分 ）3 .采用遞歸方法找一個(gè)

4、解與找全部解稍有不同，在找一個(gè)解的算法中，遞歸算法要對(duì)當(dāng)前候選解最終是否能成為解要有回答。 當(dāng)它成為最終解時(shí)， 遞歸函數(shù)就不再遞歸試探， 立即返回；若不能成為解，就得繼續(xù)試探。設(shè)函數(shù) queen_one（）返回1表示找到解，返回0表示當(dāng)前候選解不能成為解。（60 分）4 .最大子段和 : 動(dòng)態(tài)規(guī)劃算法。 （20 分）5 .一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個(gè)序列X和Y,找出二者的最長(zhǎng)公共子序列。最大子段和：動(dòng)態(tài)規(guī)劃算法。（20分）6 .最大團(tuán)問題 （20 分）7 .背包問題的貪心算法。 （20 分）8 .背包問題的程序解析（20 分）9 .皇后問題的全部解和一個(gè)解

5、（20 分）10 . 裝載問題最優(yōu)解（20 分）11 . 一個(gè)飼養(yǎng)場(chǎng)引進(jìn)一只剛出生的新品種兔子，這種兔子從出生的下一個(gè)月開始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去， 問到第 12 個(gè)月時(shí)， 該飼養(yǎng)場(chǎng)共有兔子多少只？ （20 分 ）12 .回溯法解迷宮問題：迷宮用二維數(shù)組存儲(chǔ)，用H表示墻，O表示通道。（20分）13 .標(biāo)準(zhǔn)的數(shù)獨(dú)游是在一個(gè)9 X 9的棋盤上填寫1 - 9這9個(gè)數(shù)字，規(guī)則是這樣的：棋盤分成上圖所示的 9 個(gè)區(qū)域 （不同顏色做背景標(biāo)出， 每個(gè)區(qū)域是3 X 3 的子棋盤） ， 在每個(gè)子棋盤中填充 1 - 9且不允許重復(fù)，下面簡(jiǎn)稱塊重復(fù)每一行不許有重復(fù)值，每一列

6、不許有重復(fù)值（20 分）14 . 假設(shè)要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)算法進(jìn)行安排。 （20 分）15 .N 皇后回溯法。 （20 分）16 .給定已按升序排好序的 n個(gè)元素a0:n-1,現(xiàn)要在這n個(gè)元素中找出一特定元素 x,返回 其在數(shù)組中的位置，如果未找到返回 -1 。寫出二分搜索的算法，并分析其時(shí)間復(fù)雜度。 （20分）17 . 統(tǒng)計(jì)數(shù)字問題： 一本書的頁碼從自然數(shù) 1 開始順序編碼直到自然數(shù) n 。 書的頁碼按照通常的習(xí)慣編排，每個(gè)頁碼都不含多余的前導(dǎo)數(shù)字0。例如，第6 頁用數(shù)字 6 表示，而不是06或006等。數(shù)字計(jì)數(shù)問題要求對(duì)Z定書的總頁碼 n（1n

7、109）,計(jì)算出書的全部頁碼中分別用到多少次數(shù)字0, 1, 2,，9。輸入數(shù)據(jù)、輸出結(jié)果示例（60分）18 . 假設(shè)某國家發(fā)行了 n 種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m 張郵票。連續(xù)郵箱問題要求對(duì)于給定的 n 和 m ，給出郵票面值的最佳設(shè)計(jì)，在1 張信封上貼出從郵資 1 開始，增量為 1 的最大連續(xù)郵資區(qū)間。例如當(dāng) n=5， m=4 時(shí)，面值為 1 ， 3， 11， 15，32 的 5 種郵票可以貼出郵資的最大連續(xù)區(qū)間是1 到 70。 （20 分 ）19 .有7對(duì)數(shù)字：兩個(gè)1,兩個(gè)2,兩個(gè)3,兩個(gè)7,把它們排成一行。要求，兩個(gè) 1間有1 個(gè)其它數(shù)數(shù)，兩個(gè)2 間有 2 個(gè)其它數(shù)

8、數(shù)，以此類推，兩個(gè)7 之間有 7 個(gè)其它數(shù)數(shù)。如下就是一個(gè)符合要求的排列：17126425374635 當(dāng)然，如果把它倒過來，也是符合要求的。請(qǐng)你找出另一種符合要求的排列法， 并且這個(gè)排列法是以 74 開頭的。 注意： 只填寫這個(gè)14 位的整數(shù)，不能填寫任何多余的內(nèi)容（20 分）20 . 標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃的基本框架（20 分）21 .求出在一個(gè)nxn的棋盤上，放置n個(gè)不能互相捕捉的國際象棋皇后”的所有布局（20分）22 .有7對(duì)數(shù)字：兩個(gè)1,兩個(gè)2,兩個(gè)3,兩個(gè)7,把它們排成一行。要求，兩個(gè)1間有1個(gè)其它數(shù)數(shù)， 兩個(gè) 2 間有 2 個(gè)其它數(shù)數(shù)， 以此類推， 兩個(gè) 7 之間有 7 個(gè)其它數(shù)數(shù)。 如下

9、就是一個(gè)符合要求的排列： 17126425374635 當(dāng)然，如果把它倒過來，也是符合要求的。 請(qǐng)你找出另一種符合要求的排列法，并且這個(gè)排列法是以 74 開頭的。 注意：只填寫這個(gè)14 位的整數(shù)，不能填寫任何多余的內(nèi)容（20 分）23. 利用分治算法寫出合并排序的算法，并分析其時(shí)間復(fù)雜度。（20 分）24. 編寫計(jì)算斐波那契（Fibonacci ）數(shù)列的第n 項(xiàng)函數(shù) fib （ n） （20 分 ）25. 假設(shè)某國家發(fā)行了 n 種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m 張郵票。連續(xù)郵箱問題要求對(duì)于給定的 n 和 m ，給出郵票面值的最佳設(shè)計(jì)，在1 張信封上貼出從郵資 1 開始，增量為 1 的最大連續(xù)郵資區(qū)間。 例如當(dāng) n=5， m=4 時(shí)，面值為 1 ， 3， 11， 15，32 的 5 種郵