全國名校計(jì)算機(jī)基礎(chǔ)綜合考研真題匯編

TOC\o"1-5"\h\z1,首都加范大學(xué)計(jì)4機(jī)學(xué)科琮合歷年考研真題 52014年首都師范大學(xué)90X計(jì)算機(jī)學(xué)科綜合考研真題 52013年苜都師范大學(xué)908計(jì)算機(jī)學(xué)科綜合考研亮題 142.浙江工商大學(xué)計(jì)算機(jī)柒礎(chǔ)綜合歷年考研支鹿 222015年浙江工商大學(xué)845計(jì)R機(jī)基礎(chǔ)綜合考研真題 222014年浙江工商大學(xué)845計(jì)算機(jī)基礎(chǔ)綜合考研真題 242013年浙江工商大學(xué)845計(jì)匏機(jī)基礎(chǔ)綜合考研真題 273,江蘇科技大學(xué)計(jì)黨機(jī)基礎(chǔ)綜合歷年號研其鹿 292014年江蘇科技大學(xué)845計(jì)算機(jī)基礎(chǔ)綜合考研真題 292013年江蘇科技大學(xué)845計(jì)算機(jī)燧礎(chǔ)瓊合考研「題 35.汕頭大學(xué)計(jì)算機(jī)基礎(chǔ)綜合歷年考研真題 482014年汕頭大學(xué)830計(jì)停機(jī)基礎(chǔ)綜合考研真題 482013年汕頭大學(xué)830計(jì)算機(jī)基礎(chǔ)綜合考研或麴 54.重慶理工大學(xué)計(jì)算機(jī)學(xué)科〃業(yè)盛礎(chǔ)綜合歷年考研真題 602014年前慶理匚大學(xué)810計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)琮介考研典典 602013年正慶理工大學(xué)809計(jì)算機(jī)學(xué)科專業(yè)施礎(chǔ)琮合考研真題 656,沈陽*P范大學(xué)計(jì)甄機(jī)學(xué)科專業(yè)基礎(chǔ)標(biāo)合歷年考研真題 702014年沈陽師范大學(xué)868計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考研真題 702013年沈陽師范大學(xué)868計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合與研自腮 74.東北財(cái)經(jīng)大學(xué)計(jì)算機(jī)綜合歷年考研真題 782014年東北財(cái)經(jīng)大學(xué)809計(jì)算機(jī)綜合考研真鹿 782013年東北財(cái)經(jīng)大學(xué)809計(jì)算機(jī)琮合考研真題 86.全國碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)繪合歷年考研五密及詳解 922012年全國碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科。業(yè)基礎(chǔ)蹤合真題 922012年全國獨(dú)士研究生入學(xué)統(tǒng)?芍試408計(jì)W機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解 1012011年全國碩士研究生入學(xué)統(tǒng)考試408計(jì)算機(jī)學(xué)科專業(yè)植礎(chǔ)綜合真題 1192011年全國碩士研究生入學(xué)統(tǒng)一考試408計(jì)區(qū)機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真盟及詳解 128.其他名校計(jì)算機(jī)綜合歷年考研真題 1462014年中國科學(xué)技術(shù)大學(xué)408計(jì)算機(jī)學(xué)科專業(yè)雁礎(chǔ)綜合考研出超 146說明:精選了18套名校計(jì)算機(jī)夠合歷年考研真題.1.首都師葩大學(xué)計(jì)算機(jī)學(xué)科綜合歷年考研真踐2014年首都抑范大學(xué)908計(jì)算機(jī)學(xué)科綜合考研真腌首都師范大學(xué)2014年攻讀碩士學(xué)位研究生入學(xué)考試試卷考試科目代碼；908 考試科目名稱t計(jì)耳機(jī)學(xué)科綜合請將答案注明題號寫在答題紙上，試題紙上做告無效。第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)(共75分)一、單項(xiàng)選擇題(集題1分,共25分).算法是解決某一問題的有限運(yùn)算序列,它必須具各輸入、輸出、_①可行性 ②可移植性 ③有窮性 ④確定性 一⑤穩(wěn)定性(A)①?③ (B)①?? (C)①?⑤ (D)級泡.設(shè)rear是指向非空的帶頭結(jié)點(diǎn)的單循環(huán)篋表健尾結(jié)點(diǎn)的指針,若要副山鏈表第一個(gè)結(jié)點(diǎn),則應(yīng)該執(zhí)行.s=rear：rear=rear->next;free(s);rear=rear-〉next：free(rear);rear=rear->next->next;free(rear)：s=rear->next->nMt;rear->next->next=s->next;frre(s);.長度為n(n〉D的單磕表上,在值為*的結(jié)點(diǎn)后面插入一個(gè)新結(jié)點(diǎn)的算法的時(shí)間發(fā)雜度為 ?(A)0(n) (B)0(1) (C)0(n1) (D)o(nlogn).利斯一個(gè)表達(dá)式中左右括號是否或?qū)Τ霈F(xiàn)的算法，采用—這腫拔■雄構(gòu).好.(A) (B)<- 7 ))域隊(duì).修序槿S中元素個(gè)數(shù)是(A)S.lop-i-S.base...? (B)o..r.ja.(C)S.top+S.base (D)S.top-S.base.若循環(huán)隊(duì)列的存"空間大小為6,當(dāng)前front和rear的值分別為】和4,生療兩次Engeue和一次DeQueue后，front和rear的值分別是.(A)鈾0 (B)2和6 (C)3和5 (D)o和2.一棵度為4的M中，度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、1,則讀樹葉子她用的個(gè)數(shù)是.(A)5 (B)6 (C)7 (D)8.任何一朦薦交二叉樹中，?.丁一?：： 歷中的相對位置 .(A)都會發(fā)生改變 (B)不會發(fā)生改變(C)有可能會發(fā)生改受 (D)部分會發(fā)生改變考試科目代碼：908.在一棵先序線索二叉樹中,結(jié)點(diǎn)*p的前驅(qū)可能是(A)與的左核子(B)”的右孩子 (C)與的雙親 (D)*p的右孩子的右孩子.具有n個(gè)頂點(diǎn)的連通圖的生成樹一定有條邊.(A)n-1 (B)n (C)n+1 (D)2n.如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是(A)完全圖 (B)連通圖《C)有回路 (D)一棵樹.用DFS遍歷一個(gè)有向無環(huán)圖，并在退出DFS時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是.(A)拓?fù)溆行?B)逆拓?fù)溆行颉禖》頂點(diǎn)值有序 (D)無序.在具有n個(gè)連埃存儲單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 個(gè)元素。(A)n+2 (B)n+1 (C)n (D)n-1.將10個(gè)元素散列到100000個(gè)單元的哈希表,M產(chǎn)生沖突.(A)一定會 《B》一定不會 (C)仍可能會 (D)以上都不對.若特排序數(shù)據(jù)已經(jīng)有序，排序算法花費(fèi)的時(shí)間反而?多.(A)起泡 (B)希爾 (C)快速 (D)堆.若有100000個(gè)數(shù)據(jù)，只想找出從小到大序列中前10個(gè)數(shù)據(jù)，用方法最快.(A)堆排序 (B)希爾 (C)快速 (D)面單選擇.如果對含有n(n>l>個(gè)元素的線性表的運(yùn)算只有4種：刪除第一個(gè)元素：刪除最后一個(gè)元素；在第一個(gè)元素前面插入新元素；在?后一個(gè)元素的后面插入新元素，則?好使用?(A)只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的循環(huán)單域表(B)只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)的非循環(huán)單集表(C)只有頭結(jié)點(diǎn)指針沒有尾結(jié)點(diǎn)指針的循環(huán)雙鐮表(D)既有頭結(jié)點(diǎn)指針也有尾結(jié)點(diǎn)指針的循環(huán)單鏈表.關(guān)于哈希查找，錯誤的說法是.(A)不存在量好和最壞的哈希函數(shù)，需視具體情況選擇(B)用能地址法解決沖突時(shí)，杳找任一元素的時(shí)間是相同的(C)用鏈地址法解決沖突時(shí)，同義詞在同一個(gè)愜表中(D)哈希表的平均查找長度與處理沖突的方法有關(guān).數(shù)組的物理結(jié)構(gòu),需要存儲以下內(nèi)容：①起始地址②每一維的維界③地址計(jì)算所甯要的常數(shù)④下標(biāo) ⑤數(shù)蛆大小(A)①?③ . (B)③? (C)①@⑤ (D)③?⑤.已知一個(gè)棧的進(jìn)棧序列是ABC,出校序列是BCA,實(shí)施的棧操作是(A)push.pop.push,pop.push,pop (B)push.push.pop.push,pop,pop(C)push,pushtpop.pop.push,pop (D)push,pop.push.push.pop.pop21.對于鏈隊(duì)，在進(jìn)行11除操作時(shí).(A)僅修改頭指針?(B)僅修改尾指針(C)頭、尾指針都要修改(D)頭、尾指針可能都要修改22.線僵二叉軻是一種 結(jié)構(gòu)(A)邏輯 (B)線性(C)物理 (D)履序23.哈夫曼樹不具有的特點(diǎn)是 (A)帝權(quán)路徑長度?小的樹(B)有度為0的結(jié)點(diǎn)(C)有度為1的結(jié)點(diǎn)(D)有度為2的結(jié)點(diǎn)24. 不能判斷一個(gè)有向圖是否存在回路.①拓?fù)渑判?②深度優(yōu)先遍歷③找?短路徑 ④找關(guān)倭路徑(A)(D? (B)②?(C) (D)(D?25.有一個(gè)有序表為｛1.3.9,12,32.41.45.62.75,77,82.95.99|,當(dāng)采用折半杳找法查找關(guān)鍵字為3的元素時(shí)，次比較后者找成功.(A)1 (B)2 (C)3 (D)4二、填空題(每空1分,共10分).然性表L=(al,a2an)用數(shù)組裹示，假設(shè)刪除表中任一元素的可能性相同，則刪除一個(gè)元素平均需要移動個(gè)元素..在單健表I,中，表示指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)..由3個(gè)結(jié)點(diǎn)可以構(gòu)造出 櫬不同的二叉相(不考慮結(jié)點(diǎn)的值)..T和P是兩個(gè)字符串，在T中查找等于P的子串的過程稱為..采用數(shù)姐tree[1..18]存放一棵完全二叉樹,則結(jié)點(diǎn)tree[7]的右段子是..采用二叉廢表結(jié)構(gòu)存儲二叉樹，若要交換所有分支結(jié)點(diǎn)的左右孩子，應(yīng)利用 遍歷方法?合適..iTn個(gè)頂點(diǎn)的有向圖,至少有一條弧才可能是連通的..數(shù)組(98,36.-10,2,40.20,7,12.24),按步快3進(jìn)行一超希爾排序的結(jié)果序列為一..假設(shè)有k個(gè)關(guān)候字互為同義詞，若用線性探測再散列的方法處理沖突，至少要進(jìn)行次探測..按一遍歷二叉排序樹,可以得到按值遞增的關(guān)鍵碼序列..f三；筒答題(共21分).設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，用來表示學(xué)生的基本信息：學(xué)號、姓名、出生年月日、班級、專業(yè)、愛好.請說明設(shè)計(jì)理由.(3分).什么是排序算法的穩(wěn)定性？請舉例說明.(3分).一個(gè)8行6列稀疏矩陣的三元Sfi表為：(1.3,5)⑵6,8)(4,3,15)(4.1,21)(5,3,567)(7,1,4)(8,6,3).(1,3,5)為第1個(gè)三元組，請同轉(zhuǎn)置后(3,1.5)是第幾個(gè)三元蛆，請說明原因.(3分).分析下列程序段的時(shí)間復(fù)雜性.(3分)voidunion(List&La,ListLb){La_len=ListLength(La); 〃計(jì)算表La的長度，假設(shè)值為naLb_len=ListLength(Lb); 〃計(jì)算表Lb的長度,假設(shè)值為nbfor(i=l;i<=Lb_len;i*+)(GetElen(Lb,i,e);if(iLocateElenda,e,equal))ListInsert(La,++La_len,e)：)}.如何定義循環(huán)隊(duì)列的物理結(jié)構(gòu)？清根據(jù)你的定義說明如何計(jì)算隊(duì)列中有多少個(gè)元素.(3分).依次*入以下關(guān)鍵字t5.36.24,73,8.20,66,94,1,18.構(gòu)造3階、軻.(3分).按層序給一櫬完全二叉軻中所有結(jié)點(diǎn)樵號，舉例說明如何找到第i個(gè)結(jié)點(diǎn)和第j個(gè)結(jié)點(diǎn)?近的共同祖先.(3分)四、請判斷下列說法是否正確，正確回答“是"，不正確回答“否”(每廖1分，共10分).■序表在?序存催方式下插入和刪除效率太低，因此不如鐮式存儲方式好.為提高內(nèi)存利用率，兩個(gè)棧共用一段連續(xù)的存儲空間.為減少溢出機(jī)會，應(yīng)把兩個(gè)稅的枝底分別設(shè)在這段存儲空間的兩嫻.由二叉樹的先序序列和后序序列可以惟一地確定一棵二叉樹.下三角矩陣壓縮存儲后仍可以實(shí)現(xiàn)隨機(jī)存取.串“abc”共有6個(gè)子串.數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型操作的定義與數(shù)據(jù)的物理結(jié)構(gòu)有關(guān).尋找關(guān)曼路徑是在拓?fù)渑判虻幕A(chǔ)上完成的.?短路徑一定是面單路徑.(100.85.98.82.80.77,66,60.40,20,10}是一個(gè)堆.二叉排序樹的查找效率和二叉排序樹的高度有關(guān)五、嫌合運(yùn)用題（9分.選做其中一H）.數(shù)組child[n+l]中依次存放了具有n個(gè)結(jié)點(diǎn)的二叉樹T層序遍歷時(shí)輸出的誨個(gè)結(jié)點(diǎn)的子軻個(gè)數(shù)，child（O）沒有意義.請寫一個(gè)算法判斷該二叉料是否是完全二叉樹.（9分）.無向圖G的存儲結(jié)構(gòu)為鄰接表.請寫出判斷圖G中頂點(diǎn)u與頂點(diǎn)v之間是否有路徑的算法.（9分）鄰接衰定義為：typedefstructArcNode（intadjvex; 〃鄰接頂點(diǎn)structArcNode*nextarc;//指向下一條列的指針）ArcNode：typedefstructVNode（char data[5]： //頂點(diǎn)信息ArcNode?firstarc://指向第一條依附頂點(diǎn)的弧的指計(jì)IVNode,AdjList[MAX_VERTEX_NIM];typedefstruct{AdjListvertices;intvexnum.arcnua;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)）ALGraph;第二部分計(jì)算機(jī)組成原理（共75分）一、選擇鹿（每題1分，共15分）.馮?諾依曼機(jī)工作的基本特點(diǎn)是,（A）多指令流單數(shù)據(jù)流 （B）按地址訪問并順序執(zhí)行指令（C）堆棧操作 （D）存貯器按內(nèi)容選擇地址.計(jì)對8位二進(jìn)制數(shù)，下列說法中正確的是.（A>-127的孫瑪為10000000 （B）-127的反碼等于0的移碼（C）+1的移碼等于T27的反碼 （D）。的補(bǔ)碼等于-1的反碼.運(yùn)算翳雖然由許多部件蛆成，但其核心部件是.（A）數(shù)據(jù)總線 （B）算術(shù)iS輯單元（C）多路開關(guān) （D）累加寄存卷.在定點(diǎn)二進(jìn)制運(yùn)算器中，減法運(yùn)算一般通過來實(shí)現(xiàn).（A）原碼運(yùn)算的二進(jìn)制減法器 （B）補(bǔ)碼運(yùn)算的二進(jìn)制減法卷?（C）補(bǔ)碼運(yùn)算的十進(jìn)制加法舞 （D）補(bǔ)碼運(yùn)算的二進(jìn)制加法器.若浮點(diǎn)數(shù)用補(bǔ)碼衰示，則判斷運(yùn)算結(jié)果是否為規(guī)格化數(shù)的方法是.(A)階符與數(shù)符相同為規(guī)格化數(shù)(B)階符與數(shù)符相異為規(guī)格化數(shù)(C)數(shù)符與尾數(shù)小數(shù)點(diǎn)后第一位數(shù)字相異為規(guī)格化數(shù)(D)數(shù)符與尾數(shù)小數(shù)點(diǎn)后第一位數(shù)字相同為規(guī)格化數(shù).下面浮點(diǎn)運(yùn)算器的描述中正確的句子是 .(A)階碼部件可實(shí)現(xiàn)加、減、乘、除四種運(yùn)N(B)階碼部件只進(jìn)行階碼相加、相減和比較操作(C)尾數(shù)部件只進(jìn)行加法和減法運(yùn)算(D)尾數(shù)部件只進(jìn)行乘法和減法運(yùn)算.假定用若干個(gè)2kx4位芯片組成一個(gè)8k*8位存儲器，則地址OBIFH所在芯片的最小地址是?(A)OOOOH (B)0600H(C)0700H (D)0800H.存貯單元是指.(A)存放一個(gè)二進(jìn)制信息位的存貯元<B)存放一個(gè)機(jī)II字的所有存七元集合(C)存放一個(gè)字節(jié)的所有存貯元集合(D)存放兩個(gè)字節(jié)的所有存貯元集合.動毒存儲卷(DRAM)依靠存儲信息.(A)門電路 (B)觸發(fā)器(C)多路開關(guān) (D)電容電荷.下列因素下，與Cache的命中率無關(guān)的是.(A)主存的存取時(shí)間 (B)塊的大小Cache的蛆織方式 (D)Cache的容量.程序控制類指令的功能是?(A)進(jìn)行算術(shù)運(yùn)算和邏,運(yùn)算(B)進(jìn)行主存與CPU之間的數(shù)據(jù)傳送(C)進(jìn)行CPU和I/O設(shè)備之間的數(shù)據(jù)傳送(D)改變程序執(zhí)行的?序.指令系統(tǒng)采用不同尋址方式的目的是,(A)實(shí)現(xiàn)存貯程序和程序控制(B)縮短指令長度.擴(kuò)大尋址空間，提高館程靈活性(C)可直接訪問外存(D)提供擴(kuò)展掾作碼的可能弁降低指令譯碼的難度.在CPU中跟蹤指令后繼地址的寄存器是.(A)主存地址寄存卷 (B)程序計(jì)數(shù)器(C)指令寄存器 (D)狀態(tài)條件寄存器.減少指令中地址個(gè)數(shù)的辦法是采用.(A)寄存器尋址 (B)寄存器同址(C)變址導(dǎo)址 (D)隱含尋址.微程序控制器中,機(jī)器指令與做指令的關(guān)系是?(A)每一條機(jī)器指令由一條微指令來執(zhí)行(B)誨一條機(jī)器指令由一段做指令編寫的減程序來解稀執(zhí)行(C)每一條機(jī)器指令組成的程序可由一條貓指令來執(zhí)行一條微指令由若干條機(jī)修指令組成二、尚答同(每題5分，共20分).在浮點(diǎn)數(shù)的IEEE754格式中，其尾數(shù)部分的表示采用隱蔽位技術(shù),請解釋何為除蔽位？其目的是什么？.DRAM存儲器為什么要刷新？刷新方式有哪幾種？.為什么多體低位交叉結(jié)構(gòu)存儲器可以提高訪存速度？.與組合邏輯控制器相比，境程序控制舞有何優(yōu)缺點(diǎn)？三、分析計(jì)算題(每息5分，共2吩).設(shè)十進(jìn)制數(shù)尸(-12S.75)Ml-10,調(diào)回答：(1)寫出x的16位補(bǔ)碼的機(jī)內(nèi)定點(diǎn)數(shù)表示；(2)寫出x的IEEE短浮點(diǎn)數(shù)格式..設(shè)計(jì)算機(jī)的主存儲器為64Kxi6位，采用直接映像方式的高速緩存容量為】KT6位，穿埃大小為4字.(1)主存儲器的地址分為唱幾個(gè)字段？每個(gè)字段的位數(shù)是多少？(2)高速依存地址的標(biāo)志字段、塊號和塊內(nèi)地址字段分別有多少位？(3)高速緩存中可裝入多少塊數(shù)據(jù)？.假設(shè)CPU執(zhí)行某段程序時(shí)，訪問CMheSlOO次，訪問主存900次，已如Cache存取周期為。ns,主春的存取周期為250ns.求Cache的命中率和平均訪問時(shí)間.4,假定一個(gè)32位的微處理器，指令字長32位，每條指令由兩部分組成，其中第一個(gè)字節(jié)為操作碼，剩余的為立即數(shù)或操作數(shù)地址.(1)可直接訪問的最大主存空間是多少？(2)程序計(jì)數(shù)器和指令寄存器各需要多少位？(3)該微處理器運(yùn)算電路是多少位？四、除合應(yīng)用息《每題10分，任選2題，共2詡).設(shè)某機(jī)配有基址寄存器和變址寄存器，采用一地址格式的指令系統(tǒng)，允許直接和間接尋址，且指令字長、機(jī)器字長和存儲字長均為16位.(1)若采用單字長指令，共能完成】05種操作，則指令可直接尋址的范圍是多少？一次間址的尋址范圍是多少？畫出其指令格式并說明各字段的含義.(2)若存儲字長不變，可采用什么方法直接訪問容量為16MB的主存？畫出其指令格式并說明各字段的含義..設(shè)某機(jī)為定長指令字結(jié)構(gòu).指令長度12位，每個(gè)地址碼占3位.(1)請?zhí)岢鲆环N方案，使謨系統(tǒng)包含4條三地址指令,8條二地址指令，180條單地址指令.<2>能否構(gòu)成三地址指令4條，單地址指令255條，華地址指令64條呢？.已知某CPU和存儲芯片組成的系統(tǒng)框圖如下，其中A15?A0為地址總線,D7?D0為數(shù)據(jù)總線，請看圖回答以下問題.(1)圖中ROM存貯芯片的容量為RAM存貯芯片的容量為(2)現(xiàn)已實(shí)現(xiàn)擴(kuò)展的存貯容量為(3)片選逐輯CS1的逆管表達(dá)式為片選運(yùn)螭CS2的邏■表達(dá)式為(4)寫出每組石片的地址范圍(16進(jìn)制表示)起始地址 終止地址第一蛆： 第二蛆， (5)該系統(tǒng)的片選控制采用的是譯碼方式.首都師范大學(xué)2013年攻讀碩士學(xué)位研究生入學(xué)考試試卷考試科目代碼：908 考試科目名稱：計(jì))1機(jī)學(xué)科綜合 滿分150分請將答案注明題號寫在答題紙上.試題紙上做答無效第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)(共75分)-.單項(xiàng)逸打18每分，共20分).下列關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的表述中.是錯誤的.①數(shù)據(jù)的邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計(jì)算機(jī)中如何存儲有關(guān)②邏輯結(jié)構(gòu)相同的數(shù)據(jù),可以采用多種不同的存儲方法③定義邏輯結(jié)構(gòu)時(shí)需要為慮物理結(jié)構(gòu)(A)(D? (B)@@> (C)— (D)?.一個(gè)具有515個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為.(A)9 (B)10 (C)10—515 (D)11—5153.設(shè)極S的初始狀態(tài)為空,元素I、2.3.4.5.6.7依次入枝.出枝髓序?yàn)?、3.5.2.7.1.在搽作過程中.段中元素通多時(shí)有t.(A)4 (B)5 (C)6 CD)7.循環(huán)隊(duì)列qu的隊(duì)滿條件是.(qu.rear?l)%MAXSIZE-(qu.front*I)%MAXSIZE(qu.rear*l)%MAXSIZE=qu.front*I(qu.rear^i)、HAXS1ZE=qu.frontqu.rear-qu.front.兩個(gè)串相卻必有串長度相等且(A)串的各位置字符任意 (B)阜中方僅置字符均對應(yīng)相希(C)兩個(gè)串含有相同的字符 (D)兩個(gè)事所含字符任意.以卜數(shù)據(jù)結(jié)構(gòu)中.是M0性結(jié)構(gòu).(A)線性衰(B)圖 (C)數(shù)m(D)棧.根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是.(A)000.001,010.Oil.I (B)0000.0001,001.01.1(C)000.001.01.10.Il (D)00.100.101.110.111.在表示乘車線路的有向圖中,可以通過以下搜索方法找到換乘次數(shù)最少秉車方案.(A)深度優(yōu)先搜索 (B)廣度優(yōu)先搜索(C)先序搜索 (D)后序搜索.棵—k的中曲一叉機(jī)若餌個(gè)/葉子蟀點(diǎn).的平曲因子均為0.則誣柯其玉_個(gè)結(jié)由.(A)2*-1 (B>2*' (02'-1UH2lI。.以卜解作的W法時(shí)間愛雜性不是0《向的是.(A>&；1有n個(gè)站立的有序單也表中插入一個(gè)新的結(jié)點(diǎn)并使能表仍惘有序(B)逆位停建，,有n個(gè)結(jié)點(diǎn)的隼斑表(C)在K/.Q為n(nI)只有尾結(jié)點(diǎn)指針r的不帶頭結(jié)點(diǎn)的惆環(huán)單城表上,那除最后個(gè)元索(P)在有n個(gè)元素的循環(huán)隊(duì)列中取以尾元素的值.三維數(shù)組A的每個(gè)元素占5個(gè)字節(jié),元素a,仆的下標(biāo)i*j.k的范南分別是。到4.0M5.0到7.以行序?yàn)橥列蝽樞虼鎯υ?000開始的存體維元中.元素Af'的地址是?(A)1825 (B)1535 (C)1620 (D)2110.圖中所有項(xiàng)點(diǎn)的廢敷之和尊于所有邊敷的—J8.(A)12 (B)1 (C)2 (D)413,已知某有向圖GMV.A).其中V=fvl.v2,v3.v4.v5,v6|.A=?vl.v2>.<vl.v4>.<v2,<v3.vl\v3,“.、v4.v5>.<v5.v2Xv5,v6?,G的拓?fù)湫蛄惺?(A】v3,vl,v-l,v5,v2,v6 ，B)v3,v4.v1,v5,v2,vfi(C)vl,v3.v4.v5,v2,v6 (D)vl,v4,v3,v5.v2,v6M.個(gè)有向伯如圖所示，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先渴歷不可能得利的DFS序列為(A)mibcfc(8)adcefb (C)adcbfe(D)adefcb15.對線性表進(jìn)行折軍音找時(shí)，要求線性表必須.(A)以廓序方式存儲 (B)以順序方式存儲,且結(jié)點(diǎn)按關(guān)a?字有序抵列(C)以鏈我方式存M (D)以鐮表方式存健，且結(jié)立筱美堪字有序揖例16.5列排序方法中.在一趟排序結(jié)束后不定能選出一個(gè)元素放在其最終位置上.(A)良接選抨抵序(B)皆泡撲序(C)歸件抵序(D)用排序17.記錄的關(guān)撰字為{46.79,56.38.40.841.進(jìn)行快速柞序.“第一個(gè)記錄為星處得到的第一次劃分結(jié)果為.(A)(38,40.46.56,79,841 (B){40,38,46.79,56,84)(C)|40,M46.56.79,84[ (D)!40,38,46,56,84.79}.設(shè)圖中有n個(gè)頂點(diǎn)e條邊,栗用鄰接表表示圖，遍歷圖所需要的時(shí)間為――..(A)0(n*) (B)0(n*e) (C)O(nXe)(D)0(n).以F序列不是塔的是.HOG,85.98.77.80,60,82,40,20,10.66)（100.98.85,82.80.77.66.60.10.20.10110.20.40.60.6fi.77.80.82.85.98.IO<?i（I））1100.85.40.77.80.60.66.98.82.10.20.當(dāng)采用分塊齊擾時(shí).數(shù)摳的空猊方式為（A）數(shù)據(jù)分成若干塊.一塊內(nèi)做據(jù)有成（B）敷據(jù)分成若干塊,每塊內(nèi)數(shù)據(jù)不必有序.但塊閭必力行FT.肉塊內(nèi)始人（成母小）的代據(jù)組成索引塊（C）數(shù)據(jù)分成若干塊.每塊內(nèi)數(shù)據(jù)仃序,肉塊內(nèi)最人（蛻般?。┑囊罁?jù)組成東引塊（0）數(shù)據(jù)分成若干塊，每塊（曲:最后一塊外）中的數(shù)據(jù)個(gè)數(shù)需相同—.填空胭每空1分，共10分）.若果用潮序春儲結(jié)構(gòu),在長度為舊的N空投性衰的的第i個(gè)元靠前插入一個(gè)數(shù)加元案，i的取值范圍是..已如二叉樹的層的兩近遍列為AHJCEFG.中序中歷序列/0BCAFEG,其后序電歷序列為3,若將n階上三箱矩陣A按列優(yōu)先腐序壓制存放在維數(shù)組中,第一個(gè)非零元素當(dāng)存于Ml］中，則於。故到Mk】中的非零兀素“jWn.iWj）的卜標(biāo)I、j與k的對應(yīng)關(guān)系是.4.囁優(yōu)一叉樹（編夫曼樹）中共（H7個(gè)結(jié)點(diǎn).則一叉樹上有 個(gè)葉子結(jié)點(diǎn).5,對棵完全文樹所有結(jié)點(diǎn)從上到卜從左到4編號.摭號】和編切的兩個(gè)結(jié)點(diǎn)處于同層的條件是..已知按后序遍歷一義將的結(jié)果為ABCD.有搐不同的一叉樹可以得到這遍歷結(jié)果..一憬m階的B樹中,通入個(gè)新關(guān)設(shè)字時(shí)若產(chǎn)生結(jié)點(diǎn)分裂.剛讀結(jié)點(diǎn)原有個(gè)關(guān)犍字..若個(gè)非逆通的無向圖被多有28條邊，則該無向圖至少在一個(gè)球點(diǎn)...圖的廣度優(yōu)先遍歷需要利用這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)..利用大小為MAXSTACKSIZE的數(shù)組百篇一個(gè)棧時(shí),若tap也表不機(jī)空，條料表示棧源二、商答小（共20分）比較順序表和鞋表的特點(diǎn).（3分）2,假設(shè)CPU每眇處理10’個(gè)指令.對于輸入規(guī)校為10?的問題,時(shí)間代價(jià)T（n）=2n：的算法要運(yùn)行多少小時(shí)？<3分）3.將關(guān)鍵字序列（7、8.30.II.18,9.14）敢列存儲到敢列表中，般列表的存儲空間是個(gè)下標(biāo)從0開始的長度為10的維數(shù)組.散列函數(shù)為H（key）（keyx3）MOD10.處理沖突采用線性探測再散列法.（3分）請將答案注明題號寫在答題紙上，試題紙上做答無效4. 畫出FIS對胸外鄰接女.（2分）（2）什么是最，NI成樹？根據(jù)你的都接我.找出該圖的一探最小生成樹“（5分）5,依次輸入序列（62,68.30.61.25.M.53.47,90.84）中元素,生成-梅中荷義排序樹,并計(jì)算杳找成功時(shí)的平均有我氏度ASL（4分）四.，「廉卜劉說法,1確,正瑞回務(wù)“是不正確回省“否”每魄I分,共10分，!在邊々示活動（A0Q網(wǎng)中,任何一個(gè)關(guān)鍵活動的延期先成，郎會’?以整個(gè)1!丫蚪延購?fù)瓿?4儂E衣小活動的有向圖中,通過快速州序的方法可以確定哪個(gè)活動先做.消除通仃不定要用枝.只在能夠用程序設(shè)計(jì)語聲描述的算法是仃效。法.矩輝壓縮存儲是為了節(jié)省空間,可能需要付出時(shí)間代價(jià).堆是一株平衡-XW.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在內(nèi)存的存儲方式.在完全一義樹中,左仃右孩子的結(jié)點(diǎn).一定是葉結(jié)點(diǎn).義樹是度為2的4件樹.數(shù)據(jù)結(jié)構(gòu)研究散據(jù)的邏輯結(jié)構(gòu).物理一陶和縣本黑作五,琮臺北用做（共15分,請先寫出存儲結(jié)構(gòu)）n（Jn個(gè)始點(diǎn)的完全一義樹存放在ft數(shù)組中（上標(biāo)為。的單元不用）,1訕找中冷兩歷過程中結(jié)點(diǎn)V后繼結(jié)點(diǎn)的算法.（7分）.循環(huán)隊(duì)列的存儲空間若發(fā)生以下變化：隊(duì)滿并需要插入新元素時(shí)存儲空間獷大一倍，哨曲寫入隊(duì)操作；StatusEnUueue（SqQueue&Q,QEIeaTypee）（8分）第二部分計(jì)算機(jī)組成原理(共75分).單沌選杼之每獨(dú)2分,共30分).某機(jī)字長32何.其中I位符號位.31仿故值機(jī)若用定盧.小數(shù)表示.喇展大正小熱為(A)?(1-2、) ⑻+(C)2U (D)2"2.float型數(shù)據(jù)通常用IEEE751單精度浮點(diǎn)效格式表示,若編譯器將Coal型變Tx分配在一個(gè)32位浮點(diǎn)寄存SSFR1中,且x=T2.25,則FRI的內(nèi)容足.(A)C1440000H (B)C2040000H(C)C184OOOOH (D)CIC20000H.如果浮點(diǎn)數(shù)的能數(shù)用補(bǔ)碼表示，則下列中的尾數(shù)是規(guī)格化數(shù)形式.(a)I.noon (B)o.ouio(C)0.01010 (D) 1.00010.在浮點(diǎn)加減運(yùn)算中，對附的原則是<A)人階向小階對齊 (B)被加數(shù)向加數(shù)對齊(C)小階向大階對齊 (D)加數(shù)向被加數(shù)對齊.若特發(fā)送的信息碼字為U10QQ11,生成多曲式G(x)=X,+x'+X+I?則什口出的CRC校裝碼為.(A)1110001101101 (B、HlOOOlHiOlO(C)11100011001101 (D)111000110011010.動態(tài)RAM的刷新是以為單位進(jìn)行的.(A)存儲單元 (B)存儲矩陣行(C)存儲矩陣列 (D)存儲位.假定用若干個(gè)2kx4位的芯片組成一個(gè)8kX8位的存儲器系統(tǒng).則地址0B1FH所在芯片的最小胞母是.(A)0000H (B)0600H(C)0700H (D)0800H.下例說法中不正確的是.(A)多體交叉存儲器結(jié)構(gòu)是為了擴(kuò)人存儲器的容，(B)主存'Cache之間信息交換的單何是數(shù)據(jù)塊(C)高速接存八有較高命中率是利用了程序的局部性質(zhì)理(D)在Cache的全相聯(lián)映象方式中,Cache塊的標(biāo)記字段記錄的是調(diào)入的主存塊號.卜列因者中,'jChcM的命中軍無美的是.”）上存的存取時(shí)間 （B）塊的大小Cath。的繁象方式 （D）Cachi?的容V0.指令后就中果用不同尋知方式的口的主要是 .（A）可良接訪悶本存＜B）找展操作碼Jt博依指令譯碼的速度（C）實(shí)現(xiàn)科'華存儲和程序控制⑺）縮加指令長度，擴(kuò)大尋址空間，提高編程靈活性H.偏移尋址通過將某個(gè)新存IS內(nèi)容5個(gè)形式地址相加而生成有效地址.下列尋址方式中,不雇于偏折尋址方式的是.（A）間接尋址 《B》基址尋址（O相對尋址 . （D）變址尋址12..鄴時(shí)序系統(tǒng)提供的三糕時(shí)序信號空.IA）—期.機(jī)圈周期,除沖（K）指令周期.機(jī)器周IW.時(shí)許做明（C）指令閹知，節(jié)拍.脈沖（D）指令冏期.微指令周期.時(shí)鐘周明.微理序控制器中,機(jī)器指令％微指令的關(guān)系是.（A）句條機(jī)器指令由條微指令來執(zhí)行（B）句條機(jī)黯指令由段做指令褊成的微程序來物料執(zhí)行U）段機(jī)器指令組成的程序可由一條微指令來執(zhí)行（0）一條很指令由若干條機(jī)罌指令組成.假定不采用Cache和指令預(yù)取技術(shù),則在卜列有關(guān)指令執(zhí)行的敘述中,甘I誤的足.（A）每個(gè)指令周期中CFU都至少訪問內(nèi)存一次（B）拉個(gè)指令周期一定大于或等于一個(gè)CPU時(shí)鐘周期f＜：＞空微件指令的指令周期中任何寄存器的內(nèi)容都不會被改變ID）當(dāng)前并序在屋條指令執(zhí)行結(jié)束時(shí)都可能被外部中勘打斷.卜列說法中止確的是.1A）做程序控制方式和組合邏輯控制方式相比.前者可以任指令的執(zhí)行速度更快（B）若采用微科序控制方式,則可用uPC取代PC（C）水平型微指令采用分段班碼的格式是為了縮短微指令的K度（D）指令周凱也稱為CPU周期..■答胭（每月3分,共15分）I，計(jì)一機(jī)中所表示的數(shù)有時(shí)會發(fā)生0出.其根本原因足什么？對干雙苻號如何切斷溢出？.存儲器系統(tǒng)采用層次結(jié)內(nèi)就次什么問也？實(shí)現(xiàn)存儲器層次結(jié)構(gòu)的先決條仃是什么？用什么來度?其效率？.為什么多體低位交叉結(jié)構(gòu)存儲器可以提高訪存速M(fèi)?1.指令和數(shù)據(jù)都存放在土存儲港中,如何識別從主存中取出的的指令還比數(shù)據(jù)？5.與城合邏期控制器相比,曲柝序按制器有何優(yōu)缺點(diǎn)？3.瓊合應(yīng)用股，每收10分,共30分）I.有兩個(gè)辯敷x和y.x=-66.尸-80.采用補(bǔ)碼形式（含的符號何）表示,x和y分別存放在寄存器R。和R1中.另外,汪。兩個(gè)寄。器R2和R3.RO.RL心和R3都是8位的寄存器.請何答下列同胭：（薯求出算用上六進(jìn)制在示進(jìn)制序列）（1）寄存嚼R0和R1中的內(nèi)容分別居什么？（2）x和y相加后的結(jié)果存放在R2寄存器中,寄存器虺中的內(nèi)容是什么？此時(shí),湛出標(biāo)志付阱是什么？符號標(biāo)志位SF是什么？進(jìn)位標(biāo)志位CF是什么？（3）x和y相減后的結(jié)果存放在R3寄存器中.寄存器R3中的內(nèi)容是什么？此時(shí),溫出標(biāo)志位0F是什么？符號標(biāo)志位SF是什么？進(jìn)位標(biāo)志位CF是什么？.箱令字長為12位.每個(gè)地址碼為3位.采用獷履操作碼的方式.設(shè)計(jì)4條地址指令.16條二地址指令、64條一地址指令和16條《地址指令.（I）給出一種微作碼的獷展方案（2）畫出指令譯碼邏輯.（3）計(jì)黨操作碼的平均氏度..CPU結(jié)構(gòu)如圖所示,包含一個(gè)累加寄存器AC.一個(gè)狀態(tài)寄存器以及分別用a,b、c和件示的其它四個(gè)寄存器,各部分之間的連坡表示數(shù)據(jù)通路.清頭表示信息傳送方向.（1）標(biāo)明圖中a、b、c,。四個(gè)寄有餐的名稱.（2）簡述指令從主存取到控制器的數(shù)據(jù)通路.（3）簡述數(shù)據(jù)在運(yùn)算照和主存之間進(jìn)行存/取訪問的數(shù)據(jù)通路.

