2022四川大學(xué)874考研真題-2023修改整理

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁(yè)/共2頁(yè)精品文檔推薦2022四川大學(xué)874考研真題2022年攻讀碩士學(xué)位討論生入學(xué)考試試題考試科目:計(jì)算機(jī)科學(xué)專業(yè)基礎(chǔ)綜合

科目代碼:874

（試題共8頁(yè)）（答案必需寫在答題紙上，寫在試題上不給分）

數(shù)據(jù)結(jié)構(gòu)與算法（65分）

一、單項(xiàng)挑選題（每小題2分，共17小題，共34分

1.下面關(guān)于“算法”的描述，錯(cuò)誤的是（）

A.算法必需是正確的

B.算法必需要能夠結(jié)束

C.一個(gè)問(wèn)題可以有多種算法解決

D.算法的某些步驟可以有二義性

2.下面函數(shù)的時(shí)光復(fù)雜度是（）

voidfunc(intn){

intsum＝0,i,j;

for(i＝1;i,,,

,,,,,,}，則G的一個(gè)拓?fù)湫蛄校ǎ?/p>

A.V1，V3，V2，V6，V4，V5，V7

B.V1，V3，V4，V6，V2，V5，V7

C.V1，V3，V4，V5，V2，V6，V7

D.V1，V2，V5，V3，V4，V6，V7

13.采納Kruskal算法求右圖的最小生成樹時(shí)，

依次挑選的邊是（）

A.(a,b)(b,c)(c,d)(d,f)(a,e)

B.(d,f)(c,d)(b,c)(a,b)(a,e)

C.(a,b)(b,c)(d,f)(c,d)(a,d)

D.(a,b)(d,f)(b,c)(c,d)(a,e)

14.設(shè)哈希表長(zhǎng)為13，哈希函數(shù)是H（key）=key％13，表中已有關(guān)鍵字18，39，75，93共四個(gè)，現(xiàn)要將關(guān)鍵字為70的結(jié)點(diǎn)加到表中，用偽隨機(jī)探測(cè)再散列法解決矛盾，使用的偽隨機(jī)序列為5，8，3，9，7，1，6，4，2，11，13，21則放入的位置是（

A.8

B.11

C.7

D.5

15.一棵高度為3的3階B樹，至少含有（）個(gè)關(guān)鍵字

A.12

B.10

C.7

D.都不是

16.在下列排序算法中，哪一個(gè)算法的時(shí)光復(fù)雜度與數(shù)據(jù)的初始羅列無(wú)關(guān)（）

A.直接插入排序

B.希爾排序

C.迅速排序

D.基數(shù)排序

17.數(shù)據(jù)表中有10000個(gè)元素，假如僅要求求出最大的3個(gè)元素，則采納（）算法最節(jié)約時(shí)光

A.堆排序

B.希爾排序

C.迅速排序

D.直接挑選排序

二、綜合應(yīng)用題（18-20題，共31分

18.（10分）對(duì)于一個(gè)字符集中具有不同權(quán)值的字符舉行Huffman編碼時(shí)，假如已知某個(gè)字符的Huffman編碼為0101，對(duì)于其他無(wú)字符的Huffman編碼，請(qǐng)分析說(shuō)明:（1）具有哪些特征的編碼是不行能的

（2）具有哪些特征的編碼是一定會(huì)有的

19.（10分）設(shè)有向圖用鄰接表表示，圖有n個(gè)頂點(diǎn)，表示為0至n-1，試寫一個(gè)算法求頂點(diǎn)k的入度（0＜＝k＜n）

20.（11分）二叉樹結(jié)點(diǎn)的平衡因子（bf）定義為該結(jié)點(diǎn)的左子樹高度與右子樹高度之差。設(shè)二叉樹結(jié)點(diǎn)結(jié)構(gòu)為：(lchild,data,bf,rchild)，child，rchild左右兒子指針；data是數(shù)據(jù)元素；bf是平衡因子，編寫遞歸算法計(jì)算二叉樹中各個(gè)結(jié)點(diǎn)的平衡因子。

