961真題答案針對(duì)回憶版

1、17 18 年 兩年說一下：由于學(xué)校封題，所以只有回憶版，軟工細(xì)節(jié)無法復(fù)現(xiàn)所以只能盡量寫出東西2017 年第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)1. 向量相對(duì)于數(shù)組優(yōu)點(diǎn)：優(yōu)缺點(diǎn)？（1）可以動(dòng)態(tài)增長長度（2） 數(shù)組在內(nèi)存中分配的連續(xù)空間，多次分配后會(huì)有內(nèi)存碎片，而 vectors是動(dòng)態(tài)增長的，不是連續(xù)的，所以不會(huì)出現(xiàn)內(nèi)存碎片，還有 vector 的迭代器能防止出現(xiàn)類似數(shù)組愈界等等。（3）數(shù)組不允許拷貝和賦值，即不能將數(shù)組的內(nèi)容拷貝到其他數(shù)組作為其初始值，但是 vector 可以。缺點(diǎn)：(1)在進(jìn)行刪除，效率較低。(2)只能在末端進(jìn)行 pop 和 push。(3) 當(dāng)動(dòng)態(tài)長度超過默認(rèn)分配大小后，要整體重新分配、拷貝和施

2、放。2.二叉樹計(jì)算葉子節(jié)點(diǎn)算法，時(shí)間復(fù)雜度。（可使用任一程序設(shè)計(jì)語言或偽代碼，建議先用自然語言描述算法）。答：主要：采用遞歸算法，先序遍歷二叉樹的每個(gè)結(jié)點(diǎn)，如果結(jié)點(diǎn)沒有樹和右，則葉子結(jié)點(diǎn)個(gè)數(shù)加 1。代碼：CountOfLeaf ( BiTree T)/求二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)if(!T) return 0;if (T-lchild=NULL&T-rchild=NULL)/如果沒有左右孩子，則為葉子結(jié)點(diǎn)count+;CountOfLeaf ( T-lchild);/遍歷樹CountOfLeaf ( T-rchild);/遍歷右return count;main( BiTree T)/全局變量 cou

