北工大计算机考研真题答案

说明：此答案是我考研时所做，先整理出来，正确率足够使用（作者是某年学硕专业课第一名，但不保证所有题都正确，请按自己的情况酌情处理。可以从王道，从1995年的开始，但我建议从2003年开始看，因为以前的题太旧了，跟现在的考试风格差别很大，所以我的答案也是从03年开始的。2003年答选择题：CDDCA填空题：9：栈10:n-i+1 12:入度为0 13：14：n^2-2e P->next=21:第一种：a1右孩子是a2，a2右孩子是a3。第二种：a3左孩子是a2，a2左孩子是不画了，麻 =(3^h-1)/(3-32.（1）这种画图的真不想画，不画图了，反正10年后的图我都画了会就 我、再、也、不、画、图、了35.(1)将a[low~high]按x值划分，小于x的面，其他的在后面，并返回最后一个小于x的位intpartition(int{inti=arrange(b,1,n,0);return(j-}五．算法设37.bool returnfalse;returntrue;if(print_x_ancestor(T-{printT->data;returntrue;}elseif(print_x_ancestor(T-{printT->data;returntrue;}return}六.应用设计题ADT数据对象：D={ai|ai∈ElemSet,i基本操作}ADT

void初始条件：小根堆A存操作结果：将元素k向下调void初始条件：小根堆A存操作结果：将元素k向上调void初始条件：小根堆A存操作结果：将小根堆A2004答一选择二填空题：1.数据元素的表示和关系的表2. 5.log2(n+1)- 三解答1.2.3.第一次、、、、、7、908、653、、、、、、7、908、653、、、、、、7、908、653、4.略，有些简单题或者上可以找到的，或者画图题我就不写了 2.(1)1.查找u、v之间的所有简单路径并输记录经过的路0102102310235405054returni;五．应用框架1，如未出现过此单词则加入后需保持字典typedefstructintfreq;//频度structwordnode（3)就是个链表（4)boolgetword(chara[])//一个单词AddToList(chara[],wordlistlist);PrintList(wordlistlist);void{chara[20];}空间复杂度 有n个单词，需O（N），建表O(n^2)，时间复杂度2005答一．选择题二．填空题 425163三．解答（6（2（18，18）(1)图（2）u,v的一条路径则把次路径的瓶颈值与当前最void{if(u==v){if(max<{max=}}for{if{ifminuw边权值{}visited[w]=}}}}（5）main()道路有最大载荷值，货车载重需要小于这个瓶颈值 所以货车应找到瓶颈值最大的道路以载重2006答一．选择题二．填空题1.O(nu+tu) 2.AGOODSTUDENT 3.、、、 4（1）35%13=9，h1(35)=35%11+1=13四．抽象数据类型设ADT数据对象 是具有相同特性的数据元素的集合，每个元素由两部分组成，分别为关键码和性基本操作初始条件：字操作结果：返回字典中元素的个初始条件：字典Dt存操作结果：清空并初始化字操作结果：插入数据A操作结果：删除数据ADt存在，A是字典元素链 结构，方便更2007年答一．解答DFS:acfebd BFS:acefbd 二．算法设计void;print(Tnodes[j].data)}三．方案设计数据库的每个记录一个结点及与之相连的结点，表的属性包括节点值key（主键，与之相关联的各结点值C1,C2，C3...2010年专硕答一．选择题 二．填空队列是一端入另一端出，容易出带权路径总和最小的二叉按照某种规则，对树中的每个结点一次且仅一其关键字与给定值进行比较的记录个数的平均选你还是看王道上那个有答案的吧，虽然错误很多，但有的图我不想画。我只把错误标出来好了四她写的不对，连循环都没typedefenum{RED,WHITE,BLUE}color;voidFlag_Arrange(colora[],intn){inti=0,j=0,k=n-1;casecasecaseBLUE:swap(a[j],a[k]);k--;//蓝色，则和k交换，这里没有j++语句以防交换后a[j]}}2011年专硕答选择5：C三3.（2）深度生成树1-2-3-6-4-5（竖起来五。1.她写的程序逻辑不对，边界也不{intflag=0;for(inti=L.length;i>1;--{flag=for(int{if(L.r[j]key>L{tmp=Lr[j];flag=1;}}if(flag=={}}}2.答案不{for{if{}{

returntrue;//存在回if{return}visited[w]=0;//回溯时取消w的记}}return}第五大题2题，我按照有向图做的，题目给的是无向图，所以回溯时不需要取消记录，我懒得改了，而且这个有向图的算了更好。2012专硕答一。选择BACCD二。更新操作较少，需要随机存方便找到结点的前驱队从树根结点到任意结点的路径长度与该结点上权值的边的权值之和最小的生成对于关键字集合的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等A：1100B:111C:10D:00E:1101F:01（不唯一）0（A,14、0（A9、无穷（C10、无穷|AC、0（A14、0、0（D7（C，10（D，8）|ACD0（E6、0、0、0（C10（E、2）|ACDE0（E6、0、0、0（C10、0|ACDEG0、0、0、0、0（C，10、0|ABCDEGFABCDEFG4、空 、空5（1）8、6、9、3、10、11、14、12、（2）3、6、8、9、10、11、14、12、、（2）0、2、3、5、6、7、8、11、13、（3）1、1、2、3、3、4、5、6、7、7、7、8、8、voidadjust(sqlist{intlow=0,high=L.size-1;while(low<high&&{high--}while(low<high&&{}if{L.data[high]=tmp;}}}2{NODE*p={p=p-}p-}3.（1）每个站点的信息，站点与相邻站点的距离，任两个站点的最短路用图，站点之间的联系跟图类似，图可以求出站点间的最短路链式，效率高且结点信息易更2013学硕答选择题CDABC一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实链式插入和删除数据不需要移动数走不通回溯的过程需要退到上一5.V1V2两个字符串的总长度可能大于字符串的最大长关键字映射成地址后2.（1）不子孙结点在左子兄弟结点在右子3.（2）1-4-7:15；1-2-5-7：30；1-3-6-7：（2）空间上直接插入排序不需额外的空间，快速排序需要递归工作栈，所以直接插入排序的空间性能更好四。{if{}LNodep=(LNode*)malloc(sizeof(LNode));if(H==0){}}2.（1）位置信息、道路信息、两个位置之间的道路、最短路径、通行速（2）采用图的数据结ADT数据对象V：V是具有相同特性的数据元素的集合，即坐标基本操作P：CreateDitu(&D,V,VR初始条件：V是坐标信息，VR是坐标的关系LocateGPS(D,V);}ADT

初始条件：地D存在，V是坐标信息GetMinPath(D,u,v);操作结果：找到u、v之间的最短路c2C功能：在"CProgram"字符串里删除输入的字符并统计个数问题：最后k的值是10，str[10]地址越界344512问题：没释放指2（1）作用：从键盘若干行数据，最长行的数据（可能有多行最长，都）并出入的行号，然后打印出来#include<stdioh>#include<stdlibh>#include<string.h>int{inti,j,n,x=0,index=-1;charline[60];char*buf[70];for(i=1;{n=strlen(line);if(0==n)elseif(n<elseif(n>{for(j=0;j<={}index=-1;x=n;}buf[++indexchar*)malloc(n+2);//多申请一个空间存放行号buf[index][0]=i;//0单元存放行号}for(j=0;j<={}return}

printf("第 行：",buf[j][0]);//行号按数字，单独打2013专硕算法计数排序（题没说知道界限，所以用效率低的方法做的，知道界限可以把时间限制在O(N)）voidcountSort(SqListA,SqList&B){intcount[MAXLEN]={0};for(inti=0;i<A.size;++i){for(int{if{}}}B.size=for(int{}}哈编码长intMaxLenHuffmanCode(HuffmanTreeHT,int{intmax=0,j,num=0;{{}if(max<{}}return}14C语言大//从键盘一个数字，如果没出现过就把出现次数初始化为1，出现过就频度加1，遇到0就输出所有出现Link{intnum;intseq;structLinkvoid{inti=Link*buf=buf->next=NULL;Link*p=NULL;Link*r=NULL;printf("inputainteger\