XXXX大學(xué)二。。四年碩士研究生入學(xué)考試試題考試科目：計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ) 考試科目代碼：［424］報(bào)考專(zhuān)業(yè):計(jì)算機(jī)科學(xué)與技術(shù)考生注意：答案務(wù)必寫(xiě)在答題紙上，并標(biāo)明題號(hào)。答在試題上無(wú)效。題號(hào)一二三四五六七八九十十一總分分?jǐn)?shù)109724252871030150分答題注意事項(xiàng)：數(shù)據(jù)結(jié)構(gòu)的答案必須寫(xiě)在計(jì)算機(jī)原理答案的前面。I.數(shù)據(jù)結(jié)構(gòu)（含高級(jí)語(yǔ)言）部分（75分）一、 填空（每空1分，共10分）用下標(biāo)從0開(kāi)始的n個(gè)元素的數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量m加1后，m仍在數(shù)組有效下標(biāo)范圍內(nèi)，^則m=①。若二元樹(shù)的一個(gè)葉結(jié)點(diǎn)是某子樹(shù)的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必然是該子樹(shù)的后根遍歷序列中的②個(gè)結(jié)點(diǎn)。對(duì)具有17個(gè)元素有序表A［1...17］作折半查找，在查找其元素值等于A［8］的元素時(shí)，被比較的元素下標(biāo)依次是③。快速分類(lèi)的最大和最小涕歸深度分別是④和⑤。外部分類(lèi)過(guò)程主要分為兩個(gè)階段：⑥階段和⑦階段。已知下面這些字母在某字典中A出現(xiàn)的概率為0.08,B出現(xiàn)的概率為0.04,I出現(xiàn)的概率為0.15,C出現(xiàn)的概率是0.20，E出現(xiàn)的概率是0.12,F出現(xiàn)的概率是0.16，R出現(xiàn)的概率是0.15,K出現(xiàn)的概率是0.10，若采用霍夫曼（Huffman）編碼，則E的編碼是⑧（要求概率小的作為左分支）。索引文件在存儲(chǔ)器上分兩個(gè)區(qū)，分別為⑨和⑩。二、 單項(xiàng)選擇（每題1分，共9分）已知一算術(shù)表達(dá)式的中綴形式為a-（b+c/d）*e,其后綴形式為（①）。-a+b*c/dB.-a+b*cd/eC.-+*abc/deD.abcd/+e*-在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將數(shù)據(jù)依次寫(xiě)入緩沖區(qū)，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)是一個(gè)（②）結(jié)構(gòu)A.棧B.隊(duì)列C.線(xiàn)性表D.以上都不是設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過(guò)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少應(yīng)該是（③）。6B.4C.3D.2在下列敘述中，不正確的是（④）。關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成。 帶.市某些關(guān)鍵活動(dòng)若提前完成，則整個(gè)工程提前完成。 第2貝所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程將提前完成。 共5頁(yè)5.若需在O（nlogn）時(shí)間內(nèi)完成對(duì)數(shù)組的分類(lèi)，且要求分類(lèi)是穩(wěn)定的，則可選擇的分類(lèi)方法是:5.（⑤）快速分類(lèi)B.堆分類(lèi)C.歸并分類(lèi)D.插入分類(lèi)就分類(lèi)算法所用的輔助空間而言，堆分類(lèi)，快速分類(lèi)和歸并分類(lèi)的關(guān)系是（⑥）。A.堆分類(lèi)〈快速分類(lèi)〈歸并分類(lèi) B.堆分類(lèi)〈歸并分類(lèi)〈快速分類(lèi)C.堆分類(lèi)〉歸并分類(lèi)〉快速分類(lèi) D.堆分類(lèi)〉快速分類(lèi)〉歸并分類(lèi)將兩個(gè)具有n個(gè)整數(shù)的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（⑦）A.nB.2n-1C.2nD.n-1快速分類(lèi)在（⑧）的情況下不利于發(fā)揮其長(zhǎng)處。A.待分類(lèi)的數(shù)據(jù)量太大 B.待分類(lèi)的數(shù)據(jù)相同值過(guò)多C.待分類(lèi)的數(shù)據(jù)已基本有序 D.待分類(lèi)的數(shù)據(jù)值差過(guò)大倒排文件的主要優(yōu)點(diǎn)為（⑨）。A.便于進(jìn)行文件的插入和刪除操作 B.便于節(jié)省空間C.便于進(jìn)行文件合并操作 D.能大大提高基于非關(guān)鍵字的檢索速度三、判斷下列敘述是否正確，若正確，請(qǐng)畫(huà)“"'；否則，畫(huà)“X”（每題1分，共7分）就平均查找長(zhǎng)度而言，分塊查找最小，折半查找次之，順序查找最大。（①）外部分類(lèi)的K路平衡歸并，采用選擇樹(shù)法時(shí)，歸并效率與K有關(guān)。（②）對(duì)于n個(gè)記錄的集合進(jìn)行歸并分類(lèi)，最壞情況下時(shí)間復(fù)雜性為O（n2）。（③）倒排文件與多重表文件的次關(guān)鍵字索引結(jié)構(gòu)不同。（④）樹(shù)的父鏈表示法其實(shí)就是用數(shù)組表示樹(shù)的存儲(chǔ)結(jié)構(gòu)。（⑤）在n個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)＞n-1，則該圖必是連通圖。（⑥）若一個(gè)有向圖的鄰接矩陣中對(duì)角線(xiàn)以下元素均為0,則該圖的拓?fù)溆行蛐蛄幸欢ù嬖凇＃á撸┧摹?簡(jiǎn)答（每題8分，共24分）已知散列函數(shù)hash（k）=k%11，把一個(gè)整數(shù)值轉(zhuǎn)換成散列表的下標(biāo)，使用線(xiàn)性探測(cè)再散列法與鏈地址法構(gòu)造散列表。分別畫(huà)出所構(gòu)造的兩種散列表并把數(shù)據(jù)1，13,12,34,38,33,27，22依次插入到散列表中。簡(jiǎn)述堆的定義及堆分類(lèi)算法的思想。 _已知某數(shù)列輸入順序?yàn)?0,5,7,14,3,1,18,12,15,16，按輸入順序畫(huà)出其二元查找樹(shù)并畫(huà)出刪除結(jié)點(diǎn)14后的二元查找樹(shù)。五、 算法設(shè)計(jì)（共25分）試寫(xiě)一個(gè)算法建立有向圖的鄰接表，并保存每個(gè)結(jié)點(diǎn)的入度和出度。（8分）試寫(xiě)一個(gè)算法，在中根線(xiàn)索二元樹(shù)中求任意結(jié)點(diǎn)P的中根順序的前導(dǎo)結(jié)點(diǎn)SP。（8分）設(shè)有一個(gè)雙向鏈表，每個(gè)結(jié)點(diǎn)中除有prior（指向其前導(dǎo)結(jié)點(diǎn)）、data（數(shù)據(jù)域）和next（指向其后繼結(jié)點(diǎn)）三個(gè)域外，還有一個(gè)訪(fǎng)問(wèn)頻度域freq，在鏈表被起用之前，其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode（L,x）運(yùn)算時(shí)，令元素值為x的結(jié)點(diǎn)中freq域的值加1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪(fǎng)問(wèn)頻度的遞減序排列，以便使頻繁訪(fǎng)問(wèn)的結(jié)點(diǎn)總是靠近表頭。試寫(xiě)一符合上述要求的LocateNode運(yùn)算的算法。（9分）第3頁(yè)共5頁(yè)II.計(jì)算機(jī)組成原理部分（共75分）六、 填空（28分，每空1分）Cache的命中率是指A，命中率與B有關(guān)。為了協(xié)調(diào)CPU和DMA訪(fǎng)問(wèn)主存的沖突，DMA與主存交換數(shù)據(jù)時(shí)可采用三種方法，分別是A、B和C。某計(jì)算機(jī)采用微程序控制，微指令字中操作控制字段共12位，若采用直接控制，則此時(shí)一條微指令最多可同時(shí)啟動(dòng)A 個(gè)微操作。若采用字段直接編碼控制，并要求一條微指令需同時(shí)啟動(dòng)3個(gè)微操作，則微指令孚中的操作控制字段應(yīng)分B段。若每個(gè)字段的微命令數(shù)相同，這樣的微指令格式最多可包含C個(gè)微操作命令。利用訪(fǎng)存指令與設(shè)備交換信息，這在1/O編址方式中稱(chēng)為A。每個(gè)總線(xiàn)部件一般都配有土電路，以避免總線(xiàn)訪(fǎng)問(wèn)沖突，當(dāng)某個(gè)部件不占用總線(xiàn)時(shí)，由該電路禁止向總線(xiàn)輸出信息。1/O與主機(jī)交換信息的控制方式中，A方式CPU和設(shè)備是串行工作的，而B(niǎo)和C方式CPU和設(shè)備是并行工作的，前者傳送和主程序是并行進(jìn)行的，后者傳送和主程序是串行進(jìn)行的。如果CPU處于開(kāi)中斷狀態(tài)，一旦接受了中斷請(qǐng)求，CPU就會(huì)自動(dòng)A ，防止再次接受中斷。同時(shí)為了返回程序斷點(diǎn)，CPU必須將B內(nèi)容存至C 中。為了在中斷結(jié)束后返回主程序，并且允許接受新的中斷，必須D和E。依次從控制器、運(yùn)算器、存儲(chǔ)器和1/O系統(tǒng)四個(gè)方面，可采用A、B、C和D措施來(lái)提高計(jì)算機(jī)的整機(jī)速度。32位字長(zhǎng)的浮點(diǎn)數(shù)，其中階碼8位（含1位階符），數(shù)符1位，尾數(shù)23位，其對(duì)應(yīng)的最大負(fù)數(shù)為A，最小的絕對(duì)值為B，若機(jī)器數(shù)采用補(bǔ)碼規(guī)格化表示，則對(duì)應(yīng)的最大負(fù)數(shù)為C。（均用十進(jìn)制表示）設(shè)指令字長(zhǎng)等于存儲(chǔ)字長(zhǎng)，均為16位，若指令系統(tǒng)共有120種操作，操作碼位數(shù)固定，且具有直接、間接、變址、基址、相對(duì)、立即等尋址方式，則直接尋址的最大范圍是A，一次間址的范圍是B，立即數(shù)（補(bǔ)碼）的范圍是C。七、 選擇題（7分，每題1分）采用DMA方式傳送數(shù)據(jù)時(shí)，每傳送一個(gè)數(shù)據(jù)要占用①的時(shí)間。一個(gè)存取周期；一個(gè)指令周期；一個(gè)機(jī)器周期；一個(gè)中斷周期。在程序的執(zhí)行過(guò)程中，Cach。與主存的地址映射是由②。A.操作系統(tǒng)來(lái)管理的；B.程序員調(diào)度的；C.由操作系統(tǒng)和程序員共同協(xié)調(diào)完成的；D.由硬件自動(dòng)完成的。存取周期是指③。A.存儲(chǔ)器的寫(xiě)入時(shí)間和讀出時(shí)間的最小值；B.存儲(chǔ)器進(jìn)行連續(xù)寫(xiě)操作允許的最短間隔時(shí)間；C.存儲(chǔ)器進(jìn)行連續(xù)讀或?qū)懖僮魉试S的最短間隔時(shí)間；D.以上說(shuō)法都不對(duì)。下列敘述中④是正確的。程序中斷方式和DMA方式中實(shí)現(xiàn)數(shù)據(jù)傳送都需中斷請(qǐng)求；程序中斷方式中有中斷請(qǐng)求，DMA方式中沒(méi)有中斷請(qǐng)求；程度中斷方式和DMA方式中都有中斷請(qǐng)求，但目的不同；DMA要等指令周期結(jié)束時(shí)才可進(jìn)行周期竊取。下列敘述中⑤是正確的。A.虛擬存儲(chǔ)器實(shí)際上就是輔存；B.一條指令中可以包含多個(gè)操作碼；I/O接口是負(fù)責(zé)主存與外設(shè)交換信息的部件；由于定點(diǎn)乘法運(yùn)算時(shí)不會(huì)出現(xiàn)溢出，所以浮點(diǎn)乘法運(yùn)算時(shí)也不會(huì)出現(xiàn)溢出。某機(jī)指令系統(tǒng)共有101種操作，采用微程序控制方式時(shí)，控制存儲(chǔ)器中相應(yīng)有⑥個(gè)程序。TOC\o"1-5"\h\z101；102；103；104。采用變址尋址可擴(kuò)大尋址范圍，且⑦。A?變址寄存器內(nèi)容由用戶(hù)確定，且在程度執(zhí)行過(guò)程中不可變；B.變址寄存器內(nèi)容由操作系統(tǒng)確定，且在程度執(zhí)行過(guò)程中不可變；C.變址寄存器內(nèi)容由用戶(hù)確定，且在程序執(zhí)行過(guò)程中可變；D.變址寄存器內(nèi)容由操作系統(tǒng)確定，且在程序執(zhí)行過(guò)程中可變。八、簡(jiǎn)答與計(jì)算（10分，每題5分）總線(xiàn)管理包括哪些內(nèi)容？簡(jiǎn)要說(shuō)明各種管理措施。設(shè)機(jī)器數(shù)字長(zhǎng)為8位（含1位符號(hào)位）。設(shè)A=-11/32,B=95/128，列出豎式計(jì)算［A-B］補(bǔ)。七、綜合題（30分，共2題，第1題18分，第2題12分）假設(shè)X，Y，Z寄存器均為16位（最高位為第0位），在乘法指令開(kāi)始前，被乘數(shù)已存于X中，并用Y//Z存放乘積。要求：⑴畫(huà)出實(shí)現(xiàn)補(bǔ)碼Booth算法的運(yùn)算器框圖。（4分）⑵假設(shè)CU為組合邏輯控制，且采用中央控制和局部控制相結(jié)合的辦法，寫(xiě)出完成MULa指令（a為主存地址）的全部微操作及節(jié)拍安排（包括取指階段）。（10分）⑶指出哪些節(jié)拍屬于中央控制節(jié)拍，哪些節(jié)拍屬于局部控制節(jié)拍，局部控制最多需幾拍？（4分） 設(shè)CPU共有20根地址線(xiàn)，8根數(shù)據(jù)線(xiàn)，并用啊作訪(fǎng)存控制信號(hào)（低電平訪(fǎng)存），用g作讀寫(xiě)控制信號(hào)（高電平為讀，低電平為寫(xiě)），存儲(chǔ)器按奇偶分體，按字節(jié)方式訪(fǎng)問(wèn)。現(xiàn)有下列芯片：

