2004年软件设计师考试真题解析

"2004年软件设计师考试的上午真题，包含了面向对象技术、数据结构、队列、图的存储、哈夫曼树、有向图的入度、树的节点度数、二叉树遍历等计算机科学的基础概念和问题。" 本题目是2004年上半年软件设计师（高级程序员）级的上午考试试卷的一部分，主要涉及了多个计算机科学的关键知识点。以下是各个问题的解析： 1. 类属（Class-Scheme）是一种参数多态（B）机制，它允许通过参数化类来创建一系列相关的类，这些类共享一部分相同的行为，但可以通过不同的参数（变元）实现差异化的功能。 2. 类属类强调的是与具体类型无关（B）的成员特征，即这些特征对任何符合类属定义的类都适用，而变元代表与具体类型相关的部分，可以被不同类型的实例所替换。 3. 数据结构中，散列存储结构（D）的特点是元素的存储地址与关键字之间存在映射关系，例如哈希表就是基于这种思想实现的。 4. 循环队列的队首元素实际位置计算，如果rear表示队尾，length表示元素个数，那么队首位置可以通过(B) (rear-length+m) mod m 计算得出。 5. 在邻接矩阵存储的简单无向图中，非零元素表示边，所以零元素的个数为矩阵的总元素数减去边的数量两次，即 n^2 - 2e（C），其中n是顶点数，e是边数。 6. 哈夫曼树（Huffman Tree）的性质表明，叶子节点的个数等于总节点数减一，若总节点数为9，则叶子节点数为9 - 1 = 8（D）。 7. 一个顶点i在有向图的邻接矩阵中的入度等于第i列中值为1的元素个数（D），因为入度表示指向该顶点的边数。 8. 在度为3的树中，如果有2个度为3的节点，1个度为2的节点，根据树的性质，节点度数之和乘以2等于边数，即(2*3 + 1*2 + d0*0) = 2e，其中d0为度为0的节点数，解得d0 = 5（B）。 9. 在二叉树的先根遍历和后根遍历中，x在y之前但在后根遍历中在y之后，表明x是y的祖先（C），因为先根遍历先访问根节点再遍历左右子树，而后根遍历则先遍历子树再访问根节点。 10. 线性表按分块查找，索引表顺序查找确定子块，这种情况下讨论的是索引顺序查找的效率和实现方式。 这些题目涵盖了计算机科学基础中的核心概念，包括数据结构（如队列、图、树）、算法（如哈夫曼编码、二叉树遍历）以及面向对象编程中的多态性。这样的考试旨在检验考生对于计算机科学基础知识的掌握程度和应用能力。