2015年浙江工商大學(xué)845計(jì)算機(jī)基浙江工商大學(xué)2015年全國碩士研究生考試試卷（A）卷專法科EL845考洪對同：3小時(shí)計(jì)算機(jī)基地療合（敷腳結(jié)構(gòu)5s.也護(hù)系統(tǒng)5G）專法科EL845考洪對同：3小時(shí)第一部分St據(jù)結(jié)構(gòu)（75分）算法皿用基：（共4小國，父小?10分,共40分）（10分）已知二JC*的光（的）序龍歷序列為ABCDEFCK,中序遴歷序列為CBEDFAGH.1S山此一文??k蛤出其好序■歷序列.（10分）對關(guān)H干序列（712.817.611.213.904.106.45.598）進(jìn)行城柞序?濟(jì)給出調(diào)整后峭初始餐小城."0分）武用權(quán)集合！12,4,5,6,1,2）構(gòu)造哈夫曼樹.并計(jì)算哈大如期的用權(quán)路冷K度.（10分）ACE同如卜所示，未關(guān)區(qū)路橋.-.算法設(shè)計(jì)題：〈共35分）1、（10分）Q-櫬—義設(shè)為在幢悄內(nèi)，結(jié)點(diǎn)結(jié)構(gòu)為Jchild|（tesirchiid.2計(jì)個(gè)算法.前（先）序序列中處于第k個(gè)府亶的結(jié)點(diǎn).（10分,已如我性口中的元素以值遹書有序拎制，片以*?&<r存住結(jié)構(gòu).求耳一算法,副除表中所有人丁x且小Ty的元第（著表中不在這株的元本）網(wǎng)時(shí)桿放橫射除結(jié)點(diǎn)空間.（15分）國設(shè)計(jì)?一個(gè)算法,求山給定字符串中的?對體字符！T.?*."efghiihgfabc-.最KF標(biāo)字符率,fghiihgT.?opqrslww".UK?對稱字符本?是-abcdefghijk,.無?時(shí)焦字燈事、第二部分操作系統(tǒng)（75分）--以交公（每空2分.共20分）.從向I種上看.每個(gè)進(jìn)程由二部分融成，它力讓 .和..嘉蛻中存在多個(gè)班這些班以對共事修*的使用存在事不同的相4制的美系.一“雄 一一關(guān)系,另一種地 關(guān)系.3、地如歡財(cái)必指將腳序中的城址》｛帙內(nèi)內(nèi)存中的地計(jì).在分更胃理最蛻中.為實(shí)現(xiàn)地給轉(zhuǎn)換口工了控制寄存給,其中存放的緞 在內(nèi)存中的起始墟址.1/0Q&技信息存取的?付進(jìn)行分類,可分成決和字符做備.磁你同丁校瞽.Kl/Ctam主要采用控制方式.