3、nt 表示葉子結(jié)點(diǎn)的個(gè)數(shù)count=0;/求二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)CountOfLeaf (T);return count;時(shí)間復(fù)雜度為 O(n)2. 幾乎逆序的數(shù)組排序用什么排序算法？寫出算法，時(shí)間復(fù)雜度。答：前提條件：假定數(shù)組原始幾乎從大到小排列，要將數(shù)組從小到大進(jìn)行排列主要：先將數(shù)組先原地倒置，然后再將數(shù)組進(jìn)行冒泡排序。代碼：a, n)/逆序函數(shù)，將數(shù)組中的元素原地倒置VoidReverse(for(i = 0; i n/2 ;i+)Swap(ai,an - i - 1);n)/冒泡排序void BubbleSort(a,/將j 從 0n-2 進(jìn)行循環(huán)for(j=0;jj;i-)if(ait

4、op = -1;return stack;/判斷棧是否為空1,空;0,非空emptyStack(PSeqStack stack)if(stack-top = -1)return 1;elsereturn 0;pushStack(PSeqStack stack,Elemtype x)/入棧if(stack-top = MAXSIZE-1)return 0;elsestack-top +;stack-datastack-top = x;return 1;popStack(PSeqStack stack,Elemtype &x)/出棧if(emptyStack(stack)return 0;else

5、x = stack-datastack-top;stack-top -;return 1;struct LinkListdaype data;struct LinkList *next;struct stackdaype data;struct stack *next;typedef struct stackStack;/創(chuàng)建棧Stack *s;/初始化棧void init()s=NULL;/判斷棧是否為空Empty()if(s=NULL)return 1;elsereturn 0;判斷棧是否已滿了void full(Stack *s)if(s-top=maxsize-1)maxsize+;s

6、-data=(daype *)malloc(s-data,maxsize);/入棧void Push(daype element)Stack *p = (Stack *)malloc(sizeof(Stack);p-data=element;p-next=s;s=p;/出棧void Pop()if(!Empty(s)s=s-next;elseprf(?？課);用數(shù)組和鏈表實(shí)現(xiàn)棧，在出棧和進(jìn)棧時(shí)時(shí)間復(fù)雜度都為 o（1），性能幾乎相同。排序，關(guān)鍵部分，填空。是否穩(wěn)定，舉例說明3.void SSort(a,n)for(dk=n/2;dk=1;dk=dk/2)for(i=dk+1;i=n;i+)if(

7、Ai0&A0Aj;j=j-dk) Aj+dk=Aj;Aj+dk=A0;穩(wěn)定性：不穩(wěn)定因?yàn)樵诓煌呐判蜻^程中，相同的元素可能在各自的排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂。舉例：3,2,2(1),1第一趟排序后：2(1),1,3,24. 向量相對(duì)于數(shù)組的區(qū)別和優(yōu)缺點(diǎn)？5. huffman 樹壓縮效率計(jì)算不會(huì)考了，可以不看可以先寫算法typedef struct WNodewkey;/wkey 為節(jié)點(diǎn)出現(xiàn)的頻度struct WNode *lchild,*rchild;WNode,*WTree;float huffman(WTree,len)/len 為huffman 編碼的每個(gè)字符編碼位數(shù)front=

8、-1,rear=-1;last=0,level=0;newcount=0,count=0;WTree QMaxSize;Q+rear=tree;WTree p;while(frontwkey;count+=len*p-wkey;if(p-lchild)Q+rear=p-lchild;if(p-rchild)Q+rear=p-rchild;if(front=last)level+;last=rear;float result=newcount/count;returnresult;第二部分 csapp1.優(yōu)化程序性能的方法同 17 年的2.局部性定義局部性的定義：程序傾向于過的數(shù)據(jù)項(xiàng)本身。鄰近于

9、其他過的數(shù)據(jù)項(xiàng)的數(shù)據(jù)項(xiàng)，或者最近時(shí)間局部性：最近被的內(nèi)容（指令或數(shù)據(jù)）很快還會(huì)被?？臻g局部性：當(dāng)前被的內(nèi)容附近的內(nèi)容很快會(huì)被。3. 虛擬內(nèi)存和 memory cache 的比較Cache：一種小容量高速緩沖器，速度較快，接近 CPU；設(shè)置在主存和 CPU之間，通過存放被頻繁速度。的活躍數(shù)據(jù)或程序，減少 CPU 訪存次數(shù)，加快處理虛擬內(nèi)存：并不是物理內(nèi)存，是一種空間管理技術(shù)，將硬盤中的一部分勻出來當(dāng)做主存，從而擴(kuò)大主存，確保程序的運(yùn)行。cache 和虛擬內(nèi)存的區(qū)別:(1)側(cè)重點(diǎn)不同：cache 主要解決主存與 CPU 的速度差異問題；而就性能價(jià)格比的提高而言，虛存主要是解決儲(chǔ)保護(hù)等方面。容量問題

10、，另外還包括管理、主存分配和存(2)數(shù)據(jù)通路不同：CPU 與 cache 和主存之間均有直接通路，cache 不命中時(shí)可直接主存；而虛存所依賴的輔存與 CPU 之間不存在直接的數(shù)據(jù)通路，當(dāng)主存不命中時(shí)只能通過調(diào)頁解決，CPU 最終還是要主存。(3)透明性不同：cache 的管理完全由硬件完成，對(duì)系統(tǒng)程序員和應(yīng)用程序員均透明；而虛存管理由作系統(tǒng)）和硬件共同完成，由于的介入，虛存對(duì)實(shí)現(xiàn)管理的系統(tǒng)程序員不透明，而只對(duì)應(yīng)用程序員透明（段式和段頁式管理對(duì)應(yīng)用程序員“半透明”）。(4)未命中時(shí)的損失不同：由于主存的存取時(shí)間是 cache 的存取時(shí)間的 510 倍，而主存的存取速度通常比輔存的存取速度快上千倍，故主存未命中時(shí)系統(tǒng)的性能損失要遠(yuǎn)大于