2020年全國碩士研究生入學(xué)統(tǒng)一考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考

題。1.將一個10*10對稱矩陣M的上三角部分的元素素mij(1≤i≤j≤10)按列優(yōu)先存CNm2在N中的下標(biāo)是：度為5且有10個節(jié)點的二叉樹，若采用順序存儲結(jié)構(gòu)保存，每個結(jié)點占1個存儲單元(僅存放結(jié)點的數(shù)據(jù)信息)，則存放該二叉樹需要的存儲單元數(shù)量4.已知森林F及與之對應(yīng)的二叉樹T，若F的先根遍歷序列是a,b,c,d,e,f，中根遍badfecT遍歷序列是：能生成如下二叉排序樹的是：6.修改遞歸方式實現(xiàn)的圖的深度優(yōu)先搜索(DFS)算法，將輸出(訪問)定點信息的語句移到退出遞歸前(即執(zhí)行輸出語句后立刻退出遞歸)。采用修改后的算法遍歷有向無環(huán)圖G，若輸出結(jié)果中包含G中的全部頂點，則輸出的頂點序列是G的：7.已知無向圖G如下所示，使用克魯斯卡爾(K『uskal)算法求圖G的最小生成樹，加入 (不確定最后一個括號的內(nèi)容)8.若使用AOE網(wǎng)估算工程進度，則下列敘述中正確的是：A、關(guān)鍵路徑是從原點到匯點邊數(shù)最多的一條路徑B是從原點到匯點路徑長度最長的路徑C任一關(guān)鍵活動的時間不會延長工程的工期D的時間將會縮短工程的工期9.下列關(guān)于大根堆(至少含2個元素)的敘述中正確的是：12.下列給出的部件中其位數(shù)(寬度)一定與機器字長相同的是：ABCD14.在按字節(jié)編址，采用小端方式的32位計算機中，按邊界對齊方式為以下C語言結(jié)構(gòu)型變量a分配存儲空間。ructrecordshortx1;intx2;}a;若a的首地址為2020FE00H，a的成員變量x2的機器數(shù)為12340000H，則其中34H所在存儲單元的地址是：15.下列關(guān)于TLB和Cache的敘述中錯誤的是：D、都由DRAM存儲器組成。18.下列關(guān)于“自陷”(Trap，也稱陷阱)的敘述中錯誤的是：C、自陷發(fā)生后CPU將轉(zhuǎn)去執(zhí)行操作系統(tǒng)內(nèi)核相應(yīng)程序；QPI是一種點對點全工雙周同步串行總線，總線上的設(shè)備可同時接收和發(fā)送信息，每個方向可同時傳輸20位信息(16位數(shù)據(jù)+4位校驗位)，每個QPI數(shù)據(jù)包有80位信息，分2個時鐘周期傳送，每個時鐘周期傳遞2次，因此QPI總線帶寬為每秒傳事件中屬于外部中斷事件的是：21.外部中斷包括不可屏蔽中斷(NMI)和可屏蔽中斷，下列關(guān)于外部中斷的敘述中錯誤的NMIC可屏蔽中斷的優(yōu)先級高；22.若設(shè)備采用周期挪用DMA方式進行輸入輸出，每次DMA傳送的數(shù)據(jù)塊大小為512A2位數(shù)據(jù)，DMA控制器就發(fā)出一次總線請求；C個數(shù)據(jù)塊的傳送過過程中，CPU不可以訪問主存儲器；DDMA中斷請求。A讀”方式打開文件F；D、進程關(guān)閉F時系統(tǒng)刪除F在系統(tǒng)打開文件表中的表選項中支持文件長度可變，隨機訪問的磁盤存儲空間分配方式是：25.下列與中斷相關(guān)的操作中，由操作系統(tǒng)完成的是：CIII,IV;DII,III,IV.隊列調(diào)度算法時需要考慮的是：I就緒隊列的數(shù)量II就緒隊列的優(yōu)先級III各就緒隊列的調(diào)度算法IV進程在就緒隊列間的遷移條件AB6個，t時刻資源分配及需求情況如下表所示AP1,P2,P3;B、存在安全序列P2,P1,P3;C序列P2,P3,P1;D、不存在安全序列。28.下列因素影響請求分頁系統(tǒng)有效(平均)訪存時間的是：關(guān)于父進程與子進程的敘述中錯誤的是：A、父進程與子進程可以并發(fā)執(zhí)行C、父進程與子進程有不同的進程控制塊0.對于具備設(shè)備獨立性的系統(tǒng)下列敘述中錯誤的是：B備與物理設(shè)備之間的映射關(guān)系D、更換物理設(shè)備后必須修改訪問該設(shè)備的應(yīng)用程序。(缺一個選項)遵循的是：33.下圖描述的協(xié)議要素是:I、語法II、語義III、時序關(guān)于虛電路網(wǎng)絡(luò)的敘述中錯誤的是：A、可以確保數(shù)據(jù)分組傳輸順序B寬C電路時需要進行路由選擇D、依據(jù)虛電路號(VCID)進行數(shù)據(jù)分組轉(zhuǎn)發(fā)35.下圖所示的網(wǎng)絡(luò)沖突域和廣播域的個數(shù)分別37.某IEEE802.11無線局域網(wǎng)中主機H與AP之間發(fā)送或接收CSMA/CA幀的過程如下圖所示，在H或AP發(fā)送幀前所等待的幀間間隔時間(IFS)中最長的是：38.若主機甲與主機乙已建立一條TCP連接，最大段長(MSS)為1KB，往返時間(RTT)為39.若主機甲與主機乙建立TCP連接時發(fā)送的SYN段中的序號為1000，在斷開連接時，ms。41.定義三元組(a,b,c)(a,b,c均為正數(shù))的距離D=|a-b|+|b-c|+|c-a|.給定3個非空整數(shù)集合S1,S2,S3,按升序分別存儲在3個數(shù)組中。請設(shè)計一個盡可能高效的算法，計算并輸出所有可能的三元組(a,b,c)(a∈S1,b∈S2,c∈S3)中的最小距離。例如S1={-的三元組為(9，10，9)要求：計思想，采用C或C++語言描述算法，關(guān)鍵之處給出注時間復(fù)雜度和空間復(fù)雜度。字符集(字符個數(shù)≥2)的不等長編碼，每個字符的編碼均為二進制的0，1序列，最長為L位，且具有前綴特性。請回答下列問題： 碼？ (2)基于你所設(shè)計的數(shù)據(jù)結(jié)構(gòu)，簡述從0/1串到字符串的譯碼過程 (3)簡述判定某字符集的不等長編碼是否具有前綴特性的過程43.有實現(xiàn)x*y的兩個C語言函數(shù)如下：ignedumulunsignedxunsignedy{returnx*y;}ntimulintxinty{returnx*y;}M中ALU只能進行加減運算和邏輯運算。請回答： MM (2)若M的指令系統(tǒng)中有乘法指令，則基于ALU、位移器、寄存器以及相應(yīng)控制邏 (3)針對以下3種情況：(a)沒有乘法指令；(b)有使用ALU和位移器實現(xiàn)的乘法 (4)n位整數(shù)乘法指令可保存2n位乘積，當(dāng)僅取低n位作為乘積時，其結(jié)果可能會到的x*y的2n位乘積分別是什么(用十六進制表示)？此時函數(shù)umul()和imul()的44.假定主存地址為32位，按字節(jié)編址，指令Cache和數(shù)據(jù)Cache與主存之間均采用8B各為32KB。開始時Cache均為空，請回答下列問題： (1)Cache每一行中標(biāo)記(Tag)、LRU位各占幾位？是否有修改位？ (2)有如下C語言程序段：for(k=0;k<1024;k++)Sk2*s[k];組s在主存中的起始地址為008000C0H，則該程序段執(zhí)行過程中，訪問數(shù)組S的數(shù) (3)若CPU最先開始的訪問操作是讀取主存單元0001003H中的指令，簡要說明從45.現(xiàn)有5個操作A、B、C、D和E，操作C必須在A和B完成后執(zhí)行，操作E必須在C和D完成后執(zhí)行，請使用信號量的wait(),signal(),操作(P、V操作)描述上述關(guān)系，并說明所用信號量及其初值。表項長度均為4字節(jié)，虛擬地址結(jié)構(gòu)如下：頁目錄號(10位)頁號(10位)頁內(nèi)偏移量(12位)CaH數(shù)組元素占4字節(jié)，該程序運行時，其進程的頁目錄起始物理地址為00201000H，請回答下列問題： (2)數(shù)組a在虛擬地址空間中所占區(qū)域是否必須連續(xù)？在物理地址空間中所占區(qū)域是？ (3)已知數(shù)組a按行優(yōu)先方式存放，若對數(shù)組a分別按行遍歷和按列遍歷，則哪一種為以太網(wǎng)交換機，局域網(wǎng)采用靜態(tài)IP地址配置，路由器部分接口以及各主機的IP地圖所示：假設(shè)NAT轉(zhuǎn)換表結(jié)構(gòu)為：號號 (1)為使H2和H3能夠訪問Web服務(wù)器(使用默認端口號)，需要進行什么配置？ (2)若H2主動訪問Web服務(wù)器時，將HTTP請求報文封裝到IP數(shù)據(jù)報P中發(fā)送，則H2發(fā)送P的源IP地址和目的IP地址分別是？經(jīng)過R3轉(zhuǎn)發(fā)后，P的源IP地1.將一個10*10對稱矩陣M的上三角部分的元素素mij(1≤i≤j≤10)按列優(yōu)先存C的一維數(shù)組N中，元素m7,2在N中的下標(biāo)是：mNN22]【】D作后的棧(左側(cè)為棧底)aabace點占1個存儲單元(僅存放結(jié)點的數(shù)據(jù)信息)，則存放該二叉樹需要的存儲單元數(shù)量本二叉樹使用順序結(jié)構(gòu)存儲時，為了保證任意性，其1-5層的所有節(jié)點(包括空1badfecT遍歷序列是：n樹，都可由它的中序序列和先序序列唯一確定。edca能生成如下二叉排序樹的是：B選項構(gòu)造出的二叉排序樹6.修改遞歸方式實現(xiàn)的圖的深度優(yōu)先搜索(DFS)算法，將輸出(訪問)定點信息的語句移到退出遞歸前(即執(zhí)行輸出語句后立刻退出遞歸)。采用修改后的算法遍歷有向無環(huán)圖G，若輸出結(jié)果中包含G中的全部頂點，則輸出的頂點序列是G的： [管案]B點U到點V有一條弧，則在拓撲序列中U一定在V之前．深度優(yōu)先算法搜索路徑恰恰是一條弧，梭的輸出是從最后一個被訪問點開始輸出，最后一個輸出的點是第一個被訪問的7.已知無向圖G如下所示，使用克魯斯卡爾(K『uskal)算法求圖G的最小生成樹，加入 (不確定最后一個括號的內(nèi)容) 基本思想：按照權(quán)值的遞增順序選擇n-1條邊，并保證這n-1條邊不構(gòu)成回路。具體做法：首先構(gòu)造一個只含n個頂點的森林，然后依權(quán)值從小到大從連通網(wǎng)中選森林變成一棵樹為止。bf值最小，因此將它加入到最小生成樹中。跳過邊<d,f>,將邊<a,e>它加入到最小生成樹中。A、關(guān)鍵路徑是從原點到匯點邊數(shù)最多的一條路徑B度最長的路徑C動的時間不會延長工程的工期D的時間將會縮短工程的工期關(guān)鍵路徑(criticalpath)：在AOE網(wǎng)中，從源點到匯點的所有路徑中具有最大路徑徑9.下列關(guān)于大根堆(至少含2個元素)的敘述中正確的是：堆(Heap)具有以下特點：1)完全二叉樹2)存儲的值是偏序大根堆(Max-heap)：父節(jié)點的值大于或等于子節(jié)點的值一般用數(shù)組(順序結(jié)構(gòu))來表示堆：子數(shù)為[2,M]結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2,M]4.每個結(jié)點存放至少M/2-1(取上整)和至多M-1個關(guān)鍵字；(至少2個關(guān)鍵字)數(shù)=指向兒子的指針個數(shù)-1i子結(jié)點位于同一層單選擇排序相比1)直接插入排序元素比較次數(shù)少2)簡單選擇排序移動的元素少12.下列給出的部件中其位數(shù)(寬度)一定與機器字長相同的是：關(guān)ABCDCH1001000000000000000000000000000Hfloat1000000000000000000000000000H=-21714.在按字節(jié)編址，采用小端方式的32位計算機中，按邊界對齊方式為以下C語言結(jié)構(gòu)型變量a分配存儲空間。ructrecordshortx1;intx2;}a;若a的首地址為2020FE00H，a的成員變量x2的機器數(shù)為12340000H，則其中34H所在存儲單元的地址是：時，對應(yīng)a的存放方式為x00Hx00H15.下列關(guān)于TLB和Cache的敘述中錯誤的是：D、都由DRAM存儲器組成。CPI(ClockcyclePerInstruction)：每條計算機指令執(zhí)行所需的時鐘周期CPI=執(zhí)行程序所需要的時鐘周期數(shù)/所執(zhí)行的指令條數(shù)PIIV的指令18.下列關(guān)于“自陷”(Trap，也稱陷阱)的敘述中錯誤的是：C、自陷發(fā)生后CPU將轉(zhuǎn)去執(zhí)行操作系統(tǒng)內(nèi)核相應(yīng)程序；QPI是一種點對點全工雙周同步串行總線，總線上的設(shè)備可同時接收和發(fā)送信息，每個方向可同時傳輸20位信息(16位數(shù)據(jù)+4位校驗位)，每個QPI數(shù)據(jù)包有80位信息，分2個時鐘周期傳送，每個時鐘周期傳遞2次，因此QPI總線帶寬為每秒傳事件中屬于外部中斷事件的是：21.外部中斷包括不可屏蔽中斷(NMI)和可屏蔽中斷，下列關(guān)于外部中斷的敘述中錯誤的NMIC可屏蔽中斷的優(yōu)先級高；A：[關(guān)中斷]在中斷服務(wù)過程中為了保護中斷現(xiàn)場不被新的中斷所打斷，在保護現(xiàn)志位的影響，即使在關(guān)中斷的情況下也會被響應(yīng)。PU②CPU允許中斷及開中斷③一條指令執(zhí)行完畢且沒有更緊迫的任務(wù)22.若設(shè)備采用周期挪用DMA方式進行輸入輸出，每次DMA傳送的數(shù)據(jù)塊大小為512A2位數(shù)據(jù)，DMA控制器就發(fā)出一次總線請求；UDDMA中斷請求。ADMA的傳送是以塊為單位的CDMADMACPU的工作A、個進程只能用“讀”方式打開文件F；D、進程關(guān)閉F時系統(tǒng)刪除F在系統(tǒng)打開文件表中的表A：各進程既可以用讀方式打開文件F，也可用寫方式打開文件FC個文件的表項內(nèi)容不一定相同選項中支持文件長度可變，隨機訪問的磁盤存儲空間分配方式是：BC長度可變D式25.下列與中斷相關(guān)的操作中，由操作系統(tǒng)完成的是：III、初始化中斷向量表IV、保存中斷屏蔽字IIIII,IV.26.下列與進程調(diào)度有關(guān)的因素中在設(shè)計多級反饋隊列調(diào)度算法時需要考慮的是：I就緒隊列的數(shù)量II就緒隊列的優(yōu)先級III各就緒隊列的調(diào)度算法IV進程在就緒隊列間的遷移條件，優(yōu)先級、調(diào)度算法及進程在隊列間的遷移條件。AB6個，t時刻資源分配及需求情況如下表所示APPP;B、存在安全序列P2,P1,P3;CP,P3,P1;D、不存在安全序列。442321Need=Max–Allocation=31-21=10341222Available=(1,0)進程P2的需求釋放P2所占的資源，Available=(0,0)+(3,1)=(3,1)，僅能滿足P1的需求釋放P1所占的資源，Available=(1,0)+(4,4)=(5,1)，可以滿足P3的需求PPP28.下列因素影響請求分頁系統(tǒng)有效(平均)訪存時間的是：關(guān)于父進程與子進程的敘述中錯誤的是：A、父進程與子進程可以并發(fā)執(zhí)行C、父進程與子進程有不同的進程控制塊間0.對于具備設(shè)備獨立性的系統(tǒng)下列敘述中錯誤的是：B備與物理設(shè)備之間的映射關(guān)系D、更換物理設(shè)備后必須修改訪問該設(shè)備的應(yīng)用程序。(缺一個選項)，索引節(jié)點為4個字節(jié)32位，故最多個文件遵循的是：①空閑讓進→II②忙則等待→I③有限等待→III④讓權(quán)等待33.下圖描述的協(xié)議要素是:I、語法II、語義III、時序和同步(時序)三部分組成。語法規(guī)定了傳輸數(shù)據(jù)的格式；語義規(guī)規(guī)定了執(zhí)行各個操作的條件、時序關(guān)系等，即時間實現(xiàn)順序的詳細說明。關(guān)于虛電路網(wǎng)絡(luò)的敘述中錯誤的是：A、可以確保數(shù)據(jù)分組傳輸順序B寬C電路時需要進行路由選擇D、依據(jù)虛電路號(VCID)進行數(shù)據(jù)分組轉(zhuǎn)發(fā)35.下圖所示的網(wǎng)絡(luò)沖突域和廣播域的個數(shù)分別t0*8b/10kbps=800msTms*2+800ms*2=2000ms信道利用率=*100%=40%37.某IEEE802.11無線局域網(wǎng)中主機H與AP之間發(fā)送或接收CSMA/CA幀的過程如下圖所示，在H或AP發(fā)送幀前所等待的幀間間隔時間(IFS)中最長的是：DIFSIFS低，用于異步幀競爭訪問的時延PIFSPCF操作中使用SIFS最短，優(yōu)先級最高，用于需要立即響應(yīng)的操作38.若主機甲與主機乙已建立一條TCP連接，最大段長(MSS)為1KB，往返時間 (RTT)為2ms，則在不出現(xiàn)擁塞的前提下，擁塞窗口從8kB增長到32KB所需的最長個輪次的擁塞窗口+1，此時可求得題目所需的最長時間為 (32–8)*2ms=48ms39.若主機甲與主機乙建立TCP連接時發(fā)送的SYN段中的序號為1000，在斷開連接時，SYN為1001，字節(jié)數(shù)=FIN–1001=4000ms域名與IP地址的映射ms存在映射，需要迭代查詢各級域名服務(wù)器3次10ms+迭代查詢3次30ms+數(shù)據(jù)傳輸10ms=50ms41.定義三元組(a,b,c)(a,b,c均為正數(shù))的距離D=|a-b|+|b-c|+|c-a|.給定3個非空整數(shù)集合S1,S2,S3,按升序分別存儲在3個數(shù)組中。請設(shè)計一個盡可能高效的算法，計算并輸出所有可能的三元組(a,b,c)(a∈S1,b∈S2,c∈S3)中的最小距離。例如S1={-的三元組為(9，10，9)要求：時間復(fù)雜度和空間復(fù)雜度。forOlmnlmnSSS字符集(字符個數(shù)≥2)的不等長編碼，每個字符的編碼均為二進制的0，1序列，最長為L位，且具有前綴特性。請回答下列問題： (1)哪種數(shù)據(jù)結(jié)構(gòu)適宜保存上述具有前綴特性的不等長編碼？ (2)基于你所設(shè)計的數(shù)據(jù)結(jié)構(gòu)，簡述從0/1串到字符串的譯碼過程 (3)簡述判定某字符集的不等長編碼是否具有前綴特性的過程(Huffman)樹(1)二叉樹或赫夫曼樹對前者的優(yōu)化。串作為該葉子子結(jié)點即可。若存儲有某個字符信息的43.有實現(xiàn)x*y的兩個C語言函數(shù)如下：ignedumulunsignedxunsignedy{returnx*y;}ntimulintxinty{returnx*y;}M中ALU只能進行加減運算和邏輯運算。請回答： (2)若M的指令系統(tǒng)中有乘法指令，則基于ALU、位移器、寄存器以及相應(yīng)控制邏 (3)針對以下3種情況：(a)沒有乘法指令；(b)有使用ALU和位移器實現(xiàn)的乘法 (4)n位整數(shù)乘法指令可保存2n位乘積，當(dāng)僅取低n位作為乘積時，其結(jié)果可能會到的x*y的2n位乘積分別是什么(用十六進制表示)？此時函數(shù)umul()和imul()的 (1)乘法運算也可以通過加法操作和移位操作實現(xiàn) (2)實現(xiàn)相加和移位的控制 (3)最長：a最短：ca)情況下執(zhí)行時間最長，需要利用其他指令來實現(xiàn)乘法功能c)情況使用陣列乘法器做并行乘法運算，時間顯然最快 FFEHFFFFFFFEH44.假定主存地址為32位，按字節(jié)編址，指令Cache和數(shù)據(jù)Cache與主存之間均采用8B各為32KB。開始時Cache均為空，請回答下列問題： (1)Cache每一行中標(biāo)記(Tag)、LRU位各占幾位？是否有修改位？ (2)有如下C語言程序段：for(k=0;k<1024;k++)Sk2*s[k];組s在主存中的起始地址為008000C0H，則該程序段執(zhí)行過程中，訪問數(shù)組S的數(shù) (3)若CPU最先開始的訪問操作是讀取主存單元0001003H中的指令，簡要說明從 其中6位為塊內(nèi)地址32–6–6=20位修改位 (2)在該程序的執(zhí)行過程中，產(chǎn)生一次缺失時會更新Cache中的16塊，之后的15CacheCacheK的范圍 CPU訪指的大致過程：e存，并把此字所在的一塊一次性從主存調(diào)入Cache，若此時Cache已滿，就根RUCache45.現(xiàn)有5個操作A、