-同等學(xué)力計(jì)算機(jī)綜合真題答案解析

2011-2014年同等學(xué)力人員申請(qǐng)碩士學(xué)位學(xué)科綜合水平全國(guó)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)試卷2011年同等學(xué)力人員申請(qǐng)碩士學(xué)位學(xué)科綜合水平全國(guó)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)試卷第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程第二部分專(zhuān)業(yè)知識(shí)課程Ⅰ.計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)Ⅱ.計(jì)算機(jī)網(wǎng)絡(luò)Ⅲ.軟件工程Ⅳ.人工智能原理Ⅴ.計(jì)算機(jī)圖形學(xué)考生須知1.本試卷滿(mǎn)分為100分，包括數(shù)學(xué)基礎(chǔ)課程和專(zhuān)業(yè)知識(shí)課程兩部分。數(shù)學(xué)基礎(chǔ)課程滿(mǎn)分40分，每位考生必答；專(zhuān)業(yè)知識(shí)課程包括五門(mén)課程，每門(mén)課程滿(mǎn)分30分，考生須從中任選2門(mén)作答，多選者只按前選課程計(jì)分。2.請(qǐng)考生務(wù)必將本人考號(hào)最后兩位數(shù)字填寫(xiě)在本頁(yè)右上角方框內(nèi)。3.考生一律用藍(lán)色或黑色墨水筆在答題紙指定位置上按規(guī)定要求作答，未做在指定位置上的答案一律無(wú)效。4.監(jiān)考員收卷時(shí)，考生須配合監(jiān)考員驗(yàn)收，并請(qǐng)監(jiān)考員在準(zhǔn)考證上簽字（作為考生交卷的憑據(jù)）。否則，若發(fā)生答卷遺失，責(zé)任由考生自負(fù)。22011-2014年數(shù)學(xué)真題解析地址為：/item.htm?id=5292688659852011-2014年計(jì)算機(jī)網(wǎng)絡(luò)真題解析地址為：/item.htm?id=529749987686第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程（共40分）一、用邏輯符號(hào)表達(dá)下列語(yǔ)句（每小題2分，共4分）1．有些人運(yùn)氣好，但并非所有人都運(yùn)氣好。2．不管黃狗還是花狗，能夠看家護(hù)院就是好狗。二、填空題（每小題2分，共12分）1．設(shè)A={1,2,3,4},B={a,b,c}，從A到B不同的二元關(guān)系共有個(gè)。從A到B不同的函數(shù)共有個(gè)。2．設(shè)|A|=n（即集合A的基數(shù)為n），問(wèn)在A上有個(gè)不同的對(duì)稱(chēng)關(guān)系。3．對(duì)6123（2x3xx)進(jìn)行展開(kāi)合并同類(lèi)項(xiàng)后，32123xxx的系數(shù)是。4．從m個(gè)人中選取n個(gè)人（n≤m）圍成一個(gè)圓桌就座，則不同的就座方法數(shù)是。5．設(shè)G是頂點(diǎn)個(gè)數(shù)為n，邊數(shù)為e，連通分支數(shù)為k的簡(jiǎn)單圖，T是包含G的所有頂點(diǎn)的森林，則G的不在T中的邊有條。6．設(shè)u,v是圖G的兩個(gè)不鄰接的頂點(diǎn)，S是圖G的頂點(diǎn)割集，且u,v是屬于GS的兩個(gè)不同的連通分支，稱(chēng)S為一個(gè)uv分離集。設(shè)最小的uv分離集中所含頂點(diǎn)的個(gè)數(shù)為a，且G中從u到v內(nèi)部不相交的路的最大條數(shù)為b，則a和b滿(mǎn)足的關(guān)系為。三、計(jì)算題（每個(gè)問(wèn)題4分，共8分）設(shè)1234567a,a,a,a,a,a,a是7個(gè)互不相同的非零實(shí)數(shù)，這七個(gè)數(shù)的全排列中，數(shù)ia（i1,,7）的原來(lái)位置是指第i個(gè)位置。求這七個(gè)數(shù)的全排列中：（1）1357a,a,a,a都不在原來(lái)的位置上，而246a,a,a都在原來(lái)位置上的排列數(shù)目。（2）246a,a,a都不在原來(lái)位置上的排列數(shù)目。四、證明題（第1，2小題各4分，第3小題8分，共16分）1．下列公式是否正確？如正確請(qǐng)證明，如錯(cuò)誤試舉出反例。(x)(y)(P(x)∧P(y)Q(x,y))=(x)(y)(P(x)∧P(y)∧Q(x,y))2．用“≈”表示等勢(shì)，試證明(0,1](a,b](a,bR,ab，R為實(shí)數(shù)集)。3．設(shè)12{,,,,}naaa滿(mǎn)足11nknknkaaa且12{,,,,}naaa的母函數(shù)為1()nnnAxax≥，3（1）（4分）證明2A(x)A(x)x0（2）（4分）證明122,11nnannn≥，其中221nn表示從2n2個(gè)數(shù)中取出n1個(gè)的組合數(shù)。4第二部分專(zhuān)業(yè)知識(shí)課程Ⅰ．計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)（共30分）一、填空題（每小題2分，共10分）1．某RISC計(jì)算機(jī)在理想情況（Cache命中率100%）下的CPI等于1。假設(shè)Load和Store這兩條指令條數(shù)占整個(gè)程序指令條數(shù)的40%，Cache的缺失率為2%，Cache缺失代價(jià)為25個(gè)時(shí)鐘周期。則這臺(tái)機(jī)器在理想情況下的速度是有Cache缺失情況下的倍。2．編號(hào)分別為0、1、…、15的16個(gè)處理器，采用單級(jí)互連網(wǎng)絡(luò)連接。當(dāng)互連函數(shù)為Cube3時(shí)，第13號(hào)處理器與第號(hào)處理器相連。3．某處理器的指令字長(zhǎng)為16位，有雙地址指令、單地址指令和零地址指令3類(lèi)，并假設(shè)每個(gè)地址字段的長(zhǎng)度均為6位。如果雙地址指令有15條，單地址指令和零地址指令的條數(shù)相近，則單地址指令有條，零地址指令有條。4．16×16矩陣A以行主（按行依次存放）方式存放在PE0至PE255中，則對(duì)A進(jìn)行至少次完全混洗變換后可獲得轉(zhuǎn)置矩陣AT。5．某計(jì)算機(jī)系統(tǒng)部件A的處理時(shí)間占某個(gè)任務(wù)運(yùn)行時(shí)間的百分比為f1，部件B的處理時(shí)間占這個(gè)任務(wù)運(yùn)行時(shí)間的百分比為f2。如果將部件A和部件B的處理速度分別加快到原來(lái)的s1倍和s2倍，則針對(duì)這類(lèi)任務(wù)，采用加速措施后整個(gè)系統(tǒng)獲得的加速比為。二、判斷題（每小題1分，共15分）判斷下列說(shuō)法是否正確。如果正確，用“√”表示，否則用“×”表示。1．對(duì)于分支造成的損失，超標(biāo)量處理器比超流水線(xiàn)處理器大。（）2．流水線(xiàn)采用的是空間并行技術(shù)。（）3．?dāng)?shù)據(jù)總線(xiàn)寬度對(duì)于高級(jí)程序員來(lái)說(shuō)是透明的。（）4．INTEL系列處理器是從INTEL486開(kāi)始使用流水線(xiàn)技術(shù)的。（）5．寄存器窗口技術(shù)是SUNSPARC處理器最先采用的技術(shù)。（）6．現(xiàn)代馮·諾依曼結(jié)構(gòu)計(jì)算機(jī)是以運(yùn)算器為中心的。（）7．指令流水線(xiàn)技術(shù)可以使任一條指令的執(zhí)行時(shí)間縮短。（）8．平均CPI越小的處理器，其速度越快。（）9．軟件兼容性要求必須做到向后兼容。（）10．INTEL安騰處理器采用的是VLIW指令系統(tǒng)。（）11．對(duì)于指令執(zhí)行速度來(lái)說(shuō)，間接尋址方式比變址尋址方式慢。（）12．VLIW采用顯式并行指令計(jì)算(EPIC：ExplicitlyParallelInstructionComputing)方式。（）13．MIPS處理器指令操作碼采用定長(zhǎng)編碼法進(jìn)行編碼。（）514．層次存儲(chǔ)系統(tǒng)需要滿(mǎn)足包含性關(guān)系，即存在于上層存儲(chǔ)器的信息，在對(duì)應(yīng)下層存儲(chǔ)器中也一定存在。（）15．片上多核（CMP）屬于SIMD型處理器。（）三、名詞解釋?zhuān)啃☆}1分，共5分）1．NUMA2．寫(xiě)通過(guò)（writethrough）3．控制相關(guān)4．向量鏈接5．Amdahl定律6Ⅱ．計(jì)算機(jī)網(wǎng)絡(luò)（共30分）一、填空題（每空1分，共6分）說(shuō)明：計(jì)算中使用簡(jiǎn)化數(shù)值：1G≈109；1M≈106；1K≈1031．長(zhǎng)度為500位的應(yīng)用層數(shù)據(jù)遞交給傳輸層處理，需加上20字節(jié)的TCP頭部。再遞交給網(wǎng)絡(luò)層處理，需加上20字節(jié)的IP頭部。最后遞交給數(shù)據(jù)鏈路層的以太網(wǎng)傳送，還需加上18字節(jié)的頭部和尾部。假設(shè)不計(jì)其他開(kāi)銷(xiāo)，該數(shù)據(jù)的傳輸效率為。2．某計(jì)算機(jī)的IP地址為22，子網(wǎng)掩碼為40，則該計(jì)算機(jī)的子網(wǎng)地址為；與掩碼對(duì)應(yīng)的網(wǎng)絡(luò)前綴有位。3．主機(jī)A和主機(jī)B要建立TCP連接，A的初始序號(hào)為X，B的初始序號(hào)為Y，在建立連接過(guò)程中，共交換了個(gè)報(bào)文；其中每一端的確認(rèn)序號(hào)的含義是。4．假設(shè)使用TCP協(xié)議傳送文件。TCP的報(bào)文段大小為1K字節(jié)（假設(shè)無(wú)擁塞，無(wú)丟失分組），接收方通告窗口為1M字節(jié)。當(dāng)慢啟動(dòng)打開(kāi)發(fā)送窗口達(dá)到32K字節(jié)時(shí)，用了個(gè)往返時(shí)延（RTT）。二、單項(xiàng)選擇題（每小題1分，共5分）1．主機(jī)A的以太網(wǎng)適配器在線(xiàn)路上偵聽(tīng)到一個(gè)幀，并將它遞交給主機(jī)A進(jìn)行處理。下列說(shuō)法中（）不能．．解釋該過(guò)程。A．該網(wǎng)絡(luò)適配器工作在混雜模式B．該幀的目的MAC地址和主機(jī)A在同一個(gè)網(wǎng)段中C．該幀的目的MAC地址是一個(gè)廣播地址D．該幀的目的MAC地址是主機(jī)A所在的多播組地址2．采用集線(xiàn)器進(jìn)行網(wǎng)絡(luò)互連，下列說(shuō)法中（）是正確的。A．?dāng)?shù)據(jù)傳輸速率可不同，數(shù)據(jù)鏈路層協(xié)議相同B．?dāng)?shù)據(jù)傳輸速率相同，數(shù)據(jù)鏈路層協(xié)議可不同C．?dāng)?shù)據(jù)傳輸速率和數(shù)據(jù)鏈路層協(xié)議均相同D．?dāng)?shù)據(jù)傳輸速率和鏈路層協(xié)議均可不同3．為實(shí)現(xiàn)透明傳輸，PPP協(xié)議使用的是（）方法。A．字符填充B．位填充C．在異步傳輸時(shí)使用位填充；在同步傳輸時(shí)使用字符填充D．在異步傳輸時(shí)使用字符填充；在同步傳輸時(shí)使用位填充4．某單位分配了一個(gè)B類(lèi)地址，計(jì)劃將內(nèi)部網(wǎng)絡(luò)分成20個(gè)子網(wǎng)，將來(lái)還要增加18個(gè)子網(wǎng)，每個(gè)子網(wǎng)的主機(jī)數(shù)接近700臺(tái)，一個(gè)可行的掩碼方案是（）。A．255．255．128．0B．255．255．248．0C．255．255．252．0D．255．255．254．075．在采用數(shù)字證書(shū)機(jī)制的系統(tǒng)中，采用公鑰密碼體制提供安全服務(wù)，其中用戶(hù)的公鑰可用于（）。A．加密和鑒別B．解密和鑒別C．加密和簽名D．解密和簽名三、名詞解釋?zhuān)啃☆}2分，共4分）1．MTU2．生成樹(shù)算法四、問(wèn)答和計(jì)算題（共15分）說(shuō)明：計(jì)算中使用簡(jiǎn)化數(shù)值：1G≈109；1M≈106；1K≈1031．（4分）主機(jī)A通過(guò)一條帶寬為100Mbps的網(wǎng)絡(luò)鏈路向主機(jī)B傳輸數(shù)據(jù)幀，假設(shè)每幀攜帶的數(shù)據(jù)是1K字節(jié)，鏈路的單向時(shí)延為15ms。若設(shè)計(jì)一個(gè)滑動(dòng)窗口協(xié)議，使得發(fā)送窗口和接收窗口的大小相同，最少需要多少位表示序號(hào)？2．（5分）考慮一個(gè)城域網(wǎng)，若源和目的主機(jī)之間的平均距離為10km，信號(hào)在傳輸介質(zhì)中的傳播速率為2×108m/s。試回答問(wèn)題：①當(dāng)數(shù)據(jù)的傳輸速率為多大時(shí)，2K字節(jié)分組的傳輸時(shí)延等于鏈路的往返傳播時(shí)延？②若線(xiàn)路帶寬為1Gbps，線(xiàn)路長(zhǎng)度為2000km，數(shù)據(jù)傳輸采用停等協(xié)議，傳輸一個(gè)100K字節(jié)的文件，能否通過(guò)增加帶寬來(lái)顯著縮短成功傳輸該文件所需的時(shí)間？試簡(jiǎn)要說(shuō)明理由。3．（6分）在圖1所示的網(wǎng)絡(luò)中，主機(jī)H_A、主機(jī)H_B、路由器R_1和路由器R_2的各端口的IP地址和MAC地址分別表示為（MAC地址，IP地址）的形式，即有：H_A(MAC_A,IP_A),H_B(MAC_B,IP_B),R_1的端口11（MAC_11，IP_11）,R_1的端口12（MAC_12，IP_12）,R_2的端口21（MAC_21，IP_21），R_2的端口22（MAC_22，IP_22）。試回答問(wèn)題：①主機(jī)H_A向主機(jī)H_B發(fā)送數(shù)據(jù)，最多需要使用多少次ARP協(xié)議？簡(jiǎn)要說(shuō)明理由。②主機(jī)H_A向主機(jī)H_B發(fā)送數(shù)據(jù)，試分別．．寫(xiě)出路由器R_1的端口11收到的數(shù)據(jù)單元以及路由器R_2的端口22轉(zhuǎn)發(fā)的數(shù)據(jù)單元中，數(shù)據(jù)鏈路層協(xié)議首部的地址字段和網(wǎng)絡(luò)層協(xié)議首部的地址字段內(nèi)容。8路由器R_1路由器R_2LAN1LAN2LAN3主機(jī)H_A主機(jī)H_B端口11端口12端口21端口22圖19Ⅲ．軟件工程（共30分）一、單項(xiàng)選擇題（每小題1分，共5分）1．（）的說(shuō)法是錯(cuò)誤的。A．螺旋模型和演化模型都適用于軟件需求不明確的項(xiàng)目開(kāi)發(fā)B．演化模型和增量模型都適用于軟件需求不明確的項(xiàng)目開(kāi)發(fā)C．螺旋模型是在瀑布模型和演化模型的基礎(chǔ)上加以修改而形成的D．增量模型是在瀑布模型的基礎(chǔ)上加以修改而形成的2．設(shè)計(jì)軟件結(jié)構(gòu)不需考慮（）。A．模塊之間的接口B．模塊間的調(diào)用關(guān)系C．模塊的功能D．模塊的局部數(shù)據(jù)3．（）的目標(biāo)是發(fā)現(xiàn)軟件的功能實(shí)現(xiàn)與需求規(guī)約的不一致。A．單元測(cè)試B．集成測(cè)試C．有效性測(cè)試D．驗(yàn)證測(cè)試4．千里馬和馬都是類(lèi)，它們之間是一種（）關(guān)系。A．聚合B．分類(lèi)C．依賴(lài)D．泛化5．公司有一名法人代表，公司和法人代表之間是一種（）關(guān)系。A．聚合B．分類(lèi)C．泛化D．依賴(lài)二、判斷題（每小題1分，共5分。如果正確，用“√”表示，否則，用“×”表示）1．UML既是一種建模語(yǔ)言，又是一種建模方法。（）2．兩個(gè)模塊共同引用一個(gè)全局?jǐn)?shù)據(jù)項(xiàng)，模塊間的這種耦合稱(chēng)為數(shù)據(jù)耦合。（）3．在應(yīng)用演化模型時(shí)，可以使用瀑布模型來(lái)管理每一個(gè)演化的增量。（）4．在軟件生存周期過(guò)程中，質(zhì)量保證過(guò)程是一類(lèi)組織過(guò)程。（）5．CMM的每一成熟度等級(jí)表示了過(guò)程能力，并且包含一組特定的關(guān)鍵過(guò)程域。（）三、簡(jiǎn)答題（每小題4分，共12分）1．給出事務(wù)型數(shù)據(jù)流圖的定義，并舉例說(shuō)明。2．給出對(duì)象的依賴(lài)關(guān)系的定義，并舉例說(shuō)明。3．給出軟件測(cè)試中分支覆蓋的定義，并舉例說(shuō)明。四、建模題（8分）問(wèn)題陳述：在一簡(jiǎn)化的圖書(shū)管理系統(tǒng)中，圖書(shū)管理員負(fù)責(zé)：10（1）購(gòu)入新書(shū)時(shí)，錄入新書(shū)的信息（分類(lèi)目錄號(hào)，流水號(hào)，書(shū)名，作者，單價(jià)，購(gòu)書(shū)日期）；（2）當(dāng)讀者借書(shū)時(shí)，將讀者的借書(shū)單信息輸入系統(tǒng)，檢查讀者學(xué)號(hào)是否有效，若無(wú)效，則拒絕借書(shū)；否則登記圖書(shū)分類(lèi)目錄號(hào)、讀者學(xué)號(hào)和借書(shū)日期等，寫(xiě)入借書(shū)文件中；（3）當(dāng)讀者還書(shū)時(shí)，根據(jù)還書(shū)單信息，從借書(shū)文件中查看讀者的借書(shū)記錄，看是否超期，若超期則給出罰款單；（4）當(dāng)一些書(shū)過(guò)期沒(méi)有保留價(jià)值時(shí)，從圖書(shū)目錄文件中刪除相關(guān)記錄。讀者負(fù)責(zé)：（1）借書(shū)時(shí)，填寫(xiě)借書(shū)單（姓名，學(xué)號(hào)，圖書(shū)分類(lèi)目錄號(hào)）；（2）還書(shū)時(shí)，填寫(xiě)還書(shū)單（姓名，學(xué)號(hào)，圖書(shū)分類(lèi)目錄號(hào)）。圖書(shū)館領(lǐng)導(dǎo)負(fù)責(zé)：（1）根據(jù)讀者學(xué)號(hào)，查詢(xún)讀者借書(shū)情況；（2）根據(jù)圖書(shū)流水號(hào)，查詢(xún)圖書(shū)庫(kù)存情況。1．（3分）用結(jié)構(gòu)化分析方法給出該系統(tǒng)的頂層DFD；2．（2分）給出頂層DFD的數(shù)據(jù)字典；3．（3分）選擇該圖書(shū)管理系統(tǒng)中的一個(gè)交互，并用順序圖來(lái)描述。11Ⅳ．人工智能原理（共30分）一、單項(xiàng)選擇題（每小題2分，共8分）1．啟發(fā)式搜索是一種尋求問(wèn)題（）的方法。A．最優(yōu)解B．一般通用解C．滿(mǎn)意解2．基于案例（case）的推理是歸結(jié)推理方法的一種特例嗎？（）A．是B．不是3．腳本（script）方法是一種結(jié)構(gòu)化的推理方法嗎？（）A．是B．不是4．不確定性推理是一種概率意義下的推理方法嗎？（）A．是B．不是二、證明題（共10分）使用單元（unit）歸結(jié)策略的歸結(jié)法（resolution）證明A1A2A3B其中A1=(x)((Ｃ(x)Ｄ(x))(y)(Ｇ(x,y)Ｅ(y)))A2=(x)((Ｃ(x)Ｆ(x))(y)(Ｇ(x,y)Ｆ(y)))A3=(y)(Ｄ(x)Ｆ(x))B=(x)(Ｅ(x)Ｆ(x))三、問(wèn)答題（每小題4分，共12分）1．說(shuō)明數(shù)據(jù)挖掘的含義，并列舉出幾種數(shù)據(jù)挖掘方法。2．說(shuō)明框架（frame）表示的含義，并給出框架的一般表示形式。3．說(shuō)明如何用基于案例的推理來(lái)構(gòu)建一個(gè)醫(yī)療診斷系統(tǒng)。12Ⅴ．計(jì)算機(jī)圖形學(xué)（共30分）一、判斷題（每小題1分，共5分。如果正確，用“√”表示，否則，用“×”表示）1．彩色打印機(jī)是采用CMY顏色模型，即利用青、品紅、黃三色在原色上的減色效果。（）2．B樣條曲線(xiàn)優(yōu)點(diǎn)之一是造型靈活，可構(gòu)造除了尖點(diǎn)之外的直線(xiàn)段、切線(xiàn)等多種特殊情況的線(xiàn)形。（）3．用NURBS方法構(gòu)造的曲線(xiàn)，對(duì)幾何變換和投影變換具有不變性。（）4．在透視投影中，若投影面的法線(xiàn)平行于某一個(gè)坐標(biāo)軸，則只可能在該軸上出現(xiàn)一個(gè)主滅點(diǎn)，即形成了一點(diǎn)透視。（）5．三維線(xiàn)框模型是表示形體常用模型之一，可應(yīng)用于繪制二、三維線(xiàn)框圖，也能準(zhǔn)確無(wú)誤地表示實(shí)體。（）二、填空題（每小題2分，共10分）1．對(duì)二維圖形使用變換矩陣031030100T變換后的結(jié)果是。2．在多邊形區(qū)域填充中必須解決的兩個(gè)特殊問(wèn)題：一是；二是。3．在計(jì)算機(jī)圖形中，所謂“體”是三維幾何元素，它是由封閉表面圍成的空間，也是歐氏空間R3中子空間，其邊界是。4．光線(xiàn)跟蹤方法是基于的原理，通過(guò)來(lái)確定反射、折射和陰影等。5．圖象數(shù)據(jù)壓縮中，步長(zhǎng)法是針對(duì)的一種基本的壓縮符號(hào)化方法，其算法實(shí)現(xiàn)是。三、問(wèn)答題（共15分）1．（5分）寫(xiě)出Bezier曲線(xiàn)的定義（提示：包括其插值公式和調(diào)和函數(shù)）。2．（4分）設(shè)投影中心為點(diǎn)O(0,0,0)，投影平面為平行于XOZ平面，且Y=5的平面，請(qǐng)寫(xiě)出此透視投影變換矩陣，并求端點(diǎn)A(4,10,6)和B(30,15,9)的直線(xiàn)段AB在該投影平面的投影。3．（3分）設(shè)一個(gè)四邊形的四個(gè)頂點(diǎn)坐標(biāo)分別為(0.5,0.5)，(1.5,1.5)，(2.5,1.5)和(1.5,0.5)，第一個(gè)頂點(diǎn)為紅色，其他三個(gè)都為白色，試寫(xiě)出用OpenGL繪制該多邊形的程序段。4．（3分）立方體網(wǎng)格模型是實(shí)體造型系統(tǒng)中建模方法之一，簡(jiǎn)要敘述其基本思想和優(yōu)缺點(diǎn)。__1絕密★啟用前2012年同等學(xué)力人員申請(qǐng)碩士學(xué)位學(xué)科綜合水平全國(guó)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)試卷第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程第二部分專(zhuān)業(yè)知識(shí)課程Ⅰ.計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)Ⅱ.計(jì)算機(jī)網(wǎng)絡(luò)Ⅲ.軟件工程Ⅳ.人工智能原理Ⅴ.計(jì)算機(jī)圖形學(xué)考生須知1.本試卷滿(mǎn)分為100分，包括數(shù)學(xué)基礎(chǔ)課程和專(zhuān)業(yè)知識(shí)課程兩部分。數(shù)學(xué)基礎(chǔ)課程滿(mǎn)分40分，每位考生必答；專(zhuān)業(yè)知識(shí)課程包括5門(mén)課程，每門(mén)課程滿(mǎn)分30分，考生須從中任選2門(mén)作答，多選者只按前選課程計(jì)分。2.請(qǐng)考生務(wù)必將本人考號(hào)最后兩位數(shù)字填寫(xiě)在本頁(yè)右上角方框內(nèi)。3.考生一律用藍(lán)色或黑色墨水筆在答題紙指定位置上按規(guī)定要求作答，未做在指定位置上的答案一律無(wú)效。4.監(jiān)考員收卷時(shí)，考生須配合監(jiān)考員驗(yàn)收，并請(qǐng)監(jiān)考員在準(zhǔn)考證上簽字（作為考生交卷的憑據(jù)）。否則，若發(fā)生答卷遺失，責(zé)任由考生自負(fù)。2第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程（共40分）一、用邏輯符號(hào)表達(dá)下列語(yǔ)句（每小題2分，共4分）1．在中國(guó)居住的人未必都是中國(guó)人（要求分別用存在量詞和全稱(chēng)量詞各給出一個(gè)表達(dá)式）。2．有且僅有一個(gè)火星。二、填空題（每空2分，共14分）1．在(12)nx的展開(kāi)式中kx的系數(shù)是，其中(1≤k≤n)。2．設(shè)數(shù)列{}na滿(mǎn)足遞推關(guān)系：12nnaa且1a1，則滿(mǎn)足此遞推關(guān)系na的解是。3．設(shè)G是一個(gè)有n個(gè)頂點(diǎn)和f個(gè)面的連通平面圖，則G有條邊。4．如果五個(gè)文科生和五個(gè)理科生排成一排，共有種不同的排法；如果要求文科生和理科生交替排成一排，則共有種不同的排法。5．由3個(gè)a，1個(gè)b，2個(gè)c這六個(gè)元素組成的不同排列的總數(shù)是。6．設(shè)圖G的頂點(diǎn)集合6,12345VG=v,v,v,v,vv，邊集合為122334455156EG=vv,vv,vv,vv,vv,vv，則G的不同生成樹(shù)的棵數(shù)為。三、解答題（共16分）1．（5分）設(shè)用數(shù)字2，4，6，8（數(shù)字可重復(fù)使用）可組成na個(gè)含奇數(shù)個(gè)2，偶數(shù)個(gè)6且至少含一個(gè)8的n位數(shù)(n≥2)。（1）（2分）寫(xiě)出數(shù)列{}na的指數(shù)型母函數(shù)g(x)；（2）（3分）求出na的表達(dá)式。2．（5分）把4個(gè)相異的球放到3個(gè)相異的盒子中，使得不出現(xiàn)空盒，有多少種不同的放法？3．（6分）設(shè)A{1,2,3}，（1）計(jì)算A上二元關(guān)系的個(gè)數(shù)。（2）求出A上所有的等價(jià)關(guān)系。四、證明題（6分）證明：對(duì)任意集合A，B，__________C，有(A∩B)∪C=A∩(B∪C)當(dāng)且僅當(dāng)CA。3第二部分專(zhuān)業(yè)知識(shí)課程Ⅰ．計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)（共30分）一、選擇題（每小題1分，共5分）一臺(tái)個(gè)人計(jì)算機(jī)采用了如下三種基本輸入輸出方式：A．程序控制（狀態(tài)驅(qū)動(dòng)）方式B．中斷方式C．DMA（直接存儲(chǔ)器存?。┓绞綄?duì)于下面5種情況，應(yīng)該采用哪種輸入輸出方式？試選擇對(duì)應(yīng)的A或B或C分別填入括號(hào)中。1．從硬盤(pán)存儲(chǔ)器中讀一個(gè)數(shù)據(jù)塊到內(nèi)存中，通常采用（）。2．處理電源掉電等例外事件，應(yīng)該采用（）。3．從鍵盤(pán)接收字符并輸出到顯示器上，要求編程簡(jiǎn)單，應(yīng)該采用（）。4．CPU運(yùn)行用戶(hù)程序與打印機(jī)輸出文件并行工作，應(yīng)該采用（）。5．實(shí)際輸入輸出操作主要由硬件（不是程序）完成，應(yīng)該采用（）。二、填空題（每空1分，共10分）1．一個(gè)存儲(chǔ)系統(tǒng)由第一級(jí)Cache、第二級(jí)Cache和主存儲(chǔ)器組成，它們的延遲時(shí)間分別為1個(gè)時(shí)鐘周期、10個(gè)時(shí)鐘周期和100個(gè)時(shí)鐘周期。每條指令平均訪(fǎng)問(wèn)存儲(chǔ)器1.5次。在執(zhí)行1000條指令的過(guò)程中，訪(fǎng)問(wèn)第二級(jí)Cache90次，訪(fǎng)問(wèn)主存儲(chǔ)器36次。試問(wèn)：（1）第一級(jí)Cache的命中率是（）。（2）第二級(jí)Cache的命中率是（）。（3）訪(fǎng)問(wèn)一次存儲(chǔ)器平均需要（）個(gè)時(shí)鐘周期。（4）由于訪(fǎng)問(wèn)存儲(chǔ)器引起的執(zhí)行每條指令平均停頓（）個(gè)時(shí)鐘周期。（5）只考慮訪(fǎng)問(wèn)存儲(chǔ)器的影響，CPI為（）。2．有64個(gè)處理機(jī)采用單級(jí)互連網(wǎng)絡(luò)連接，處理機(jī)編號(hào)分別為0、1、2、…、63，試分別計(jì)算下列互連函數(shù)（自變量為10進(jìn)制數(shù)表示的處理機(jī)編號(hào)，計(jì)算結(jié)果也用10進(jìn)制數(shù)表示）。（1）Exchange3(15)＝（）（2）Shuffle(6)＝（）（3）Butterfly(17)＝（）（4）Reversal(40)＝（）（5）PM2I+4(54)＝（）三、計(jì)算題（共15分）1．（每小題2分，其中每個(gè)答案各1分；共10分）一臺(tái)處理機(jī)采用頁(yè)式虛擬存儲(chǔ)器和組相聯(lián)Cache，按字節(jié)編址，最多允許32個(gè)用戶(hù)同時(shí)使用，每頁(yè)大小為1KB。虛擬地址的長(zhǎng)度為32位（二進(jìn)制）?？毂戆吹刂吩L(fǎng)問(wèn)，其地址經(jīng)散列變換得到，容量為32個(gè)字。主存容量為1GB。Cache容量為2MB。Cache的組大小與主存的頁(yè)大小相等，每組16塊。試40123456789101112131415計(jì)算：（1）虛擬地址中，用戶(hù)號(hào)和虛頁(yè)號(hào)各多少位？（2）主存地址中，實(shí)頁(yè)號(hào)和頁(yè)內(nèi)偏移各多少位？（3）Cache地址中，組號(hào)和塊號(hào)各多少位？（4）散列變換部件的輸入和輸出各多少位？（5）快表每個(gè)字中虛頁(yè)號(hào)和實(shí)頁(yè)號(hào)各多少位？2．（每小題1分，共5分）一臺(tái)多處理機(jī)系統(tǒng)由16個(gè)相同的處理機(jī)通過(guò)閉合螺旋線(xiàn)網(wǎng)絡(luò)連接而成，如圖。每個(gè)處理機(jī)內(nèi)有一個(gè)4級(jí)流水線(xiàn)加法器。該加法器每個(gè)流水段的延遲時(shí)間均為1ns。在相鄰處理機(jī)之間傳送一個(gè)數(shù)據(jù)需要2ns。采用這臺(tái)多處理機(jī)計(jì)算310iiSA。32個(gè)源操作數(shù)分別存放在16個(gè)處理機(jī)中，每個(gè)處理機(jī)中存放源操作數(shù)Ai(i=0,1,2,…,31)中的兩個(gè)。只計(jì)算加法時(shí)間和數(shù)據(jù)在處理機(jī)之間的傳送時(shí)間。最終結(jié)果存放在0號(hào)處理機(jī)中。（1）試設(shè)計(jì)求S的算法：要求所用時(shí)間最少，并寫(xiě)出算法主要步驟。（2）給出全部計(jì)算所用的時(shí)間。（3）計(jì)算16個(gè)加法器流水線(xiàn)的總使用效率。（4）如果采用單處理機(jī)（與上述16個(gè)處理機(jī)中的一個(gè)處理機(jī)性能相同）完成這32個(gè)數(shù)的求和運(yùn)算需要多少時(shí)間？（5）計(jì)算這臺(tái)多處理機(jī)系統(tǒng)的加速比。5Ⅱ．計(jì)算機(jī)網(wǎng)絡(luò)（共30分）一、填空題（每空1分，共6分）1．在無(wú)噪聲的情況下，若某通信鏈路的帶寬為3kHz，所采用的調(diào)制方法支持32種信號(hào)狀態(tài)，則該通信鏈路的最大數(shù)據(jù)傳輸速率為kbps。2．3是一個(gè)類(lèi)IP地址，若子網(wǎng)掩碼為，則該IP地址所在子網(wǎng)的廣播地址為。3．針對(duì)不同自治系統(tǒng)之間的路由選擇協(xié)議，目前最常用的外部網(wǎng)關(guān)協(xié)議為。4．FTP采用的傳輸層協(xié)議為，建立連接時(shí)服務(wù)器端的缺省端口號(hào)為。二、單項(xiàng)選擇題（每小題1分，共5分）1．對(duì)于選擇重傳ARQ的滑動(dòng)窗口協(xié)議，若序號(hào)位數(shù)為n個(gè)bit，則接收窗口的最大尺寸為（）。A．2n-1B．2nC．2n-1D．2n-12．在某一個(gè)子網(wǎng)中，為四臺(tái)計(jì)算機(jī)分別分配以下4個(gè)IP地址（子網(wǎng)掩碼均為40），其中一臺(tái)計(jì)算機(jī)因IP地址分配不當(dāng)而造成通信故障，這一臺(tái)計(jì)算機(jī)的IP地址為（）。A．90B．95C．00D．053．以太網(wǎng)交換機(jī)按照自學(xué)習(xí)算法建立轉(zhuǎn)發(fā)表，它通過(guò)（）進(jìn)行地址學(xué)習(xí)。A．幀中的源MAC地址B．幀中的目的MAC地址C．幀中的源MAC地址和目的MAC地址D．ARP協(xié)議4．主機(jī)甲與主機(jī)乙之間已建立TCP連接，主機(jī)甲向主機(jī)乙發(fā)送了三個(gè)TCP段，其中有效載荷長(zhǎng)度分別為400、500、600字節(jié)，第一個(gè)段的序號(hào)為100，傳輸過(guò)程中第二個(gè)段丟失，主機(jī)乙收到第一和第三個(gè)段后分別返回確認(rèn)，分別返回的兩個(gè)確認(rèn)號(hào)是（）。A．500和1600B．500和500C．500和1100D．400和10005．關(guān)于應(yīng)用層協(xié)議，以下說(shuō)法中錯(cuò)誤的是（）。A．HTTP協(xié)議在傳輸層使用TCP協(xié)議B．FTP使用2個(gè)TCP連接：一個(gè)控制連接和一個(gè)數(shù)據(jù)連接C．如果傳輸?shù)恼?qǐng)求與應(yīng)答報(bào)文丟失，將由Web瀏覽器與Web服務(wù)器負(fù)責(zé)恢復(fù)D．WWW服務(wù)器進(jìn)程的默認(rèn)端口號(hào)是80（TCP）三、名詞解釋?zhuān)啃☆}2分，共4分）1．路由協(xié)議RIP2．VPN6四、問(wèn)答和計(jì)算題（共15分）1．（每小題2分，共4分）一個(gè)采用CSMA/CD介質(zhì)訪(fǎng)問(wèn)控制方式的局域網(wǎng)，總線(xiàn)是一條完整的同軸電纜，數(shù)據(jù)傳輸率為10Mbps（1M=106），信號(hào)在總線(xiàn)傳輸介質(zhì)中的傳播速度為2×108m/s。試計(jì)算：（1）如果最小幀長(zhǎng)為600bit，那么最遠(yuǎn)的兩臺(tái)主機(jī)之間的距離為多少米？（2）假如最小幀長(zhǎng)保持不變，當(dāng)數(shù)據(jù)傳輸率提高到100Mbps時(shí)，為滿(mǎn)足CSMA/CD要求，該局域網(wǎng)需做哪些調(diào)整？2．（5分）某網(wǎng)絡(luò)采用RIP路由協(xié)議，當(dāng)路由器A收到從路由器C發(fā)來(lái)的距離向量時(shí)，試問(wèn)：（1）（3分）A的路由表將發(fā)生怎樣的變化？試畫(huà)出路由器A新的路由表。（2）（2分）隨后A收到兩個(gè)分別發(fā)往Net4和Net6的數(shù)據(jù)報(bào)，A將怎樣轉(zhuǎn)發(fā)？3．（6分）設(shè)TCP擁塞控制算法中，擁塞窗口cwnd的初始值為1（報(bào)文段），慢開(kāi)始閾值ssthresh的初始值為8（報(bào)文段）。當(dāng)擁塞窗口cwnd上升到14（報(bào)文段），網(wǎng)絡(luò)發(fā)生超時(shí)，TCP啟用擁塞避免過(guò)程。試分別計(jì)算TCP建立連接后第1輪次到第15輪次的擁塞窗口cwnd大?。▓?bào)文段），并要求寫(xiě)出計(jì)算過(guò)程。C發(fā)來(lái)的距離向量表目的網(wǎng)絡(luò)距離Net11Net22Net30Net43Net53Net65A的路由表目的網(wǎng)絡(luò)距離下一跳路由器Net10直接連接Net27ANet41CNet65DNet76BNet82D7Ⅲ．軟件工程（共30分）一、單項(xiàng)選擇題（每小題1分，共5分）1．軟件的正確性是指（）。A．軟件能正常運(yùn)行B．軟件達(dá)到預(yù)期功能的程度C．軟件符合用戶(hù)的要求D．軟件運(yùn)行中不出現(xiàn)任何錯(cuò)誤2．結(jié)構(gòu)化分析方法中的主要概念有（）。A．模塊內(nèi)聚和耦合B．對(duì)象及類(lèi)C．模塊和信息隱蔽D．加工、數(shù)據(jù)流和數(shù)據(jù)源等3．軟件需求很明確時(shí)，適用的軟件開(kāi)發(fā)模型是（）。A．噴泉模型B．增量模型C．瀑布模型D．螺旋模型4．軟件測(cè)試過(guò)程模型給出了（）。A．用例設(shè)計(jì)過(guò)程B．軟件測(cè)試的要素以及它們之間的關(guān)系C．白盒測(cè)試技術(shù)的要點(diǎn)D．測(cè)試覆蓋準(zhǔn)則5．教師是學(xué)校的一個(gè)部分，學(xué)校和教師之間是一種（）關(guān)系。A．聚合B．分類(lèi)C．泛化D．依賴(lài)二、判斷題（每小題1分，共5分。如果正確，用“√”表示，否則，用“×”表示）1．在對(duì)象的整個(gè)生命周期中，不同的對(duì)象可以具有相同的標(biāo)識(shí)。（）2．模塊間通過(guò)參數(shù)傳遞基本類(lèi)型的數(shù)據(jù)，模塊間的這種耦合稱(chēng)為數(shù)據(jù)耦合。（）3．以結(jié)構(gòu)化分析方法建立的系統(tǒng)模型就是數(shù)據(jù)流圖。（）4．CMM（能力成熟度模型）的第三級(jí)是已定義級(jí)。（）5．面向?qū)ο蠓治龇椒ㄅc結(jié)構(gòu)化分析方法的區(qū)別之一是一個(gè)使用“抽象”，而另一個(gè)沒(méi)有使用“抽象”。（）三、簡(jiǎn)答題（每小題4分，共12分）1．給出模塊耦合的定義，并舉例說(shuō)明3種模塊耦合。2．給出對(duì)象的關(guān)聯(lián)關(guān)系定義，并舉例說(shuō)明。3．給出模塊的高內(nèi)聚、低耦合原則的具體含義。四、建模題（8分）問(wèn)題陳述：在一簡(jiǎn)化的圖書(shū)銷(xiāo)售管理系統(tǒng)中，庫(kù)房管理員負(fù)責(zé)：（1）輸入、修改、刪除入庫(kù)圖書(shū)信息（圖書(shū)名，圖書(shū)編號(hào)，數(shù)量，單價(jià)，入庫(kù)日期）；8（2）打印庫(kù)房圖書(shū)庫(kù)存清單（圖書(shū)名，圖書(shū)編號(hào)，庫(kù)存量，庫(kù)存金額）。銷(xiāo)售員負(fù)責(zé)：（1）錄入圖書(shū)銷(xiāo)售信息（圖書(shū)名，圖書(shū)編號(hào)，銷(xiāo)售量，單價(jià)）；（2）輸入、修改、刪除前臺(tái)圖書(shū)信息（圖書(shū)名，圖書(shū)編號(hào)，數(shù)量，單價(jià)）；（3）打印前臺(tái)圖書(shū)庫(kù)存清單（圖書(shū)名，圖書(shū)編號(hào)，庫(kù)存量，庫(kù)存金額）。部門(mén)經(jīng)理負(fù)責(zé)：（1）統(tǒng)計(jì)月圖書(shū)銷(xiāo)售金額；（2）統(tǒng)計(jì)月圖書(shū)庫(kù)存情況（圖書(shū)名，圖書(shū)編號(hào)，庫(kù)存量，庫(kù)存金額）。試回答：1．（3分）用結(jié)構(gòu)化分析方法給出該系統(tǒng)的頂層DFD；2．（2分）給出頂層DFD的數(shù)據(jù)字典；3．（3分）選擇該圖書(shū)銷(xiāo)售管理系統(tǒng)中的一個(gè)交互，并用順序圖來(lái)描述。9Ⅳ．人工智能原理（共30分）一、單項(xiàng)選擇題（每小題2分，共8分）1．本體（ontology）是一種（）。A．推理方法B．產(chǎn)生式系統(tǒng)的另一種表示形式C．概念和概念間關(guān)系的表示方法2．百度、谷歌的知識(shí)問(wèn)答系統(tǒng)，所使用的主要技術(shù)是（）。A．知識(shí)推理方法B．自然語(yǔ)言的語(yǔ)義理解C．簡(jiǎn)單的模式匹配方法3．A*算法是一種（）。A．深度優(yōu)先搜索算法B．寬度優(yōu)先搜索算法C．可求得最優(yōu)解的圖搜索算法4．使用神經(jīng)網(wǎng)絡(luò)求解問(wèn)題，常用的方法是通過(guò)（）來(lái)達(dá)到。A．增減神經(jīng)網(wǎng)絡(luò)的層次B．調(diào)整神經(jīng)網(wǎng)絡(luò)的連接權(quán)值C．增減輸入節(jié)點(diǎn)二、證明題（共10分）使用線(xiàn)性歸結(jié)策略的歸結(jié)法(resolution)證明A1A2A3B其中A1=(x)((P(x)Q(x))(y)(W(x,y)V(y)))A2=(x)((P(x)U(x))__隷____(y)(W(x,y)U(y)))A3=(x)(Q(x)U(x))B=(x)(V(x)U(x))三、問(wèn)答題（每小題4分，共12分）1．說(shuō)明在專(zhuān)家系統(tǒng)中不確定推理的含義，以及建立一種不確定推理機(jī)制，要解決哪些問(wèn)題？2．說(shuō)明在自然語(yǔ)言處理中，機(jī)器理解了一段輸入的“自然語(yǔ)言文本”的含義是什么？3．近年來(lái)人工智能學(xué)科的研究熱點(diǎn)，主要集中在哪幾個(gè)方面？10Ⅴ．計(jì)算機(jī)圖形學(xué)（共30分）一、判斷題（每小題1分，共5分。如果正確，用“√”表示，否則用“×”表示）1．LCD圖形顯示器可采用CMY顏色模型，即利用青、品紅、黃三色在原色上的加色效果。（）2．B樣條曲線(xiàn)與Bezier曲線(xiàn)都具有幾何不變性，仿射不變性。（）3．Coons曲面造型方法是基于一種曲面分片和拼合造型形成的。（）4．只要往三坐標(biāo)平面做平行的投影，就可以產(chǎn)生出工程制圖所需要的三個(gè)視圖。（）5．真實(shí)感圖形繪制能在計(jì)算機(jī)中重現(xiàn)真實(shí)世界，其主要任務(wù)是模擬真實(shí)物體的屬性，包括最難模擬的光照和物體表面屬性。（）二、填空題（每小題2分，共10分）1．對(duì)二維圖形使用變換矩陣11211000120變換后的結(jié)果是：。2．畫(huà)家算法是繪制真實(shí)圖形常用算法之一，其原理是：先將屏幕，再將物體的各個(gè)面排序后，由遠(yuǎn)及近地繪制。3．在邊界表示法中，物體邊界上的面是有向的﹑有界的，而且其法向總是，其邊界是。4．在簡(jiǎn)單光照明模型中，光源被假定為點(diǎn)光源，反射作用被細(xì)分為和。5．在真實(shí)感圖形學(xué)中，可用和兩種不同的方法定義紋理。三、問(wèn)答題（共15分）1．（5分）寫(xiě)出B樣條曲線(xiàn)的定義及其表達(dá)式和遞推公式。2．（4分）簡(jiǎn)要說(shuō)明OpenGL是什么標(biāo)準(zhǔn)，具有什么突出特點(diǎn)。3．（6分）八叉樹(shù)模型是實(shí)體造型系統(tǒng)中建模方法之一，簡(jiǎn)要敘述其優(yōu)缺點(diǎn)。__1絕密★啟用前2013年同等學(xué)力人員申請(qǐng)碩士學(xué)位學(xué)科綜合水平全國(guó)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)試卷第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程第二部分專(zhuān)業(yè)知識(shí)課程Ⅰ．計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)Ⅱ．計(jì)算機(jī)網(wǎng)絡(luò)Ⅲ．軟件工程Ⅳ．人工智能原理Ⅴ．計(jì)算機(jī)圖形學(xué)考生須知1.本試卷滿(mǎn)分為100分，包括數(shù)學(xué)基礎(chǔ)課程和專(zhuān)業(yè)知識(shí)課程兩部分。數(shù)學(xué)基礎(chǔ)課程滿(mǎn)分為40分，每位考生必答；專(zhuān)業(yè)知識(shí)課程包括五門(mén)課程，每門(mén)課程滿(mǎn)分為30分，考生須從中任選2門(mén)作答，多選者只按前選課程計(jì)分。2.考生務(wù)必將本人考號(hào)最后兩位數(shù)字填寫(xiě)在本頁(yè)右上角方框內(nèi)。3.考生一律用藍(lán)色或黑色墨水筆在答題紙指定位置上按規(guī)定要求作答，未做在指定位置上的答案一律無(wú)效。4.監(jiān)考員收卷時(shí)，考生須配合監(jiān)考員驗(yàn)收，并請(qǐng)監(jiān)考員在準(zhǔn)考證上簽字（作為考生交卷的憑據(jù)），否則，若發(fā)生答卷遺失，責(zé)任由考生自負(fù)。2第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程（共40分）一、用邏輯符號(hào)表達(dá)下列語(yǔ)句（每小題2分，共4分）1．發(fā)光的不都是金子。（注：給出兩種表達(dá)，一種用存在量詞，另一種用全稱(chēng)量詞）2．有些大學(xué)生不尊敬老人。二、填空題（第1小題2分，第2到第6小題每空2分，共16分）1．設(shè)集合A有100個(gè)元素，則A有個(gè)子集。其中有個(gè)子集其元素個(gè)數(shù)為奇數(shù)。2．任意一個(gè)圖中度數(shù)是奇數(shù)的頂點(diǎn)個(gè)數(shù)一定是。3．如果四對(duì)夫妻圍圓桌就座，沒(méi)有任何限制條件，共有種不同的座法；如果這四對(duì)夫妻中的四個(gè)男士和四個(gè)女士排成一排，要求男女交替，則有種不同的排法;如果這四對(duì)夫妻圍圓桌就座,要求夫妻相鄰的座法有種。4．設(shè)是頂點(diǎn)集為V、邊集為E的圖。令，則用和把表示出來(lái)的表達(dá)式是。這里是頂點(diǎn)的度數(shù)（或次數(shù)），和分別是V和E中所含元素的個(gè)數(shù)。(,)GVE1()()||vVDGdvV()DG||V||E()dvv||V||E5．設(shè)Q是一個(gè)有理數(shù)集。對(duì)任意的，定義二元運(yùn)算，則Q關(guān)于運(yùn)算的單位元是，其中“”是有理數(shù)中通常的乘法運(yùn)算。,abQ()/2abab6．把6個(gè)相同的球分到3個(gè)同學(xué)手里，允許有的同學(xué)未分配到球的情況出現(xiàn)，則有種不同的分法。三、計(jì)算題（第1小題3分，第2小題4分，第3小題6分，共13分）1．定義P↑Q=(P∧Q)，試僅用與非聯(lián)結(jié)詞↑分別表示出（1）P（2）P∧Q（3）PQ均要求結(jié)果簡(jiǎn)潔。2．設(shè)a、b、c、d這四個(gè)元素的全排列中不允許出現(xiàn)ac和bd的排列數(shù)。3．用紅、黃、藍(lán)色對(duì)的棋盤(pán)方格涂色，設(shè)涂紅色方格的個(gè)數(shù)是偶數(shù)且至少有一個(gè)方格涂黃色的涂色方法數(shù)為（n是正整數(shù)）。1nnh（1）試確定的指數(shù)型生成函數(shù)；nh（2）求。nh3四、證明題（第1小題4分，第2小題3分，共7分）1．給出命題：“對(duì)于集合A上的任意關(guān)系R，如果R是對(duì)稱(chēng)的和傳遞的，則R一定是自反的。”若命題正確，則給出完整證明；若命題錯(cuò)誤，則指出錯(cuò)誤所在，并在集合{1,2,3}上構(gòu)造一個(gè)關(guān)系R1（反例）使得R1是對(duì)稱(chēng)的和傳遞的，但不是自反的。2．設(shè)A為包含n個(gè)元素的有限集，R是A上的關(guān)系，則必存在s和t，使得，且。stRR202nst≤≤4第二部分專(zhuān)業(yè)知識(shí)課程Ⅰ．計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)（共30分）一、選擇題（每小題1分，共5分）某大型計(jì)算機(jī)有如下三種通道工作方式：A．字節(jié)多路通道B．?dāng)?shù)組多路通道C．選擇通道對(duì)于下面5種情況，選擇對(duì)應(yīng)的A或B或C填入括號(hào)中。1．低速外部設(shè)備通常采用（）方式2．使用硬件元件最少的是（）方式3．使用硬件元件最多的是（）方式4．通常只有一個(gè)磁盤(pán)工作，采用（）方式5．經(jīng)常需要多個(gè)磁盤(pán)同時(shí)工作，采用（）方式二、填空題（每空1分，共10分）1．采用2-4擴(kuò)展編碼法設(shè)計(jì)指令操作碼，最多能設(shè)計(jì)出（）條指令，其中操作碼長(zhǎng)度為2位的指令（）條，操作碼長(zhǎng)度為4位的指令（）條。2．用1M×8b（二進(jìn)制位）的靜態(tài)存儲(chǔ)芯片構(gòu)成一個(gè)4M×32b的存儲(chǔ)器，需要存儲(chǔ)器芯片（）片，各存儲(chǔ)芯片的地址有（）位，該靜態(tài)存儲(chǔ)器的地址共有（）位。3．在一個(gè)存儲(chǔ)系統(tǒng)中，主存儲(chǔ)器的訪(fǎng)問(wèn)周期、存儲(chǔ)容量和單位容量?jī)r(jià)格分別為30ns、2GB和0.1元/MB；而Cache的訪(fǎng)問(wèn)周期、存儲(chǔ)容量和單位容量?jī)r(jià)格分別為5ns、16MB和1元/MB，Cache的命中率為0.98。則這個(gè)存儲(chǔ)系統(tǒng)的訪(fǎng)問(wèn)周期是（），存儲(chǔ)容量是（），單位容量的價(jià)格是（），這個(gè)存儲(chǔ)系統(tǒng)的訪(fǎng)問(wèn)效率是（）。5三、計(jì)算題（共15分）1．（每小題2分，共8分）一個(gè)由20000條指令組成的程序，在一臺(tái)工作主頻為2GHz，采用5段流水線(xiàn)的雙發(fā)射處理機(jī)上執(zhí)行，忽略由于轉(zhuǎn)移指令和亂序執(zhí)行等造成的損失。試計(jì)算：（1）相對(duì)于同樣工作主頻的非流水線(xiàn)單發(fā)射處理機(jī)的加速比。（2）指令流水線(xiàn)在執(zhí)行這個(gè)程序時(shí)的效率。（3）指令流水線(xiàn)在執(zhí)行這個(gè)程序時(shí)的吞吐率。（4）該處理機(jī)的峰值速度。2．（共7分）在一臺(tái)單流水線(xiàn)多操作部件處理機(jī)上執(zhí)行下面的程序P。取指令和指令譯碼各需要一個(gè)時(shí)鐘周期，執(zhí)行MOVE、ADD和MUL操作分別需要2個(gè)、3個(gè)和4個(gè)時(shí)鐘周期。每個(gè)操作都在第一個(gè)時(shí)鐘周期從通用寄存器中讀操作數(shù)，在最后一個(gè)時(shí)鐘周期把運(yùn)算結(jié)果寫(xiě)到通用寄存器中。程序P：k：MOVER1,R0；R1←（R0）k+1：MULR0,R2,R1；R0←（R2）×（R1）k+2：ADDR0,R2,R3；R0←（R2）＋（R3）（1）寫(xiě)出指令之間的所有數(shù)據(jù)相關(guān)（包括寫(xiě)讀相關(guān)、讀寫(xiě)相關(guān)和寫(xiě)寫(xiě)相關(guān)）。（2）在程序?qū)嶋H執(zhí)行過(guò)程中，有哪幾種數(shù)據(jù)相關(guān)會(huì)引起流水線(xiàn)停頓？分別停頓了幾個(gè)時(shí)鐘周期？（3）計(jì)算執(zhí)行完這3條指令共用了多少個(gè)時(shí)鐘周期。6Ⅱ．計(jì)算機(jī)網(wǎng)絡(luò)（共30分）一、填空題（每空1分，共6分）1．在網(wǎng)絡(luò)協(xié)議的三要素中，表示事件實(shí)現(xiàn)順序的詳細(xì)說(shuō)明；說(shuō)明需要發(fā)出何種控制信息及如何響應(yīng)。2．一個(gè)路由器的路由表有如下表項(xiàng)：目的網(wǎng)絡(luò)地址子網(wǎng)掩碼下一跳接口0接口1路由器ADefaultDefault路由器B2014年同等學(xué)力計(jì)算機(jī)綜合真題第一部分?jǐn)?shù)學(xué)基礎(chǔ)課(共40分）用邏輯符號(hào)表達(dá)下列語(yǔ)句（每小題2分，共4分）所有正數(shù)都可以開(kāi)平方（注：所設(shè)論域均為包含一切事物的集合，下同）。沒(méi)有最大的自然數(shù)。填空題（第1小題2分，其他每小題3分，共14分）如果=，則=_______。n個(gè)男同學(xué)和n個(gè)女同學(xué)參加舞會(huì)，當(dāng)?shù)谝皇孜枨懫饡r(shí)，每個(gè)男同學(xué)要找一位女同學(xué)跳舞，n個(gè)男同學(xué)一共有____種方法選擇女同學(xué)。當(dāng)?shù)诙孜枨懫饡r(shí)，要求每個(gè)人都要更換舞伴，這時(shí)n個(gè)男同學(xué)選擇女同學(xué)的方法數(shù)是_______。設(shè)G是n個(gè)頂點(diǎn)的簡(jiǎn)單連同平面圖且每個(gè)面的度數(shù)（也稱(chēng)次數(shù)）都是3，則此圖的邊數(shù)是_______________。設(shè)G是有n個(gè)頂點(diǎn)的圈，如果n是奇數(shù)，則G的正常邊著色數(shù)是＿＿＿＿＿。設(shè)ɑn滿(mǎn)足的遞推關(guān)系和初始條件分別為,，則的精確表達(dá)式是__________。計(jì)算題（共12分）（3分）設(shè)集合A={1,2}，B={a,b,c}。（1）問(wèn)從A到B有多少個(gè)單射函數(shù)。（2）試寫(xiě)出從A到B所有非單射的函數(shù)。（3分）已知集合A={1,2，...，6}上的等價(jià)關(guān)系R定義為：R=IA∪{<1,5>,<5,1>,<2,3>,<3,2>,<2,6>,<6,2>,<3,6>,<6,3>}求出由R誘導(dǎo)的A的劃分（即由R的商集誘導(dǎo)的劃分）。（6分）已知A是由54的所有因子組成的集合，設(shè)%為A上的整除關(guān)系，（1）畫(huà)出偏序集<A,%>的哈斯圖。（2）確定A中最長(zhǎng)鏈的長(zhǎng)度，并按字典序?qū)懗鯝中所有最長(zhǎng)的鏈。（3）A中元素至少可以劃分成多少個(gè)互不相交的反鏈，并完整寫(xiě)出這些反鏈。解答題（每小題5分，共10分）1.求方程t1+t2+t3+t4=20整數(shù)解的個(gè)數(shù)，其中t1≥3,t2≥1,t3≥0,t4≥5。2.設(shè)S={∞·2,∞·4,∞·5,∞·7,∞·9}是給定的重集，其中2,4,5,7,9是S中的五個(gè)不同元素，且每個(gè)元素在集合中可以有無(wú)窮多。設(shè)hn表示從S中取n個(gè)元素（可以重復(fù)取）且要求2和4出現(xiàn)偶數(shù)次的排列數(shù)，求hn。Ⅱ.計(jì)算機(jī)網(wǎng)絡(luò)（共30分）填空題（每空1分，共6分）以太網(wǎng)交換機(jī)在收到一幀后先進(jìn)行；在轉(zhuǎn)發(fā)幀時(shí)，對(duì)于未知目的地的幀，可以采用方式轉(zhuǎn)發(fā)。某計(jì)算機(jī)的IP地址為，子網(wǎng)掩碼為，則該計(jì)算機(jī)的子網(wǎng)地址為；與掩碼對(duì)應(yīng)的網(wǎng)絡(luò)前綴有位。TCP的連接端點(diǎn)稱(chēng)為，由拼接而成。單項(xiàng)選擇題（每小題1分，共5分）不屬于數(shù)據(jù)鏈路層的功能是（）。A.使用滑動(dòng)窗口協(xié)議進(jìn)行流量控制B.為應(yīng)用進(jìn)程之間提供端到端的可靠通信C.提供數(shù)據(jù)的透明傳輸機(jī)制D.提供差錯(cuò)檢測(cè)機(jī)制關(guān)于BGP協(xié)議的描述正確的是（）。A.BGP協(xié)議總是選擇最短路徑進(jìn)行分組路由B.BGP不支持無(wú)分類(lèi)域間路由選擇CIDRC.BGP采用距離向量算法計(jì)算路由表D.BGP協(xié)議交換路由信息的結(jié)點(diǎn)數(shù)量級(jí)是自治系統(tǒng)個(gè)數(shù)的量級(jí)一臺(tái)主機(jī)的IP地址為2，子網(wǎng)掩碼為，下列選項(xiàng)中可不經(jīng)過(guò)路由器直接與該主機(jī)進(jìn)行通信的是（）。A.7B.2C.5D.2某單位建立了一個(gè)由30臺(tái)計(jì)算機(jī)組成的通信網(wǎng)絡(luò)，網(wǎng)絡(luò)中任意兩個(gè)計(jì)算機(jī)之間的往返時(shí)延是20ms，它們之間的通信采用UDP協(xié)議進(jìn)行請(qǐng)求和響應(yīng)。如果在40ms內(nèi)沒(méi)有收到響應(yīng)，該計(jì)算機(jī)就重傳請(qǐng)求。但很快該網(wǎng)絡(luò)就發(fā)生了擁塞崩潰。下列選項(xiàng)中能解決這個(gè)問(wèn)題的方法是（）。A.增加超時(shí)計(jì)時(shí)器的超時(shí)時(shí)間B.增加路由器中隊(duì)列長(zhǎng)度C.接收方使用滑動(dòng)窗口機(jī)制防止緩沖區(qū)溢出D.在超時(shí)后重傳請(qǐng)求時(shí)，使用二進(jìn)制指數(shù)后退算法用戶(hù)甲發(fā)送消息給用戶(hù)乙，如果既需要提供認(rèn)證功能，又要保證被發(fā)送消息的保密性，可采用的方法是（）。A.發(fā)送方先用接收方的公鑰進(jìn)行數(shù)字簽名，然后再用自己的私鑰進(jìn)行加密B.發(fā)送方先用其私鑰對(duì)消息進(jìn)行數(shù)字簽名，然后再用接收方的公鑰加密C.發(fā)送方用其私鑰對(duì)消息進(jìn)行數(shù)字簽名和加密D.發(fā)送方先用接收方的公鑰進(jìn)行數(shù)字簽名和加密名詞解釋?zhuān)啃☆}2分，共4分）1.時(shí)延帶寬積2.慢開(kāi)始（slow-start)問(wèn)題和計(jì)算題（共15分）說(shuō)明：計(jì)算中記：1G≈；1M≈；1K≈（5分）假設(shè)一個(gè)4Mbps點(diǎn)到點(diǎn)鏈路，節(jié)點(diǎn)間距離為5000km，數(shù)據(jù)幀大小為1KB，設(shè)計(jì)一個(gè)選擇性重傳的滑動(dòng)窗口協(xié)議（SelectiveRepeat,SR),在管道滿(mǎn)載的情況下，最少需要多少位作為序號(hào)？（信號(hào)的傳播速率為3×m/s）（6分）假設(shè)要在網(wǎng)絡(luò)上傳送1MB的文件。設(shè)分組長(zhǎng)度為1KB，往返時(shí)延為40ms，網(wǎng)絡(luò)帶寬為10Mbps。數(shù)據(jù)發(fā)送前與接收方建立連接的時(shí)間為兩倍的往返時(shí)延。試計(jì)算以下兩種情況下傳輸文件所需的時(shí)間（即接收方收到該文件的最后一個(gè)比特所需的時(shí)間）。（1）數(shù)據(jù)可以被連續(xù)發(fā)送；（2）每發(fā)送完一個(gè)分組后等待一個(gè)往返時(shí)延的時(shí)間才能再次發(fā)送下一個(gè)分組（4分）某網(wǎng)絡(luò)采用RIP路由協(xié)議，當(dāng)路由器A收到從路由器C發(fā)來(lái)的距離向量時(shí)，試問(wèn)A的路由表將發(fā)生怎樣的變化？試畫(huà)出路由器A新的路由表。A的路由表C發(fā)來(lái)的距離向量表目的網(wǎng)絡(luò)距離下一跳路由器目的網(wǎng)絡(luò)距離Net10直接連接Net110Net26BNet22Net34CNet38Net510ANet45Net67CNet61Net75DNet82

