情况下需要进行多少次比较?说明理由,并给出一个最好情况下初始排列的Р 实例; Р (2)在最坏的情况下需要进行多少次比较?为什么?并给出此时的一个实例。Р Р Р 4、设 n 为正整数,分析如下程序段中加下划线的语句的执行次数。Р Р int i, j, k, x=0, y=0; Р for (i=1; i<=n; i++) Р for(j=1; j<=i ; j++) Р for(k=1; k<=j ; k++) Р x=x+y; Р Р Р 5、有一棵二叉排序树按先序遍历得到的序列为(50,38,30,45,40,48,70,60,75,Р 80),试画出该平衡二叉树,并求出等概率下的查找成功和查找失败的平均查找长度。Р Р Р 五、写算法(共 50 分,每题 25 分) Р 1、已知顺序表中有 n 个记录,表中记录不依关键字有序排列,编写一算法为该顺序表建立Р 一个有序的索引表(依关键字递增排列),索引表中的每一项应含有记录的关键字和该记录Р 在顺序表中的序号。要求算法的时间复杂度在最好的情况下能达到 O(n)。Р 要求:(1)写出算法的基本思想; Р (2)用熟悉的程序设计语言实现上述算法。Р Р 2、改进有向图的邻接表存储方法,不用遍历整个有向图就可获得某个顶点的出度和入度。Р 编写算法实现改进的有向图邻接表存储。Р 要求:(1)写出算法的基本思想; Р (2)画出下图的改进的有向图邻接表示意图; Р (3)用熟悉的程序设计语言实现上述算法。Р V0 Р V Р V1 3Р V2 Р Р Р 科目名称:程序设计第 4 页共 4 页Р Р科大科院考研网提供中科大、中科院考研真题及答案笔记专业课内部辅导班火热报名中Р2013 年中科院考研真题由科大科院考研网(集,均Р为官方原版。登录网站可获得本科目全套的复习资料。Р中科院考研资料:/ Р中科院考研专业课辅导班:ss/
全文预览
