計算機專業(yè)(基礎綜合)-試卷1

計算機專業(yè)（基礎綜合）-卷1(分：104.00，題時間90分鐘)一、單項擇(總題數(shù)：，數(shù)82.00)1.單項選擇1-40小題。下列每題給出的四個選項中，有一個選項是最符題目要求。__________________________________________________________________________________________2.堆的邏輯結(jié)構(gòu)是)。A.性結(jié)構(gòu)B.形結(jié)構(gòu)C.狀結(jié)構(gòu)D.組

√堆是一種經(jīng)過排序的樹形數(shù)據(jù)結(jié)構(gòu)，每個結(jié)點都有一個值。通常我們所說的堆是指二叉堆。堆的特點是根結(jié)點的值最小(最大)且根結(jié)點的兩個子樹也是一個堆。3.循環(huán)隊列用數(shù)組A[0，1…m一1]放其元素值，已知其頭尾指針分別為front，rear，則其隊列元素個數(shù)為()。A.(rearfront+m)％mB.rear一front+1C.rear一frontD.frontrear

√數(shù)組下標從0開共m個元素，故隊列元素個數(shù)(rear—front+m)％m4.設森林M中有三棵樹，它們結(jié)點個數(shù)分別N1，N2N3，森林相對應的二叉樹上，根結(jié)點的右子樹上的結(jié)點個數(shù)為()。A.N1B.NI+N2C.N3D.N2+N3

√由森林和二叉樹的轉(zhuǎn)換關(guān)系可知，森林中第一棵樹的根結(jié)點轉(zhuǎn)換為二叉樹的根結(jié)點、其他結(jié)點變?yōu)槎鏄涞母Y(jié)點的左子樹上的結(jié)點，森林中第二和第三棵樹全部構(gòu)成二叉樹根結(jié)點的右子樹，故知根結(jié)點的右子樹上的結(jié)點個數(shù)為N2+N3故選D5.采用鄰接表存儲圖的廣度優(yōu)先遍歷算法類似于樹的)。A.根遍歷B.根遍歷C.根遍歷D.層次遍歷

√圖的深度優(yōu)先遍歷類似于樹的先序遍歷；圖的廣度優(yōu)先遍歷類似于樹的層次遍歷。6.已知一棵完全二樹的第6層(根為第1層有8葉結(jié)點，則完全二叉樹的結(jié)點個數(shù)最多是)。A.39B.52C.111D.119

√第6層時第6層共有32個點，當?shù)诹鶎拥淖詈?個結(jié)點為葉結(jié)點，其余24結(jié)點為非葉結(jié)點時完全二叉樹結(jié)點總數(shù)達最多，此時共有個結(jié)點；故C7.判斷有向圖是否在回路，除了可以利用拓撲排序外，還可以利用的是)。A.關(guān)鍵路徑的方法B.最短路徑的DUKSTRA方法C.度優(yōu)先遍歷算法D.度優(yōu)先遍歷算法

√本題考查判斷有向圖是否存在回路的基本方法：拓撲排序和深度優(yōu)先遍歷。

8.對于序(49，3865，97，76，13，27，50)非遞減方式排序，采用步長4希爾排序，第一次排序結(jié)果為()。A.(49，7665，13，27，509738)B.(13，2738，49，50，657697)C.(97，7665，50，49，382713)D.(49，1327，50，76，386597)

√由希爾排序的規(guī)則易知，步長為第一次排序是第1個元素和第5元素比較、小的放第元素所在位置，大的放第5個元素所在位置；以類推比較第2和第元素，第和第元素，第4和8個元素；故選D9.已知一個線性表38，25，74，6352，48)表長為，假定采用散列函數(shù)h(key)=key％7計算散列地址，并存儲在散列表中，若采用線性探測方法解決沖突，在該散列表上，進行等概率成功查找的平均查找長度為()。A.1．5B.1．7C.2．0D.2．3

√由散列函數(shù)畫出散列表后易知：38，，74，63，52，48找成功分別須要11，1，43次查找，故查找成功的平均查找長度=(1+1+2+1+4+3)／010.下關(guān)于無向連通圖特性的敘述中，正確的描述是)。．所有頂點的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點個數(shù)減1．至少有一個頂點的度為1A.有IB.有ⅡC.IⅡD.IⅢ