（I） 74138（II） 門(mén)電路自定（III） ROM芯片①64KX8位；②32KX8位；③32KX16位。（W）RAM芯片①64KX8位；②32KX8位；③32KX16位。試問(wèn)：（DCPU按字節(jié)訪(fǎng)問(wèn)的地址范圍是多少？（2分）⑵指定最大64KB為系統(tǒng)程序區(qū)，與其相鄰的128KB為用戶(hù)程序區(qū)，選擇存儲(chǔ)芯片的類(lèi)型和數(shù)量（按奇偶分體）。（2分）⑶根據(jù)所選芯片，用二進(jìn)制寫(xiě)出每片存儲(chǔ)芯片所占地址空間。（2分）⑷按⑵中要求，畫(huà)出CPU和存儲(chǔ)器芯片的連接圖。（6分）■-I1SS■-I1SSjj根數(shù)據(jù)線(xiàn)，而允許寫(xiě)，ROM、RAM信號(hào)定義：i根地址線(xiàn)，而允許輸出^片選，?「允許編程。XXXX大學(xué)第1頁(yè)二。。五年碩士研究生入學(xué)考試試題共5頁(yè)考試科目：計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ) 考試科目代碼：［424］報(bào)考專(zhuān)業(yè):計(jì)算機(jī)科學(xué)與技術(shù)考生注意：答案務(wù)必寫(xiě)在答題紙上，并標(biāo)明題號(hào)。答在試題上無(wú)效。題號(hào)一二三四五六七八九十總分分?jǐn)?shù)1088222730520812150分答題注意事項(xiàng)：數(shù)據(jù)結(jié)構(gòu)的答案必須寫(xiě)在計(jì)算機(jī)原理答案的前面。I.數(shù)據(jù)結(jié)構(gòu)（含高級(jí)語(yǔ)言）部分（75分）一、 填空題（每空1分，共10分）設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為100n2和2n,要使前者快于后者，nTOC\o"1-5"\h\z至少為① 。在AOE（ActivityOnEdge）網(wǎng)中，從原點(diǎn)到匯點(diǎn)路徑上各個(gè)活動(dòng)的時(shí)間總和最長(zhǎng)的路徑稱(chēng)為② 。在等概率情況下，對(duì)具有n個(gè)元素的順序表進(jìn)行順序查找，查找成功（即表中有關(guān)鍵字等于給定值K的記錄）的平均查找長(zhǎng)度為 ③ ：查找不成功（即表中無(wú)關(guān)鍵字等于給定值K的記錄）的平均查找長(zhǎng)度為④ 。高度為h的堆中，最多有⑤個(gè)元素：最少有⑥個(gè)元素。求具有最小帶權(quán)外路徑長(zhǎng)度的擴(kuò)充二元樹(shù)的算法稱(chēng)為⑦算法。每次使用兩個(gè)有序表合并成一個(gè)有序表，這種排序方法叫彳 —排序。若一個(gè)具有n個(gè)頂點(diǎn)，e條邊的無(wú)向圖是一個(gè)森林，則該森林中比有⑨棵樹(shù)。設(shè)森林F對(duì)應(yīng)的二元樹(shù)B，它有m個(gè)結(jié)點(diǎn)，B的根為P，P的右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)為n，則森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是⑩ 。二、 單項(xiàng)選擇（每題1分，共8分）將長(zhǎng)度為n的單向鏈表鏈接在長(zhǎng)度為m的單向鏈表之后的算法的時(shí)間復(fù)雜性為（①）。A.0（1）B.O（n）C.O（m）D.O（m+n）對(duì)于一個(gè)線(xiàn)性表既要求能夠進(jìn)行較快速的插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能反映數(shù)據(jù)之間的邏輯關(guān)系，則應(yīng)該用（②）。A.順序存儲(chǔ)方式B.鏈?zhǔn)酱鎯?chǔ)方式C.散列存儲(chǔ)方式 D.以上均可以下述編碼哪一組不是前綴碼（③）。A.{00,01,10,11}B.{0,1,00,11}C.{0,10,110,111}D.{000,001,010,101}當(dāng)n足夠大時(shí)，下述函數(shù)中漸近時(shí)間最小的是（④）。A.T（n）=nlogn-1000lognB.T（n）=nlog3-1000lognC.T（n）=n2-1000logn D.T（n）=2nlogn-1000gn設(shè)有一個(gè)n行n列的對(duì)稱(chēng)矩陣A，將其下三角部分按行存放在一個(gè)一維數(shù)組B中，A[0][0]存放在B[0]中，那么第i行對(duì)角元素A[i][i]存放于B中（⑤）處。（i+3）*i/2B.（i+1）*i/2C.（2n-i+1）*i/2D.（2n-i-1）*i/2已知一個(gè)線(xiàn)性表（1,13,12,34,38,33,27,22）,假定采用h（k）=k%11計(jì)算散列抵制進(jìn)行散列存儲(chǔ)，若用鏈地址法處理沖突，則查找成功的平均查找長(zhǎng)度為（⑥）。A.1B.9/8C.13/11D.13/8設(shè)有向圖G是有10個(gè)頂點(diǎn)的強(qiáng)連通圖，則G至少有（⑦）條邊。A.45B.90C.10D.9倒排文件包含有若干個(gè)倒排表，倒排表的內(nèi)容是（⑧）°A.一個(gè)關(guān)鍵字值和該關(guān)鍵字的記錄地址 B.一個(gè)屬性值和該屬性的一個(gè)記錄地址C.一個(gè)屬性值和該屬性的全部記錄地址 D.多個(gè)關(guān)鍵字和它們相對(duì)應(yīng)的某個(gè)記錄的地址三、 判斷題（每空1分，共8分）有環(huán)路的有向圖不能進(jìn)行拓?fù)浞诸?lèi)。（①）對(duì)給定的關(guān)鍵字集合，以不同的次序插入初試為空的二元樹(shù)中，不可能得到同一棵二元排序樹(shù)。（②）在外部排序中，使用選擇樹(shù)法可以減少初試歸并段的數(shù)量。（③）若在磁盤(pán)上的順序文件中插入新的記錄，不一定要復(fù)制整個(gè)文件。（④）順序存儲(chǔ)方式只能用于存儲(chǔ)線(xiàn)性結(jié)構(gòu)。（⑤）折半查找與二元查找樹(shù)的時(shí)間性能在最壞的情況下是相同的。（⑥）稀疏矩陣壓縮存儲(chǔ)后，還可以進(jìn)行隨機(jī)存取。（⑦）對(duì)一個(gè)無(wú)向圖進(jìn)行先深搜索時(shí)，得到的先深序列是唯一的。（⑧）四、 簡(jiǎn)答題（共22分）畫(huà)出對(duì)長(zhǎng)度為18的有序順序表進(jìn)行折半查找的判定樹(shù)，并計(jì)算出在等概率時(shí)查找成功的平均查找長(zhǎng)度，以及查找失敗時(shí)所需的最多的關(guān)鍵字比較次數(shù)。（8分）假設(shè)以I和O分別表示入棧和出棧的操作，棧的初態(tài)和終態(tài)均為空。入棧和出棧的操作序列表示為僅由I和O組成的序列。（1） 下面所示的序列中哪些是合法的？（2分）A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2） 通過(guò)對(duì)（1）的分析，給出判斷一個(gè)給定序列是否合法的算法思想。（4分）已知某圖的鄰接表如圖4-1,以V1為起點(diǎn)分別給出先深搜索序列和先廣搜索序列，并簡(jiǎn)述先深搜索算法的基本思想。（8分）ffl4-1五、算法設(shè)計(jì)題（共27分）試設(shè)計(jì)一個(gè)HeapInsert（Rkey）算法，將關(guān)鍵字key插入到堆R中去，并保證插入后R仍是堆。并分析你的算法的時(shí)間復(fù)雜性。（15分）結(jié)點(diǎn)類(lèi)型和存儲(chǔ)結(jié)構(gòu)如下：typedefstruct{intkey;datatypedata;intcount;}node;nodeR[n];試設(shè)計(jì)一個(gè)排序算法，要求不移動(dòng)結(jié)點(diǎn)的存儲(chǔ)位置，只在結(jié)點(diǎn)的count字段記錄結(jié)點(diǎn)在排序中的序號(hào)，并將排序結(jié)果按升序輸出。（12分）II.計(jì)算機(jī)組成原理部分（共75分）六、填空題（30分，每空1分）總線(xiàn)上信息傳送的管理是通過(guò)A主要包括B、C 兩個(gè)方面，前者主要解決總線(xiàn)使用權(quán)問(wèn)題，后者主要解S的問(wèn)題，其中需增設(shè)一條“等待”（WAIT）響應(yīng)信號(hào)線(xiàn)的控制方式是E。CPU從主存中取出一條指令并執(zhí)行該指令的時(shí)間叫做A ，它通常包含若干個(gè) B而后者又包含若干個(gè)C。主機(jī)與I/O交換信息時(shí)，通常可用A、B、C 、通道和I/O處理機(jī)等五種控制方式。某計(jì)算機(jī)字長(zhǎng)32位，存儲(chǔ)容量8MB，若按半字編址，它的尋址范圍是A，若按雙字編址，其尋址范圍是B。假設(shè)機(jī)器字長(zhǎng)為31位（不含符號(hào)位），若一次移位需10uS，一次加法需10uS，則原碼一位乘最多需要A時(shí)間，補(bǔ)碼Booth算法最多需要B時(shí)間。除了采用高速芯片外，存儲(chǔ)器還可以采用A提高速度，運(yùn)算器可采用衛(wèi)提高運(yùn)算速度，控制器可采用C提高處理機(jī)速度。設(shè)相對(duì)尋址的轉(zhuǎn)移指令占3個(gè)字節(jié)，第一字節(jié)為操作碼，第2字節(jié)是相對(duì)位移量（補(bǔ)碼表示）的低8位，第3字節(jié)是相對(duì)位移量（補(bǔ)碼表示）的高8位。每當(dāng)CPU從存儲(chǔ)器中取出一個(gè)字節(jié)時(shí)，即自動(dòng)完成（PC）+1-PC，若PC當(dāng)前值為2005H，要求轉(zhuǎn)移到200CH，依次寫(xiě)出該轉(zhuǎn)移指令第2、第3字節(jié)的機(jī)器代碼為A氏若PC當(dāng)前值為200AH，要求轉(zhuǎn)移到2003H，則依次寫(xiě)出該轉(zhuǎn)移指令的第2、第3字節(jié)的機(jī)器代碼為 BH。設(shè)浮點(diǎn)數(shù)階碼為8位（含1位階符），基值為2,用移碼表示，尾數(shù)為24位（含1位數(shù)符），用補(bǔ)碼規(guī)格化表示，則對(duì)應(yīng)其最大正數(shù)的機(jī)器數(shù)形式為A，真值為B（十進(jìn)制表示）；對(duì)應(yīng)其最大負(fù)數(shù)的機(jī)器數(shù)形式為C，真值為D （十進(jìn)制表示）。控制單元CU是提供完成機(jī)器全部指令操作的微操作命令序列部件。其形式方法有兩種，種是A設(shè)計(jì)方法，為B邏輯；另一種是C設(shè)計(jì)方法，為D邏輯。某機(jī)共有32個(gè)32位的通用寄存器，且能完成130種操作，假設(shè)指令字長(zhǎng)等于機(jī)器字長(zhǎng)。若采用通用寄存器作為變址寄存器，設(shè)計(jì)一種變址尋址的“寄存器一寄存器”型指令格式，則指令的形式地址為A位，操作數(shù)的尋址范圍是B。七、 選擇題（5分，每題1分）在補(bǔ)碼定點(diǎn)加法運(yùn)算中，若采用1位符號(hào)位，則當(dāng)時(shí)，表示結(jié)果溢出。A.符號(hào)位有進(jìn)位 B.符號(hào)位進(jìn)位和最高數(shù)位進(jìn)位異或結(jié)果為0C.符號(hào)位為1 D.符號(hào)位進(jìn)位和最高數(shù)位進(jìn)位異或結(jié)果為1指令系統(tǒng)中采用不同尋址方式的目的主要。A.可直接訪(fǎng)問(wèn)外存 B.提供擴(kuò)展操作碼并降低指令譯碼難度C.縮短指令長(zhǎng)度，擴(kuò)大尋址空間 D.實(shí)現(xiàn)存儲(chǔ)程序和程序控制CPU內(nèi)通用寄存器的位數(shù)取決于 。A.存儲(chǔ)器的容量 B.機(jī)器字長(zhǎng)C.指令的長(zhǎng)度 D.CPU的管腳數(shù)某計(jì)算機(jī)有四級(jí)中斷，優(yōu)先級(jí)從高到低為1一2—3—4,假定將優(yōu)先級(jí)順序修改，改后1級(jí)中斷的屏蔽字為1011，2級(jí)中斷的屏蔽字為1111，3級(jí)中斷的屏蔽字為0011，4級(jí)中斷的屏蔽字為0001，則修改后的優(yōu)先級(jí)順序從高到低。A.3一2一1一4 B.2一1一3一4C.1一3一4一2 D.4一3一2一1一個(gè)組相聯(lián)地址映像Cache由64個(gè)存儲(chǔ)塊構(gòu)成，每組包含4個(gè)存儲(chǔ)塊，主存包含4096個(gè)存儲(chǔ)塊，每塊由8字組成，每字為32位，存儲(chǔ)器按字節(jié)編址。試問(wèn)主存地址18AB9H映像到Cache的組的任一字塊中。A.第一組 B.第二組C.第三組 D.第四組八、 簡(jiǎn)答與計(jì)算（20分）假設(shè)計(jì)算機(jī)A和計(jì)算機(jī)B采用相同的操作系統(tǒng)，現(xiàn)用同一基準(zhǔn)程序P測(cè)試這兩臺(tái)機(jī)器的速度，如果測(cè)得A的速度為MIPSA，B的速度為MIPSB，且MIPSA>MIPSB，試問(wèn)是否可以認(rèn)為，在執(zhí)行程序P時(shí)，計(jì)算機(jī)A的速度比計(jì)算機(jī)B的速度快？為什么？（3分）DMA接口電路中需有幾個(gè)寄存器？若主存容量為1MX16位，外設(shè)的地址空間為256，傳送的最大批量為512字節(jié)，寫(xiě)出每個(gè)寄存器的名稱(chēng)、作用和位數(shù)。（4分）已知x=0.1010，y=0.1101，按機(jī)器運(yùn)算步驟計(jì)算x：y并還原成真值（機(jī)器數(shù)形式自定）。（5分）CPU進(jìn)入中斷響應(yīng)周期要完成什么操作？這些操作由誰(shuí)來(lái)完成？（4分）什么是雙重分組跳躍進(jìn)位鏈？設(shè)機(jī)器字長(zhǎng)為32位，最高位為第0位，采用雙重分組跳躍進(jìn)位鏈，要求大組內(nèi)按5、3、5、3分組，寫(xiě)出每個(gè)大組內(nèi)的全部進(jìn)位Ci。（4分）九（8分）設(shè)CPU共有16根地址線(xiàn)，8根數(shù)據(jù)線(xiàn)，并用網(wǎng)作訪(fǎng)存控制信號(hào)，用而為讀控制信號(hào)，露為寫(xiě)控制信號(hào)。要求最大8K地址空間為系統(tǒng)程序區(qū)，與其相鄰的16K地址空間為用戶(hù)程序區(qū)，最小4K地址空間為系統(tǒng)程序工作區(qū)。現(xiàn)有下列芯片：ROM芯片：①2KX8位②4KX8位③8KX8位RAM芯片：①4KX8位②8KX8位③16KX8位74138門(mén)電路自定ROM信號(hào)定義：施允許輸出，弟片選，壬允許編程。RAM信號(hào)定義：死允許輸出，眺片選，而允許寫(xiě)畫(huà)出CPU與存儲(chǔ)芯片的連接圖，要求：（1） 畫(huà)出每片存儲(chǔ)芯片的地址范圍（用二進(jìn)制表示）（2） 指出存儲(chǔ)芯片的類(lèi)型和數(shù)量（3） 詳細(xì)畫(huà)出存儲(chǔ)芯片的片選邏輯十、綜合題（12分）畫(huà)出執(zhí)行ADD@M（@為間接尋址特征）指令的信息流程圖（2分）假設(shè)CPU中有PC、IR、ID、MAR、MDR、ACC、ALU和CU，寫(xiě)出完成該指令所需的全部微操作命令及節(jié)拍安排。（5分）如果CU采用微程序設(shè)計(jì)，畫(huà)圖說(shuō)明CU中應(yīng)包含哪些硬件，并指出完成上述指令還需增加哪些微操作命令？（4分）XXXX大學(xué)第1頁(yè)二。。六年碩士研究生入學(xué)考試試題共4頁(yè)考試科目：計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ) 考試科目代碼：［424］報(bào)考專(zhuān)業(yè):計(jì)算機(jī)科學(xué)與技術(shù)考生注意：答案務(wù)必寫(xiě)在答題紙上，并標(biāo)明題號(hào)。答在試題上無(wú)效。題號(hào)一二三四五六七八九總分分?jǐn)?shù)9910202715301416150分答題注意事項(xiàng)：數(shù)據(jù)結(jié)構(gòu)的答案必須寫(xiě)在計(jì)算機(jī)原理答案的前面。I.數(shù)據(jù)結(jié)構(gòu)（含高級(jí)語(yǔ)言）部分（75分）、填空題（每空1分，共9分）由二元樹(shù)的前序和后序序列①唯一確定這棵二元樹(shù)。在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)結(jié)點(diǎn)的下標(biāo)為i（0〈iWn-1），則它的左兒子的下標(biāo)為T(mén)OC\o"1-5"\h\z② ，右兒子的下標(biāo)為③ 。以折半查找方法從長(zhǎng)度為10的有序表中杳找一個(gè)元素時(shí)，杳找成功的平均長(zhǎng)度為④。高度為K的完全二元樹(shù)中，結(jié)點(diǎn)數(shù)n和K之間的關(guān)系是 ⑤。同一棵二元查找樹(shù)中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的元素值，則應(yīng)把它插入到根結(jié)點(diǎn)的⑥上。舉出兩種磁帶文件的分類(lèi)方法： ⑦和?。按二元樹(shù)的定義，具有三個(gè)結(jié)點(diǎn)的二元樹(shù)共有⑨種形態(tài)。、單項(xiàng)選擇（每題1分，共9分）已知一個(gè)序列為｛21，39,35,12,17,43｝，則利用堆分類(lèi)方法建立的初試堆為（①）。A.39，21，35，12，17，43A.39，21，35，12，17，43C.43，39，35，21，17，1243，39，35，12，17，21D.43，35，39，17，21，12算法性能分析的兩個(gè)主要方面是（②）OA.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 B.可讀性和健壯性時(shí)間復(fù)雜性和空間復(fù)雜性 D.正確性和簡(jiǎn)單性已知一個(gè)棧的輸入序列順序?yàn)?，2，3,4，…，n，輸出序列為P1，P2,P3，…，Pn。若Pn=n,則Pi（1<i<n）為（③）。A.iB.n-i C.n-i-1 D.不確定在（④）算法中，第一趟排序后，最大的或最小的數(shù)一定在其最終位置上。A.歸并排序 B.插入排序 C.快速排序 D?冒泡排序從二元查找樹(shù)中查找一個(gè)元素時(shí)，其平均時(shí)間復(fù)雜性為（⑤）。A.O（n）B.0（1）C.O（logn） D.O（n2）設(shè)結(jié)點(diǎn)X和結(jié)點(diǎn)Y的二元樹(shù)T中的兩個(gè)結(jié)點(diǎn)，若在前序序列中X在Y之前，而在后序序列中X在Y之后，則X與Y的關(guān)系是（⑥）。A.X是Y的左兄弟B.X是Y的右兄弟C.Y是X的祖先D.Y是X的后代在一個(gè)長(zhǎng)度為n的線(xiàn)性表中的第i個(gè)元素（0〈iWn-1）之前插入一個(gè)新元素時(shí)，需向后移動(dòng)（⑦）個(gè)元素。A.n-1B.n—i+1C.n-i-1D.i對(duì)于一組權(quán)值都相等的16個(gè)字母，構(gòu)造相應(yīng)的哈夫曼樹(shù)，這棵哈夫曼樹(shù)是一棵（⑧）。A.完全二元樹(shù) B.一般二元樹(shù) C.滿(mǎn)二元樹(shù)D.以上都不正確若要盡可能快地完成對(duì)實(shí)型數(shù)組的排序，且要求排序是穩(wěn)定的，則應(yīng)選擇（⑨）。A.快速排序 B.堆排序C.歸并排序 D.基數(shù)排序三、 判斷題（每題1分，共10分）折半查找只適合用于有序表，包括有序的順序表和有序的鏈接。（①）拓?fù)浞诸?lèi)適合于無(wú)環(huán)路有向圖且拓?fù)湫蛄形ㄒ弧＃á冢┰趎個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1，則該圖必是連通圖。（③）散列法存儲(chǔ)的基本思想是由關(guān)鍵字的值確定關(guān)鍵字的存儲(chǔ)地址。（④）用鄰接矩陣存儲(chǔ)一個(gè)圖，所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。（⑤）在磁盤(pán)分類(lèi)中，對(duì)于能容納P個(gè)記錄的緩沖區(qū)，不能產(chǎn)生出長(zhǎng)度大于P的初始?xì)w并段。（⑥）倒排文件與多重鏈表文件相似，都是用來(lái)處理多關(guān)鍵字查找。（⑦）8.中序線(xiàn)索二元樹(shù)的優(yōu)點(diǎn)是便于在中序遍歷時(shí)查找任意結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。（⑧）外部排序過(guò)程主要分為兩個(gè)階段：生成初始?xì)w并段和對(duì)歸并段進(jìn)行逐趟歸并。（⑨）索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上。（⑩）四、 簡(jiǎn)答題（共20分）（10分）已知一個(gè)邊帶權(quán)無(wú)向圖的頂點(diǎn)集V和邊集E分別為：V={0，1，2，3，4，5，6，7}；E={（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20，（6，7）30}。邊集E中的一條邊表示成（x，y）z的形式，其中x，y代表邊的兩個(gè)頂點(diǎn)，z代表該邊的權(quán)值。要求（1）簡(jiǎn)述Kruskal算法求最小生成樹(shù)的基本思想；（2）按該算法寫(xiě)出構(gòu)造最小生成樹(shù)的每一步。（6分）簡(jiǎn)述用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列時(shí)隊(duì)列滿(mǎn)與隊(duì)列空的區(qū)別方法，并給出判斷隊(duì)列滿(mǎn)和隊(duì)列空的條件。（4分）試舉例說(shuō)明，如果允許帶權(quán)有向圖中某些邊的權(quán)為負(fù)實(shí)數(shù)，則Dijkstra算法不能正確地求出從源點(diǎn)到每個(gè)頂點(diǎn)的最短路徑。五、 算法設(shè)計(jì)題（共27分）（13分）已知A、B、C是三個(gè)線(xiàn)性表且其元素按遞增順序排列，每個(gè)表中元素均無(wú)重復(fù)。在表A刪去既在表B中出現(xiàn)又在表C中出現(xiàn)的元素。試設(shè)計(jì)實(shí)現(xiàn)上述刪除操作的算法Delete，并分析其時(shí)間復(fù)雜性。（14分）設(shè)圖中各邊的權(quán)值都相等，以鄰接表為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)求任意兩個(gè)不同頂點(diǎn)之間最短距離的算法ShortPath（可以直接使用棧或隊(duì)列的存儲(chǔ)結(jié)構(gòu)和操作）。計(jì)算機(jī)組成原理部分（共75分）六、 填空（15分，每空1分）當(dāng)機(jī)器零用全0表示時(shí)，其階碼為A碼。設(shè)CPU的主頻為16MHz，若每個(gè)機(jī)器周期包含4個(gè)時(shí)鐘周期，該機(jī)的平均指令執(zhí)行速度為0.8MIPS，則該機(jī)的時(shí)鐘周期為AM，平均指令周期為BM，每個(gè)指令周期含C個(gè)機(jī)器周期。一個(gè)四路組相聯(lián)的Cache容量為8KB，主存容量為4MB，每字塊有16個(gè)字，每個(gè)字32位，則主存地址中的主存子快標(biāo)記為A位，組地址為B位，字塊內(nèi)地址為C位。CPU響應(yīng)中斷后可通過(guò)A或B 轉(zhuǎn)至中斷服務(wù)程序的入口地址，前者需配有C，后者需配有D。某計(jì)算機(jī)采用微程序控制，微指令字中操作控制字段共20位，若采用直接控制，則可以定義里種微操作，此時(shí)一條微指令最多可同時(shí)啟動(dòng)業(yè)個(gè)微操作。若采用編碼控制，并要求一條微指令需同時(shí)啟動(dòng)4個(gè)微操作，則微指令字中的操作控制字段應(yīng)分C 段，若每個(gè)字段的微命令數(shù)相同，這樣的微指令格式最多可包含D個(gè)微操作命令。七、 簡(jiǎn)答與計(jì)算（30分）說(shuō)明總線(xiàn)通信中半同步通信的特點(diǎn)，若想提高總線(xiàn)帶寬，可采取什么措施？（5分）試從五個(gè)方面比較程序中斷方式和DMA方式。（5分）假設(shè)階碼取3位，尾數(shù)取6位（均不包括符號(hào)位），按浮點(diǎn)補(bǔ)碼運(yùn)算步驟計(jì)算^乂圳陽(yáng)皿晶）。如何判斷其結(jié)果是否溢出。（6分）今有五級(jí)流水線(xiàn)，分別完成取指（IF），譯碼并取數(shù)（ID），執(zhí)行（EX），訪(fǎng)存（MEM），寫(xiě)吉果（WR）五個(gè)階段。假設(shè)完成各個(gè)階段操作的時(shí)間依次位90nS，60nS，70nS，100nS，50ns。試問(wèn)流水線(xiàn)的時(shí)鐘周期應(yīng)取何值？若第一和第二條指令發(fā)生數(shù)據(jù)相關(guān)，試問(wèn)第二條指令需推遲多少時(shí)間才能不發(fā)生錯(cuò)誤？若相鄰兩指令發(fā)生數(shù)據(jù)相關(guān)，而不推遲第二條指令的執(zhí)行，可采取什么措施？（3分）設(shè)某機(jī)有四個(gè)中斷源，優(yōu)先順序按1一2—3—4降序排列，若1、2、3、4中斷源的服務(wù)程序中對(duì)應(yīng)的屏蔽字分別為1110、0100、0110、1111。試寫(xiě)出這四個(gè)中斷處理次序（按降序排列）。若四個(gè)中斷源同時(shí)有中斷請(qǐng)求，畫(huà)出CPU執(zhí)行程序的軌跡。（5分）試比較補(bǔ)碼除法和原碼除法。設(shè)寄存器為16位（含1位符號(hào)位），試問(wèn)兩種除法分別作多少次加法和多少次移位？（6分）八（14分）設(shè)CPU有16根地址線(xiàn)，8根數(shù)據(jù)線(xiàn)，并用哽作訪(fǎng)存控制信號(hào)，梅作訪(fǎng)問(wèn)I/O端口的控制信號(hào)，而為讀命令，甌為寫(xiě)命令，I/O編址采用單獨(dú)編址，現(xiàn)有下列芯片及各種門(mén)電路（自定】PGMGinG2NDE贛DCBAPGMGinG2NDE贛DCBAA2AiAo4線(xiàn)一6線(xiàn)譯碼器接口芯片DE存儲(chǔ)器芯片畫(huà)出CPU和存儲(chǔ)芯片及CPU的I/O接口芯片的連接圖，要求：主存除最大地址空間存放系統(tǒng)BIOS程序(約4KB)夕卜，其余地址空間均為用戶(hù)所用。接口芯片的地址范圍為80H—87H。指出選用的芯片類(lèi)型、數(shù)量及地址范圍。詳細(xì)畫(huà)出存儲(chǔ)器芯片和接口芯片的片選邏輯。九(16分)某模型機(jī)共有64種操作，操作碼位數(shù)固定，且具有以下特點(diǎn)：采用一地址或二地址格式；有寄存器尋址，基址尋址(通用寄存器作基址寄存器)和相對(duì)尋址(位移量為一128?+128)；有16個(gè)通用寄存器，算術(shù)運(yùn)算和邏輯運(yùn)算的操作數(shù)均在寄存器中，結(jié)果也在寄存器中；取數(shù)/存數(shù)指令在通用寄存器和存儲(chǔ)器之間傳送數(shù)據(jù)；CPU的數(shù)據(jù)線(xiàn)為16位，存儲(chǔ)器按字節(jié)編址；有效地址的形成可通過(guò)地址加法器及相應(yīng)的硬件(自定)完成。要求：設(shè)計(jì)算術(shù)邏輯指令、取數(shù)/存數(shù)指令和相對(duì)轉(zhuǎn)移指令的格式，并簡(jiǎn)單說(shuō)明。以基址尋址的取數(shù)指令為例，按序畫(huà)出完成該指令的信息流程(如一)以基址尋址的取數(shù)指令為例，寫(xiě)出完成該指令由組合邏輯控制單元所發(fā)出的微操作命令及節(jié)拍安排。如果采用微程序控制，需增加哪些微操作命令？XXXX大學(xué)第1頁(yè)二。。七年碩士研究生入學(xué)考試試題 共5頁(yè)考試科目：計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)報(bào)考專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)考試科目代碼：［424］考生注意：答案務(wù)必寫(xiě)在答題紙上，并標(biāo)明題號(hào)。答在試題上無(wú)效。題號(hào)一二三四五六七八九十總分分?jǐn)?shù)108101433231881214答題注意事項(xiàng)：數(shù)據(jù)結(jié)構(gòu)的答案必須寫(xiě)在計(jì)算機(jī)原理答案的前面。I.數(shù)據(jù)結(jié)構(gòu)（含高級(jí)語(yǔ)言）部分（75分）一、 填空題（每空1分，共10分）設(shè)圖G有n個(gè)頂點(diǎn)e條邊，采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜性① 。TOC\o"1-5"\h\z線(xiàn)索二元樹(shù)的左線(xiàn)索指向②，右線(xiàn)索指向③ 。若分別以實(shí)數(shù)4,5,6,7,8作為葉結(jié)點(diǎn)的權(quán)值來(lái)構(gòu)造哈夫曼（Huffman）樹(shù)，則該哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是④ 。n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有⑤個(gè)非零元素。設(shè)只包含根結(jié)點(diǎn)的二元樹(shù)的高度為0,則高度為K的二元樹(shù)的最多結(jié)點(diǎn)數(shù)為⑥ ，最少結(jié)點(diǎn)數(shù)⑦ 。任意一個(gè)有n個(gè)結(jié)點(diǎn)的二元樹(shù)，已知它有m個(gè)葉結(jié)點(diǎn)，則度數(shù)為2的結(jié)點(diǎn)有⑧ 。對(duì)n個(gè)記錄的表進(jìn)行選擇排序，在最壞情況下所需要進(jìn)行的關(guān)鍵字的比較次數(shù)為⑨ 。在⑩情況下，等長(zhǎng)編碼是最優(yōu)前綴碼。二、 選擇題（每題1分，共8分）若結(jié)點(diǎn)的存儲(chǔ)地址是其關(guān)鍵字的某個(gè)函數(shù)，則稱(chēng)這種存儲(chǔ)結(jié)構(gòu)為① 。A.順序存儲(chǔ)結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu) D.散列存儲(chǔ)結(jié)構(gòu)對(duì)于一個(gè)索引順序文件，索引表中的每個(gè)索引項(xiàng)對(duì)應(yīng)主文件中的 ② 。A.一個(gè)記錄 B.多條記錄C.所有記錄 D.以上都不對(duì)將兩個(gè)各有n個(gè)元素的已排序表歸并成一個(gè)排好序的表，其最少的比較次數(shù)是③ 。A.n B.2n-1C.2n D.n-1假定有K個(gè)關(guān)鍵字且散列地址相同，若用線(xiàn)性探測(cè)法（步長(zhǎng)為1）把K個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行④次探測(cè)。A.K-1 B.KC.K+1 D.K（K+1）/2在關(guān)鍵字隨機(jī)分布的情況下，用二元查找樹(shù)的方法進(jìn)行查找，其平均杳找長(zhǎng)度與⑤量級(jí)相當(dāng)。A.順序查找 B.折半查找C.分塊查找 D.散列查找對(duì)于一個(gè)有向圖，若某頂點(diǎn)的入度為K1，出度為K2，則在該圖的逆鄰接表中，關(guān)于該頂點(diǎn)鏈表的結(jié)點(diǎn)個(gè)數(shù)為⑥ 。A.K1 B.K2C.K1-K2 D.K1+K2下列說(shuō)法正確的是⑦ 。A.最小生成樹(shù)也是哈夫曼（Haffman）樹(shù)B.最小生成樹(shù)唯一對(duì)于n個(gè)頂點(diǎn)的連通無(wú)向圖，Prim算法的時(shí)間復(fù)雜性為O（n2）Kruskal算法比Prim算法更適合邊稠密的圖一個(gè)有n個(gè)頂點(diǎn)的連通無(wú)向圖，它所包含的連通分量個(gè)數(shù)為⑧ 。A.0 B.1C.n D.n+1三、 判斷題（每題1分，共10分）順序存儲(chǔ)的線(xiàn)性表可以隨機(jī)存取。（①）單源最短路徑的Dijkstra算法中要求邊上的權(quán)值不能為負(fù)的原因是實(shí)際應(yīng)用無(wú)意義。（②）若無(wú)向圖G的頂點(diǎn)度數(shù)的最小值大于或等于2,則G必然存在環(huán)路。（③）在二元樹(shù)中，具有一個(gè)兒子的父結(jié)點(diǎn)，在中根遍歷序列中沒(méi)有后繼結(jié)點(diǎn)。（④）廣義表中原子的個(gè)數(shù)即為廣義表的長(zhǎng)度。（⑤）有環(huán)路的有向圖不存在拓?fù)湫蛄小＃á蓿┛焖倥判虻乃俣仍谒幸员容^為基礎(chǔ)的排序方法中是最快的，且所需附加空間最小。（⑦）對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，在最壞情況下所需要的時(shí)間是O（n2）。（⑧）外排序過(guò)程主要分為兩個(gè)階段：生成初始?xì)w并段和對(duì)歸并段進(jìn)行逐趟歸并。（⑨）一個(gè)連通的無(wú)向圖是雙連通的，當(dāng)且僅當(dāng)它沒(méi)有關(guān)節(jié)點(diǎn)。（⑩）四、 簡(jiǎn)答題（14分）（7分）舉例說(shuō)明4X3的稀疏矩陣的兩種存儲(chǔ)方法。（7分）一組關(guān)鍵字（46,79,56,38,40，84）所對(duì)應(yīng)的完全二元樹(shù)是否為堆，如果是堆，請(qǐng)給出堆排序的前兩步的圖示；如不是，則給出建立初始堆（大頂堆）及堆排序的前兩步的圖示。五、 算法設(shè)計(jì)題（33分）隊(duì)列和棧的基本操作可以直接使用。（11分）設(shè)二元樹(shù)的存儲(chǔ)結(jié)構(gòu)為左右鏈形式，設(shè)計(jì)按層次遍歷該二元樹(shù)的算法并輸出結(jié)點(diǎn)序列。（11分）對(duì)于給定的一個(gè)排好序的整數(shù)序列。設(shè)計(jì)一個(gè)算法構(gòu)造一棵二元樹(shù)，使得在該二元樹(shù)中，以任意結(jié)點(diǎn)為根的子樹(shù)的高度之差的絕對(duì)值不大于1。（11分）可以使用“破圈法”求解帶權(quán)連通無(wú)向圖的一棵最小生成樹(shù)。所謂“破圈法”就是任取一個(gè)圈并去掉圈上權(quán)最大的邊，反復(fù)執(zhí)行這一步驟，直到?jīng)]圈為止。請(qǐng)?jiān)O(shè)計(jì)該算法求解給定帶權(quán)連通無(wú)向圖的最小生成樹(shù)。（注：圖即為環(huán)路）。計(jì)算機(jī)組成原理部分（共75分）六、填空（23分，每空1分）某機(jī)有五級(jí)中斷，優(yōu)先級(jí)從高到低為1-2-3-4-5。若將優(yōu)先級(jí)順序修改，改后1級(jí)中斷的屏蔽字為11111，2級(jí)中斷的屏蔽字為01010,3級(jí)中斷的屏蔽字為01111，4級(jí)中斷的屏蔽字為00001，5級(jí)中斷的屏蔽字為01011，則修改后的處理優(yōu)先級(jí)順序從高到低為A。已知74181是4位的ALU芯片，其4位進(jìn)位是同時(shí)產(chǎn)生的，74182是先行進(jìn)位芯片，現(xiàn)用8片74181和2片74182可組成。在集中式總線(xiàn)仲裁中，A 方式響應(yīng)時(shí)間最快， B 方式對(duì)電路故障最敏感。有一主存-Cache層次的存儲(chǔ)器，其主存容量1MB，Cache容量16KB，每字塊有8個(gè)字，每字32位，采用直接地址映像方式，若主存地址為35301H，且CPU訪(fǎng)問(wèn)Cache命中，則在Cache的第A（十進(jìn)制表示）字塊中（Cache起始字塊為第0字塊）。對(duì)于某些指令（如乘法指令），控制器通常采虬^_控制方式來(lái)控制指令的執(zhí)行，但這種控制中的節(jié)拍寬度與B控制的節(jié)拍寬度是相等的，而且.這兩種控制是C。一個(gè)DMA接口可采用周期竊取方式把字符傳送到存儲(chǔ)器，它支持的最大批量為200個(gè)字節(jié)，若存取周期為0.2us，每處理一次中斷需4us，現(xiàn)有的字符設(shè)備的傳輸率為9600位/秒。假如字符之間的傳輸是無(wú)間隙的，試問(wèn)DMA方式每秒因數(shù)據(jù)傳輸占用處理器土?xí)r間，如果完全采用中斷方式，又需占處理器 時(shí)間。（忽略預(yù)處理所需的時(shí)間）。設(shè)相對(duì)尋址的轉(zhuǎn)移指令占2個(gè)字節(jié)，第一字節(jié)為操作碼，第二字節(jié)為位移量（用補(bǔ)碼表示），每當(dāng)CPU從存儲(chǔ)器取出一個(gè)字節(jié)時(shí)，即自動(dòng)完成（pc）+1-pc。設(shè)當(dāng)前指令地址為3008H，要求轉(zhuǎn)移到300FH，則該轉(zhuǎn)移指令第二字節(jié)的內(nèi)容應(yīng)為A 。若當(dāng)前指令地址300FH，要求轉(zhuǎn)移到3004H，則該轉(zhuǎn)移指令第二字節(jié)的內(nèi)容為B。二進(jìn)制數(shù)在計(jì)算機(jī)中常用的表示方法有原碼、補(bǔ)碼、反碼和移碼等多種。表示定點(diǎn)整數(shù)，若要求數(shù)值0在計(jì)算機(jī)中唯一表示為全“0”，應(yīng)采用；表示浮點(diǎn)數(shù)時(shí)，若要機(jī)器零（即尾數(shù)為零，且階碼最小的數(shù)）在計(jì)算機(jī)中表示為全“0”，則階碼應(yīng)采用^_。某計(jì)算機(jī)中，浮點(diǎn)數(shù)的階碼占8位（含1位階符），尾數(shù)占40位（含1位數(shù)符），都采用補(bǔ)碼，則該機(jī)器中所能表達(dá)的最大浮點(diǎn)數(shù)是 C。在浮點(diǎn)機(jī)中，設(shè)尾數(shù)采用雙符號(hào)位，當(dāng)補(bǔ)碼運(yùn)算結(jié)果的尾數(shù)部分不是A的形式應(yīng)進(jìn)行規(guī)格化處理，當(dāng)尾數(shù)符號(hào)位為B時(shí)，需要右規(guī)。除了采用高速芯片外，從計(jì)算機(jī)的各個(gè)子系統(tǒng)的角度分析，可采 一、— 、C、D、E、F等措施提高整機(jī)諫度。七、簡(jiǎn)答與計(jì)算（18分）（5分）為了減輕總線(xiàn)負(fù)載，總線(xiàn)上的部件應(yīng)具備什么特點(diǎn)？什么是總線(xiàn)通信控制？總線(xiàn)通信控制有幾種方式？2（7分）設(shè)計(jì)中斷系統(tǒng)需考慮哪些主要問(wèn)題？分別可用哪些技術(shù)解決?

