南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A歷年考研真題匯編

南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院

824計(jì)算機(jī)專業(yè)基礎(chǔ)A歷年考研真題匯編THROUGHTRRIN最新資料，WORD格式，可編輯修改!TOC\o"1-5"\h\z\o"CurrentDocument"2012年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 32011年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 132010年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 222009年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 312008年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 392007年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 502006年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 602005年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 702004年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 782003年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題 862012年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題南京理工大學(xué)2012年碩士學(xué)位斫究生入學(xué)考試試題科目代碼：824 科目名稱：計(jì)算機(jī)專業(yè)基礎(chǔ)（A）滿分：150分注意:①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫在溶畫|上,寫在本試題紙或草稿紙上均無效；③本試題紙須隨答題紙一起裝入試題袋中交回！第一部分離散數(shù)學(xué)（50分）.已知K是4上的自反和對(duì)稱的二元關(guān)系，試證明：（8分）（1）對(duì)于任意的nwW,肥具有對(duì)稱性；（2），（的為4上的等價(jià)關(guān)系..已知48,CO為四個(gè)集合，/為/到3的滿射，g為C到。的滿射，且{cC=3cD=O.h為AkjC至!IBuD的映射，且對(duì)于Vxe/l^C.A（x）=fW^XeA,試證明方為6C到爪。的滿射.（6分）U（x）當(dāng)xwC.彳為一個(gè)集合，試證明i川（6分）.G=（匕E）是一個(gè)簡(jiǎn)單無向平面圖，若|E[<30,則G中至少有一個(gè)頂點(diǎn)的度數(shù)小于等于4.（6分）.G=(匕玲是一個(gè)連通且無圖的圖。若G中僅有兩個(gè)1度頂點(diǎn)，期G可以畫成一條直線.(6分).設(shè)/和g都是群(40到群(8J)的同態(tài)映射，證明(CQ是(46的一個(gè)子群，其中C={x|xe4M/Xx)=g(x)}(6分).把下列語句翻譯為謂詞演算公式(每小題3分，共6分)(1〉任何個(gè)集合X,總存在一個(gè)集合3,使得8的基數(shù)比人的基數(shù)耍大：(2)布.些大學(xué)生喜歡所有的網(wǎng)絡(luò)游戲..已知知識(shí)的表示如下；Ux(P(x)t(4(x)v8(x))) .<2)Vx(N(x)fQ(x))rUx(P(x)T0(x))824計(jì)算機(jī)專業(yè)品端(A)第I頁共6頁結(jié)論：3xU\x)B(x)),貳用歸結(jié)原理證明之“〈6分)第二部分 數(shù)據(jù)結(jié)構(gòu)(共50分)一環(huán)空(每個(gè)空瓶1分，共15分)LAOE網(wǎng)中的關(guān)鍵路徑是LO,.與線性表的麟接存貯方式相比較，線性表的順序存世方式的優(yōu)點(diǎn)於⑵缺一是.131。..二叉樹的先序和中序遍歷序列分別是ABCDEFG,CDBAFEG,則后序遮歷序列是一(4) °.有向圖G=(V,A4其中Vyabcde}.A={<a,b>,<a、c>,<d,c),vdQ,<b,e>,v%e>,<c,b>},清給出的一個(gè)拓?fù)湫蛄校孩伞?在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)征隊(duì)列中，結(jié)點(diǎn)的結(jié)構(gòu)為(da弭next),有指針p指向隊(duì)列最后一個(gè)元素.若第一個(gè)元素出隊(duì)列，則應(yīng)執(zhí)行的操作為：s=p->next->next;(6) .；fiec(s)(free⑸也可以用deletes)?.一棵二叉樹中葉子結(jié)點(diǎn)數(shù)刖和度為2的結(jié)點(diǎn)數(shù)匹之間滿足以下關(guān)系：no=n2+l；一棵滿k叉樹上的葉子結(jié)點(diǎn)數(shù)n°和非四結(jié)點(diǎn)數(shù)n(之同滿足一⑺關(guān)系。1.一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹按層次，(同層次從左向巖)用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的哇子的序號(hào)是_W_:編號(hào)是i的?點(diǎn)斫花的層次號(hào)是一(9)(根所在的層次號(hào)規(guī)定為1層人.有關(guān)鍵字序列為：(20,11.12,9,23,42,44,36)/對(duì)應(yīng)的大頂堆為：10)一;一趟冒泡排序后的序列為：(II)；將序列中的關(guān)鍵字看作權(quán)值，構(gòu)造哈夫曼樹，其帶全路徑長(zhǎng)度為：(⑵。.若某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有304結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的結(jié)，數(shù)是C3），.在無序線索二叉樓中，若P爐指結(jié)點(diǎn)的右孩子域?yàn)楹⒆又竷r(jià)，則P的后繼結(jié)點(diǎn)是（14） ..在B-樹中剁除關(guān)鍵字K,若Ki為并終端結(jié)點(diǎn)中的關(guān)維字,則以 C5）代替心二、（15分）笥答題：設(shè)關(guān)鍵字的輸入序列為{55,31,11,37,46,39}（5分）從空樹開始構(gòu)造平衡二叉樹，畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)，若發(fā)生不平鋤，指明需做的平衡旋轉(zhuǎn)類型及平衡旋轉(zhuǎn)的紹果，《4分）所出1.中二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)，并給出對(duì)該二叉樹進(jìn)行中序遍店的雉出序列.（2分）構(gòu)造一棵二叉排序梃.（4分）畫出在2,中的二叉排序樹服除31后的二叉排序樹，接著再班824計(jì)算機(jī)y業(yè)耳咄（A）第2支共6支除55后的二叉排序樹.三、（】0分）對(duì)給定的有6個(gè)頂點(diǎn)的無向圖的鄰接矩陣如F：.（3分）畫出鄰接表存儲(chǔ)結(jié)構(gòu)：.（2分）畫出該無向圖；.（3分）畫出該圖的最小生成樹；.（2分）給出從V1出發(fā)的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列:8 1260087 8684002686656oo600003qo4600ao7ooao537co四、（10分）用類C（類-C++）寫出如下算法：1.（4分）已知源二叉樹s,將其復(fù)制成另一棵二叉樹t.voidCopyTree（BiTNodes,BiTNodet）二叉樹用二叉鏈表存儲(chǔ)，存儲(chǔ)結(jié)構(gòu)定義為：typedefstructBiTNode{Elemtypedata;structBiTNode,[child,*rchild;}BiTNode,*BiTree;（6分）線性表用單握表存儲(chǔ)，使用盡可能少的存儲(chǔ)空［可將其元素全部顛踮倒。 statusTum（Linklist鏈表有頭結(jié)點(diǎn)單鏈衣的存儲(chǔ)結(jié)構(gòu)定義為：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkLis!;第三部分操作系統(tǒng)（50分）單項(xiàng)選擇題（每題1分，共20分）.當(dāng)沙兜機(jī)區(qū)分了管態(tài)（系統(tǒng)態(tài)）和月態(tài)（用戶態(tài)）指令之后，從管態(tài)到目態(tài)的轉(zhuǎn)換是由操作系統(tǒng)程序執(zhí)行后完成的，而目態(tài)到管態(tài)的轉(zhuǎn)換則是由 完成的.A.硬件 B.管態(tài)程序C.用戶程序 D.中斷處理程序.作業(yè)在執(zhí)行中發(fā)生了缺頁中斷’經(jīng)操作系統(tǒng)處理后，應(yīng)讓其執(zhí)行指令.A.被中斷的前一條 B.被中斷的后一條C..作業(yè)的第一條 D.作業(yè)的最后一條.在用戶程序中將一個(gè)字符送到顯不器上顯示，使用的是操作系統(tǒng)提供的接口.A.系統(tǒng)調(diào)用 B.庫函數(shù)C,原語 D.例理824計(jì)算機(jī)專業(yè)拈裙（A） 第3頁共6克.在文件系統(tǒng)中引入“當(dāng)前目錄”的主要目的是A.方便用戶 B.提高系統(tǒng)性能C.增強(qiáng)系統(tǒng)安全性D.支持共享訪問.為了便于上層軟件的編制，設(shè)備通常需要提供是A.控制寄存器、狀態(tài)寄存器和控制命令I(lǐng)/O地址寄存器、工作方式狀態(tài)寄存器和控制命令C.中斷寄存耦、控制寄存器和控制命令D.控制寄存器、編程空間和控制邏輯寄存春.在批處理操作系統(tǒng)控制下實(shí)現(xiàn)多道程序并行工作,從系統(tǒng)的角度，主要希望進(jìn)入“輸入井”的作業(yè)能夠 ,A.響應(yīng)時(shí)間短 B.平均周轉(zhuǎn)時(shí)間短oC.題務(wù)費(fèi)用低 D.長(zhǎng)作業(yè)優(yōu)先得到服務(wù).并發(fā)進(jìn)程中與共享變是有關(guān)的程序段被稱為臨界區(qū),因此這姐并發(fā)進(jìn)程A.相莖間是有交互的 B.擁有一個(gè)共同的臨界區(qū)C.不能修改共享變量的值 D.執(zhí)行絡(luò)果不受執(zhí)行速度的影響8,采用伸態(tài)分配資源策略可以防止死校,這是因?yàn)?A.破壞了互斥使用貨源的條件 B.系統(tǒng)不會(huì)出現(xiàn)循環(huán)等待資源的現(xiàn)政C.提高了資源利用率 D.能隨時(shí)檢泅資源的使用情況.用戶“實(shí)現(xiàn)按名存取”屬于操作系統(tǒng)中的A.處理那管理 B.存儲(chǔ)管理C.文件管理 D.設(shè)務(wù)管理.進(jìn)程的并發(fā)性是指A.一組進(jìn)程可同時(shí)執(zhí)行B.每個(gè)進(jìn)程的執(zhí)行結(jié)果不受其它進(jìn)程的影響C.每個(gè)進(jìn)程的執(zhí)行都是可再現(xiàn)的D.通過一個(gè)進(jìn)程創(chuàng)建出多個(gè)進(jìn)程.在下列選項(xiàng)中，不屬于造成某進(jìn)程狀態(tài)從等特態(tài)到就緒態(tài)變化的原因是_A.有更高優(yōu)先級(jí)的進(jìn)程要運(yùn)行B.讀進(jìn)程占用的外圍設(shè)備工作結(jié)束C.該進(jìn)程等待的貨源得到滿足D.談進(jìn)程等待干位的故障被排除.某文件共有4個(gè)記錄采用篋接存儲(chǔ)結(jié)構(gòu)，每個(gè)記錄及鏈接指針占用一個(gè)磁盤塊，主存儲(chǔ)器中的磁盤繾沖區(qū)的大小與磁盤塊的大小相哥?為了在L和L，之間插入-個(gè)記錄Lj?（已蛭在內(nèi)存中），需要進(jìn)行的磁盤掾作有一A.4次讀盤和2次寫盤 B.4次讀盤和1次寫盤C.3次讀盤和2次寫盤 D.3次讀盤和I次寫盤13.采用銀行家算法可避免死楨的發(fā)生，這是因?yàn)樵撍惴ˋ,可搶奪已分配的資源B.能及時(shí)為各進(jìn)程分配資源C.任何時(shí)刻都能保證每個(gè)進(jìn)用得到所需的資源D.任何時(shí)刻都能保證至少有個(gè)進(jìn)程可利到所需的全部資源.假定一個(gè)分時(shí)系統(tǒng)允許20個(gè)終端用戶同時(shí)工作?若分配給每個(gè)終端用戶的時(shí)間片為50毫秒,而對(duì)終端用戶的每個(gè)請(qǐng)求需處理200曝秒給出應(yīng)答，那么終潮的最長(zhǎng)響應(yīng)時(shí)間為秒A.1B.2C.3D.4.頁式存儲(chǔ)管理中，作業(yè)運(yùn)行時(shí)，該作業(yè)的頁表是放在 X24H■機(jī)專業(yè)呆哇（A>箍4天共6頁踮A.磁盤B.主存系統(tǒng)區(qū)C.主存用戶區(qū) D.用戶程序.為實(shí)現(xiàn)磁盤空間的分配與回收，UNIX采用的是A.位示圖法B.單塊鏈接法C.成組鏈接法D.索引鏈接法.假設(shè)每條磁道被分為8個(gè)扇區(qū)，每個(gè)扇區(qū)存放一個(gè)記錄，處理程序順序處理這8個(gè)記錄L，L2，…，U.每次請(qǐng)求從磁盤上讀一個(gè)記錄，然后對(duì)讀出的記錄花1ms的時(shí)間進(jìn)行處理，以后再讀下一個(gè)記錄進(jìn)行處理.磁盤旋轉(zhuǎn)一周花費(fèi)16ms（即每讀一個(gè)扇區(qū)需2ms）.若將這8個(gè)記錄在?條磁道上進(jìn)行優(yōu)化分布，則全部處理完這8個(gè)記錄至少需要msA.31B.32C.33D.34.虛擬頁式存儲(chǔ)管理中頁表有若干項(xiàng)，當(dāng)內(nèi)存中某一頁面被淘汰時(shí)，可根據(jù)其中哪一項(xiàng)決定是否將該頁寫回外存.A.是否在內(nèi)存標(biāo)志B.外存地址C.修改標(biāo)志D.訪問標(biāo)志.有一磁盤，共有10個(gè)柱面，每個(gè)柱面20個(gè)磁道，每個(gè)盤面分成16個(gè)扇區(qū).采用位示圖對(duì)其存儲(chǔ)空間進(jìn)行管理.如果字長(zhǎng)是16個(gè)二進(jìn)制位，那么位示圖共需字.A.200B.128C.256 D.100.校友會(huì)的文件系統(tǒng)磁盤庫中，“畢業(yè)生檔案”文件的記錄包含的數(shù)據(jù)項(xiàng)是畢業(yè)年份、身份證號(hào)和在校時(shí)檔案材料.由于各人的檔案信息量不同，記錄的長(zhǎng)度因人而異，但記錄總是先按照畢業(yè)年份，然后按身份證序號(hào)在磁盤中順序存放.使用這個(gè)文件的方式是按畢業(yè)年份和身份證號(hào)快速查出此人的檔案材料.適合這個(gè)文件的邏輯結(jié)構(gòu)是A.順序結(jié)構(gòu) B.準(zhǔn)接結(jié)構(gòu) C.索引結(jié)構(gòu) D.索引順序結(jié)構(gòu)解答題（1-5題每空1分，6題每空2分，共20分）.在具有N個(gè)進(jìn)程的系統(tǒng)中，允許M個(gè)進(jìn)程（NZM21）同時(shí)進(jìn)入它們的共享區(qū),其信號(hào)量s的值的變化范圍是（1）,處于等待狀態(tài)的進(jìn)程數(shù)場(chǎng)多是3個(gè)..假設(shè)某操作系統(tǒng)采用時(shí)間片輪轉(zhuǎn)調(diào)度策略，時(shí)間片大小為100ms,就緒進(jìn)程&列的平均長(zhǎng)度為5,如果在系統(tǒng)中運(yùn)行一個(gè)需要在CPU上執(zhí)行0.8s時(shí)間的程