√參見無向連通圖的定義。I確，對于任意一條邊必然連接著兩個頂點即產(chǎn)生2個度，所以頂點度之和必為偶數(shù)；Ⅱ錯誤，邊數(shù)可能等于頂點個數(shù)減Ⅲ錯誤，無此特性。故A11.若求盡快地對序列進行穩(wěn)定的排序，應選擇)。A.速排序B.并排序C.泡排序D.排序

√A、，快速排序和堆排序是非穩(wěn)定排序。歸并排序和冒泡排序是穩(wěn)定的排序。歸并排序的時間復雜度為O(nlogn)冒泡排序的時間復雜度為O(n

2

)故選B12.浮運算尾數(shù)不是規(guī)格化數(shù)，執(zhí)行左規(guī)操作，即尾數(shù))。A.移一位，階碼加一B.移一位，階碼減一C.移一位，階碼加一D.移一位，階碼減一

√尾數(shù)左移一位，階碼減一即執(zhí)行左規(guī)；尾數(shù)右移一位，階碼加一即執(zhí)行右規(guī)。13.虛存儲器由兩級存儲器組成，它們是)。A.存一輔存

√B.Cache主存C.Cache輔存D.用寄存器一輔存虛擬存儲器的兩級存儲結(jié)構(gòu)即主存一輔存結(jié)構(gòu)，Cache一主存系統(tǒng)是解決存系統(tǒng)速度問題的。14.下關(guān)于計算機中指令和數(shù)據(jù)存放位置的敘述，正確的是)。A.令存放在內(nèi)存中，數(shù)據(jù)存放在外存中B.令和數(shù)據(jù)任何時候都存放在內(nèi)存中C.令和數(shù)據(jù)任何時候都存放在外存中

D.序啟動前，指令和數(shù)據(jù)存放在外存中，啟動后指令和數(shù)據(jù)存放在內(nèi)存中√指令和數(shù)據(jù)在程序啟動之前都放在外存中，只有當程序啟動后才調(diào)入內(nèi)存。15.下說法正確的是)A.ROM用刷新，但集成度比動態(tài)RAM，斷電后存儲內(nèi)容消失B.導體RAM信息可讀可寫，且斷電后仍能保持記憶C.DRAM和SRAM儲信息都是易失性存儲器，斷電后存儲信息均消失√D.DRAM屬非易失性存儲器，而屬易失性存儲器A錯，ROM電后信息不丟失。B錯，RAM斷電后信息丟失。錯，DRAM和SRAM屬于易失性存儲器。16.在列信息中，與Cache命率無關(guān)的是)。A.存的存儲時間B.的大小C.Cache組織方式D.Cache容量

√塊大小，Cache織方式和容量都和Cache命中率有關(guān)，而主存存儲時間與命中率無關(guān)。17.某算機指令系統(tǒng)采用定長操作碼指令格式，操作碼位數(shù)為8位則其指令數(shù)最多為()。A.64B.128C.256√D.32操作碼采用固定長度方案，操作碼位數(shù)為，指令數(shù)最多為2

8

