廣東工業(yè)大學(xué)年《計算機(jī)軟件技術(shù)基礎(chǔ)》期末試題及答案

1、一、填空題 （每空1分，共20分，）1在同一問題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時，可以用 和 兩種方法來分析算法的工作量。2. 在一個長度為n的順序存儲的線性表中，向第i個元素（1in+1）位置插入一個新元素時，需要從后向前依次后移 個元素。3. 在一個單向鏈表中，若要在P所指向的結(jié)點(diǎn)之后插入一個新結(jié)點(diǎn)，則需要相應(yīng)修改原鏈表的 個指針域的值。4. 操作系統(tǒng)的功能是進(jìn)行處理機(jī)管理、 管理、 管理、設(shè)備管理和文件管理。5. 在鏈?zhǔn)酱鎯Ψ绞街?，每個結(jié)點(diǎn)由兩部分組成： 和 。6. 二叉樹每一個結(jié)點(diǎn)最多有 棵子樹，非空二叉樹只有 個根結(jié)點(diǎn)。7. 一個進(jìn)程的活動情況至少可以劃分為

2、3種基本狀態(tài)： 、 和 。8. 在關(guān)系模型中，把數(shù)據(jù)看成一個二維表，表中的每一列稱為 ，相當(dāng)于記錄中的一個數(shù)據(jù)項；每一行稱為 ，相當(dāng)于記錄值。9. 軟件定義期包括3個階段： 、 和 。10.系統(tǒng)設(shè)計的質(zhì)量主要反映在模塊的獨(dú)立性上。按照模塊之間耦合程度從強(qiáng)到弱的順序，可以將模塊的耦合分為5級，其中最強(qiáng)的耦合是 ，最弱的耦合是 。二、問答題 （每題8分，共40分）1 如何提高Hash表的查找效率？簡要說明線性Hash表、隨機(jī)Hash表和溢出Hash表的適用對象及其優(yōu)缺點(diǎn)？ 2分時系統(tǒng)與實時系統(tǒng)的主要區(qū)別是什么？3什么是數(shù)據(jù)字典？數(shù)據(jù)字典和數(shù)據(jù)流圖的關(guān)系是什么？數(shù)據(jù)字典包括哪些內(nèi)容？4什么是地址重定

3、位？為什么要對程序進(jìn)行重定位？5關(guān)系模型和格式化模型比較有哪些主要優(yōu)點(diǎn)？ 三、應(yīng)用題 （第1題10分，第2、3題各15分，共40分）將關(guān)鍵字元素序列（09,12,04,16,19,31,20,45,01,11,25,26）依次填入長度為n=12的線性Hash表中，并指出各個關(guān)鍵字元素在填入過程中的沖突次數(shù)。設(shè)Hash碼為i=mod(k*0.618, n)。將表達(dá)式 QUOTE f(a*b+c/d,x/y,s-t,w*v) f(a*(b+c/d),x/y,s-t,w*v)用表達(dá)式樹表示，再分別轉(zhuǎn)化成二叉樹，最后寫出其波蘭表達(dá)式。（15分）用冒泡排序?qū)€性表（81,52,57,22,95,04,8

4、3,96,42,32,48,78,14,87,67）進(jìn)行排序，要求按照步驟給出中間每一步的結(jié)果和最后結(jié)果。（15分）答案頁一、填空題 （每空1分，共20分，）1平均性態(tài)(AverageBehavior)、最壞情況復(fù)雜性(Worst-CaseComplexity)(1)平均性態(tài)(AverageBehavior)所謂平均性態(tài)分析，是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。 設(shè)x是所有可能輸入中的某個特定輸入，P(x)是x出現(xiàn)的概率(即輸入為x的概率)，t(x)是算法在輸入為x時所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為(2)最壞情況復(fù)雜性(Worst-CaseComple

5、xity)所謂最壞情況分析，是指在規(guī)模為n時，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為。顯然，W(n)的計算要比A(n)的計算方便得多。由于w(n)實際上是給出了算法工作量的一個上界，因此，它比A(n)更具有實用價值。2. n-(i-1)在順序表中，結(jié)點(diǎn)的物理順序必須和結(jié)點(diǎn)的邏輯順序保持一致，因此必須將表中位置為n ，n-1，i上的結(jié)點(diǎn)，依次后移到位置n+1，n，i+1上，空出第i個位置，然后在該位置上插入新結(jié)點(diǎn)x。僅當(dāng)插入位置i=n+1時，才無須移動結(jié)點(diǎn)，直接將x插入表的末尾。3. 1個（即p指針指向的結(jié)點(diǎn)的指針域修改指向新結(jié)點(diǎn)。新結(jié)點(diǎn)指針域指向P后的結(jié)點(diǎn)）。4. 存儲管理。 進(jìn)程管理。5.

