計算機(jī)科學(xué)與技術(shù)試卷
第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程
第二部分專業(yè)知識課程
Ⅰ.計算機(jī)系統(tǒng)結(jié)構(gòu)
Ⅱ.計算機(jī)網(wǎng)絡(luò)
Ⅲ.軟件工程
Ⅳ.人工智能原理
Ⅴ.計算機(jī)圖形學(xué)
考生須知
1. 本試卷滿分為100 分，包括數(shù)學(xué)基礎(chǔ)課程和專業(yè)知識課程兩部分。數(shù)學(xué)基礎(chǔ)課程滿分40
分，每位考生必答；專業(yè)知識課程包括五門課程，每門課程滿分30 分，考生須從中任選
2 門作答，多選者只按前選課程計分。
2. 請考生務(wù)必將本人準(zhǔn)考證號最后兩位數(shù)字填寫在本頁右上角方框內(nèi)。
3. 考生一律用藍(lán)色或黑色墨水筆在答題紙指定位置上按規(guī)定要求作答，未做在指定位置上
的答案一律無效。
4. 監(jiān)考員收卷時，考生須配合監(jiān)考員驗收，并請監(jiān)考員在準(zhǔn)考證上簽字（作為考生交卷的
憑據(jù)）。否則，若發(fā)生答卷遺失，責(zé)任由考生自負(fù)。
計算機(jī)科學(xué)與技術(shù)試卷第1 頁共10 頁
第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程
（共40 分）
一、用邏輯符號形式化下列語句（本大題共2 小題，每小題2 分，共4 分）
1．每個人的指紋都不相同。
2．自然數(shù)不是奇數(shù)就是偶數(shù)，且奇數(shù)不能被2 整除。
二、填空題（本大題共4 小題，第1 小題每空1 分，第2、3、4 小題每空2 分，共10 分）
1．設(shè)A、B 均為有窮集合，A 和B 的基數(shù)分別是m 和n（m >0, n >0）。
（1）當(dāng)m 和n 滿足時，存在從A 到B 的雙射函數(shù)。
此時共可生成個不同的雙射函數(shù)。
（2）當(dāng)m 和n 滿足時，存在從A 到B 的單射函數(shù)。
此時共可生成個不同的單射函數(shù)。
2．已知5 位老師和3 位學(xué)生圍圓桌就座，如果要求學(xué)生兩兩不相鄰，則有種就座方
案。
3．整除2310 的正奇數(shù)有個。
4．設(shè)圖的頂點集合為V G ，邊集合為。則G
的生成樹有
G 1 2 3 4
( ) { , , , } v v v v =} 1 2 2 3 3 4 4 1 1 3
( ) { , , , , E G v v v v v v v v v v =
棵。
三、解答題（本大題共3 小題，第1、2 小題每題4 分，第3 小題8 分，共16 分）
1．設(shè)P↓Q = ?(P∨Q)，僅用聯(lián)結(jié)詞↓分別表示出?P，P∧Q，P∨Q。
2．設(shè)T
是一棵有13 個頂點的樹，稱樹中度為1 的頂點為葉子。如果T
的頂點的度只可能是
1,2,5 且T
恰好有3 個度為2 的頂點，那么，T
中有多少個葉子？
3．求1,4,5,8,9 這五個數(shù)字組成的位數(shù)的個數(shù)，要求4,8 出現(xiàn)的次數(shù)均為偶數(shù)，而1,5,9 出現(xiàn)
的次數(shù)不加限制。
n
四、證明題（本大題共2 小題，第1 小題4 分，第2 小題6 分，共10 分）
1．設(shè)R 是非空集合A 上的二元關(guān)系，R 滿足條件：
（1）R 是自反的；
（2）若<a，b>∈R ∧<a，c>∈R，則<b，c>∈R；
試證明R 是A 上的等價關(guān)系。
2．隨意地把一個9
棋盤的每個方格涂成紅色或藍(lán)色，求證：必有兩行方格的涂色是一樣的。
3 ′
計算機(jī)科學(xué)與技術(shù)試卷第2 頁共10 頁
第二部分專業(yè)知識課程
Ⅰ．計算機(jī)系統(tǒng)結(jié)構(gòu)
（共30 分）
一、填空題（本大題共2 小題，每小題2 分，共4 分）
1．用下面三條指令可以完成向量表達(dá)式D=A×(B+C)的運算。假設(shè)向量長度N<64 位，且向量
B 和C 已經(jīng)存于V0 和V1，讀寫操作各需要時間1 拍。
V3←A (6 拍)
V2←V0+V1 (6 拍)
V4←V2×V3 (7 拍)
若這三條指令串行執(zhí)行則需要的時間為拍，當(dāng)采用鏈接技術(shù)后所需時
間為拍。
2．有編號為0,1,2,…,31 共32 個處理機(jī)（結(jié)點），采用移數(shù)函數(shù)構(gòu)成互連網(wǎng)，則網(wǎng)絡(luò)直徑
為，結(jié)點度為。
二、問答題（本大題共3 小題，每小題2 分，共6 分）
一臺計算機(jī)以字為單位訪問存儲器。其主存共包含4096 個存儲塊，每個存儲塊大小為128
個字。采用組相聯(lián)映像方式的Cache 由64 個存儲塊構(gòu)成，每組包含4 個存儲塊。
1．問主存地址需要用多少位表示？
2．問Cache 地址需要用多少位表示？
3．計算主存地址格式中，區(qū)號、組號、塊號和塊內(nèi)地址字段的位數(shù)。
三、設(shè)計題（本大題共5 小題，每小題2 分，共10 分）
一條具有3 個功能段非線性流水線的預(yù)約表如下所示。
1．寫出對應(yīng)的禁止集合和初始沖突向量；
2．畫出流水線調(diào)度的狀態(tài)轉(zhuǎn)移圖；
3．求最小啟動循環(huán)和最小平均啟動距離；
4．畫出流水線各功能段之間的連接圖；
5．通過插入非計算延遲單元（預(yù)留算法），周期
1 2 3 4 5 6
段
可以實現(xiàn)該流水線的最優(yōu)調(diào)度。假設(shè)流
S1 X X X
水線的時鐘周期τ=20ns，流水線最大
S2 X X
可能的吞吐率TP＝？
S3 X
計算機(jī)科學(xué)與技術(shù)試卷第3 頁共10 頁
四、計算題（本大題共4 小題，共10 分）
在一臺每個時鐘周期發(fā)射兩條指令的超標(biāo)量處理機(jī)上運行下面一段程序。所有指令都要
經(jīng)過“取指令”、“譯碼”、“執(zhí)行”和“寫結(jié)果”4 個階段，其中，“取指令”、“譯碼”和“寫
結(jié)果”三個階段各為一個流水段，其延遲時間都為10ns。在“執(zhí)行”階段，LOAD 操作和AND
操作各需要延遲10ns，ADD 操作需要延遲20ns，MUL 操作需要延遲30ns，四種操作部件各
設(shè)置一個。ADD 部件和MUL 部件都采用流水線結(jié)構(gòu)，每一級流水線的延遲時間都為10ns。
程序：
n+1 ：LOAD R0, A ；R0←主存(A)單元
n+2 ：ADD R1, R0 ；R1←（R1）＋（R0）
n+3 ：LOAD R2, B ；R2←主存(B)單元
n+4 ：MUL R3, R4 ；R3←（R3）×（R4）
n+5 ：AND R4, R5 ；R4←（R4）∧（R5）
n+6 ：ADD R2, R5 ；R2←（R2）＋（R5）
1．（4 分）列出這個程序中所有的數(shù)據(jù)相關(guān)，包括先寫后讀數(shù)據(jù)相關(guān)（RAW）、先讀后寫數(shù)據(jù)
相關(guān)（WAR）和先寫后寫數(shù)據(jù)相關(guān)（WAW）；
2．（2 分）如果所有運算型指令都在“譯碼”流水段讀寄存器，在“寫結(jié)果”流水段寫寄存器，
采用順序發(fā)射順序完成調(diào)度方法。畫出流水線的時空圖，并計算執(zhí)行這段程序所用的時間；
3．（2 分）如果所有運算型指令都在“譯碼”流水段讀寄存器，在“寫結(jié)果”流水段寫寄存器，
采用順序發(fā)射亂序完成調(diào)度方法。畫出流水線的時空圖，并計算執(zhí)行這段程序所用的時間；
4．（2 分）如果每個操作部件的輸出端都有直接數(shù)據(jù)通路與輸入端相連，采用順序發(fā)射亂序完
成調(diào)度方法。畫出流水線的時空圖，并計算執(zhí)行這段程序所用的時間。
計算機(jī)科學(xué)與技術(shù)試卷第4 頁共10 頁
Ⅱ．計算機(jī)網(wǎng)絡(luò)
（共30 分）
一、單項選擇題（本大題共10 小題，每小題1 分，共10 分）
1．下面對計算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)中協(xié)議所做的描述，（）是錯誤
．．
的。
A．網(wǎng)絡(luò)協(xié)議的三要素是語法、語義和同步
B．協(xié)議是控制兩個對等層實體之間通信的規(guī)則的集合
C．在OSI 參考模型中，要實現(xiàn)第N 層的協(xié)議，需要使用N＋1 層提供的服務(wù)
D．協(xié)議規(guī)定了對等層實體之間所交換的信息的格式和含義
2．若數(shù)據(jù)鏈路層采用回退N（go-back-N）滑動窗口協(xié)議，發(fā)送幀的序號用7bit 表示，發(fā)送窗
口的最大值為（）。
A．7 B．64
C．127 D．128
3．以太網(wǎng)中采用二進(jìn)制指數(shù)后退算法處理發(fā)送沖突問題，下列數(shù)據(jù)幀中重傳時再次發(fā)生沖突
概率最低的是（）。
A．首次重傳的幀B．發(fā)生兩次沖突的幀
C．發(fā)生三次沖突的幀D．發(fā)生四次沖突的幀
4．采用二層以太網(wǎng)交換機(jī)擴(kuò)展局域網(wǎng)，（）是錯誤
．．
的。
A．二層以太網(wǎng)交換機(jī)的各個端口可以支持不同的速率
B．二層以太網(wǎng)交換機(jī)可以隔離廣播幀
C．二層以太網(wǎng)交換機(jī)需要對收到的數(shù)據(jù)幀進(jìn)行處理，增加了傳輸時延
D．二層以太網(wǎng)交換機(jī)在轉(zhuǎn)發(fā)幀時不改變幀的源地址
5．在采用（）的傳輸方式下，由網(wǎng)絡(luò)負(fù)責(zé)差錯控制和流量控制，分組按順序被交付。
A．電路交換B．報文交換
C．虛電路分組交換D．?dāng)?shù)據(jù)報分組交換
6．對于IP 分組的分段和重組，（）是正確的。
A．IP 分組可以被源主機(jī)分段，并在中間路由器進(jìn)行重組
B．IP 分組可以被路徑中的路由器分段，并在目的主機(jī)進(jìn)行重組
C．IP 分組可以被路徑中的路由器分段，并在中間路由器上進(jìn)行重組
D．IP 分組可以被路徑中的路由器分段，并在最后一跳的路由器進(jìn)行重組
7．假定一臺主機(jī)的IP 地址是180.120.74.56，子網(wǎng)掩碼為255.255.240.0，則該子網(wǎng)地址為
（）。
A．180.120.0.0 B．180.120.64.0
C．180.120.72.0 D．180.120.74.0
計算機(jī)科學(xué)與技術(shù)試卷第5 頁共10 頁
8．在Internet 上，主機(jī)采用（）標(biāo)識，運行在主機(jī)上的應(yīng)用程序用（）標(biāo)識。
A．端口號主機(jī)地址B．主機(jī)地址IP 地址
C．IP 地址主機(jī)地址D．IP 地址端口號
9．當(dāng)客戶端請求域名解析時，如果本地DNS 服務(wù)器不能完成解析，就把請求發(fā)送給其
他服務(wù)器，依次進(jìn)行查詢，直到把域名解析結(jié)果返回給請求的客戶端。這種方式稱為
（）。
A．迭代解析B．遞歸解析
C．迭代與遞歸相結(jié)合的解析D．高速緩存解析
10．在信息安全領(lǐng)域，使用（）方法可以使通信的接收方驗證收到報文是否受到篡改和
偽造。
A．?dāng)?shù)字簽名B．?dāng)?shù)據(jù)加密
C．防火墻D．身份認(rèn)證
二、名詞解釋（本大題共2 小題，每小題3 分，共6 分）
1．自治系統(tǒng)AS（autonomous system）
2．慢啟動（slow start）
三、問答和計算題（本大題共4 小題，共14 分）
1．（3 分）試說明以太網(wǎng)規(guī)定的最短幀長是多少？為什么要限制最短幀長？
2．（3 分）試說明TCP 協(xié)議是如何提供端到端可靠的傳輸服務(wù)的？
3．（4 分）考慮一條帶寬為1.6Mbps 的鏈路，往返傳播時延為45ms，假設(shè)數(shù)據(jù)幀的大小為1KB。
若采用滑動窗口協(xié)議來保證鏈路的利用率，允許發(fā)送方在收到應(yīng)答之前盡量連續(xù)發(fā)送多幀。
那么，至少需要多少位作為序號？（忽略確認(rèn)幀大小和接收處理開銷）
4．（4 分）如下圖所示的網(wǎng)絡(luò)中，采用距離向量路由算法進(jìn)行路由選擇。假設(shè)路由器C 在啟
動時，測得與相鄰路由器A、B 的時延分別為7，14。此后，路由器C 分別收到來自相鄰
路由器發(fā)出的路由向量：B（15，0，4，6），A（0，3，12，16）。上述向量表示發(fā)送該向
量的路由器分別與網(wǎng)絡(luò)中路由器A、B、C、D 之間的時延。計算路由器C 在收到相鄰路
由器發(fā)出的向量后，更新的路由表是什么？
計算機(jī)科學(xué)與技術(shù)試卷第6 頁共10 頁
Ⅲ．軟件工程
（共30 分）
一、單項選擇題（本大題共5 小題，每小題1 分，共5 分）
1．軟件開發(fā)的需求活動，其主要任務(wù)是（）。
A．給出軟件解決方案B．給出系統(tǒng)模塊結(jié)構(gòu)
C．定義模塊算法D．定義需求并建立系統(tǒng)模型
2．軟件總體設(shè)計結(jié)束后得到（）。
A．初始化的軟件結(jié)構(gòu)圖B．優(yōu)化的軟件結(jié)構(gòu)圖
C．模塊的算法D．程序編碼
3．面向?qū)ο蠓治龇椒ㄅc結(jié)構(gòu)化分析方法的區(qū)別之一是（）。
A．一個使用了“抽象”，而另一個沒有使用“抽象”
B．一個以問題域的成分為基點來構(gòu)造一個模塊，而另一個不是
C．一個目標(biāo)明確，而另一個目標(biāo)不明確
D．一個需要考慮數(shù)據(jù)結(jié)構(gòu)，而另一個不需要考慮數(shù)據(jù)結(jié)構(gòu)
4．確定測試的計劃是在（）階段制定的。
A．需求分析B．詳細(xì)設(shè)計
C．編碼D．測試
5．按不同人員的工作內(nèi)容來分類軟件過程，基本過程包括（）。
A．維護(hù)過程和改進(jìn)過程等B．開發(fā)過程和改進(jìn)過程等
C．獲取過程和供應(yīng)過程等D．改進(jìn)過程和裁減過程等
二、判斷題（本大題共5 小題，每小題1 分，共5 分。如果正確，用“√”表示，否則，用
“×”表示）
1．在軟件開發(fā)方法中，結(jié)構(gòu)化方法總的指導(dǎo)原則是自頂向下、逐步求精。（）
2．當(dāng)一個模塊直接修改另一個模塊的數(shù)據(jù)時，模塊間的這種耦合稱為數(shù)據(jù)耦合。（）
3．測試用例只需選用合理的輸入數(shù)據(jù)。（）
4．邊界值分析法是一種白盒測試法。（）
5．關(guān)聯(lián)是建立類之間關(guān)系的一種手段。（）
計算機(jī)科學(xué)與技術(shù)試卷第7 頁共10 頁
三、簡答題（本大題共3 小題，每小題4 分，共12 分）
1．給出模塊耦合的定義，并舉例說明3 種模塊耦合。
2．將下面的偽碼轉(zhuǎn)換成N-S 圖和PAD 圖。
BEGIN
S1;
S2;
IF a>5 THEN S3 ELSE S4;
n=1;
WHILE n<=5 DO
{ S5;
n=n+1; }
IF b>5 THEN S6 ELSE S7;
END.
3．給出CMM 的5 級模型，并以其中一個CMM 等級為例，列出該等級包含的關(guān)鍵過程域。
四、建模題（本大題共3 小題，共8 分）
問題陳述：在一簡化的某學(xué)校圖書管理系統(tǒng)中，
庫房管理員職責(zé)：
根據(jù)各系的要求負(fù)責(zé)購買圖書，并為新書編制圖書卡片（分類目錄號、流水號、書
名、作者、價格、購書日期），寫入圖書目錄文件。
圖書管理員職責(zé)：
根據(jù)借還書的要求負(fù)責(zé)借還圖書處理：
（1）當(dāng)沒有要借的圖書時，向借閱人發(fā)無書通知；
（2）當(dāng)借閱人將圖書丟失時，以圖書丟失單的形式報告圖書管理員，由圖書管理員
下罰款單給借閱人；同時圖書管理員負(fù)責(zé)修改圖書目錄文件，并通知庫房管理員。
圖書館主任職責(zé)：
每月末根據(jù)分類目錄號查看某種圖書庫存量，當(dāng)庫存量低于庫存下限時，通知庫房
管理員購書。
1．（3 分）用結(jié)構(gòu)化分析方法給出該系統(tǒng)的頂層DFD（系統(tǒng)環(huán)境圖）；
2．（2 分）給出頂層DFD 的數(shù)據(jù)字典；
3．（3 分）選擇該圖書管理系統(tǒng)中的一個交互，并用順序圖來描述。
計算機(jī)科學(xué)與技術(shù)試卷第8 頁共10 頁
Ⅳ．人工智能原理
（共30 分）
一、單項選擇題（本大題共4 小題，每小題2 分，共8 分）
1．使用神經(jīng)網(wǎng)絡(luò)來求得分類問題的解，實際常用的手法是通過（）來達(dá)到。
A．增減神經(jīng)網(wǎng)絡(luò)的層數(shù)
B．調(diào)整神經(jīng)網(wǎng)絡(luò)的連接權(quán)值
C．增減輸入節(jié)點
2．本體（Ontology）是一種（）。
A．推理方法
B．產(chǎn)生式系統(tǒng)的另一種形式
C．概念和概念間關(guān)系的表示方法
3．從理論上講沒有當(dāng)今計算機(jī)不能計算求解的問題（）。
A．是
B．不是
C．尚無定論
4．像Baidu（百度），Google（谷歌）這類知識問答系統(tǒng)，所使用的主要技術(shù)是（）。
A．自然語言的語義理解方法
B．知識推理方法
C．簡單的模式匹配方法
二、證明題（7 分）
試用線性歸結(jié)法證明A A →B 1 2
A ùù
3
()()()(
其中)()()()(){}1
A , x C x D x y G x y E y ="ù??$ù
()()()()()()(){}2
A , x C x F x y G x y F y =$ùù"?
()()()()3
A x D x F x ="?ú?
()()()()B x E x F x =?"??
三、問答題（本大題共3 小題，每小題5 分，共15 分）
1．近年來人工智能學(xué)科的研究熱點，主要在哪幾個方面？
2．說明Agent（智能體或主體）概念，以及多Agent 系統(tǒng)的主要研究內(nèi)容。
3．說明一種歸結(jié)方法是完備的含義，并舉出一種不完備的歸結(jié)策略。
計算機(jī)科學(xué)與技術(shù)試卷第9 頁共10 頁
Ⅴ．計算機(jī)圖形學(xué)
（共30 分）
一、判斷題（本大題共5 小題，每小題1 分，共5 分。如果正確，用“√”表示，否則，用
“×”表示）
1．在圖形系統(tǒng)中，圖形處理運算的精度不取決于顯示器的分辯率。（）
2．Bezier曲線形狀取決于所選擇的坐標(biāo)系和特征折線集（多邊形）頂點的相對位置。（）
3．B樣條曲線具有幾何不變性（形狀和位置與坐標(biāo)系的選擇無關(guān)）。（）
4．定義了物體的邊界也就唯一的定義了物體的幾何形狀邊界，物體邊界上的面可以是平面或
任何形狀曲面。（）
5．平行投影能真實地反映物體精確的尺寸和形狀，視覺效果更有真實感。（）
二、填空題（本大題共5 小題，每小題2 分，共10 分）
1．使用二維圖形變換矩陣
ú
ú
ú
?
ù
ê
ê
ê
?
é
=T
1 2 1 0
0 1 0
0 0 2 1
將產(chǎn)生變換的結(jié)果是。
2．種子填充算法也是一種很常用的多邊形區(qū)域填充算法，與邊填充算法不同，其基本原理
是。
3．Z-Buffer消隱算法是一種典型的消隱算法，其缺點是。
4．Phong模型是簡單光反射模型，它模擬物體表面對光的反射作用，主要考慮的是物體表面
對的反射作用。對物體間的光反射作用，只用一個做近似處理。
5．用于減少或消除“走樣”的技術(shù)措施，就被稱為“反走樣”。除了提高分辨率之外，還有
和兩種常用的“反走樣”方法。
三、問答題（本大題共3 小題，每小題5 分，共15 分）
1．在計算機(jī)圖形學(xué)中，通常所謂“物體”的含義是什么？并寫出其準(zhǔn)確的定義。
2．已知三次B樣條曲線上的五個形值點分別為Q 0 (30,0), Q 1 (24,24), Q 2 (0,18), Q 3 (-24,24),
Q 4 (-30,0)控制頂點P 0 , P 1 , P 2 , P 3 , P 4 ，該曲線起點Q 0 與P 0 重合，切于向量P 0 P 1 ，終點Q 4 與
P 4 重合, 切于向量P 3 P 4 ，求控制頂點P 1 , P 2 , P 3 。
3．為生成真實感圖形，可采用一種HLS顏色模型，試分別說明H、L和S所代表的三個要素及
其含義。
計算機(jī)科學(xué)與技術(shù)試卷第10 頁共10 頁
2008 年同等學(xué)力人員申請碩士學(xué)位學(xué)科綜合水平全國統(tǒng)一考試
計算機(jī)科學(xué)與技術(shù)試卷答案及評分參考
第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程
一、形式化下列語句（本大題共2 小題，每小題2 分，共4 分）
1．解：設(shè)M(x)：x
是人；N(x, y)：x ≠y，即x 與y 是不同的人；E(x，y)：x
與y
的指紋相
同。則原句可形式化為以下兩種形式之一：
（1）("x)( "y) (M(x)∧M(y)∧N(x, y)??E(x, y))
（2）("x)( M(x)?("y)(M(y)∧N(x, y)??E(x, y)))
說明：如僅缺少N(x, y)的內(nèi)容，則只給1 分。
2．解：設(shè)P(x)：x
是自然數(shù)，Q(x)：x
是奇數(shù)，R(x)：x
是偶數(shù)，D(x)：x
能被2 整除。
原句可形式化為：
("x)((P(x)?(Q(x)∨R(x))∧(Q(x)??D(x)))
說明：（1）如僅答對部分內(nèi)容最多給1 分。
（2）全句必須寫成一個式子，且中間用聯(lián)結(jié)詞∧聯(lián)結(jié)，否則扣0.5 分。
二、填空題（本大題共4 小題，第1 小題每空1 分，第2、3、4 小題每空2 分，共10 分）
1．（1）m = n m!
（2）m ≤n !
m m
n n
C m A ×=
2．或1440 4! 5 4 3 ×××
3．16
4．8
三、解答題（本大題共3 小題，第1、2 小題每題4 分，第3 小題8 分，共16 分）
1．解：（1）?P ??(P∨P) P↓P -----------1 分?
（2）P∧Q
??(?P∨?Q)
?(?P)↓(?Q)
?(P↓P)↓(Q↓Q)
（見下面說明）
計算機(jī)科學(xué)與技術(shù)試卷答案第1 頁共14 頁
（3）P∨Q
??(?(P∨Q))
??(P↓Q)
?(P↓Q)↓(P↓Q)
（見下面說明）
如（2）、（3）小題中僅做對一題則給2 分，（2）和（3）小題都做對則給3 分。
2．解設(shè)T 中有x 個葉子，則T 中有13 3 10 x x --=-個度為5 的頂點，
由于樹中的邊數(shù)等于頂點個數(shù)減去1，即邊數(shù)為12 -----------2 分
由頂點度數(shù)之和等于邊數(shù)的兩倍得
1 2 3 5 (10 ) 2 1 x x ′+′+′-=′2
解得，故中有8 個葉子。-----------2 分8 x =T
3．解設(shè)滿足條件的位數(shù)的個數(shù)為，則序列對應(yīng)的指數(shù)型母函數(shù)G( i i
a 1 2 3
, , , a a a L ) x 為
2 4 2 3
2
G( )=(1+ + ) (1 )
2! 4! 2! 3!
x x x x
x x +++++L
3
L -----------2 分
由于
2 3
e =1
2! 3!
x x x
x ++++L 故
2 3
e =1
2! 3!
x x x
x
-
-+-+L
于是
2 4
1
1 (
2! 4! 2
)
x x x x
e e
-
+++=+L ---------3 分
故
2 3 1
G( )= ( )
4
x x x
x e e e
-
+=
5 3 1
( 2
4
)
x x x
e e e ++
0
1
(5 2 3 1)
4 !
n
n n
n
x
n
￥
=
=+×+
?---------2 分
故= n
a
1
(5 2 3 1)
4
n n
+×+---------1 分
四、證明題（本大題共2 小題，第1 小題4 分，第2 小題6 分，共10 分）
1．證明：由條件（1），R
已滿足自反性。需證明R
滿足對稱性和傳遞性。
1）對于任意的<a，b>，
<a，b>∈R
且由條件（1）
T<a，b>∈R
∧<a，a>∈R -----------1 分
由條件（2）<b，a>∈R -----------1 分T
所以，R
滿足對稱性。
計算機(jī)科學(xué)與技術(shù)試卷答案第2 頁共14 頁
2）對于任意的<a，b>，<b，c>
<a，b>∈R
∧<b，c>∈R
由對稱性<b，a>∈R
∧<b，c>∈R -----------1 分T
由條件（2）<a，c>∈R -----------1 分T
所以，R
滿足傳遞性。綜合1），2）可得，R
是A
上的等價關(guān)系。
2．證明：用紅、藍(lán)兩色去涂1 棋盤，共有3 ′
3
2 8 =種涂色方法。-----------2 分
設(shè)表示第種涂色方法. 設(shè)是任一個已用紅、藍(lán)涂了色的棋盤，以
表示的第k 行的涂色方法。設(shè)
( 1,2, ,8) i
a i =L
( 1,2, ,9) b k =L
i J 9 3 ′
k
J 1 2 9
{ , , , }, B b b b =L 并令
{ | }, ( 1,2, ,8) j
B b b B b a j =?=j
且與相同L 。則。-----------2 分
8
j=
j
B B B í=
1
且
U
j
B
) B 中9 個元素放到這8 個抽屜里，由鴿籠原理，必有正整數(shù),使
得| | ，即
( 1,2, ,8 j
B j =L (1 8) t t ￡￡
2 t
B 3t
B 中至少有兩個元素不妨設(shè)為，這說明在涂色中，棋盤的第行
和第行的涂色一樣。-----------2 分
m
b b 和l
J m
l
計算機(jī)科學(xué)與技術(shù)試卷答案第3 頁共14 頁
第二部分專業(yè)知識課程
Ⅰ．計算機(jī)系統(tǒng)結(jié)構(gòu)試卷答案及評分參考
一、填空題（本大題共2 小題，每小題2 分，共4 分）
1．3N+22；N+16
2．3；9
二、問答題（本大題共3 小題，每小題2 分，共6 分）
因為主存包含4096=2
12
個塊，Cache中包含64=2
6
個塊，每個塊大小128=2
7
個字，所以：
1．主存字地址為12+7=19 位
2．Cache 字地址為6+7=13 位
3．區(qū)號為19-13=6 位，組號為6-2=4 位，塊號為2 位，塊內(nèi)地址為7 位
區(qū)號組號塊號塊內(nèi)地址
12
6
2
7
（注：只要得數(shù)正確就可以得分）
三、設(shè)計題（本題共5 小題，每小題2 分，共10 分）
1．禁止集合為{2，3，5}，初始沖突向量為（1 0 1 1 0）
2．流水線調(diào)度的狀態(tài)轉(zhuǎn)移圖如下：
簡單循環(huán)平均啟動距離
（1，6）3.5
（4，6）5
（4）4
（6）6
3．流水線的最小啟動循環(huán)為（1，6）；最小平均啟動距離為3.5
計算機(jī)科學(xué)與技術(shù)試卷答案第4 頁共14 頁
4．流水線各功能段之間的連接圖如下：
輸出
輸入
S1 S2 S3
5．插入非計算延遲后，流水線的最佳平均啟動距離為3，所以，最大可能的吞吐率
TP=1/(3*20) ns
四、計算題（本大題共4 小題，共10 分）
1．指令n+1 與n+2 之間有關(guān)于寄存器R0 的寫讀數(shù)據(jù)相關(guān)；-----------1 分
指令n+3 與n+6 之間有關(guān)于寄存器R2 的寫讀數(shù)據(jù)相關(guān)；-----------1 分
指令n+4 與n+5 之間有關(guān)于寄存器R4 的讀寫數(shù)據(jù)相關(guān)；-----------1 分
指令n+3 與n+6 之間有關(guān)于寄存器R2 的寫寫數(shù)據(jù)相關(guān)。-----------1 分
2．采用順序發(fā)射順序完成調(diào)度方法的流水線時空圖：（1 分）
1 2 3 4 5 6 7 8 9 10 11 12 13
n+1 IF1 ID1 LS WR1
n+2 IF2 ID2ADDADDWR2
n+3 IF1 ID1 LS WR1
n+4 IF2 ID2 MUL MUL MUL WR2
n+5 IF1 ID1 AND WR1
n+6 IF2 ID2 ADD ADD WR2
執(zhí)行這個程序共用130ns。-----------1 分
3．采用順序發(fā)射亂序完成調(diào)度方法的流水線時空圖：（1 分）
1 2 3 4 5 6 7 8 9
n+1 IF1 ID1 LS WR1
n+2 IF2 ID2 ADD ADD WR2
n+3 IF1 ID1 LS WR1
n+4 IF2 ID2 MUL MUL MUL WR2
計算機(jī)科學(xué)與技術(shù)試卷答案第5 頁共14 頁
n+5 IF1 ID1 AND WR1
n+6 IF2 ID2 ADD ADD WR2
執(zhí)行這個程序共用90ns -----------1 分
4．采用順序發(fā)射亂序完成調(diào)度方法的流水線時空圖：（1 分）
1 2 3 4 5 6 7
n+1 IF1 ID1 LS WR1
n+2 IF2 ID2 ADD ADD WR2
n+3 IF1 ID1 LS WR1
n+4 IF2 ID2 MUL MUL MUL WR2
n+5 IF1 ID1 AND WR1
n+6 IF2 ID2 ADD ADD WR1
執(zhí)行這個程序共用70ns -----------1 分
IF：取指令ID：譯碼LS：LOAD 訪存WR：寫結(jié)果
ADD：加法MUL：乘法AND：與操作
計算機(jī)科學(xué)與技術(shù)試卷答案第6 頁共14 頁
Ⅱ．計算機(jī)網(wǎng)絡(luò)試卷答案及評分參考
一、單項選擇題（本大題共10 小題，每小題1 分，共10 分）
1．C；2．C；3．D；4．B；5．C；6．B；7．B；8．D；9．B 10．A
二、名詞解釋（本大題共2 小題，每小題3 分，共6 分）
1．答：指具有單一管理權(quán)限（或獨立行政單位管轄下）的網(wǎng)絡(luò)和路由器（2 分）；
采用AS 內(nèi)部網(wǎng)關(guān)協(xié)議（域內(nèi)路由選擇協(xié)議）確定分組在AS 內(nèi)的路由（0.5 分）；采
用外部網(wǎng)關(guān)協(xié)議（域間路由選擇協(xié)議）處理分組在AS 之間的路由（0.5 分）。
2．答：TCP 進(jìn)行擁塞控制的一種方法（1 分）；使擁塞窗口在初始時大小為1（1 個最大報文
段長度），每收到一個ACK 應(yīng)答（對新報文段的確認(rèn)），擁塞窗口增1，逐步增加擁塞
窗口大?。?font face="Times New Roman">2 分）。
三、問答和計算題（本大題共4 小題，共14 分）
1．答：以太網(wǎng)定義最短幀長為64 字節(jié)（1 分）。最短長度的限制與以太網(wǎng)MAC 層的CSMA/CD
．．．．．．．
協(xié)議有關(guān)（1 分）。以太網(wǎng)在發(fā)送數(shù)據(jù)幀時能夠檢測到?jīng)_突并停止發(fā)送。如果幀長度過短，
在檢測到?jīng)_突之前幀已經(jīng)發(fā)送完畢，則協(xié)議無法進(jìn)行有效沖突檢測（1 分）。
2．答：TCP 協(xié)議是面向連接的協(xié)議（1 分）；可靠建立連接（也可答三次握手建立連接）和終
止連接（1 分）；采用滑動窗口協(xié)議進(jìn)行流量控制和差錯控制（1 分）。
3．答：發(fā)送一幀所需時間t1 = 1KB*8/1.6Mbps = 5ms （1 分）
RTT=45ms
若使用滑動窗口協(xié)議，可連續(xù)發(fā)送幀數(shù)：1＋45/5=10 幀（1 分），
2
4
>10>2
3
, 因此，至少使用4 位序號；（2 分）
4．答：收到路由向量：A（0，3，12，16）B（15，0，4，6），
C 更新后的路由表（分別到A,B,C,D 的路由向量）;
(（7，A），（10，A），（0，－），（20，B）)
評分說明：每答對到一個節(jié)點的路由的時延值得0.5 分，答對輸出線路得0.5 分；若答案
為（7，10，0，20）得2 分
計算機(jī)科學(xué)與技術(shù)試卷答案第7 頁共14 頁
Ⅲ．軟件工程試卷答案及評分參考
一、單項選擇題（本大題共5 小題，每小題1 分，共5 分）
1．D；2．B；3．B；4．A；5．C
二、判斷題（本大題共5 小題，每小題1 分，共5 分。如果正確，用“√”表示，否則，用
“×”表示）
1．√2．× 3．× 4．× 5．√
三、簡答題（本大題共3 小題，每小題4 分，共12 分）
1. 答：耦合是對不同模塊之間相互依賴程度的度量。（定義1 分）
一般地，模塊耦合可分為：
1）內(nèi)容耦合：當(dāng)一個模塊直接修改或操作另一個模塊的數(shù)據(jù)時，模塊間的這種耦合
稱為內(nèi)容耦合。
2）公共耦合：當(dāng)兩個以上的模塊共同引用一個全局?jǐn)?shù)據(jù)項時，模塊間的這種耦合稱
為公共耦合。
3）控制耦合：一個模塊在界面上傳遞一個信號控制另一個模塊，接收信號的模塊的
動作根據(jù)信號值進(jìn)行調(diào)整，模塊間的這種耦合稱為控制耦合。
4）標(biāo)記耦合：當(dāng)兩個模塊至少有一個通過界面?zhèn)鬟f的公共參數(shù)時，模塊間的這種耦
合稱為標(biāo)記耦合。
5）數(shù)據(jù)耦合：當(dāng)模塊間通過參數(shù)傳遞基本類型的數(shù)據(jù)時，模塊間的這種耦合稱為數(shù)
據(jù)耦合。
（給出任意3 種模塊耦合，得3 分，其中每種耦合1 分）
2．答：對應(yīng)的N-S 圖如下所示：（2 分）
S2
T a>5 F
S3 S4
n=1
n<=5
S5
n=n+1;
T b>5 F
S6 S7
S1
計算機(jī)科學(xué)與技術(shù)試卷答案第8 頁共14 頁
對應(yīng)的PAD 圖如下所示：（2 分）
b>5
a>5
S1
開始
結(jié)束
WHILE n<=5
S2
S3
S4
S5
S6
n=1
n=n+1
S7
3．答：CMM 的5 級模型如下所示：（2 分）
初始級(1)
可重復(fù)級(2)
已定義級(3)
已管理級(4)
持續(xù)優(yōu)化級(5)
例如：（1）可重復(fù)級的關(guān)鍵過程域包括：軟件配置管理、軟件質(zhì)量保證、軟件子合同管理、
軟件項目跟蹤和監(jiān)督、軟件項目規(guī)劃以及需求管理。
（2）已定義級的關(guān)鍵過程域包括：組織過程焦點、組織過程定義、培訓(xùn)大綱、集成
軟件管理、軟件產(chǎn)品工程、組間協(xié)調(diào)以及同行評審。
（3）已管理級的關(guān)鍵過程域包括：定量過程管理和軟件質(zhì)量管理。
（4）持續(xù)優(yōu)化級的關(guān)鍵過程域包括：缺陷預(yù)防、技術(shù)變化管理和過程變化管理。
（至少答出2 個關(guān)鍵過程域，得2 分）。
計算機(jī)科學(xué)與技術(shù)試卷答案第9 頁共14 頁
四、建模題（本大題共3 小題，共8 分）
答：
（1）系統(tǒng)的頂層DFD 如下：（3 分）
圖書管理系統(tǒng)
頂層DFD
時鐘
庫房管理員
圖書管理員
圖書館主任
借閱人
入庫
告單
丟失報
單
購書通知
時間
月末庫存量
查看要求
借還書的要求
圖書丟失單
無
書
通
知
單
罰款單
購書通知
2）數(shù)據(jù)字典：（2 分）
入庫單＝分類目錄號＋流水號＋書名＋作者＋價格＋購書日期
借還書的要求＝[借書信息|還書信息]
借書信息＝[書名|作者]＋借書日期
還書信息＝書名＋還書日期
借閱人圖書證號
無書通知單＝借閱人圖書證號＋無書信息
罰款單＝借閱人圖書證號＋罰款金額
查看要求＝分類目錄號
月末庫存量＝{分類目錄號＋書名＋庫存量}
購書通知＝分類目錄號＋書名＋購買量
購書”這一交互，給出其
順序圖：（
（
圖書丟失單＝圖書流水號＋
丟失報告單＝書名＋分類目錄號＋圖書流水號
（3）以下針對“圖書圖書館主任根據(jù)
3 分）
月末庫存情況通知庫房管理員
計算機(jī)科學(xué)與技術(shù)試卷答案第10 頁共14 頁
其中，對象“圖書館主任”是界面對象，它調(diào)用對象“圖書庫存信息文件”，根據(jù)圖書的
分類目錄號統(tǒng)計圖書月末庫存情況，當(dāng)圖書的庫存量低于下限時，對象“圖書館主任”
向?qū)ο?font face="Times New Roman">“庫房管理員”發(fā)購書通知。
注：該題的答案在形式上可能是多種多樣的，但在回答時，主要注意三點：
（1）頂層DFD 是否符合系統(tǒng)環(huán)境圖的構(gòu)造特點；
（2）數(shù)據(jù)字典的定義是否符合其書寫原則；
（3）所畫的順序圖是否符合UML 中順序圖的定義。
圖書月末庫存情況(分類目
錄號，書名，庫存量)
統(tǒng)計圖書月末庫存情況(分類
目錄號)
：圖書館主任：圖書庫存信息文件：庫房管理員
When 庫存量
<下限
購書通知(分類目
錄號，書名，購買
量)
計算機(jī)科學(xué)與技術(shù)試卷答案第11 頁共14 頁
Ⅳ．人工智能原理試卷答案及評分參考
一、單項選擇題（每小題2 分，共8 分）
1．B；2．C；3．B；4．C；
二、證明題（7 分）
答：
1 2 3
A A A B ùùù?的子句集為
﹛①()()()(), , C x D x G x f x ?úú②()()()(), C x D x E f x ?úú③()C a ，④()F a ，⑤
()(), y F y ú(G a ?，⑥)()D x F ?x ?ú，⑦()()E x F x ??ú﹜
（占3 分）
一種線性歸結(jié)證明過程（可能有多種）：
（占4 分）
三、問答題（每小題5 分，共15 分）
答：
1．Agent 理論與應(yīng)用，數(shù)據(jù)挖掘，統(tǒng)計機(jī)器學(xué)習(xí)。（答出一個方面占2 分，全答出占5 分）
2．Agent 是某個環(huán)境下的計算機(jī)系統(tǒng)，具有在該環(huán)境下自動行動來實現(xiàn)目標(biāo)的能力（自主性）。
還具有與其他Agent 交互共同完成問題求解的能力（社會性）（占2 分）。
多Agent 系統(tǒng)主要研究Agent 和Agent 群體的模型，以及多Agent 合作求解的機(jī)理（占3 分）。
3．一種歸結(jié)方法是完備的，指的是如果定理成立，使用這種歸結(jié)方法必會給出證明（占3 分）。
如單元歸結(jié)策略就是不完備的（占2 分）。
。⑦②。
。
。⑤
。
①。
。
。
⑥
。
③
。
。
④。
。
計算機(jī)科學(xué)與技術(shù)試卷答案第12 頁共14 頁
Ⅴ．計算機(jī)圖形學(xué)試卷答案及評分參考
一、判斷題（本大題共5 小題，每小題1 分，共5 分。如果正確，用“√”表示，否則，用
“×”表示）
1.√2.× 3.√4.× 5.×
二、填空題（本大題共5 小題，每小題2 分，共10 分）
1．沿X坐標(biāo)軸方向縮小1/2 倍，沿Y坐標(biāo)軸方向移動1/2 個繪圖單位
2．假設(shè)在多邊形區(qū)內(nèi)部有一象素已知，由此出發(fā)找到區(qū)域內(nèi)的所有圖象
3．圖象空間面
需要有較多的存儲空間，即還需要一個存放每個象素的深度值的Z緩沖區(qū)
4．直接光照環(huán)境光常量
5．簡單的區(qū)域取樣加權(quán)的區(qū)域取樣
三、問答題（本大題共3 小題，每小題5 分，共15 分）
1．答：在計算機(jī)圖形學(xué)中，通常所謂“物體”是三維歐氏空間點的正則集合ciS。在此，S 是
三維歐氏空間的一個點集；iS 是點集S 的內(nèi)部，即其中任何一點，在該點的一個充分
小的鄰域所包含的點都屬于此點集；ciS 是點集的閉包，即點集iS（開集）與其所有
變界的并集。
評分說明：指出“三維歐氏空間點的正則集合”得2 分，說明了S點集, S的內(nèi)部iS（開集），點
集的閉包ciS（并集）概念各得1 分，共5 分。
2．答：按照三次B 樣條曲線的矢量方程可得到線性方程組：
Q 0 =P 0
Q 1 =(P 0 +4P 1 +P 2 )/6
Q 2 =(P 1 +4P 2 +P 3 )/6
Q 3 =(P 2 +4P 3 +P 4 )/6
Q 4 =P 4
將給定點Q 0 (30,0), Q 1 (24,24), Q 2 (0,18), Q 3 (-24,24), Q 4 (-30,0)的坐標(biāo)值代入求解線性方
程組，可得到控制頂點：
P 1 (21,17)，P 2 (0,20) ，P 3 (-21,17)
評分說明：列出線性方程組得2 分，正確地寫出一個控制頂點得1 分，共5 分。
計算機(jī)科學(xué)與技術(shù)試卷答案第13 頁共14 頁
計算機(jī)科學(xué)與技術(shù)試卷答案第14 頁共14 頁
3.答：（1）H——代表色彩（hue），就是通常所說的紅、綠、藍(lán)、紫等，是一種顏色區(qū)別于另
一種顏色的要素；
（2）L——代表亮度（lightness），就是光的強(qiáng)度。
（3）S——代表飽和度（saturation），就是顏色的純度，在某中顏色中增加白色相當(dāng)于減
少該色的飽和度。
評分說明：H——要素名稱和含義各占1 分；L——指出亮度或強(qiáng)度就得1 分；S——要素名稱
和含義各占1 分，共5 分。（可以不寫英文名稱）
