復(fù)旦大學(xué)考研計(jì)算機(jī)961真題答案針對(duì)回憶版

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