卷52021天勤計算機考研408八套模擬

1、2021 天勤計算機考研 408 八套模擬卷（卷五）22021 天勤計算機考研 408 八套模擬卷 卷五數(shù)據(jù)結(jié)構(gòu)篇一、選擇題1. 在 n 個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復雜度是 O（1）的操作是（）。A. 第 i（1in）個結(jié)點和求第 i 個結(jié)點的直接前驅(qū)（1in）B. 在第 i（1in）個結(jié)點后一個新結(jié)點C. 刪除第 i（1in）個結(jié)點D以上都不對2. 以下說法正確的是（）。 結(jié)點的循環(huán)雙鏈表 L 為空的條件是：Lprior=L&&Lnext=L 線性表的 和刪除總是伴隨著大量數(shù)據(jù)的移動只有刪除靜態(tài)鏈表的尾結(jié)點才不需要移動元素若線性表采用鏈式 結(jié)構(gòu)，要求內(nèi)存中可用 單

2、元的地址必須不連續(xù)A僅B僅、C僅、D、和3. 循環(huán)隊列用數(shù)組 A0 m-1存放其元素值，已知其頭尾指針分別是 front 和 rear（且隊尾指針 rear 指向隊尾元素的下一個元素），則當前隊列中的元素個數(shù)是（）。A(rear-front+m)%mB(rear-front+1)%mCrear-front-1Drear-front4. 下列關于二叉樹的敘述中正確的是（）。對于任何一棵二叉樹，葉子結(jié)點數(shù) 為 2 的結(jié)點數(shù)加 1二叉樹的左右子樹不可以任意地交換二叉樹只適合使用鏈式結(jié)構(gòu) ，不可能用順序結(jié)構(gòu) 結(jié)點按層序編號的二叉樹，第 i 個結(jié)點的（假設 ）的編號為 2i A僅、B僅C僅、D僅、5.

3、若二叉樹是由森林變換而來的，若森林中有 n 個非終端結(jié)點，則二叉樹中無右孩子的結(jié)點有（）。An-1BnCn+1Dn+26. 已知二叉樹后序遍歷序列是 dabec，中序遍歷序列是 debac，它的前序遍歷序列是（）。Aacbed Bdecab Cdeabc Dcedba7. 在具有 n 個頂點的圖 G 中，若最小生成樹不唯一，則（）。G 的一定大于 n-1G 的最小的邊一定有多條G 的最小生成樹代價不一定相等A僅B僅、C僅、D僅88 題圖中強連通分量的個數(shù)為（）。A2B3C4D59. 在一棵二叉排序樹上，查找關鍵字為 35 的結(jié)點，依次比較的關鍵字有可能是（）。A28，36，18，46，35B1

4、8，36，28，46，35 C46，28，18，36，35D46，36，18，28，358 題圖10. 排序趟數(shù)與序列的原始狀態(tài)無關的排序是（）。直接排序簡單選擇排序冒泡排序基數(shù)排序A僅、B僅、C僅、D僅、二、綜合題1. 對給定的有 7 個頂點 v1，v2，v7 的有向圖的鄰接矩陣，如下表所示，要求：（1） 畫出該有向圖；（2） 畫出其鄰接表；（3） 從 v1 出發(fā)到其余各頂點的最短路徑長度；題 1 表 鄰接矩陣2532813553952. 給定一字符串，該字符串中 若干對相同的字符，設計一個在時間和空間上盡可能高效的算法，找出一對相 同字符在該字符串中的最大距離。例如：“KLabcLdecL

5、”，其中第一個“L”和最后一個“L”相距最遠，它們 在原字符串中的位置相差 8，要求：（1） 給出算法的基本設計思想。（2） 根據(jù)設計思想，采用 C、C+語言描述算法，關鍵之處給出注釋。（3） 說明你所設計算法的時間復雜度和空間復雜度。2021 天勤計算機考研 408 八套模擬卷（卷五）4組成原理篇一、選擇題（單選）1. CPU 的CPI 與下列哪個因素無關？（）。時鐘頻率系統(tǒng)結(jié)構(gòu)指令集A僅、B僅、C僅、D、和2. 設某浮點機采用規(guī)格化浮點數(shù)表示，階碼用移碼表示（最高位代表符號位），尾數(shù)用補碼表示。下列規(guī)格化浮點數(shù)中哪個數(shù)最大（）。A1111111，1.000000B0011111，1.011

