本资料为2018年重庆邮电大学802数据结构考试的真实试题，以PDF格式提供，并保证清晰度与原貌呈现，适合备考学生参考使用。
在提供的文件内容中可以看到涉及的是数据结构相关的考试题目，其中包含了一系列关于基础概念、算法及应用的选择题与填空题。
### 选择题知识点总结
1. **时间复杂度**：衡量算法运行时间的增长趋势的指标，在本例中的程序段的时间复杂度为O(log3n)，即随着输入规模n增大，其增长速度与对数函数成正比。
2. **顺序表操作**：在插入或删除元素时需要移动平均n/2个元素（假设选项B代表此值）。
3. **循环队列**：使用取模运算计算循环队列中的元素数量（选择题A正确反映这一点）。
4. **栈与队列的应用场景**：问题中提到十进制到八进制转换最适合用栈来实现。
5. **特定输出序列的生成条件**：当已知出栈的第一个元素为n时，后续元素必须符合一定顺序（选项C描述正确情况）。
6. **二叉树和栈的操作限制**：问题中提到的错误操作是违反了后进先出的原则（即选项B所指情形）。
7. **特殊的二叉树结构**：当一个结点没有右孩子时，其先序遍历序列与后续遍历序列相反。
8. **完全二叉树节点数量计算**：通过公式2^(k-1)可以确定至少拥有的节点数（选项C正确）。
9. **只有度为0和2的二叉树**：使用公式2^h来计算这种特殊情况下最大可能的结点数目。
10. **数组元素地址计算方法**：按行优先存放时，特定位置的数据可以通过一定的算法获得其内存地址（需要理解相关概念）。
11. **最小生成树特性**：当无向连通图存在唯一的一颗最小生成树时，这一结论是正确的。
12. **邻接表表示的图形结构特征**：讨论了使用链式存储方式来实现无向图的数据结构。
13. **二叉树中的祖先关系判断**：在特定遍历顺序中，x结点为y结点后代的情况（选项D正确）。
14. **路径和度数的关系描述**：非连通图的边数与顶点数之间没有直接相关性。
15. **快速排序算法的应用场景**：字符串类型的序列在特定条件下可以高效地通过快速排序进行处理，需要理解其工作原理（选项B正确）。
### 填空题知识点总结
1. **顺序查找的平均长度计算**：等概率情况下成功完成一次搜索所需的比较次数。
2. **最优排序算法的选择依据**：当数据项接近于它们最终位置时，选择最合适的排序方法以节省时间（例如插入排序）。
3. **非连通图边数与顶点数量的关系描述**
4. **循环队列为空的条件判断**：基于头尾指针的位置来确定是否为空
5. **大根堆中最小元素位置确认**：此类问题的答案通常在叶节点处找到（选项为“叶结点”）。
6. **后缀表达式求值方法的应用**
以上知识点涵盖了考试中的关键概念和算法，考生需要熟练掌握这些基础知识以便于快速准确地解答相关题目。
5星
