复旦大学考研计算机961真题答案针对回忆版

1718年两年答案所以我们只能尽量写出更多东西2023年第一局部数据构造向量相对于数组有什么优缺点？优点：可以动态增长长度vectorsvector的迭代器能防止消灭类似数组愈界等等。vector可以。缺点：poppush。(3)当动态长度超过默认安排大小后，要整体重安排、拷贝和施放。〔可使用任一程序设计语言或伪代码，建议先用自然语言描述算法。1。代码：IntCountOfLeaf(BiTreeT) //求二叉树叶子结点个数{if(!T)return0;if(T->lchild==NULL&&T->rchild==NULL)count++; //假设没有左右孩子，则为叶子结点CountOfLeaf(T->lchild); //遍历左子树CountOfLeaf(T->rchild);//遍历右子树returncount;}intmain(BiTreeT){intcount=0; //全局变量count表示叶子结点的个数CountOfLeaf(T); //求二叉树叶子结点个数returncount;}时间简洁度为O(n)2.几乎逆序的数组排序用什么排序算法？写出算法，时间简洁度。主要思想：先将数组先原地倒置，然后再将数组进展冒泡排序。代码：Void Reverse(inta[],n) //逆序函数，将数组中的元素原地倒置{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进展循环{intflag=false; //初始化标志位for(inti=n-1;i>j;i--){if(a[i]<a[i-1]) //假设后面的数小于前面的数，则交换，并修改标志位{swap(a[i],a[i-1]);flag=true;}}if(flag==false)return;//false}}}intsort(inta[],intn){Reverse(a,n); //先将原有数组进展原地逆序BubbleSort(a,n); //再用冒泡排序得出最终结果}时间简洁度：原地逆序的时间简洁度为O(n),冒泡排序在根本有序的状况下时间简洁度也为O(n)O(n)。4.二叉排序树的2种优化方法，并且介绍这两种方法是怎样优化二叉排序树的。①红黑树本质上是一种二叉查找树，但它在二叉查找树的根底上额外添加了一个标记〔颜色O(logn)。②AVLAVL中任何节点的两个子树的1〔gn增加和删除可能需要通过一次或屡次树旋转来重平衡这个树。其次局部csapp1.Amdahl性能分析定律，硬件优化趋势anSN：程序在N个处理器〔总核心数〕相对在单个处理器〔单核〕中的速度提升比1-a=0s=n；当a=0时〔即只有串行，没有并行，最小加速比s=；当n→∞时，极限加速比→11-这个公式说明：增加处理器数、计算负载分布到更多处理器上，可以提高计算速度程序中可并行代码的比例打算你增加处理器〔总核心数〕所能带来的速度提升的上限流水线是怎样提高性能的，会遇到什么问题，解决方法是什么。指令执行根本分为取指，译码，执行，访存，写回，依据存放器的特性可以不断的将一个时序过程分解成假设干个子过程。这样可以提高处理器处理效率，争取在一个时钟周期中完成一条指令。会遇到的问题：包括数据冒险和把握冒险。处理数据冒险时：指令通过了写回阶段，具体做法是在执行阶段插入一个气泡。使用转发来避开数据冒险直接将结果值从流水线阶段传到更早点阶段加载和使用数据冒险而处理把握冒险时，〔有时也称为指令排解〕那两条预存错误的指令。软件优化至关重要，软件优化一般有哪些方法？高级设计。选择适合的算法和数据构造。根本编码原则。避开限制优化的因素，这样编译器就能产生高效的代码。的模块性以获得更大的效率出来时，才将结果存放到数组或全局变量中。3〕低级优化。构造化代码以利用硬件功能。●开放循环，降低开销，并且使进一步的优化成为可能。●通过使用例如多个累积变量和重结合等技术，找到方法提高指令级并行。●用功能性的风格重写条件操作，使得编译承受条件数据传送。什么是高速缓存，存储构造是怎样提高性能的，它和局部性的关系是什么。什么是高速缓存Cache是一种小容量高速缓冲存储器，由快速的SRAM组成，直接制作在CPU芯CPU处于同一个量级。存储构造是怎样提高性能的CPUCache中取得指令和数据，而不必访问慢速的主存。它和局部性的关系是什么〔指令或数据〕很快还会被访问。空间局部性：当前被访问的内容四周的内容很快会被访问。Cache中，良好的时间局部性和空间局部性能提高cache的命中率，削减CPU访存的时间，加快运行虚拟内存的作用，通过什么方式提高虚拟内存的性能。〕DRAM当做局部的虚拟地址空间的缓存;②〔作为内存治理工具〕为每个进程供给了统一的线性地址空间③〔作为内存保护工具〕进程之间不会相互影响；用户程序不能访问内部信息和代码第三局部软件工程瀑布过程的特点①瀑布模型是一种文档驱动模型，模型简洁；②每个阶段都要提交文档承受审查，有质量保证；③阶段之间有挨次性和依靠性；④推迟实现，先进展规律设计再进展物理设计；⑤对需求变更的响应比较困难开闭原则的概念一个软件实体如类、模块和函数应当对扩开放放，对修改关闭。灵敏宣言是什么个体和交互 重于过程与工具可以工作的软件 重于详尽的文档客户合作 重于合同谈判响应变化 重于遵循打算一个场景〔学生毕业申请系统，画出数据流图顶层、0层、1层。结合传感器说明简述软件测试的作用。是不是用例越多越好？为什么？不是越多越好，由于虽然抱负状况下，测试应对系统中全部可能的执行路径进展承受不同级别的掩盖标准，来到达提高测试效率的目的。白盒测试和黑盒测试在用例设计上的区分。白盒测试：测试用例，检查全部规律是否依据预定的要求正确工作。黑盒测试：性，只依据需求规格说明书，检查程序的功能是否符合它的功能要求。2023年考题回忆版第一局部数据构造1.栈的链表实现代码，数组实现与链表性能比较#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;//创立栈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}

栈空用数组和链表实现栈，在出栈和进栈时时间简洁度都为〔，性能几乎一样。希尔排序，关键局部，填空。是否稳定，举例说明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];}}稳定性：不稳定不同的插入排序过程中一样的元素可能在各自的插入排序中移动最终其稳定性就会被打乱。举例：3,2,2(1),1 第一趟排序后：2(1),1,3,2向量相对于数组的区分和有什么优缺点？huffman树压缩效率计算不会考了，可以不看可以先写算法思想typedefstructWNode{intwkey;//wkey为节点消灭的频度structWNode*lchild,*rchild;}WNode,*WTree;floathuffman(WTree,intlen)//lenhuffman编码的每个字符编码位数{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年的局部性定义引用过的数据项本身。〔指令或数据〕很快还会被访问。空间局部性：当前被访问的内容四周的内容很快会被访问。虚拟内存和memorycache的比较CPUCPUCPU访存次数，加快处理速度。做主存，从而扩大主存，确保程序的运行。cache和虚拟内存的区分:储保护等方面。cache和主存之间均有直接访问通路，cache不命中时CPU之间不存在直接的数据通路