提升软件设计师技能：试题解析与概念概述

本文档主要针对软件设计师考试的试题，涵盖了面向对象技术、数据结构、算法、图论、哈夫曼树、有向图存储、树的性质、二叉树遍历以及分块查找等多个知识点。让我们逐一解析： 1. **面向对象技术：** - 类属是面向对象技术中的一个抽象概念，它通过强调类的共同特性（如属性或行为）来描述一组类，而忽略了与具体对象相关或类型的细节。类属通过变元来表达那些与具体对象无关的部分。 2. **数据结构与存储方式：** - 链式存储结构（如链表）并不保证元素的存储地址与其关键字之间有固定的映射关系，而索引存储结构和散列存储结构（如哈希表）则实现了这种映射，其中散列存储结构的特点即在于此。 3. **循环队列：** - 循环队列中队首元素的位置可以通过计算rear指针与元素个数length的关系来得到，即(rear + 1 - length) mod m，选项C正确。 4. **邻接矩阵的零元素：** - 对于无向图的邻接矩阵，每条边会在两个顶点对应的行和列各出现一次，因此除了主对角线上的元素外，其余均为零。总共有n^2个元素，去掉n条对角线上的元素，剩下(n^2 - n) = (n-1)n = e个零元素，因为e条边。 5. **哈夫曼树：** - 哈夫曼树（最优二叉树）的非叶节点数量总是比叶子节点少1，所以当有9个顶点时，叶子结点个数为9 - 1 = 8，但选项中没有这个选项，可能题目有误。 6. **有向图的入度：** - 邻接矩阵中，一个顶点的入度等于对应行中值为1的元素个数，因为每一条进入该顶点的边都会增加该顶点所在行的一个1。 7. **树的度数与度为0的结点：** - 在度为3的树中，如果有两个度为3的节点和一个度为2的节点，这意味着总共还有3个结点（包括已知的3个）具有非零度数。根据树的性质，所有结点的度数之和等于边的数量，所以树中总的非零度数是3+3+2=8。由于所有结点的度数加起来应该是边的数量的两倍，即2e，所以e=4。因此，度为0的结点数是总结点数减去非零度数，即n - 8 = n - 4 - 2，即n - 6，所以有4个度为0的结点。 8. **二叉树遍历：** - 先根遍历和后根遍历中，x在y之前意味着x可能位于y的左侧，而在后根遍历中x在y之后，这表明x是y的祖先，而不是左右兄弟，也不是后裔。 9. **分块查找的平均查找长度：** - 对于123个元素的线性表，等分为3块意味着每块有大约41个元素。如果采用顺序查找，首先查找索引表确定子块，平均而言，第一次查找找到正确子块的概率是1/3，之后在子块内再查找平均需要41次。所以，分块查找的平均查找长度为1（索引表查找）+ (123/3 - 1) * (1/3 + 1) ≈ 47。 文档内容主要考察了软件设计师应掌握的基础理论，包括面向对象编程、数据结构、图论算法、树的性质和查找算法等，对考生的理论素养和实践能力有一定要求。