=3\*ROMANIII.軟件工程（共30分）單項(xiàng)選擇題（每小題1分，共5分）1、瀑布模型是一種（）。A.軟件產(chǎn)品模型B.軟件過(guò)程模型C.軟件項(xiàng)目模型D.軟件測(cè)試模型軟件需求開(kāi)發(fā)階段包括多種活動(dòng)，不屬于需求開(kāi)發(fā)活動(dòng)的是（）。A.軟件需求獲取B.軟件需求分析建模C.軟件需求定義與評(píng)審D.軟件需求管理模塊設(shè)計(jì)中，最差的內(nèi)聚類(lèi)型是（）。A.功能內(nèi)聚B.邏輯內(nèi)聚C.信息內(nèi)聚D.巧合內(nèi)聚軟件集成測(cè)試主要依據(jù)的文檔應(yīng)該是（）。A.軟件需求規(guī)格說(shuō)明書(shū)B(niǎo).軟件工作分解結(jié)構(gòu)C.軟件概要設(shè)計(jì)說(shuō)明書(shū)D.軟件詳細(xì)設(shè)計(jì)說(shuō)明書(shū)軟件項(xiàng)目管理中，用于實(shí)施進(jìn)度控制的圖是（）。A.Gantt圖B.IPO圖C.管理圖D.系統(tǒng)流程圖判斷題（每小題1分，共5分。如果正確，用“√”表示，否則，用“×”表示）軟件配置管理是一種保護(hù)傘活動(dòng)，它貫穿于整個(gè)軟件生存周期過(guò)程，用于控制變更。（）若對(duì)象a是對(duì)象b的一個(gè)組成部分，則對(duì)象a是整體對(duì)象，對(duì)象b是部分對(duì)象。（）3.邊界值分析法是一種常用的白盒測(cè)試的測(cè)試用例設(shè)計(jì)方法。（）4.在使用SD的變換分析方法建立系統(tǒng)模塊結(jié)構(gòu)時(shí)，模塊結(jié)構(gòu)的主模塊應(yīng)是由DFD的變換中心部分映射而來(lái)。（）5.MVC架構(gòu)是一種典型的軟件體系結(jié)構(gòu)，它主要包括三部分，即表示層、控制邏輯層和數(shù)據(jù)層。（）問(wèn)答題（每小題4分，共12分）1.什么是面向?qū)ο笙到y(tǒng)中的消息？一個(gè)消息應(yīng)包括哪幾部分？2.什么是基本路徑覆蓋測(cè)試？它應(yīng)滿(mǎn)足哪一種測(cè)試覆蓋準(zhǔn)則？3.什么是CMMI？在CMMI連續(xù)式表示中把能力等級(jí)劃分為哪幾個(gè)等級(jí)？建模題（共8分）一個(gè)簡(jiǎn)化的教學(xué)管理系統(tǒng)的描述如下：●與學(xué)生相關(guān)的活動(dòng)：