6、101C1000001，0.111101D0111111，0.1000 103. 有一主存-Cache 層次的器，其主存容量為 1MB（按字節(jié)編址），Cache 容量為 16KB，每字塊有 8 個字，每字為 32 位，采用直接地址映像方式。若主存地址為 35301H，且CPU Cache 命中，則在 Cache 的第（ ）號字塊（Cache 字塊號從 0 開始）。A152B153C154D1514. 下列的說法正確的是（）。高位多體交叉器能很好地滿足程序的局部性原理高位四體交叉器可能在一個周期內(nèi)連續(xù) 4 個模塊雙端口器可以同時對同一區(qū)間、同一單元進行寫操作A僅、 B僅、 C僅D僅54 片 16

7、KB×8 位的可以設計成（）容量的器。 64KB×8 位32KB×4 位32KB×16 位16KB×32 位 A僅、BB僅、 C僅、D僅、6. 下列說法正確的是（）。某加法指令，在指令的地址碼中給出了器地址，則此指令在執(zhí)行周期一定器零地址雙操作數(shù)指令不需要指出操作數(shù)地址在一地址格式的指令中，只有一個操作數(shù)A僅、B僅I、 C僅、D、和7. 指令系統(tǒng)中采用不同尋址方式的目的主要是（）。A實現(xiàn) 程序 B縮短指令長度，擴大尋址空間，提高編程靈活性C可以直接 外存D提供擴展操作碼的可能性并降低指令譯碼難度8. 微指令的組成部分不可能包含（）。微操作字段外

8、部條件字段操作碼字段下地址字段A僅B僅、C僅、D僅、9采用相對尋址方式的轉(zhuǎn)移指令占兩個字節(jié)，第一字節(jié)是操作碼，第二字節(jié)是相對位移量（用補碼表示）。取指令時，每次 CPU 從器取出一個字節(jié)，并自動完成 PC+1 的操作。假設執(zhí)行到某轉(zhuǎn)移指令時（即取指令前），PC 的內(nèi)容為 200CH，該指令的轉(zhuǎn)移目標地址為 1FB0H，則該指令第二字節(jié)的內(nèi)容應為（）。A5CHB5EHCA2HDA4H10. 下列關于總線仲裁方式的說法中，正確的是（）。計數(shù)器定時方式下，有一根總線請求（BR）線和一根地址線，如果每次計數(shù)器從 0 開始計，則號大的優(yōu)先級高計數(shù)器定時方式下，有一根總線請求（BR）線和一根地址線，如果每

9、次計數(shù)器從當前開始計，則號小的優(yōu)先級高分布式仲裁邏輯分散在總線各部件中，不需要仲裁器A僅、B僅C僅、 D僅和11. 設CPU 與I/O 以中斷方式進行數(shù)據(jù)傳送。當CPU 響應中斷時，該I/O 接口 器送給CPU 的中斷向量表（中斷向量表存放中斷向量）的指針是 0800H，0800H 單元中的值為 1200H，則該 I/O 的中斷服務程序在主存中的 地址為（ ）。A. 0H B0801H C1200H D1201H二、綜合題1.short fun1(unsigned short si)return si*256;short fun2(unsigned short si)2021 天勤計算機考研

10、408 八套模擬卷（卷五）9short temp = si*256; return temp/256;請回答下列問題：（1） 假設計算機硬件不提供直接乘除運算功能，如何實現(xiàn)上述函數(shù)的功能？函數(shù)fun1 返回結(jié)果的低 8 位又什么特點？fun2 返回結(jié)果可取到的最大值和最小值是什么？（2） 根據(jù)以上程序填寫下表（要求機器數(shù)用十六進制表示）。（3） 表中的哪些數(shù)據(jù)異常？sifun1(si)fun2(si)值機器數(shù)值機器數(shù)值機器數(shù)1271282562.以下是計算兩個向量點積的程序段：float dotproduct(float x8,float y8)float sum=0; int i;for(i

11、=0;i<8;i+) sum+=xi*yi;return sum;（1 該段程序運行的計算機的數(shù)據(jù) Cache 采用直接方式，其容量為 32B，每個主存塊大小為 16B。假定編譯程序?qū)⒆兞?sum 和i 分配給寄存器，數(shù)組x 存放在 00000000H 開始的 32B 的連續(xù)區(qū)中，數(shù)組 y 則緊跟在x 后進行存放。試計算該程序數(shù)據(jù)中率。（2） 將上述（1）中的數(shù)據(jù) Cache 改用 2-相聯(lián)方式，塊大小改為 8B，其他條件不變，則該程序數(shù)據(jù)中率是多少？（3） 在上述（1）中條件不變的情況下，如果將數(shù)組 x 定義為float12，則數(shù)據(jù)中率又是多少？操作系統(tǒng)篇一、選擇題（單選）1. 在操作