序，則該程序的平均周轉(zhuǎn)時(shí)間是一□1_.平均等待時(shí)序是（4）.（不考慮10情況）.在頁式虛存管理系統(tǒng)中，設(shè)頁面大小為2\頁表內(nèi)容如卜，現(xiàn)訪問虛地址:（233）8,則將虛地址（233）1t變換成物理地址是（5）.頁表：（表中的數(shù)均為八進(jìn)制）衣號(hào)有效位頁幀號(hào)軸存塊號(hào)001004011517721206304.假定在某動(dòng)臂磁盤匕剛處理了訪問75號(hào)柱前的請(qǐng)求，目前正在74號(hào)柱面上讀信息，且有如下清求序列在等待訪問磁盤; 請(qǐng)求序列12345678欲訪問柱面號(hào)22481931889278156101寫出電梯調(diào)度算法處理時(shí)的序列次序。寫出最短尋找時(shí)間優(yōu)先算法時(shí)處理的時(shí)窗的移動(dòng)方向改變了 （7）次..假定在一個(gè)請(qǐng)求頁式存儲(chǔ)管理系統(tǒng)中，某作業(yè)J所涉及的頁面依次為頁面訪824計(jì)算機(jī)專業(yè)條何（A）第5頁共6女問序歹U：2,3,2』,5,2,45325,2'分配內(nèi)存塊：3塊.采用頁面調(diào)度算法LRU產(chǎn)生缺頁中斷的次數(shù)是優(yōu))，采用FIFO產(chǎn)生缺頁中斷的次數(shù)是(9),采用Clock算法產(chǎn)生歌頁中斷的次數(shù)是一001，.戰(zhàn)地指揮官通過無線電不斷地向他的兩個(gè)士兵下達(dá)作戰(zhàn)指令，但是他必須在得到所有士兵對(duì)前一條指令的“確認(rèn)”之后才能下達(dá)新的指令。使用P、V集作完成指揮官和士兵之間的協(xié)同管理。structsemaphoreSl=(11) .S2-1;cobeginprocess指揮官：beginwhile(true){(⑵：(13):向上兵1發(fā)送指令；O向士兵2發(fā)送指令：}end；process士兵】begin -while<tme){接收指揮官的指令；(14);}end；process士兵2beginwhile(true){接收指揮官的指令：(15J;踮end；coend三.簡(jiǎn)答題(每題5分，共10分).什么是進(jìn)程和線程？應(yīng)用程序可以采用多進(jìn)程實(shí)現(xiàn)，也可以采用多線程實(shí)現(xiàn),試分析這兩種實(shí)現(xiàn)方法對(duì)應(yīng)用程序的運(yùn)行有什么影響？.什么是設(shè)備無關(guān)性？*，4i+flr機(jī)專業(yè)戰(zhàn)砧(A)笫6頁共6頁2011年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題南京理工大學(xué)2011年碩士學(xué)位研究生入學(xué)考試試題科目代碼：824科目名稱：計(jì)算機(jī)專業(yè)基礎(chǔ)(A) 滿分：150分注意：①認(rèn)真閱讀答題紙上的注意事項(xiàng)；②所有答案必須寫在函國上，寫在本試題紙或草稿紙上均無效：③本試題紙須隨答題紙一起裝入試題袋中交回！數(shù)據(jù)結(jié)構(gòu)(共50分)一、填空(每個(gè)空格1.5分，共15分).線性表的兩種存儲(chǔ)方式是和(2)。.用鄰接表表示圖時(shí)，頂點(diǎn)數(shù)為n,邊數(shù)為e,在鄰接表上執(zhí)行圖的深度優(yōu)先遍歷操作時(shí)，時(shí)間復(fù)雜性(3).對(duì)二叉排序樹樹進(jìn)行(4) 遍歷，可以得到樹中數(shù)據(jù)元素的有序序列..由帶權(quán)為3、9、6,2、5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長(zhǎng)度為..棵一叉樹中，度為2的結(jié)點(diǎn)有15個(gè)，度為1的有30個(gè)，則葉子數(shù)有(6)個(gè)。.設(shè)待排序的序列為(48,35,60,13,75,80,26,49}下面是排序過程：TOC\o"1-5"\h\z(48) 35 60 13 75 80 26 49(35 48) 60 13 75 80 26 49(35 48 60) 13 75 80 26 49(4)這一精排序的序列為 (7〉 .7.單鏈表的存儲(chǔ)結(jié)構(gòu)定義為：typedefstructLNode{EletnTypedata;structLNode*next;}LNode,*LinkList;下面是單鏈表的插入算法，請(qǐng)?jiān)诳崭裉幪钊胝_的語句.StatusInsertnode(Link!ist&L,inti,EletnTypee){//L為無頭結(jié)點(diǎn)的鏈表,在第i個(gè)元素結(jié)點(diǎn)前面插入元素e：s=(LinkList)malloc(sizeof(LNode));//分配新結(jié)點(diǎn)824計(jì)算機(jī)專業(yè)基A第I貞共7人s-〉data=e;if((8) ))s->next=L;L=SsreturnOK：)p-L；j=O：while((9))(p=p->next;++j;)〃尋找第i4個(gè)元素結(jié)點(diǎn)if((10))returnERROR：//i小于1或者大于表長(zhǎng)s->next=p->next;p>next=s; 〃插入新結(jié)點(diǎn)returnOK;I//LinstTnsert_L二、簡(jiǎn)答題(15分).分別畫出右圖所示二叉樹的存儲(chǔ)表示：(3分)(1)順序表示；(2)二叉性表表示法；(3)靜態(tài)鏈表表示..對(duì)于下圖的AQE網(wǎng)(12分)(1)填寫下面的2個(gè)表(各2分);(2)事件vlv2v3v4v5v6v7最早發(fā)生時(shí)間最遲發(fā)生時(shí)間活動(dòng)ala2a3a4a5a7aBa9alO及早發(fā)生時(shí)間最遲發(fā)生時(shí)間(2)列出關(guān)鍵活動(dòng)(2分)；(3)忽略圖中的權(quán)值，將圖看成AOE網(wǎng)，寫出圖的3個(gè)拓?fù)湫蛄?3分)；(4)將圖看成無向圖(將圖中的有向邊看成無向邊)，商出最小生成樹(3分)；三、(每題5分，共10分)設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,37,70.29).L逐個(gè)輸入各個(gè)數(shù)據(jù)生成的3階B-樹，畫出過程；2.設(shè)Hash表表長(zhǎng)m=13,選取Hash函數(shù)為H(key)=keyMOD11,處理沖突的方法為“線性探測(cè)再散列",請(qǐng)對(duì)輸入序列構(gòu)造Hash表.四、算法(10分)二叉樹的存儲(chǔ)結(jié)構(gòu)如下：typedefstructBitNode(Telemlypedata:structBitnode*lchild,*rchild;}BitNode.*Bitree;用類C寫出二叉樹中序遍歷的非遞歸算法.注；算法中可能用到的枝的操作Ini(Stack(s)s初始一個(gè)化棧sPush(s,p)：將所指向的結(jié)點(diǎn)進(jìn)s棧Pop(s,p)：s棧頂元素出棧gettop(s,p)：取s棧頂元素stackempty(s)：判棧s是否為空