操作系統(tǒng)（50分）

一.單項(xiàng)挑選題（26分，每題2分）

1.假如一個(gè)程序被多個(gè)進(jìn)程分享，那么該程序的代碼在執(zhí)行過(guò)程中不能被修改，即程序應(yīng)當(dāng)是？

A可執(zhí)行碼B可重入碼

C可轉(zhuǎn)變碼D可再現(xiàn)碼

2.當(dāng)被堵塞進(jìn)程所期盼的大事浮現(xiàn)時(shí)，如I/0操作完成或等待的數(shù)據(jù)到達(dá)，則調(diào)用喚醒原語(yǔ)操作，將被堵塞的進(jìn)程喚醒請(qǐng)問(wèn)喚醒被堵塞進(jìn)程的是？

A.被堵塞進(jìn)程的父進(jìn)程

B.被堵塞進(jìn)程的子進(jìn)程

C.被堵塞進(jìn)程自身

D.與被堵塞進(jìn)程相關(guān)的進(jìn)程或其他進(jìn)程

3.某基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的計(jì)算機(jī)，其主存的容量為55MB，這些空間在初始為空閑。采納最佳分配算法，分配和釋放的挨次分離為:分配15MB、分配30MB、釋放15MB、分配8MB、分配6MB，此時(shí)主存中最大空閑分區(qū)的大小是？

A7M

BB9MB

C10MB

D15MB

4.關(guān)于DMA（DirectMemoryAccess），下列說(shuō)法哪個(gè)是正確的？

A.進(jìn)程可以直接讀寫一個(gè)外部設(shè)各

B.內(nèi)核可以直接讀寫進(jìn)程的內(nèi)存而不需要緩沖區(qū)

C.進(jìn)程可以直接讀寫內(nèi)核內(nèi)存而不需要緩沖區(qū)

D.外部設(shè)備可以直接讀寫系統(tǒng)內(nèi)存

5.當(dāng)一個(gè)程序被裝入內(nèi)存預(yù)備開頭執(zhí)行時(shí)，下面哪個(gè)段的大小是操作系統(tǒng)不知道的？

A.text

B.data

C.bss

D.heap

6.假設(shè)某系統(tǒng)中的TLB的命中率大約為75％，并且使用了2級(jí)頁(yè)表，那么平均內(nèi)存時(shí)光為？

A.大約是本來(lái)的1.25倍

B.大約是本來(lái)的1.5倍

C.大約是本來(lái)的1.75倍

D.大約是本來(lái)的2倍

7.在動(dòng)態(tài)分區(qū)存儲(chǔ)系統(tǒng)中，空閑表的內(nèi)容如下:

空閑塊號(hào)1234

塊大小80755590

塊的基址60150250350

此時(shí)，進(jìn)程P哀求50KB內(nèi)存，系統(tǒng)從第1個(gè)空閑塊開頭查找，結(jié)果把第4個(gè)空閑塊分配給了進(jìn)程P。請(qǐng)問(wèn)系統(tǒng)是采納哪種分區(qū)別配算法實(shí)現(xiàn)這一計(jì)劃？

A首次適應(yīng)法B最佳適應(yīng)法

C最差適應(yīng)法D下次適應(yīng)法

8.某系統(tǒng)使用32位規(guī)律地址，頁(yè)大小為4kbytes，以及36位物理地址。那么該系統(tǒng)中的頁(yè)表大小為？

