中科院考研程序设计试题

所需积分/C币:34 2015-09-08 18:06:01 153KB PDF
4
收藏 收藏
举报

2013年中国科学院大学的考研程序设计真题,可以帮助大家复习
4、设关键字序列为{3,7,6,9,7,1,4,5,20},对其进行排序的最小交换次数是【 5、将一个nXn的对称矩阵A的下三角部分按行存放在一个一维数组B中,A[01[O存放于 B|0中,那么第i行的对角元素A[[在B中的存放位置是【 6、在一棵度为4的树中,有20个度为4的结点,10个度为3的结点,1个度为2的结点, 10个度为1的结点,则树中度为0的结点个数为【 7、在n个结点的线索二叉树中,线索的数目是【 8、由权值为8,4,5,7的4个叶结点构造一棵 Huffman树,该树的带权路径长度为 9、中缀表达式A-(B+CD)*E的后缀形式是【 四、问答题(共50分,每题10分) 1、试利用 Dijkstra算法求下图中从顶点a到其它各顶点间的最短路径,写出执行算法过程 中各步的状态。 d+5-(f 2、在地址空间为0~-16的散列区中,对以下关键字序列构造两个哈希表: (Jan, Fcb, Mar, Apr, May, Junc, July, Aug, Scp, Oct, Nov, Dcc (1)用线性探测开放定址法处理沖突; (2)用链地址法处理冲突; 并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。设哈希函数为 H(x)-L2,其中i为关键字中第一个字母在字母表中的序号 科目名称:程序设计 第3页共4页 3、对一个具有7个记录的文件进行快速排序,回答下面的问题: (1)在最好的情况下需要进行多少次比较?说明理由,并给出一个最好情况下初始排列的 实例; (2)在最坏的情况下需要进行多少次比较?为什么?并给出此时的一个实例。 4、设n为正整数,分析如下程序段中加下划线的语句的执行次数。 k x for(i=1;1<=n;i++) fo(-1;j<-i;j++) for(k=1;k<=;x++) x=X+ 5、有一棵二义排序树按先序遍历得到的序列为(50,38,30,45,40,48,70,60,75, 80),试面出该平衡二叉树,并求出等概率下的查找成功和香找失败的平均查找长度。 五、写算法(共50分,每题25分) 1、已知顺序表中有n个记表中记录不依关键字有序排列,编写一算法为该顺序表建立 个有序的索引表(依关键字递增排列),索引表中的每一项应含有记录的关键字和该记录 在顺序表中的序号。要求算法的时间复余度在最好的情况下能达到O(n) 要求:(1)写出算法的基本思想 (2)用熟悉的程局设计语言实现上述算法。 2、改进有向图的接表存储方法,不用遍历整个有向图就可获得某个顶点的出度和入度。 编写算法实现或进的有向图邻接表存储 要求:(1与出算法的基本思想 (2)画出下图的改进的有向图邻接表示意图 (3)用熟悉的程序设计语言实现上述算法。 0 科目名称:程序设计 第4页共4页

...展开详情
试读 4P 中科院考研程序设计试题
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
上传资源赚积分or赚钱
    最新推荐
    中科院考研程序设计试题 34积分/C币 立即下载
    1/4
    中科院考研程序设计试题第1页

    试读结束, 可继续读1页

    34积分/C币 立即下载 >