6、 指針域。 數(shù)據(jù)域。6. 兩（2）。 一（1）。7. 就緒、運(yùn)行、阻塞8. 屬性。一元組。9. 問題定義、可行性研究、需求分析10. 內(nèi)容耦合、數(shù)據(jù)耦合（1）數(shù)據(jù)耦合（2）控制耦合（3）特征耦合（4）公共耦合（5）內(nèi)容耦合；二、問答題 （每題8分，共40分）1（1）簡化Hash函數(shù)，降低函數(shù)運(yùn)行耗時。優(yōu)化Hash函數(shù)，降低映射沖突（二次沖突）。良好沖突解決方案， （2）線性Hash表優(yōu)點(diǎn)是簡單。缺點(diǎn)是a 、“堆聚”現(xiàn)象：填入過程發(fā)生沖突時，首先考慮的是下一項，因此當(dāng)沖突較多時，在線性Hash表中就產(chǎn)生“堆聚”。b、二次沖突：在線性Hash表的填入過程中，處理沖突時會產(chǎn)生二次沖突。c、裝填因子影

7、響查找效率。平均查找次數(shù)為：（2-）/(2-2)。適用小型表。 （3）隨機(jī)Hash表：發(fā)生沖突時，表項序號改變不是采用加1取模的方法，而是用某種偽隨機(jī)數(shù)來改變 優(yōu)點(diǎn)是簡單、且沖突減少。缺點(diǎn)：計算耗時增多、沖突仍較多。適宜中小表。 （4）溢出Hash表：將沖突的元素安排在另外的空間，而不占用Hash表本身的空間，就不會產(chǎn)生沖突。優(yōu)點(diǎn)是簡單、且沖突減少。缺點(diǎn)：需要額外的溢出空間。適宜大型表。 2 分時系統(tǒng)按相等的時間片調(diào)度進(jìn)程輪流運(yùn)行，通用性強(qiáng)，交互性強(qiáng)，及時響應(yīng)性要求一般（通常數(shù)量級為秒）；有調(diào)度程序自動計算進(jìn)程的優(yōu)先級，而非用戶控制優(yōu)先級。不能實時響應(yīng)外部異常事件。適于科學(xué)計算、信息查詢等。實

8、時系統(tǒng)往往是專用的，系統(tǒng)與應(yīng)用很難分離，常常緊密結(jié)合在一起，實時系統(tǒng)并不強(qiáng)調(diào)資源利用率，而更關(guān)心及時響應(yīng)性（通常數(shù)量級為毫秒或微秒）、可靠性等。與分時系統(tǒng)相比，實時系統(tǒng)要求有更高的可靠性和更嚴(yán)格的及時性。限定時間完成監(jiān)控功能和響應(yīng)外部異常。適于：過程控制、數(shù)據(jù)采集、通信、多媒體信息處理等。3 所謂數(shù)據(jù)字典，是數(shù)據(jù)流程圖的基礎(chǔ)上，進(jìn)一步定義和描述所有數(shù)據(jù)的工具，包括對一切動態(tài)數(shù)據(jù)（數(shù)據(jù)流）和靜態(tài)數(shù)據(jù)（數(shù)據(jù)存儲）的數(shù)據(jù)結(jié)構(gòu)和相互關(guān)系的說明，是數(shù)據(jù)分析和數(shù)據(jù)管理的重要工具，是系統(tǒng)設(shè)計階段進(jìn)行數(shù)據(jù)庫（文件）設(shè)計的參考依據(jù)。數(shù)據(jù)字典（Data dictionary）是一種用戶可以訪問的記錄數(shù)據(jù)庫和應(yīng)用程

9、序源數(shù)據(jù)的目錄。數(shù)據(jù)字典的作用是給 HYPERLINK /view/228931.htm t _blank 數(shù)據(jù)流圖上每個成分加以定義和說明。換句話說， HYPERLINK /view/228931.htm t _blank 數(shù)據(jù)流圖上所有的成分的定義和解釋的文字集合就是數(shù)據(jù)字典，數(shù)據(jù)流圖是描述各個子塊之間如何進(jìn)行數(shù)據(jù)傳遞：數(shù)據(jù)字典相當(dāng)于數(shù)據(jù)庫中的對照表。數(shù)據(jù)字典的內(nèi)容主要是對數(shù)據(jù)流程圖中的數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、處理邏輯、數(shù)據(jù)存儲和外部實體等六個方面進(jìn)行具體的定義。數(shù)據(jù)流程圖配以數(shù)據(jù)字典，就可以從圖形和文字兩個方面對系統(tǒng)的邏輯模型進(jìn)行完整的描述4地址重定位就是把程序中相對地址變換為絕對地址

10、。有靜態(tài)重定位和動態(tài)重定位兩種重定位技術(shù)。便于編程、便于多道程序裝入內(nèi)存運(yùn)行、便于模塊化、程序不連續(xù)的存放（段頁式管理）、數(shù)據(jù)和查詢分開。5關(guān)系模型較之格式化模型(網(wǎng)狀模型和層次模型)有以下方面的優(yōu)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)比較簡單、具有很高的數(shù)據(jù)獨(dú)立性、可以直接處理多對多的聯(lián)系、以及有堅實的理論基礎(chǔ)。三、應(yīng)用題 （第1題10分，第2、3題各15分，共40分）將關(guān)鍵字元素序列（09,12,04,16,19,31,20,45,01,11,25,26）依次填入長度為n=12的線性Hash表中，并指出各個關(guān)鍵字元素在填入過程中的沖突次數(shù)。設(shè)Hash碼為i=mod(k*0.618, n)。表項序號123456789101112關(guān)鍵字010425264509111231161920沖突次數(shù)0001021將表達(dá)式 QUOTE f(a*b+c