12、系統(tǒng)中，用戶在使用I/O 時，通常采用（ ）。A物理 名B邏輯 名C虛擬 名D 序號2. 考慮下面的基于動態(tài)改變優(yōu)先級的可搶占式優(yōu)先權(quán)調(diào)度算法。大的優(yōu)先權(quán)數(shù)代表高優(yōu)先級。當一個進程在等待CPU 時（在就緒隊列中，但未執(zhí)行），優(yōu)先權(quán)以a速率改變；當它運行時，優(yōu)先權(quán)以b速率改變。所有的進程在進入就緒隊列被給定優(yōu)先權(quán)數(shù)為 0。參數(shù)a和b可以設定給許多不同的調(diào)度算法。下列（ ）設定可以實現(xiàn)進程FIFO（First In First Out）。Ab>a>0Ba>b>0Cb<a<0Da<b<03. 假設系統(tǒng)有 5 個進程，A、B、C 三類資源。某時刻進程和資

13、源狀態(tài)如下表所示。3 題表 某時刻進程和資源狀態(tài)Alloca tionMaxAvaila bleABCABCABCP1212559233P2402536P34054011P4204425P5314424下面敘述正確的是（ ）。A系統(tǒng)不安全B. 該時刻，系統(tǒng)安全，安全序列為<P1，P2，P3，P4，P5> C該時刻，系統(tǒng)安全，安全序列為<P2，P3，P4，P5，P1> D該時刻，系統(tǒng)安全，安全序列為<P4，P5，P1，P2，P3>4. 設有一個發(fā)送者進程和接收者進程，其流程圖如下圖所示。S 是用于實現(xiàn)進程同步的信號量，mutex 是用于實現(xiàn)進程互斥的信號量。試

14、問流程圖中的 A、B、C、D 4 個框中應填寫什么？ 緩沖區(qū)有無限多個且初始為空，S 和mutex 的初值應該是什么？（）AP(mutex)、V(mutex)、P(S)、P(mutex)S=緩沖區(qū)的個數(shù)mutex=1BP(S)、V(mutex)、P(S)、P(mutex)S=0mutex=1CP(mutex)、V(mutex)、P(S)、P(mutex)S=0mutex=1DP(S)、V(mutex)、P(S)、P(mutex)S=緩沖區(qū)的個數(shù)mutex=04 題圖 發(fā)送者進程和接收者進程的流程圖5考慮在一個虛擬頁式管理的系統(tǒng)中，在地址變換過程中，進程狀態(tài)可能發(fā)生的變化有（）。進程被撤銷進程變

15、為阻塞ABC和D都不可能6. 在虛擬分頁 管理系統(tǒng)中，若進程的頁面不在主存，且主存中沒有可用的空閑幀時，系統(tǒng)正確的處理順序為（）。A. 決定淘汰頁頁面調(diào)出缺頁中斷頁面調(diào)入B決定淘汰頁頁面調(diào)入缺頁中斷頁面調(diào)出C缺頁中斷決定淘汰頁頁面調(diào)出頁面調(diào)入D缺頁中斷決定淘汰頁頁面調(diào)入頁面調(diào)出7. 下列關于Belady 現(xiàn)象和工作集的說法正確的是（）。先進先出（FIFO）頁面置換算 產(chǎn)生Belady 現(xiàn)象最近最少使用（LRU）頁面置換算 產(chǎn)生 Belady 現(xiàn)象為了保證進程高效的運行，它的工作集頁面需要都在虛擬器內(nèi)，否則會出現(xiàn)頻繁的頁面調(diào)入/調(diào)出現(xiàn)象為了保證進程高效的運行，它的工作集頁面需要都在主器內(nèi)，否則會

16、出現(xiàn)頻繁的頁面調(diào)入/調(diào)出現(xiàn)象A、B、C、D、8. 某文件系統(tǒng)物理結(jié)構(gòu)采用三級索引分配，如果每個磁盤塊的大小為 1024B，每個盤塊索引號占用 4B， 請問在該文件系統(tǒng)中，最大的文件大小最接近的是（）。A. 8GBB16GBC32GBD2TB9 在外存空間的排列也會影響存取等待時間。考慮幾個邏輯 A、B、C、J，它們被存放于磁盤上，每個磁道存放 10 個，安排如下表所示。9 題表 每個磁道存放 10 個物理塊12345678910邏輯ABCDEFGHIJ要經(jīng)常順序處理這些 ，磁盤旋轉(zhuǎn)速度為 20ms/r，處理程序讀出每個后花 4ms 進行處理。考慮對的分布進行優(yōu)化，如下表所示，相比之前的分布，優(yōu)

