計(jì)算機(jī)專業(yè)(基礎(chǔ)綜合)-試卷14

計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）試卷(分：104.00，題時(shí)間90分鐘)一、單項(xiàng)擇(總題數(shù)：，數(shù)82.00)1.單項(xiàng)選擇1-40小題。下列每題給出的四個(gè)選項(xiàng)中，有一個(gè)選項(xiàng)是最符題目要求。__________________________________________________________________________________________2.在一個(gè)長(zhǎng)度n(n>1)的頭結(jié)點(diǎn)的單鏈表h，設(shè)有尾指針r(向尾結(jié))則執(zhí)()操作與鏈表的長(zhǎng)度有關(guān)。A.除單鏈表中的第一個(gè)元素B.除單鏈表中的最后一個(gè)元素√C.單鏈表第一個(gè)元素前插入一個(gè)新元素D.單鏈表最后一個(gè)元素后插入一個(gè)新元素執(zhí)行B時(shí)要找到尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針因此需遍歷該單鏈表，因此與鏈表的長(zhǎng)度有關(guān)。3.若用單鏈表來(lái)表隊(duì)列，則應(yīng)該選用)。A.尾指針的非循環(huán)鏈表B.尾指針的循環(huán)鏈表C.頭指針的非循環(huán)鏈表D.頭指針的循環(huán)鏈表

√設(shè)尾指針為TAIL，則通過TAIL可訪問隊(duì)尾，通過訪問隊(duì)頭。4.對(duì)于一個(gè)滿二叉，共有n個(gè)結(jié)點(diǎn)和m個(gè)葉子結(jié)點(diǎn)，度為h則()A.n=h+mB.h+m=2nC.m=h—1D.n=2

一1

√對(duì)于深度為h的二叉樹，一

+2+…+2-1m=2

。5.關(guān)于哈夫曼樹，列說(shuō)法正確的是).A.哈夫曼樹中。權(quán)值相同的葉子結(jié)點(diǎn)都在同一層上B.哈夫曼樹中，權(quán)值較大的葉子結(jié)點(diǎn)一般離根結(jié)點(diǎn)較遠(yuǎn)C.夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近√D.哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)作特殊處理哈夫曼編碼中不允許出現(xiàn)兩個(gè)字符編碼相同的情況，故。6.每棵樹都能唯一轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹，由樹轉(zhuǎn)換成的二叉樹中，一個(gè)結(jié)點(diǎn)N的左孩子是它在原樹對(duì)應(yīng)結(jié)點(diǎn)的()。A.左孩子B.右孩子C.鄰兄弟D.鄰兄弟

√7.已知8個(gè)數(shù)據(jù)元素(3476，45，1826，54，92，65)按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，則該樹的深度為()。A.4B.5C.6D.7

√根據(jù)二叉排序樹插入結(jié)點(diǎn)算法，將上述數(shù)據(jù)元素按照依次插入結(jié)點(diǎn)的方法構(gòu)造出一棵二叉排序樹后，該樹的最大層次為5故該樹的深度：勾58.下列敘述正確的數(shù)是()的平m路查找樹AVL(2)m=3的平m路查找樹23樹(3)m=2的平m路找樹的葉結(jié)點(diǎn)不一定在同一層(4)m階一樹的葉結(jié)點(diǎn)必須在同一(5)m階B樹是平衡m查找樹(6)平m查找樹不一定是B一樹

A.3B.4C.5D.6

√參見B-樹義。9.下列說(shuō)法正確的()A.何有向網(wǎng)絡(luò)(AOV一網(wǎng))拓?fù)渑判虻慕Y(jié)果是唯一的B.回路的圖不能進(jìn)行拓?fù)渑判颉藽.在AOE網(wǎng)一定只有一條關(guān)鍵路徑D.個(gè)正常的AOE中只能有一個(gè)源點(diǎn)、一小匯點(diǎn)和一條關(guān)鍵路徑拓?fù)渑判虻慕Y(jié)果不一定是唯一的；在中，關(guān)鍵路徑可以不止一條，故選B10.對(duì)意7個(gè)關(guān)鍵字進(jìn)行排序，至少要進(jìn)行)次關(guān)鍵字間的兩兩比較。A.13B.14C.15D.16