操作系統(tǒng)（共50分）一、選擇題（每題1分，共20分）1、為了實(shí)現(xiàn)多道程序設(shè)計(jì)，il算機(jī)需要有.A）更大的內(nèi)存B）更快的外部設(shè)備C）更快的CPUD）更先進(jìn)的終端2.、進(jìn)程的—和并發(fā)性是兩個(gè)很重要的屬性.A）動(dòng)態(tài)性B）鄢態(tài)性C）易用性D）順序性3、P、V黑作是.A）兩條低級(jí)進(jìn)程通信原語C）兩條系統(tǒng)調(diào)用命令B）兩條高級(jí)進(jìn)程通信原語D）兩條特權(quán)指令4、在下列操作系統(tǒng)的各個(gè)功能組成部分中，—不需要硬件的支持。A）進(jìn)程調(diào)度 B）時(shí)鐘管理C）地址映射 D）中斷系統(tǒng)5,關(guān)于處理機(jī)調(diào)度，以下說法錯(cuò)誤的是—.A）衡量調(diào)度策略的主要指標(biāo)有：周轉(zhuǎn)時(shí)間、吞吐率、響應(yīng)時(shí)間和設(shè)備利用率B）處理機(jī)調(diào)度可以分為4級(jí)：作業(yè)調(diào)度、交換調(diào)度、進(jìn)程調(diào)度和線程調(diào)度。作業(yè)調(diào)度時(shí)，先來先服務(wù)法不利于長(zhǎng)作業(yè)，最短作業(yè)優(yōu)先法不利于短作業(yè)D）進(jìn)程調(diào)度的算法有：輪轉(zhuǎn)法、先來先服務(wù)法、優(yōu)先級(jí)法6、分段管理提供—維的地址結(jié)構(gòu).A）1 B）2C）3 D）47、若一個(gè)系統(tǒng)內(nèi)存有64MB,處理器是32位地址，則它的虛擬地址空間為 字節(jié).A）2GB B）4GBC）100KBD）64MB8、操作系統(tǒng)中的工作集模型與一有關(guān)。A）合并存儲(chǔ)區(qū)中的空白塊A）合并存儲(chǔ)區(qū)中的空白塊C）?個(gè)進(jìn)程訪問的頁面集合9、成組健法是用于_.A）文件的邏輯組織C）文件存儲(chǔ)器空閑空間的組織B）將CPU分配給進(jìn)程D）為進(jìn)程分配1/0資源B）文件的物理組織D）文件的目錄組織10、虛擬頁式存儲(chǔ)管理中頁表有若干項(xiàng)，當(dāng)內(nèi)存中某一頁而被淘汰時(shí)，可根據(jù)其中哪決定是否將該頁寫回外存—.A）是否在內(nèi)存標(biāo)志 B）外存地址C）修改標(biāo)志 D）訪問標(biāo)志11、有一磁盤，共有10個(gè)柱面,每個(gè)柱面20個(gè)磁道，體?個(gè)盤面分成16個(gè)扇區(qū).采用位824計(jì)算機(jī)專業(yè)基礎(chǔ)A第4次共7頁圖對(duì)其存儲(chǔ)空間進(jìn)行管理。如果字長(zhǎng)是16個(gè)二進(jìn)制位，那么位示圖共需_字.A)200A)200B)128C)256D)10012,設(shè)備的打開、關(guān)閉'讀、寫等操作是由—完成的。A）用戶程序B）編譯程序C）設(shè)備分配程序 D）設(shè)備驅(qū)動(dòng)程序13-14,靜態(tài)重定位是在作業(yè)的_中進(jìn)行的，動(dòng)態(tài)重定位是在作業(yè)的—中進(jìn)行的。A）編譯過程 B）裝入過程 C）修改過程D）執(zhí)行過程15、如果允許不同用戶的文件可以具有相同的文件名，通常采用—來保證按名存取的安全.A）重名翻譯機(jī)構(gòu)B）建立索引表C）建立指針D）多級(jí)目錄結(jié)構(gòu) 是直接存取的存儲(chǔ)設(shè)備。D）鍵盤、顯示終端B）優(yōu)先級(jí)變?yōu)樽畲驞）變?yōu)榫途w狀態(tài)D）鍵盤、顯示終端B）優(yōu)先級(jí)變?yōu)樽畲驞）變?yōu)榫途w狀態(tài)一個(gè)進(jìn)程被喚醒，意味著該進(jìn)程_.A）重新占有CPUC）移至等待隊(duì)列之首18、通道是一種.A）I/O端口B）數(shù)據(jù)通道 C）I/O專用處理機(jī) D）軟件工具19、SPOOLing技術(shù)利用于 .A）外設(shè)概念B）虛擬設(shè)備概念C）磁帶概念D）存儲(chǔ)概念20.從用戶的觀點(diǎn)看，操作系統(tǒng)是一A）用戶與計(jì)算機(jī)之間的接口B）控制和管理計(jì)算機(jī)資源的軟件C）合理地組織計(jì)算機(jī)工作流程的軟件D）由若干層次的程序按?定的結(jié)構(gòu)組成的有機(jī)體二、填空題（銀空1分，共5分）I、操作系統(tǒng)提供給編程人員的唯?接口是⑴ 。2、將主存空閑區(qū)按地址順序從小到登記在空閑區(qū)表中，每次分配時(shí)總是順序杳找空閑區(qū)表.直到找到一個(gè)能滿足其大小要求的空閑區(qū)為止，此種算法稱為 （2）算法.3、在頁式虛擬存儲(chǔ)系統(tǒng)中，選擇頁面調(diào)度算法時(shí)技盡量注意減少或避免工”現(xiàn)象的發(fā)4」.4、頁是信息的（4）單位,進(jìn)行分頁是出于系統(tǒng)管理的需要；段是信息的工單位，分段是出F用戶的需要三、填空題（共15分，每題1分）824計(jì)算機(jī)專業(yè)基瞅A第5網(wǎng)共7頁I、請(qǐng)你寫出請(qǐng)求頁式管理中缺頁中斷處理時(shí)的2種不同的洵汰算法的名稱：3、⑵.2.系統(tǒng)為一個(gè)有6頁的進(jìn)程分配4個(gè)物理塊，其頁表如下所示(時(shí)間單位：滴答)，頁的大小為1K,請(qǐng)計(jì)算邏輯地址為0X17C8的物理地址.按CLOCK算法為⑶:按FIFO算法為(4)；頁號(hào)塊號(hào)裝入時(shí)間上次引用時(shí)間R(讀)M(修改)07126279001423026010221202721139160280113、若F個(gè)等待訪問磁盤者依次要訪問的磁道為20,44,40,4,80,12,76,移動(dòng)臂當(dāng)前位于40號(hào)柱面，則先來先服務(wù)算法的平均天道氏度為一@；最短手道時(shí)間優(yōu)先算法的平均尋道長(zhǎng)度為(6):4,在采用分頁存貯管理系統(tǒng)中，地址結(jié)構(gòu)長(zhǎng)度為18位，其中11至17位表示頁號(hào)，。至10位表示頁內(nèi)位移量。主存容最最大可為K,每塊有⑻K。5、有一個(gè)恐龍博物館和個(gè)公園.有m個(gè)旅客和n輛車,每輛車只能容納一個(gè)旅客。旅客在博物館逛了一會(huì)兒，然后排隊(duì)乘坐旅行車。當(dāng)一輛車可用時(shí)，它載入一個(gè)旅客，然后繞公園行駛?cè)我馐系臅r(shí)間。如果n輛車都已被旅客乘坐游玩，則想坐車的旅客需要等待；如果一輛車已經(jīng)就緒，但沒有旅客等待，那么這輛車等待。使用信號(hào)量同步m個(gè)旅客和n輛車的進(jìn)程.(1)完善如下程序，在下列(9)-(12)四處填入有關(guān)語句(2)說明每個(gè)信號(hào)量的物理意義。muicx^l;pci()muicx^l;pci(){repeatp(visitors):(⑵start;run;stop;v(visitors);v(muiex);untilfalse;⑼；p(mutex);gelon;travell;getoff;-00)—;(ID;untilfalse;)visitors的含義（13） ;cars的含義（14）n;mutex的含義（15）四、簡(jiǎn)答題（每題5分，共10分）1、可以通過哪些途徑來提高內(nèi)存的利用率？2、為什么位示圖法適用于分頁式存儲(chǔ)管理和對(duì)磁盤存儲(chǔ)空間的管理？如果在存儲(chǔ)管理中采用可變分區(qū)存儲(chǔ)管理方案，也能采用位示圖法來管理空閑區(qū)嗎？為什么？離散數(shù)學(xué)（共50分）（4分）已知集合/={{<?}.⑴},B={{a}},試求（1）2'；（2）8x2"（6分）把下列語句翻譯為謂詞演算公式（1）魚我所欲，能掌亦我所欲：（2）并非所有人均喜歡電腦游戲：（6分）已知E是集合/上的自反和對(duì)稱關(guān)系,試證明，（幻為/上的等價(jià)關(guān)系。（6分）7=（匕馬是一棵樹。試證明（1）7為二部圖；（2）若{匕，匕}是二部圖丁的頂點(diǎn):分類，H|K|=n,|E\=m,試證明mV2.4（6分）設(shè)G=（匕E）是一個(gè)簡(jiǎn)單無向圖，卜|=",〃23.若對(duì)于任何兩個(gè)不相鄰的頂點(diǎn)w,veV,d（u）+d（v）>n,試證明G是連通圖。（4分）證明：在一個(gè)有限群中，階大于2的元素個(gè)數(shù)一定是偶數(shù)。（6分）已知0，=。-{0}.0是有理數(shù)集，Vm.neQ'.n^m=-mn,證明（。=4）為群.6（6分）已知知識(shí)的符號(hào)表示（1）女（尸（x）aVy（D（y）->Z（x,y）））W（P（x）fVy（0（y）->-￡（x,y）））結(jié)論：Vx（D（x）->r°（X））試用HORN子句邏輯程序證明之.（6分）已知G=（匕E）是一個(gè)簡(jiǎn)單平面圖，K|￡|<30.成證明至少有一個(gè)頂點(diǎn)的度數(shù)小于或等于4.第21頁2010年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題南京理工大學(xué)2010年碩士學(xué)位入學(xué)考試試題試題編號(hào)：2010006020考試科目：計(jì)算機(jī)專業(yè)基礎(chǔ)(滿分150分)(AJ考生注意：.所有答案(包括填空題)按試題序號(hào)寫在答題紙上，寫在試卷上不給分.本試卷共有三部分組成，其中第一部分為“數(shù)據(jù)結(jié)構(gòu)”，第二部分為"操作系統(tǒng)，第三部分為“離散數(shù)學(xué)”.每部分各50分.第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)(共50分)一、填空(每個(gè)空格1.5分，共15分).I.已知一個(gè)帶頭結(jié)點(diǎn)的單鏈表L,其存儲(chǔ)結(jié)構(gòu)為：typedefstructLNode{ElemTypedata;structLNode*next;)LNode,*LinkList;下面的算法是在L中刪除其最大值結(jié)點(diǎn)(表中有唯一的最大值)的算法，請(qǐng)?jiān)诳崭裉幪钊胝_的語句。voidDeleteMaxNode(LinkList&L){pre-L,p-pre->next,maxp=p,maxpre=pre;while((1)){if((2)){maxp=p;maxpre=pre;Jpre=p；(3);}//while:free(maxp);}//DeleteMaxNode.設(shè)哈希表長(zhǎng)為14,哈希函數(shù)是H(key)=key%ll,表中已有數(shù)據(jù)的關(guān)健字為16,28,40,52共四個(gè)，現(xiàn)要將關(guān)鍵字為61的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位中是(5):用線性探測(cè)再散列法解決沖突,則放入的位置是 ⑹ ..在一棵二叉樹中，度為I的結(jié)點(diǎn)有40個(gè)，總的結(jié)點(diǎn)數(shù)為99,則二叉樹中葉子結(jié)點(diǎn)數(shù)共有(7)..有序表為{2,5,9,12,16,20,26,28,32,36,40,43,45),在該表中用二分法查找值為37的數(shù)據(jù)，比較(8)次,可以確定查找失敗.共7頁第1版.對(duì)序列［50,37,66,98,75,12,26,49}進(jìn)行樹型選擇排序，選出12的二叉樹為⑼ ，接著再選出26的二叉樹為（10） .二、簡(jiǎn)答題（23分）.已知有向圖G有6個(gè)頂點(diǎn)（頂點(diǎn)號(hào)從1計(jì)），弧集E如下：（其中弧后面冒號(hào)后數(shù)表示弧上的權(quán)）E={<1,2>:12,<1,4>:15,<1,5>:8,<2,3>:13,<4,3>:25,<4,6>:5,<5,4>:5,<5,6>:20,<6,3>:2}請(qǐng)回答下面的問題：（3分）畫出該有向圖.（2）（3分）畫出該圖鄰接表存儲(chǔ)結(jié)構(gòu)。（3分）按Dijkstra算法，給出從頂點(diǎn)1到其余頂點(diǎn)的最短路徑及路徑長(zhǎng)度。（3分）將圖看成無向圖（將圖中方向去掉），畫出該無向圖的最小生成樹。2.已知關(guān)鍵字的集合{46,55,13,42,94,5,17,70）（1）（3分）請(qǐng)按給出的序列構(gòu)造一棵二叉排序樹（不要構(gòu)造過程），并給出該二叉樹排序樹的深度；（3分）請(qǐng)對(duì)（1）中的二叉樹進(jìn)行先、中、后序遍歷，分別給出遍歷結(jié)果；（3分）請(qǐng)給出該關(guān)健字集合的大頂堆；（2分）如果對(duì)該關(guān)鍵字集合進(jìn)行起泡排序，請(qǐng)給出第一趟排序后關(guān)鍵字的序列.三、算法（共12分）二叉樹的存儲(chǔ)結(jié)構(gòu)如下：typedefstructBitnode{TelemTypedata;structBitnode*Ichild,*rchild;}Bitnode,*Bitree;請(qǐng)編寫按層次順序（同一層自左至右）遍歷二叉樹的算法（6分）voidLayerOrder（Bitree,T）。所用隊(duì)列操作如下：InitQueue（Q）〃隊(duì)列初始化EnQueue（Q,T）//T入隊(duì)列，將T插入到隊(duì)尾QueueEmpty（Q）//隊(duì)列判空操作DeQueue（Q,p）〃出隊(duì)列，將隊(duì)頭元素賦值給p如果隊(duì)列用循環(huán)隊(duì)列實(shí)現(xiàn)，其存儲(chǔ)結(jié)構(gòu)為：#defineMAXQSIZE100typedefstruct{