17、化后的時間縮短了（）。9 題表優(yōu)化后磁道存放的 10 個物理塊12345678910邏輯AHEBIFCJGDA60msB104msC144msD204ms10考慮單用戶計算機上的下列I/O 操作，需要使用緩沖技術的是（）。圖形用戶界面下使用鼠標在多任務操作系統(tǒng)下的磁帶驅(qū)動器（假設沒有預分配） 包含用戶文件的磁盤驅(qū)動器使用器 I/O，直接和總線相連的圖形卡A、B、C、D全選二、綜合題1. I/O 有哪幾種實現(xiàn)方式？各有何優(yōu)缺點？2. 在單CPU 和兩臺輸入/輸出（I1，I2）的多道程序設計環(huán)境下，同時投入 3 個作業(yè)J1、J2 和J3 運行。這3 個作業(yè)對CPU 和輸入/輸出的使用順序和時間如下

18、所示。J1：I2（30ms）；CPU（10ms）；I1（30ms）；CPU（10ms）；I2（20ms） J2：I1（20ms）；CPU（20ms）；I2（40ms） J3：CPU（30ms）；I1（20ms）；CPU（10ms）；I1（10ms） CPU、I1、I2 都能并行工作，J1 優(yōu)先級最高，J2 次之，J3 優(yōu)先級最低，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU，但不搶占I1 和I2。試求：（1）3 個作業(yè)從投入到完成分別需要的時間。（2） 從投入到完成的 CPU 利用率。（3） I/O利用率。計算機網(wǎng)絡篇1. 計算機網(wǎng)絡可分 信子網(wǎng)和資源子網(wǎng)，下列屬于通信子網(wǎng)的是（）。網(wǎng)橋交換機

19、 計算機 路由器A、B、C、D、2. 已知循環(huán)冗余碼生成多項式G(x)=x5+x4+x+1，若位為 10101100，則冗余碼是（）。A01101B01100C1101D11003. 若子網(wǎng)掩碼為 ，則下列（）IP 與其他地址不在同一網(wǎng)絡中？ A00B5C00D54. 在IPv6 協(xié)議中，一個數(shù)據(jù)流可以由（）進行標識。A源地址、目的地址和流名稱B源地址、目的地址和流標號C源地址、端和流標號DMAC 地址、端和流名稱5使用CIDR 技術把 4 個網(wǎng)絡 /18、100

20、.100.64.0/18、/18、/18 匯聚成一個超網(wǎng)，得到的地址是（）。A/16 B/18 C/18 D/186. 一個有 50 個路由器的網(wǎng)絡，采用基于距離-向量的路由選擇算法，路由表的每個表項長度為 6B，每個路由器都有 3 個鄰接路由器，每秒與每個鄰接路由器交換 1 次路由表，則每條鏈由于路由器更新路由 而耗費的帶寬為（ ）。A2400bit/s B3600bit/s C4800bit/s D6000bit/s7. 設某TCP 的擁塞窗口的

21、慢啟動門限值初始為 8（為報文段，且最大報文段長度為 1KB），當擁塞窗口上升到 12 時，網(wǎng)絡會發(fā)生超時。按照以上給出的條件，第 12 次傳輸時，擁塞窗口的大小為（）。 A5B6 C7 D88關于FTP 的工作過程，下面說法錯誤的是（）。 A每次數(shù)據(jù)傳輸結(jié)束后，F(xiàn)TP 服務器同時 21 和 20 端口BFTP 的數(shù)據(jù)連接是非持久的CFTP 的文件傳輸需要兩條 TCP 連接DFTP 協(xié)議可以在不同類型的操作系統(tǒng)之間傳送文件二、綜合題一個公司有兩個部門：研發(fā)部和市場部，研發(fā)部有 29 臺計算機，市場部有 11 臺計算機。現(xiàn)在，公司申請了一個C 類地址 ，規(guī)劃的網(wǎng)絡拓撲如下

22、圖所示。試問：綜合題 1 圖 規(guī)劃的網(wǎng)絡拓撲（1） 請給出合理的子網(wǎng)規(guī)劃，并說明理由，然后將規(guī)劃填入下表。（1）表 子網(wǎng)規(guī)劃表子網(wǎng)號子網(wǎng)掩碼子網(wǎng)網(wǎng)絡地址子網(wǎng)廣播地址子網(wǎng)網(wǎng)絡地址范圍NO.ANO.BNO.C其他（2） 根據(jù)第一題的規(guī)劃，為兩個路由器的接口和各臺計算機分配IP 地址。（3） 如果路由器R1 和R2 都采用了路由協(xié)議（Routing Information Protocol，RIP）作為路由選擇協(xié)議，當運行之后，R1 的路由表應該是怎樣？請?zhí)顚懴卤?。?）表 R1 的路由表目的網(wǎng)絡地址接口下一跳度量注：度量是一個通用的詞語，如果采用 RIP 協(xié)議，度量即表示跳數(shù)。如果采用其他協(xié)議，度

