848 計算機基礎(chǔ)綜合-暨南大學(xué)2023年招收攻讀碩士學(xué)位研究生入學(xué)考試試題

考試科目：計算機基礎(chǔ)綜合共7頁，第頁2023年招收攻讀碩士學(xué)位研究生入學(xué)考試試題（A）********************************************************************************************招生專業(yè)與代碼：試卷內(nèi)容結(jié)構(gòu)1.操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、C語言程序設(shè)計客觀題2.操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、C語言程序設(shè)計主觀題報考010信息科學(xué)技術(shù)學(xué)院下述4個專業(yè)的考生請選擇操作系統(tǒng)和數(shù)據(jù)結(jié)構(gòu)作答081201計算機系統(tǒng)結(jié)構(gòu)081202計算機軟件與理論081203計算機應(yīng)用技術(shù)085400電子信息(專業(yè)學(xué)位)下設(shè)02(全日制)計算機技術(shù)報考044智能科學(xué)與工程學(xué)院下述2個專業(yè)的考生請選擇數(shù)據(jù)結(jié)構(gòu)和C語言程序設(shè)計作答0812Z3人工智能085400電子信息(專業(yè)學(xué)位)下設(shè)01(全日制)人工智能報考063珠海研究院下述1個專業(yè)的考生請選擇數(shù)據(jù)結(jié)構(gòu)和C語言程序設(shè)計作答085400電子信息(專業(yè)學(xué)位)下設(shè)01(非全日制)人工智能考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。第一部分客觀題一、單項選擇題(第1-20題，每小題1分，第21-30題，每小題2分，1-10題為操作系統(tǒng)部分，11-20題為數(shù)據(jù)結(jié)構(gòu)部分，21-30題為C語言程序設(shè)計部分)1-10操作系統(tǒng)部分1.下列關(guān)于管道（Pipe）通信的敘述中，正確的是()。A.一個管道可實現(xiàn)雙向數(shù)據(jù)傳輸B.管道的容量僅受磁盤容量大小限制C.進程對管道進行讀操作和寫操作都可能被阻塞D.一個管道只能有一個讀進程或一個寫進程對其操作2.避免死鎖的一個著名的算法是()。A.先入先出法B.銀行家算法C.優(yōu)先級算法D.資源按序分配法3.在9個生產(chǎn)者，6個消費者共享容量為8的緩沖區(qū)的生產(chǎn)者-消費者問題中，互斥使用緩沖區(qū)的信號量S的初始值為（）。A.8B.1C.9D.64.一種既有利于短小作業(yè)又兼顧到長作業(yè)的作業(yè)調(diào)度算法是（）。A.先來先服務(wù)B.輪轉(zhuǎn)C.最高響應(yīng)比優(yōu)先D.均衡調(diào)度5.分布式操作系統(tǒng)與網(wǎng)絡(luò)操作系統(tǒng)本質(zhì)上的不同在于（）。A.實現(xiàn)各臺計算機之間的通信B.共享網(wǎng)絡(luò)中的資源C.滿足較大規(guī)模的應(yīng)用D.系統(tǒng)中若干臺計算機相互協(xié)作完成同一任務(wù)6.假定磁盤塊的大小為1K，對于1.2MB的軟盤，F(xiàn)AT需占用（）的存儲空間A.1KBB.1.5KBC.1.8KBD.2.4KB7.關(guān)于線程以下的說法正確的是（）。A.同一進程中各線程可以共享進程的主存空間B.同一進程中多線程不能獨立執(zhí)行C.線程是資源分配的獨立單位 D.線程是就是進程的另外一個稱呼8.正在運行的進程需要向外設(shè)上輸出數(shù)據(jù)，此時進程狀態(tài)從（）。A.等待態(tài)變?yōu)榫途w態(tài)B.運行態(tài)變?yōu)榈却龖B(tài)C.就緒態(tài)變?yōu)檫\行態(tài) D.運行態(tài)變?yōu)榫途w態(tài)9.有10個并發(fā)進程，每個進程對資源的最大需求數(shù)是3，當(dāng)這10個進程共享m個資源時，m值最小?。ǎr不會發(fā)生死鎖。A.3B.20C.30D.1010.當(dāng)分時系統(tǒng)用戶數(shù)為200個，對每個用戶的響應(yīng)時間為1s，時間片最大值是（）。A.5msB.10msC.200msD.0.1s11-20數(shù)據(jù)結(jié)構(gòu)部分11.若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則最節(jié)省運算時間的存儲方式是（）。A.單鏈表