（6分）已知二進(jìn)制數(shù)x=-0.1111,y=0.1101,用補(bǔ)碼一位乘Booth算法計(jì)算xXy。八、（8分）假設(shè)某機(jī)有8個(gè)16位的通用寄存器，主存容量為256K字，共能完成54種操作，且有4種尋址方式，試回答：⑴設(shè)計(jì)一個(gè)三地址格式的寄存器一存儲(chǔ)器型指令，可完成（Ri）OP（M）—Rj。⑵若采用直接尋址方式訪(fǎng)問(wèn)主存中的任一地址，上述三地址格式指令中的地址碼域應(yīng)分配多少位？指令字長(zhǎng)應(yīng)為幾位？⑶若采用基址尋址方式，上述指令格式應(yīng)如何修改？⑷若指令字長(zhǎng)等于存儲(chǔ)字長(zhǎng)，假設(shè)主存容量擴(kuò)充到4G字，在不改變硬件結(jié)構(gòu)的前提下，可采用什么尋址方式使指令能訪(fǎng)問(wèn)主存空間中的任一位置？九、（12分）設(shè)CPU有18根地址線(xiàn)和8根數(shù)據(jù)線(xiàn)，并用土次療作訪(fǎng)存控制信號(hào)，拆^作讀寫(xiě)命令，存儲(chǔ)器采用四體低位交叉結(jié)構(gòu)，畫(huà)出CPU和存儲(chǔ)芯片的連接圖。要求：⑴合理選用下列芯片，門(mén)電路自定。AjAoCE_RAMAjAoCE_RAM□QEVVEDjDo鑰KM位128KXEGiD CSaG明c--■,?.C,*—B*A%> T4138? ⑵寫(xiě)出每片存儲(chǔ)芯片的二進(jìn)制地址范圍。⑶詳細(xì)畫(huà)出存儲(chǔ)芯片的片選邏輯。⑷該存儲(chǔ)器在一個(gè)存取周期內(nèi)可向CPU提供多少位信息？十、（14分）已知帶返轉(zhuǎn)指令的含義如下圖所示：