√任何一個(gè)借助于“比較”進(jìn)行排序的算法，在最壞情況下所需進(jìn)行的比較次數(shù)至少為：。11.一記錄的關(guān)鍵字為2550，15，35，80，85，20，40，36，其中含有5個(gè)長(zhǎng)度為的有序表，用歸并排序方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果是()。A.1525，35，50，20408085，36，70B.1525，35，50，80208540，70，36C.1525，50，35，80852036，40，70D.1525，35，50，80203640，70，85

√對(duì)5個(gè)度為2的有序表一趟歸并后得到兩個(gè)長(zhǎng)度為的有序表和一個(gè)長(zhǎng)度2有序表。故選A。12.完的計(jì)算機(jī)系統(tǒng)由)成。A.算器和控制器B.CPU主存儲(chǔ)器C.機(jī)和外部設(shè)備D.件系統(tǒng)和軟件系統(tǒng)

√完整的計(jì)算機(jī)系統(tǒng)由配套的硬件系統(tǒng)和軟件系統(tǒng)組成。13.真0原碼、反碼和補(bǔ)碼機(jī)器數(shù)形式下)。A.有正0負(fù)0種形式B.在原碼中有兩種形式，而在反碼、補(bǔ)碼機(jī)器數(shù)形式下只有一種形式C.在反碼中有兩種形式，而在原碼、補(bǔ)碼機(jī)器數(shù)形式下只有一種形式D.在補(bǔ)碼中有一種形式，而在反碼、原碼機(jī)器數(shù)形式下均有兩種形式√真值0在碼、反碼機(jī)器數(shù)形式下都有正負(fù)種形式，而在補(bǔ)碼機(jī)器數(shù)形式下只有一種形式。14.某點(diǎn)機(jī)字長(zhǎng)8位(含1位符號(hào))現(xiàn)該機(jī)中一個(gè)寄存器的內(nèi)容43H則將其算術(shù)左移一位、算術(shù)右移一位的結(jié)果分別為()。A.86H，B.果出錯(cuò)，21H

√C.果出錯(cuò)，A1HD.給出機(jī)器數(shù)形式，無(wú)法判斷雖然題中未給出機(jī)器數(shù)形式是原碼反碼還是補(bǔ)碼但由于寄存器中數(shù)據(jù)的符號(hào)位為即表示一個(gè)正數(shù)，故仍可進(jìn)行判斷；算術(shù)左移位時(shí)，符號(hào)位為0變，最高數(shù)值1丟，結(jié)果出錯(cuò)；算術(shù)右移1位時(shí)，符號(hào)位為0不，數(shù)值位最高位補(bǔ)0，結(jié)果為21H15.浮數(shù)加減運(yùn)算過程一般包括對(duì)階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判斷溢出等步驟。設(shè)浮點(diǎn)數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示，且位數(shù)分別為和7位含2位符號(hào)位若有兩個(gè)數(shù)X=／8則用浮點(diǎn)加法計(jì)算X+Y的最終結(jié)是(。A.001111100010

×29／32，Y=2

×

B.001110100010C.010000010001D.生溢出

√根據(jù)題意X可記為001110011101(分號(hào)前為階碼，號(hào)后為尾)Y記為001010010100首先對(duì)階，、階碼相減，00111—00101=00，111+11011=00，010(最高位進(jìn)位自然丟)可知X的階碼比Y階碼大2根據(jù)小階向大階看齊的原則將Y的階碼加2尾數(shù)右移2位得為001110000101尾數(shù)相加，即，11101+0000101=01，00010尾數(shù)相加結(jié)果符號(hào)位為01，故需行右規(guī)；規(guī)格化，將尾數(shù)右移1位，階碼加，X+Y為，000；00，，階碼符號(hào)位為01，說(shuō)明發(fā)生溢出。16.半體隨機(jī)存儲(chǔ)器的訪問速度與)有。A.儲(chǔ)芯片的存取周期B.儲(chǔ)芯片的容量大小C.訪問存儲(chǔ)單元的位置D.上都包括

