復旦大學考研計算機961真題答案針對回憶版

1718年兩年答案所以我們只能盡量寫出更多東西2023年第一局部數(shù)據(jù)構(gòu)造向量相對于數(shù)組有什么優(yōu)缺點？優(yōu)點：可以動態(tài)增長長度vectorsvector的迭代器能防止消滅類似數(shù)組愈界等等。vector可以。缺點：poppush。(3)當動態(tài)長度超過默認安排大小后，要整體重安排、拷貝和施放。〔可使用任一程序設(shè)計語言或偽代碼，建議先用自然語言描述算法。1。代碼：IntCountOfLeaf(BiTreeT) //求二叉樹葉子結(jié)點個數(shù){if(!T)return0;if(T->lchild==NULL&&T->rchild==NULL)count++; //假設(shè)沒有左右孩子，則為葉子結(jié)點CountOfLeaf(T->lchild); //遍歷左子樹CountOfLeaf(T->rchild);//遍歷右子樹returncount;}intmain(BiTreeT){intcount=0; //全局變量count表示葉子結(jié)點的個數(shù)CountOfLeaf(T); //求二叉樹葉子結(jié)點個數(shù)returncount;}時間簡潔度為O(n)2.幾乎逆序的數(shù)組排序用什么排序算法？寫出算法，時間簡潔度。主要思想：先將數(shù)組先原地倒置，然后再將數(shù)組進展冒泡排序。代碼：Void Reverse(inta[],n) //逆序函數(shù)，將數(shù)組中的元素原地倒置{for(i=0;i<n/2;i++){Swap(a[i],a[n-i-1]);}}voidBubbleSort(inta[],intn) //冒泡排序{for(j=0;j<n-2;j++) //j0~n-2進展循環(huán){intflag=false; //初始化標志位for(inti=n-1;i>j;i--){if(a[i]<a[i-1]) //假設(shè)后面的數(shù)小于前面的數(shù)，則交換，并修改標志位{swap(a[i],a[i-1]);flag=true;}}if(flag==false)return;//false}}}intsort(inta[],intn){Reverse(a,n); //先將原有數(shù)組進展原地逆序BubbleSort(a,n); //再用冒泡排序得出最終結(jié)果}時間簡潔度：原地逆序的時間簡潔度為O(n),冒泡排序在根本有序的狀況下時間簡潔度也為O(n)O(n)。4.二叉排序樹的2種優(yōu)化方法，并且介紹這兩種方法是怎樣優(yōu)化二叉排序樹的。①紅黑樹本質(zhì)上是一種二叉查找樹，但它在二叉查找樹的根底上額外添加了一個標記〔顏色O(logn)。②AVLAVL中任何節(jié)點的兩個子樹的1〔gn增加和刪除可能需要通過一次或?qū)掖螛湫D(zhuǎn)來重平衡這個樹。其次局部csapp1.Amdahl性能分析定律，硬件優(yōu)化趨勢anSN：程序在N個處理器〔總核心數(shù)〕相對在單個處理器〔單核〕中的速度提升比1-a=0s=n；當a=0時〔即只有串行，沒有并行，最小加速比s=；當n→∞時，極限加速比→11-這個公式說明：增加處理器數(shù)、計算負載分布到更多處理器上，可以提高計算速度程序中可并行代碼的比例打算你增加處理器〔總核心數(shù)〕所能帶來的速度提升的上限流水線是怎樣提高性能的，會遇到什么問題，解決方法是什么。指令執(zhí)行根本分為取指，譯碼，執(zhí)行，訪存，寫回，依據(jù)存放器的特性可以不斷的將一個時序過程分解成假設(shè)干個子過程。這樣可以提高處理器處理效率，爭取在一個時鐘周期中完成一條指令。會遇到的問題：包括數(shù)據(jù)冒險和把握冒險。處理數(shù)據(jù)冒險時：指令通過了寫回階段，具體做法是在執(zhí)行階段插入一個氣泡。使用轉(zhuǎn)發(fā)來避開數(shù)據(jù)冒險直接將結(jié)果值從流水線階段傳到更早點階段加載和使用數(shù)據(jù)冒險而處理把握冒險時，〔有時也稱為指令排解〕那兩條預存錯誤的指令。軟件優(yōu)化至關(guān)重要，軟件優(yōu)化一般有哪些方法？高級設(shè)計。選擇適合的算法和數(shù)據(jù)構(gòu)造。根本編碼原則。避開限制優(yōu)化的因素，這樣編譯器就能產(chǎn)生高效的代碼。的模塊性以獲得更大的效率出來時，才將結(jié)果存放到數(shù)組或全局變量中。3〕低級優(yōu)化。構(gòu)造化代碼以利用硬件功能?！耖_放循環(huán)，降低開銷，并且使進一步的優(yōu)化成為可能。●通過使用例如多個累積變量和重結(jié)合等技術(shù)，找到方法提高指令級并行?！裼霉δ苄缘娘L格重寫條件操作，使得編譯承受條件數(shù)據(jù)傳送。什么是高速緩存，存儲構(gòu)造是怎樣提高性能的，它和局部性的關(guān)系是什么。什么是高速緩存Cache是一種小容量高速緩沖存儲器，由快速的SRAM組成，直接制作在CPU芯CPU處于同一個量級。存儲構(gòu)造是怎樣提高性能的CPUCache中取得指令和數(shù)據(jù)，而不必訪問慢速的主存。它和局部性的關(guān)系是什么〔指令或數(shù)據(jù)〕很快還會被訪問?？臻g局部性：當前被訪問的內(nèi)容四周的內(nèi)容很快會被訪問。Cache中，良好的時間局部性和空間局部性能提高cache的命中率，削減CPU訪存的時間，加快運行虛擬內(nèi)存的作用，通過什么方式提高虛擬內(nèi)存的性能?！矰RAM當做局部的虛擬地址空間的緩存;②〔作為內(nèi)存治理工具〕為每個進程供給了統(tǒng)一的線性地址空間③〔作為內(nèi)存保護工具〕進程之間不會相互影響；用戶程序不能訪問內(nèi)部信息和代碼第三局部軟件工程瀑布過程的特點①瀑布模型是一種文檔驅(qū)動模型，模型簡潔；②每個階段都要提交文檔承受審查，有質(zhì)量保證；③階段之間有挨次性和依靠性；④推遲實現(xiàn)，先進展規(guī)律設(shè)計再進展物理設(shè)計；⑤對需求變更的響應比較困難開閉原則的概念一個軟件實體如類、模塊和函數(shù)應當對擴開放放，對修改關(guān)閉。靈敏宣言是什么個體和交互 重于過程與工具可以工作的軟件 重于詳盡的文檔客戶合作 重于合同談判響應變化 重于遵循打算一個場景〔學生畢業(yè)申請系統(tǒng)，畫出數(shù)據(jù)流圖頂層、0層、1層。結(jié)合傳感器說明簡述軟件測試的作用。是不是用例越多越好？為什么？不是越多越好，由于雖然抱負狀況下，測試應對系統(tǒng)中全部可能的執(zhí)行路徑進展承受不同級別的掩蓋標準，來到達提高測試效率的目的。白盒測試和黑盒測試在用例設(shè)計上的區(qū)分。白盒測試：測試用例，檢查全部規(guī)律是否依據(jù)預定的要求正確工作。黑盒測試：性，只依據(jù)需求規(guī)格說明書，檢查程序的功能是否符合它的功能要求。2023年考題回憶版第一局部數(shù)據(jù)構(gòu)造1.棧的鏈表實現(xiàn)代碼，數(shù)組實現(xiàn)與鏈表性能比較#defineMAXSIZE100//棧的順式儲存類型typedefstruct{Elemtypedata[MAXSIZE];inttop;}SeqStack,*PSeqStack;//棧的初始化PSeqStackinitSeqStack{PSeqStackstack;stack=(PSeqStack)malloc(sizeof(SeqStack));stack->top=-1;returnstack;}//推斷棧是否為空 1,空;0,非空intemptyStack(PSeqStackstack){if(stack->top==-1){return1;}else{return0;}}intpushStack(PSeqStackstack,Elemtypex){//入棧if(stack->top==MAXSIZE-1){return0;}else{stack->top++;stack->data[stack->top]=x;return1;}}intpopStack(PSeqStackstack,Elemtype&x){//出棧if(emptyStack(stack)){return0;}else{x=stack->data[stack->top];stack->top--;return1;}}structLinkList{datatypedata;structLinkList*next;};structstack{datatypedata;structstack*next;};typedefstructstackStack;//創(chuàng)立棧Stack*s;//初始化棧voidinit{s=NULL;}//推斷棧是否為空intEmpty{if(s==NULL)return1;else}