23、量就可能是其他含義。（4） 當路由器 R1 的接口E0 斷掉了，經(jīng)過一次交互之后，R1 的路由表發(fā)生了怎樣的變化？請?zhí)顚懴卤?。?）表 交互后 R1 的路由表目的網(wǎng)絡地址接口下一跳度量2021 天勤計算機考研 408 八套模擬卷（卷五）10數(shù)據(jù)結(jié)構(gòu)篇一、選擇題1.A2.A3.A4.B5.C6.D7.A8.C9.D10.B二、綜合題1.(1)有向圖：（2）臨接表（3）0 到其余頂點到最短路徑長度：2.（1） 設計思想：（2） 在遍歷字符數(shù)組的過程中，對已經(jīng) 過的字符進行標記，同時記下它們第一次出現(xiàn)在原字符串中的位置， 當以后再次遍歷到此字符時，根據(jù)當前的位置和第一次出現(xiàn)的位置，求出它們之間的距離

24、，然后用得到的距離和當 前最大距離相比較。為此需要設置一個數(shù)組用來存放已經(jīng) 過的字符，為了能加快搜索，采用字符的 ASCII 碼作為數(shù)組的下標來支持隨機 ，通過對應下標中的數(shù)組元素的 標記來 它是否被 過，同時獲取它第一次出現(xiàn)的位置，每遍歷一個字符就開始 ，并用 max 來保存當前最大距離。代碼：int getMaxLength(char str,int n)int max=0;2021 天勤計算機考研 408 八套模擬卷（卷五）11int i;int isrray128; for(i=0; i<128; +i)isrrayi = -1; for(i=0; i<n; +i)if(i

25、srraystri = -1) isrraystri = i;elseint tempL = i - isrraystri; if(max < tempL)max = tempL;return max;時間復雜度 O(n)?？臻g復雜度 O(1)。組成原理篇一、選擇題1.C2.C3.A4.D5.D6.B7.B8.A9.C10.B11.C二、綜合題1.(1)fun1 返回結(jié)果的低 8 位全為 0fun2 返回結(jié)果最小值為-128，最大值為 127(2)sifun1(si)fun2(si)值機器數(shù)值機器數(shù)值機器數(shù)127007FH325127F00H127007FH1280080H-327688

26、000H-128FF08H2560100H00000H00000H(3)當 si 等于 128 和 256 時，fun1 和 fun2 都異常。2.(1) 為 0。(2) 為 50%(3) 75%。2021 天勤計算機考研 408 八套模擬卷（卷五）13操作系統(tǒng)篇一、選擇題1.B2.A3.D4.C5.C6.C7.B8.B9.C10.D二、綜合題1.（1）程序 方式、中斷方式、DMA 方式和通道方式。（2）程序 方式優(yōu)點：實現(xiàn) 簡單；程序 方式缺點：需要消耗大量的 CPU 時間用來，無法發(fā)現(xiàn) 錯誤，且 CPU 和、 和 無法并行工作。中斷 方式的優(yōu)點：能檢測 錯誤，能并行工作；中斷 方式的缺點：

27、CPU 仍然要話費大量的時間用來中斷處理，的并行程度會受到中斷處理時間的限制。DMA 方式的優(yōu)點：采用了外設和內(nèi)存直接交換數(shù)據(jù)的方式，因此 CPU 對于 I/O 的時間開銷少；DMA 方式的缺點：數(shù)據(jù)傳輸結(jié)束時需要中斷處理，增加了硬件開銷。通道方式的優(yōu)點：CPU 對于 I/O 的時間開銷更少；通道方式的缺點：硬件開銷更大，數(shù)據(jù)傳輸結(jié)束時仍需要中斷，需要進行通道程序的設計，增加了實現(xiàn)難度。2.（1）J1：30+10+30+10+10+20 = 110ms J2：20+10+10+10+40 = 90ms J3：20+30+10+10+20+10+10 = 110ms（2）從投入到完成的 CPU 利用率為：(20+10x6)/110 = 72.7%（3） I1 的利用率為(20+30+20+10)/110，即 72.7%；I2 的利用率為(30+40+20)/110，即 81.8