《北京师大教育技术考研数据结构09答案.doc》由会员分享，可在线阅读，更多相关《北京师大教育技术考研数据结构09答案.doc（4页珍藏版）》请在三一文库上搜索。
1、北京师范大学2009年招收硕士学位研究生入学考试试题答案一、1、时间复杂度分析 冒泡排序的时间复杂度为： T(n) = O(n2) 快速排序的时间复杂度为： T(n) = O(n*log n) （前面的报告中已经有分析说明） 堆 排序的时间复杂度为 ： T(n) = O(n*log n) （ 在最坏的情况下） 堆排序的运行时间主要是耗费在建立初始堆和调整建立新堆的反复筛选上面，在建立初始堆的时候，需要的时间是0(n);因为在建初始堆的时候，调用 Heapify() n/2次，有Heapify()所需要的时间可知道，当i在n/2的到n/4+1的范围内时，每次调用耗费时间为C，C为一常数，当i在n
2、/4到n /8+1的范围内时，耗费的时间为2C，。所以 C(n/4+2*n/8+3*n/16+.)=O(n) 在调整堆的时候，调用Heapify共n-1次，每次调用所需要的时间为O(n)的时间，所以整个算法在最坏的情况下只需要：T(n) = O(n*log n) 的时间。 运行结果和分析 1）当数组的规模都为10000个元素的时候： 冒泡排序所需的时间是：0.625秒；快速排序和堆排序基本上不需要时间（因为规模比较小所以看不出来）。 2）当数组的规模都为100000个元素的时候： 冒泡排序所需要的时间为：69.875秒； 快速排序所需要的时间为：0.047 秒； 堆 排序所需要的时间为：0.0
3、31 秒； 从上面的比较不难看出堆排序要比快速好，快速又要比冒泡排序好。但这时候堆排序和快速排序所花的时间相差不时很多。 3）当数组规模为1000000个元素的时候： 这主要是比较快速排序和堆排序之间的差距，因为当规模这么大时，冒泡排序要花太多时间所以就没有进行比较测试。从结果中可以看到，当数组规模很大的时候， 堆排序的优势就彻底的体现出来了，比快速排序要块很多。所以证明了一点，当数组元素很大的时候，用堆排序时最优的。2、stack: 由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间 heap: 需要程序员自己申请，并指明大小，在c中malloc函数
4、如p1 = (char *)malloc(10); 在C+中用new运算符 如p2 = (char *)malloc(10); 但是注意p1、p2本身是在栈中的。 3、4、参阅各树定义。5、多态性是允许你将父对象设置成为和一个或更多的他的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作EFBHGKAIDJC6、参阅各系统平台二、1、2、请用工作栈遍历次序分析之528134769103、用最小生成树分析之4、5、5230682050607052，686020，307020，3060，7052建成后的树： 删除50后的树 删除68后的树6、【初始关键字】：50
5、3 087 512 061 908 170 897 275 653 426第一趟 ：426 087 275 061 170503 897 908 653 512第二趟 ：170 087 275 061426 503 512 653897 908第三趟 ：061 087170 275 426 503 512 653 897 908第四趟 ：061 087 170 275 426 503 512 653 897 908三、1、 （1） inthreading(p-lchild) （2）p-ltag=thread;p-lchild=pre; （3）pre-rtag=thread;pre-rchild
6、=p; （4）inthreading(p-rchild) 2、i+; j+; C.elemk+=A.elemi;四、1、#include “SeqList.h” template void FindMaxMin(SeqList& A, int& Max, int& Min) Max=Min=A.getData(0); for(int i=1; iMax) Max=A.getData(i); else if(A.getData(i)Min) Min=A.geyData(i); 2解：Status Build_AdjList(ALGraph &G) /输入有向图的顶点数,边数,顶点信息和边的信息建
7、立邻接表 InitALGraph(G); scanf(%d,&v); if(v0) return ERROR; /顶点数不能为负 G.vexnum=v; scanf(%d,&a); if(a0) return ERROR; /边数不能为负 G.arcnum=a; for(m=0;mv;m+) G.verticesm.data=getchar(); /输入各顶点的符号 for(m=1;m=a;m+) t=getchar();h=getchar(); /t为弧尾,h为弧头 if(i=LocateVex(G,t)0) return ERROR; if(j=LocateVex(G,h)nextarc;q=q-nextarc); q-nextarc=p; p-adjvex=j;p-nextarc=NULL; /while return OK; /Build_AdjList4