√半導(dǎo)體隨機(jī)存儲(chǔ)器的訪問速度與存儲(chǔ)芯片的容量和存儲(chǔ)單元的位置無(wú)關(guān)，只取決于存儲(chǔ)芯片的存取周期，選A17.Cache常的寫回策略有寫直達(dá)法和寫回法。當(dāng)采用寫回法時(shí)，一個(gè)Cache數(shù)據(jù)塊在)時(shí)寫回主存。A.何一次寫操作數(shù)時(shí)B.一次寫操作數(shù)時(shí)C.據(jù)塊被換出時(shí)D.上都有可能

√寫直達(dá)法指寫操作數(shù)時(shí)既寫入寫入主存；寫回法指寫操作數(shù)時(shí)寫Cache不寫入主存，僅當(dāng)數(shù)據(jù)被替換出Cache時(shí)才寫回主存。18.主地址寄存器MAR的位數(shù)與下列哪個(gè)寄存器相同()。A.存數(shù)據(jù)寄存器MDRB.序計(jì)數(shù)器PCC.令寄存器IRD.加器AC

√主存地址寄存器MAR和程序計(jì)數(shù)PC的位數(shù)都取決于主存器的容量，二者位數(shù)相等，選B19.控存儲(chǔ)器使用EPROM構(gòu)的控制器是)。A.態(tài)微程序控制器B.態(tài)微程序控制器C.微程序控制器D.上都不對(duì)

√采用EPROM作控制存儲(chǔ)器，可以通過改變微指令和微程序來(lái)改變機(jī)器的指令系統(tǒng)，此時(shí)控制器又稱為動(dòng)態(tài)微程序控制器，選B20.下關(guān)于PCI總線的說(shuō)法中錯(cuò)誤的是()。A.PCI線采用集中式總線判優(yōu)控制方式B.PCI線是一種16的并行總線√C.PCI線具有自動(dòng)配置能力D.PCI線在PC中得到了廣泛的使用PCI線是一種32或的并行總線。21.某算機(jī)有8個(gè)主設(shè)備競(jìng)爭(zhēng)總線使用權(quán)使用鏈?zhǔn)秸?qǐng)求方式進(jìn)行總線判優(yōu)控制則該機(jī)為實(shí)現(xiàn)總線判優(yōu)控制需要的控制線數(shù)為()。A.3

√B.5C.16D.法確定鏈?zhǔn)秸?qǐng)求方式下，為實(shí)現(xiàn)總線判優(yōu)控制，需1總線請(qǐng)求線1根總線忙線1總線同意線，共3根控制線。

22.下說(shuō)法中錯(cuò)誤的是)A.一編址方式即把IO端口當(dāng)作主儲(chǔ)器的單元來(lái)分配地址B.一編址方式下不需要專門的O令C.一編址方式下指令系統(tǒng)的實(shí)現(xiàn)比單獨(dú)編址方式復(fù)雜√D.用統(tǒng)一編址方式會(huì)減少主存的編址空間統(tǒng)一編址方式下不需要專門的O指令，因而簡(jiǎn)化了指令系統(tǒng)，其指令系統(tǒng)的實(shí)現(xiàn)比單獨(dú)編址方式簡(jiǎn)單。23.活頭磁盤的尋道時(shí)間是指)。A.大尋道時(shí)間B.小尋道時(shí)間C.A、B和D.A、B平均值