=256條。18.堆尋址方式中，設A為通用寄存器，為棧指示器，為SP指示的堆棧頂單元，如果進棧操作的動作是(A)→(SP)－SP，么出棧操作為)A.(SP)+1SP，Map→(A)√B.Map→(SP)+1→C.(SP)1→SP，→(A)D.Map→(A)(SP)－1→SP進棧是先存數(shù)再sP減一，故出棧是SP加一再取數(shù)。故A19.操控制器的功能是)A.生時序信號B.主存中取出一條指令C.成指令操作碼的編譯D.主存中取出一條指令，完成指令操作碼的編譯，產(chǎn)生有關(guān)操作控制信號√控制器是計算機的指揮中心責定執(zhí)行程序的順序出行指令時機器各部件需要的操作控制命令，由程序計數(shù)器、指令寄存器、指令譯碼器、時序產(chǎn)生器和操作控制器組成，完成協(xié)調(diào)和指揮整個計算機系統(tǒng)的操作?？刂破鞯墓δ苤饕校孩購膬?nèi)存中取出一條指令，并指出下一條指令在內(nèi)存中位置。②對指令進行譯碼或測試，并產(chǎn)生相應的操作控制信號，以便啟動規(guī)定的動作。③指揮并控制CPU、內(nèi)存和輸入／輸出設備之間數(shù)據(jù)流動的方向。20.若盤的轉(zhuǎn)速提高一倍，則)。A.均存取時間減半B.均尋道時間減半C.儲密度可以提高一倍D.均旋轉(zhuǎn)延遲時間減半√平均存取時間一尋道時間+轉(zhuǎn)延遲時間+數(shù)據(jù)傳輸替換間，尋道時間為磁頭移動到指定磁道所需時間；旋轉(zhuǎn)延遲時間指要讀寫的扇區(qū)旋轉(zhuǎn)到磁頭下方所需要的時間；數(shù)據(jù)傳輸時間指傳輸一個扇區(qū)的時間。磁盤尋道時間一般為510ms，旋轉(zhuǎn)延遲時間大約為46ms數(shù)據(jù)傳輸時間相對于前兩者來說非常短。當磁盤轉(zhuǎn)速提高一倍時，旋轉(zhuǎn)延遲時間和數(shù)據(jù)傳輸時間減半，尋道時間不變，A、。又存儲密度與磁盤轉(zhuǎn)速無關(guān)，故C錯21.下陳述中正確的是)A.在DMA周內(nèi)，CPU能執(zhí)行程序。

B.斷發(fā)生時，CPU首先執(zhí)行人棧指令將程序計數(shù)器的內(nèi)容保護起來。C.DMA送方式中，DMAC每送一個數(shù)據(jù)就竊取一個指令周期。D.入輸出操作的最終目的是要實現(xiàn)CPU與外設之間的據(jù)傳輸?！藺錯DMA周期內(nèi)CPU然可以執(zhí)行程序。B，對于單重中斷發(fā)生時首先執(zhí)行中斷周期，其順序為中斷響應、關(guān)中斷、程序斷點(PC)進棧、向量址送PC22.在立編址方式下，存儲設備和I／O備是)區(qū)分的。A.同地址代碼B.同指令或不同的控制信號√C.同的地址總線D.上都不對獨立編址方式下對IO備的操作使用單獨的I／O令來完成。故可用不同的指令來區(qū)分是存儲設備還是IO設備。23.顯器的灰度是指)A.度B.示字符的清晰程度C.示器中光點亮暗的層次級別√D.示器的色彩度A錯，灰度非亮度。B，清晰度由分辨率決定。錯，灰度不是色彩度。確，灰度指每個像素點的亮暗級別如用8位示則灰度值可取0～25524.在作系統(tǒng)層次結(jié)構(gòu)中，)操作系統(tǒng)的核心部分，它位于最內(nèi)層。A.儲管理B.理器管理C.備管理D.業(yè)管理

√處理器管理主要有兩項工作：中斷處理和處理器調(diào)度。處理器管理是操作系統(tǒng)的核心部分。25.在時操作系統(tǒng)中，進程通常采用)算。A.來先服務B.高優(yōu)先級C.間片輪轉(zhuǎn)D.機

√分時操作系統(tǒng)將系統(tǒng)處理機時間與內(nèi)存空間進行時間上的分割，每個時間段稱為一個時間片，每個用戶依次輪流使用時間片。由于時間間隔很短，每個用戶的感覺就像他獨占計算機一樣。26.在個單處理器系統(tǒng)中，存在3個進程，最多有幾個進程處于就緒隊列)。A.0B.1C.2D.3

√由于是單處理器，故每個時刻只能有一個進程處于運行狀態(tài)，其他進程只能處于就緒狀態(tài)或阻塞狀態(tài)，故最多有2個程處于就緒隊列。27.某統(tǒng)采用非搶戰(zhàn)短作業(yè)優(yōu)先的調(diào)度算法，現(xiàn)有作業(yè)序列，作業(yè)(交時間8：，行時1．5小時)作業(yè)二(交時間830運行時間8時作業(yè)三交時間9：00，運行時間1小時作業(yè)四(交時間9：30，運行時間0．3)，其平均帶權(quán)周轉(zhuǎn)時間為)A.2．6B.3

