201X年哈工大計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)854考研真題

..精選實(shí)用文檔..精選2021年哈工大計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)854考研真題I．?dāng)?shù)據(jù)結(jié)構(gòu)選擇題設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是〔〕。Intx=n*n;While(x>=1){ X=x/2;}O(log2n)O(n)O(nlog2n)O(n1/2)需要分配一個(gè)較大的存儲(chǔ)空間并且插入和刪除操作不需要移動(dòng)，元素滿足以上特點(diǎn)的線性表存儲(chǔ)結(jié)構(gòu)是〔〕。單向鏈表靜態(tài)鏈表線性鏈表順序表字符串S為〞ababcabcacbab〞，模式串T為〞abcac〞。假設(shè)采用KMP算法進(jìn)行模式匹配，那么需要〔〕遍〔趟匹配〕，就能確定T是S的子串。3456某棵二叉樹的前序序列是1,2,3,4，那么不可能為該二叉樹的中序序列的是〔〕。1,2,3,42,3,4,11,4,3,23,1,4,2將森林F轉(zhuǎn)換為對(duì)應(yīng)的二叉樹T，F(xiàn)中任何一個(gè)沒(méi)有右兄弟的結(jié)點(diǎn)，在T中〔〕。沒(méi)有左子樹沒(méi)有右子樹沒(méi)有左子樹和右子樹以上都不對(duì)一個(gè)含有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，在其鄰接矩陣存儲(chǔ)結(jié)構(gòu)中共有〔〕個(gè)零元素。e2en2-2en2-e在一棵高度為2和7階B樹中，所含關(guān)鍵字的個(gè)數(shù)最少是〔〕。57814..精選實(shí)用文檔..精選設(shè)待排序的元素個(gè)數(shù)為n，那么基于比擬的排序最壞情況下的時(shí)間復(fù)雜度的下界為〔〕。log2nnnlog2nn2下面關(guān)于B樹和B+樹的表達(dá)中，不正確的選項(xiàng)是〔〕。B樹和B+樹都能有效地支持隨機(jī)檢索B樹和B+樹都能有效地支持順序檢索B樹和B+樹都是平衡的多路樹B樹和B+樹都可以用于文件的索引結(jié)構(gòu)假設(shè)待排序關(guān)鍵字序列在排序前已按其關(guān)鍵字遞增順序排列，那么采用〔〕方法比擬次數(shù)最少。插入排序快速排序堆排序選擇排序填空題在一棵n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)為 11 。假設(shè)二叉樹的一個(gè)葉結(jié)點(diǎn)是其某子樹的中序遍歷序列中的第一個(gè)結(jié)點(diǎn)，那么它必是該子樹的后序遍歷序列中的第 12 個(gè)結(jié)點(diǎn)。在有n個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行 13 場(chǎng)比賽。在有4033個(gè)葉子結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 14 個(gè)。一個(gè)有向圖G1的反向圖是將G1的所有有向邊取反而得到的有向圖G2，假設(shè)G1和G2的鄰接矩陣分別為A，B，那么A與B的關(guān)系為 15 。N個(gè)頂點(diǎn)e條邊的無(wú)環(huán)路有向圖，假設(shè)采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，那么拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為 16 。在10階B樹中根結(jié)點(diǎn)所包含的關(guān)鍵字最多有 17 個(gè)，最少有 18 個(gè)。在具有12個(gè)結(jié)點(diǎn)的平衡二叉樹〔AVL樹〕中，查找AVL樹中的一個(gè)關(guān)鍵字最多需要 〔18〕次比擬。對(duì)初態(tài)有序的表，最少時(shí)間的排序算法是 〔19〕 。簡(jiǎn)答題在n個(gè)數(shù)據(jù)中找出前K個(gè)最大元素，可以采用堆排序或敗者樹來(lái)實(shí)現(xiàn)。分別說(shuō)明上述兩種實(shí)現(xiàn)方法的根底步驟，并分析每種方法的時(shí)間復(fù)雜度和空間復(fù)雜度。假設(shè)舉辦一個(gè)1000人參加的學(xué)術(shù)會(huì)議，作為會(huì)議報(bào)道組的負(fù)責(zé)人，你會(huì)收到會(huì)務(wù)組為每名參會(huì)者開具的包含其英文名字的注冊(cè)費(fèi)發(fā)票，同時(shí)還會(huì)收到為每位參會(huì)者提供的印有其英文名字的參會(huì)胸牌和其他會(huì)議資料。請(qǐng)答復(fù)以下問(wèn)題：如何有效地把每個(gè)參會(huì)者注冊(cè)費(fèi)發(fā)票和參會(huì)胸牌等其他會(huì)議資料放在一起形成一份參會(huì)資料？如何在會(huì)議報(bào)道日更有效地把每份資料發(fā)放給參會(huì)者？要求：說(shuō)明你所使用的主要技術(shù)和相關(guān)步驟。算法設(shè)計(jì)題按以下要求設(shè)計(jì)算法：描述算法設(shè)計(jì)的根本思想；根據(jù)設(shè)計(jì)思想，采用C或C++或Java語(yǔ)言描述算法；..精選實(shí)用文檔..精選分析算法時(shí)間復(fù)雜度和空間復(fù)雜度。給定一個(gè)n個(gè)整數(shù)的無(wú)序數(shù)組A，設(shè)計(jì)一個(gè)時(shí)間和空間盡可能高效的算法，找出其中第k個(gè)小的整數(shù)：intfindTheKmin(intA[],intn,intk)。給定一棵n個(gè)結(jié)點(diǎn)的二叉排序樹〔即BST〕，每個(gè)結(jié)點(diǎn)均存放一個(gè)整數(shù)，其結(jié)點(diǎn)格式為[lechild][data][rechild]。令half=(BST中的最大值+BST中的最小值)/2。設(shè)計(jì)一個(gè)算法intfindNearMid(BinTree*root)，完成:找出BST中最大和最小以及計(jì)算half的值；返回大于half且與half相差最小的結(jié)點(diǎn)值。II．計(jì)算機(jī)組成原理局部填空在整數(shù)定點(diǎn)機(jī)中，采用1位符號(hào)位，假設(shè)存放器內(nèi)容為10000000，當(dāng)它分別表示為原碼、補(bǔ)碼，及無(wú)符號(hào)數(shù)時(shí)，其對(duì)應(yīng)的真值分別為 1-1 、 1-2 、 1-3 和 1-4 ?！簿檬M(jìn)制表示〕變址尋址和基址尋址的區(qū)別是：在基址尋址中，基址存放器提供 2-1 ，指令提供 2-2 ；而變址尋址中，變址存放器提供 2-3 ，指令提供 2-4。利用 3-1指令進(jìn)行輸入輸出操作的I/O編址方式為統(tǒng)一編址。設(shè)n=16〔不包括符號(hào)位〕，機(jī)器完成一次加和移位各需100ns，那么原碼一位乘最多需 4-1 ns，補(bǔ)碼Booth算法最多需 4-2 ns。CPU從主存取出一條指令并執(zhí)行該指令的時(shí)間叫 5-1 ，它通常包含假設(shè)干個(gè) 5-2 。而后者又包含假設(shè)干個(gè) 5-3 、 5-4 組成多級(jí)時(shí)序系統(tǒng)。選擇題馮·假設(shè)依曼計(jì)算機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器，CPU區(qū)分它們的依據(jù)是〔〕。指令操作碼的譯碼結(jié)果指令和數(shù)據(jù)的尋址方式指令周期的不同階段指令和數(shù)據(jù)所在的存儲(chǔ)單元DMA方式傳送數(shù)據(jù)時(shí)是在〔〕控制的。CPU程序CPU+程序硬件電路總線通信中的同步控制是〔〕。只適合于CPU控制的方式由統(tǒng)一時(shí)序控制的方式只適合于外圍設(shè)備控制的方式只適合于主存以下表達(dá)中〔〕是錯(cuò)誤的。采用微程序控制器的處理器稱為微處理器在微程序編碼中，編碼效率最低的是直接編碼方式在各種微地址形成方式中，增量計(jì)數(shù)法需要的順序控制字段較短CMAR是控制器中存儲(chǔ)地址存放器設(shè)相對(duì)尋址的轉(zhuǎn)移指令占兩個(gè)字節(jié)，第一字節(jié)是操作碼，第二字節(jié)是相對(duì)位移量〔用補(bǔ)碼表示〕，假設(shè)CPU每當(dāng)從存儲(chǔ)器取出一個(gè)字節(jié)時(shí)，即自動(dòng)完成(PC)+1PC。設(shè)當(dāng)前PC的內(nèi)容為2021H，要求轉(zhuǎn)移到2000H地址，那么該轉(zhuǎn)移指令第二字節(jié)的內(nèi)容應(yīng)為〔〕..精選實(shí)用文檔..精選F5HF7H09H0AH簡(jiǎn)答與計(jì)算設(shè)一個(gè)32位微處理器配有16位的外部數(shù)據(jù)總線，時(shí)鐘頻率為50MHz，假設(shè)總線傳輸最短周期為4個(gè)時(shí)鐘周期，試問(wèn)處理器的最大數(shù)據(jù)傳輸率是多少？假設(shè)想提高1倍數(shù)據(jù)傳輸率，可采用什么措施？主機(jī)與I/O傳送數(shù)據(jù)時(shí)，有幾種控制方式，簡(jiǎn)述它們各自的特點(diǎn)，并指出哪種方式的CPU效率最高。設(shè)主存容量為1MB，Cache容量為16KB，每字塊有16個(gè)字，每字32位。假設(shè)Cache采用直接相聯(lián)映像，求出主存地址字段中各段的位數(shù)。假設(shè)Cache采用四路組相聯(lián)映像，求出主存地址字段中各段的位數(shù)。設(shè)階碼取3位，尾數(shù)取6位〔均不包括符號(hào)位〕，按浮點(diǎn)補(bǔ)碼運(yùn)算規(guī)那么計(jì)算：2綜合題設(shè)CPU共有16根地址線，8根數(shù)據(jù)線，并用MREQ作訪存控制信號(hào)〔低電平有效〕，用WR作讀寫控制信號(hào)〔高電平為讀，低電平為寫〕?，F(xiàn)有以下芯片：ROM(2K*8位，8K*8位，32K*8位)RAM(1K*4位，2K*8位，8K*8位，16K*1位，4K*4位)及74138譯碼器和其他門電路〔門電路自定〕。畫出CPU與存儲(chǔ)器的連接圖，要求：存儲(chǔ)器芯片的地址空間分配為：最大4K地址空間空系統(tǒng)程序區(qū)，相鄰的4K地址空間為系統(tǒng)程序工作區(qū)，最小16K地址空間為用戶程序區(qū)；指出選用的存儲(chǔ)芯片類型及數(shù)量；詳細(xì)畫出片選邏輯。設(shè)CPU中各部件及其互相連接關(guān)系如下圖，圖中W是寫控制標(biāo)志，R是讀控制標(biāo)志，R1和R2是暫存器。..精選實(shí)用文檔..精選假設(shè)要求在取指周期由ALU完成(PC)+1PC的操作〔即ALU可以對(duì)它的一個(gè)源操作數(shù)