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

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

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

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

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

）。A先序遍歷

B中序遍歷

C后序遍歷

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