√C.5．5D.6．228.()是從磁盤移動臂當前位置開始沿著臂的移動方向去選擇離當前移動臂最近的那個柱面的訪問者，若沿臂的移動方向無訪問請求時，就改變臂的移動方向再選擇。A.來先服務調(diào)度算法

B.短尋找時間優(yōu)先調(diào)度算法C.梯調(diào)度算法

√D.環(huán)掃描調(diào)度算法掃描算法(SCAN)可類似為按照樓層順序依次服務請求，它讓電梯在最底層和最頂層之間連續(xù)往返運行，在運行過程中響應處于電梯運行方向相同的各樓層上的請求。在這個算法中，每個電梯響應乘客請求使乘客獲得服務的次序是由其發(fā)出請求的乘客的位置與當前電梯位置之間的距離來決定的，所有的與電梯運行方向相同的乘客的請求在一次電梯向上運行或向下運行的過程中完成。29.虛存儲器技術(shù)是基于程序的)特。A.算機的高速性B.容量的內(nèi)存C.環(huán)性原理D.部性原理

√虛擬存儲器技術(shù)的原理是程序的局部性原理，它的實現(xiàn)需要軟硬件的共同支持。30.某程代碼頁在頁框中固定不換出，數(shù)據(jù)頁在缺頁時換頁，每頁大小為。當前正在執(zhí)行一條指令，其語義為：從數(shù)據(jù)頁讀四個字節(jié)并以此為地址從數(shù)據(jù)頁讀另4個字節(jié)到寄存器中，則缺頁次數(shù)最多是()次。A.1B.2C.3D.4

√每次讀取的4個節(jié)可能不在同一頁中。31.可定位內(nèi)存分區(qū)的目的為了)。A.決碎片問題

√B.于多作業(yè)共享內(nèi)存C.便回收空閑區(qū)D.脫用戶干預32.I／O備控制的發(fā)展過程中，最主要的推動因素是)A.高資源利用率B.高系統(tǒng)吞吐量C.高IO設備與的行操作程度D.少主機對IO制的干預√33.下協(xié)議中，可以將IP地址轉(zhuǎn)化為MAC地址的是()A.RARPB.ARPC.DNSD.ICMP

√ARP議將IP址轉(zhuǎn)換為MAC址，RARP協(xié)將MAC地址轉(zhuǎn)換為IP地址。34.FCPIP模型由以下層次構(gòu)成)A.理層、數(shù)據(jù)鏈路層、網(wǎng)絡層、傳輸層、會話層、表示層、應用層B.絡接口層、互聯(lián)網(wǎng)層、傳輸層、應用層√C.理層、數(shù)據(jù)鏈路層、網(wǎng)絡層、傳輸層、應用層D.域網(wǎng)層、廣域網(wǎng)層、互聯(lián)網(wǎng)層A屬于OSI的7模型。35.下關(guān)于奈氏準則和香農(nóng)公式說法錯誤的是)。A.氏準則指出了碼元傳輸?shù)乃俾适鞘芟薜?，不能任意提高，否則在接收端就無法正確判定碼元是1還0B.農(nóng)公式給出了信息傳輸速率的極限，即對于一定的傳輸帶寬和傳輸信噪比，信息傳輸速率的上限就確定了√C.氏準則雖然是在理想條件下推導出的，但是給出了在實際條件下對信息傳輸率的限制

D.農(nóng)公式告訴我們，若要得到無限大的信息傳送速率，有兩個辦法：要么使用無限大的傳輸帶寬，要么使信號的信噪比為無限大，即采用沒有噪聲的傳輸信道或使用無限大的發(fā)送功率A選項即為奈氏準則B錯，對于一定的傳輸帶寬和傳輸信噪比，則給出了碼元傳輸率的限制，沒有對信息傳輸速率(bits)給出限制，可以通過讓每個碼元攜帶更多比特的方法提高信息傳輸速率C、項由香農(nóng)定理可以得出。36.假一臺連接到網(wǎng)絡上的計算機的網(wǎng)絡配置為地=136子網(wǎng)掩碼一255網(wǎng)關(guān)地址=13662．89．這臺計算機在網(wǎng)絡中不能與其他主機進行通信。其中)項設置導致了問題的產(chǎn)生。A.網(wǎng)掩碼B.關(guān)地址C.IP地D.他配置

