2004年软件设计师上午试题回顾与解析

本资源是一份2004年上半年的软件设计师（高级程序员）级上午试题，主要涉及面向对象编程、数据结构与算法、图论以及树结构等相关知识点。具体内容包括： 1. 面向对象技术中，类属是一种**抽象机制**，它关注的是类的公共属性或行为，即（1）选项A.包含多态。类属强调与**具体对象无关**的特性，通过变元表示与具体类型相关的部分。 2. 数据结构中具有**索引存储结构**（选项C），如哈希表，特点是数据元素的存储地址与其关键字之间存在映射关系。 3. 循环队列的队首元素位置计算公式为 `(rear + 1 - length) mod m`，因此选项C是正确的。 4. 对于一个简单无向图的邻接矩阵，除了对角线上的元素外，其余元素都是0，因为每条边在矩阵中会被计数两次（一次来自起点，一次来自终点），所以总共有 `n2 - e` 个零元素，选项C。 5. 哈夫曼树的叶子结点数等于非叶结点数加1。对于9个顶点的哈夫曼树，非叶结点数为9-1=8，所以叶子结点数为9，选项D。 6. 在邻接矩阵表示有向图时，顶点i的入度等于第i列中值为1的元素个数，选项D。 7. 在度为3的树中，度数为0的结点被称为叶子结点，由于已知有两个度为3的结点和一个度为2的结点，根据树的性质（所有节点度数之和等于边数加1），可以推算出度为0的结点数为2 * 3 + 1 - (2 + 1) = 4，选项A。 8. 先根遍历（根->左->右）和后根遍历（右->左->根）中，x在y之前且之后，说明x在y的前驱和后继之间，即x是y的**左兄弟**，选项A。 9. 最后部分提到了线性表的分块查找，但没有给出完整的问题，因此这部分内容需要完整的试题题目才能继续分析。 通过这份试题，考生将检验自己的面向对象编程、数据结构优化、图论基础以及二叉树遍历等知识点的掌握程度，对于准备软件设计师考试或希望巩固理论知识的程序员来说，这是一个很好的参考资料。