QelemType*base;intfront;intrear;JSqQueue;請(qǐng)實(shí)現(xiàn)函數(shù)EnQueue(Q,T)(3分)和DeQueue(Q,p)(3、)第二部分操作系統(tǒng)（共50分）一、 單項(xiàng)選擇題（每小題1分，共20分）.關(guān)于多道程序設(shè)計(jì)的論述中不正確的是（ ）A）.能提高資源使用效率B）能增加單位時(shí)間的算題量0對(duì)每個(gè)計(jì)算問題的計(jì)算時(shí)間可能要延長(zhǎng)D）對(duì)每個(gè)計(jì)算問題的計(jì)算時(shí)間不會(huì)延長(zhǎng).當(dāng)一個(gè)進(jìn)程獨(dú)占處理器順序執(zhí)行時(shí)，具有兩個(gè)特性（ ）A）封閉性和可再現(xiàn)性 B）實(shí)時(shí)性和可靠性0交互性和可再現(xiàn)性 D）封閉性和實(shí)時(shí)性.某系統(tǒng)中，每個(gè)進(jìn)程在I/O阻塞之前的運(yùn)行時(shí)間為T,一次進(jìn)程切換的系統(tǒng)開銷時(shí)間為S,若采用時(shí)間片長(zhǎng)度為Q的時(shí)間片輪轉(zhuǎn)法，并且SVQVT,則CPU的利用率是（）D)Q/CT+S)A）T/（T+S） B）Q/（Q+S） C）50%D)Q/CT+S).把并發(fā)進(jìn)程中與共享變量有關(guān)的程序段稱為（ ）A）共享數(shù)據(jù)區(qū) B）臨界區(qū)D）共享程序C）D）共享程序.有關(guān)并發(fā)進(jìn)程的闡述中，不事確的說法是（ ）A）進(jìn)程的執(zhí)行速度不能由‘進(jìn)'程'自己來控制B）進(jìn)程的執(zhí)行速度與進(jìn)程能占用處理器的時(shí)間有關(guān)O進(jìn)程的執(zhí)行速度與是否出現(xiàn)中斷事件有關(guān)D）任何兩個(gè)并發(fā)進(jìn)程之間均存在著相互制約關(guān)系.有n個(gè)進(jìn)程競(jìng)爭(zhēng)某共享資源，系統(tǒng)允許每次最多m個(gè)進(jìn)程同時(shí)使用該資源,若用PV操作管理時(shí)信號(hào)量的變化范圍為（ ）B）[n>（m+n）]B）[n>（m+n）]D）[（m-n）,n]B）只能在管態(tài)下D）從目態(tài)變?yōu)楣軕B(tài)時(shí)C）[（m-n）,m].特權(quán)指令（ ）執(zhí)行.A）只能在目態(tài)下0可在管態(tài)也可在目態(tài)下.造成某進(jìn)程狀態(tài)從運(yùn)行態(tài)到等待態(tài)的變化原因不可能是（ ）A）該進(jìn)程運(yùn)行中請(qǐng)求啟動(dòng)了外圍設(shè)備B）該進(jìn)程在運(yùn)行中申請(qǐng)資源得不到滿足共7金第3貝0分配給該進(jìn)程的處理器時(shí)間用完D）該進(jìn)程在運(yùn)行中出現(xiàn)了程序錯(cuò)誤故障.在五個(gè)哲學(xué)家就餐問題中，為保證其不發(fā)生死鎖，可限定同時(shí)要求就餐的人數(shù)最多不舉可：（ ）A）2個(gè) B）3個(gè) C）4個(gè) D）5個(gè).已知作業(yè)的周轉(zhuǎn)時(shí)間=作業(yè)完成時(shí)間一作業(yè)的到達(dá)時(shí)間.現(xiàn)有三個(gè)同時(shí)到達(dá)的作業(yè)JI,J2和J3,它們的執(zhí)行時(shí)間分別是Tl,T2和T3,且TKT2VT3.系統(tǒng)按單道方式運(yùn)行且采用短作業(yè)優(yōu)先算法，則平均周轉(zhuǎn)時(shí)間是（）。A）T1+T2+T3 B）（T1+T2+T3）/3C）Tl+2*T2/3+T3/3 D）Tl/3+2*T2/3+T3.作業(yè)8：00到達(dá)系統(tǒng)，估計(jì)運(yùn)行時(shí)間為1小時(shí)，若10：00開始執(zhí)行該作業(yè)，其響應(yīng)比是（）A）2 B）1 03 D）0.5TOC\o"1-5"\h\z.讓多個(gè)用戶作業(yè)輪流進(jìn)入內(nèi)存執(zhí)行的技術(shù)稱為（ ）A）覆蓋技術(shù)B）對(duì)換技術(shù)C）移動(dòng)技術(shù) D）虛存技術(shù).可以采用靜態(tài)重定位方式轉(zhuǎn)換地址的管理內(nèi)存方案是（ ）A）頁式管理 B）頁式虛擬管理0可變分區(qū)管理 D）固定分區(qū)管理.在以下存貯管理方案中，不適用于多道程序設(shè)計(jì)系統(tǒng)的是（ ）A）單用戶連續(xù)分配 B）固定式分區(qū)分配O可變式分區(qū)分配 D）頁式存貯管理.現(xiàn)有如下請(qǐng)求隊(duì)列：8,18,27,129,110,186,78,147,41,10,64,12：用最短尋道時(shí)間優(yōu)先算法處理所有請(qǐng)求，移動(dòng)的總柱面數(shù)（ ）..假設(shè)磁頭當(dāng)前位置在100.A）263 B）264 C）265 D）266.在頁式虛存管理中，（ ）有一個(gè)頁表.A）整個(gè)主存空間 B）整個(gè)虛存空間0每個(gè)作業(yè) D）每個(gè)用戶文件.在頁式存儲(chǔ)管理中，假定訪問主存的時(shí)間為200亳微秒，訪問高速緩沖存儲(chǔ)器的時(shí)間為40亳微秒,高速緩沖存儲(chǔ)器為16個(gè)單元，查快表的命中率為90%,則按邏輯地址轉(zhuǎn)換成絕對(duì)地址進(jìn)行存取的平均時(shí)間為（ ）A） 256亳微秒 B） 400毫微秒C） 260亳微秒 D） 240毫微秒.信箱通信是一種（ ）通信方式.A）高級(jí)通信 B）低級(jí)通信0信號(hào)量 0）直接通信.在操作系統(tǒng)提供的文件系統(tǒng)中，用戶把信息組織成文件并對(duì)其操作時(shí)，關(guān)于文件存儲(chǔ)位置和如何組織輸入/輸出等工作，正確的說法是（ ）

