2009試卷A(研)評(píng)分標(biāo)準(zhǔn)44709

1、北京航空航天大學(xué)研究生課程試卷 A20092010 學(xué)年 第一學(xué)期期末試卷學(xué)號(hào) 姓名 成績(jī) 考試日期：2009年12月 23 日考試科目： 軟件技術(shù)基礎(chǔ) （A卷）注意事項(xiàng)：1、考試時(shí)間120分鐘題目：一、論述問(wèn)題（本題共 40 分）1、在一個(gè)算法中，時(shí)間與空間往往構(gòu)成一對(duì)矛盾體，論述并舉例說(shuō)明解決時(shí)間的有效方法。（本小題15分）(10分)論述解決時(shí)間的有效方法。答題點(diǎn)包括：1) (3分)增加存儲(chǔ)空間是解決問(wèn)題的一種方法2) (7分)有效的算法是解決問(wèn)題的有效方法3)舉(5分)例任何例子，能反映算法有效性都可以。2、論述并舉例說(shuō)明軟件工程中的測(cè)試與調(diào)試之間的相同點(diǎn)與不同點(diǎn)？（本小題10分）答題要

2、點(diǎn)及分?jǐn)?shù)：1)軟件調(diào)試是編碼過(guò)程中校正代碼的過(guò)程2)軟件測(cè)試是軟件工程中一個(gè)評(píng)價(jià)軟件的過(guò)程3) (4分)相同點(diǎn)在于試圖考證程序的正確與否4) (6分，只要答對(duì)兩點(diǎn)就給6分)不同點(diǎn)在于組織方式，實(shí)施方法以及結(jié)果處理等幾個(gè)方面組織方式：調(diào)試工作由程序員完成，測(cè)試需要獨(dú)立的小組實(shí)施方法：調(diào)試基于代碼級(jí)，測(cè)試可以是白盒子也可以是黑盒子結(jié)果處理：調(diào)試中發(fā)現(xiàn)的錯(cuò)誤要改正，測(cè)試中只記錄測(cè)試結(jié)果3、闡述圖與二叉樹(shù)的相同點(diǎn)和不同點(diǎn)，在此基礎(chǔ)上，闡述二叉樹(shù)的前序遍歷算法與圖的深度優(yōu)先遍歷算法的相同點(diǎn)和不同點(diǎn)？（本小題15分）1)（3分）圖與二叉樹(shù)都是非線性結(jié)構(gòu)2)（4分）圖與二叉樹(shù)之間的不同點(diǎn)是：二叉樹(shù)中不同點(diǎn)的

3、后繼集合不相交，而圖則不然3)（4分）遍歷算法中的相同點(diǎn)：訪問(wèn)當(dāng)前結(jié)點(diǎn)，然后訪問(wèn)該結(jié)點(diǎn)的后繼結(jié)點(diǎn)（鄰結(jié)點(diǎn)）4)（4分）遍歷算法中的不同點(diǎn)：對(duì)于圖的訪問(wèn)，訪問(wèn)結(jié)點(diǎn)時(shí)需要記錄已訪問(wèn)標(biāo)志，訪問(wèn)結(jié)點(diǎn)的鄰結(jié)點(diǎn)時(shí)需要判斷是否已訪問(wèn)；對(duì)于二叉樹(shù)而言，訪問(wèn)鄰結(jié)點(diǎn)時(shí)，不需要記錄與判斷。二、假設(shè)在數(shù)組AN中存貯N個(gè)整數(shù)，設(shè)計(jì)算法change(int *A, int *B, int N),其中N為數(shù)組A中元素的個(gè)數(shù)，該算法將數(shù)組A中整數(shù)移動(dòng)到數(shù)組B中，使得數(shù)組B中的元素呈現(xiàn)小、大、小、大間隔的形式，即B0B2, B2B4,而且相鄰兩元素值之間的差的絕對(duì)值隨下標(biāo)值的增加呈現(xiàn)不增加趨勢(shì)，例如|B0-B1|B1-B2|B

4、2-B3| （本題20分）算法的核心是對(duì)數(shù)組A實(shí)現(xiàn)從小到大的排序，然后從A數(shù)組的左右兩端分別取數(shù)據(jù)，順序放入B數(shù)組。分?jǐn)?shù)安排如下：1)( 10分)排序算法:任何排序算法都得分。如果沒(méi)有給出排序算法，只說(shuō)明要排序，得5分2) (10分)移動(dòng)數(shù)據(jù)到B ：任意的移動(dòng)，只要結(jié)果正確便得分。三、假設(shè)每個(gè)人的信息僅包括姓名，年令和性別，在某信息管理系統(tǒng)中，經(jīng)常需要查找同令人的姓名，設(shè)計(jì)物理存貯結(jié)構(gòu)，使得查找過(guò)程方便快速，并給出相應(yīng)的查找給定年令的算法，分析該算法的性能。（本題 20 分）存儲(chǔ)結(jié)構(gòu)的核心是：以年令age為關(guān)鍵字的hash散列，散列函數(shù)是age-1；沖突的解決方法是鏈表。分?jǐn)?shù)安排如下：1)存貯結(jié)構(gòu)(5分)：畫(huà)圖，類(lèi)C描述，文字描述都可以2) 查找算法(10分):函數(shù)原型描述(即假設(shè)的已知條件)，算法描述（包括根據(jù)年令訪問(wèn)數(shù)組，單向鏈表的訪問(wèn)）3)算法分析(5分):結(jié)出平均比較次數(shù)的概念四、假定二叉樹(shù)存貯對(duì)象是整數(shù)，修改二叉樹(shù)非遞歸前序遍歷算法，使其能求得二叉樹(shù)中最大元