√尋道時(shí)間又叫平均尋道時(shí)間，是指磁盤最大尋道時(shí)間和最小尋道時(shí)間的平均值。24.下選擇中，)是操作系統(tǒng)關(guān)心的主要問題。A.理計(jì)算機(jī)裸機(jī)B.計(jì)、提供用戶程序與計(jì)算機(jī)硬件資源的接口C.理計(jì)算機(jī)系統(tǒng)資源D.級(jí)程序設(shè)計(jì)語(yǔ)言的編譯器√D不是操作系統(tǒng)的功能。25.采用)會(huì)產(chǎn)生內(nèi)部碎片。A.頁(yè)式存儲(chǔ)管理B.段式存儲(chǔ)管理

√C.定分區(qū)式存儲(chǔ)管理D.頁(yè)式存儲(chǔ)管理分段式存儲(chǔ)管理會(huì)產(chǎn)生外部碎片。26.在作系統(tǒng)中，要對(duì)并發(fā)進(jìn)程進(jìn)行同步的原因是)。A.程必須在有限的時(shí)間內(nèi)完成B.程具有動(dòng)態(tài)性C.發(fā)進(jìn)程訪問共享資源√D.程具有結(jié)構(gòu)性為了相互協(xié)調(diào)的順序進(jìn)程訪問共享資源，必須提供同步和互斥機(jī)制。27.()是分段式虛擬存儲(chǔ)管理優(yōu)于分頁(yè)式虛擬存儲(chǔ)管理的方面。A.有內(nèi)零頭B.于處理在進(jìn)程執(zhí)行過程中堆棧尺寸的增長(zhǎng)問題C.于共享內(nèi)存中數(shù)據(jù)D.需將進(jìn)程的一部分調(diào)入內(nèi)存，進(jìn)程即可運(yùn)行√D分頁(yè)虛擬存儲(chǔ)管理也有此功能。28.在面四段描述中)錯(cuò)誤的。A.進(jìn)程A和進(jìn)程B臨界區(qū)上互斥，那么當(dāng)進(jìn)程A處于該臨界區(qū)時(shí)，它不能被進(jìn)程B打斷B.擬存儲(chǔ)管理中采用對(duì)換策略后，用戶進(jìn)程可使用的存儲(chǔ)空間似乎增加了C.擬存儲(chǔ)管理中的抖動(dòng)現(xiàn)象是指頁(yè)面置換時(shí)用于換頁(yè)的時(shí)間遠(yuǎn)多于執(zhí)行程序的時(shí)間D.程可以由程序、數(shù)據(jù)和進(jìn)程控制塊PCB)描進(jìn)程A在界去訪問是可以被B打斷的，但是由于互斥機(jī)制，進(jìn)不了臨界區(qū)的。29.存在磁盤上的文件)A.可隨機(jī)訪問，又可順序訪問√B.能隨機(jī)訪問C.能順序訪問D.須通過操作系統(tǒng)訪問根據(jù)文件物理結(jié)構(gòu)的不同，文件可以被隨機(jī)和順序訪問。30.文系統(tǒng)中，文件訪問控制信息存儲(chǔ)的合理位置是)。

√

A.件控制塊B.件分配表C.戶口令表D.統(tǒng)注冊(cè)表

√文件的訪問控制信息存儲(chǔ)在。31.在作系統(tǒng)中，，作是一種()。A.器指令B.統(tǒng)調(diào)用命令C.業(yè)控制命令D.級(jí)進(jìn)程通信原語(yǔ)

√PV操作是原子操作。32.()操作系統(tǒng)必須提供的功能。A.GUI(形用戶界面)B.進(jìn)程提供系統(tǒng)調(diào)用命令C.理中斷

√D.譯源程序中斷系統(tǒng)是操作系統(tǒng)運(yùn)行所需的硬件支撐，所以必須提供。33.磁和磁帶是兩種存儲(chǔ)介質(zhì)，他們的特點(diǎn)是)。A.者都是順序執(zhí)行的B.者都是隨機(jī)存取的C.盤是順序存取的，磁帶是隨機(jī)存取的D.帶是順序存取的，磁盤是隨機(jī)存取的√本題主要考查磁盤和磁帶的工作方式的區(qū)別。34.網(wǎng)是在以下)上實(shí)現(xiàn)不同網(wǎng)絡(luò)互聯(lián)的設(shè)備。A.理層B.據(jù)鏈路層C.絡(luò)層D.輸層