A)B)A)B)C)D)用戶不需要考慮文件存儲(chǔ)的物理位置，也不需要組織輸入輸出工作用戶需要考慮文件存儲(chǔ)的物理位置，但不需要組織輸入輸出工作用戶不需要考慮文件存儲(chǔ)的物理位置，但需要組織輸入輸出工作B）盤的軀動(dòng)調(diào)度D）頁式虛擬存貯管理中的頁面調(diào)度.位示圖方法可用于（A）B）盤的軀動(dòng)調(diào)度D）頁式虛擬存貯管理中的頁面調(diào)度二、填空題（每空1分，共5分）1.2.1.2.為了便于對(duì)文件進(jìn)行控制和管理，在文件系統(tǒng)內(nèi)部，需要為每個(gè)文件建立一個(gè)處在采用線程技術(shù)的操作系統(tǒng)中，線程是他和執(zhí)行單位，而進(jìn)程是④單位.要確定一個(gè)盤塊所在的位置必須給出三個(gè)參數(shù)：15）_,柱面號(hào)和扇區(qū)號(hào)。三、解答題（共15分）1.（4分）有一個(gè)多道批處理系統(tǒng)，作業(yè)調(diào)度采用“短作業(yè)優(yōu)先“調(diào)度算法，進(jìn)程調(diào)度采用“優(yōu)先數(shù)搶占式“調(diào)度算法，且優(yōu)先數(shù)越小而優(yōu)先級(jí)越高。現(xiàn)系統(tǒng)擁有一臺(tái)打印機(jī)，采用靜態(tài)方法分配，忽略系統(tǒng)的調(diào)度開銷，現(xiàn)有如下作業(yè)序列到達(dá)系統(tǒng)：回答：（1）寫出作業(yè)完成的先后次序。（2）求出作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間.作業(yè)編號(hào)到達(dá)系統(tǒng)時(shí)間要求執(zhí)行時(shí)間需打印機(jī)數(shù)進(jìn)程優(yōu)先級(jí)J114：0040分鐘1臺(tái)4J214：2030分鐘0臺(tái)2J314：3050分鐘1臺(tái)3J414：5020分鐘0臺(tái)5J515：0010分鐘1臺(tái)12.（2分）在一個(gè)分頁存儲(chǔ)管理系統(tǒng)中，邏輯地址長(zhǎng)度為16位，頁面大小為4096個(gè)字節(jié).且第0、1,2頁依次存在物理塊10、12、14號(hào)中，則邏輯地址為2F6AH所對(duì)應(yīng)的物理塊號(hào)是,其物理地址是.3.（2分）假定在某動(dòng)臂磁盤上，剛處理了訪問75號(hào)柱面的請(qǐng)求，目前正在74號(hào)柱面上讀信息,且有如下請(qǐng)求序列在等待訪問磁盤：請(qǐng)求序列12345678欲訪問柱面號(hào)22481931889278156101試回答：（1）寫出電梯調(diào)度算法處理時(shí)的序列次序：（2）寫出最短尋找時(shí)間優(yōu)先算法時(shí)處理的序列次序；4.（2分）在一請(qǐng)求分頁系統(tǒng)中，一作業(yè)共有7個(gè)頁面，其中頁面0,1,2,3分別裝入到物理頁塊中.若作業(yè)的頁面走向?yàn)?123213252362142,采用FIFO頁面置換算法，產(chǎn)生缺頁中斷次,采用LRU頁面置換算法，產(chǎn)生缺頁中斷次。5.(5分)現(xiàn)有n個(gè)進(jìn)程，它們的標(biāo)號(hào)依次為1、2、…、n.現(xiàn)允許它們同時(shí)讀文件FL但必須滿足條件：同時(shí)該文件的進(jìn)程的標(biāo)號(hào)之和小于采用PV操作協(xié)調(diào)多進(jìn)程讀文件的程序如下，完成填空。semaphproewaits,mutex;intnumbersum=0;wait=0;TOC\o"1-5"\h\zmutex= (]) ;cobeginprocessreaderi(intnumber){//i=l,2,…P(mutcx); ,while(numbersum+number>=ni)f⑵：P(waits);}numbersum=nunibersum^number; .⑶：ReadFl⑷：numbersum=numbersum-numbcr;?_；V(mutex);四、簡(jiǎn)答題(每題5分，共10分).對(duì)資源采用靜態(tài)分配策略為什么能防止死鎖？.文件目錄一般包括哪些信息？設(shè)置文件目錄的功能是什么？第三部分離散數(shù)學(xué)(共50分).試把下列語句翻譯為謂詞演算公式(每小題3分，共6分)(1)我為人人，人人為我；(2)魚我所欲，熊掌亦我所欲..已知知識(shí)的符號(hào)表示(5分)⑴3x(P(x)aV>(產(chǎn)(y)fZ(xj)))Vx(P(x)f4"(y)->rL(x,y)))結(jié)論：Vx(尸(x)-Y(x))試用Hom子句邏輯程序證明之。4,8,C是三個(gè)任意的集合，若4￡(8uC),則(H-B)c(4-C)=<D.(5分)已知為四個(gè)集合，|川且Hc3=CcO=(D,試證明MuB|=|CuD|.(5分)G=(匕￡)是一個(gè)簡(jiǎn)單連通平面圖，試證明G中一定存在一個(gè)頂點(diǎn)，其度數(shù)小于等于5.(4分)H是集合力上的二元關(guān)系，對(duì)于任意的a,b,ce/，如果(a,6)eR,(b,c)wA,則(CM)e/?,稱R為循環(huán)關(guān)系。試證明K是自反的和循環(huán)的關(guān)系當(dāng)且僅當(dāng)/?是等價(jià)關(guān)系.(5分)1-已知9個(gè)人匕,匕，…“，其中匕與2個(gè)人握過手，》＞2，與，！，匕各與3個(gè)人握過手，v6與4個(gè)人握過手，叫,匕各與5個(gè)人握過手，vg與6個(gè)人握過手.試用圖論的語言證明這9個(gè)人中一定可以找出3個(gè)人互相握過手.(5分)7=(匕E)為一棵樹.若匕，匕是？作為二部圖的頂點(diǎn)分類，國國匕I，則匕中至少有一片樹葉。(5分)(4*)，(8,*)是兩個(gè)群.令C=4x8,且對(duì)于任意的(db),(c,W)wC,有(a,b)*(c,d)=(a*c,b*d)。證明(C,*)也是一個(gè)群。(5分)設(shè)(4*)是群(民*)的子群，定義C={x|xe8,x*〃xT=/}。試證明(C,*)是(民*)的子群.(5分)第30頁2009年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題南京理工大學(xué)2009年碩士學(xué)位入學(xué)考試試題試題編號(hào):

考試科目:試題編號(hào):

考試科目:計(jì)算機(jī)專業(yè)基礎(chǔ)(滿分150分)考生注意:.所有答案(包括填空題)按試題序號(hào)寫在答題紙上，寫在試卷上不給分.本試卷共有三部分組成，其中第一部分為“數(shù)據(jù)結(jié)構(gòu)”，第二部分為“操作系統(tǒng)”,第三部分為“離散數(shù)學(xué)”。每部分各50分.第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)(共50分)一、填空(每個(gè)空格L5分，共15分).與順序表相比鏈表不具有的特點(diǎn)是 (1)。.待排序的序列為(55,31,11,37,46,73,63,2,7},快速排序進(jìn)行一趟劃分后的序列⑵.設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,next),且rear是指向非空的帶頭結(jié)點(diǎn)的單循環(huán)鏈表尾結(jié)點(diǎn)的指針。若要?jiǎng)h除鏈表的第一個(gè)結(jié)點(diǎn)(刪除結(jié)點(diǎn)后，鏈表仍然不空)，則應(yīng)執(zhí)行 ⑶ 。.無向圖6=(V,E),其中：V={a,b,c,d,e,丹，E={(a,b),(a,e),(a,c),(b,c),(c,f),(f,d),(c,d)}, 圖的存儲(chǔ)結(jié)構(gòu)為鄰接矩陣。從a出發(fā)對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列是⑷ ；從a出發(fā)對(duì)該圖進(jìn)行廣度優(yōu)先遍歷，得到的頂點(diǎn)序列是⑸ 。.二叉樹的先序和中序遍歷序列分別是ABCDEFGH,CBEDFAGH,則后序遍歷序列是(6) ..折半插入排序算法如下所示，請(qǐng)?jiān)诳崭裉幪钊胝_的語句。voidBsort(Sqlist&L){fbr(i=2;i<=L.length;-H-i){L.r[0]=L.r[i];low=l;high=ST.length;while(⑺){m=(low+high)/2;TOC\o"1-5"\h\zif(LT(L.r[0].key,L.r[m].key)) ⑻：else(9) :}//whilefor(j=i-ly>=high+1;-j) (10) ;L.r[high+l]=L,r[O];

}//for}//Bsort二、簡(jiǎn)答（每小題5分，共15分）.已知關(guān)鍵字的集合{56,8,15,80,10,22},試構(gòu)造3階打樹。.編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)；.畫出下圖的最小生成樹三、（每小題4分，共12分）輸入關(guān)鍵字序列{10,6,7,4,8,9,12}.構(gòu)造一棵二叉排序樹T；.在T的中序線索樹中，結(jié)點(diǎn)7的前驅(qū)和后繼結(jié)點(diǎn)分別是什么結(jié)點(diǎn)；datanext四、算法（共8分）設(shè)有兩個(gè)集合計(jì)算(A-B)U(B-A)四、算法（共8分）設(shè)有兩個(gè)集合計(jì)算(A-B)U(B-A),A和B,分別用有頭節(jié)點(diǎn)的單鏈表（結(jié)點(diǎn)結(jié)構(gòu)）la和1b表示。用類C語言設(shè)計(jì)算法：結(jié)果放在la中。第二部分操作系統(tǒng)（共50分）一、單項(xiàng)選擇題（每小題1分，共20分）.使用戶所編制的程序與實(shí)際使用的物理設(shè)備無關(guān)，這是由設(shè)備管理的功能實(shí)現(xiàn)的。A）設(shè)備獨(dú)立性 B）設(shè)備分配C）緩沖管理D）虛擬設(shè)備.在頁式虛存管理中，有一個(gè)頁表。A）整個(gè)主存空間B）整個(gè)虛存空間 C）每個(gè)作業(yè) D）每個(gè)用戶文件.對(duì)一般用戶是透明的，但是對(duì)程序員是不透明的。A）虛擬存儲(chǔ)器 B）頁表C）人工覆蓋 D）靜態(tài)重定位.重定位的地址轉(zhuǎn)換工作是指。A）絕對(duì)地址轉(zhuǎn)換成物理地址B）物理地址轉(zhuǎn)換成絕對(duì)地址0絕對(duì)地址轉(zhuǎn)換成邏輯地址D）邏輯地址轉(zhuǎn)換成絕對(duì)地址.對(duì)若干進(jìn)程共享某一變量的相關(guān)臨界區(qū)的管理描述錯(cuò)誤的是。A）一次最多讓規(guī)定數(shù)目的進(jìn)程在臨界區(qū)執(zhí)行B）任何一個(gè)進(jìn)入臨界區(qū)執(zhí)行的進(jìn)程必須在有限的時(shí)間內(nèi)退出臨界區(qū)0不能強(qiáng)迫一個(gè)進(jìn)程無限地等待進(jìn)入它的臨界區(qū)D）有進(jìn)程退出臨界區(qū)時(shí)一定要選擇一個(gè)進(jìn)程進(jìn)入臨界區(qū).對(duì)死鎖的解除有關(guān)描述正確的是.A）可采用重新啟動(dòng)操作系統(tǒng)來解除死鎖B）可采用強(qiáng)迫進(jìn)程結(jié)束來解除死鎖0可采用靜態(tài)分配資源來解除死鎖D）可采用銀行家算法來解除死鎖.進(jìn)程并發(fā)執(zhí)行時(shí)，每個(gè)進(jìn)程的執(zhí)行速度是。A）由進(jìn)程的程序結(jié)構(gòu)決定的 B）由進(jìn)程自己控制的0在進(jìn)程被創(chuàng)建時(shí)確定的 D）與進(jìn)程調(diào)度的策珞有關(guān).當(dāng)多道程序系統(tǒng)中發(fā)生死鎖時(shí)，。A）計(jì)算機(jī)系統(tǒng)不能處理任何事情B）某個(gè)進(jìn)程不能執(zhí)行0一組進(jìn)程相互等待，并進(jìn)入阻塞狀態(tài)D）不能進(jìn)行輸入和輸出.三個(gè)進(jìn)程A、B,C對(duì)某類資源的需求量分別是7個(gè)、8個(gè)和3個(gè)，且目前別得到了3個(gè)、3個(gè)和2個(gè)。為保證系統(tǒng)的安全，該系統(tǒng)目前剩余的資3少是oA）1個(gè)B）2個(gè)C）5個(gè) D）10個(gè).為避免用戶程序中直接使用特權(quán)指令，用戶進(jìn)程運(yùn)行在oA）系統(tǒng)態(tài)B）核心態(tài)C）目態(tài) D）管態(tài).一個(gè)進(jìn)程獨(dú)占處理器順序執(zhí)行時(shí)具有封閉性和可再現(xiàn)性，其含義是A）進(jìn)程執(zhí)行的結(jié)果只取決于進(jìn)程本身B）進(jìn)程執(zhí)行的速度對(duì)執(zhí)行結(jié)果有影響O進(jìn)程多次執(zhí)行時(shí)其執(zhí)行結(jié)果可能不同D）進(jìn)程執(zhí)行時(shí)不會(huì)發(fā)生中斷事件.在批處理系統(tǒng)中，作業(yè)控制說明書是用編寫而成。A）C語言B）命令語言 0作業(yè)控制語言 D）會(huì)話語.當(dāng)進(jìn)程處于阻塞狀態(tài)時(shí)，進(jìn)程。A）沒有占用處理機(jī) B）將進(jìn)入結(jié)束狀態(tài)0將進(jìn)入執(zhí)行狀態(tài) D）等待處理機(jī).在下列各項(xiàng)步驟中，不是創(chuàng)建進(jìn)程所必須的步驟。A）建立一個(gè)PCB B）進(jìn)程調(diào)度程序?yàn)檫M(jìn)程分配CPU0為進(jìn)程分配內(nèi)存等資源 D）將PCB插入進(jìn)程就緒隊(duì)列.靜態(tài)分配資源（所有進(jìn)程在開始運(yùn)行之前，都必須一次性地申請(qǐng)其在整，行過程所需的全部資源）死鎖防止策略。A）破壞了“循環(huán)等待”和“占有并等待”兩個(gè)條件B）破壞了“互斥”和“占有并等待“兩個(gè)條件C）破壞了“互斥”條件D）破壞了“不可搶奪”條件.平均周轉(zhuǎn)時(shí)間最小的作業(yè)調(diào)度算法是oA）先來先服務(wù)算法 B）短作業(yè)優(yōu)先算法0響應(yīng)比最高者優(yōu)先算法 D）優(yōu)先數(shù)調(diào)度算法.段邏輯地址形式是：段號(hào)13位，段內(nèi)地址23位，內(nèi)存1M,輔存100G,那么虛擬存儲(chǔ)器最大實(shí)際容量可能是oA）8G-1M B）8G C）64G+1M D）64G.假設(shè)有編號(hào)為1、2、3、4四個(gè)空閑區(qū)，大小分別為16K、24K、15K、30K,現(xiàn)要申請(qǐng)15K的主存空間，采用最壞適應(yīng)算法，則申請(qǐng)到的空閑區(qū)編號(hào)為=A）1 B）2 C）3 D）4.設(shè)備的打開、關(guān)閉、讀、寫等操作是由完成的。A）用戶程序B）編譯程序C）設(shè)備分配程序 D）設(shè)備驅(qū)動(dòng)程序.尋道時(shí)間是指。A）由磁頭把扇區(qū)中的信息讀到主存儲(chǔ)器所需時(shí)間B）磁頭在移動(dòng)臂帶動(dòng)下移動(dòng)到指定磁道所需的時(shí)間0指定扇區(qū)旋轉(zhuǎn)到磁頭下所需的時(shí)間D）把主存儲(chǔ)器中信息寫到扇區(qū)中所需的時(shí)間二、填空題（每空1分，共5分）.系統(tǒng)中有4個(gè)進(jìn)程都要使用某類資源，而系統(tǒng)能提供的該類資源數(shù)為9個(gè)。那么，當(dāng)每個(gè)進(jìn)程需申請(qǐng)的資源超過口_個(gè)時(shí)，該系統(tǒng)就可能發(fā)生死鎖。.在UNIX中，文件系統(tǒng)的文件存儲(chǔ)結(jié)構(gòu)采用的是（2）。.我們把并發(fā)進(jìn)程中與共享變量有關(guān)的程序段稱為“⑶I.在采用線程技術(shù)的操作系統(tǒng)中，線程是（4）和執(zhí)行單位,而進(jìn)程是（5）單位。三、解答題（共15分）1.（本小題2分）設(shè)正在處理器上執(zhí)行的一個(gè)進(jìn)程的頁表如下，表中的頁號(hào)，物理塊號(hào)是十進(jìn)制數(shù)，起始頁號(hào)（塊號(hào)）均為0,所有的地址均是存儲(chǔ)器字節(jié)地址，頁面大小為1024字節(jié)，則邏輯地址2148對(duì)應(yīng)的物理地址為,邏輯地址4000對(duì)應(yīng)的物理地址為。頁號(hào)物理塊號(hào)02132136.（本小題2分）在一個(gè)請(qǐng)求頁式存儲(chǔ)管理系統(tǒng)中，某作業(yè)所涉及的頁面依次為0,1,4,2,0,2,6,5,1,2,3,2,1,2,6,2,1,3,6,2,并已知分給該作業(yè)的主存物理塊是3,則按照FIFO置換算法將產(chǎn)生 次缺頁中斷。按照最佳頁面置換算法將產(chǎn)生 次缺頁中斷。（所有內(nèi)存開始時(shí)都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷）.（本小題2分）假設(shè)一個(gè)磁盤驅(qū)動(dòng)器有500個(gè)柱面，編號(hào)從0到499。磁盤驅(qū)動(dòng)器正在為第255柱面的一個(gè)請(qǐng)求提供服務(wù)，且磁頭目前向0號(hào)柱面移動(dòng)，按FIFO順序排列的磁盤請(qǐng)求的柱面號(hào)依次為233,474,392,175,55,176,252,65,487,0和22。當(dāng)用FCFS（先來先服務(wù)）,SSTF（最短尋道時(shí)間優(yōu)先）來安排磁頭移動(dòng)時(shí)，移動(dòng)的總量分別是，。.（本小題3分）設(shè)一個(gè)文件由100個(gè)物理塊組成，若要將一塊信息加在文件的50塊之后，對(duì)順序、鏈接和索引（一級(jí)）三種存儲(chǔ)結(jié)構(gòu)各需啟動(dòng)I/O操作,,次。（其中該添加塊，目錄項(xiàng)（及索引塊，如果采用索引分配的話）都已經(jīng)在內(nèi)存中）.（本小題6分）在一個(gè)箱子里混裝有數(shù)量相等的黑色圍棋子和白色圍棋子，現(xiàn)要用自動(dòng)分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個(gè)并發(fā)執(zhí)行的進(jìn)程組成，功能如下：（1）進(jìn)程A專門揀黑子，進(jìn)程B專門揀白子；（2）每個(gè)進(jìn)程每次只揀一個(gè)子，當(dāng)一個(gè)進(jìn)程在揀子時(shí)不允許另一個(gè)進(jìn)程去揀子；（3）當(dāng)一個(gè)進(jìn)程揀了一個(gè)棋子（黑子或白子）以后，必讓另一個(gè)進(jìn)程揀一個(gè)棋子（黑子或白子），并要求A進(jìn)程首先開始。要求（1）（4分）完善如下程序，在下列A,B,C,D四處填入有關(guān)語句（2）（2分）說明信號(hào)量的物理意義。sl,s2:semaphore;siA; s2:=B;processA processBbegin beginLl:P（sl）; L2:P（s2）;揀黑子； 揀白子；C ； D；gotoLI; gotoL2;end; end;四、簡(jiǎn)答題（每小題5分，共10分）L什么叫文件目錄？文件目錄應(yīng)含哪些基本內(nèi)容？2.為實(shí)現(xiàn)分頁式虛擬存儲(chǔ)，頁表中至少包含哪些內(nèi)容？第三部分離散數(shù)學(xué)（共50分）（每小題3分，共6分）把下列語句翻譯為謂詞演算公式（1）所有的學(xué)生均喜歡老師；（2）任何一個(gè)集合X,總存在一個(gè)集合y,y的勢(shì)比x的勢(shì)要大。（6分）已知公理：?。≒TT（0T「P）B：PT（QfP）0：（PT（0f （（PT0）f（p-R））D：（Pv0）-＞（0vP）E：Pf（0vF）以及分離規(guī)則和代入規(guī)則試證明；（尸f「rP）V（&人為定理。（4分）證明小于30條邊的簡(jiǎn)單平面圖至少有一個(gè)頂點(diǎn)的度數(shù)小于或等于4。（6分）已知（4。）是一個(gè)群，（8,*）是一個(gè)代數(shù)系統(tǒng)，/是4到8的一個(gè)滿射,且對(duì)于Va,6w/I,有f（aob）=f（a）*f（b）。證明（8,*）是一個(gè)群。（5分）證明具有7個(gè)頂點(diǎn)15條邊的連通平面圖，它的每一個(gè)面都是有3條邊圍成。（6分）設(shè)48,C是三個(gè)集合，試證明（4- C）=/當(dāng)且僅當(dāng)ZcBcC=①。（5分）簡(jiǎn)單圖G=（匕E）且|P|=v"E|=e,若有e2+2,則G是哈密爾頓圖。（6分）（G,*）是一個(gè)群，aeG,/是G到G的一個(gè)映射：VxeG,/（x）=a*x*a7。試證明/是G到G的雙射。（6分）G=（匕約是一個(gè)簡(jiǎn)單無向圖。設(shè)G中任何兩點(diǎn)間僅有唯一的一條簡(jiǎn)單通路，試證明：（1）G是一棵樹；（2）G是一個(gè)二部圖。第38頁2008年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題南京理工大學(xué)2008年碩士學(xué)位研究生入學(xué)考試試題試題編號(hào)：2008006018考試科目：計(jì)算機(jī)專業(yè)基礎(chǔ)（滿分150分）考生注童:（1）所有答案（包括填空?qǐng)D按試題序號(hào)寫在答題紙上,寫在試卷上不給分.（2）本試卷共有三部分組成,其中第一部分為“計(jì)算機(jī)組成原理”，第二部分為“數(shù)據(jù)結(jié)構(gòu)”,該兩部分共100分，所有考生必做.第三部分有“離散數(shù)學(xué)”和“操作系境”各50分,考生可選做其中之一.若兩者均做，將按“離散數(shù)學(xué)”閱卷.請(qǐng)?jiān)诮獯鸬谌糠衷囶}時(shí),注明所選考試科目名稱.一、 計(jì)算機(jī)組成原理部分（共50分）（-）簡(jiǎn)答題（本題12分）1,中斷是計(jì)算機(jī)的處理一些意外事件和特殊請(qǐng)求的重要機(jī)制，一旦有中斷請(qǐng)求，CPU則響應(yīng)，并進(jìn)入中斷周期。請(qǐng)問中斷周期（又稱中斷隱指令）的主要任務(wù)是什么？ （本小題4分）2,某雙面磁盤，每面有220道，已知磁盤轉(zhuǎn)速r=3000轉(zhuǎn)/分，數(shù)據(jù)傳輸率為17500B/S,請(qǐng)問磁盤的總?cè)?是多少？ （本小JH4分）3、在CPU與DMA控制器共享總線的結(jié)構(gòu)中，DMA都采用哪些傳送方式實(shí)現(xiàn)外設(shè)和主存之間的數(shù)據(jù)傳送？ （本小題4分）（二）單項(xiàng)選擇題：（本題共9分，在每小愿的四個(gè)備選答案中，選出一個(gè)正確的答案.）1,設(shè)某浮點(diǎn)格式為16位,最高1位為數(shù)符、最低8位是尾數(shù)值，尾數(shù)采用補(bǔ)碼形式，階碼用移碼表示（1位階符、6位階值）.若十進(jìn)制數(shù)為-143,則其規(guī)格化的浮點(diǎn)數(shù)是。（H表示十六進(jìn)制）①C871H ②8871H ③E572H ④8143H2、主存儲(chǔ)器和CPU之間增加cache的目的是.①擴(kuò)大主存儲(chǔ)器的容量②擴(kuò)大CPU中通用寄存器的數(shù)量解決CPU和主存之間的速度匹配問題既擴(kuò)大主存儲(chǔ)容量又?jǐn)U大CPU通用寄存器數(shù)量3、當(dāng)采用 對(duì)設(shè)備進(jìn)行編址情況下，需要專門的I/O指令組.①統(tǒng)一編址法②單獨(dú)編址法③兩者都是④兩者都不是4、指令系統(tǒng)中采用不同尋址方式的目的主要是.①縮短指令長(zhǎng)度，擴(kuò)大尋址空間，提高編程靈活性②實(shí)現(xiàn)存儲(chǔ)程序和程序控制③可以直接訪問外存④提供擴(kuò)展操作碼的可能并降低指令譯碼難度5,奔騰CPU內(nèi)的浮點(diǎn)處理單元采用的浮點(diǎn)格式符合標(biāo)準(zhǔn).①ASCII②GB2312 ③IBM360④IEEE7546,為了更好地實(shí)現(xiàn)計(jì)算機(jī)的多級(jí)子程序嵌套調(diào)用，需要支持.①累加器②堆棧③光盤 ④磁盤7、運(yùn)算型指令的尋址與轉(zhuǎn)移性指令的尋址不同點(diǎn)在于.①前者是短指令，后者是長(zhǎng)指令②前者是長(zhǎng)指令，后者是短指令③后者取操作數(shù)，前者決定程序轉(zhuǎn)移地址④前者取操作數(shù)，后者決定程序轉(zhuǎn)移地址8、在單級(jí)中斷系統(tǒng)中，CPU一旦響應(yīng)中斷，則立即關(guān)閉標(biāo)志，以防止本次中斷服務(wù)結(jié)束前同級(jí)的其他中斷源產(chǎn)生另一次中斷進(jìn)行干擾.①中斷允許 ②中斷請(qǐng)求 ③獨(dú)立請(qǐng)求 ④中斷屏蔽9、流水處理器中本條指令的結(jié)果是后繼指令的操作數(shù)源，則存在.①資源相關(guān) ②控制相關(guān)③數(shù)據(jù)相關(guān) ④中斷相關(guān)（三）圖1.1為一個(gè)可以實(shí)現(xiàn)撲碼加法、減法和補(bǔ)碼一位乘法的筒單逆輯框圖.（C寄存器具有右移功能，門電路可自選，但需標(biāo)明功能：本題1。分）圖1.11、請(qǐng)指出A、B、C寄存器分別在加、減、乘運(yùn)算中的用途.（本問4分）2、若加、減、乘的控制信號(hào)分別為ADD、SUB、MUL,請(qǐng)寫出Pl、P2的邏輯表達(dá)式，并設(shè)計(jì)其形成電路. （本問6分）（四）設(shè)某機(jī)指令長(zhǎng)為16位，每個(gè)地址碼長(zhǎng)為4位，試用擴(kuò)展操作碼方法設(shè)計(jì)指令格式.其中三地址指令有10條，二地址指令為90條，單地址指令84條，還有若干零地址指令.現(xiàn)給定帶有使能端（低電位有效）的446譯碼⑶（譯碼器輸出低電位有效），其它愛輯門電路自選，但需說明所選電扇功能，

1、零地址指令最多有多少條？ （本問5分）2,若指令已在指令寄存器IR中，怎樣設(shè)計(jì)指令譯碼ID部件？（本問4分）（五）假設(shè)某計(jì)算機(jī)的運(yùn)算器框圖如圖1.2所示，其中ALU為16位的并行加法器（高電平工作），低位進(jìn)位位Co取值為?；?,Sa、Sb為16位暫存器，接收數(shù)據(jù)分別受Pa、Pb控制，且Reset信號(hào)用于給Sb復(fù)位（清零），Ldalu、LdE信號(hào)分別控制SB的原值輸出和反值輸出，4個(gè)16位的通用寄存器CRo-Rj）由D觸發(fā)器組成，并由原端（Q端）輸出.（本題10分）16位數(shù)據(jù)總線R?W?4個(gè)16位二款：｝讀選擇通用寄存器 WAoT.寫選擇 WA1J圖1.2通用寄存器（R/Rj）的讀寫控制如表1.1所示:表1.1寄存器讀寫控制表讀控制寫控制RRA0RA)選擇WWA0WAi選擇100讀即100寫&101讀Ri101寫R]110讀R2110寫Rz111讀1111寫R30XXX0XXX（注；X表示不工作）1、請(qǐng)簡(jiǎn)述控制器的微程序設(shè)計(jì)基本思想。 （本問3分）2,請(qǐng)用水平型微程序方法設(shè)計(jì)微指令控制字段的格式 （本問4分）（替不考慮后繼地址）.3,請(qǐng)給出實(shí)現(xiàn)減法（Ri）-（R2）》R3運(yùn)算的控制信號(hào)序列. （本問3分）二、 數(shù)據(jù)結(jié)構(gòu)部分（共50分）（-）填空（本題15分，每個(gè)空格1.5分）1,對(duì)序列{50,37,66,98,75,12,26,49}進(jìn)行樹型選擇排序，畫出選出12,和26的兩棵二叉樹 （1） 。2,已知一棵完全二叉樹共有892個(gè)結(jié)點(diǎn)，則該二叉樹的高度是經(jīng),葉子數(shù)是（3）,度為1的結(jié)點(diǎn)數(shù)是（4）,最后一個(gè)非葉結(jié)點(diǎn)的序號(hào)是⑸.（注：二叉樹結(jié)點(diǎn)按自然數(shù)順序從1開始從上到下，同一層從左至！J右編號(hào)）3、下面的算法是求有向圖中所有頂點(diǎn)入度的算法，請(qǐng)?jiān)诳崭裉幪钊脒m當(dāng)?shù)恼Z句。voidFindindegree（ALGraphG,intindegree[vexnum]）{for（i=0;i<vexnum;i++）indegree[i]=0;…for（i=0;i<vexnum;i++）-for（p=G.vertices[i]. 7c）~wr（（7） ;indegree[k+l]++;}//forp}//fori}//Findindegree4、設(shè)哈希表長(zhǎng)為14,哈希函數(shù)是H（key）=key%13,表中已有數(shù)據(jù)的關(guān)鍵字為16,30,44,58共四個(gè)，現(xiàn)要將關(guān)鍵字為82的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是（8）；用線性探測(cè)再散列法解決沖突，則放入的位置是 （9）.5,在B—樹中刪除關(guān)鍵字Ki,若Ki為非終端結(jié)點(diǎn)中的關(guān)鍵字，則以（1。）代替記（二）簡(jiǎn)答（本題15分）1,用類C的類型說明定義樹的二叉鏈表（孩子-兄弟）存儲(chǔ)結(jié)構(gòu)。（本小題2分）2,給出圖2.1樹的先序遍歷和后序遍歷序列。（本小題2分）3、將圖2.1的樹轉(zhuǎn)換成二叉樹，并畫出該二叉樹的二叉鏈表存儲(chǔ)表示.（本小題4分）