return0;推斷棧是否已滿了voidfull(Stack*s){if(s->top==maxsize-1){maxsize++;s->data=(datatype*)malloc(s->data,maxsize);}}//入棧voidPush(datatypeelement){Stack*p=(Stack*)malloc(sizeof(Stack));p->data=element;p->next=s;s=p;}//出棧voidPop{if(!Empty(s))s=s->next;else}

?？沼脭?shù)組和鏈表實現(xiàn)棧，在出棧和進棧時時間簡潔度都為〔，性能幾乎一樣。希爾排序，關(guān)鍵局部，填空。是否穩(wěn)定，舉例說明voidShellSort(inta[],intn){for(dk=n/2;dk>=1;dk=dk/2)for(i=dk+1;i<=n;i++)if(A[i]<A[i-dk]){A[0]=A[i];for(j=i-dk;j>0&&A[0]<A[j];j=j-dk)A[j+dk]=A[j];A[j+dk]=A[0];}}穩(wěn)定性：不穩(wěn)定不同的插入排序過程中一樣的元素可能在各自的插入排序中移動最終其穩(wěn)定性就會被打亂。舉例：3,2,2(1),1 第一趟排序后：2(1),1,3,2向量相對于數(shù)組的區(qū)分和有什么優(yōu)缺點？huffman樹壓縮效率計算不會考了，可以不看可以先寫算法思想typedefstructWNode{intwkey;//wkey為節(jié)點消滅的頻度structWNode*lchild,*rchild;}WNode,*WTree;floathuffman(WTree,intlen)//lenhuffman編碼的每個字符編碼位數(shù){intfront=-1,rear=-1;intlast=0,level=0;intnewcount=0,count=0;WTreeQ[MaxSize];Q[++rear]=tree;WTreep;while(front<rear){p=Q[++front];newcount+=level*p->wkey;count+=len*p->wkey;if(p->lchild)Q[++rear]=p->lchild;if(p->rchild)Q[++rear]=p->rchild;if(front==last){level++;last=rear;}}floatresult=newcount/count;returnresult;}其次局部csapp年的局部性定義引用過的數(shù)據(jù)項本身?！仓噶罨驍?shù)據(jù)〕很快還會被訪問?？臻g局部性：當前被訪問的內(nèi)容四周的內(nèi)容很快會被訪問。虛擬內(nèi)存和memorycache的比較CPUCPUCPU訪存次數(shù)，加快處理速度。做主存，從而擴大主存，確保程序的運行。cache和虛擬內(nèi)存的區(qū)分:儲保護等方面。cache和主存之間均有直接訪問通路，cache不命中時CPU之間不存在直接的數(shù)據(jù)通路