√網(wǎng)橋是數(shù)據(jù)鏈路層設(shè)備。35.一數(shù)據(jù)編碼的海明距是，那么使用這種編碼最多可以糾正()個(gè)錯(cuò)誤A.0B.1C.2D.3

√為了糾正d個(gè)誤，需要使用距離為的碼方案，所以答案是3個(gè)。36.在個(gè)HDLC幀的數(shù)據(jù)中，如果出現(xiàn)了000111111011這的流，請(qǐng)問發(fā)送到信道上它將會(huì)變成)。A.0001111110110B.0001111111011C.0001111101011D.0000111111011

√HDLC采了比特填充法來(lái)實(shí)現(xiàn)鏈路層的透明傳輸，如果在數(shù)據(jù)流中發(fā)現(xiàn)了連續(xù)的5“1就在其后面加一個(gè)“0，所以C是正確答案。37.以網(wǎng)交換機(jī)進(jìn)行轉(zhuǎn)發(fā)決策時(shí)使用的PDU地是()A.的物理地址B.的IP地C.物理地址D.源IP地

√以太網(wǎng)交換機(jī)是數(shù)據(jù)鏈路層設(shè)備，它的轉(zhuǎn)發(fā)決策是依據(jù)的目的物理地址。

38.一路由器的路由表中有以下幾項(xiàng)CIDR)：發(fā)給()。A.口0

請(qǐng)問當(dāng)目的地址為．146．63．127分組將會(huì)被B.口1

√C.口2D.口0和接口1從掩碼上看第一項(xiàng)和第二項(xiàng)都可以，而路由器會(huì)選擇匹配位數(shù)最多的項(xiàng)目發(fā)送，所以這里應(yīng)當(dāng)選擇第二項(xiàng)的端口來(lái)發(fā)送分組，即接口1。39.假一個(gè)連接的最大數(shù)據(jù)段長(zhǎng)度為2KB，TCP的閥值64KB如果這時(shí)候傳輸發(fā)生了超時(shí)那么新的閥值為()。A.32KBB.63KBC.128KBD.2KB

√當(dāng)發(fā)生了超時(shí)的情況下，TCP的閥值將會(huì)減半。40.如在TCP連接中有一方發(fā)送了組，并且收到了回復(fù)，那么它將)。A.可以發(fā)送數(shù)據(jù)，也不可以接收數(shù)據(jù)B.以發(fā)送數(shù)據(jù)，不可以接收數(shù)據(jù)C.可以發(fā)送數(shù)據(jù)，可以接收數(shù)據(jù)√D.接馬上斷開TCP供了一個(gè)全雙工的連接一方希望斷開連接時(shí)需要發(fā)送FIN分組另一方仍然可以發(fā)送數(shù)據(jù)。41.下的應(yīng)用層協(xié)議中，)采用UDP傳的。A.SMTPB.DNSC.HTTPD.FTP

