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

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