主程序 子程序⑴寫(xiě)出機(jī)器在完成帶返轉(zhuǎn)指令時(shí)，組合邏輯控制取指階段和執(zhí)行階段所需的全部微操作命令及節(jié)拍安排。⑵若采用微程序控制，還需增加哪些微操作？⑶假設(shè)該機(jī)指令系統(tǒng)采用6位定長(zhǎng)操作碼格式，共對(duì)應(yīng)多少個(gè)微程序？⑷微指令的操作控制方式有幾種？各有何特點(diǎn)？⑸微指令的下地址字段位數(shù)如何確定？二。。八年碩士研究生入學(xué)考試試題考試科目：計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)報(bào)考專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)考試科目代碼：【424】 是否允許使用計(jì)算器：【否】考生注意：答案務(wù)必寫(xiě)在答題紙上，并標(biāo)明題號(hào)。答在試題上無(wú)效。題號(hào)一二三四五六七八九總分分?jǐn)?shù)209163015329910答題注意事項(xiàng)：數(shù)據(jù)結(jié)構(gòu)的答案必須寫(xiě)在計(jì)算機(jī)原理答案的前面。I.數(shù)據(jù)結(jié)構(gòu)（含高級(jí)語(yǔ)言）部分（75分）一、 填空（每題2分.共20分）已知一個(gè)線(xiàn)性表有n個(gè)元素，其中每個(gè)元素的數(shù)據(jù)占8個(gè)字節(jié)，假設(shè)一個(gè)指針的大小為4個(gè)字節(jié)，如果采用有30個(gè)元素的數(shù)組存儲(chǔ)，那么當(dāng)數(shù)組中有效元素個(gè)數(shù)滿(mǎn)足_^條件時(shí)，數(shù)組的存儲(chǔ)效率比不帶頭結(jié)點(diǎn)的單鏈表更高。給定14個(gè)字母，假設(shè)它們的權(quán)值都相等.采用huffman編碼，則每個(gè)字母的平均代碼長(zhǎng)TOC\o"1-5"\h\z度是⑵ 。按C語(yǔ)言的運(yùn)算符優(yōu)先級(jí)，中綴表達(dá)式“A&&B||!（E>F）”的等價(jià)后綴形式為_(kāi)^_。設(shè)按順時(shí)針?lè)较蛞苿?dòng)的循環(huán)隊(duì)列Q[N]的頭尾指針?lè)謩e為F、R，頭指針F總是指在隊(duì)列中的第一個(gè)元素的前一位置，尾指針R在最后一個(gè)元素的位置，則隊(duì)列中的元素個(gè)數(shù)為⑷ 。從空二叉樹(shù)開(kāi)始，嚴(yán)格按照BST（二又查找樹(shù)）的插入算法，逐個(gè)插入關(guān)鍵字｛18,73,10,5,68,99,27,41,32,25）構(gòu)造出一顆BST，對(duì)該BST按照先根遍歷得到的序列為⑸ 。將兩個(gè)長(zhǎng)度為m的有序序列歸并為一個(gè)有序序列，最少需要做—⑥—次關(guān)鍵字比較，最多需要做 ⑺次關(guān)鍵字比較。散列查找中， ⑻ 現(xiàn)象稱(chēng)為沖突， ⑼現(xiàn)象稱(chēng)為聚集。設(shè)可用的內(nèi)存單元可處理4個(gè)記錄，采用4路歸并的選擇樹(shù)法生成由小到大的初始?xì)w并段，對(duì)有12個(gè)記錄在案的文件，產(chǎn)生的第一個(gè)初的歸并段長(zhǎng)度為⑽個(gè)。在兩種求圖的最小生成樹(shù)的算法中，（11） 算法適合于邊稀疏的圖的最小生成樹(shù)。已知一個(gè)序列為｛21，39,35,12,17,43｝，則利用堆排序方法建立的初始堆為：（12）。二、 判斷（每題1分.共9分）倒排文件只能按關(guān)鍵字的順序存儲(chǔ)。（①）堆的存儲(chǔ)表示可能是鏈接式的，也可以是順序的。（②）在AOE網(wǎng)中，任何一個(gè)關(guān)鍵活動(dòng)的延遲，都會(huì)使整個(gè)工程延遲。（③）有環(huán)路的有向圖不能進(jìn)行拓?fù)渑判颉＃á埽?duì)無(wú)向圖進(jìn)行一次深度優(yōu)先搜索可以訪(fǎng)問(wèn)到圖中的所有頂點(diǎn)。（⑤）大根堆的最大元素應(yīng)該在堆頂，即根結(jié)點(diǎn)。（⑥）歸并排序的平均時(shí)間復(fù)雜度為O（nlogn），最壞為o（n2）。（⑦）棧總是在棧底刪除元素。（⑧）分塊查找只適合靜態(tài)查找，不適合動(dòng)態(tài)查找。（⑨）三、 問(wèn)答題（每題8分.共16分）許多文獻(xiàn)中認(rèn)為常用的排序算法是快速排序算法，而不是歸并排序，你是如何理解的？在包含n個(gè)關(guān)鍵字的線(xiàn)性表中進(jìn)行順序查找若查找第i個(gè)關(guān)鍵字的概率為七且分布如下:P『1/2,P2=1/4，…，Pn_i=1/2（n-D,Pn=1/2n；求：（1）查找成功的平均查找長(zhǎng)度。（2）查找失敗情況下的平均查找長(zhǎng)度。四、 算法設(shè)計(jì)題（每題15分.共30分）設(shè)二叉樹(shù)結(jié)點(diǎn)表示的數(shù)據(jù)元素類(lèi)型為Elementtype,二叉樹(shù)用左右鏈表示。一棵二叉樹(shù)的最大枝長(zhǎng)和最小枝長(zhǎng)分別如下定義：最大枝長(zhǎng)就是二叉樹(shù)的層數(shù);最小枝長(zhǎng)就是離根結(jié)點(diǎn)距離最近的葉結(jié)點(diǎn)到根路徑上的邊數(shù)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，同時(shí)求出一棵二叉樹(shù)的最大和最小枝長(zhǎng)。設(shè)計(jì)一查找無(wú)環(huán)路有向圖第對(duì)頂點(diǎn)間“最長(zhǎng)簡(jiǎn)單路徑“（所謂最長(zhǎng)簡(jiǎn)單路徑是指該簡(jiǎn)單路徑包含邊最多）的算法，即以一個(gè)無(wú)環(huán)路有向圖作為輸入，對(duì)于每個(gè)頂點(diǎn)如果它們之間存在簡(jiǎn)單路徑，則輸出其中最長(zhǎng)的，否則輸出為空。計(jì)算機(jī)組成原理部分（共75分）五、填空題（每空1分.共15分）總線(xiàn)控制主要解決⑴問(wèn)題。集中式仲裁有⑵ 、 ⑶ 、 ⑷三種。若數(shù)據(jù)在存儲(chǔ)器中采用以低字節(jié)地址的存放方式，則十六進(jìn)制數(shù)12,34,56,78H按字節(jié)地址由小到大依次為⑸。總線(xiàn) —技術(shù)是指不同的信號(hào)（如地址信號(hào)和數(shù)據(jù)信號(hào)）共用一組物理線(xiàn)路，分時(shí)使用，此時(shí)需要配置相應(yīng)的電路。一個(gè)四級(jí)流水的處理器，共有12條指令連續(xù)輸入此流水線(xiàn)，則在12個(gè)時(shí)鐘周期結(jié)束時(shí)執(zhí)行完⑺ 條指令。CPU在⑻ 時(shí)刻采樣中斷請(qǐng)求信號(hào)（在開(kāi)中斷情況下）。而在⑼ 時(shí)刻采樣DMA的總線(xiàn)請(qǐng)求信號(hào)。32位字長(zhǎng)的浮點(diǎn)數(shù)，其中階碼8位（含1位階符），基值為2,尾數(shù)為24位（含1位數(shù)符）。當(dāng)機(jī)器數(shù)采用原碼表示，則其對(duì)應(yīng)的最小正數(shù)是⑽ ，最小負(fù)數(shù)是（11） ;當(dāng)機(jī)器數(shù)采用補(bǔ)碼表示，尾數(shù)為規(guī)格化形式，則其對(duì)應(yīng)的最大正數(shù) ，最大負(fù)數(shù)是（13）。（均用十進(jìn)制表示）定點(diǎn)原碼除法和定點(diǎn)補(bǔ)碼除法均可采用（14）法，但補(bǔ)碼除法中（15）參與運(yùn)算。六、問(wèn)答題（每題8分.共32分）什么是DMA（特點(diǎn)），簡(jiǎn)述采用DMA方式實(shí)現(xiàn)主機(jī)與I/O交換信息的數(shù)據(jù)傳遞過(guò)程。下圖為某SRAM的寫(xiě)入時(shí)序圖，月方線(xiàn)為讀寫(xiě)信號(hào)線(xiàn)，8線(xiàn)為片選信號(hào)線(xiàn)，要求寫(xiě)入地址為2450H的存儲(chǔ)單元中，指出圖中的錯(cuò)誤，并把相應(yīng)的正確的時(shí)序圖畫(huà)出來(lái)。什么是單重分組和雙重分組跳躍進(jìn)位鏈？一個(gè)按3、5、3、5分組的雙重分組跳躍進(jìn)位鏈（最低為第0位）。試問(wèn)大組中產(chǎn)生的是哪幾位進(jìn)位？與按4444分組的雙重分組跳躍進(jìn)位鏈相比，試問(wèn)產(chǎn)生全部進(jìn)位的時(shí)間是否一致？為什么？若某機(jī)采用微程序控制方式，微指令字長(zhǎng)24位，共有微指令30個(gè)，一條微指令允許同時(shí)啟動(dòng)4個(gè)微操作命令，可判定的外部條件共3個(gè)，畫(huà)出微指令格式，并指出控制存儲(chǔ)器的容量為多少？七、設(shè)某計(jì)算機(jī)機(jī)器字長(zhǎng)為16位，共有16個(gè)通用寄存器，4種尋址方式（尋址模式只需用一個(gè)字段表示），采用擴(kuò)展操作碼技術(shù)，指令字長(zhǎng)可變，主存容量為1M*16位，存儲(chǔ)器按字編址。（1） 設(shè)計(jì)單字長(zhǎng)寄存器寄存器型指令格式，并指出這類(lèi)指令最多允許幾條。（2） 在（1）的基礎(chǔ)上，擴(kuò)展成單操作數(shù)的指令，設(shè)計(jì)指令格式，并指出這類(lèi)指令最多允許幾條。（3） 設(shè)計(jì)允許直接訪(fǎng)問(wèn)主存單元的“寄存器一存儲(chǔ)器”指令格式。（4） 若可指定任一通用寄存器作為變址寄存器，設(shè)計(jì)變址尋址的“寄存器一存儲(chǔ)器”型指令格式。八、設(shè)CPU有18根地址線(xiàn)和16根數(shù)據(jù)線(xiàn)，并用小師作訪(fǎng)存控制信號(hào)，商為讀命令，麗為寫(xiě)命令，已知：（1）下列芯片及各種電路（門(mén)電路自定）

