1、2018 874數據結構：選擇題1 .D詳解略2 .C解析：外層循環每執行一次，內層循環執行logn次，又因為外層循環 n次，因此總的次數應該是nlogn次3 .B解析：因為順序存儲具有隨機存取（隨機查找）的優點，缺點是插入和刪除需要移動大量元素，對鏈式存儲來說，插入刪除比較快，而對于查處需要遍歷，因此鏈式不一定說比順序存儲塊4 .D解析：因為刪除節點必須前一個結點，這個就可以排除單鏈表。于是 abc排除，選Do （拓 展一下看王道書題目）5 .B解析：n第一個出棧，n前面已經入棧，棧內元素是1-n-1 ，出棧逆序，所以第i個元素就 是n-i+1 ,可以舉例第2個出應該是n-1 ,就是n-2+

2、16 .C解析：n0+n1+n2=666,n0=n2+1; 推出2n2+n1+1=666,完全二叉樹為 1結點數最多有一個。 所以 n1=1 , n2=332 , n0=3337 .A解析：排除法，對 A顯然36<86,94>86,不可能出現在86同一個分支里，故選 A8 .D解析:AC排除，因為AC只有中序排序有序，題目要求從任意節點到根節點，又因為哈夫曼 樹的非葉節點不是關鍵字。選D9 .D10.B解析：樹的先序遍歷序列與其對應的二叉樹的先序遍歷序列相同，書的后續遍歷預期對應的二叉樹的中序遍歷相同10 .B解析：因為BFS只能解決不帶權的單源不帶權最短路徑問題，所以權值相同可以

3、看成無權12.B解析：題目問題：沒有 <v2,v6> 。如下圖，按照拓撲排序算法解決即可13 .A解析：克魯斯卡爾算法，依次將最小且不構成回路的邊加入到集合中14 .A解析：畫出散列表，用除留余數法，算出各個地址，然后偽隨機序列解決沖突，例如H0(70)=5,沖突；H11(70) = (70+5 )%13=10,沖突；H2(70)=(70+8)%13=0,沖突；H 3( 70)= (70+3 )%13=8,存入815 .C解析：直接用公式，n0=0 , n1=1 , n2=2, N h=N h-i+N h-2 + 1,于是可以求出 N3=4 ,所以總的結點數為716 .D解析：顯然

4、，基數排序和初始序列無關，因為基數排序不是基于比較的排序算法17 .A解析：對于多元素排序選出前幾個使用堆排序最佳 二、綜合應用題18 .如圖所示，（ 1 ） 0 ， 01， 010 三個編碼以及以0101 開頭的是不可能有的2）以1 ， 00， 011， 0100 開頭的一定有。19 .int count(AdjList g, int k) int count = 0;for(i=0;i<=n-l;i+)if(i!= k)p = gi. firstarc;while (p) If (p->adjvex = k)count+;p = p->next;return count;

5、20 .解析： int deepesHeight(TreeNode node)If(node=null) return 0;Int lH = deepesHeight(node->lchild);Int rH = deepesHeight(node-rchild);return lH>rH ? lH+1 : rH+1;int Balance(TreeNode node)node->bf = deepesHeight(noed->lchild)- deepesHeight(node->rchild)操作系統1. B解析： 可重入代碼是一種允許多個進程同時訪問的代碼，