AOE網(wǎng)可以表示某個(gè)工程，在網(wǎng)中頂點(diǎn)表示事件，有向弧表示活動(dòng).給出求AOE網(wǎng)中某個(gè)事件j的最早發(fā)生時(shí)間Ve（j）和最遲發(fā)生時(shí)間VI。）的式子：如果活動(dòng)ai由弧勺k>表示，持續(xù)時(shí)間記為dutq,k>,則：活動(dòng)的最早（本小題4分）（本小題3分）開始時(shí)間e（i）（本小題4分）（本小題3分）（=）設(shè)關(guān)鍵字序列為{4,6,7,8,9,10,12},試解答：（本題12分）1,請(qǐng)對(duì)該關(guān)鍵字序列構(gòu)造一棵平衡二叉樹，畫出樹的生成過程和所進(jìn)行的平衡操作.（本問2分）平衡操作.2、計(jì)算該平衡二叉樹所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，并給出樹的深度.（本問4分）3、畫出刪除該平衡二叉樹關(guān)鍵字為8的結(jié)點(diǎn)后的平衡二叉樹。（本問2分）（本問2分）（本問2（本問2分）（本問2分）5,將序列建成大頂堆。（四）現(xiàn)給出數(shù)據(jù)類型描述如下所示.請(qǐng)用類C語言設(shè)計(jì)一個(gè)算法，將“中，所有結(jié)點(diǎn)的原有次序保持在各個(gè)結(jié)點(diǎn)的next域中，利用pre域把所有結(jié)點(diǎn)按照其值從小到大的順序連接起來。（本題8分）類型定義為：#defineM1000//鏈表最大長(zhǎng)度typedefstruct{Elemlypedata;int pre;int next;}component,SLinkList[M];假設(shè)si為SLinkList類型的雙向鏈表，sl[0].next指向表的第一個(gè)結(jié)點(diǎn)。三、操作系統(tǒng)部分（共50分.若選擇此部分，請(qǐng)?jiān)诖痤}紙上標(biāo)明）（-）單項(xiàng)選擇題（每小題1分，本題共2Q分）I、從下述對(duì)操作系統(tǒng)的敘述中選出正確的敘述是A）操作系統(tǒng)的程序都是在核心態(tài)下運(yùn)行.B）分時(shí)系統(tǒng)中常用的原則是使時(shí)間片越小越好.C）批處理系統(tǒng)的主要缺點(diǎn)是缺少交互性.D）Windows是一個(gè)多用戶多任務(wù)的操作系統(tǒng)。2、在采用線程技術(shù)的操作系統(tǒng)中，不正確的說法是A）線程是資源分配的獨(dú)立單位.B）線程是調(diào)度執(zhí)行的單位。C）同一進(jìn)程中各線程共享該進(jìn)程分配到的主存空間。D）線程運(yùn)行的系統(tǒng)開錯(cuò)更小.3、若當(dāng)前進(jìn)程因時(shí)間片用完而讓出處理機(jī)時(shí)，該進(jìn)程的狀態(tài)變?yōu)锳）就緒B）等待 C）運(yùn)行D）完成4,在一個(gè)單處理系統(tǒng)中，若有4個(gè)用戶進(jìn)程，則處于就緒狀態(tài)的用戶進(jìn)程最多有個(gè)，最少有個(gè).A）4、1 B）3、IC）3、0 D）4、05、進(jìn)程依靠從阻塞狀態(tài)過渡到就緒狀態(tài).A）程序員的命令 B）系統(tǒng)服務(wù)C）等待下一個(gè)時(shí)間片到來 D）“合作”進(jìn)程的喚醒6、臨界區(qū)是指并發(fā)進(jìn)程涉及共享變量的A）程序段B）緩沖區(qū)C）數(shù)據(jù)區(qū)D）信息區(qū)7、從下列有關(guān)進(jìn)程管理的敘述中，選出正確的描述A）進(jìn)程之間同步，主要源于進(jìn)程之間的資源競(jìng)爭(zhēng)，是指對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào).B）臨界資源是指每次僅允許一個(gè)進(jìn)程訪問的資源.C）信號(hào)量是一個(gè)整型變量，在其上只能進(jìn)行P操作和V操作.D）V操作是對(duì)信號(hào)量執(zhí)行加1操作，意味著釋放一個(gè)單位資源，加1后如果信號(hào)量的值小于等于零，則從等待隊(duì)列中喚醒一個(gè)進(jìn)程，現(xiàn)進(jìn)程變?yōu)榈却隣顟B(tài)，否則現(xiàn)進(jìn)程繼續(xù)進(jìn)行.8、在操作系統(tǒng)中，對(duì)信號(hào)量S的P操作中，使進(jìn)程進(jìn)入相應(yīng)阻塞隊(duì)列等待的條件是 A）S>0 B）S=0 C）S<0 D）SW09,某系統(tǒng)有4個(gè)并發(fā)進(jìn)程，都需要同類資源2個(gè)，當(dāng)系統(tǒng)中這類資源最少數(shù)是個(gè)時(shí)系統(tǒng)不會(huì)發(fā)生死鎖。A）4 B）5 C）6 D）710、某進(jìn)程被喚醒后，立即被執(zhí)行，該系統(tǒng)采用的調(diào)度方式是A）搶先調(diào)度 B）非搶先調(diào)度C）不能確定是否采用搶先調(diào)度 D）用戶搶先調(diào)度1k為了使系統(tǒng)中各部分資源得到均衡使用，就必須選擇對(duì)資源需求不同的作業(yè)進(jìn)行合理搭配,這項(xiàng)工作是由完成的。A）作業(yè)調(diào)度B）中級(jí)調(diào)度C）進(jìn)程調(diào)度 D）內(nèi)存調(diào)度12、在下面的調(diào)度算法中，算法不是合理的作業(yè)調(diào)度。A）時(shí)間片輪轉(zhuǎn) B）先來先服務(wù)C）短進(jìn)程優(yōu)先 D）優(yōu)先權(quán)13、假設(shè)系統(tǒng)中有三類互斥資源R】、氏和R3,可用資源數(shù)分別為9、8和5.在To時(shí)刻系統(tǒng)中有口、Pz、P,、P,和P,五個(gè)進(jìn)程，這些進(jìn)程對(duì)資源的最大需求量和已分配資源數(shù)如下表所示.如果進(jìn)程按序列執(zhí)行，那么系統(tǒng)狀態(tài)是安全的.源進(jìn)程最大需求，已分配資源數(shù)RiR?R3RiRjRjP.652121P?221211Pj801200P，121120巴344113A）P|-―?p4—kPs-B）p2-*P1-*?4-*Pj—*PjC）P2-*P4->Pj-?Pi―>Pj D）P4-—>Pj―?Pi-^Pj14、當(dāng)采用資源有序分配方法預(yù)防死鎖時(shí)，它破壞了產(chǎn)生死鎖必要條件中的一A）互斥條件B）請(qǐng)求和保持條件C）不剝奪條件D）環(huán)路等待條件15、以下存儲(chǔ)管理不可用于多道程序系統(tǒng)中.A）固定分區(qū)B）單一連續(xù)區(qū)C）動(dòng)態(tài)分區(qū) D）段式存儲(chǔ)管理16、在可變分區(qū)管理算法中，把空閑區(qū)按其長(zhǎng)度遞減次序排序的做法最適合于一A）首次適應(yīng)算法 B）最佳適應(yīng)算法C）最壞適應(yīng)算法 D）循環(huán)首次適應(yīng)算法17,在分頁存儲(chǔ)管理中，地址轉(zhuǎn)換工作是由完成的.A）硬件B）地址轉(zhuǎn)換程序 C）用戶程序 D）裝入程序18、在一個(gè)請(qǐng)求頁式存儲(chǔ)管理系統(tǒng)中，某作業(yè)所涉及的頁面依次為3,2,1,4,4,5,3,4,3.2,1,5,并已知分給該作業(yè)的主存物理塊是3,則按照LRU調(diào)度算法將產(chǎn)生 次缺頁中斷.（所有內(nèi)存開始時(shí)都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷.）A）7 B）8 C）9 D）1019、采用SPOOLing技術(shù)的目的是A）提高獨(dú)占設(shè)備的利用率 B）提高主機(jī)效率C）減輕用戶編程負(fù)擔(dān) D）提高程序的運(yùn)行速度20、要考慮磁頭當(dāng)前移動(dòng)方向的移符調(diào)度算法是A）最短尋找時(shí)間優(yōu)先調(diào)度算法 B）先來先服務(wù)調(diào)度算法C）優(yōu)先級(jí)調(diào)度算法 D）電梯調(diào)度算法（二）填空（每個(gè)空格1分，本題共5分）1,虛擬存儲(chǔ)管理系統(tǒng)的基礎(chǔ)是程序的（1）理論,根據(jù)這個(gè)理論，Denning提出了（2）理論.2、文件存儲(chǔ)設(shè)備管理中,UNIX采用的空闈塊管理方法是qi?3、為了使得操作系統(tǒng)具有特權(quán)，通常將計(jì)算機(jī)指令分為二類，即一般指令和（4）指令.4、通常情況下，連續(xù)文件結(jié)構(gòu)在順序存取時(shí)速度量快，皿結(jié)構(gòu)在隨機(jī)存取時(shí)速度最快.