A.2^20個(gè)頁(yè)表項(xiàng)(2^(32-12)

B.2^24個(gè)頁(yè)表項(xiàng)(2^(36-12))

C.2^4個(gè)頁(yè)表項(xiàng)(2^(36-32))

D.2^12個(gè)頁(yè)表項(xiàng)

9.在上下文切換期間，操作系統(tǒng)做了以下哪項(xiàng)工作？

A修改了頁(yè)表中的某些項(xiàng)，以反映新進(jìn)程的內(nèi)存映射

B切換頁(yè)表寄存器指向另外的頁(yè)表

C為新進(jìn)程修改頁(yè)表中的拜訪權(quán)限

D由于頁(yè)表是系統(tǒng)級(jí)別的資源，所以并不會(huì)修改頁(yè)表

10.下列選項(xiàng)中，降低進(jìn)程優(yōu)先權(quán)級(jí)的合理時(shí)機(jī)是？

A、進(jìn)程的時(shí)光片用盡

B、進(jìn)程剛完成I/0，進(jìn)入就緒列隊(duì)

C、進(jìn)程長(zhǎng)久處于就緒列隊(duì)

D、進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)

11.設(shè)與某資源相關(guān)聯(lián)的信號(hào)量初值為3，當(dāng)前值為1，若M表示該資源的可用個(gè)數(shù)，N表示等待該資源的進(jìn)程數(shù)，則M，N分離是？

A.0，1

B.1，0

C.1，2

D.2，0

12.有以哀求分頁(yè)的存儲(chǔ)管理系統(tǒng)，頁(yè)面大小為100B，有一個(gè)50×50的整型數(shù)組，按行為主序延續(xù)存放，每個(gè)整數(shù)占2B，將數(shù)組初始化為0的程序描述如下:

intA(50)(50);

for(inti=0;i<50;i++)

for(intj=0;j<50;j++)

A(i,j)＝0;

若在程序執(zhí)行時(shí)內(nèi)存惟獨(dú)一個(gè)存儲(chǔ)塊用來(lái)存放數(shù)組信息，試問(wèn)該程序執(zhí)行時(shí)產(chǎn)生多少次缺頁(yè)中斷？

A.1

B.50

C.100

D.2500

13.某文件中共有3個(gè)記錄，每個(gè)記錄占用1個(gè)磁盤塊，在1次讀文件的操作中，為了讀出最后1個(gè)記錄，不得不讀出了其他的2個(gè)記錄。按照這個(gè)狀況可知這個(gè)文件所采納的結(jié)構(gòu)是？

A挨次結(jié)構(gòu)B鏈接結(jié)構(gòu)

C索引結(jié)構(gòu)D挨次結(jié)構(gòu)或銜接結(jié)構(gòu)

二.綜合題（24分，每題8分）

1.設(shè)文件索引節(jié)點(diǎn)中有8個(gè)地址項(xiàng)，其中4個(gè)地址為直接地址索引，2個(gè)地址項(xiàng)是一級(jí)間接地址索引，2個(gè)地址項(xiàng)是二級(jí)間接地址索引，每個(gè)地址項(xiàng)的大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，計(jì)算可表示的單個(gè)文件最大長(zhǎng)度。（8分）

2.已知某系統(tǒng)頁(yè)面長(zhǎng)4K字節(jié)，頁(yè)表項(xiàng)4字節(jié)，采納多層分頁(yè)策略映射64位虛擬地址空間。若限定最高層頁(yè)表占1頁(yè)。問(wèn)它可以采納幾層分頁(yè)策略。（8分）

3.有一只球框，最多可以容納兩個(gè)球。每次只能放入或取出一個(gè)球男老師特地向框中放入白球(wb)，女老師特地向框中放入黑球(bb)。男生特地拿框中的白球(wb)，女生拿框中的黑球(bb)。請(qǐng)用Wait，Signal操作實(shí)現(xiàn)男老師，女老師，男生，女生之間的同步關(guān)系。（8分）

計(jì)算機(jī)網(wǎng)絡(luò)（共35分）

一、挑選題（每題2分，共9題，18分）

1關(guān)于ARPANET特征的描述中，不正確的是（）

A.ARPANET的勝利運(yùn)行證實(shí)了交換理論的正確性

B.ARPANETInternet的基礎(chǔ)