6、為了使各個進程所執行的代碼完全相同，故不允許任何進程對其進行修改。2. D解析：在某進程中調用的阻塞原語，則必須在與之相合作的另一進程或其他相關進程中安排喚醒原語，以能喚醒阻塞進程。3. B解析：如圖04. A解析：概念題，直接內存訪問可以不需要cpu控制，進程可以直接讀寫一個外部設備。5. D解析：text段通常是指用來存放程序執行代碼的一塊內存區域。這部分區域的大小在程序運行前就已經確定，并且內存區域通常屬于只讀(某些架構也允許代碼段為可寫，即允許修改程序)°data段通常是指用來存放程序中已初始化的全局變量的塊內存區域。 數據段屬于靜態內存分配。bss (Block Start

7、ed by Symbol)段通常是指用來存放程序中未初始化的全局變量的一塊內存區域。屬于靜態內存分配。堆(heap)是用于存放進程運行中被動態分配的內存段，它的大小并不固定，可動態擴張或縮減。6.解析：題目有歧義。假設原來沒有快表，且 2級頁表假設訪問內存一次時間為t原來：3t (無快表，訪問3次內存)現在：0.75t+0.25*3t=1.5td選項改為大名是原來0.5倍7. D解析：印刷錯誤，23分開塊號應該為 2和3,塊大小75, 55。地址為150和250。因為 分配最大空閑塊給進程p,因此為最差適應法。8. A解析：由題意，邏輯地址為32位，虛擬空間大小為2A32b，又因為每頁大小為

8、4kb(2人12), 所以總的頁表項有 2A (32-12 )個。物理地址 36位為干擾選項。9.B解析：A選項進程切換不會影響頁跟塊的映射關系，c選項訪問權限項應該在pcb中，不應該在頁表中。D頁表10.A解析：時間片用完應降低降低進程優先權，然后換入優先權更高的進程進入就緒隊列11.B解析：當前值為1表示可用資源為1,等待為012.B解析：以行為主序，一頁存 50個數，存滿一行缺一次頁，就會產生50次缺頁。13.B解析：題意意思是只能順序訪問磁塊，所有只有鏈式結構符合題意二.綜合題1.每塊可以裝的地址項：256/4=64直接地址：4*256一級間接索引：2*64*256二級簡介索引：2*6

9、4*64*265最后加起來等于 21309442 .每頁表項數為4kb/4b=2A10 , 64虛地址共有2A64/4kb=2A52頁，最高層頁表占一項，所以最高層的頁表項不超過2A10 , 5<52/10=5.2<6 ，所以就采用6層3 .信號量s表示球筐內還可以放的球數，wb表示球筐內白白球數，bb表示球筐內的黑球數,m限制只有一個操作。Semaphore S=2 wb=0 , bb=0 , m=1男教師女教師男生女生wait(s);wait(s);wait(wb);wait(bb);wait(m);wait(m);wait(m);wait(m);放入白球；放入黑球；拿走白球；

10、拿走黑球；signal(m);signal(m);signal(m);signal(m);signal(wb);signal(wb);signal(S);signal(S);計算機網絡一. 選擇題1. C解析：ARPNET出現在web之前，c錯誤解析：生成多項式位5 位，所以在發送序列4 個 0，然后用模二運算除以11011 ，求出余數發到初始序列后，即為發送序列3. B解析：DF為1不允許分片，超過MTU丟棄分組，需要發送ICMP差錯報文， 即錯誤4. D解析：A類地址前8位為網絡號，后24位為主機號，700+450<2A11=2048所以11位主機號就可以了，同時2A13-2=819

11、0>4092 滿足題意，所以共需8+11=19 位滿足題意5. C解析：概念題解析略，TCP通過差錯檢測和糾正方法來保證可靠性6. C解析：當兩個IP地址不在同一網絡下，需要通過路由器進行通信。因為子網掩碼位144=10010000 ，因為子網掩碼,化為點分十進制位 11111111.11111111.11000000.000000,所以前 18 位位網絡號，所以只需要觀察 4 個選項中前18 位和題給的主機ip 地址是否匹配即可7. D解析：因為題給交換機是全雙工的，需要乘2（算兩個端口），所以24*100M*2+2*1000M*2 = 8.8G8. D概念題，解析略9. A解析：下層為上層提供服務、綜合應用題1.2.解析1）數據量=3000+200=3200bit傳輸時延=3200bit/1Mbps=3.2ms四個路由器加源主機傳送有5次傳輸，傳播時延=1ms*5=5ms （5段鏈路）總時延=3.2*5+5=21ms2）數據量：3000bit+100bit=3100bit傳輸時延：3100bit/1Mbps=3.1ms ,四個路由器加源主機傳送有5次傳輸，傳播時延=