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