學(xué)生向系統(tǒng)提出注冊(cè)申請(qǐng)

系統(tǒng)向?qū)W生反饋學(xué)籍通知

系統(tǒng)向部分優(yōu)秀學(xué)生發(fā)出獎(jiǎng)勵(lì)通知●與教務(wù)處相關(guān)的活動(dòng)：

教務(wù)處將學(xué)籍審批結(jié)果輸入系統(tǒng)

系統(tǒng)向教務(wù)處顯示統(tǒng)計(jì)報(bào)告

教務(wù)處向系統(tǒng)提供獎(jiǎng)勵(lì)憑證●與系教學(xué)辦相關(guān)的活動(dòng)：

系統(tǒng)顯示學(xué)籍報(bào)告管理情形

系教學(xué)辦將學(xué)籍處理意見(jiàn)和獎(jiǎng)勵(lì)建議輸入系統(tǒng)●與教師相關(guān)的活動(dòng)：

系統(tǒng)將教學(xué)安排通知教師

教師將學(xué)生成績(jī)輸入系統(tǒng)試回答：1.（3分）根據(jù)以上描述，畫(huà)出該系統(tǒng)的頂層數(shù)據(jù)流圖；2.（2分）寫(xiě)出至少兩個(gè)相關(guān)的數(shù)據(jù)文件；3.（3分）如果系統(tǒng)的主要功能是注冊(cè)管理、學(xué)籍管理、成績(jī)管理、獎(jiǎng)勵(lì)管理，請(qǐng)畫(huà)出系統(tǒng)的第一層數(shù)據(jù)流圖。Ⅳ.人工智能原理（共30分）單項(xiàng)選擇題（每小題2分，共8分）1.建造一個(gè)多層神經(jīng)網(wǎng)絡(luò)，可實(shí)現(xiàn)逼近一個(gè)任意的（）。A.函數(shù)B.連續(xù)函數(shù)C.只有有限個(gè)間斷點(diǎn)的連續(xù)函數(shù)2.支持向量機(jī)（SVM）是一種（）算法。A.小樣本下的統(tǒng)計(jì)機(jī)器學(xué)習(xí)B.大樣本下的統(tǒng)計(jì)機(jī)器學(xué)習(xí)C.大樣本下的實(shí)例機(jī)器學(xué)習(xí)3.非單調(diào)推理是由于處理（）問(wèn)題提出來(lái)的。A.邏輯矛盾B.知識(shí)不完全C.知識(shí)表示4.在MYCIN專(zhuān)家系統(tǒng)中，已知證據(jù)（事實(shí)）A和B的不確定性度量分別為CF(A)=0.3和CF(B)=0.5，那么證據(jù)A∧B的不確定性度量CF(A∧B)=().A.0.5B.0.3C.0.15證明題（共10分）使用線(xiàn)性歸結(jié)法（resolution)證明A1A2A3→B其中A1=（x)｛(D(X)E(X))→(y)(F(x,y)H(y))｝A2=(x)｛D(x)G(x)(y)(F(x,y)→G(y))}A3=(x)(E(x)G(x))B=(x)(H(x)G(x))問(wèn)答題（每小題4分，共12分）1.對(duì)一類(lèi)問(wèn)題求解來(lái)說(shuō)，若有部分案例（case),而有較多的推理規(guī)則（知識(shí)），試問(wèn)如何建造一個(gè)由基于案例推理和規(guī)則推理相結(jié)合的求解系統(tǒng)，以使推理效率高又能求得問(wèn)題的解。2.已知北京市地圖以及地圖中任意兩點(diǎn)A和B的最短路徑算法，試給出一種計(jì)算A和B最短路徑的啟發(fā)式算法。3.給出分類(lèi)問(wèn)題的描述，進(jìn)而說(shuō)明用于分類(lèi)的有監(jiān)督機(jī)器學(xué)習(xí)方法與無(wú)監(jiān)督機(jī)器學(xué)習(xí)方法。1絕密★啟用前2013年同等學(xué)力人員申請(qǐng)碩士學(xué)位學(xué)科綜合水平全國(guó)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)試卷第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程第二部分專(zhuān)業(yè)知識(shí)課程Ⅰ．計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)Ⅱ．計(jì)算機(jī)網(wǎng)絡(luò)Ⅲ．軟件工程Ⅳ．人工智能原理Ⅴ．計(jì)算機(jī)圖形學(xué)考生須知1.本試卷滿(mǎn)分為100分，包括數(shù)學(xué)基礎(chǔ)課程和專(zhuān)業(yè)知識(shí)課程兩部分。數(shù)學(xué)基礎(chǔ)課程滿(mǎn)分為40分，每位考生必答；專(zhuān)業(yè)知識(shí)課程包括五門(mén)課程，每門(mén)課程滿(mǎn)分為30分，考生須從中任選2門(mén)作答，多選者只按前選課程計(jì)分。2.考生務(wù)必將本人考號(hào)最后兩位數(shù)字填寫(xiě)在本頁(yè)右上角方框內(nèi)。3.考生一律用藍(lán)色或黑色墨水筆在答題紙指定位置上按規(guī)定要求作答，未做在指定位置上的答案一律無(wú)效。4.監(jiān)考員收卷時(shí)，考生須配合監(jiān)考員驗(yàn)收，并請(qǐng)監(jiān)考員在準(zhǔn)考證上簽字（作為考生交卷的憑據(jù)），否則，若發(fā)生答卷遺失，責(zé)任由考生自負(fù)。2第一部分?jǐn)?shù)學(xué)基礎(chǔ)課程（共40分）一、用邏輯符號(hào)表達(dá)下列語(yǔ)句（每小題2分，共4分）1．發(fā)光的不都是金子。（注：給出兩種表達(dá)，一種用存在量詞，另一種用全稱(chēng)量詞）2．有些大學(xué)生不尊敬老人。二、填空題（第1小題2分，第2到第6小題每空2分，共16分）1．設(shè)集合A有100個(gè)元素，則A有個(gè)子集。其中有個(gè)子集其元素個(gè)數(shù)為奇數(shù)。2．任意一個(gè)圖中度數(shù)是奇數(shù)的頂點(diǎn)個(gè)數(shù)一定是。3．如果四對(duì)夫妻圍圓桌就座，沒(méi)有任何限制條件，共有種不同的座法；如果這四對(duì)夫妻中的四個(gè)男士和四個(gè)女士排成一排，要求男女交替，則有種不同的排法;如果這四對(duì)夫妻圍圓桌就座,要求夫妻相鄰的座法有種。4．設(shè)G(V,E)是頂點(diǎn)集為V、邊集為E的圖。令1()()||vVDGdvV，則用D(G)和|V|把|E|表示出來(lái)的表達(dá)式是。這里d(v)是頂點(diǎn)v的度數(shù)（或次數(shù)），|V|和|E|分別是V和E中所含元素的個(gè)數(shù)。5．設(shè)Q是一個(gè)有理數(shù)集。對(duì)任意的a,bQ，定義二元運(yùn)算ab(ab)/2，則Q關(guān)于運(yùn)算的單位元是，其中“”是有理數(shù)中通常的乘法運(yùn)算。6．把6個(gè)相同的球分到3個(gè)同學(xué)手里，允許有的同學(xué)未分配到球的情況出現(xiàn)，則有種不同的分法。三、計(jì)算題（第1小題3分，第2小題4分，第3小題6分，共13分）1．定義P↑Q=(P∧Q)，試僅用與非聯(lián)結(jié)詞↑分別表示出（1）P（2）P∧Q（3）PQ均要求結(jié)果簡(jiǎn)潔。2．設(shè)a、b、c、d這四個(gè)元素的全排列中不允許出現(xiàn)ac和bd的排列數(shù)。3．用紅、黃、藍(lán)色對(duì)1n的棋盤(pán)方格涂色，設(shè)涂紅色方格的個(gè)數(shù)是偶數(shù)且至少有一個(gè)方格涂黃色的涂色方法數(shù)為nh（n是正整數(shù)）。（1）試確定nh的指數(shù)型生成函數(shù)；（2）求nh。3四、證明題（第1小題4分，第2小題3分，共7分）1．給出命題：“對(duì)于集合A上的任意關(guān)系R，如果R是對(duì)稱(chēng)的和傳遞的，則R一定是自反的?！比裘}正確，則給出完整證明；若命題錯(cuò)誤，則指出錯(cuò)誤所在，并在集合{1,2,3}上構(gòu)造一個(gè)關(guān)系R1（反例）使得R1是對(duì)稱(chēng)的和傳遞的，但不是自反的。2．設(shè)A為包含n個(gè)元素的有限集，R是A上的關(guān)系，則必存在s和t，使得stRR，且202n≤st≤。4第二部分專(zhuān)業(yè)知識(shí)課程Ⅰ．計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)（共30分）一、選擇題（每小題1分，共5分）某大型計(jì)算機(jī)有如下三種通道工作方式：A．字節(jié)多路通道B．?dāng)?shù)組多路通道C．選擇通道對(duì)于下面5種情況，選擇對(duì)應(yīng)的A或B或C填入括號(hào)中。1．低速外部設(shè)備通常采用（）方式2．使用硬件元件最少的是（）方式3．使用硬件元件最多的是（）方式4．通常只有一個(gè)磁盤(pán)工作，采用（）方式5．經(jīng)常需要多個(gè)磁盤(pán)同時(shí)工作，采用（）方式二、填空題（每空1分，共10分）1．采用2-4擴(kuò)展編碼法設(shè)計(jì)指令操作碼，最多能設(shè)計(jì)出（）條指令，其中操作碼長(zhǎng)度為2位的指令（）條，操作碼長(zhǎng)度為4位的指令（）條。2．用1M×8b（二進(jìn)制位）的靜態(tài)存儲(chǔ)芯片構(gòu)成一個(gè)4M×32b的存儲(chǔ)器，需要存儲(chǔ)器芯片（）片，各存儲(chǔ)芯片的地址有（）位，該靜態(tài)存儲(chǔ)器的地址共有（）位。3．在一個(gè)存儲(chǔ)系統(tǒng)中，主存儲(chǔ)器的訪(fǎng)問(wèn)周期、存儲(chǔ)容量和單位容量?jī)r(jià)格分別為30ns、2GB和0.1元/MB；而Cache的訪(fǎng)問(wèn)周期、存儲(chǔ)容量和單位容量?jī)r(jià)格分別為5ns、16MB和1元/MB，Cache的命中率為0.98。則這個(gè)存儲(chǔ)系統(tǒng)的訪(fǎng)問(wèn)周期是（），存儲(chǔ)容量是（），單位容量的價(jià)格是（），這個(gè)存儲(chǔ)系統(tǒng)的訪(fǎng)問(wèn)效率是（）。5三、計(jì)算題（共15分）1．（每小題2分，共8分）一個(gè)由20000條指令組成的程序，在一臺(tái)工作主頻為2GHz，采用5段流水線(xiàn)的雙發(fā)射處理機(jī)上執(zhí)行，忽略由于轉(zhuǎn)移指令和亂序執(zhí)行等造成的損失。試計(jì)算：（1）相對(duì)于同樣工作主頻的非流水線(xiàn)單發(fā)射處理機(jī)的加速比。（2）指令流水線(xiàn)在執(zhí)行這個(gè)程序時(shí)的效率。（3）指令流水線(xiàn)在執(zhí)行這個(gè)程序時(shí)的吞吐率。（4）該處理機(jī)的峰值速度。2．（共7分）在一臺(tái)單流水線(xiàn)多操作部件處理機(jī)上執(zhí)行下面的程序P。取指令和指令譯碼各需要一個(gè)時(shí)鐘周期，執(zhí)行MOVE、ADD和MUL操作分別需要2個(gè)、3個(gè)和4個(gè)時(shí)鐘周期。每個(gè)操作都在第一個(gè)時(shí)鐘周期從通用寄存器中讀操作數(shù)，在最后一個(gè)時(shí)鐘周期把運(yùn)算結(jié)果寫(xiě)到通用寄存器中。程序P：k：MOVER1,R0；R1←（R0）k+1：MULR0,R2,R1；R0←（R2）×（R1）k+2：ADDR0,R2,R3；R0←（R2）＋（R3）（1）寫(xiě)出指令之間的所有數(shù)據(jù)相關(guān)（包括寫(xiě)讀相關(guān)、讀寫(xiě)相關(guān)和寫(xiě)寫(xiě)相關(guān)）。（2）在程序?qū)嶋H執(zhí)行過(guò)程中，有哪幾種數(shù)據(jù)相關(guān)會(huì)引起流水線(xiàn)停頓？分別停頓了幾個(gè)時(shí)鐘周期？（3）計(jì)算執(zhí)行完這3條指令共用了多少個(gè)時(shí)鐘周期。6Ⅱ．計(jì)算機(jī)網(wǎng)絡(luò)（共30分）一、填空題（每空1分，共6分）1．在網(wǎng)絡(luò)協(xié)議的三要素中，表示事件實(shí)現(xiàn)順序的詳細(xì)說(shuō)明；說(shuō)明需要發(fā)出何種控制信息及如何響應(yīng)。2．一個(gè)路由器的路由表有如下表項(xiàng)：目的網(wǎng)絡(luò)地址子網(wǎng)掩碼下一跳接口0接口1路由器ADefaultDefault路由器B若該路由收到一個(gè)分組，其目的地址為，路由器轉(zhuǎn)發(fā)的下一跳為。3．考慮在主機(jī)A和主機(jī)B之間建立一個(gè)TCP連接，若主機(jī)A向主機(jī)B連續(xù)發(fā)送兩個(gè)TCP報(bào)文段，第一個(gè)報(bào)文段的序號(hào)為200，第二個(gè)報(bào)文段的序號(hào)是1100，則第一個(gè)報(bào)文段中的數(shù)據(jù)為字節(jié)。若第一個(gè)報(bào)文段丟失，第二個(gè)報(bào)文段到達(dá)主機(jī)B，那么主機(jī)B發(fā)送的報(bào)文中確認(rèn)號(hào)為。4．在解析域名時(shí)，客戶(hù)端向本地域名服務(wù)器發(fā)出查詢(xún)請(qǐng)求，如果服務(wù)器不能回答該請(qǐng)求，就向其他域名服務(wù)器發(fā)出查詢(xún)請(qǐng)求，直到最終將查詢(xún)結(jié)果返回給客戶(hù)端。這種方式可稱(chēng)之為查詢(xún)。二、單項(xiàng)選擇題（每小題1分，共5分）1．以太網(wǎng)的爭(zhēng)用期是指（）。A．信號(hào)從線(xiàn)路一端傳輸?shù)搅硪欢说臅r(shí)間B．從數(shù)據(jù)發(fā)送完畢到收到應(yīng)答的時(shí)間C．相鄰兩個(gè)站之間的傳播時(shí)延D．總線(xiàn)兩端的兩個(gè)站之間的往返傳播時(shí)延2．在部署分層OSPF協(xié)議時(shí)，如果一個(gè)路由器同時(shí)連接兩個(gè)不同區(qū)域，其中一個(gè)是主干區(qū)域，則該路由器（）。A．是內(nèi)部路由器B．需要為每個(gè)區(qū)域單獨(dú)運(yùn)行最短路徑算法C．需要為每個(gè)區(qū)域單獨(dú)運(yùn)行距離向量算法D．需要維護(hù)一個(gè)統(tǒng)一的鏈路狀態(tài)數(shù)據(jù)庫(kù)3．某單位要新建一個(gè)可以連接16臺(tái)主機(jī)的網(wǎng)絡(luò)，并將其連入已有的內(nèi)部網(wǎng)中。如果該網(wǎng)絡(luò)采用劃分子網(wǎng)的方法，則子網(wǎng)掩碼為（）。A．52B．48C．40D．2474．IP分組在轉(zhuǎn)發(fā)過(guò)程中可能需要經(jīng)過(guò)多個(gè)網(wǎng)絡(luò)和路由器。在整個(gè)傳輸過(guò)程中，下列說(shuō)法正確的是（）。A．源MAC地址和目的MAC地址都可能發(fā)生變化。B．源IP地址和源MAC地址都不會(huì)發(fā)生變化。C．源IP地址和目的IP地址都可能發(fā)生變化。D．源IP地址不會(huì)發(fā)生變化，目的IP地址可能發(fā)生變化。5．一個(gè)公司的辦事處和部門(mén)分散在多個(gè)城市中，希望能夠利用Internet進(jìn)行通信，同時(shí)保證安全性，數(shù)據(jù)流量不會(huì)泄漏到公司各工作場(chǎng)所以外。為滿(mǎn)足該需求可以采用（）技術(shù)。A．PGPB．NATC．VPND．Proxy三、名詞解釋?zhuān)啃☆}2分，共4分）1．VLAN2．CIDR四、問(wèn)答和計(jì)算題（共15分）說(shuō)明：計(jì)算中使用以下簡(jiǎn)化數(shù)值：1G≈109；1M≈106；1K≈1031．（5分）兩臺(tái)主機(jī)之間通過(guò)長(zhǎng)距離網(wǎng)絡(luò)通信，彼此之間通過(guò)一條傳輸速率為1Gbps的信道相連。線(xiàn)路的單向傳播時(shí)延為10ms。分組（包括頭部和數(shù)據(jù)字段）長(zhǎng)度為1500字節(jié)。如果ACK分組很小，接收方收到一個(gè)分組后立即發(fā)送A