·天新网首页·加入收藏·设为首页·网站导航
数码笔记本手机摄像机相机MP3MP4GPS
硬件台式机网络服务器主板CPU硬盘显卡
办公投影打印传真
家电电视影院空调
游戏网游单机动漫
汽车新车购车试驾
下载驱动源码
学院开发设计
考试公务员高考考研
业界互联网通信探索
2003年系统设计师(高程)试题解析-数据结构篇
http://www.21tx.com 2004年04月02日 中国软考联盟 陈智罡

1 2 下一页

  数据结构在高程考试中占有很大的比例,掌握好数据结构,对于编程人员来说无疑是内功的修炼。数据结构主要有三个方面的内容:数据的逻辑结构;数据的物理存储结构;对数据的操作(或算法)。通常,算法的设计取决于数据的逻辑结构,算法的实现取决于数据的物理存储结构。逻辑结构有四种基本类型:集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构,许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的(全序关系),树(偏序或层次关系)和图(局部有序)是非线性结构。掌握线性表、多维数组、阵列、栈、树、二叉树,图的定义、存储和操作以及常见的排序和查找算法。重点是二叉树和图以及与其相关的算法。对数据结构的复习要求面面俱到,大家应该对教材的每一点都掌握。

  1.关键路径是指AOE(Activity On Edge)网中________。
  A. 最长的回路 B. 最短的回路
  C. 从源点到汇点(结束顶点)的最长路径
  D. 从源点到汇点(结束顶点)的最短路径

  答案:C

  解析:AOE网是一个有向图,通常用来估算工程的完成时间,图中的顶点表示事件,有向边表示活动,边上的权表示完成这一活动所需的时间。AOE网没有有向回路,存在唯一的入度为零的开始顶点,及唯一的出度为零的结束顶点。对AOE网最关心的两个问题:完成整个工程至少需要多少时间?那些活动是影响工程进度的关键?这就引出两个概念:关键路径和关键活动。从开始顶点到结束顶点的最长路径是关键路径,路径的长度也是工程完成的最少时间。关键路径上的所有活动是关键活动,关键活动的最大特征是:该活动的最早开始时间等于该活动所允许的最迟开始时间。关键活动拖延时间,整个工程也要拖延时间。求关键路径只需求出起点到终点的最长路径即可,注意关键路径不是唯一的。
复习提示:类似的考点还有:AOV网、最短路径、最小生成树。

  2.以下序列中不符合堆定义的是________。
  A.(102,87,100,79,82,62,84,42,22,12,68)
  B.(102,100,87,84,82,79,68,62,42,22,12)
  C.(12,22,42,62,68,79,82,84,87,100,102)
  D.(102,87,42,79,82,62,68,100,84,12,22)
 
  答案:D
 
  解析:判断堆的办法就是把序列看成是一棵完全二叉树,若树中的所有非终端结点的值均不大于(或不小于)其左右孩子的结点的值,则该序列为堆。
复习提示:考生复习过程中对定义一定要清楚,这是拿分的关键。

  3.一个具有767个结点的完全二叉树,其叶子结点个数为____。
  A. 383 B. 384 C. 385 D. 386
 
  答案:B
 
  解析:可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知:n0=n2+1,则n= n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n= 2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2,合并成一个公式:n0=?(n+1)/2 ?,就可根据完全二叉树的结点总数计算出叶子结点数。本题计算得:384。
 
  复习提示:该记得公式要记住,临时推导也可以,但容易耽误时间。





上一篇: 中程-高程-系统分析员的成长经历
下一篇: 高级程序员考试时间安排和参考书推荐

1 2 下一页

关于我们 | 联系我们 | 加入我们 | 广告服务 | 投诉意见 | 网站导航
Copyright © 2000-2011 21tx.com, All Rights Reserved.
晨新科技 版权所有 Created by TXSite.net