（共3小題.w小-5分15分）（5分）在創(chuàng)建一個(gè)進(jìn)程，件系統(tǒng)需要完成的士蜜1件給什么？（5分）操作系蜿中存在晴厘二級灣度.它們各有何作用？（5分）文件物■結(jié)構(gòu)中存在嘟二即站構(gòu)？著有何優(yōu)劣？Z.蚌合H（共3小國.乂加分）h（15分）若某務(wù)收果同分頁式存怯管理方式.頁表放倉內(nèi)衣中,系統(tǒng)中流有怏*（TLB）.（I）油出諼內(nèi)在管理系統(tǒng)的邏?地址到物現(xiàn)地H的替換示意用.（2）頁面大小為4KB.建堂地批空間為24KB,頁表的內(nèi)弁女卜衰,r?一一一—一r甲幀弓］。1A50010002B10005C|3 0006AJ40008F1I5,-3FD00]劃邃《1地卅0x3005濟(jì)換成物理皿為多少？恰比計(jì)算過界（01發(fā)示十六遺整數(shù),初珂地處怯梟4求也以十六進(jìn)制我示）.（3）S果訪向一次內(nèi)。妥I5n*.快收拘命中率為85、.并找快發(fā)的時(shí)閭為0.5ns.計(jì)霓諜系統(tǒng)的有成功問時(shí)間.（15分）破疝共。200個(gè)料面<0'199）,它剛剛從92號修造修刎98，）他10完成*假設(shè)此時(shí)系統(tǒng)中*侍5問磁型的出道序列為，190.97. 90. 45. 1S0, 32. 162. 108, 112. 80.試給出果用卜列畀法后破頭樓動的■了.并計(jì)算difiifc*.I）FCFS算法:2>SSTF算法;3）SCAN算法;4）C-SCA'X法;5）100K算法（10分）現(xiàn)有贛人進(jìn)NPA.計(jì)算進(jìn)NPB,*出班內(nèi)PC廣發(fā)執(zhí)行.三個(gè)選同共享兩個(gè)螳沖區(qū).如出所不：BuRcrl BufTcrlBuRcrl BufTcrlPAR次*入一個(gè)敢據(jù).放入到Buffed中,Buffer1人小為N1.PB15次從Buffe”中拿山一個(gè)依據(jù)計(jì)算,然后將妖果收入Buff”2中，Buffer人小為N2.PC毋次從BMm2中拿出一個(gè)敢再道行*山?要求果用wartagn?l（成P.V）排作.設(shè)或合適的P!步機(jī)*.保證這二個(gè)進(jìn)出的對步執(zhí)行.對Buffed.Buffer2要求立斥必修?