C.Web服務(wù)的浮現(xiàn)促進(jìn)了ARPANET的進(jìn)展

D.ARPANET采納的是TCP/IP標(biāo)準(zhǔn)

2.假如發(fā)送數(shù)據(jù)比特序列為11110011，生成多項(xiàng)式比特序列為11001，那么發(fā)送辦法給接收方的比特序列為（）

A.111100110001

B.111100111100

C.1111001111001

D.111100111110

3.IP分組分片基本辦法中，描述錯(cuò)誤的是（）

A.IP分組長(zhǎng)度大于MTU時(shí)，就必需對(duì)IP分組舉行分片

B.DF＝1，分組的長(zhǎng)度超過(guò)MTU，則丟棄分組，不需要向源主機(jī)報(bào)告

C.分片MF值為1表示接收的分片不是最后一個(gè)分片

D.片偏移值是以8字節(jié)為單位來(lái)計(jì)數(shù)的

4.如果有一個(gè)公司有一個(gè)A類IP地址，本來(lái)內(nèi)部有700個(gè)子網(wǎng)，公司重組之后需要再建450個(gè)子網(wǎng)，而且要求每個(gè)子網(wǎng)最多可以容納4092臺(tái)主機(jī)，含適的子網(wǎng)掩碼是（）

A./16

B./17

C./18

D./19

5、以下關(guān)于TCP支持牢靠傳輸服務(wù)的描述中，錯(cuò)誤的是（）

A.TCP使用確認(rèn)機(jī)制來(lái)檢查數(shù)據(jù)是否平安和完整地到達(dá)，并提供擁塞控制功能

B.TCP對(duì)發(fā)送和接收的數(shù)據(jù)舉行跟蹤、確認(rèn)和重傳，以保證數(shù)據(jù)能夠到達(dá)接收端

C.TCP能夠通過(guò)校驗(yàn)和來(lái)保證傳輸?shù)睦慰啃?/p>

D.TCP采納滑動(dòng)窗口辦法舉行流量控制。

6.假如子網(wǎng)掩碼為，那么下列地址的主機(jī)中必需通過(guò)路由器才干夠與主機(jī)通信的是（）

A.2

B.7

C.60

D.21

7.一臺(tái)交換機(jī)具有24個(gè)10/100Mbps的端口和兩個(gè)1Gbps端口，假如全部端口都工作在全雙工狀態(tài)，那么交換機(jī)的最大帶寬為（）

A.4.4G

B.6.4G

C.6.8G

D.8.8G

8.在MAC協(xié)議中，對(duì)正確接收的數(shù)據(jù)幀舉行確認(rèn)的是（

A.CDMA

B.CSMA

C.CSMA/CD

D.CSMA/CA

9.在對(duì)OSI參考模型中第n層與n＋1層關(guān)系的描述中，正確的是（）

A.第n-1層為第n層提供服務(wù)

B.第n層和n＋1層之間是互相自立的

C.第n層利用n＋1層提供的服務(wù)為n-1層提供服務(wù)

D.第n＋1層為從n層接收的數(shù)據(jù)添加一個(gè)頭部

二、計(jì)算題（共17分）

（8分）1.按照?qǐng)D1所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及地址，請(qǐng)寫出R1的路由表，其中R1有兩個(gè)接口m1和m0，路由表形式如下表所示。（要求R1的路由表的表項(xiàng)在滿足路由狀況下，盡可能精簡(jiǎn)）

圖1拓?fù)浣Y(jié)構(gòu)

（9分）2.假設(shè)把一個(gè)大小為3000bit的數(shù)據(jù)報(bào)從源主機(jī)發(fā)送到目的主機(jī)，中間經(jīng)過(guò)4個(gè)路由器，共5段鏈路。每條鏈路的傳輸速率是1Mbps，每條鏈路的傳揚(yáng)時(shí)延都是1ms，忽視隊(duì)列時(shí)延和處理時(shí)延。

（1