2022中南大學(xué)網(wǎng)絡(luò)教育課程考試：算法分析與設(shè)計(jì)復(fù)習(xí)試題及答案解

第第頁2022中南大學(xué)網(wǎng)絡(luò)教育課程考試：算法分析與設(shè)計(jì)復(fù)習(xí)試題及答案解2022中南高校網(wǎng)絡(luò)教育課程考試：算法分析與設(shè)計(jì)復(fù)習(xí)試題及答案解析

算法分析與設(shè)計(jì)

一、簡要回答以下問題：

1.算法重要特性是什么？2.算法分析的目的是什么？

3.算法的時(shí)間繁復(fù)性與問題的什么因素相關(guān)？4.算法的漸進(jìn)時(shí)間繁復(fù)性的含義？

5.最壞狀況下的時(shí)間繁復(fù)性和平均時(shí)間繁復(fù)性有什么不同？6.簡述二分檢索〔折半查找〕算法的基本過程。

7.背包問題的目標(biāo)函數(shù)和貪心算法最優(yōu)化量度相同嗎？8.采納回溯法求解的問題，其解如何表示？有什么規(guī)定？9.回溯法的搜尋特點(diǎn)是什么？

10.n皇后問題回溯算法的判別函數(shù)place的基本流程是什么？11.為什么用分治法設(shè)計(jì)的算法一般有遞歸調(diào)用？12.為什么要分析最壞狀況下的算法時(shí)間繁復(fù)性？13.簡述漸進(jìn)時(shí)間繁復(fù)性上界的定義。14.二分檢索算法最多的比較次數(shù)？

15.快速排序算法最壞狀況下需要多少次比較運(yùn)算？16.貪心算法的基本思想？

17.回溯法的解〔*1,*2,*n〕的朦攏束一般指什么？18.闡述歸并排序的分治思路。

19.快速排序的基本思想是什么。

20.什么是徑直遞歸和間接遞歸？清除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？21.什么是哈密頓環(huán)問題？

22.用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)？23.請寫出prim算法的基本思想。

二、繁復(fù)性分析

1、MERGESORT(low，high)iflowhigh；thenmid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；

endif

endMERGESORT

2、procedureS1(P，W，M，*，n)i←1;a←0

whilei≤ndo

ifW(i)Mthenreturnendifa←a+ii←i+1;repeatend

3.procedurePARTITION(m,p)

Integerm,p,i;globalA(m:p-1)v←A(m);i←m

loop

loopi←i+1untilA(i)≥vrepeatloopp←p-1untilA(p)≤vrepeat

ifip

thencallINTERCHANGE(A(i),A(p))elsee*itendifrepeat

A(m)←A(p);A(p)←vEndPARTITION

4.procedureF1(n)

ifn2thenreturn(1)

elsereturn(F2(2,n,1,1))endifendF1

procedureF2(i,n,*,y)ifi≤n

thencallF2(i+1,n,y,*+y)endifreturn(y)endF2

5.procedureMA*(A,n,j)*ma*←A(1);j←1fori←2tondo

ifA(i)*ma*then*ma*←A(i);j←i;endifrepeat

endMA*

6.procedureBINSRCH(A,n,*,j)integerlow,high,mid,j,n;low←1;high←nwhilelow≤highdo

mid←|_(low+high)/2_|

2022中南高校網(wǎng)絡(luò)教育課程考試：算法分析與設(shè)計(jì)復(fù)習(xí)試題及答案解析

算法分析與設(shè)計(jì)

一、簡要回答以下問題：

1.算法重要特性是什么？2.算法分析的目的是什么？

3.算法的時(shí)間繁復(fù)性與問題的什么因素相關(guān)？4.算法的漸進(jìn)時(shí)間繁復(fù)性的含義？

5.最壞狀況下的時(shí)間繁復(fù)性和平均時(shí)間繁復(fù)性有什么不同？6.簡述二分檢索〔折半查找〕算法的基本過程。

7.背包問題的目標(biāo)函數(shù)和貪心算法最優(yōu)化量度相同嗎？8.采納回溯法求解的問題，其解如何表示？有什么規(guī)定？9.回溯法的搜尋特點(diǎn)是什么？

10.n皇后問題回溯算法的判別函數(shù)place的基本流程是什么？11.為什么用分治法設(shè)計(jì)的算法一般有遞歸調(diào)用？12.為什么要分析最壞狀況下的算法時(shí)間繁復(fù)性？13.簡述漸進(jìn)時(shí)間繁復(fù)性上界的定義。14.二分檢索算法最多的比較次數(shù)？

15.快速排序算法最壞狀況下需要多少次比較運(yùn)算？16.貪心算法的基本思想？

17.回溯法的解〔*1,*2,*n〕的朦攏束一般指什么？18.闡述歸并排序的分治思路。

19.快速排序的基本思想是什么。

20.什么是徑直遞歸和間接遞歸？清除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？21.什么是哈密頓環(huán)問題？

22.用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)？23.請寫出prim算法的基本思想。

二、繁復(fù)性分析

1、MERGESORT(low，high)iflowhigh；thenmid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)