√易知本網(wǎng)絡是B類網(wǎng)絡192=11000000IP址中前18位是網(wǎng)絡地址，89=01011011，2=00000010現(xiàn)IP地與網(wǎng)關(guān)地址的前18位不同，前位同，要使IP址與網(wǎng)關(guān)地址屬于同一子網(wǎng)，子網(wǎng)掩碼必須為2552551280顯lP址與網(wǎng)關(guān)地址二者之一有錯。B類網(wǎng)絡下子網(wǎng)掩碼2551280所允許的有效子網(wǎng)是2

一子網(wǎng)掩碼255．255．192．0允許的有效子網(wǎng)是

一子網(wǎng)號01和10(00保留地址)個子網(wǎng)的主機地址分別為136—136和136一13662．191．故IP地址不在上述范圍內(nèi)。故選C。37.內(nèi)網(wǎng)關(guān)協(xié)議包括)A.OSPF和IGPB.OSPF和C.RIPBGPD.OSPF和

√動態(tài)路由協(xié)議包括內(nèi)部網(wǎng)關(guān)協(xié)議(IGP)和外部網(wǎng)關(guān)協(xié)(EGP)。具體的內(nèi)部網(wǎng)關(guān)協(xié)議有OSPF、、IGRP以及．EIGP等具體的外部網(wǎng)關(guān)協(xié)議有和BGPA的原因在于IGP是部網(wǎng)關(guān)協(xié)議的英文簡寫，它并不是一個具體的協(xié)議。38.對算機網(wǎng)絡按照信號頻帶占用方式來劃分，可以劃分的網(wǎng)絡是)。A.絞線網(wǎng)和光纖網(wǎng)B.域網(wǎng)和廣域網(wǎng)C.帶網(wǎng)和寬帶網(wǎng)D.形網(wǎng)和總線形網(wǎng)

