作者：chzg99<br />转自：www.CSDN.net<br /><br /><br />2003年度系统设计师（高级程序员）上午试题解析<br /><br />－数据结构篇<br /><br /> <br /><br />陈智罡（chzg99@21cn.com）<br /><br /> <br /><br />数据结构在高程考试中占有很大的比例，掌握好数据结构，对于编程人员来说无疑是内功的修炼。数据结构主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的（全序关系），树(偏序或层次关系)和图（局部有序）是非线性结构。掌握线性表、多维数组、阵列、栈、树、二叉树，图的定义、存储和操作以及常见的排序和查找算法。重点是二叉树和图以及与其相关的算法。对数据结构的复习要求面面俱到，大家应该对教材的每一点都掌握。<br /><br /> 1．关键路径是指AOE(Activity On Edge)网中________。 <br /><br />    A. 最长的回路          B. 最短的回路<br /><br />C. 从源点到汇点(结束顶点)的最长路径<br /><br />D. 从源点到汇点(结束顶点)的最短路径<br /><br />答案：C<br /><br />解析：AOE网是一个有向图，通常用来估算工程的完成时间，图中的顶点表示事件，有向边表示活动，边上的权表示完成这一活动所需的时间。AOE网没有有向回路，存在唯一的入度为零的开始顶点，及唯一的出度为零的结束顶点。对AOE网最关心的两个问题：完成整个工程至少需要多少时间？那些活动是影响工程进度的关键？这就引出两个概念：关键路径和关键活动。从开始顶点到结束顶点的最长路径是关键路径，路径的长度也是工程完成的最少时间。关键路径上的所有活动是关键活动，关键活动的最大特征是：该活动的最早开始时间等于该活动所允许的最迟开始时间。关键活动拖延时间，整个工程也要拖延时间。求关键路径只需求出起点到终点的最长路径即可，注意关键路径不是唯一的。<br /><br />复习提示：类似的考点还有：AOV网、最短路径、最小生成树。<br /><br /> 2．以下序列中不符合堆定义的是________。 <br /><br />A．(102，87，100，79，82，62，84，42，22，12，68) <br /><br />B．(102，100，87，84，82，79，68，62，42，22，12) <br /><br />C．(12，22，42，62，68，79，82，84，87，100，102) <br /><br />D．(102，87，42，79，82，62，68，100，84，12，22)<br /><br />答案：D<br /><br />解析：判断堆的办法就是把序列看成是一棵完全二叉树，若树中的所有非终端结点的值均不大于（或不小于）其左右孩子的结点的值，则该序列为堆。<br /><br />复习提示：考生复习过程中对定义一定要清楚，这是拿分的关键。<br /><br /> 3．一个具有767个结点的完全二叉树，其叶子结点个数为____。 <br /><br />A. 383   B. 384   C. 385   D. 386<br /><br />答案：B<br /><br />解析：可以根据公式进行推导，假设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＝&amp;euml;（n＋1）/2 &amp;ucirc;，就可根据完全二叉树的结点总数计算出叶子结点数。本题计算得：384。<br /><br />复习提示：该记得公式要记住，临时推导也可以，但容易耽误时间。<br /><br /> 4．若一个具有n个结点、k条边的非连通无向图是一个森林(n&gt;k)，则该森林中必有____棵树。 <br /><br />A. k     B. n   C. n-k D. n+k<br /><br />答案：C<br /><br />解析：假设该森林中有s棵树：T1,T2,……,TS ，且每个Ti有ni 个结点，ki条边(i=1,2,……，S),由树的等价条件可知： ki＝ni－1，则k＝k1+k2+……+ks=（n1－1）+（n2－1）＋……＋（ns－1）＝n－s,故s=n－k,所以该森林中必有n－k棵树。<br /><br />复习提示：该题如果清楚树的等价条件，可以很容易的解出。若不清楚，则无法下手。不过考生也可以画出一个具体的非连通无向图的森林，如：5个结点3条边2棵树的森林，也可帮助判断。抽象问题具体化是作选择题的一个重要方法。

楼主是不是准备考高程阿？哦觉得你所提供的都是比较基础的。其实去年考试内容的一大变化或者说是很多人不注意的应该在关于质量保证和版权。如果想复习全面一些，光注意这些基础的东东是不够的，要多看一些新知识才行。<br />还有下午的试题要常练习才行。去年下午的试题没有多大的变化。

<!--QuoteBegin-threehair+2004-04-07 10:03:48--><div class='quotetop'>QUOTE(threehair @ 2004-04-07 10:03:48)</div><div class='quotemain'><!--QuoteEBegin--> 楼主是不是准备考高程阿？哦觉得你所提供的都是比较基础的。其实去年考试内容的一大变化或者说是很多人不注意的应该在关于质量保证和版权。如果想复习全面一些，光注意这些基础的东东是不够的，要多看一些新知识才行。<br />还有下午的试题要常练习才行。去年下午的试题没有多大的变化。 <!--QuoteEnd--></div><!--QuoteEEnd--><br /><!--emo&:wub:--><img src='style_emoticons/default/wub.gif' border='0' style='vertical-align:middle' alt='wub.gif' /><!--endemo-->  三毛 jj 你考过了吗？ <br /><br /> <!--emo&:unsure:--><img src='style_emoticons/default/unsure.gif' border='0' style='vertical-align:middle' alt='unsure.gif' /><!--endemo-->  偶打算 2005 年新考试分类出来再说。。。

