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

科目代碼:874

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

數據結構與算法（65分）

一、單項挑選題（每小題2分，共17小題，共34分

1.下面關于“算法”的描述，錯誤的是（）

A.算法必需是正確的

B.算法必需要能夠結束

C.一個問題可以有多種算法解決

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

2.下面函數的時光復雜度是（）

voidfunc(intn){

intsum＝0,i,j;

for(i＝1;i,,,

,,,,,,}，則G的一個拓撲序列（）

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算法求右圖的最小生成樹時，

依次挑選的邊是（）

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.設哈希表長為13，哈希函數是H（key）=key％13，表中已有關鍵字18，39，75，93共四個，現要將關鍵字為70的結點加到表中，用偽隨機探測再散列法解決矛盾，使用的偽隨機序列為5，8，3，9，7，1，6，4，2，11，13，21則放入的位置是（

A.8

B.11

C.7

D.5

15.一棵高度為3的3階B樹，至少含有（）個關鍵字

A.12

B.10

C.7

D.都不是

16.在下列排序算法中，哪一個算法的時光復雜度與數據的初始羅列無關（）

A.直接插入排序

B.希爾排序

C.迅速排序

D.基數排序

17.數據表中有10000個元素，假如僅要求求出最大的3個元素，則采納（）算法最節約時光

A.堆排序

B.希爾排序

C.迅速排序

D.直接挑選排序

二、綜合應用題（18-20題，共31分

18.（10分）對于一個字符集中具有不同權值的字符舉行Huffman編碼時，假如已知某個字符的Huffman編碼為0101，對于其他無字符的Huffman編碼，請分析說明:（1）具有哪些特征的編碼是不行能的

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

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

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

操作系統（50分）

一.單項挑選題（26分，每題2分）

1.假如一個程序被多個進程分享，那么該程序的代碼在執行過程中不能被修改，即程序應當是？

A可執行碼B可重入碼

C可轉變碼D可再現碼

2.當被堵塞進程所期盼的大事浮現時，如I/0操作完成或等待的數據到達，則調用喚醒原語操作，將被堵塞的進程喚醒請問喚醒被堵塞進程的是？

A.被堵塞進程的父進程

B.被堵塞進程的子進程

C.被堵塞進程自身

D.與被堵塞進程相關的進程或其他進程

3.某基于動態分區存儲管理的計算機，其主存的容量為55MB，這些空間在初始為空閑。采納最佳分配算法，分配和釋放的挨次分離為:分配15MB、分配30MB、釋放15MB、分配8MB、分配6MB，此時主存中最大空閑分區的大小是？

A7M

BB9MB

C10MB

D15MB

4.關于DMA（DirectMemoryAccess），下列說法哪個是正確的？

A.進程可以直接讀寫一個外部設各

B.內核可以直接讀寫進程的內存而不需要緩沖區

C.進程可以直接讀寫內核內存而不需要緩沖區

D.外部設備可以直接讀寫系統內存

5.當一個程序被裝入內存預備開頭執行時，下面哪個段的大小是操作系統不知道的？

A.text

B.data

C.bss

D.heap

6.假設某系統中的TLB的命中率大約為75％，并且使用了2級頁表，那么平均內存時光為？

A.大約是本來的1.25倍

B.大約是本來的1.5倍

C.大約是本來的1.75倍

D.大約是本來的2倍

7.在動態分區存儲系統中，空閑表的內容如下:

空閑塊號1234

塊大小80755590

塊的基址60150250350

此時，進程P哀求50KB內存，系統從第1個空閑塊開頭查找，結果把第4個空閑塊分配給了進程P。請問系統是采納哪種分區別配算法實現這一計劃？

A首次適應法B最佳適應法

C最差適應法D下次適應法

8.某系統使用32位規律地址，頁大小為4kbytes，以及36位物理地址。那么該系統中的頁表大小為？

A.2^20個頁表項(2^(32-12)

B.2^24個頁表項(2^(36-12))

C.2^4個頁表項(2^(36-32))

D.2^12個頁表項

9.在上下文切換期間，操作系統做了以下哪項工作？

A修改了頁表中的某些項，以反映新進程的內存映射

B切換頁表寄存器指向另外的頁表

C為新進程修改頁表中的拜訪權限

D由于頁表是系統級別的資源，所以并不會修改頁表

10.下列選項中，降低進程優先權級的合理時機是？

A、進程的時光片用盡

B、進程剛完成I/0，進入就緒列隊

C、進程長久處于就緒列隊

D、進程從就緒狀態轉為運行狀態

11.設與某資源相關聯的信號量初值為3，當前值為1，若M表示該資源的可用個數，N表示等待該資源的進程數，則M，N分離是？

A.0，1

B.1，0

C.1，2

D.2，0

12.有以哀求分頁的存儲管理系統，頁面大小為100B，有一個50×50的整型數組，按行為主序延續存放，每個整數占2B，將數組初始化為0的程序描述如下:

intA(50)(50);

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

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

A(i,j)＝0;

若在程序執行時內存惟獨一個存儲塊用來存放數組信息，試問該程序執行時產生多少次缺頁中斷？

A.1

B.50

C.100

D.2500

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

A挨次結構B鏈接結構

C索引結構D挨次結構或銜接結構

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

1.設文件索引節點中有8個地址項，其中4個地址為直接地址索引，2個地址項是一級間接地址索引，2個地址項是二級間接地址索引，每個地址項的大小為4字節，若磁盤索引塊和磁盤數據塊大小均為256字節，計算可表示的單個文件最大長度。（8分）

2.已知某系統頁面長4K字節，頁表項4字節，采納多層分頁策略映射64位虛擬地址空間。若限定最高層頁表占1頁。問它可以采納幾層分頁策略。（8分）

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

計算機網絡（共35分）

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

1關于ARPANET特征的描述中，不正確的是（）

A.ARPANET的勝利運行證實了交換理論的正確性

B.ARPANETInternet的基礎

C.Web服務的浮現促進了ARPANET的進展

D.ARPANET采納的是TCP/IP標準

2.假如發送數據比特序列為11110011，生成多項式比特序列為11001，那么發送辦法給接收方的比特序列為（）

A.111100110001

B.111100111100

C.1111001111001

D.111100111110

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

A.IP分組長度大于MTU時，就必需對IP分組舉行分片

B.DF＝1，分組的長度超過MTU，則丟棄分組，不需要向源主機報告

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

D.片偏移值是以8字節為單位來計數的

4.如果有一個公司有一個A類IP地址，本來內部有700個子網，公司重組之后需要再建450個子網，而且要求每個子網最多可以容納4092臺主機，含適的子網掩碼是（）

A./16

B./17

C./18

D./19

5、以下關于TCP支持牢靠傳輸服務的描述中，錯誤的是（）

A.TCP使用確認機制來檢查數據是否平安和完整地到達，并提供擁塞控制功能

B.TCP對發送和接收的數據舉行跟蹤、確認和重傳，以保證數據能夠到達接收端

C.TCP能夠通過校驗和來保證傳輸的牢靠性

D.TCP采納滑動窗口辦法舉行流量控制。

6.假如子網掩碼為，那么下列地址的主機中必需通過路由器才干夠與主機通信的是（）

A.2

B.7

C.60

D.21

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

A.4.4G

B.6.4G

C.6.8G

D.8.8G

8.在MAC協議中，對正確接收的數據幀舉行確認的是（

A.CDMA

B.CSMA

C.CSMA/CD

D.CSMA/CA

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

A.第n-1層為第n層提供服務

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

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

D.第n＋1層為從n層接收的數據添加一個頭部

二、計算題（共17分）

（8分）1.按照圖1所示的網絡拓撲結構及地址，請寫出R1的路由表，其中R1有兩個接口m1和m0，路由表形式如下表所示。（要求R1的路由表的表項在滿足路由狀況下，盡可能精簡）

圖1拓撲結構

（9分）2.假設把一個大小為3000bit的數據報從源主機發送到目的主機，中間經過4個路由器，共5段鏈路。每條鏈路的傳輸速率是1Mbps，每條鏈路的傳揚時延都是1ms，忽視隊列時延和處理時延。

（1