16KX8位 16KxM位 7413 8位 32KXW位6JKX8位 16KX8位 16KxM位 7413 8位 32KXW位6JKX8位 "4KX8位12SKXS要求：（1） 指出選用的存儲(chǔ)器芯片類(lèi)型及數(shù)量；（2） 寫(xiě)出每片存儲(chǔ)芯片的二進(jìn)制地址范圍；（3） 畫(huà)出CPU與存儲(chǔ)器的連接圖。九、（1）什么是多級(jí)時(shí)序系統(tǒng)？（2） 假設(shè)CU為組合邏輯控制，且采用中央控制和局部控制相結(jié)合的辦法，寫(xiě)法指令MULa指令（a為主存地址）的全部微操作命令及節(jié)拍安排（包括取指階段器數(shù)字長(zhǎng)為N位，（不包括符號(hào)位），機(jī)器數(shù)形式自定。假設(shè)在乘法開(kāi)始前，被乘于X寄存器中，并用A//Q寄存器存放乘積。序區(qū)，出完成乘）。設(shè)機(jī)數(shù)已存在最多需要（3） 指出哪些節(jié)拍屬于中央控制節(jié)拍，哪些節(jié)拍屬于局部控制節(jié)拍，局部控制幾拍？序區(qū)，出完成乘）。設(shè)機(jī)數(shù)已存在最多需要XXXX大學(xué)二零一三年計(jì)算機(jī)專(zhuān)業(yè)課真題（回憶版）數(shù)據(jù)結(jié)構(gòu)部分:75分一、 選擇題一個(gè)6層的的完全二叉樹(shù)最少有幾個(gè)節(jié)點(diǎn)：n節(jié)點(diǎn)的森林有k個(gè)分支，問(wèn)有幾棵樹(shù)：m個(gè)初始?xì)w并段k路歸并共歸并多少次：在排序中哪種排序算法直到最后才能確定每個(gè)元素的最終位置：高度為h的二叉樹(shù)只有度為0或2的節(jié)點(diǎn)，這棵樹(shù)節(jié)點(diǎn)數(shù)為有n個(gè)節(jié)點(diǎn)的無(wú)向圖壓縮存儲(chǔ)最少需要的空間上述編碼中，哪一組不是前綴碼。（00,01,10,11）（0,1,00,11）（0,10,110,11）（1,01,000,001）k路歸并需要的歸并趟數(shù)logk（m）；log2（m）；log2（k）；logm（k）9n個(gè)頂點(diǎn)的小頂堆，下列位置可能是最大值位置是（）選項(xiàng)。A.n/2-1B.n/2C.n/2+2D.n-1二、 填空題在n元素的有序表，在第一個(gè)元素前面插入一個(gè)新元素的時(shí)間復(fù)雜度（）平均時(shí)間復(fù)雜度（）。給一個(gè)后續(xù)序列的算術(shù)表達(dá)式求值：（）給一個(gè)中序序列的算術(shù)表達(dá)式求后續(xù)序列（）有2n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)度為1的節(jié)點(diǎn)個(gè)數(shù)（），度為2的節(jié)點(diǎn)個(gè)數(shù)（）稀疏矩陣的存儲(chǔ)方法有（）和（）高為h的b樹(shù)，葉節(jié)點(diǎn)在第（）層，要插入一個(gè)元素需取出（）節(jié)點(diǎn)三、 簡(jiǎn)答題1，已知一個(gè)圖的先序和中序序列先序序列CADBEF，中序序列CDBAFE問(wèn)：1.畫(huà)出這個(gè)樹(shù)，簡(jiǎn)要說(shuō)一下如何根據(jù)中序和前序構(gòu)造二叉樹(shù)。3.畫(huà)出該樹(shù)的后序線(xiàn)索二叉樹(shù)2靠查floyd算法，以及離心度的概念四、 算法設(shè)計(jì)題要求：給出算法，用偽代碼實(shí)現(xiàn)；分析時(shí)間復(fù)雜度和空間復(fù)雜度。1已知一個(gè)有序序列和一個(gè)數(shù)。設(shè)計(jì)一個(gè)函數(shù)findsum，從有序序列中找出兩個(gè)數(shù)，是這兩個(gè)數(shù)的和等于已知的這個(gè)數(shù)。如果存在多對(duì)，給出一對(duì)即可。數(shù)組的數(shù)據(jù)大概是1,3,4,5,7,8,11，已知數(shù)字給的是11。然后求數(shù)組里兩個(gè)數(shù)相加和等于給的已知數(shù)字，比如4+7等于112.求以孩子兄弟鏈表表示的森林的葉子節(jié)點(diǎn)個(gè)數(shù)counterleaves王道論壇（）友情分享嚴(yán)禁任何人用于商業(yè)用途牟利計(jì)算機(jī)組成原理部分:75分一、 填空題（每空1分）1判優(yōu)控制中一一對(duì)電路故障最敏感，一一反應(yīng)最快。2FFH，當(dāng)為127時(shí)，是一一碼，負(fù)127時(shí)，一一碼，負(fù)0時(shí)，一一碼，負(fù)1時(shí)，一一碼。3流水線(xiàn)中影響因素有一一沖突，一一相關(guān)，一一相關(guān)4低位交叉存儲(chǔ)器， （大概是問(wèn)為什么會(huì)提高速度），其中低位——，高位——。5指令兩個(gè)字，第一個(gè)字為操作碼，每取出一個(gè)字PC內(nèi)容+1，現(xiàn)PC中內(nèi)容為2000H，想要轉(zhuǎn)移到2008H，問(wèn)第二個(gè)字是什么二、 簡(jiǎn)答題（每題六分）第一題求兩個(gè)浮點(diǎn)數(shù)相加減第二題寫(xiě)出直接映像，四路組關(guān)聯(lián)和全相聯(lián)映像的地址，數(shù)據(jù)大概是，4M主存，4Kcache，每字塊8個(gè)字，每字32位第三題8MHZ，速度0.8MIPS，每個(gè)機(jī)器周期有四個(gè)時(shí)鐘周期，求機(jī)器周期數(shù)；如果時(shí)鐘周期變?yōu)?.4，求速度。如果想要速度變?yōu)椋ǎ┣髸r(shí)鐘周期。第四題簡(jiǎn)述單重分組跳躍進(jìn)位鏈和雙重分組跳躍進(jìn)位鏈區(qū)別第五題為什么需要中斷判優(yōu)?中斷判優(yōu)有什么方法?如果要改變中斷優(yōu)先級(jí)有哪些技術(shù)？三、 綜合題第一題唐朔飛組成原理習(xí)題冊(cè)第七章第28題，228頁(yè)，只有2,3問(wèn)（8分）第二題cpu內(nèi)有mar,mdr,ir,pc沒(méi)有總線(xiàn)（忘了，好像是這意思），有取指，間址，執(zhí)行，中斷周期，要求寫(xiě)出取指周期和中斷周期組合邏輯設(shè)計(jì)和微程序設(shè)計(jì)的微指令和節(jié)拍第三題唐朔飛組成原理習(xí)題冊(cè)第四章的第40題，65頁(yè)（12分）XXXX大學(xué)二零一四年計(jì)算機(jī)專(zhuān)業(yè)課真題(回憶版)全套試題基本上都是由道友-----persevere童鞋回憶的，感謝為本套題做出貢獻(xiàn)的所有道友！數(shù)據(jù)結(jié)構(gòu)部分75分一、 選擇題(共10題，每題2分)有一個(gè)100*90整型數(shù)的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需字節(jié)數(shù)為()。A.60B.66C.180D.33(2)在度為m的哈夫曼樹(shù)中，葉結(jié)點(diǎn)的個(gè)數(shù)為n，則非葉結(jié)點(diǎn)的個(gè)數(shù)為()。A.n-1B.n/(m-1)C.(nT)/(mT)D.(n+1)*(m+1)-1長(zhǎng)度為12的有序