第6章程序設(shè)計(jì)與算法分析(答案)

第6章程序設(shè)計(jì)與算法分析習(xí)題(答案)1.A 2.D 3.A 4.C 5.D6.B 7.B 8.D 9.ABCD 10.D11.C 12.A 13.B 14.D 15.A二、簡答題1．簡述程序的概念。答：一個(gè)程序就是能夠?qū)崿F(xiàn)特定功能的一組指令序列的集合?；蛘弑硎緸椋撼绦颍剿惴ǎ珨?shù)據(jù)結(jié)構(gòu)。2．結(jié)構(gòu)化程序設(shè)計(jì)的思想是什么？答：結(jié)構(gòu)化程序設(shè)計(jì)的基本思想就是采用自上而下、逐步求精的設(shè)計(jì)方法和單入口單出口的控制結(jié)構(gòu)。3．結(jié)構(gòu)化程序設(shè)計(jì)的原則是什么？答：結(jié)構(gòu)化程序設(shè)計(jì)的原則是：(1)使用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)表示程序邏輯。(2)程序語句組織成容易識別的語句模塊，每個(gè)模塊都是單入口、單出口。(3)嚴(yán)格控制GOTO語句的使用。4．結(jié)構(gòu)化程序設(shè)計(jì)語言采用自頂向下的方法進(jìn)行程序設(shè)計(jì)的特點(diǎn)是什么？答：利用結(jié)構(gòu)化程序設(shè)計(jì)語言采用自上而下的方法進(jìn)行程序設(shè)計(jì)的特點(diǎn)是：(1)問題分解成子問題的結(jié)構(gòu)必須與3種基本程序結(jié)構(gòu)之一相對應(yīng)。(2)問題的劃分決定了程序的結(jié)構(gòu)。一方面，子問題的劃分決定了這一層次的程序是3種基本結(jié)構(gòu)中的哪一種結(jié)構(gòu)；另一方面，一個(gè)問題該如何劃分成子問題是靈活的，并不是只有一種分解方法。分解的好壞就決定了設(shè)計(jì)的質(zhì)量，也決定了程序的不同結(jié)構(gòu)。(3)問題的邊界應(yīng)該清晰明確。只有這樣才能精確地解決這些子問題，否則就會模棱兩可，無從下手。5．簡述面向?qū)ο蠛徒Y(jié)構(gòu)化程序設(shè)計(jì)的區(qū)別。答：面向?qū)ο笫菑谋举|(zhì)上區(qū)別于傳統(tǒng)的結(jié)構(gòu)化方法的一種新方法、新思路。它吸收了結(jié)構(gòu)化程序設(shè)計(jì)的全部優(yōu)點(diǎn)，同時(shí)又考慮到現(xiàn)實(shí)世界與計(jì)算機(jī)之間的關(guān)系，認(rèn)為現(xiàn)實(shí)世界是由一系列彼此相關(guān)并且能夠相互通信的實(shí)體組成，這些實(shí)體就是面向?qū)ο蠓椒ㄖ械膶ο?，每個(gè)對象都有自己的自然屬性和行為特征，而一類相似對象的共性的抽象描述，就是面向?qū)ο蠓椒ㄖ械暮诵摹悺?．答：數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素之間的相互關(guān)系的集合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的物理結(jié)構(gòu)主要有四種，分別是順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)及散列結(jié)構(gòu)。(1)順序結(jié)構(gòu)：是把所有元素存放在一片連續(xù)的存儲單元中，邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。(2)鏈表結(jié)構(gòu)：對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針域來表示，由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。(3)索引結(jié)構(gòu)：每個(gè)數(shù)據(jù)結(jié)構(gòu)建立索引表，每個(gè)數(shù)據(jù)元素占用表中的一項(xiàng)，每個(gè)表項(xiàng)通常包含關(guān)鍵字和地址指針。其中的關(guān)鍵字是能夠惟一標(biāo)志一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。(4)散列結(jié)構(gòu)：通過構(gòu)造相應(yīng)的散列函數(shù)，由散列函數(shù)的值來確定元素存放的地址。算法(Algorithm)是一組明確的、可以執(zhí)行的步驟的有序集合，它在有限的時(shí)間內(nèi)終止并產(chǎn)生結(jié)果。算法的特性有：(1)有窮性(可終止性)：一個(gè)算法必須在有限個(gè)操作步驟內(nèi)以及合理的有限時(shí)間內(nèi)執(zhí)行完成。(2)確定性：算法中的每一個(gè)操作步驟都必須有明確的含義，不允許存在二義性。(3)有效性(可執(zhí)行性)：算法中描述的操作步驟都是可執(zhí)行的，并能最終得到確定的結(jié)果。(4)輸入及輸出：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入數(shù)據(jù)、有1個(gè)或多個(gè)輸出數(shù)據(jù)。時(shí)間復(fù)雜度是與求解問題規(guī)模、算法輸入相關(guān)的函數(shù)，該函數(shù)表示算法運(yùn)行所花費(fèi)的時(shí)間。記為：T(n)，其中，n代表求解問題的規(guī)模。complexity)度量算法的空間復(fù)雜性、即執(zhí)行算法的程序在計(jì)算機(jī)中運(yùn)行所占用空間的大小。簡單講，空間復(fù)雜度也是與求解問題規(guī)模、算法輸入相關(guān)的函數(shù)。記為：S(n)，其中，n代表求解問題的規(guī)模。同樣，引入符號“O”來表示T(n)、S(n)與求解問題規(guī)模n之間的數(shù)量級關(guān)系。9．用圖示法表示語言處理的過程。答：語言處理的過程如圖所示：10．簡述編譯程序的概念。編譯程序是把高級語言程序(源程序)作為一個(gè)整體來處理，在應(yīng)用源程序執(zhí)行之前，就將程序源代碼“翻譯”成目標(biāo)代碼(機(jī)器語言)，編譯后與系統(tǒng)提供的代碼庫鏈接，形成—個(gè)完整的可執(zhí)行的機(jī)器語言程序(目標(biāo)程序代碼)。11．用圖示法表示編譯程序的框架。答：編譯程序的框架如圖所示：12．詞法分析的任務(wù)是什么？答：作為編譯過程的第一個(gè)階段，其任務(wù)是從左到右一個(gè)字符，一個(gè)字符地對源程序進(jìn)行掃描，讀入源程序，對構(gòu)成源程序的字符流進(jìn)行掃描和分解，通過詞法分析從而識別出一個(gè)個(gè)單詞(也稱單詞符號或符號)。13．語法分析的任務(wù)是什么？答：語法分析是編譯過程的第二個(gè)階段，任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語，如“程序”、“語句”、“表達(dá)式”等等。14．簡述語義處理的功能。答：編譯過程中的語義處理實(shí)現(xiàn)兩個(gè)功能：(1)審查每個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法結(jié)構(gòu)合法的程序是否真正有意義，有時(shí)把這個(gè)工作稱為靜態(tài)語義分析或靜態(tài)審查。(2)如果靜態(tài)語義正確，則語義處理要執(zhí)行真正的翻譯，要么生成程序的一種中間表示形式(中間代碼)，要么生成實(shí)際的目標(biāo)代碼。15．簡述中間代碼的概念。答：所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)，這種記號系統(tǒng)可以設(shè)計(jì)為多種多樣的形式，重要的設(shè)計(jì)原則為兩點(diǎn)：一是容易生成；二是容易將它翻譯成目標(biāo)代碼。16．目標(biāo)代碼生成階段的任務(wù)是什么？答：目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機(jī)器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后援寄存器的調(diào)度等。三、討論題1．作為一個(gè)計(jì)算機(jī)專業(yè)的學(xué)生，程序設(shè)計(jì)是大學(xué)學(xué)習(xí)的重要內(nèi)容之一，程序設(shè)計(jì)的內(nèi)容很多，語言的