B.僅有頭指針的單循環(huán)鏈表C.雙向鏈表

D.僅有尾指針的單循環(huán)鏈表12.循環(huán)鏈表的主要優(yōu)點是（）。A.不再需要頭指針B.已知某結(jié)點位置后能容易找到其直接前驅(qū)C.在進行插入、刪除操作時能保證鏈表不斷開D.從表中任一結(jié)點出發(fā)都能掃描整個鏈表13.將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為35的結(jié)點的左孩子編號為（）。A.34B.36C.70D.7114.按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種。A.3B.4C.5D.615.任何一個無向連通圖的最小生成樹（）。A.只有一棵B.一棵或多棵

C.一定有多棵D.可能不存在16.深度優(yōu)先遍歷類似于二叉樹的（

）。A先序遍歷

B中序遍歷

C后序遍歷

D層次遍歷17.表達式a*(b+c)-d的后綴表達式是（）。A.abcd+-B.abc+*d-C.abc*+d-D.-+*abcd18.如果無向圖G必須進行兩次廣度優(yōu)先搜索才能訪問其所有頂點，則下列說法中不正確的是（）。A.G肯定不是完全圖B.G中一定有回路C.G一定不是連通圖D.G有2個連通分量19.算法的時間復(fù)雜度不是O(nlogn)的算法是（）。A、快速排序 B.歸并排序 C.堆排序 D.基數(shù)排序20.用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常采用（）來實現(xiàn)算法。A.棧B.隊列C.樹D.圖21-30C語言程序設(shè)計部分21.下列哪一項是C語言合法標識符（）。intextern17_num_1000_a22.已定義整型變量i=5，j=9，那么整型變量intk=i/4+1.1*j的值是多少？（）910111223.下列程序的輸出是什么？（）#include<stdio.h>#include<stdio.h>voidswap(intp1,intp2){ int*temp=&p1; p1=p2; p2=*temp;}intmain(void){ inti=1,j=2; swap(i,j); printf("i=%d,j=%d\n",i,j); return0;}i=1,j=2i=2,j=1i=1,j=1i=2,j=224.對于整型數(shù)組a[8]和b[8]，下列說法正確的是哪一項（）a=b是合法的表達式a+1和a+2不能比較大小賦值表達式*(a+1)=*(b+2)是合法的a和&(*(a))的值不同25.已定義整型變量i和j，且i=10，j=++i*3-8，經(jīng)過上述賦值表達式運算之后i和j的值分別是多少？（）i=11,j=25i=10,j=24i=11,j=24i=10,j=2526.如下程序使用關(guān)鍵字static修飾變量i，此時的i是何種變量？staticinti;intmain(void){…}靜態(tài)全局變量靜態(tài)局部變量動態(tài)全局變量動態(tài)局部變量27.對于C語言的格式化輸出，下列語句會得到哪種結(jié)果？（）inti=60;printf("|%-6.3d|",i);|060||060||060||60|28.下列程序的輸出是什么？（）inta[2][3]={0,0,1,1,2,2};int(*p)[3]=a;printf("%d",++(*((*(p+1))+2)));012329.在定義int(*p)[8]中，p表示什么？（）p為函數(shù)指針p是包含8個整形指針的數(shù)組p是指向由8個元素構(gòu)成的一維數(shù)組的指針p為指向整型變量的指針30.對于循環(huán)for(inti=1;i<n;i++)，其循環(huán)體的執(zhí)行次數(shù)為下列哪一項？（）n-2n-1nn+1二、判斷題(每小題1分，正確的寫True，錯誤的寫False，1-10題為操作系統(tǒng)部分，11-20題為數(shù)據(jù)結(jié)構(gòu)部分，21-30題為C語言程序設(shè)計部分)1-10操作系統(tǒng)部分1.根據(jù)死鎖定理，資源分配圖中存在環(huán)路，就一定會產(chǎn)生死鎖。2.虛擬存儲器的容量是由用戶和輔存所決定的。3.阻塞隊列可能包含系統(tǒng)進程。4.只要破壞產(chǎn)生死鎖的四個必要條件中的其中一個就可以預(yù)防死鎖的發(fā)生。5.優(yōu)化文件物理塊的分布可顯著地減少尋道時間，因此能有效地提高磁盤I/O的速度。6.字符設(shè)備指的是只能存取文本符號的設(shè)備。7.在用于同步時，信號量的初值設(shè)為負數(shù)表示缺少的資源個數(shù)。8.分時系統(tǒng)的時間片越小，響應(yīng)速度越快，因此用戶的滿意度就越高。9.在內(nèi)存利用率方面，分頁存儲管理比分段存儲管理更高些。10.任何手段都無法實現(xiàn)計算機系統(tǒng)資源之間的互換。11-20數(shù)據(jù)結(jié)構(gòu)部分11.在一棵二叉樹中，中序遍歷的第一個結(jié)點，是二叉樹的最左下結(jié)點。12.順序表查找指的是在順序存儲結(jié)構(gòu)上進行查找。13.已知一顆二叉樹的先序序列和后序序列，一定能構(gòu)造出該樹。14.在一棵樹中，堂兄弟的雙親是兄弟關(guān)系。15.不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。16.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。17.分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。18.一個圖按廣度優(yōu)先遍歷的結(jié)果是唯一的。19.由樹轉(zhuǎn)化為二叉樹，該二叉樹的右子樹不一定為空。20.無向圖的鄰接矩陣是對稱的，因此可只存儲矩陣的下三角陣。21-30C語言程序設(shè)計部分21.C語言中，++運算符適用于float類型的變量，即如有定義floata，那么a++是合法的。22.結(jié)構(gòu)體各個成員變量之間的地址都是相同的。23.在C語言中，常量沒有數(shù)據(jù)類型。24.整型指針變量和字符型指針變量所占用的內(nèi)存大小相同。25.二進制文件比ASCII文件占用更多的存儲空間。26.局部變量一定存放在靜態(tài)存儲區(qū)。27.算數(shù)運算符的優(yōu)先級高于關(guān)系運算符。28.除了注釋以外，一段程序中的“{”和“}”的數(shù)量必須相同。29.以下程序的輸出為0。inta=0;if(a=1)printf("%d",a);elseprintf("0");30.C語言動態(tài)分配的存儲區(qū)域被稱為堆區(qū)。三、填空題（第1-10空，每空1分，第11-15空，每空2分，1-9題為操作系統(tǒng)部分，10-14題為數(shù)據(jù)結(jié)構(gòu)部分）1-9操作系統(tǒng)部分1.為實現(xiàn)CPU與外部設(shè)備的并行工作,系統(tǒng)必須引入（1）作為硬件基礎(chǔ)。2.在磁盤調(diào)度策略中有可能使I/O請求無限期等待的調(diào)度算法是（2）。3.在（3）的作業(yè)調(diào)度算法中，當(dāng)各個作業(yè)等待時間相同時，運行時間短的作業(yè)將得到優(yōu)先調(diào)度；當(dāng)各個作業(yè)要求運行的時間相同時，等待時間長的作業(yè)得到優(yōu)先調(diào)度。4.UNIX的文件系統(tǒng)空閑空間的管理采用的是（4）法。5.同步機制要遵循的四條規(guī)則分別是空閑讓進、忙則等待、（5）及讓權(quán)等待。6.文件的三種物理結(jié)構(gòu)是：順序結(jié)構(gòu)、（6）、索引結(jié)構(gòu)。7.分時系統(tǒng)的特點是：（7）、交互性、獨占性和及時性。8.虛擬存儲器的特征是：（8）、多次性、對換性和虛擬性。9.n個進程共享m個同類資源(n≥m≥1,設(shè)信號量初值S=m)，S的值可能的變化范圍是（9），處于等待狀態(tài)的進程數(shù)最多有（10）個。10-14數(shù)據(jù)結(jié)構(gòu)部分10．一組記錄的排序碼為(45，35，71，51，20，26，61，12)，則利用快速排序的方法，以第一個記錄為基準得到的第一次劃分結(jié)果為（11）。11．在折半查找中，要求待查找的關(guān)鍵字序列必須（12），這樣才能進行查找操作。12．設(shè)二叉樹中度為0的結(jié)點數(shù)為30，度為1的結(jié)點數(shù)為20，則該二叉樹中總共有（13）個結(jié)點數(shù)。13．設(shè)矩陣是一個N×N對稱矩陣，將其下三角部分按行序存放在一維數(shù)組中，對下三角部分中任一元素Aij(i>=j)，在一維數(shù)組中的下標位置k與i和j的關(guān)系為（14）。14．在N個結(jié)點的線索二叉樹中線索的數(shù)目為（15）。第二部分操作系統(tǒng)主觀題舉例說明什么是實時系統(tǒng)中的優(yōu)先級反轉(zhuǎn)(或倒轉(zhuǎn))。(5分)試比較內(nèi)存管理和外存管理的異同點。(5分)簡述設(shè)備驅(qū)動程序的主要功能。(5分)采取哪些措施才能提高文件檢索的速度。(5分)八、fork為創(chuàng)建進程的系統(tǒng)調(diào)用，下面的程序創(chuàng)建多少個子進程?輸出多少個A和B?(5分)intmain(void){inti;for(i=0;i<3;i++){if(fork()==0)printf("A");}printf(“B\n”);}九、一座小橋橫跨南北兩岸，南側(cè)橋段和北側(cè)橋段較窄只能通過一人，橋中央一處寬敞，允許兩個人通過或歇息。南側(cè)橋段和北側(cè)橋段在任意時刻只允許一人過橋。請寫出從北岸到南岸過橋的同步算法。(10分)十、某系統(tǒng)的文件物理結(jié)構(gòu)采用多級索引結(jié)構(gòu)。索引結(jié)點共設(shè)置13個地址項，其中0到9項為直接地址項，后3項分別為一級、二級、三級間接地址。邏輯塊和物理塊大小均為1K字節(jié)，磁盤盤塊地址占16位。(10分)（1）請畫出該文件系統(tǒng)文件索引結(jié)構(gòu)示意圖。（2）列出計算該文件系統(tǒng)允許的最大文件的長度計算表達式。（3）讀取一個長256256字節(jié)的文件的全部數(shù)據(jù)，共需讀盤多少次？第三部分數(shù)據(jù)結(jié)構(gòu)主觀題十一、設(shè)一組初始記錄關(guān)鍵字序列為（41，35，52，17，8，50，22，38），請分別給出第5趟簡單選擇排序和第4趟直接插入排序的結(jié)果。（5分）十二、設(shè)計一數(shù)據(jù)結(jié)構(gòu)，用來表示圖的鄰接矩陣存儲結(jié)構(gòu)（包括弧的結(jié)構(gòu)和圖的結(jié)構(gòu)）。(5分)十三、閱讀下面的程序代碼，寫出此函數(shù)的功能。(5分)voidF(BitreeT,Stack&S){if(T){Push(S,T->data);if(!T->Lchild&&!T->Rchild)PrintStack(S);else{F(T->Lchild,S);F(T->Rchild,S);}Pop(S);}}十四、假設(shè)表中關(guān)鍵字序列為（41，36，58，12，79，25），將關(guān)鍵字依次插入一棵初始為空的二叉排序樹，然