√計算機網(wǎng)絡按覆蓋范圍分為：局域網(wǎng)作用范圍一般為米到幾十公里城域網(wǎng)MAN(介wAN與之間)廣域網(wǎng)WAN(作用范圍一般為幾十到幾千公里按拓撲結(jié)構(gòu)分類：總線型、環(huán)型、星型、網(wǎng)狀；按信息的交換方式來分電路交換報文交換、報文分組交換；按傳輸介質(zhì)分類線網(wǎng)光纖網(wǎng)、無線網(wǎng)、局域網(wǎng)通常采用單一的傳輸介質(zhì)，而城域網(wǎng)和廣域網(wǎng)采用多種傳輸介質(zhì)；按通信方式分類：點對點傳輸網(wǎng)絡、廣播式傳輸網(wǎng)絡。39.下關(guān)于TCP和UDP的描述正確的是()。A.TCPUDP都是無連接的B.TCP無連接的，UDP面向連接C.TCP用于可靠性較差的廣域網(wǎng)，UDP適用于可靠性較的局域網(wǎng)√D.TCP用于可靠性較高的局域網(wǎng)，UDP適用于可靠性較的廣域網(wǎng)TCP面向連接的，UDP無連接的，所以A、B錯。由TCP向連接，所以可用于可靠性較差的廣域網(wǎng)，而UDP是連接的，適用于可靠性較高的局域網(wǎng)。故D錯，選40.在特網(wǎng)中以下說法正確的是I機通常需要實現(xiàn)TCP議Ⅱ由器必須實現(xiàn)議Ⅲ機必須實現(xiàn)IP協(xié)議Ⅳ．路由器必須實IP協(xié)議A.I、和ⅢB.I、和ⅣC.I、和ⅣD.、Ⅲ和Ⅳ

√

主機是終端設備，需實現(xiàn)整個五層協(xié)議，而路由器是網(wǎng)絡層設備，僅需實現(xiàn)網(wǎng)絡層及其以下層的協(xié)議即物理層，數(shù)據(jù)鏈路層和網(wǎng)絡層三個層次的協(xié)議。而傳輸層協(xié)議，路由器無需實現(xiàn)此協(xié)議故排除Ⅱ，即AB、錯。41.下面)是數(shù)據(jù)報服務的特點。A.最大努力將分組交付給目的主機B.保證按源主機發(fā)送分組的先后順序交付給目的主機C.一種沒有質(zhì)量保證的服務D.一種面向連接的服務√數(shù)據(jù)報服務提供的是一種盡最大努力的、不保證按源主機發(fā)送分組的先后順序交付的、不可靠的服務，非面向連接的服務。故D選項錯誤。二、合應用題二、綜合用(總題數(shù)：8，數(shù)22.00)42.合應用題41-47小題。__________________________________________________________________________________________已知一組關(guān)鍵字為(26，，41384415，，12，，5l，25)用鏈地址法解決沖突。假設裝填因子a=0．75散列函數(shù)的形式為，回答下列問題（分數(shù)：）(1).造散列函數(shù)。__________________________________________________________________________________________正確答案(確答案：由a=075，得m=11／075，因此，取表長m(1)哈函數(shù)H(K)=K／13(P應該取不大于表長的最大素數(shù)))(2).畫散列表。__________________________________________________________________________________________正確答案：(確答案：哈希表見下頁。)(3).計出等概率情況下查找成功的平均查找長度。__________________________________________________________________________________________正確答案：(確答案：等概率情況下查找成功的平均查找長度：11。)(4).汁出等概率情況下查找失敗的平均查找長度。__________________________________________________________________________________________正確答案：(確答案：等概率情況下查找失敗的平均查找長度：13。

)43.設一個算法，求無向圖采用鄰接表存儲)連通分量個數(shù)。__________________________________________________________________________________________正確答案確答案解一深度優(yōu)先遍歷方法如下VoidDFS(AGraph*G,intv)；visited[v]=1／／置已訪問標記printf(”％，；／／輸出被訪問點的編號p=G->adjlist[V]．firstarc／／向頂點第一條邊的終結(jié)點while(p!=NULL){if(visited[p一>adjvex]==0)／若頂點未訪問，遞歸訪問它DFS(G，)44.假某計算機的運算器框圖如下圖所示，其中ALU16位加法器電平工作)SA、SB16鎖存器，4通用寄存器由D觸發(fā)器組成，端出，

讀控制

寫控制

微指令字長，格式如下(考慮順序控制字段)：

各字段意義如下：一讀R0一選擇控(2位。F2寫R0～R3的擇控制2位F3打入的控制信號F4打入控制信號。F5一打開非反向三態(tài)門的控制信號LDALUF6一打開反向三態(tài)門的控制信號

并使加法器最低位加F7一鎖存器SB零RESET信號。F8一微程序結(jié)束，轉(zhuǎn)入取機器指令的控制信號。一寄存器讀命令W寄存器寫命令要求：用二進制代碼設計出指令的微程序(求畫出微程序流程圖)。(1)“，R2”指令，(R1)+(R2)vR2(2)“MOV，R0R3指令，即(R0)→(R3)__________________________________________________________________________________________

正確答案：(確答案：

對應的微指令如下：ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001)45.已x和y用變形補碼計算結(jié)果，同時指出結(jié)果是否溢出。求寫出計算步驟)x=一0．1011，一01001求，—y=?__________________________________________________________________________________________正確答案：確答案：補=10101[y]補=10111[一y]補=0．1001=11．+[y]補110111得到[x+y]補101100生溢出[x]=110101+[一y]補=00．1001得到x+y]補=11．發(fā)生溢出xy=一00010)若干個等待訪問磁盤者依次要訪問的柱面為，44，40，4，12，76，假設每移動一個柱面需要3毫秒時間動臂當前位于40柱面按下列算法分別計算為完成上述各次訪問總共花費的尋找時間數(shù)：4.00(1).來先服務算法；__________________________________________________________________________________________正確答案：(確答案：(1)來先服務算法：移動臂的移動次序和移動的柱面數(shù)如下：移動次序40一>一>44>40一>4一>80->12一76移動柱面數(shù)分別為(20)、(24)(4)(36)、(76)、(68)、(64)然，共移動柱面數(shù)是292因此，總的尋道間是：毫×292=876毫)(2).最尋找時間優(yōu)先算法。___________________________________________________________