2004-2011软件设计师历年真题精华与答案概览

本资源是一份针对软件设计师考试的真题与答案汇总，涵盖了2004年上半年至2011年的考试内容。其中包括面向对象技术的概念、数据结构与算法、队列和哈夫曼树的相关理论、图的存储结构分析、有向图的邻接矩阵表示、树的度数计算、二叉树遍历的理解以及分块查找的平均查找长度计算等多个知识点。 1. 在面向对象技术中，类属是一种**参数多态**机制。类属类关注一组类共享的特性，它通过变元来表达这些特性中与**具体类型无关**的部分，即关注的是类的通用属性，而不是特定对象的行为。 2. 数据结构中，**索引存储结构**的特点在于数据结构中的元素存储地址与其关键字之间存在某种映射关系，这使得可以通过索引快速定位到对应的元素。 3. 循环队列的队首元素的实际位置可以通过公式 `(rear-length + 1) mod m` 计算，因为rear表示队尾元素位置，length表示元素个数，加上1是因为循环队列首元素在队尾之后。 4. 对于一个简单无向图，如果使用邻接矩阵存储，非边（即顶点间不存在连接）的元素将为0。对于n个顶点和e条边的图，共有 `n2 - e` 个零元素，因为每个顶点与其它n-1个顶点之间没有边，共n(n-1)/2个潜在的边，但重复计算了一次，所以减去e。 5. 哈夫曼树（一种构建最优二叉树的方法）的叶子结点个数与总结点数有关，但题目中给出的信息不足以直接计算。通常，哈夫曼树的叶子结点个数等于输入字符集的大小。 6. 在有向图的邻接矩阵中，一个顶点i的入度等于该矩阵第i列中值为1的元素个数，因为矩阵的行代表源结点，列代表目标结点，入度对应的是指向该顶点的边的数量。 7. 度为3的树中，如果有两个度为3的节点和一个度为2的节点，根据树的性质（所有节点度数之和等于边数的两倍减去2），可以推断出度为0的节点数。设度为0的节点为x，则3×2 + 2 + 1 = 2x + 1，解得x=4。 8. 结点x先在先根遍历序列中出现，后在后根遍历序列中出现，说明x是y的**后裔**，因为先根遍历遵循自顶向下的顺序，而后根遍历遵循自底向上的顺序。 9. 在等概率情况下，分块查找将平均分成3块，每块包含约41个元素。由于对索引表采用顺序查找，平均查找长度为：首先查找索引表确定块，然后在子块内顺序查找，平均情况下的查找次数是索引表的平均查找长度加上子块内的查找长度，即3（索引表查找）+ (123/3-1)（子块内查找，减一避免重复计数）= 3 + 40 = 43。因此，平均查找长度为21次，因为3次索引查找相当于一次平均查找。 这份资料为准备软件设计师考试的考生提供了重要的复习材料，覆盖了面向对象编程、数据结构、图论、树结构和查找算法等基础知识，有助于理解和巩固这些关键概念。