（=）解答題（本題共15分）1、某計(jì)算機(jī)有32位虛地址空間，且頁大小為1024字節(jié).每個(gè)頁表項(xiàng)長(zhǎng)4個(gè)字節(jié)。因?yàn)槊總€(gè)頁表都必須包含在一頁中，所以使用多級(jí)頁表，則需要幾級(jí)頁表？每一級(jí)都有多少頁表項(xiàng)？ （本小題4分）2、在單道批處理系統(tǒng)中，有四個(gè)作業(yè)進(jìn)入系統(tǒng)，進(jìn)入時(shí)間及所需時(shí)間如下表所示：現(xiàn)忽略作業(yè)調(diào)度所花時(shí)間，當(dāng)?shù)谝粋€(gè)作業(yè)進(jìn)入系統(tǒng)后就可開始調(diào)度。（本小題4分）作業(yè)進(jìn)入時(shí)間所需計(jì)重時(shí)間18t002小時(shí)28：3030分鐘39：006分鐘49：3012分鐘（1）若用“先來先服務(wù)”調(diào)度算法，則作業(yè)3完成時(shí)間是多少？作業(yè)的平均周轉(zhuǎn)時(shí)間是多少？ （本子題2分）（2）采用“非搶先的短作業(yè)優(yōu)先”調(diào)度算法時(shí)，作業(yè)3完成時(shí)間又是多少？作業(yè)的平均周轉(zhuǎn)時(shí)間是多少？（本子題2分）3,在某餐館里有一個(gè)收銀員，且同時(shí)最多允許有30個(gè)顧客就餐，我們可以將顧客和收銀員看成是兩類不同的進(jìn)程，其工作流程如圖3.1所示.為了利用PV操作正確地協(xié)調(diào)這兩類進(jìn)程之間的工作，設(shè)置了三個(gè)信號(hào)*S，、S?和Sn,且初值分別為0、0和30. （本小題7分）圖3.]（D完善流程圖，在A,B,C,D處填入有關(guān)語句. （本子題4分）（2）說明信號(hào)量Si、&和Sn的作用及它們初值的物理意義?（本子題3分）（四）敘述題（每小題5分，本題共10分）1、什么叫進(jìn)程？為什么要引入進(jìn)程？2、請(qǐng)問分頁式和分段式內(nèi)存管理有什么區(qū)別？它們都如何實(shí)現(xiàn)共享和保護(hù)？三、離散數(shù)學(xué)部分(每題5分，共50分.若選擇此部分，請(qǐng)?jiān)诖痤}紙上標(biāo)明)1、某公司生產(chǎn)的8種不同的顏色的夢(mèng)織成的雙色布,已知在品種中,每種第色至少分別與其它7種顏色中的4種顫色搭配.試用圖論的語言證明可以挑出4種雙色布,它們恰有8種不同的旗色.2、試證明他單連通圖G的任何一條邊均可以是某一生成樹的枝.3、證明一棵樹若有3片樹葉，2個(gè)2度頂點(diǎn)，則至少有一個(gè)頂點(diǎn)的度數(shù)大于等于3.4、設(shè)(G,?)是一個(gè)群，定義R為G上的二元關(guān)系，R=((x,y)|存在0WG使得y=e*x*6-l},試證明R為G上的等價(jià)關(guān)系.(G,?)是一個(gè)群，H.K均是G的正規(guī)子群，請(qǐng)證明HcK也是G的正規(guī)子群.6、在一個(gè)邊長(zhǎng)為4的正方形內(nèi)任意加入65個(gè)頂點(diǎn)，至少有兩個(gè)頂點(diǎn)的距離小于紅.試用鴿巢原理證明之.7,A是無限集，B為可數(shù)無限集，試證明：|AkjB|=IA]8、試證明：(A-B)u(A-C)=0當(dāng)且僅當(dāng)AsBrC9、設(shè)R1和R2是集合A上的兩個(gè)關(guān)系，而且R1CR2,試證明：t(Rl)￡t(R2).10、A,B,C是三個(gè)任意的非空集合，f是A到B的函數(shù)，g是B到C的函數(shù),若g是單射，且Pg是A到C的滿射.請(qǐng)證明f是滿射.第49頁2007年南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院824計(jì)算機(jī)專業(yè)基礎(chǔ)A考研真題南京理工大學(xué)2007年碩士學(xué)位研究生入學(xué)考試試題試題韁號(hào)：2007006019考試科目：計(jì)算機(jī)專業(yè)基礎(chǔ)(滿分150分)考生注意:(1)所有答案(包括填空題)按試畫序號(hào)寫在答息紙上,寫在試卷上不給分.⑵本試卷共有三部分組成,其中第一部分為《數(shù)據(jù)結(jié)構(gòu)，第二部分為《計(jì)算機(jī)組成原理，該兩部分共100分,所有考生必做.第三部分有《離效數(shù)學(xué)》和《鐮作系統(tǒng))各50分,考生可選做其中之一.若兩者均做，將按《高《數(shù)學(xué)》閱卷.請(qǐng)?jiān)诮獯鸬谌糠衷嚪謺r(shí),注明所選考試科目名口.一、 數(shù)據(jù)結(jié)構(gòu)部分(共50分)(一)填空(每個(gè)空格1.5分，共15分)1、無向圖G=(V,E),其中：V={&b,cde,f),E={(a.b),(a.c),(a.c).(b.e).(c.D,(f,d),(e,d)}對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是(1)2.該算法為簡(jiǎn)單選擇排序算法.voidsort(Linklist&H){while(q){while(p){if(⑴ )r=p;p?p->next;Jq->data?--?r->data; 14) ;}//while(q)J//sort3、滿7叉樹上的葉子結(jié)點(diǎn)數(shù)g和非葉結(jié)點(diǎn)數(shù)曲之間的關(guān)系是：(514、3階B樹如下，畫出刪除24后的B房 ⑹痣I頁.共8頁5、設(shè)單循環(huán)鋅表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,next）,且rear是指向非空的帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針.若要?jiǎng)h除徒表的第一個(gè)結(jié)點(diǎn)，則應(yīng)執(zhí)行的操作為 ⑺6、輸入殍列為!8,6,4,10,12,9.7L構(gòu)造一棵哈夫曼樹，該哈夫曼樹的帶權(quán)路徑長(zhǎng)度WPL為 ⑻7、寫出表達(dá)式a*（b+c）Y的后綴表達(dá)式」8,有序表為（5,8,10,15,32,41,45,62,75,77,82,95,100},用二分查找值為82的數(shù)據(jù)時(shí)，需要比較（10）次.（二）筒答（16分，每小題4分）1、拓?fù)渑判蛩惴?2、Prim算法.3,說出二叉樹的五種形式.4.二叉樹中序遍歷的遞歸算法.《三》（9分）輸入關(guān)犍字序列{8,