浙江工商大學(xué)2014年碩士研究生入學(xué)考試試卷（A）卷考試科日：845計(jì)怵機(jī)基磁燒令 總分?（150分）考試時(shí)Wh3小時(shí)第一■分或據(jù)結(jié)構(gòu)（76分＞海齒及（共5個(gè)小■,冤小員6分,共30分）I.分析卜面代碼段的St雜度.sSIM?0：vhile（hub＜n）Ii":sunri;I.若a.b.c依次壓入堆枚.UPS出所有可倦的出Ift序列.3.已知一個(gè)義料的中序遑歷站乘她TFXIRAMLPK.后序遑歷姑果姑TXFUU0CPR.請畫出央二義村.4,請府述數(shù)列成數(shù)中M次沖突的常用方法.5,請耳出卜面無向圖的轉(zhuǎn)接矩陣和郛接我.二.躥合分析同（共3個(gè)小題,年題15分，擾45分）.請役計(jì)一個(gè)由數(shù)intIsMatcMchar*expr）.來判別表達(dá)式中括］I（超括IN括儀,。，、方括級'口'、花招冕'（卜3#＞艙否正瑜配對.若正確此時(shí).■出I.否購■出0?.璃改計(jì)一個(gè)庫法內(nèi)定兩履二義鞫是否相似,兩棵一又樹相似.?￡＞（1）如果它旬岳為空或糊只有一個(gè)節(jié)點(diǎn)?（2）切果它的左子材相螟井且右干樹相似..一物很公司設(shè)在不鈍城市的中特站之間的拓?fù)浣Y(jié)構(gòu)可用圖來我示.假定出用匏推矩陣表示,謫設(shè)計(jì)一個(gè)算法，■出中轉(zhuǎn)站Si到中轉(zhuǎn)站SJ的所存筒單隔及（藺單路柱是指路柱上的跖點(diǎn)不*量）.