√DNS采用UDP傳輸?shù)?，而其他的三?xiàng)都使用了TCP二、綜合用(總題數(shù)：8，數(shù)22.00)42.合應(yīng)用題41-47小題。__________________________________________________________________________________________43.已二叉樹采用二叉鏈表方式存放要求返回二叉樹后序遍歷訪問的第一個(gè)結(jié)點(diǎn)是否可不用遞歸且不用棧來(lái)完成?簡(jiǎn)述原因。__________________________________________________________________________________________正確答案：(確答案：可以。原因：后序遍歷的順序是“左子樹一右子樹一根結(jié)點(diǎn)”。因此，二叉樹最左下的葉子結(jié)點(diǎn)是遍歷的第一個(gè)結(jié)點(diǎn)下面的語(yǔ)句段說(shuō)明了這一過程二叉樹根結(jié)點(diǎn)的指針if(p!一null){while(p一lchild!=nuUllp一>rchild!=null){while(p>lehild!=null)p=p一lchildif(p->rehild!=null)p=p一rehild；}}return(p)／／返回后序序列第一個(gè)結(jié)點(diǎn)的指針44.設(shè)一個(gè)雙向鏈表h每個(gè)結(jié)點(diǎn)中除有prior，data和next三個(gè)域外，還一個(gè)訪問頻度域freq，在鏈表被起用之前，每個(gè)結(jié)點(diǎn)中的域被初始化為零。每當(dāng)進(jìn)行LocateNode(h，x)運(yùn)時(shí)，令元素值為x的點(diǎn)中freq域的值加一并調(diào)整表中結(jié)點(diǎn)的次序使其按訪問頻度的遞減序列排序以便使被頻繁訪問的結(jié)點(diǎn)總靠近表頭，試寫一符合上述要求的運(yùn)算的算法。__________________________________________________________________________________________正確答案(確答案：DLinkList類型的定義中添加freq(int類)給該域初始化0。每次查找到一個(gè)結(jié)點(diǎn)*P時(shí)，使其freq域增再在結(jié)點(diǎn)的前面找到一個(gè)結(jié)點(diǎn)它或是頭結(jié)點(diǎn)或是滿足q->freq>=p->freq然后刪除*P點(diǎn)，使其插入到*q結(jié)點(diǎn)之后。算法描述如下：intLocateNode(DLinkList*hx)DLinkList*p=h一while(p!=NULL＆p->data!=x)p=p>)45.寫單總線結(jié)構(gòu)計(jì)算機(jī)中指令)VER1R2(含義是將寄器R1內(nèi)容寫入寄存器R2中)的操作步驟。

__________________________________________________________________________________________正確答案：確答案：操作步驟如下：第一步，送指令地址。將PC的送MAR。PC→MAR二步，計(jì)算下一條指令的地址。PC加送PC。PC+1→PC第三步，讀人指令。把存儲(chǔ)器中讀出來(lái)的指令經(jīng)MDR送入IR中。DBUSMDRIR第四步，送數(shù)據(jù)。R2)某計(jì)算機(jī)系統(tǒng)的內(nèi)存儲(chǔ)器由(2ache和主構(gòu)成的存取周期45納秒的存取周期200納秒。已知在一段給定的時(shí)間內(nèi)，CPU共訪內(nèi)存次，其中訪問主存。問：（分?jǐn)?shù)：(1).Cache命中率是多少?__________________________________________________________________________________________正確答案：(確答案：CCache的命中h=Nc／(Nc+Nm)=(4500--340)4500=0．92=929／5)(2).CPU訪內(nèi)存的平均時(shí)間是多少納秒?__________________________________________________________________________________________正確答案(確答案：CCPU訪存的平均時(shí)間Ta=h*Tc+(1-h)*Tm=092×45+(1一0．92)×200=57．(3).Cache一存系統(tǒng)的效率是多少__________________________________________________________________________________________正確答案：(確答案：CCache一主存統(tǒng)的效率e=Tc／57．4=0．78=78％(4).如Cache為8，主存16塊，分別采用三種方式映射主存的第9塊到Cache中什么位置寫出值)?__________________________________________________________________________________________正確答案：確答案：全相聯(lián)方式：8行中的任意行，tag=1001直接方式：中的第1行，tag=1組相聯(lián)方式：第1組任意行，46.P—V作實(shí)現(xiàn)寫優(yōu)先讀者一寫者問題。__________________________________________________________________________________________正確答案：(確答案：Semaphoremutex=1；／讀文件計(jì)數(shù)的互斥Semaphorewrite=1；／／寫互斥Semaphores=1；／／用于實(shí)現(xiàn)“寫優(yōu)先”count=0；{while(1){p(s)；p(mutex)；if(count==0)p(write)／／當(dāng)?shù)谝粋€(gè)讀者讀文件時(shí)，阻止寫者寫：；讀文件)(