哦去年考过了。你可以考今年十月份的那次阿。不用等明年

<!--QuoteBegin-threehair+2004-04-07 10:13:06--><div class='quotetop'>QUOTE(threehair @ 2004-04-07 10:13:06)</div><div class='quotemain'><!--QuoteEBegin--> 哦去年考过了。你可以考今年十月份的那次阿。不用等明年 <!--QuoteEnd--></div><!--QuoteEEnd--><br />偶看过了，今年的考试，都是高级程序员<br /><br /><!--QuoteBegin--><div class='quotetop'>QUOTE</div><div class='quotemain'><!--QuoteEBegin-->下半年考试时间初定为10月10日（如有变动另行通知）；<br /><br />下半年考试级别：初级：网络管理员、程序员<br /><br />　　　　　　　　中级：软件设计师（原高级程序员）、网络工程师（原网络设计师）、数据库系统工程师<br /><br />　　　　　　　　高级：系统分析师（原系统分析员）<br /><br /><!--QuoteEnd--></div><!--QuoteEEnd--><br /><br /><!--QuoteBegin--><div class='quotetop'>QUOTE</div><div class='quotemain'><!--QuoteEBegin-->2005年将全面推开三个级别，20个科目的考试<!--QuoteEnd--></div><!--QuoteEEnd--><br /><br />这些具体科目里面应该有针对嵌入式系统的，偶觉得这样更有针对性一点。

呵呵，看到这个突然想起偶还是2001年的时候就考过了，sigh，以前的高级程序员现在只当个中级资格啦，贬值了<!--emo&:(--><img src='style_emoticons/default/sad.gif' border='0' style='vertical-align:middle' alt='sad.gif' /><!--endemo-->，可是那个系分哪是随便就敢去报考的啊~~

<!--QuoteBegin-threehair+2004-04-07 10:03:48--><div class='quotetop'>QUOTE(threehair @ 2004-04-07 10:03:48)</div><div class='quotemain'><!--QuoteEBegin--> 楼主是不是准备考高程阿？哦觉得你所提供的都是比较基础的。其实去年考试内容的一大变化或者说是很多人不注意的应该在关于质量保证和版权。如果想复习全面一些，光注意这些基础的东东是不够的，要多看一些新知识才行。<br />还有下午的试题要常练习才行。去年下午的试题没有多大的变化。 <!--QuoteEnd--></div><!--QuoteEEnd--><br />我还没打算考，只是先了解一些这方面的东西 <!--emo&:)--><img src='style_emoticons/default/smile.gif' border='0' style='vertical-align:middle' alt='smile.gif' /><!--endemo--> <br /><br />您考过，能否多讲讲相关的东西或者你的心得 <!--emo&:rose:--><img src='style_emoticons/default/rose.gif' border='0' style='vertical-align:middle' alt='rose.gif' /><!--endemo-->  <!--emo&:rose:--><img src='style_emoticons/default/rose.gif' border='0' style='vertical-align:middle' alt='rose.gif' /><!--endemo--> 3X

<!--QuoteBegin-Ego+2004-04-07 14:00:49--><div class='quotetop'>QUOTE(Ego @ 2004-04-07 14:00:49)</div><div class='quotemain'><!--QuoteEBegin--> <!--QuoteBegin-threehair+2004-04-07 10:03:48--><div class='quotetop'>QUOTE(threehair @ 2004-04-07 10:03:48)</div><div class='quotemain'><!--QuoteEBegin--> 楼主是不是准备考高程阿？哦觉得你所提供的都是比较基础的。其实去年考试内容的一大变化或者说是很多人不注意的应该在关于质量保证和版权。如果想复习全面一些，光注意这些基础的东东是不够的，要多看一些新知识才行。<br />还有下午的试题要常练习才行。去年下午的试题没有多大的变化。 <!--QuoteEnd--></div><!--QuoteEEnd--><br />我还没打算考，只是先了解一些这方面的东西 <!--emo&:)--><img src='style_emoticons/default/smile.gif' border='0' style='vertical-align:middle' alt='smile.gif' /><!--endemo--> <br /><br />您考过，能否多讲讲相关的东西或者你的心得 <!--emo&:rose:--><img src='style_emoticons/default/rose.gif' border='0' style='vertical-align:middle' alt='rose.gif' /><!--endemo-->  <!--emo&:rose:--><img src='style_emoticons/default/rose.gif' border='0' style='vertical-align:middle' alt='rose.gif' /><!--endemo--> 3X <!--QuoteEnd--></div><!--QuoteEEnd--><br />不好说。因为今年开始，考试有了很大的改变。所以具体的要看考试大纲比较准确。<br />去年哦考的时候，首先是拿到往年的卷子，大概研究了一下考试内容。<br />不过后来考的时候觉得上午的题目范围越来越广也来越灵活，而且考试的内容从以外的纯粹的从课本上看到的死知识扩展到对知识点的掌握和对知识点在现实中的实践。<br />还有觉得对于新知识、新热点的考察。例如去年的题目中对版权知识、质量的相关知识的比重就比较大。<br />哦的感觉就是除了按照考纲复习相关知识之外，要多注意相关的热点、常识。<br /><br />至于下午的题目，改变不大。但是要动手练习才行