第二修分掾作系統(tǒng)（76分）一、筒答霆（共4個(gè)小d.年小■5分,共20分）.商述！》作系統(tǒng)中進(jìn)程的構(gòu)成,它與程序的區(qū)別？.死政發(fā)生的四個(gè)必要條件是什么？.筒述文件在物理介質(zhì)上的三師存放方式.并分析它。］的優(yōu)點(diǎn)及缺點(diǎn)..簡迷CPU0度中可能出現(xiàn)的護(hù)航效應(yīng).維合分析H（興4個(gè)小d.共55分）U0分）若干個(gè)等符功何娥fit者依次要切向的磴道為20.M.?.4.80.12.76.但設(shè)每移動一個(gè)磁道需要3修秒時(shí)間,移動曾當(dāng)前位于41號磁道.請按下列算法分別寫出坊向序列，并計(jì)算為完成上述各次訪問總共花將的尋道時(shí)閽.（城道筑號從I到100）（I）先來先事務(wù)算法；（2）■蚯尋道時(shí)間優(yōu)先算法.（3）掃描算法（當(dāng)前磁頭移動的方向?yàn)橐厘弁ㄓ茫?5分）一個(gè)耳序具育460個(gè)字節(jié),它的內(nèi)存訪問序列如卜,101110417073309185245246434458364（1）若頁面大小為100字節(jié).請給出正■的頁號訪問序列.（2）若物理內(nèi)存A有200字方的有效空間.果用FIR）頁面置換算法?諦計(jì)克軟頁次IL并輸出計(jì)JI過程.（3）若物理內(nèi)存M有200字節(jié)的有效空間.果用LRU寬面置換算法.諦計(jì)算軟頁次數(shù)，并給出計(jì)算過程.3.（15分）考慮系統(tǒng)中一tfl進(jìn)程，它們的CPV執(zhí)行時(shí)間（CPU-burstti?e*位：5??s>和優(yōu)先級(Priority)?F：ProcessBurstTiaPriorityPl83P211P323P424PS52假定。時(shí)刻進(jìn)程按Pl.P2.P3.P4.P5的次序到達(dá)：（!）分別擊出進(jìn)程采用FCTS.SJF（最短作業(yè)時(shí)間優(yōu)先）.等拉占優(yōu)先舞（小的優(yōu)先級故衣示具有育的優(yōu)先版》,和醺（roundrobin.qstg=2?）調(diào)度靠法的甘特HL（2）計(jì)茸那個(gè)進(jìn)程在（1）中善神調(diào)度京法的圖相時(shí)間.（3）計(jì)算每個(gè)進(jìn)程在（1）中善神調(diào)度算法的等行時(shí)間.（4）比較羯個(gè)進(jìn)程在（D中善種四度11法中的平均周轉(zhuǎn)時(shí)間，?聆調(diào)度算法最小？答案寫在杏通《￡答案寫在杏通《￡上.可在試卷上無依第2頁（共3頁）4.“5分）卜圖是一個(gè)從檢盤■人到打卬機(jī)，出的數(shù)據(jù)處理at程圖,其中便盤*入送界pi通過懾沖區(qū)bun（大小為?）把?入數(shù)據(jù)傳送給計(jì)算進(jìn)程.計(jì)算進(jìn)程間把處理結(jié)果通過饅沖buf2（大小為n）傳送給打印進(jìn)程P3.若touf2已裝滿數(shù)據(jù).則計(jì)算進(jìn)程丟棄新生成的數(shù)需.bufl和buf2為險(xiǎn)界儕源，試耳山■盤輸入進(jìn)程.計(jì)算進(jìn)程及打印進(jìn)程間的同步咽崎入速程—bufl-計(jì)算進(jìn)程-buf2-打印迸理谷案寫在答府抵匕弓在武卷上無效加3頁（共3頁）浙江工商大學(xué)2013年碩I:研究生入學(xué)考試試卷 （A）卷考試科th845計(jì)翼機(jī)基礎(chǔ)綜合 總分：150分 考試時(shí)間：3小時(shí)數(shù)據(jù)結(jié)構(gòu)（共60分）（12分）已知一個(gè)：叉樹的中序遍歷結(jié)果是12543,后序遍歷結(jié)果是12345.請畫出這課：叉樹.（12分）從結(jié)節(jié)點(diǎn)1開始，用Prim峰法時(shí)出下圖的最小生成樹的過程.（12分）已知?個(gè)電報(bào)包含的字符為"a".一"，"c","d"和它們出現(xiàn)的頻率次數(shù)分別為｛25.9,12.8.11）.請給出字符的Huffman編碼.（12分）已知一個(gè)整數(shù)序列12017221260321615）,清幽出快速排序的過程和最后的結(jié)果.（12分）請構(gòu)造函數(shù)inifulKblrcc*bt）,判斷顆：叉樹是否為滿：叉樹.是返回I,否返回0?二、計(jì)算機(jī)組成（共45分）I.（9分）畫出卿型的馮?諾依登計(jì)算機(jī)硬件系統(tǒng)組成框圖,并簡述各功能部件的作用.（9分）某機(jī)器字長為16位.請寫出下列各種情況下它能衣示的『進(jìn)制數(shù)的能用（采用1位符號位）：（1）無符號整數(shù)：（2）用補(bǔ)碼表示的定點(diǎn)整數(shù)：（3）用5位階碼（含I位階符八11位尾碼（含1位數(shù)符）表示的規(guī)格化浮點(diǎn)數(shù).（9分）己知Cache存取周期為30ns.主存存取冏期為120ns,執(zhí)行某段程序共訪問Cache5000次，訪問主存200次.求：（I）Cache命中率：（2）平均內(nèi)存訪問時(shí)間.（9分）舉例說明中斷處理流程.（9分）某機(jī)舞中采用RAM芯片8KX8銀成16KX8的RAM區(qū)域,起始地址為8000H.假設(shè)RAM芯片有CS和WE信號控制端,CPU的地址總線為AA”數(shù)據(jù)總找D.D.控制fj號為RW.MREQ.（I）請?jiān)O(shè)計(jì)地址譯碼方案：（2）廊出RAM和CPU連接圖.三'操作系統(tǒng)（共45分）（8分）描述進(jìn)程的三個(gè)法本狀態(tài)以及它們之間轉(zhuǎn)換的典型傲因,（9分）在單道程序環(huán)境下若仃四道作業(yè)，具進(jìn)入系統(tǒng)及所需的執(zhí)行時(shí)間如下表所示：表1四道作業(yè)的進(jìn)入和執(zhí)行時(shí)間答案丐在答題紙上.”在試卷上無效第答案丐在答題紙上.”在試卷上無效第1頁（共2頁）作業(yè)進(jìn)入時(shí)間（小時(shí)）執(zhí)行時(shí)間（小時(shí)）18228.50.53分別按先進(jìn)先出以法、短作業(yè)優(yōu)先算法、響應(yīng)比高存優(yōu)先的調(diào)度算法調(diào)度,則其平均周轉(zhuǎn)時(shí)間分別為多少（上述二種辦法均為II搶占方式）？（10分）有一個(gè)閱覽室,讀者進(jìn)入時(shí)必須先在一張登記表上進(jìn)行修記,該表為內(nèi)￡一座位列一表目,包括座號和姓名，讀齊離開時(shí)要撤消登記自息：閱覽室共有100個(gè)座位.節(jié)閱覽室滿員后,讀者不得進(jìn)入,只能在室外等待.試用P,V操作寫出上述問題的同步算法.（動作部分可用文字描述）假定某時(shí)刻用戶貞衣中（9分）某虛擬存七器的用戶編程空間共32個(gè)頁面,每頁IKB,主存為16KB.已調(diào)入在存的頁面的頁號和物理塊號（頁架號）對照衣為：假定某時(shí)刻用戶貞衣中同：（同：（1）虛擬存IT器的功能是怎么實(shí)用用?虛頁號物理頁號051102137（2）邏輯地址0A5c（H）、1A5C（H）對應(yīng)的物理地址分別為多少？（如果主存中找不到,即為更失效）（9分）假定系統(tǒng)中有五個(gè)進(jìn)程（P0.Pl.P2.P3,P4）和三種類型的資源（A.B.C.D；.按銀行家算法中.若出現(xiàn)卜述的資源分配情況（在T0時(shí)刻的資源分配情況如卜圖所示）；最大需求己分配尚需求剩余進(jìn)程ABCDABCDABCDABCDP0001400320012Ih21P1275010001750P236101013542356P?098403320652圖T0時(shí)刻的資源分配圖問：⑴TO時(shí)刻系統(tǒng)安全嗎？（2）如果此時(shí)進(jìn)程P2提出請求Requcsl（I.2,2.2）后，系統(tǒng)能否招資源分配給它？答案寫住答題紙匕寫在試卷上無效第2頁（共2頁）3.江蘇科技大學(xué)計(jì)算機(jī)攝礎(chǔ)綜合歷年考研真題2014年江蘇科技大學(xué)2014年江蘇科技大學(xué)845計(jì)算機(jī)基告考研真題江蘇科技大學(xué)2014年碩士研究生入學(xué)考試初試試題弋MS科H名4： 計(jì)算機(jī)U峰合 4分：?注意：3認(rèn)4他?冬?級上的連叁事事;6所方吝霰必用寫桃旦眄上.?械*＞草稿*.**?：③*■通4銀發(fā)僭軍鼻鍛一起，入“堂，文W;④本科R考試為(1)IUK姑構(gòu)(2)計(jì)H敘■姐*原*,(1)數(shù)據(jù)結(jié)構(gòu)試題一、選擇題(每小HI2分,共15小E,小計(jì)30分).?序存儲，■構(gòu)中敷據(jù)無H之何的愛輒大瓜是由( )出示的.A.紋件納構(gòu) B.UH性體構(gòu) C.3W0.ffilt.卜面《 )不是才格所必饗R善的行性.A.TT分性 B.畸定性C.高效性 D.ajfjft.若找性表J?*用般今艙在就一個(gè)元1｛之后播入十元型"射除■n一個(gè)元素.購果用( )〃41方法?》營時(shí)間.A.*HA B.帶星指針的*幅壞fit表C.Ml壞刈隨& D.電頭蛇r竹的小循環(huán)做表4.4nrrn個(gè)精點(diǎn)仃序me*中始人一個(gè)新站點(diǎn)力使之仍然疔序的打闿贊雜度修().A.0(1)B.O(ii) C.娛)D.O(nlo?,i()TOC\o"1-5"\h\z0梅S和隊(duì)鈍Q的初始狀態(tài)為主.元Itrhe2.e3.f*e5.eti依次通過枝S.耀個(gè)元素必加先入校痔出帙，Hi惶后同送入隊(duì)列Q.打6個(gè)元,出隊(duì)列的?序星”2.Z.e3.c6.eS.el.凰&S的\片至少應(yīng)逢金( ).A.6 B.4 C.3 D.2 .6.小大81配的KMPW法中士巾翱足式的，jfHk什分例為i|Wj.。打福利的冬同?拘不相WM.( ).4.iPKjwab.僅jpiaic. d.；不問那.j不網(wǎng)霸.( )不俄幅為特媒融環(huán).A.挹狀短陣 B上或產(chǎn)三角亞陶 C.財(cái)煉曲陣D.0以建限. 個(gè)同修為k的蠲一X科乂"n個(gè)儲點(diǎn).K中有z個(gè)時(shí)干站.點(diǎn).內(nèi)。( ).A-n=k4?uB.2nak-n.C.n?3k-|D.n*2m-lM［頁共6jfiTOC\o"1-5"\h\z.由.5.7分別什為叫結(jié)點(diǎn)權(quán)值為透哈人什科,黯權(quán)路冷K度為（ ）.A.58 B.68 C.48 D.74.GM個(gè)1?1通無向陽,共杳18條地.剎津出至少仃（ >個(gè)煩*.A.1 B.5 G6 D.8.&010000個(gè)元素.衲SI用餐快速反挑通山前10個(gè)鼻N的.果用（ >力法Ulf.1快速推序 B.城得序C.啊橙場撲抻序D.門片H序.已知8個(gè)碼值為：42.26.18.37.64.78.58.44.36.技制依次掃播插入一收從空開妁的一叉痔序一的方法健。二叉，?序樹，在找值為5?的結(jié)點(diǎn)所需比依次的為（ ）.A.2 B.3 C4 D.S11采用分塊內(nèi)推時(shí).t；紋性收中共有225個(gè)元素.科找每個(gè)兀事的依率相同.代&采用娛序在找來確定站力.所a的續(xù)時(shí).年塊應(yīng)分別含（ ）個(gè)納點(diǎn)最值.A.12 B.10 C.15 D.25.在一個(gè)7冊的B樣上.除根外的鼻個(gè)曾外結(jié)點(diǎn)所含的f歸數(shù)最少為（ ）.M3 B.3 C.4 0.5.適合！茁于比較大H碼的動金什提方法是（ ）.A.履印0故 B.改則在找C.*引，序齊找 D.折t聲找二、填空題（每小?2分,共12小■.小計(jì)24分）.故榭的《本小位是.在數(shù)盤結(jié)構(gòu)中遍*竹為個(gè)數(shù)據(jù)十位進(jìn)打處瑁.,■萍我的第一個(gè)元素的存健地卻此50.抵個(gè)元H的檢度為5個(gè)十的.則就20個(gè)元素的〃儲地卅4 .3段的?人操ft特性總際龍先出UFO.從列的疑人報(bào)件特性是..維敏組A中打的卜林從5到8.的的卜&從4妁15,技行優(yōu)先存儲.m個(gè)兀家占5個(gè)存儲單元?N5][4]的〃儲地址是500?則元宗A網(wǎng)（口1的存儲地址掄.. 脖。蛛的煌11次.其13株竹體現(xiàn)在..某叉樹的先序0歷序列讓ABDECFG.中序?歷序列是DBEAFGC.則4無序■歷序例始*個(gè)具有。個(gè)頂點(diǎn)e條做的有向圖的拓?fù)錄_網(wǎng)的W法.凡時(shí)間包雜度為.8號將大蹲亨獷例：15.19.73.61.82.24.47.窿成小楸地.只需m73、 交換..快速抖序在n個(gè)收必丫現(xiàn)為時(shí),W法效率反而降為O（n2）..對8個(gè)碼值所構(gòu)魂的一叉排序椅,為找一個(gè)碼值的平均比較次數(shù)為.11給定一個(gè)鍵值序列：25.43,62.31.48.56,梟用散列函數(shù)川k）=kmod7,則元素48的同義詞是.12.在一株5階B件中.除根結(jié)點(diǎn)和外結(jié)點(diǎn)外，句個(gè)結(jié)點(diǎn)的子樹數(shù)目最多為.三、計(jì)算題（共12分）（6分）給定權(quán)值集IL4.7.10,6,8）.試分別以它們每一個(gè)作為葉結(jié)在的權(quán)值構(gòu)造相應(yīng)的哈大曼樹.力il京式帶權(quán)路程K度.（6分）已知一批關(guān)健字為：26.36,41.38.44.15.68.12.6.51.25,22.要求裝境囚子為0.8.選用除由余法IMKeyMKcy、p作散列函數(shù)，p=13,用線性探作法婚決沖突.構(gòu)造閉儂舛衰.并計(jì)算存找成功卜的干均住找長度.四、算法設(shè)計(jì)題（總計(jì)9分）.（4分）設(shè)有一個(gè)整數(shù)頌序喪.反計(jì)算法將其調(diào)帙為前部為令數(shù).，后睇為偶數(shù)，11時(shí)間復(fù)雜改為0（n）,空間復(fù)雜度為0（1）..（5分）嬪丐算法.求給定關(guān)憎碼在一義掙序樹中所在的￡效.(2)計(jì)算機(jī)組成原理試題一、單項(xiàng)選擇JS小端i分,共10分).卜列數(shù)中餐小的數(shù)是( ).A.(100101)>B.(50).C.(100010)?D.(625)?.( ，泉示法主要用丁我示存點(diǎn)數(shù)中的冊碼.A.原碼 B.料碼C.反碼 D.蜂碼1在機(jī)得效( )中,寫的表示形式地唯一的.A.季碼 B.熱碼C.移碼11反碼.馮?4依曼機(jī)1作方式的*本特點(diǎn)C).A.%指令薄?數(shù)據(jù)渣 B.按地址訪問井看序執(zhí)行指令C.應(yīng)槿！ttr D.存貯器按內(nèi)齊選產(chǎn)地計(jì).在定點(diǎn)一或制運(yùn)為器中.城法地U股也過( )來實(shí)現(xiàn).A.厥碼玷尊的一遺制城法81 B.於碼匕K的一道制減法器C.原網(wǎng)運(yùn)算的卜堪加那法賽 0.計(jì)碼達(dá)11的：遺制加法器.寄存器方按4址方式中.推件敢住( ).A.需存81Bt存餐無C.堆棧 D.科'序計(jì)數(shù)需7,微積序控制5中.機(jī)器指令，WU&令的關(guān)系是( ).a.n條機(jī)器指令由條做指令未執(zhí)行一段機(jī)器指令皿成的理序可由一條6指今執(zhí)上一條。指令由若干條機(jī)1S指。物成D.句一條機(jī)器題令由段用他指令0成的6程療求執(zhí)行.在?綏中斯系統(tǒng)中.CPU一口舊咫中*.則立即大閉( )林A.以防4次中斷股務(wù)站取的同級的R他中斯源產(chǎn)生另一次中斷堪打1擾.丸中貨允胃&中斷請求 C.中曲屏4r I).中斷保護(hù)UitWtflTK32O.其存儲界俄為1MB.心楂T字蛔卅.它的WE范因叢( ).配4MR 區(qū)2MB C2)1 D.IM.EPR（N是指（ ）.A,注弓存儲器&只it有儲4 C,閃速存他舞D.紫外光擦除可*界只“〃儲我二.填空題（年小』2分,共10分）.在計(jì)W機(jī)傳統(tǒng)術(shù)論中,將和合在一起稱為CPU.前將CPU燈倉在一起陳為主機(jī)..形成指令他卅的方式.喙為方式.盯噴序3址和?址兩a.使用 來跟蹲..RISC指令系統(tǒng)的量入特點(diǎn)是，.冏定.的類少..假品總線中傳送的信息神類不同.計(jì)尊機(jī)系統(tǒng)總貨可分為三綱.分別為總線、.總線和總線.s在一個(gè)CPU周期中. 次健定義并執(zhí)行多個(gè)并行梅仙盤命令的Hk疥令叫.4個(gè)CPU周期中,栗用操作碼方式.次只能控制信息從某個(gè)源解料到霞個(gè)日林IK竹拉”過料的微指一叫?后者實(shí)現(xiàn)條機(jī)淳指令的依用序■比侑看歸耳的e程序.三、綜合題（共55分）（7分）已知x3OlOOl.0.1100采用雙符號律求[*?/?=?.ixy}?=?.并指出讓便結(jié)果是否泡出.（10分）沒有浮點(diǎn)效X-2X0.0110011.y-2'x（-O.”10010）.附碼用4位移碼衰示.屋敷《北符號傳）用8位補(bǔ)碼費(fèi)小.求flXy]?.R未門接用補(bǔ)叫完成屋數(shù)修法ifill.匕算的梟尾數(shù)仍保留867（含符號位）,并用尾依之后的4位值處理有入攤件.（10分）IIOlWy=-O.1011.用比收法訃碼f>金法<H'l&xrth公式.）求x?尸？4.110分）St機(jī)賽的指令格式如卜圖所示，0PXD15 109 87 0陽中X為4U-特征僮，H.X=0B4,不費(fèi)址1X=1時(shí),陰受時(shí)寄存JSXiig行變址：X=2時(shí).陽曼0市存舞X,?Hj關(guān)址tX=3時(shí).相對尋址.設(shè)（PC）M234H.（X,）MJO37H.（W-I122H.誼■定卜州指令的白效地址（均用十六進(jìn)般入示.H表示卜六遏制）.(D4420H (2)2244H ⑶1322H (4)352IK⑸6723H(10分)累計(jì)IT機(jī)系統(tǒng)的內(nèi)存由cache構(gòu)成,cuehe的存取冏財(cái)為45m.上。的4取周期為200n,.已如在段給定的時(shí)何內(nèi).CPI共訪日內(nèi)44500次.耳中M0次優(yōu)問士存.M>cache的命中率是多少？E坊網(wǎng)內(nèi)存的平均時(shí)畫是多少n??Cwhe?土存事統(tǒng)的效率是衣少7(8分)陰RXX8位的RAM芯片iill?一個(gè)32KX8位的WiB.RAM芯片有四個(gè)輸入?h、衣彳效時(shí).饃片透中.當(dāng)府/m=1時(shí).執(zhí)行準(zhǔn)揖件：當(dāng)R/mmO時(shí),執(zhí)行與舞行.C求赤山此春UtM蛆成結(jié)構(gòu)圖(包括。E的連接).江蘇科技大學(xué)2013年碩士研究生入學(xué)考試初試試題（A卷）H日代竭； 845“同名低： 計(jì)算如?-J鼻合（B&二） 晨價(jià).ISO?注意《認(rèn)真回讀*星城上的逵童事項(xiàng)：②所需各索必短耳電迥上,￥和半試盤或生草修弧士政；Q本認(rèn)釐圾境隨￥4統(tǒng)一**人迷?11中文?；④本科耳才達(dá)為可選二，才叟從如t”b（221V-（，）卅日中速#26flAMWg. HU._（1）計(jì)算機(jī)組成原理試題一、單項(xiàng)選擇題'脩小■1分.共10分）I.洛?諾依生機(jī)I件方式的M本朽點(diǎn)足（ ）.*.多指令流單數(shù)摳潦 B.懂地加訪問力■序執(zhí)行指令C雄棧柒4 D.右七方核內(nèi)力總界域用2.4機(jī)器般（ ）中.專的&示杉式是唯的.”碼 B.林碼G幡碼D,反碼.在宅點(diǎn)一送制也的器中.M法玷M般通過（ ）條實(shí)一.A.原螞運(yùn)H的—遇耕減法IS B.樸碼運(yùn)的的_進(jìn)制破法器C.用碼也W的I班曲加法X I）.孫碼造M的一進(jìn)制加法2XTOC\o"1-5"\h\z.其計(jì)算機(jī)字及32位,其"儲齊0為4MB.號按丫字竭址.它的?址范國坦（ ）.-1MB B.泗 C.2H D.!MEPROM是指（ ）.A.潘干存儲黔B.只讀〃依58 C.閃速〃昧器D.縈外光捧除用炮程只讀行口器1/ZU2SWCW之間:DMcache的臼的是（ ）.A.皖決CH和主存之間的速儀匹配M國B.獷人士存貯I#容量C.獷人E中的刖芍存U的數(shù)HD.既獷人上存r?舞容量,乂擴(kuò)大CH中通用而存M的數(shù)W.指令的尋址方式右眼序和跳跳向科方長.采用跳躍尋址方式,可以實(shí)現(xiàn)（ ）.A堆極尋址 B程序的條件轉(zhuǎn)修C.程序的無條件轉(zhuǎn)移 D.程序的條件轉(zhuǎn)移或無條件M移由fCPU內(nèi)部的掾作速度較快.向CPU坊向一次主存所注的時(shí)間較長*因此機(jī)舞周.期通常用（ ）宋規(guī)定.A./件中讀JR一個(gè)指令？的U知時(shí)間 B主行中讀取個(gè)散燃字的修長時(shí)間C主件中寫入一個(gè)數(shù)小字的平均時(shí)間 0主存中取個(gè)效蛔字的平均時(shí)間.系績總線中地址線的功能足（ ）.A選擇主存單元地址 B.填擇遙行信息傳輸?shù)牧６珻.選持外存地址 0指定主件和I/O設(shè)善接口電路的地址.在艙級中斷累驚中，CPU口用應(yīng)中斷,畫上抑大角< ）標(biāo)上,以防本次中斷明芬精火前同1?的JC他中新潭產(chǎn)生另一次中斷進(jìn)M干擾.A.中新允許U.中斷請求 C.中斷解觸 D.中臥保護(hù)二.填空題,每小婚2分,共10分）.移科&示法_L瞿用「我示 敢的階網(wǎng)E,以便］?比收兩個(gè) 的人小M. 愜件..存儲冊的技術(shù)指標(biāo)。.....在一個(gè)CPU網(wǎng)期中.一次能定義并執(zhí)行多個(gè)井仃株什詵命令的指指令叫 -右tCRU它用爆竹碼方A，一次月偏拄酬信息從某個(gè)海都修刎某個(gè)口心酸。熱h1"的微指令叫.后方實(shí)現(xiàn)一條機(jī)器所令的布用字曼比福褥偏弓的BHY序 ..RlSClfi。系維的?人特色.冏定.牌矣少..在罐布縝拄制器中,杷投做探代右情為產(chǎn)什力門冏定時(shí)序拉M伍q的建銀電跳.liHSW電路站熱曲知構(gòu)成的H雜幟比網(wǎng)絡(luò).為執(zhí)行不同的指令時(shí).通過&活一摹列坡此微不相同的火未一對指令的婚tth三、綜合黑（共58分）.（10分）*“博機(jī)殺父的內(nèi)存儲網(wǎng)由cache⑷t〃幢質(zhì).owhe的。地瑜刪為451H.tU的存取周期為200m.已卻在一段錚定的時(shí)間內(nèi)，CR共防何內(nèi)。450）次.X中340次訪向上存.Micache的命中率虺多少7 .CH：坊向內(nèi)存的平均時(shí)間站多少n$?C3）Cache-主存系&的效率蚪多少？ 、.（10分）已他「S.|聞他廣0.1011.用比我法撲碼傅乘法，的800th公式.）^??>?18分）用8KX8俏的RAM芯片評J&>32KXH位的?！捌?RAM芯片《網(wǎng)個(gè)?入”:》序“歡時(shí).該片迭中."月，'m=1財(cái).執(zhí)，ii*柒件?當(dāng)什/訴±0時(shí).執(zhí)行”熱仲.要求諼出此存MUS餌成標(biāo)構(gòu)用（色拈。CHttiilt）.?出切步g山&喝k?明崎坳*anvwmwu國蚓圖w*皿4嫡w婢用'i%同/國土身*明”呢?！窘衸13靖陰女與??>?<!<2?1#"**□’3-8-VSi^hlVtPBUWW*WJI山〈的。rW”93(?￡)9HEKZ4KS)HIZS￡(t->HSZEl(E) HV?-2Z(Z)KO^KD—'/4冬等H?坐*腌下*IIM峪)西琳襠空處專身網(wǎng)43”生WII?(T0也￡00=(K)'UKol=CM)枳?—舊冊?/￡=X茶US?*整方朱祖基出?收Z-X”"為9第3痛以副/苓出*收CX?神芟+'WO=XK.川利，，稗3MX6國0 28 601 S1aXdo‘生妁SH叫第做心果端SRWK（好01）巧?M&Y串苗隔切々，柒UN礙由卅M"（06取號）NB裾由出修物SfWli硒?總邱十步通聲M￥G，#仲巖。/諉,*[*x?J*的#圖8M（可白狼tWM^rWlOOIHO）x,Z^ttOOIIOOx,^J?lBVi（tt?<^?）?(2)數(shù)據(jù)結(jié)構(gòu)試題一、填空題(每題i分,共10分).你法nrr五個(gè)符性.分域是仃零個(gè)或玄上?入，n個(gè)或u外輸出.有列件,偷止性和()..俄有一個(gè)I。階的對秣W陣A采用X，解〃儲.A[0][0]為筠一個(gè)兀茶.其白楠康卅為d.何個(gè)元KAI個(gè)存球中山.則兀KAl6H7的存卜為().XdfoJ義加1f"n.(h.tc.di),e),用llead和TM1咕數(shù)取出15中原子d的的管?()..圖的?山優(yōu)先西歷所用刻的我也結(jié)構(gòu)足<>>.MT .L25,22.10.29,.13.11).一定悵有了點(diǎn)的二投鎮(zhèn)琳利同，？；按二叉撐序網(wǎng)的鍬讀數(shù)列.M1件找個(gè)數(shù)的平均比校次數(shù)為<1..K取為25的有字表未用折子15拉,共為()個(gè)；iik的齊推長度XH..IS定常,死⑵M5.劍.果陽的改列的故為H(k)d?odII.劇元「61的同義詞見<)..對刊記錄<H.IR.16.IX15.22.17,團(tuán)63)理行八接垢入樣序,與把工7個(gè)記錄17必入依仃序々時(shí),為尋找插人竹置W比校:)次..在7階B樽中網(wǎng)站點(diǎn)所值M的犬德瑪個(gè)數(shù)從匕林的少分別為(.>..即樹的所有叫納點(diǎn)移該<)在一個(gè)能中.二、選擇題(每181分,就20分)I.假收行如卜遺尸緡女愛刷：士人和去「可以村”群長遺產(chǎn)；子女可以施承父家或母?的笳產(chǎn)if女間小酷《111維次.樹&r讀遍/事承大系的母介活的數(shù)據(jù)情構(gòu)曲渣林( ).A.H B.圖 C.相性化 D. 4畬2?卜而( )不是算泣所必須I]瞽的折性.A.仃列性 B.虢切性 C.。救性 D. 41jtl3.若情表中的常用的預(yù)作是4與后個(gè)結(jié)點(diǎn)之冗拙人個(gè)站點(diǎn)和劃歐個(gè)站點(diǎn).Wl?UI( )存堿〃法第節(jié)看泡》時(shí)間.A.甲附表H.循環(huán)“觸表C.單附環(huán)鎮(zhèn)&D.書屋街「的中改.對丁n個(gè)元泰就成的或性表,建立個(gè)行力中型表的時(shí)間U架屋足( ).A.0(1)B.0(n)C.Otn1) 0.OlnloHrfil5.A殆耳久健求的p即指玷/與始人s所指川口的嫩竹姑( ).4p--*neMi^s.4-"zim-p.r>->neil->prior?fi；5-.ncMi^p，nc*t;

p-/ncxl3s:'ncxL/pricf;s->|inor-n.s-next-p-ncit,s->prior^p.xnex?-p'next;pnext-8;pnextpriorFs*prior?p,sncit^p-zncut;p-iM-xt->prhn-s:p-Xwxtr.設(shè)US加隊(duì)列Q的切她狀6為中,JcKrl.c2.e：?.Mel楨依次通戌棧$.一個(gè)兒表山枝后即進(jìn)入隊(duì)列Q./6個(gè)幾薇山隊(duì)的哦用比*J.M.e5、el.rt.el.則枝卜的力討至少就讀是( ).. 決計(jì)算機(jī)L機(jī),“I印機(jī)之沏速應(yīng)不M；配問題時(shí)逋常小—個(gè)"印饋沖。藻嫂沖|?川謂是個(gè)( )雄札A,故 B,隊(duì)列C.M.梅鼓物稱為附機(jī)存取地檢是內(nèi)力( >.A.數(shù)粗兒靠型煙機(jī)的 K對數(shù)州仟兀*的存取時(shí)間是相等的G劭時(shí)可以對敏利進(jìn)打訪向 D.轂用的存體結(jié)構(gòu)足不定.卜面( )不思丁為憬址M.A.妙韻規(guī)輯B.三角如陽 C.林遮規(guī)30.對稱地陣.若「義衣A調(diào)足llo?d<A)=Trtll(AJ.)MAA( >.A.()B.(())C.(().())y.((),<).())ILiQ義利白二個(gè)彷力.的K漢僅為( )C.[log3nj+lD.不附惻定個(gè)局也為h的漏又網(wǎng)共行“個(gè)品點(diǎn).K中百i?個(gè)叫廣姑巾,則"( >成立.A.n-h*?H.h*?-2nC.?=hI I)."2?-|IXUh*林中右4爆樹,將中格力的個(gè)數(shù)依次為n】.“2.g.rtl.M把A林找整版XAH.H根結(jié).&.的。子樹L。( )個(gè)百點(diǎn).A.iil-1B.nlC.nl，n21n3 l>.n2，n：“n1M.GM 通無向圖.具仃布條妝.則談圖十少。< )個(gè)偷點(diǎn).A.8 氏9 C.10 0.H.堆的筋狀是W(A.二叉井序樹B.i聾一義幟C.充上二義樹D.刑定樹.QOlCtOfK)個(gè)兀本,禮室用AJ快的速值搞選出優(yōu)1期)個(gè)助人的.XMJ< )方法蝌”A.快速推序B.堆井序C.楮爾帶序 D.m井撲序.( )方法從從k槨序昨列中挑選?？?丹利此放入仁州莊序列的一端.A.IH井柞序B.插入槨件 C.快避排步 P.以界拉中.卜例序列中.( )足拘仃笫一售快速撲用的鉆農(nóng). 、A.[dn?aiteh.de.bb]ff[hn>gcIA.[dn?aiteh.de.bb]ff[hn>gcIC(?t-n?.rb.?'(l,hh1ft\!n.ha19.( )作中4泣出小班定的.A.fttflM H.“按插入20.( )可能是甲劭X?,.-A.完全一叉樹 B.滿XMB.cd.cb,hx.du]ff(hn>gc<hb]D.?*<.hb.<<1,rt/i]nvh.?c.h"|C.”整透桿D.起泡三、判斷題(正■的打精課的打“XL毋BH分.共10分)TOC\o"1-5"\h\z所調(diào)敷網(wǎng)的邃料站構(gòu)指的是數(shù)榭之時(shí)的也軟欠嘉- I >0(nlogn)<C(n). ( )iQp(q'指thiSrpy.廁*嚴(yán)*<j. ( >t有n個(gè)元素依次進(jìn)枝.劃出梗序列在OrD2機(jī).< >.在福環(huán)隊(duì)列中,from。,向隊(duì)頭兀*的前個(gè)位雷.re“r指向隊(duì)昆兀氏的伸司?則隊(duì)血的條II%fronsreftr. C ).使用一兀川&行此稱蹙城陣的元本.有時(shí)并不慌存禽史陶< >.二文材足值為21n村. < )&時(shí)任一酒叉啊.其分低敷R=2(nOI).式中.nO為蜂憫州點(diǎn)數(shù)?( )9時(shí)任寬個(gè)旭，從某凈點(diǎn)小發(fā)!￡，；次深度優(yōu)尢或！比優(yōu)比遍歷，可廿同圖的所。限點(diǎn)?( )10.&個(gè)仃向閽的拓?fù)湫蛄校?"艮加日在頂點(diǎn)b之四.■圖中心力條從「巾點(diǎn)”到M點(diǎn)h的克. ( > ?四、計(jì)算題(共19分).(8分)已知上18碼序列為(.Inn,leb.Mar,Apr.May.Jun.Jul.Aug.Sep.Oct,Sov,Dec).敢軻殳的地出土間為016.設(shè)收劑示數(shù)為H(x”[//2j.IC中，為大H碼中，個(gè)享用他字母表中的序。.采府線性報(bào)界1法》鋌堆址法處理沖突.試分別構(gòu)造敢例&,并求等播率情況卜育找成功的1F均為找K4..(4分)及有綱結(jié)點(diǎn).4權(quán)值*J{1.1,5.16.25.1.10J.1S出由這些”點(diǎn)后構(gòu)或的哈大世旭,力計(jì)算忖的帶權(quán)踣徑K/S..(4分)對數(shù)?C：I.5.3.6.8.11.J0,技此進(jìn)入的次序.U"慢平佇_.義利,.13分)計(jì)舞卜列枚式小的AJ丁字符地火牧由敗值(最小值為。).BAhcaabcaaab五、算法編寫想(共16分) '(9分)設(shè)A*IB分別為兩個(gè)偃力.H均由箭表觸F”&示(冷乂中無未僅為靜數(shù).掩值從小到